The spectral gap of random regular graphs

Amir Sarid

We bound the second eigenvalue of random $d$-regular graphs, for a wide range of degrees $d$, using a novel approach based on Fourier analysis. Let $G_{n,d}$ be a uniform random $…