A New Approach to Optimal Spectral Gaps

It was conjectured by Alon in the 1980s that random d-regular graphs have the largest possible spectral gap (up to negligible error) among all d-regular graphs. This conjecture was proved by Friedman in 2004 in major tour de force. In recent years, deep generalizations of Friedman's theorem, such as strong convergence of random permutation matrices due to Bordenave and Collins, have played a central role in a series of breakthrough results on random graphs, geometry, and operator algebras.

In joint work with Chen, Garza-Vargas, and Tropp, we recently discovered a surprisingly simple new approach to such results that is almost entirely based on soft arguments. This approach makes it possible to address previously inaccessible questions: for example, it enables a sharp understanding of the large deviation probabilities in Friedman's theorem, and establishes optimal spectral gaps of random Schreier graphs that require many fewer random bits than ordinary random regular graphs. I will aim to explain some of these results and some intuition behind the proofs.