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