|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
West Virginia University Title: Monotone paths in dense edge-ordered graphs Abstract: In a graph whose edges 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). Date: Thursday, March 24, 2016 Time: 3:30 pm Location: Wean Hall 8220 Submitted by: Bukh |
