MATH 233A: Geometry of polynomials and non-constructive proofs in combinatorics
Stanford University, Spring 2018
Lectures: Tue/Thu 10:30 - 11:45 AM, Building 200, Room 015 Instructor: Jan Vondrak (jvondrak@stanford.edu) Office hours: Monday 3-4 PM (383-J) Course description:
This course is about methods in combinatorics that prove the existence of certain objects
without constructing them explicitly.
In particular, we will discuss methods that rely on the location
of roots of certain polynomials.
We will also discuss the question of finding the relevant objects algorithmically.
The main two topics in this course are
The Lovasz Local Lemma, and its generalization, Shearer's Lemma.
The relevant polynomials here are the independence polynomials of graphs.
Stable polynomials, in particular as applied to the Kadison-Singer problem.
The relevant polynomials here are the characteristic polynomials of matrices.
Course requirements:
Bi-weekly homework assignments
Scribing a lecture allows you to skip one homework