2015/09/07 by Kevin G. Milans, Milans, Kevin G.
Mathematics · #05C35 #05C38 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35 #msc:05C38
paper · pdf · doi:10.48550/arxiv.1509.02143
11 pages
arxiv created 2015/09/07 · arxiv updated 2015/09/08
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(Kn), where Kn is the complete graph on n vertices. In 1973, Graham and Kleitman proved that f(Kn) ≥ √(n - 3/4) - 1/2 and in 1984, Calderbank, Chung, and Sturtevant proved that f(Kn) ≤ ((1)/(2) + o(1))n. We show that f(Kn) ≥ ((1)/(20) - o(1))(n/\lg n)2/3.