Joint GAMP-OA seminar: Nikhil Srivastava

Speaker: Nikhil Srivastava (University of California, Berkeley).

Title: Ramanujan Graphs and Finite Free Probability

Abstract: An expander is a constant degree graph whose adjacency operator has a large spectral gap. 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.