Most edge‐orderings of K n have maximal altitude

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 nonzero with probability at least 1/ e  −  o (1), and conjectured that X is asymptotically almost surely nonzero. In this paper, we prove their conjecture. We further prove a partial result regarding the limiting behavior of X , suggesting that X / n is log‐normal in the limit as n → ∞ . 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 .