Cycle lengths in sparse random graphs

DOI10.1002/RSA.21067MaRDI QIDQ6052480zbMATH OpenOpenAlexFDO

Authors Yahav Alon, Michael Krivelevich, Eyal Lubetzky

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.13591

zbMATH Keywords

cycle lengthsregular graphssparse random graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the set $calL(G)$ of lengths of all cycles that appear in a random $d$-regular $G$ on $n$ vertices for a fixed $dgeq3$, as well as in ErdH{o}s--R'enyi 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 1980's and early 1990's, 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 $calL(G)$ simultaneously contains the entire range $ell,ldots,n$ for $ellgeq3$, as an explicit expression $het{a}_{e}ll=het{a}_{e}ll(d)in(0,1)$ which goes to $1$ as $elloinfty$. For the random graph $calG(n,p)$ with $p=c/n$, where $cgeq{C}_0$ for some absolute constant $C_0$, we show the analogous result for the range $ell,ldots,(1-o(1))L_{max}(G)$, where $L_{max}$ is the length of a longest cycle in $G$. The limiting probability for $calG(n,p)$ coincides with $het{a}_{e}ll$ from the $d$-regular case when $c$ is the integer $d-1$. In addition, for the directed random graph $calD(n,p)$ we show results analogous to those on $calG(n,p)$, and for both models we find an interval of $cepsilo{n}^{2}n$ consecutive cycle lengths in the slightly supercritical regime $p=frac1+epsilonn$.

Recommendations

• scientific article; zbMATH DE number 3916307
• Short cycles in random regular graphs
• A note on long cycles in sparse random graphs
• A scaling limit for the length of the longest cycle in a sparse random graph
• Cycles of given lengths in unicyclic components in sparse random graphs

Cites work

• 1-Pancyclic Hamilton Cycles in Random Graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A scaling limit for the length of the longest cycle in a sparse random digraph
• A scaling limit for the length of the longest cycle in a sparse random graph
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• An improved upper bound on the length of the longest cycle of a supercritical random graph
• Anatomy of a Young giant component in the random graph
• Anatomy of the giant component: the strictly supercritical regime
• Clutter percolation and random graphs
• Cycle lengths in expanding graphs
• Cycles in a random graph near the critical point
• Cycles in random graphs
• Hamilton cycles containing randomly selected edges in random regular graphs
• scientific article; zbMATH DE number 3865331 (Why is no real title available?)
• scientific article; zbMATH DE number 3916307 (Why is no real title available?)
• scientific article; zbMATH DE number 17673 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Long paths in sparse random graphs
• Longest cycles in sparse random digraphs
• On large matchings and cycles in sparse random graphs
• Pancyclic Hamilton cycles in random graphs
• Random graphs.
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Smoothed Analysis on Connected Graphs
• The asymptotic distribution of short cycles in random regular graphs

Cited in

(25)

• On the sum of the reciprocals of cycle lengths in sparse graphs
• On large matchings and cycles in sparse random graphs
• Large holes in sparse random graphs
• Short cycles in random regular graphs
• Distribution of cycle lengths in graphs
• A scaling limit for the length of the longest cycle in a sparse random graph
• Cycles of given lengths in unicyclic components in sparse random graphs
• Longest cycles in sparse random digraphs
• Geodesics and almost geodesic cycles in random regular graphs
• On the average path length of a cycle plus random edges
• scientific article; zbMATH DE number 3916307 (Why is no real title available?)
• An improved upper bound on the length of the longest cycle of a supercritical random graph
• The Min Mean-Weight Cycle in a Random Network
• A note on long cycles in sparse random graphs
• A scaling limit for the length of the longest cycle in a sparse random digraph
• Longest and shortest cycles in random planar graphs
• Long paths in heterogeneous random subgraphs of graphs with large minimum degree
• Simple versus nonsimple loops on random regular graphs
• Chvátal-Erdős condition for pancyclicity
• A generalization of Bondy's pancyclicity theorem
• The emergence of a giant rainbow component
• The completion numbers of Hamiltonicity and pancyclicity in random graphs
• Chvátal-Erdős condition for pancyclicity (extended abstract)
• A generalization of Bondy's pancyclicity theorem (extended abstract)
• Cycle lengths in sparse graphs

This page was built for publication: Cycle lengths in sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6052480)