21-738: Extremal Combinatorics (Spring 2024)
Last updated 18 January 2024.
Location
- Class meets MWF 2:00 – 2:50pm in Wean 8220
- Office hours by appointment.
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.