Mar. 24, 3:30pm, Wean 8220

Kevin Milans, West Virginia University

Monotone paths in dense edge-ordered graphs

Kevin Milans, West Virginia University

Monotone paths in dense edge-ordered graphs

Abstract:

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