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

Andreas Noever¹ ; Angelika Steger¹

¹Department of Computer Science ETH Zürich 8092 Zürich Switzerland

The electronic journal of combinatorics, Tome 24 (2017) no. 4

Résumé

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

Détail

DOI : 10.37236/6281

Classification : 05C80, 05C38, 05C42
Mots-clés : random graphs, resilience, almost spanning subgraphs