Optimal Eigenvalue Rigidity of Random Regular Graphs

Consider the normalized adjacency matrices of random d-regular graphs on N vertices with fixed degree d≥ 3, and denote the eigenvalues as λ₁=d/√d-1≥ λ₂≥λ₃⋯≥ λN. We prove that the optimal (up to an extra N^ oN(1) factor, where oN(1) can be arbitrarily small) eigenvalue rigidity holds. More precisely, denote γᵢ as the classical location of the i-th eigenvalue under the Kesten-Mckay law in decreasing order. Then with probability 1-N^-1+ oN(1), {align*} |λ_i-γ_i|≤ {N^{{ o}_N(1)}}{N2/3 (min\{i,N-i+1\})1/3}, for all i∈ \{2,3,⋯,N\}. {align*} In particular, the fluctuations of extreme eigenvalues are bounded by N^-2/3+ oN(1). This gives the same order of fluctuation as for the eigenvalues of matrices from the Gaussian Orthogonal Ensemble.