Sparse pancyclic subgraphs of random graphs

Abstract

It is known that the complete graph $K_n$ contains a pancyclic subgraph with $n+(1+o(1))\cdot {\log }_{2}n$ edges, and that there is no pancyclic graph on $n$ vertices with fewer than $n+{\log }_2(n-1)-1$ edges. We show that, with high probability, $G(n,p)$ contains a pancyclic subgraph with $n+(1+o(1)){\log }_{2}n$ edges for $p\ge p^{\ast }$, where $p^{\ast }=(1+o(1))\ln n/n$, right above the threshold for pancyclicity.