Local Resilience for Squares of Almost Spanning Cycles in Sparse Random Graphs

• Published in: The Electronic journal of combinatorics 2017-10, Vol.24 (4)
• Main Authors: Noever, Andreas, Steger, Angelika
• Format: Article
• Language: English
• ISSN: 1077-8926; 1077-8926
• DOI: 10.37236/6281

In 1962, Pósa conjectured that a graph $G=(V, E)$ contains a square of a Hamiltonian cycle if $\delta(G)\ge 2n/3$. Only more than thirty years later Komlós, Sárkőzy, and Szemerédi proved this conjecture using the so-called Blow-Up Lemma. Here we extend their result to a random graph setting. We show that for every $\epsilon > 0$ and $p=n^{-1/2+\epsilon}$ a.a.s. every subgraph of $G_{n,p}$ with minimum degree at least $(2/3+\epsilon)np$ contains the square of a cycle on $(1-o(1))n$ vertices. This is almost best possible in three ways: (1) for $p\ll n^{-1/2}$ the random graph will not contain any square of a long cycle (2) one cannot hope for a resilience version for the square of a spanning cycle (as deleting all edges in the neighborhood of single vertex destroys this property) and (3) for $c