Nikhil Srivastava (Berkeley)
Monday, February 6, 2017, 2:00pm
Title: 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, as well as finite analogues of tools from Free Probability.
Joint work with Adam Marcus and Daniel Spielman.