Seminar at SMU Delhi

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. Their proof uses Deligne’s proof of the Ramanujan conjectures. 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-covers of every graph. Our proof exploits a new technique for controlling the eigenvalues of random matrices that we call the ``Method of Interlacing Polynomials''. The polynomials that arise in this method simultaneously generalize the characteristic polynomial of a single matrix and the mixed discriminant of a collection of matrices. We conclude by discussing how the same method can also be used to solve the Kadison-Singer problem in operator algebras. This is a joint --work with Adam Marcus and Dan Spielman.