Most edge‐orderings of Kn have maximal altitude. Issue 3 (12th November 2018)

• Record Type: Journal Article
• Authors: Martinsson, Anders
• Is Part Of: Random structures & algorithms. Volume 54:Issue 3(2019)
• Page Start: 559
• Page End: 585
• Publication Date: 2018-11-12
• Subjects: edge orderings -- Hamiltonian paths -- random graphs -- size bias -- third moment; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20803
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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 .