The spectral gap of dense random regular graphs
The spectral gap of dense random regular graphs
-
Konstantin Tikhomirov , Princeton University
Let G be uniformly distributed on the set of all simple d-regular graphs on n vertices, and assume d is bigger than some (small) power of n. We show that the second largest eigenvalue of G is of order 鈭歞 with probability close to one.听Combined with earlier results covering the case of sparse random graphs, this settles the problem of estimating the magnitude of the second eigenvalue, up to a multiplicative constant, for all values of n and d, confirming a conjecture of Van Vu. Joint work with Pierre Youssef.