For random $d$-regular graphs on $N$ vertices with $1 ll d ll N^{2/3}$, we develop a $d^{-1/2}$ expansion of the local eigenvalue distribution about the Kesten-McKay law up to order $d^{-3}$. This result is valid up to the edge of the spectrum. It implies that the eigenvalues of such random regular graphs are more rigid than those of ErdH{o}s-Renyi graphs of the same average degree. As a first application, for $1 ll d ll N^{2/3}$, we show that all nontrivial eigenvalues of the adjacency matrix are with very high probability bounded in absolute value by $(2 + o(1)) sqrt{d - 1}$. As a second application, for $N^{2/9} ll d ll N^{1/3}$, we prove that the extremal eigenvalues are concentrated at scale $N^{-2/3}$ and their fluctuations are governed by Tracy-Widom statistics. Thus, in the same regime of $d$, $52%$ of all $d$-regular graphs have second-largest eigenvalue strictly less than $2 sqrt{d - 1}$.
Download