Increasing Hamiltonian paths in random edge orderings1. Issue 3 (7th July 2015)

• Record Type: Journal Article
• Authors: Lavrov, Mikhail; Loh, Po‐Shen
• Is Part Of: Random structures & algorithms. Volume 48:Issue 3(2016)
• Page Start: 588
• Page End: 611
• Publication Date: 2015-07-07
• Subjects: random graphs -- edge labeling -- monotone subsequences -- Hamiltonian paths -- algorithms; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20592
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Let f be an edge ordering of K n : a bijection E ( K n ) → { 1, 2, …, ( n 2 ) } . For an edge e ∈ E ( K n ), we call f ( e ) the label of e . An increasing path in K n is a simple path (visiting each vertex at most once) such that the label on each edge is greater than the label on the previous edge. We let S ( f ) be the number of edges in the longest increasing path. Chvátal and Komlós raised the question of estimating m ( n ): the minimum value of S ( f ) over all orderings f of K n . The best known bounds on m ( n ) are n − 1 ≤ m ( n ) ≤ ( 1 2 + o ( 1 ) ) n, due respectively to Graham and Kleitman, and to Calderbank, Chung, and Sturtevant. Although the problem is natural, it has seen essentially no progress for three decades. In this paper, we consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, S ( f ) often takes its maximum possible value of n – 1 (visiting all of the vertices with an increasing Hamiltonian path). We prove that this occurs with probability at least about 1/ e . We also prove that with probability 1‐ o (1), there is an increasing path of length at least 0.85 n, suggesting that this Hamiltonian (or near‐Hamiltonian) phenomenon may hold asymptotically almost surely. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 588–611, 2016