Applications of interlacing polynomials in graph theory

Monday, October 19, 2015 -
4:30pm to 5:30pm
In this talk, I will discuss some recent applications of interlacing polynomials in graph theory. I will begin by discussing the more classical results concerning graph polynomials, including the real rootedness of the matching polynomial and the extension of Chudnovsky and Seymour to the independence polynomial of claw-free graphs. I will then discuss results using the ``method of interlacing polynomials'' developed by the speaker with Daniel Spielman and Nikhil Srivastava. In particular, I will mention recent results concerning the existence of Ramanujan graphs of all sizes and degrees as well as a recent improvement of the best known upper bound on the integrality gap in the asymmetric traveling salesman problem due to Anari and Oveis-Gharan.
Adam Marcus
Princeton University
Event Location: 
Fine Hall 214