Optimal Eigenvalue Rigidity of Random Regular Graphs

Understand

Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $d\geq 3$, and denote the eigenvalues as $\lambda_1=d/\sqrt{d-1}\geq \lambda_2\geq\lambda_3\cdots\geq \lambda_N$.

• We prove that the optimal (up to an extra $N^{{\rm o}_N(1)}$ factor, where ${\rm 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+{\rm o}_N(1)}$, \begin{align*} |\lambda_i-\gamma_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\}.