A randomized construction of high girth regular graphs

Nati Linial, Michael Simkin

We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k\ge 3$ and $c\in (0,1)$ be fixed. Let $n\in \mathbb{N}$ be even and set $g = c \log_…