Interlacing Families, graduate (reading) course


Mondays 10:15-12:00 in room 3733. Here are lecture notes that will be updated continuously.

References

A. Marcus, D. A. Spielman, N. Srivastava, Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees, arXiv
A. Marcus, D. A. Spielman, N. Srivastava, Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem, arXiv
S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), 439-561, PDF
C. D. Godsil, Algebraic Combinatorics, Chapman and Hall/CRC, 1993. Amazon
J. Renegar, Hyperbolic programs, and their derivative relaxations, Foundations of Computational Mathematics 6 (1): 59-79. PDF
R. Pemantle, Hyperbolicity and stable polynomials in combinatorics and probability, Current Developments in Mathematics Volume 2011, PDF
D. G. Wagner, Multivariate stable polynomials: theory and applications, Bull. Amer. Math. Soc. 48 (2011), 53-84, PDF

Plan/What we have done

16/9: Introduction, basic spectral graph theory, two lifts
23/9: Matching polynomials, real-rooted polynomials
30/9: Real-rooted polynomials, Interlacing families
7/10: Hyperbolic polynomials
14/10: Hyperbolic polynomials, Mixed hyperbolic polynomials
21/10: Finished proof of existence of infinite families of Ramanujan graphs, Kadison-Singer problem
28/10: Almost finished proof of the hyperbolic version of Weaver's problem