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 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:30 or by appointment

Homework 1: Postscript PDF Hints for Homework 1: Postscript PDF Homework 2: Postscript PDF Hints for Homework 2: Postscript PDF Homework 3: Postscript PDF Hints for Homework 3: Postscript PDF Homework 4: Postscript PDF Hints for Homework 4: Postscript PDF Homework 5: Postscript PDF Hints for Homework 5: Postscript PDF

Week 1: Notes on R(3,t). Alon and Spencer, Probabilistic Lense Triangle-free graphs have large independence numbers .

Week 2: Second moment method. Alon and Spencer Section 4.5 Clique Number and Chvatal and Reed: Mick gets some (the odds are on his side) , FOCS, 1992, pp. 620--627.

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

Week 4: The Moser-Tardos Local Lemma Algorithm. See Moser and Trados: A constructive proof of the general Lovasz Local Lemma , Journal of the ACM 57 (2010) (2) Art. 11, 15pp. Also see some notes written by Joel Spencer and Section 5.7 of Alon and Spencer.

Week 5: Correlation Inequalities (and partial orders). Alon and Spencer: Chapter 6.

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: Dynamic Concentration. Notes on Random Sequential Independent Set

Week 11: Branching processes and the giant component. See Janson, Luczak and Rucinski Section 5.2

Week 12: Introduction to finite markov chains. See Chapters 1, 2 Levin, Peres, and Wilmer.

Week 13: Markov chain monte carlo and mixing. See Chapters 3, 4, 5 of Levin, Peres, and Wilmer.

Week 14: Path coupling. See Chapter 14 of Levin, Peres, and Wilmer.

Week 15: student presentations.