Graduate (reading) course on Interlacing Families

In April and June this year A. Marcus (Yale), D. A. Spielman (Yale) and N. Srivastava (Microsoft) posted two papers on the arXiv containing a new and very powerful method that may be applicable to a diverse set of problems in combinatorics, computer science, probability theory and C*-algebras. In the second paper they use their method to give a positive solution to the Kadison-Singer problem from 1959, and in the first paper they prove the existence of regular bipartite Ramanujan graphs of every degree, a problem that has been open for some time. Their method is particularly useful in bounding the eigenvalues of certain random hermitian matrices.

We will prove the main results in the papers. Our approach uses the theory of hyperbolic polynomials. The course will be mostly self-contained and we will cover relevant background from spectral graph theory and the hyperbolic polynomials.

Meetings will be held on Mondays 10-12, room 3733.

For further information see: