Local resilience for squares of almost spanning cycles in sparse random graphs (Q2409840)

Summary: In 1962, L. Pósa conjectured that a graph \(G=(V, E)\) contains a square of a Hamiltonian cycle if \(\delta(G)\geq 2n/3\). Only more than thirty years later \textit{J. Komlós} et al. [Combinatorica 17, No. 1, 109--123 (1997; Zbl 0880.05049); Random Struct. Algorithms 9, No. 1--2, 193--211 (1996; Zbl 0864.05063)] 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<2/3\) a.a.s. \(G_{n,p}\) contains a subgraph with minimum degree at least \(cnp\) which does not contain the square of a path on \((1/3+c)n\) vertices.