We prove that there exist infinite families of bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also construct infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. In particular, we construct infinite families of (c,d)-biregular bipartite Ramanujan graphs for all c and d greater than 2. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the ``Method of Interlacing Polynomials''. The proofs are elementary, and the talk should be accessible to a broad audience. Joint work with Adam Marcus and Nikhil Srivastava.
A good lift: bipartite Ramanujan graphs of all degrees
Daniel Spielman, Yale University
Apr 29 2013 - 4:30pm