Spectral Gap and Edge Universality of Dense Random Regular Graphs

Let A be the adjacency matrix of a random d-regular graph on N vertices, and we denote its eigenvalues by λ₁ ⩾ λ₂⋯ ⩾ λ_N. For N^2/3+o(1) ⩽ d ⩽ N/2, we prove optimal rigidity estimates of the extreme eigenvalues of A, which in particular imply that 

                    max{|λ_N |, λ₂} < 2√d − 1

with very high probability. In the same regime of d, we also show that 

                    N^2/3 (λ₂ + d/N  / √d(N − d)/N − 2) ^d → TW₁,

where TW₁ is the Tracy–Widom distribution for GOE; analogue results also hold for other non-trivial extreme eigenvalues.

© The Author(s) 2024.