Extremal Combinatorics

12 units · Graduate

Intermittent: 12 units Classical problems and results in extremal combinatorics including the Tur and #225;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. grade B or 21-235 Min. grade B or 21-455 Min. grade B) and ( 21-373 Min. grade B or 21-237 Min. grade B)