Theoretical Statistics and Mathematics Unit, ISI Delhi

October 15, 2014 (Wednesday) ,
3:30 PM at Webinar

Speaker:
Nikhil Srivastava,
Microsoft Research, Bangalore

Title:
Ramanujan Graphs and the Solution of the Kadison-Singer Problem

Abstract of Talk

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.