# The spectral gap of dense random regular graphs

Wednesday, December 7, 2016 -

3:00pm to 4:00pm

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.

Speaker:

Konstantin Tikhomirov

Princeton University

Event Location:

Fine Hall 214