The spectral gap of dense random regular graphs

The spectral gap of dense random regular graphs

-
Konstantin Tikhomirov , Princeton University
Fine Hall 214

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 √d 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.