Spectrum of Random $d$-regular Graphs Up to the Edge

Abstract

Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $d\ge 3$. We prove that, with probability $1-N^{-1+\epsilon }$ for any $\epsilon >0$, the following two properties hold as $N\to \infty$ provided that $d\ge 3$: (i) The eigenvalues are close to the classical eigenvalue locations given by the Kesten-McKay distribution. In particular, the extremal eigenvalues are concentrated with polynomial error bound in $N$, i.e. ${\lambda }_2,|{\lambda }_N|\le 2+N^{-c}$. (ii) All eigenvectors of random $d$-regular graphs are completely delocalized.

Updated version with corrected typos

References in corpus (3)

• Local semicircle law and complete delocalization for Wigner random matrices
• The Relativized Second Eigenvalue Conjecture of Alon
• Gaussian Waves on the Regular Tree

Cited by in corpus (3)

• On the second eigenvalue of random bipartite biregular graphs
• Many nodal domains in random regular graphs
• Norm of matrix-valued polynomials in random unitaries and permutations