Ramanujan graphs of every degree

Hermann Weyl Lectures
Topic:Ramanujan graphs of every degree
Speaker:Daniel Spielman
Affiliation:Yale University
Date:Thursday, November 6
Time/Room:2:00pm - 3:00pm/S-101
Video Link:http://video.ias.edu/weyl/2014/1106-DanielSpielman

We explain what Ramanujan graphs are, and prove that there exist infinite families of bipartite Ramanujan graphs of every degree. Our proof follows a plan suggested by Bilu and Linial, and exploits a proof of a conjecture of theirs about lifts of graphs. Our proof of their conjecture applies the method of interlacing families of polynomials to Mixed Characteristic Polynomials. A bound on the roots of these polynomials will follow from a bound of Heilmann and Lieb on the roots of the matching polynomials of graphs. We also prove that there exist infinite families of irregular bipartite Ramanujan graphs. This is joint work with Adam Marcus and Nikhil Srivastava.