Computer Science/Discrete Mathematics Seminar II

I will discuss methods for deriving bounds on the roots of polynomials, and how one can use such bounds to assert the existence of combinatorial structures with certain spectral properties. This will include introducing the "method of interlacing polynomials" and showing how one can use it prove the existence of Ramanujan graphs. Lastly, I will show how one can interpret these methods as a finite version of the previous week's results. That is, for certain problems, we can take the asymptotic results from the previous lecture and use them to prove bounds on nonasymptotic structures (like graphs). Only the last part will assume knowledge from the previous talk.