The ACO Seminar (2015–2016)

In a graph whose edges are are totally ordered, a monotone path is a path that traverses edges in increasing order. Let f(G) be the minimum, over all total orderings of E(G), of the maximum length of a monotone path in G. In 1973, Graham and Kleitman proved that f(K_n) ≥ (sqrt{4n-3} - 1)/2. The best known upper bound on f(K_n) is due to Calderbank, Chung, and Sturtevant, who proved that f(K_n) ≤ (½ + o(1))n in 1984. We show that f(K_n) ≥ Ω((n/log n)^2/3).