Hamiltonian increasing paths in random edge orderings

MaRDI QIDQ6249524zbMATH OpenFDO

Authors Mikhail Lavrov, Po-Shen Loh

Publication date 4 March 2014

Abstract: If the edges of the complete graph $K_n$ are totally ordered, a simple path whose edges are in ascending order is called increasing. The worst-case length of the longest increasing path has remained an open problem for several decades, with asymptotic bounds between $sqrtn$ (Graham and Kleitman, 1973) and $n/2$ (Calderbank, Chung, and Sturtevant, 1984). We consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, an increasing path of the maximum possible length of $n-1$ exists 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.

This page was built for publication: Hamiltonian increasing paths in random edge orderings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6249524)