Hermann Weyl Lectures

Topic: Ramanujan graphs of every degree

Date & Time: Thursday November 6th, 2014, 2:00pm - 3:00pm

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.

Speaker: Daniel Spielman

Affiliation: Yale University

Location: S-101

Video: http://video.ias.edu/weyl/2014/1106-DanielSpielman