Spectral Gap and Edge Universality of Dense Random Regular Graphs

Let A A be the adjacency matrix of a random d -regular graph on N vertices, and we denote its eigenvalues by λ ₁ λ ₂⋯ λ N λ 1 ⩾ λ 2 ⋯ ⩾ λ N . For N2/3+o(1) d N/2 N 2 / 3 + o ( 1 ) ⩽ d ⩽ N / 2 , we prove optimal rigidity estimates of the extreme eigenvalues of A A , which in particular imply that aligned max \|λ N|,λ ₂\ <2√d-1 aligned max { | λ N | , λ 2 } < 2 d - 1 with very high probability. In the same regime of d , we also show that aligned N2/3 (λ ₂+d/N√d(N-d)/N-2 ) d \ TW₁, aligned N 2 / 3 ( λ 2 + d / N d ( N - d ) / N - 2 ) ⟶ d TW 1 , where TW₁ TW 1 is the Tracy–Widom distribution for GOE; analogue results also hold for other non-trivial extreme eigenvalues.