21-801: Extremal Combinatorics (Spring 2010)

Last updated 31 January 2010.

Location

Class meets MW 9:30 - 11:00am in room 300 of the Physical plant.
Office hours Wednesday 2:30-3:30pm in Wean 6204 or 6th floor lounge.

Grading

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.

Homework: 3 assignments. No collaboration is permitted.
Presentation: Each student must give a one-hour talk.
Participation: Discussion during lectures is encouraged, and many questions will be asked in-class.

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.

Classical extremal graph theory: Theorems of Turán and Ramsey; bipartite Turán problems including trees, paths, and cycles; constructions of extremal graphs.
Szemerédi's Regularity Lemma: Statement, proof, and many applications; the stability method.
Extremal set theory: Theorems of Sperner, Bollobás, Erdős-Ko-Rado, Katona, Ahlswede-Khachatrian, Kruskal-Katona, Sauer-Shelah, with applications; sunflower method; linear algebra method for extremal set theory, and applications.

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]