Ramanujan Property and Edge Universality of Random Regular Graphs

Abstract

We consider the normalized adjacency matrix of a random $d$-regular graph on $N$ vertices with any fixed degree $d\ge 3$ and denote its eigenvalues as $\hat{I}{»}_1=d/\sqrt{d-1}\ge \hat{I}{»}_2\ge \hat{I}{»}_3\cdots \ge \hat{I}{»}_N$. We establish the following two results as $N\to \infty$. (i) With high probability, all eigenvalues are optimally rigid, up to an additional $N^{\mathrm{o}(1)}$ factor. Specifically, the fluctuations of bulk eigenvalues are bounded by $N^{-1+\mathrm{o}(1)}$, and the fluctuations of edge eigenvalues are bounded by $N^{-2/3+\mathrm{o}(1)}$. (ii) Edge universality holds for random $d$-regular graphs. That is, the distributions of $\hat{I}{»}_2$ and $-\hat{I}{»}_N$ converge to the Tracy-Widom${}_1$ distribution associated with the Gaussian Orthogonal Ensemble. As a consequence, for sufficiently large $N$, approximately $69\%$ of $d$-regular graphs on $N$ vertices are Ramanujan, meaning $\max \{\hat{I}{»}_2,|\hat{I}{»}_N|\}\le 2$.

153 pages, 3 figures, updated version with corrected typos