HUJI Combinatorics Seminar
When: Monday May 23rd, 2022, at 11AM (Israel time)
Where: Sprinzak 202
Link to live session:
Speaker: Amir Sarid (TAU)
Title: The spectral gap of random regular graphs
Consider a random d-regular graph on n vertices - chosen uniformly at random from all such graphs. We may expect it to be a good expander - with second eigenvalue around (2 + o(1)) sqrt(d - 1) asymptotically almost surely, analogous to the case of G(n, p).
The case of constant d was asked by Alon and proven in a celebrated result of Friedman. In the case of non-constant d, an analogous conjecture was made by Vu in 2008. In this talk, I will discuss a proof of this conjecture for a wide range of values of d - from poly-logarithmic all the way up to c * n for some small c > 0. Together with existing results for smaller d, and a very recent result of He for larger d, this fully proves Vu's conjecture.
In order to prove this, I will introduce a general criterion for expansion in terms for certain Fourier coefficients, that measure the correlation between different edges appearing in the graph. This novel technique combines ideas from Fourier theory with the trace method, and may be of independent interest.