Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs

Journal Article (Journal Article)

Consider the maximum length f(k) of a (lexicographically) increasing sequence of vectors in GF(2) with the property that the sum of the vectors in any consecutive subsequence is nonzero modulo 2. We prove that 23 48 · 2 ≤ f(k) ≤ ( 1 2 + o(1))2 . A related problem is the following. Suppose the edges of the complete graph K are labelled by the numbers 1,2,..., ( ). 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. k k k n n 2

Full Text

Duke Authors

Cited Authors

  • Calderbank, AR; Chung, FRK; Sturtevant, DG

Published Date

  • January 1, 1984

Published In

Volume / Issue

  • 50 / C

Start / End Page

  • 15 - 28

International Standard Serial Number (ISSN)

  • 0012-365X

Digital Object Identifier (DOI)

  • 10.1016/0012-365X(84)90031-1

Citation Source

  • Scopus