Premium
Most edge‐orderings of K n have maximal altitude
Author(s) -
Martinsson Anders
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20803
Subject(s) - mathematics , conjecture , combinatorics , hamiltonian (control theory) , limiting , limit (mathematics) , graph , discrete mathematics , mathematical analysis , mechanical engineering , mathematical optimization , engineering
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 .