Most edge-orderings of \(K_{n}\) have maximal altitude. (English) Zbl 1414.05268

Martinsson, Anders

Random Struct. Algorithms 54, No. 3, 559-585 (2019).

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

Keywords:

edge orderings; Hamiltonian paths; random graphs; size bias; third moment