Mathematics Colloquium

Friedman's celebrated 2004 result states that, as the number of vertices goes to infinity, random d-regular graphs are (with high probability) nearly optimal expanders, meaning that the top non-trivial eigenvalue of their (random) adjacency matrix converges in probability to 2 sqrt(d-1). Since expanders are of great interest in mathematics and computer science, Friedman's paper (which is ~100 pages long) has attracted a lot of attention in the last two decades and more efficient proofs of his result (which yield vast generalizations) have been found. However, all the approaches to Friedman's theorem and its extensions relied on very delicate and sophisticated combinatorial considerations, making it hard to apply those ideas to other settings of interest.

In this talk I will discuss a fundamentally new (analytic) approach to Friedman's theorem which yields an elementary proof that can be written in just a few pages. Our approach also allows us to establish strong convergence (i.e. sharp norm estimates) for much more general models of tuples of random matrices (random regular graphs corresponding to the particular case of adding independent random permutations). These results can be used to show that certain infinite objects admit very strong finite dimensional approximations, which has important implications in operator algebras, spectral geometry, and differential geometry.

This is joint work with Chi-Fang Chen, Joel Tropp, and Ramon van Handel.