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


Course information: Postscript PDF

Homework 1: Postscript PDF