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.

# 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: