|
|
Unendliche Graphentheorie, WS 2019/20
Vorlesungstermine
Montags, 10:15 - 11:45 Uhr, Geomatikum H3
Übungstermine
Montags, 12:15 - 13:45 Uhr, Geomatikum 432 (Max Pitz)
Montags, 16:15 - 17:45 Uhr, Geomatikum 415 (Jan Kurkofka)
|
Inhalt
Die Graphentheorie ist eines der
jüngsten und zugänglichsten Gebiete der Mathematik.
Hier begegnet man vom ersten Tag an
mathematischen Problemen, die man im Prinzip ohne
weitere Voraussetzungen selbst bearbeiten könnte. Unendliche Graphentheorie ist ein faszinierendes Teilgebiet der Graphentheorie, deren Reiz unter anderem darin besteht, dass Beweise im Gegensatz zu den endlichen Induktionsbeweisen viel algorithmischer und konstruktiver sein müssen -- und dann oftmals auch neue Einblicke im Rückschluss auf endliche Graphen erlauben.
Die Vorlesung folgt anfangs dem 8. Kapitel des Buchs Graph Theory (Springer, Graduate Text in Mathematics 173) von Reinhard Diestel. Dort
ist der netto-Vorlesungsstoff (Definitionen, Aussagen,
Beweise) vollständig zu finden, so dass in der Vorlesung
niemand diesen Grundstoff mitschreiben muss und sich auf
den dort gebotenen Mehrwert konzentrieren kann: woher
die Begriffe kommen, welchem Ziel sie dienen, welche
Ideen den Beweisen zugrundeliegen und welche scheinbar
offensichtlicheren Ideen nicht funktionieren, und
weshalb nicht. Weitere Quellen für den späteren Teil der Vorlesung werden auch hier online zur Verfügung gestellt.
Voraussetzungen
Die Vorlesung wendet sich typischerweise an Hörer im
Mastersemester, und setzt das Material aus der Graphentheorie 1 voraus. Vorherige oder gleichzeitige Teilnahme an der Vorlesung
"Graphentheorie 2" ist nicht Voraussetzung. Bekanntschaft mit etwas Logik und Mengenlehre (Ordinalzahlen etc) ist vorteilhaft aber nicht nötig.
Übungsblätter
Zur Vorlesung gibt es Übungen, die durchaus
über den Vorlesungsstoff hinausgehen können und auf die aktuelle Forschung hinführen. Die Übungsblätter erscheinen im wöchentlichen Rhythmus. Sie werden Ihre Lösungen in den Übungen mündlich präsentieren. Hierzu tragen Sie sich jeweils vor der Übung in eine Liste ein, welche Aufgaben Sie gelöst haben und bereit sind, vorzutragen. Denken Sie beim Vortragen an das Schema: Situation -- Complication -- Solution, d.h. erinnern Sie Ihre Kommilitonen kurz daran, was eigentlich das Problem / die Aufgabe war, wo eventuell die Schwierigkeit der Aufgabe liegt, und erst dann, wie Ihre Lösung aussieht.
Leistungsnachweis
Bestehen der schriftlichen/mündlichen Prüfung. Für die Prüfungszulassung wird eine erfolgreiche Teilnahme an der Übung vorausgesetzt (Lösen von mindestens 50% der Aufgaben). Wenn Sie eine Woche wegen Krankheit verpassen, wird diese Woche bei Vorlegen eines Attests (kurze Email an mich) von den 50% rausgerechnet.) Allgemeine Tipps zum Ablauf,
zur Vorbereitung, und zum Prüfungsstoff gibt es hier.
Material
Logbuch
Ex.x beziehen sich auf die Kapitel in der englischen Version des Buches.
- 14. Oktober: Spannbäume in unendliche Graphen, Lemma von Zorn, Wohlordnungen. (E8.1 bis erster Beweis von 8.1.1 + Appendix A Anfang.)
- 21. Oktober: Ordinalzahlen, transfinite Induktion, Äquivalenzen zum Auswahlaxiom. (E8.1 bis zweiter Beweis von 8.1.1 + Appendix A Mitte.)
- 28. Oktober: Kompaktheit, das Erdös-deBruijn-Theorem 8.1.3 sowie Unfriendly Partition Conjecture für lokal endliche Graphen. (E8.1 bis page 217 + Appendix A Ende.)
- 4. November: Rekursive Strukturen, Rank, sowie Unfriendly Partition Conjecture für strahlenlose Graphen. (E8.5). Im letztgenannten Theorem 8.5.3 ist eine kleine Korrektur nötig. Für Neugierige: Hier ist das Paper zu den Unfriendly partitions of rayless graphs für beliebige Kardinalitäten.
- 11. November: Rays, ends and star-comb lemma (E8.1 bis Ende; E8.2.1 und 8.2.2) sowie das Diestel-Kühn Direction Theorem (siehe Theorem 2.2 hier).
- 18. November: Normale Spannbäume und Jungs Sätze (Fortsetzung E8.2 bis 8.2.4 sowie Übungen 8.35 und 8.40 (Jungs Dispersed Set Characterization)).
- 25. November: Overloaded graphs, T-graphs und Aronszajn-Bäume. Statement der Diestel-Leader NST Charakterisierung durch verbotene Minoren. Beweis der hinreichenden NST-Bedingungen von Halin und Diestel wie in Theorem 2 hier.
- 2. Dezember: Disjunkte Strahlen, Ubiquity Vermutung sowie Halins Grid Theorem (Fortsetzung E8.2; Satz 8.2.5 bis 8.2.6).
- 9. Dezember: Erdös' Mengerversion für unendliche Graphen (Prop. 8.4.1), sowie alternierende Kantenzüge und Gallai's konstruktiver Beweis von Menger (Lemma 3.3.2 und 3.3.3).
- 16. Dezember: Der Aharoni-Berger Satz für abzählbare Graphen, Unendliche Matchingtheorie (Kapitel 8.4 bis Ende).
- 6. Januar: Universelle Graphen (Kapitel 8.3 komplett). Homogene universelle Strukturen und Fraisse Limits.
- 13. Januar: Nash-Williams' cycle decomposition theorem and Laviolette's cut-faithful decomposition theorem.
- 20. Januar: Mehr zur Ubiquity Vermutung: Linking Lemmas, WQO-Resultate, sowie Beweis, dass ein-endige lokal endliche Graphen mit Endengrad 1 Minoren-ubiquitous sind.
- 27. Januar: Ausblick: Topological ubiquity of countable trees.
|
