Most edge-orderings of $K_n$ have maximal altitude

Abstract

Suppose the edges of the complete graph on $n$ vertices are assigned a uniformly chosen random ordering. Let $X$ denote the corresponding number of Hamiltonian paths that are increasing in this ordering. It was shown in a recent paper by Lavrov and Loh that this quantity is non-zero with probability at least $1/e-o(1)$, and conjectured that $X$ is asymptotically almost surely non-zero. In this paper, we prove their conjecture. We further prove a partial result regarding the limiting behaviour of $X$, suggesting that $X/n$ is log-normal in the limit as $n\to \infty$. A key idea of our proof is to show a certain relation between $X$ and its size-biased distribution. This relies heavily on estimates for the third moment of $X$.

arXiv comment26 pages, 2 figures

References in corpus (1)

• Hamiltonian increasing paths in random edge orderings