TAU Combinatorics Seminar 2020/21

When: Sunday, November 29, 10am
Speaker:Yahav Alon, Tel Aviv University
Title: Cycle lengths in sparse random graphs


Let $G$ be a graph, and denote by $\mathscr{L}(G)$ the set containing all the integers that appear as lengths of cycles in $G$. We study the typical behaviour of $\mathscr{L}(G)$ when $G$ is a sparse random graph. In the binomial random graph model $G(n,p)$ with $p=c/n$, for almost every large enough value of $c$ we recover an interval of nearly optimal length that is contained in $\mathscr{L}(G)$ with high probability. In the random regular graph model $G(n,d)$, $d \ge 3$ fixed, we recover the full typical distribution of $\mathscr{L}(G)$.

A joint work with Michael Krivelevich and Eyal Lubetzky.