21-737 Probabilistic Combinatorics
This course covers the probabilistic method
for combinatorics in detail and introduces
randomized algorithms and the theory of
random graphs.
Methods covered include
the second moment method, the R\"odl nibble, the
Lov\'asz Local Lemma, correlation inequalities,
martingale's and tight concentration,
Janson's inequality, branching processes, coupling and
the differential equations method for discrete
random processes.
Objects studied include the
configuration model for random regular graphs
and the phase transition in the
Erd\H{o}s-R\'enyi random graph. If time permits we will introduce
hypergraph containers and/or the spread Lemma.
Course Instructor:
Tom Bohman
Wean Hall 8208
tbohman@math.cmu.edu
Office Hours: Wednesday 5:00-6:00 or by appointment
Homework 2
Homework 3
Midterm Review
Homework 4
Week 1:
Notes on R(3,t).
- Alon and Spencer, Probabilistic Lense, Turan's Theorem.
- Alon and Spencer, Probabilistic Lense, Triangle-free graphs have large independence numbers.
Second moment method.
-
Alon and Spencer, Section 4.5, Clique number.
Week 2:
2-SAT phase transition.
-
Chvatal and Reed: Mick gets some (the odds are on his side), FOCS , 1992, pp. 620--627.
-
2-SAT notes
Week 3/4:
Lovasz Local Lemma.
- Alon and Spencer, Sections 5.1, 5.2
- Alon and Spencer, Sections 5.5, The linear arboricity of graphs.
The Moser-Tardos Local Lemma Algorithm.
- Moser and Tardos:
A constructive proof of the general Lovasz Local Lemma,
Journal of the ACM 57 (2010) (2) Art. 11, 15pp.
- Notes written by Joel Spencer
- Alon and Spencer: Section 5.7 Moser's Fix-It Algorithm
-
Terry Tao's blog post on entropy compression.
Week 5:
Correlation Inequalities (and partial orders).
- Alon and Spencer: Sections 6.1, 6.2, 6.3.
Week 6:
Janson's Inequality.
- Alon and Spencer: Section 8.1, 8.2, 8.3.
- Diameter of a random graph. See Section 7.1 of Frieze and Karonski
Week 7:
Martingales and tight concentration.
- Alon and Spencer 7.1-7.4.