ACO The ACO Seminar (2015–2016)

Mar. 24, 3:30pm, Wean 8220
Kevin Milans, West Virginia University
Monotone paths in dense edge-ordered graphs


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(Kn) ≥ (sqrt{4n-3} - 1)/2. The best known upper bound on f(Kn) is due to Calderbank, Chung, and Sturtevant, who proved that f(Kn) ≤ (½ + o(1))n in 1984. We show that f(Kn) ≥ Ω((n/log n)2/3).

Back to the ACO home page