Spectral gap and edge universality of dense random regular graphs

Abstract: Let

m a t h c a l A

be the adjacency matrix of a random

d

-regular graph on

N

vertices, and we denote its eigenvalues by

l a m b d a_{1} g e q l a m b d a_{2} c d o t s g e q l a m b d a_{N}

. For

N^{2 / 3} l l d l e q N / 2

, we prove optimal rigidity estimates of the extreme eigenvalues of

m a t h c a l A

, which in particular imply that [ max{|lambda_N|,lambda_2} <2sqrt{d-1} ] with overwhelming probability. In the same regime of

d

, we also show that [ N^{2/3}�igg(frac{lambda_2+d/N}{sqrt{d(N-d)/N}}-2�igg) overset{d}{longrightarrow} mathrm{TW}_1,, ]where

m a t h r m {T W}_{1}

is the Tracy-Widom distribution for GOE; analogues results also hold for other non-trivial extreme eigenvalues.

This page was built for publication: Spectral gap and edge universality of dense random regular graphs