# A good lift: bipartite Ramanujan graphs of all degrees

-
Daniel Spielman, Yale University
Fine Hall 214

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.