Cycle lengths in sparse random graphs

Abstract

We study the set $\mathcal{L}(G)$ of lengths of all cycles that appear in a random $d$-regular $G$ on $n$ vertices for a fixed $d\ge 3$, as well as in Erdős--Rényi random graphs on $n$ vertices with a fixed average degree $c>1$. Fundamental results on the distribution of cycle counts in these models were established in the 1980's and early 1990's, with a focus on the extreme lengths: cycles of fixed length, and cycles of length linear in $n$. Here we derive, for a random $d$-regular graph, the limiting probability that $\mathcal{L}(G)$ simultaneously contains the entire range $\{\ell ,\dots ,n\}$ for $\ell \ge 3$, as an explicit expression ${\theta }_{\ell }={\theta }_{\ell }(d)\in (0,1)$ which goes to $1$ as $\ell \to \infty$. For the random graph $\mathcal{G}(n,p)$ with $p=c/n$, where $c\ge C_0$ for some absolute constant $C_0$, we show the analogous result for the range $\{\ell ,\dots ,(1-o(1))L_{\max }(G)\}$, where $L_{\max }$ is the length of a longest cycle in $G$. The limiting probability for $\mathcal{G}(n,p)$ coincides with ${\theta }_{\ell }$ from the $d$-regular case when $c$ is the integer $d-1$. In addition, for the directed random graph $\mathcal{D}(n,p)$ we show results analogous to those on $\mathcal{G}(n,p)$, and for both models we find an interval of $c{\epsilon }^{2}n$ consecutive cycle lengths in the slightly supercritical regime $p=\frac{1+\epsilon }{n}$.

11 pages, 3 figures