Departmental colloquium 11.12.22

Usual Time
יום ראשון 11.12 בשעה 14:00
More Details



(Speaker: Amir Sarid (Tel Aviv University

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.

Zoom link: