Nikhil Srivastava: Ramanujan Graphs from Finite Free Convolutions

Abstract:  We show that a random d-regular bipartite graph is an optimal (i.e.,
Ramanujan) expander with nonzero probability. Notably, we use tools
inspired by asymptotic (i.e., large n limit) random matrix theory to prove
statements about finite dimensional matrices. The mediating role is be
played by the expected characteristic polynomials of the random matrices in
question, exploiting in particular their real-rootedness, interlacing, and
invariance properties. Our analysis of the roots of these polynomials is
based on finite analogues of tools from Free Probability Theory.

Joint work with Adam Marcus and Daniel Spielman.