Cycle lengths in sparse random graphs

25 May 2021
Michael Krivelevich

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.


We study the set $L(G)$ of cycle lengths that appear in a sparse binomial random graph $G(n,c/n)$ and in a random $d$-regular graph $G_{n,d}$. We show in particular that for most values of $c$, for $G$ drawn from $G(n,c/n)$ the set $L(G)$ contains typically an interval $[\omega(1), (1-o(1))L_{\max}(G)]$, where $L_{\max}(G)$ is the length of a longest cycle (the circumference) of $G$. For the case of random $d$-regular graphs, $d\geq 3$ fixed, we obtain an accurate asymptotic estimate for the probability of $L(G)$ to contain a full interval $[k,n]$ for a fixed $k\geq 3$. Similar results are obtained also for the supercritical case $G(n,(1+\epsilon)/n)$, and for random directed graphs.
A joint work with Yahav Alon and Eyal Lubetzky.

  • Combinatorial Theory Seminar