# zbMATH — the first resource for mathematics

Most edge-orderings of $$K_{n}$$ have maximal altitude. (English) Zbl 1414.05268
Summary: 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 M. Lavrov and P.-S. Loh [Random Struct. Algorithms 48, No. 3, 588–611 (2016; Zbl 1338.05150)] 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\rightarrow\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$$.

##### MSC:
 05C80 Random graphs (graph-theoretic aspects) 05C45 Eulerian and Hamiltonian graphs
Full Text: