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
Take-home final

Homework:

Problem set 1, due February 6
Problem set 2, due February 27
Problem set 3, due March 13

Lecture notes:

Lecture 1: Introduction
Lecture 2: The Lovasz Local Lemma
Lecture 3: The Lopsided Lovasz Local Lemma
Lecture 4: Shearer's Lemma
Lecture 5: Symmetric Shearer's Lemma
Lecture 6: The Cluster Expansion Lemma
Lecture 7: Algorithmic LLL
Lecture 8: Algorithmic LLL continued
Lecture 9: Algorithmic LLL for general probability spaces
Lecture 10: Correlation decay for Shearer's polynomials
Lecture 11: Real-rooted polynomials
Lecture 12: The matching polynomial and the Heilmann-Lieb theorem
Lecture 13: Stable polynomials and stability-preserving transformations
Lecture 14: Characterization of linear stability-preserving transformations
Lecture 15: Van der Waerden's conjecture and approximating the permanent by matrix scaling
Lecture 16: Approximating Nash Social Welfare using stable polynomials (guest lecture by Nima Anari)
Lecture 17: Ramanujan graphs from interlacing polynomials
Lecture 18: Ramanujan graphs continued
Lecture 19: The Kadison-Singer problem
Lecture 20: The Kadison-Singer problem completed

Template for scribes: Math233-lec-sample.tex

Supplemental material:
A summary of the Big O notation.