WiSe 21/22: Extremal Combinatorics
Tibor Szabo
Additional information / Pre-requisites
Prerequisite: Discrete Mathematics I or equivalent background (please contact the instructor)
Comments
Extremal Combinatorics investigates how large/how small can a collection of finite objects be if it satisfies certain properties. The underlying set could be equiped with some structure (such as the set of integers, the Euclidean plane, or a vector space) or have none (and simply host a graph or hypergraph). The desired properties can also vary greatly; many fundamental problems can be formulated in this framework and are often related to other areas including Computer Science, Information Theory, Number Theory, and Geometry. In this course we cover the classics as well as some important new developments. Besides the standard combinatorial tools we give particular emphasis to the systematic study of various methods that arose from other branches of mathematics. Topics include:
1) Struture and randomness in combinatorics: Ramsey- and Turán- theory, Szemerédi's Regularity Lemma, Roth's Theorem, independent sets and colorings.
2) Extremal combinatorics and the linear algebra method: Sperner's Theorem, Kruskal-Katona Theorem, restricted intersections and their applications, sunflowers and cap-sets.
3) Topological methods: Sperner's Lemma, independent transversals, and Kneser's conjecture.
closeSuggested reading
The material is selected from several textbooks:
N. Alon and J. Spencer, The Probabilistic Method
L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics
R. Diestel, Graph Theory
S. Jukna, Extremal Combinatorics
J. Matoušek, Using the Borsuk-Ulam Theorem
J. van Lint and R. Wilson, A Course in Combinatorics
D. West, Introduction to Graph Theory
close32 Class schedule
Additional appointments
Tue, 2022-01-25 16:00 - 18:00Regular appointments