We will continue our discussion on Marcus-Spielman-Srivastava's interlacing polynomial method. This time we will focus on their result on existence of an infinite family of Ramanujan graphs of any degree. A Ramanujan graph is a d-regular graph with its adjacency matrix has all non-trivial eigenvalues lie in between -2\sqrt{d-1} and 2\sqrt{d-1}. Their main result is the following: For any Ramanujan graph G, there exists a 2-lift of G which is also a Ramanujan graph. In particular, since the properties of bipartite and (c,d)-biregular of a graph automatically pass to its 2-lifts, the result also extends to infinite family of bipartite Ramanujan graphs of degree d and (c,d)-regular bipartite Ramanujan graphs.

Similar to their proof of Kadison-Singer problem we dicussed in last semester, their proof is the following:
1. The expected characteristic polynomial of the signing adjacency matrix correspond to a random 2-lift of G has its eigenvalue nicely bounded.
2. Using interlacing polynomial method, there exists one 2-lift of G such that roots of its characteristic polynomial of the signing adjacency matrix has the same bound for the expected characteristic polynomial.
Speaker(s): Han Huang (University of Michigan)