Computer Science/Discrete Mathematics Seminar II

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 this talk, I will discuss 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 strong convergence of very high-dimensional representations of the symmetric and classical groups. I will aim to explain some of these results and the basic ideas on which they are based. 

Joint work with Chen, Garza-Vargas, and Tropp.