Konstantin Tikhomirov, Princeton University

The spectral gap of dense random regular graphs
Dec 7, 2016, 3:00 pm4:00 pm
214 - Fine Hall


Event Description

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.

Event Category
Probability Seminar