Pancyclic subgraphs of random graphs

Abstract

An $n$-vertex graph is called pancyclic if it contains a cycle of length $t$ for all $3\le t\le n$. In this paper, we study pancyclicity of random graphs in the context of resilience, and prove that if $p\gg n^{-1/2}$, then the random graph $G(n,p)$ a.a.s. satisfies the following property: Every Hamiltonian subgraph of $G(n,p)$ with more than $(1/2+o(1))\left(\genfrac{}{}{0ex}{}{n}{2}\right)p$ edges is pancyclic. This result is best possible in two ways. First, the range of $p$ is asymptotically tight; second, the proportion 1/2 of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich, Lee, and Sudakov. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers).

19 pages, 4 figures