The spectral gap of random regular graphs

Abstract

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 $d$-regular graph on $n$ vertices, and let $\lambda (G_{n,d})$ be its second largest eigenvalue by absolute value. For some constant $c>0$ and any degree $d$ with ${\log }^{10}n\ll d\le cn$, we show that $\lambda (G_{n,d})=(2+o(1))\sqrt{d(n-d)/n}$ asymptotically almost surely. Combined with earlier results that cover the case of sparse random graphs, this fully determines the asymptotic value of $\lambda (G_{n,d})$ for all $d\le cn$. To achieve this, we introduce new methods that use mechanisms from discrete Fourier analysis, and combine them with existing tools and estimates on $d$-regular random graphs - especially those of Liebenau and Wormald.

arXiv comment38 pages, 1 figure