The threshold for the square of a Hamilton cycle

DOI10.1090/PROC/15419MaRDI QIDQ4992907zbMATH OpenOpenAlexFDO

Authors Bhargav P. Narayanan, Jinyoung Park, J. Kahn

Publication date 10 June 2021

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.08592

zbMATH Keywords

Hamilton cycles in random graphshypergraphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Resolving a conjecture of K"uhn and Osthus from 2012, we show that $p=1/sqrtn$ is the threshold for the random graph $G_{n,p}$ to contain the square of a Hamilton cycle.

Recommendations

• On Pósa's conjecture for random graphs
• The threshold for hamilton cycles in the square of a random graph
• On the square of a Hamiltonian cycle in dense graphs
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• scientific article; zbMATH DE number 4193709

Cites work

• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Are many small sets explicitly small?
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Hunting for sharp thresholds
• Introduction to Random Graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On Pósa's conjecture for random graphs
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• Random graphs.
• Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
• Sharp thresholds of graph properties, and the k-sat problem
• Spanning Subgraphs of Random Graphs
• Thresholds and Expectation Thresholds

Cited in

(28)

• Triangle resilience of the square of a Hamilton cycle in random graphs
• The threshold for hamilton cycles in the square of a random graph
• The Square of a Hamiltonian Cycle
• On Pósa's conjecture for random graphs
• A sharp threshold for spanning 2-spheres in random 2-complexes
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• A proof of the Kahn–Kalai conjecture
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Tight concentration of star saturation number in random graphs
• Threshold for Steiner triple systems
• Rainbow powers of a Hamilton cycle in G_n,p
• Threshold for stability of weak saturation
• The square of a Hamilton cycle in randomly perturbed graphs
• Rainbow thresholds
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Optimal spread for spanning subgraphs of Dirac hypergraphs
• A smoother notion of spread hypergraphs
• Spanning F-cycles in random graphs
• A robust Corrádi-Hajnal theorem
• Searching for (sharp) thresholds in random structures: where are we now?
• Weak saturation numbers in random graphs
• Universality for graphs with bounded density
• On certain spanning subgraphs of random graphs
• The threshold for powers of tight Hamilton cycles in random hypergraphs
• Sprinkling with random regular graphs
• On a conjecture of Talagrand on selector processes and a consequence on positive empirical processes
• On rainbow thresholds

This page was built for publication: The threshold for the square of a Hamilton cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4992907)