MATH 233: Non-constructive Methods in Combinatorics

Stanford University, Spring 2016

Lectures: Mon/Wed 9:00 - 10:15 AM, Building 200, Room 305
(NOTE THE CHANGE FROM OFFICIAL SCHEDULE!)
Instructor: Jan Vondrak (jvondrak@stanford.edu)
Office hours: Friday 3-4 (383-J)

Course description: This course is about methods in combinatorics that prove the existence of certain objects without constructing them explicitly.
We will cover several kinds of such methods: probabilistic, topological and algebraic. We will also discuss the computational question of constructing the respective objects efficiently.

Tentative topics: (in hindsight, clearly too ambitious)

Probabilistic:
- The Lovasz Local Lemma: satisfiability, coloring and rainbow objects
- Concentration of measure: discrepancy of set systems
Topological:
- Sperner's Lemma, Brouwer's fixed point theorem, and Nash equilibria in games
- Borsuk-Ulam Theorem: necklace theorems, graph coloring
Algebraic:
- Combinatorial Nullstellensatz: sum sets, regular subgraphs, graph/hypergraph coloring
- Interlacing polynomials: Ramanujan graphs, the Kadison-Singer problem

Course requirements:

Scribe 1-2 lectures
Bi-weekly homework assignments
Take-home final

Lecture notes:

Lecture 1: intro (no notes)
Lecture 2: The Lovasz Local Lemma
Lecture 3: Asymmetric LLL application: Ramsey numbers
Lecture 4: The Lopsided LLL and applications
Lecture 5: Shearer's Lemma
Lecture 6: Symmetric Shearer's Lemma
Lecture 7: The cluster expansion lemma
Lecture 8: Algorithmic LLL: Moser and Tardos
Lecture 9: Algorithmic LLL continued
Lecture 10: Algorithmic LLL for general probability spaces
Lecture 11: Discrepancy: Spencer's Theorem
Lecture 12: Algorithmic discrepancy by a random walk
Lecture 13: Algorithmic discrepancy continued
Lecture 14: Real-rooted polynomials and Newton's inequalities
Lecture 15: The Heilmann-Lieb Theorem
Lecture 16: Stable polynomials and stability-preserving transformations
Lecture 17: Ramanujan graphs from interlacing polynomials
Lecture 18: Ramanujan graphs continued
Lecture 19: The Kadison-Singer Conjecture
lecture 20: The Kadison-Singer Conjecture finished

Template for scribes: Math233-lec-sample.tex

Supplemental material:
A summary of the Big O notation.