Cycle lengths in sparse random graphs. Issue 3 (8th December 2021)

• Record Type: Journal Article
• Authors: Alon, Yahav; Krivelevich, Michael; Lubetzky, Eyal
• Is Part Of: Random structures & algorithms. Volume 61:Issue 3(2022)
• Page Start: 444
• Page End: 461
• Publication Date: 2021-12-08
• Subjects: cycle lengths -- regular graphs -- sparse random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21067
• Languages: English
• ISSNs: 1042-9832

Abstract

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, \dots, n\right\} $$ for ℓ ≥ 3 $$ \ell \ge 3 $$, as an explicit expression θ ℓ = θ ℓ ( d ) ∈ ( 0, 1 ) $$ {\theta}_{\ell }={\theta}_{\ell }(d)\in \left(0, 1\right) $$ which goes to 1 as ℓ → ∞ $$ \ell \to \infty $$ . 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, \dots, \left(1-o(1)\right){L}_{\mathrm{max}}(G)\right\} $$, where L max $$ {L}_{\mathrm{max}} $$ is the length of a longest cycle in G . The limiting probability for 𝒢 ( n, p ) coincides with θ ℓ $$ {\theta}_{\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{\varepsilon}^2n $$ consecutive cycle lengths in the slightly supercritical regime p = 1 + ε n $$ p=\frac{1+\varepsilon }{n} $$ .