Monotone paths in dense edge-ordered graphs. (English) Zbl 1370.05111

Milans, Kevin G.

J. Comb. 8, No. 3, 423-437 (2017).

Summary: The altitude of a graph \(G\), denoted \(f(G)\), is the largest integer \(k\) such that under each ordering of \(E(G)\), there exists a path of length \(k\) which traverses edges in increasing order. V. Chvátal and J. Komlós [Can. Math. Bull. 14, 151–157 (1971; Zbl 0214.23503)] asked for \(f(K_n)\), where \(K_n\) is the complete graph on \(n\) vertices. R. L. Graham and D. J. Kleitman [Period. Math. Hung. 3, 141–148 (1973; Zbl 0243.05116)] proved that \(f(K_n)\geq \sqrt{n-3/4}-1/2\) and A. R. Calderbank et al. [Discrete Math. 50, 15–28 (1984; Zbl 0542.05058)] proved that \(f(K_n)\leq (\frac{1}{2}+o(1))n\). We show that \(f(K_n)\geq (\frac{1}{20}-o(1))(n/\lg n)^{2/3}\).

MSC:

05C38	Paths and cycles
05C42	Density (toughness, etc.)
05C35	Extremal problems in graph theory
05C15	Coloring of graphs and hypergraphs