Cycle lengths in sparse random graphs

This is the authors' abstract. We don't add key points for this paper.

We study the set of lengths of all cycles that appear in a random d ‐regular graph G on n vertices for fixed, as well as in binomial random graphs on n vertices with a fixed average degree . 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 simultaneously contains the entire range for , as an explicit expression which goes to 1 as . For the random graph with , where for some absolute constant , we show the analogous result for the range , where is the length of a longest cycle in G . The limiting probability for coincides with from the d ‐regular case when c is the integer . In addition, for the directed random graph we show results analogous to those on , and for both models we find an interval of consecutive cycle lengths in the slightly supercritical regime .