Nikhil Srivastava, University of California at Berkeley
“Ramanujan Graphs from Finite Free Convolutions”
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 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.
Refreshments will be served in MC 5403 at 3:30 p.m. Everyone is welcome to attend.