✦ LIBER ✦
Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
✍ Scribed by A.R. Calderbank; F.R.K. Chung; D.G. Sturtevant
- Publisher
- Elsevier Science
- Year
- 1984
- Tongue
- English
- Weight
- 622 KB
- Volume
- 50
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
Consider the maximum length [(k) of a flexicographieally) 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 ~. 2 k ~<f(k)~<(~+o(1))2 k.
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 a(n), over all edge labellings, of the maximum length of a simple path with increasing edge labels? We prove that a (n)~< (21 + o(1))n.