Edge rigidity and universality of random regular graphs of intermediate degree

For random d-regular graphs on N vertices with 1 ≪ d≪ 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 Erdős–Rényi graphs of the same average degree. As a first application, for 1 ≪ d≪ 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))d-1. As a second application, for N^{2 / 9}≪ d≪ 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 2d-1.