Cycle lengths in sparse random graphs. Issue 3 (8th December 2021) - Alon, Yahav; Krivelevich, Michael; Lubetzky, Eyal
Abstract: We study the set L ( G ) L(G) of lengths of all cycles that appear in a random d ‐regular graph G on n vertices for d ≥ 3 d3 fixed, as well as in binomial random graphs on n vertices with a fixed average degree c > 1 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 ) L(G) simultaneously contains the entire range ℓ, …, n {, …, n} for ℓ ≥ 3 3 , as an explicit expression θ ℓ = θ ℓ ( d ) ∈ ( 0, 1 ) θ_=θ_(d)(0, 1) which goes to 1 as ℓ → ∞ → ∞ . For the random graph 𝒢 ( n, p ) with p = c / n p=c/n , where c ≥ C 0 cC_0 for some absolute constant C 0 C_0 , we show the analogous result for the range ℓ, …, ( 1 − o ( 1 ) ) L max ( G ) {, …, (1-o(1))L_max(G)} , where L max L_max is the length of a longest cycle in G . The limiting probability for 𝒢 ( n, p ) coincides with θ ℓ θ_ from the d ‐regular case when c is the integer d − 1 d-1 . In addition, for the directed random graph 𝒟 ( n, p ) we show results analogous to those on 𝒢 ( n, p ), and for both models we find an interval of c ε 2 n cε^2n consecutive cycle lengths in the slightly supercritical regime p = 1 + ε n p=1+ε n .