Vorlesung: Extremale Graphentheorie
Termine
- 05.04.2016 (erste VL)
- 13.04.2016 (erste UE)
- 05.05.2016 Feiertag (Christi Himmelfahrt)
- 16.-20.05.2016 Pfingstferien
VL |
Dienstag |
12:15 - 13:45 |
Geomatikum, H6 |
VL/UE |
Donnerstag (2-wöchentlich im Wechsel) |
12:15 - 13:45 |
Geomatikum, H3 |
Leistungsnachweis
- Bestehen der mündlichen Prüfung
- Termin nach Absprache
Zuordnung
- Spezialvorlesung, Master, 12LP
- 3+1 SWS
- Graphentheorie, Diskrete Mathematik
Voraussetzungen
- Graphentheorie I (und nach Möglichkeit auch Graphentheorie II)
Inhalte
In der Vorlesung werden die wichtigsten Fragestellungen, grundlegenden Methoden und zentralen Sätze der Extremalen Graphentheorie vorgestellt.
- Einführung (05.04.)
- Satz von Turán,
Sätze von Kövari, Sós und Turán und von Erdős und Stone,
Stabilitätssatz von Simonovits (07.04.-19.04.)
- Szemerédis Regularitätslemma und dessen Varianten und Anwendungen, Counting Lemma, Removal Lemma (26.04.-)
Übungen
In den Übungen wird der Stoff der Vorlesung vertieft und es werden die Übungsaufgaben
besprochen und von den Studierenden vorgetragen. Für das Bestehen der Übung ist es
erforderlich 50% aller Punkte zu erreichen.
Die Übungsaufgaben werden in der Übung und auf dieser Webseite bekanntgegeben.
Literatur
- N. Alon & J. H. Spencer, The probabilistic Method Wiley, 3rd ed., 2008
- B. Bollobás, Extremal graph theory, Academic Press, 1978
- R. Diestel, Graph Theory, Springer, 3rd ed., 2005
|