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