Rutgers Discrete Mathematics Seminar

Title: Interlacing Families: A New Technique for Controlling Eigenvalues

Speaker: Adam Marcus, Princeton University

Date: Monday, February 29, 2016 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


Matrices are one of the most fundamental structures in mathematics, and it is well known that the behavior of a matrix is dictated by its eigenvalues. Eigenvalues, however, are notoriously hard to control, due in part to the lack of techniques available. In this talk, I will present a new technique that we call the "method of interlacing polynomials" which has been used recently to give unprecedented bounds on eigenvalues, and as a result, new insight into a number of old problems. I will discuss some of these recent breakthroughs, which include the existence of Ramanujan graphs of all degrees, a resolution to the famous Kadison-Singer problem, and most recently an incredible result of Anari and Gharan on the Traveling Salesman problem that has produced an interesting anomaly in computer science. This talk will be directed at a general mathematics audience and represents joint work with Dan Spielman and Nikhil Srivastava.