Graduate Courses
**21-738**

** Extremal Combinatorics**

12 units

Classical problems and results in extremal combinatorics including the Turán and Zarankiewicz problems, the Erdős-Stone theorem and the Erd\H{o}os-Simonovits stability theorem. Extremal set theory including the Erdős-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 **R**^{n} and Borsuk's conjecture. Graph decomposition including Graham-Pollack and Baranyai's theorem.