Contents Online

# Journal of Combinatorics

## Volume 8 (2017)

### Number 3

Guest Editor: Steve Butler (Iowa State University)

### Monotone paths in dense edge-ordered graphs

Pages: 423 – 437

DOI: https://dx.doi.org/10.4310/JOC.2017.v8.n3.a2

#### Author

#### Abstract

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. In 1971, Chvátal and Komlós asked for $f(K_n)$, where $K_n$ is the complete graph on $n$ vertices. In 1973, Graham and Kleitman proved that $f(K_n) \geq \sqrt{n - 3/4} - 1/2$ and in 1984, Calderbank, Chung, and Sturtevant 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/ \mathrm{lg} \: n)}^{2/3}$.

Received 13 October 2015

Published 21 June 2017