Expander graphs are very sparse graphs which are nonetheless very well-connected, in the sense that their adjacency matrices have large spectral gap. There is a limit to how large this gap can be for a d-regular graph, and graphs which achieve the limit are called Ramanujan graphs. A beautiful number-theoretic construction of Lubotzky-Phillips-Sarnak and Margulis shows that infinite families of Ramanujan graphs exist for every d=p+1 where p is prime, leaving open the question of whether they exist for other degrees.

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. 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 rely on simple facts from the theory of real stable polynomials. In particular, they do not rely on number theory, and the talk should be accessible to a broad audience.

Joint work with Adam Marcus and Dan Spielman.