Hermann Weyl Lectures

Ramanujan graphs of every degree

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.

Date & Time

November 06, 2014 | 2:00pm – 3:00pm

Location

S-101

Speakers

Daniel Spielman, Yale University

Affiliation

Yale University

Event Series

Categories