##
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,
Markov chains, the phase transition in the
Erd\H{o}s-R\'enyi random graph, and the
Barab\'asi-Albert preferential attachment model.

##
Course Instructor:

Tom Bohman
Wean Hall 6105
tbohman@math.cmu.edu
Office Hours: Wednesday 3:00-4:0 or by appointment

Homework 2:
Postscript
PDF
Hints for Homework 2:
Postscript
PDF

###
Tentative schedule:

Week 1: Alon and Spencer, Probabilistic Lenses
`Triangle-free graphs have large independence numbers' and
`Crossing numbers, incidences, sums
and products'.
Week 2: Second moment method. See Alon and Spencer Sections 4.5 Clique Number and
4.6 Distinct Sums.

Week 3: Second moment method. Satisfiability threshold for random 2-SAT. See
Chvatal and Reed: Mick gets some (the odds are on his side), FOCS, 1992, pp. 620--627.

Week 4: Lovasz Local Lemma (and linear arboricity).
Alon and Spencer: Sections 5.1, 5.2, 5.5

Week 5: The Moser-Tardos Local Lemma Algorithm. See Moser and Trados:
A constructive proof of the general LovĂˇsz Local Lemma, Journal of the ACM 57 (2010) (2) Art. 11, 15pp. Also see some notes written by Joel Spencer.

Week 6: Janson's Inequality. See Alon and Spencer Section 8.1-8.3. Diameter of a
random graph.

Week 7: Martingales and tight concentration. See Alon and Spencer 7.1-7.4.

Week 8: Martingales and tight concentration continued. See Janson, Luczak and Rucinski Remark 3.10