WiSe 19/20: Discrete Mathematics II - Extremal Comb.
Tibor Szabo
Comments
Extremal Combinatorics investigates the general question: for a given property P, how large/small a set family satisfying P can be? Answers are more often asymptotic than exact, but always beautiful. The underlying base set could be without any structure or be equipped with some (such as the set of integers or a vector space). Many of the fundamental problems of Combinatorics can be formulated in this framework. For example, the optimization of one graph parameter with respect to others is the main object of the subfield of Extremal Graph Theory and is often relevant in theoretical computer science. 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) Extremal graph theory and the probabilistic method: Ramsey- and Turán- theory, Szemerédi's Regularity Lemma, Roth's Theorem, and further selected topics.
2) Extremal combinatorics and the linear algebraic method: Sperner's Theorem, Kruskal-Katona Theorem, restricted intersections and applications, sunflowers and cap-sets.
3) Topological methods: Sperner's Lemma, independent transversals, and Kneser's conjecture.
Suggested 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
32 Class schedule
Additional appointments
Thu, 2020-02-20 09:00 - 12:00
Location:
T9/Gr. Hörsaal (Takustr. 9)
Regular appointments