21-738: Extremal Combinatorics (Spring 2016)

Last updated 18 April 2016.

Location

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.

Announcements