Seminar über Graphentheorie

Inhalt

Im Seminar werden wir die Grundlagen der Minorentheorie behandeln. Der Beweis von Wagners Vermutung, nach der es keine unendlichen Antiketten hinsichtlich der Minorenrelation gibt, ist eines der aufwendigsten modernen Ergebnisse der Diskreten Mathematik überhaupt. Wir werden zwei faszinierende Teilaspekte (Baumzerlegungen und Gittersatz) im Seminar detailliert behandeln und von dort aus in gröberer Auflösung in den gesamten Beweishergang blicken.

Vorkenntnisse

Vorkenntnisse im Umfang der Graphentheorie I.

Literatur

Das Seminar folgt, wie auch die Vorlesungen über Graphentheorie, zunächst dem Buch Graphentheorie von Reinhard Diestel. Wir werden im weiteren Verlauf vor allem die englische Originalfassung heranziehen, in der unser Thema noch etwas ausführlicher behandelt wird.

Beide Werke sind elektronisch verfügbar auf Reinhard Diestels Homepage.

Verlauf

Datum	Thema
24.4.2007	WQO und der Satz von Kruskal I (D. Timor)
8.5.2007	WQO und der Satz von Kruskal II (D. Timor)
15.5.2007	Baumzerlegungen (12.3.1 bis 12.3.7) (A. Mischeff)
22.5.2007	Netze I (12.3.8 und 12.3.9) (D. Bassen)
5.6.2007	Netze II (12.3.8 und 12.3.9) (D. Bassen)
12.6.2007	Schlanke Baumzerlegungen (12.3.10 bis 12.4.2) (D. Timor & A. Mischeff)
19.6.2007	Der Gittersatz I (12.4.3 bis 12.4.5) (A. Mischeff)
26.6.2007	Der Gittersatz II (12.4.6 bis 12.4.8) (A. Mischeff & D. Timor)
3.7.2007	Der Gittersatz II (12.4.8) (D. Timor)
10.7.2007	Der Gittersatz IV (Beweis von 12.4.4) (D. Bassen)

(Numerierung nach der englischen Ausgabe von Reinhard Diestels Graphentheorie-Lehrbuch, siehe oben.)