zbMATH — the first resource for mathematics

Increasing Hamiltonian paths in random edge orderings. (English) Zbl 1338.05150
Summary: Let \(f\) be an edge ordering of \(K_n\): a bijection \(E(K_n)\to\{1,2,\ldots,\tbinom{n}{2}\}\). For an edge \(e\in 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 \(\sqrt{n-1}\leq m(n)\leq({\frac12}+o(1))n\), due respectively to R. L. Graham and D. J. Kleitman [Period. Math. Hung. 3, 141–148 (1973; Zbl 0243.05116)], and to A. R. Calderbank et al. [Discrete Math. 50, 15–28 (1984; Zbl 0542.05058)]. 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.85n\), suggesting that this Hamiltonian (or near-Hamiltonian) phenomenon may hold asymptotically almost surely.

05C45 Eulerian and Hamiltonian graphs
05C80 Random graphs (graph-theoretic aspects)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI
[1] Alon, The probabilistic method (2008) · doi:10.1002/9780470277331
[2] Bollobás, Random graphs (1985)
[3] Calderbank, Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs, Discrete Math 50 pp 15– (1984) · Zbl 0542.05058 · doi:10.1016/0012-365X(84)90031-1
[4] Chvátal, Some combinatorial theorems on monotonicity, Canad Math Bull 14 pp 151– (1971) · Zbl 0214.23503 · doi:10.4153/CMB-1971-028-8
[5] Cooper, On the number of Hamilton cycles in a random graph, J Graph Theory 13 pp 719– (1989) · Zbl 0707.05053 · doi:10.1002/jgt.3190130608
[6] Erdos, A combinatorial problem in geometry, Compos Math 2 pp 463– (1935)
[7] Fox, Erdos-Szekeres-type theorems for monotone paths and convex bodies, Proc London Math Soc 105 pp 953– (2012) · Zbl 1254.05114 · doi:10.1112/plms/pds018
[8] Glebov, On the number of Hamilton cycles in sparse random graphs, SIAM J Discrete Math 27 pp 27– (2013) · Zbl 1268.05179 · doi:10.1137/120884316
[9] Golomb, On the number of permutations of n, objects with greatest cycle length k, Adv Appl Math 20 pp 98– (1998) · Zbl 0897.05005 · doi:10.1006/aama.1997.0567
[10] Graham, Increasing paths in edge ordered graphs, Period Math Hungar 3 pp 141– (1973) · Zbl 0243.05116 · doi:10.1007/BF02018469
[11] Janson, Random graphs (2000) · doi:10.1002/9781118032718
[12] Kalmanson, On a theorem of Erdos and Szekeres, J Combinatorial Theory Ser A 15 pp 343– (1973) · Zbl 0362.05027 · doi:10.1016/0097-3165(73)90081-2
[13] Logan, A variational problem for random Young tableaux, Adv Math 26 pp 206– (1977) · Zbl 0363.62068 · doi:10.1016/0001-8708(77)90030-5
[14] Moshkovitz, Ramsey theory, integer partitions and a new proof of the Erdos-Szekeres Theorem, Adv Math 262 pp 1107– (2014) · Zbl 1295.05255 · doi:10.1016/j.aim.2014.06.008
[15] Robinson, Almost all regular graphs are Hamiltonian, Random Struct Algorithms 5 pp 363– (1994) · Zbl 0795.05088 · doi:10.1002/rsa.3240050209
[16] Steele, Discrete probability and algorithms pp 111– (1995) · doi:10.1007/978-1-4612-0801-3_9
[17] Szabó, A multidimensional generalization of the Erdos-Szekeres lemma on monotone subsequences, Combinatorics Probability Comput 10 pp 557– (2001) · Zbl 1113.52301 · doi:10.1017/S0963548301004862
[18] Veršik, Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux, Dokl Akad Nauk SSSR 233 pp 1024– (1977)
[19] Winkler, Puzzled: Solutions and sources, Commun ACM 51 pp 103– (2008) · doi:10.1145/1378727.1389570
[20] Wolfowitz, Note on runs of consecutive elements, Ann Math Statist 15 pp 97– (1944) · Zbl 0063.08309 · doi:10.1214/aoms/1177731319
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.