21-737 Probabilistic Combinatorics

12 units, Carnegie Mellon University

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ödl nibble, the Lovász 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ös-Rényi random graph, and the Barabási-Albert preferential attachment model. (Three 50 minute lectures)

Prerequisites: (21-301 or 21-701 (min B)) and (21-325 or 36-225 or 15-259 or 36-218)

Offered: Spring 2027, Fall 2025

Courseweave needs JavaScript to show sections, workloads and planning tools.