Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235793] of Robert Calderbank

Papers Published

  1. Calderbank, AR; Chung, FRK; Sturtevant, DG, Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs, Discrete Mathematics, vol. 50 no. C (1984), pp. 15-28, ISSN 0012-365X
    (last updated on 2017/12/15)

    Abstract:
    Consider the maximum length f(k) of a (lexicographically) increasing sequence of vectors in GF(2)k with the property that the sum of the vectors in any consecutive subsequence is nonzero modulo 2. We prove that 23 48 · 2k ≤ f(k) ≤ ( 1 2 + o(1))2k. A related problem is the following. Suppose the edges of the complete graph Kn are labelled by the numbers 1,2,..., (2n). What is the minimum α(n), over all edge labellings, of the maximum length of a simple path with increasing edge labels? We prove that α(n) ≤ ( 1 2 + o(1))n. © 1984.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320