On Pósa's Conjecture for Random Graphs

Authors:
  • DKDaniela Kühn
    Daniela Kühn
  • DODeryk Osthus
    Deryk Osthus

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}$.

This publication has 14 references indexed in Scilit: