Combinatorics: Michael Simkin (HUJI)

Title: A randomized construction of high girth regular graphs

Abstract: We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k > 2$ and $0 < c < 1$ be fixed. Let $n$ be even and set $g = c \log_{k-1} (n)$. Begin with a Hamilton cycle $G$ on $n$ vertices. As long as the smallest degree $\delta (G)<k$, choose, uniformly at random, two vertices $u,v \in V(G)$ of degree $\delta(G)$ whose distance is at least $g-1$. If there are no such vertex pairs, abort. Otherwise, add the edge $uv$ to $E(G)$.
We show that with high probability this algorithm yields a $k$-regular graph with girth at least $g$. Our analysis also implies that there are $( \Omega (n) )^{kn/2}$ $k$-regular $n$-vertex graphs with girth at least $g$.

This is joint work with Nati Linial.


Mon, 13/01/2020 - 10:00 to 12:00


C-400, CS building