The threshold for the square of a Hamilton cycle

Kahn, Jeff; Narayanan, Bhargav; Park, Jinyoung

doi:10.1090/proc/15419

The threshold for the square of a Hamilton cycle
HTML articles powered by AMS MathViewer

by Jeff Kahn, Bhargav Narayanan and Jinyoung Park PDF

Proc. Amer. Math. Soc. 149 (2021), 3201-3208 Request permission

Abstract:

Resolving a conjecture of Kühn and Osthus from 2012, we show that $p= 1/\sqrt {n}$ is the threshold for the random graph $G_{n,p}$ to contain the square of a Hamilton cycle.

References

M. Ajtai, J. Komlós, and E. Szemerédi, First occurrence of Hamilton cycles in random graphs, Cycles in graphs (Burnaby, B.C., 1982) North-Holland Math. Stud., vol. 115, North-Holland, Amsterdam, 1985, pp. 173–178. MR 821516, DOI 10.1016/S0304-0208(08)73007-X
Béla Bollobás, The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) Academic Press, London, 1984, pp. 35–57. MR 777163
Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966, DOI 10.1017/CBO9780511814068
P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
M. Fischer, N. Škorić, A. Steger, and M. Trujić, Triangle resilience of the square of a Hamilton cycle in random graphs, Preprint, arXiv:1809.07534.
K. Frankston, J. Kahn, B. Narayanan, and J. Park, Thresholds versus fractional expectation-thresholds, Preprint, arXiv:1910.13433.
Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 (1999), no. 4, 1017–1054. With an appendix by Jean Bourgain. MR 1678031, DOI 10.1090/S0894-0347-99-00305-7
Ehud Friedgut, Hunting for sharp thresholds, Random Structures Algorithms 26 (2005), no. 1-2, 37–51. MR 2116574, DOI 10.1002/rsa.20042
A. Frieze, Hamilton cycles in random graphs: a bibliography, Preprint, arXiv:1901.07139.
Alan Frieze and MichałKaroński, Introduction to random graphs, Cambridge University Press, Cambridge, 2016. MR 3675279, DOI 10.1017/CBO9781316339831
Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
Jeff Kahn and Gil Kalai, Thresholds and expectation thresholds, Combin. Probab. Comput. 16 (2007), no. 3, 495–502. MR 2312440, DOI 10.1017/S0963548307008474
Donald E. Knuth, The art of computer programming. Vol. 2, Addison-Wesley, Reading, MA, 1998. Seminumerical algorithms; Third edition [of MR0286318]. MR 3077153
János Komlós and Endre Szemerédi, Limit distribution for the existence of Hamiltonian cycles in a random graph, Discrete Math. 43 (1983), no. 1, 55–63. MR 680304, DOI 10.1016/0012-365X(83)90021-3
Daniela Kühn and Deryk Osthus, On Pósa’s conjecture for random graphs, SIAM J. Discrete Math. 26 (2012), no. 3, 1440–1457. MR 3022146, DOI 10.1137/120871729
Bhargav Narayanan and Mathias Schacht, Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs, Random Structures Algorithms 57 (2020), no. 1, 244–255. MR 4120599, DOI 10.1002/rsa.20919
Rajko Nenadov and Nemanja Škorić, Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs, Random Structures Algorithms 54 (2019), no. 1, 187–208. MR 3884618, DOI 10.1002/rsa.20782
L. Pósa, Hamiltonian circuits in random graphs, Discrete Math. 14 (1976), no. 4, 359–364. MR 389666, DOI 10.1016/0012-365X(76)90068-6
Oliver Riordan, Spanning subgraphs of random graphs, Combin. Probab. Comput. 9 (2000), no. 2, 125–148. MR 1762785, DOI 10.1017/S0963548399004150
Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi, A Dirac-type theorem for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), no. 1-2, 229–251. MR 2195584, DOI 10.1017/S0963548305007042
Michel Talagrand, Are many small sets explicitly small?, STOC’10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 13–35. MR 2743011