Optimal Eigenvalue Rigidity of Random Regular Graphs

Abstract

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/\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/3+{\mathrm{o}}_N(1)}$. This gives the same order of fluctuation as for the eigenvalues of matrices from the Gaussian Orthogonal Ensemble.

62 pages, 2 figures