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

Publication
, Journal Article

Calderbank, AR; Chung, FRK; Sturtevant, DG

Published in: Discrete Mathematics

January 1, 1984

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.

### Duke Scholars

## Published In

Discrete Mathematics

## DOI

## ISSN

0012-365X

## Publication Date

January 1, 1984

## Volume

50

## Issue

C

## Start / End Page

15 / 28

## Related Subject Headings

- Computation Theory & Mathematics
- 4904 Pure mathematics
- 4901 Applied mathematics
- 0802 Computation Theory and Mathematics
- 0102 Applied Mathematics
- 0101 Pure Mathematics

### Citation

APA

Chicago

ICMJE

MLA

NLM

Calderbank, A. R., Chung, F. R. K., & Sturtevant, D. G. (1984). Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs.

*Discrete Mathematics*,*50*(C), 15–28. https://doi.org/10.1016/0012-365X(84)90031-1Calderbank, A. R., F. R. K. Chung, and D. G. Sturtevant. “Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs.”

*Discrete Mathematics*50, no. C (January 1, 1984): 15–28. https://doi.org/10.1016/0012-365X(84)90031-1.Calderbank AR, Chung FRK, Sturtevant DG. Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs. Discrete Mathematics. 1984 Jan 1;50(C):15–28.

Calderbank, A. R., et al. “Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs.”

*Discrete Mathematics*, vol. 50, no. C, Jan. 1984, pp. 15–28.*Scopus*, doi:10.1016/0012-365X(84)90031-1.Calderbank AR, Chung FRK, Sturtevant DG. Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs. Discrete Mathematics. 1984 Jan 1;50(C):15–28.

## Published In

Discrete Mathematics

## DOI

## ISSN

0012-365X

## Publication Date

January 1, 1984

## Volume

50

## Issue

C

## Start / End Page

15 / 28

## Related Subject Headings

- Computation Theory & Mathematics
- 4904 Pure mathematics
- 4901 Applied mathematics
- 0802 Computation Theory and Mathematics
- 0102 Applied Mathematics
- 0101 Pure Mathematics