PACM Colloquium: Applications of interlacing polynomials in graph theory

Speaker: 
Adam Marcus - Princeton University
Date: 
Oct 19 2015 - 4:30pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

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.