On Pósa's Conjecture for Random Graphs
Authors:
- Daniela KühnDKDaniela Kühn
- Deryk OsthusDODeryk Osthus
- 1 January 2012
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 26 (3) , 1440-1457
Abstract
The famous Pósa conjecture states that every graph of minimum degree at least $2n/3$ contains the square of a Hamilton cycle. This has been proved for large $n$ by Komlós, Sarközy, and Szemerédi. Here we prove that if $p \ge n^{-1/2+\varepsilon}$, then asymptotically almost surely, the binomial random graph $G_{n,p}$ contains the square of a Hamilton cycle. This provides an “approximate threshold” for the property in the sense that the result fails to hold if $p\le n^{-1/2}$.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Universality of Random GraphsSIAM Journal on Discrete Mathematics, 2012
- Pósa's conjecture for graphs of order at least 2 × 108Random Structures & Algorithms, 2011
- Embedding Spanning Trees in Random GraphsSIAM Journal on Discrete Mathematics, 2010
- Factors in random graphsRandom Structures & Algorithms, 2008
- Proof of the Seymour conjecture for large graphsAnnals of Combinatorics, 1998
- Triangle Factors in Random GraphsCombinatorics, Probability and Computing, 1997
- Threshold functions for asymmetric Ramsey properties with respect to vertex coloringsRandom Structures & Algorithms, 1996
- An algorithm for finding hamilton paths and cycles in random graphsCombinatorica, 1987
- Limit distribution for the existence of hamiltonian cycles in a random graphDiscrete Mathematics, 1983
- Some Theorems on Abstract GraphsProceedings of the London Mathematical Society, 1952