Cycle lengths in sparse random graphs. Issue 3 (8th December 2021) - Alon, Yahav; Krivelevich, Michael; Lubetzky, Eyal
Abstract: We study the set L ( G ) $$ \mathcal{L}(G) $$ of lengths of all cycles that appear in a random d ‐regular graph G on n vertices for d ≥ 3 $$ d\ge 3 $$ 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 ) $$ \mathcal{L}(G) $$ simultaneously contains the entire range { ℓ, …, n } $$ \left\{\ell, …, n\right\} $$ for ℓ ≥ 3 $$ \ell \ge 3 $$, as an explicit expression θ ℓ = θ ℓ ( d ) ∈ ( 0, 1 ) $$ θ_{\ell }=θ_{\ell }(d)\in \left(0, 1\right) $$ which goes to 1 as ℓ → ∞ $$ \ell → ∞ $$ . For the random graph 𝒢 ( n, p ) with p = c / n $$ p=c/n $$, where c ≥ C 0 $$ c\ge {C}_0 $$ for some absolute constant C 0 $$ C_0 $$, we show the analogous result for the range { ℓ, …, ( 1 − o ( 1 ) ) L max ( G ) } $$ \left\{\ell, …, \left(1-o(1)\right)L_{max}(G)\right\} $$, where L max $$ L_{max} $$ is the length of a longest cycle in G . The limiting probability for 𝒢 ( n, p ) coincides with θ ℓ $$ θ_{\ell } $$ 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=\frac{1+ε }{n} $$ .