# zbMATH — the first resource for mathematics

Monotone paths in dense edge-ordered graphs. (English) Zbl 1370.05111
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
Full Text: