Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs. (English) Zbl 0542.05058

Calderbank, A. R.; Chung, F. R. K.; Sturtevant, D. G.

Discrete Math. 50, 15-28 (1984).

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

MSC:

05C99	Graph theory
05A05	Permutations, words, matrices
05C35	Extremal problems in graph theory

Keywords:

increasing sequence; increasing edge labels; labelled graphs; complete graph

References:

[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