Cycle lengths in sparse random graphs

We study the set L (G) of lengths of all cycles that appear in a random d- regular graph G on n vertices for d >= 3 fixed, as well as in binomial 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 1980s and early 1990s, 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 L (G) simultaneously contains the entire range {l, ..., n} for l >= 3, as an explicit expression theta(l) = theta(l) (d)(0, 1) which goes to 1 as l -> infinity. For the random graph G(n, p) with p = c/n, where c >= C-0 for some absolute constant C-0, we show the analogous result for the range {l, ..., (1 - o(1))L-max(G)}, where L-max is the length of a longest cycle in G. The limiting probability for G(n, p) coincides with theta(l) from the d-regular case when c is the integer d - 1. In addition, for the directed random graph D(n, p) we show results analogous to those on 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 = 1+epsilon/n.