Optimal Eigenvalue Rigidity of Random Regular Graphs

Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $d\ge 3$, and denote the eigenvalues as ${\lambda }_1=d\mathrm{/}\sqrt{d-1}\ge {\lambda }_2\ge {\lambda }_3\cdots \ge {\lambda }_N$. We prove that the optimal (up to an extra $N^{{\mathrm{o}}_N(1)}$ factor, where ${\mathrm{o}}_N(1)$ can be arbitrarily small) eigenvalue rigidity holds. More precisely, denote ${\gamma }_i$ as the classical location of the $i$-th eigenvalue under the Kesten-Mckay law in decreasing order. Then with probability $1-N^{-1+{\mathrm{o}}_N(1)}$, \begin{align*} |λ_i-γ_i|\leq \frac{N^{{\rm o}_N(1)}}{N^{2/3} (\min{i,N-i+1})^{1/3}},\quad $\text{ for all }$ i\in {2,3,\cdots,N}. \end{align*} In particular, the fluctuations of extreme eigenvalues are bounded by $N^{-2\mathrm{/}3+{\mathrm{o}}_N(1)}$. This gives the same order of fluctuation as for the eigenvalues of matrices from the Gaussian Orthogonal Ensemble.