Edge rigidity and universality of random regular graphs of intermediate degree

Abstract

For random $d$-regular graphs on $N$ vertices with $1\ll d\ll N^{2/3}$, we develop a $d^{-1/2}$ expansion of the local eigenvalue distribution about the Kesten-McKay law up to order $d^{-3}$. This result is valid up to the edge of the spectrum. It implies that the eigenvalues of such random regular graphs are more rigid than those of Erdős-Rényi graphs of the same average degree. As a first application, for $1\ll d\ll N^{2/3}$, we show that all nontrivial eigenvalues of the adjacency matrix are with very high probability bounded in absolute value by $(2+o(1))\sqrt{d-1}$. As a second application, for $N^{2/9}\ll d\ll N^{1/3}$, we prove that the extremal eigenvalues are concentrated at scale $N^{-2/3}$ and their fluctuations are governed by Tracy-Widom statistics. Thus, in the same regime of $d$, $52\%$ of all $d$-regular graphs have second-largest eigenvalue strictly less than $2\sqrt{d-1}$.

References in corpus (3)

• Edge statistics of Dyson Brownian motion
• Gaussian Waves on the Regular Tree
• Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs

Cited by in corpus (10)

• Exponential growth of random determinants beyond invariance
• The spectral density of dense random networks and the breakdown of the Wigner semicircle law
• Spectrum of Random $d$-regular Graphs Up to the Edge
• On the second eigenvalue of random bipartite biregular graphs
• Spectral gap and edge universality of dense random regular graphs
• Global eigenvalue fluctuations of random biregular bipartite graphs
• A note on quantum expanders
• Norm of matrix-valued polynomials in random unitaries and permutations
• Eigenvectors of the square grid plus GUE
• A convergence framework for Airy${}_{\beta }$ line ensemble via pole evolution