Title: The Probabilistic Method and Roots of Polynomials
Speaker: Adam Marcus, Yale University
Date: Tuesday, September 10, 2013 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
I will present a new technique that my coauthors and I have named "the method of interlacing polynomials". It allows us to take certain collections of polynomials and assert the existence of a polynomial in the collection that has all of its real roots bounded in terms of the largest real root of the expected polynomial. In many ways, this seems exactly like the type of statement that comes from the probabilistic method, and in fact we will use this intuition to guide us. This is not a trivial task, however --- the behavior of the roots of sums of polynomials can have absolutely no relation to the constituent polynomials (there could be more roots, less roots, larger roots, no roots, etc). However there are certain cases (in particular, ones where the polynomials are generated by some combinatorial objects) where things behave well and such an assertion can be made. I will discuss two such cases and use them to solve long-standing open questions about the existence of certain Ramanujan graphs and what has become known as the Kadison Singer problem concerning maximal abelian subalgebras. The results are joint work with Nikhil Srivastava and Dan Spielman.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math