Bipartite Ramanujan Graphs of Every Degree

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”.

Joint work with Adam Marcus and Nikhil Srivastava.