Hamiltonian increasing paths in random edge orderings

Let f be an edge ordering of Kn: a bijection E(Kn) → {1, 2, . . . , n2}. For an edge e ∈ E(Kn), we call f(e) the label of e. An increasing path in Kn is a simple path (visiting each vertex at most once) such that the label on each edge is greater than the label on the previous edge. We let S(f) be the number of edges in the longest increasing path. Chvatal and Komlos raised the question of estimating m(n): the minimum value of S(f) over all orderings f of Kn. The best known bounds on m(n) are , due respectively to Graham and Kleitman, and to Calderbank, Chung, and Sturtevant. Although the problem is natural, it has seen essentially no progress for three decades.

In this paper, we consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, S(f) often takes its maximum possible value of n − 1 (visiting all of the vertices with a Hamiltonian increasing path). We prove that this occurs with probability at least about 1/e. We also prove that with probability 1 − o(1), there is an increasing path of length at least 0.85n, suggesting that this Hamiltonian (or near-Hamiltonian) phenomenon may hold asymptotically almost surely.