21-801: Extremal Combinatorics (Spring 2010)

Last updated 31 January 2010.



This is a core course, and its content is vital to the career of any aspiring Combinatorialist. Grading will be rigorous, and based on the following three aspects.

Course Description

This is one of the core graduate courses in advanced combinatorial methods, for the Algorithms, Combinatorics, and Optimization program at CMU. As such, it will be a rigorous and challenging introduction to extremal combinatorics, aimed to provide the necessary background for cutting-edge research in this area. Typical problems concern the maximum or minimum values attained by common graph parameters over certain interesting families of combinatorial objects.

Extremal results are not only interesting in their own right, but are also useful in applications because sometimes one can already draw valuable conclusions from the combinatorial basis of a problem with deeper mathematical structure. In that case, the most easily accessible graph-theoretical properties are often the values of the graph parameters, such as the number of edges, diameter, size of the largest set of pairwise non-adjacent vertices, etc. It is therefore useful to understand what other properties are already implied once certain graph parameters lie in certain ranges.

This course will cover the following general areas. Although the topics are organized around central results, there will be particular emphasis on completely understanding the methods used to prove them.

Detailed Syllabus

Week 1 Classical theorems of Turán and Ramsey, with applications.
Week 2 Bipartite Turán problems.
Week 3 Algebraic constructions of extremal Turán graphs.
Weeks 4-5 Statement of Szemerédi's Regularity Lemma, and applications.
Week 6 Density increment arguments, and proof of Regularity Lemma.
Week 7 Stability arguments. Wed Feb 24 class cancelled.
Week 8 Sperner's Theorem and Littlewood-Offord Lemma; results of Bollobás and Erdős-Ko-Rado. Mon Mar 1 class cancelled.
Spring break    No meetings on Mon Mar 8 or Wed Mar 10.
Week 9 Kruskal-Katona and Sauer-Shelah.
Week 10 Sunflower Lemma.
Week 11 Linear algebra in Extremal Set Theory: Fisher, Oddtown, and Graham-Pollack.
Week 12 Frankl-Wilson Theorem and applications.
Week 13 Second half of student presentations.
Week 14 Lovasz-Kneser Theorem; dependent random choice.
Week 15 Median orders; continuous arguments.

You are visitor number since 10 January 2010.
[back home]