Spectrum of Random $d$-regular Graphs Up to the Edge

Jiaoyang Huang, Horng-Tzer Yau

Published 2021-02-01Version 1

Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $d\geq3$. We prove that, with probability $1-N^{-1+{\mathfrak c}}$ for any ${\mathfrak c} >0$, the following two properties hold as $N \to \infty$ provided that $d\geq3$: (i) The eigenvalues are close to the classical eigenvalue locations given by the Kesten-McKay distribution. In particular, the extremal eigenvalues are concentrated with polynomial error bound in $N$, i.e. $\lambda_2, |\lambda_N|\leq 2+N^{-\Omega(1)}$. (ii) All eigenvectors of random $d$-regular graphs are completely delocalized.