Spectral Gap and Edge Universality of Dense Random Regular Graphs

Let \({\mathcal {A}}\) $\mathcal{A}$ be the adjacency matrix of a random d-regular graph on N vertices, and we denote its eigenvalues by \(\lambda _1\geqslant \lambda _2\cdots \geqslant \lambda _{N}\) ${\lambda }_1⩾{\lambda }_2\cdots ⩾{\lambda }_N$ . For \(N^{2/3+o(1)}\leqslant d\leqslant N/2\) $N_{}^{2/3+o(1)}⩽d⩽N/2$ , we prove optimal rigidity estimates of the extreme eigenvalues of \({\mathcal {A}}\) $\mathcal{A}$ , which in particular imply that \(\begin{aligned} \max \{|\lambda _N|,\lambda _2\} <2\sqrt{d-1} \end{aligned}\) $$\begin{array}{c}\hfill max\{|{\lambda }_N|,{\lambda }_2\}<2\sqrt{d-1}\end{array}$$ with very high probability. In the same regime of d, we also show that \(\begin{aligned} N^{2/3}\bigg (\frac{\lambda _2+d/N}{\sqrt{d(N-d)/N}}-2\bigg ) \overset{d}{\longrightarrow }\ \textrm{TW}_1, \end{aligned}\) $$\begin{array}{c}\hfill N_{}^{2/3}(\frac{{\lambda }_2+d/N}{\sqrt{d(N-d)/N}}-2)\stackrel{d}{⟶}{\text{TW}}_1,\end{array}$$ where \(\textrm{TW}_1\) ${\text{TW}}_1$ is the Tracy–Widom distribution for GOE; analogue results also hold for other non-trivial extreme eigenvalues.