21-738 Extremal Combinatorics

12 units, Carnegie Mellon University

Classical problems and results in extremal combinatorics including the Turán and Zarankiewicz problems, the Erdos-Stone theorem and the Erdos-Simonovits stability theorem. Extremal set theory including the Erdos-Rado sunflower lemma and variations, VC-dimension, and Kneser's conjecture. The Szemeredi regularity lemma. Algebraic methods including finite field constructions and eigenvalues and expansion properties of graphs. Shannon capacity of graphs. Chromatic number of Rn and Borsuk's conjecture. Graph decomposition including Graham-Pollack and Baranyai's theorem. (Three 50 minute lectures)

Prerequisites: (21-355 (min B) or 21-235 (min B) or 21-455 (min B)) and (21-373 (min B) or 21-237 (min B))

Offered: Spring 2026

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