zbMATH — the first resource for mathematics

Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs. (English) Zbl 0542.05058
Suppose we label the edges of the complete graph on n vertices with distinct integer labels. How long a simple increasing path must exist in the resulting graph if the labeling is done diabolically to keep such paths down? In this paper it is shown that the longest path can be forced to have only a few more than half the vertices for large n, this improves the previous bound of 7n/12. The best lower bound on how long a path can be found is much lower. It is also shown that between 23/48ths and a little more than half the vertices of the n cube, each represented as a binary sequence of length n, can be ordered in increasing order, considering the sequences as numbers, so that any consecute sequence in the ordering has some component that sums to an odd number. This latter result is obtained by recursion relating the maximum length with the same where the last condition is applied only to even length sequences. It is used to derive the first result mentioned here.
Reviewer: D.Kleitman

05C99 Graph theory
05A05 Permutations, words, matrices
05C35 Extremal problems in graph theory
Full Text: DOI
[1] B. Alspach, K. Heinrich, and R. L. Graham, Personal communication.
[2] Chvátal, V.; Komlós, J., Some combinatorial theorems on monotonicity, Canad. math. bull., 14, (1971) · Zbl 0214.23503
[3] Graham, R.L.; Kleitman, D.J., Increasing paths in edge-ordered graphs, Per. math. hung., 3, 141-148, (1973) · Zbl 0243.05116
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.