WiSe 19/20: Diskrete Mathematik II - Extremal Comb.
Tibor Szabo
Kommentar
Extremal Combinatorics untersucht die allgemeine Frage: Wie groß/klein kann eine bestimmte Familie, die P erfüllt, für eine bestimmte Eigenschaft P sein? Antworten sind oft asymptotischer als exakt, aber immer schön. Der zugrundeliegende Basissatz könnte ohne Struktur sein oder mit einiger ausgestattet sein (z.B. der Satz von ganzen Zahlen oder ein Vektorraum). Viele der grundlegenden Probleme der Kombinatorik lassen sich in diesem Rahmen formulieren. So ist beispielsweise die Optimierung eines Graphenparameters in Bezug auf andere das Hauptobjekt des Teilbereichs der Extremal Graph Theory und ist in der theoretischen Informatik oft relevant. In diesem Kurs behandeln wir die Klassiker sowie einige wichtige Neuentwicklungen. Neben den üblichen kombinatorischen Werkzeugen legen wir besonderen Wert auf das systematische Studium verschiedener Methoden, die aus anderen Bereichen der Mathematik entstanden sind. Zu den Themen gehören:
1) Extremer Graphentheorie und der probabilistischen Methode: Ramsey-Theorie, Szemerédis Regularität Lemma, Roths Theorem und weitere ausgewählte Themen.
2) Extreme Kombinatorik und das lineare algebraische Verfahren: Sperner's Theorem, Kruskal-Katona Theorem, begrenzte Kreuzungen und Anwendungen, Sonnenblumen und Kappenuntergänge.
3) Topologische Methoden: Sperner's Lemma, unabhängige Transversalen und Kneser's Vermutung.
Literaturhinweise
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 Termine
Zusätzliche Termine
Do, 20.02.2020 09:00 - 12:00
Räume:
T9/Gr. Hörsaal (Takustr. 9)
Regelmäßige Termine der Lehrveranstaltung