902416 VO Ausgew. Kapitel aus Graphentheorie (2005S)

Ich möchte die Matchingtheorie als Thema der Vorlesung wählen, weil sie innerhalb des
relativ jungen mathematischen Gebietes der Graphentheorie eine sehr ausgereifte Theorie
darstellt. Sie hat ihren Ursprung in folgender Beobachtung von Tait (1880):
"Der Vierfarbensatz ist äquivalent dazu, dass die Kanten jedes planaren 3-regulären Graphen
ohne Schnittkante in drei perfekte Matchings partitioniert werden kann."
Tait wollte basierend auf dieser Beobachtung den Vierfarbensatz beweisen. Dies gelang
letztendlich bis heute nicht, aber - wie so oft in der Mathematik - gab dieser Ansatz Anlass
für eine schöne eigenständige Theorie.

Ich werde zu Beginn der Vorlesung die Grundlagen der Matchingtheorie wiederholen, also den Satz von Hall (Heiratssatz), den Satz von Tutte und den Algorithmus von
Edmonds zur Bestimmung eines Matchings maximaler Grösse. Danach werden wir uns mit der Struktur des Polytops der perfekten Matchings beschäftigen, das sind die
Konvexkombinationen aller perfekten Matchings eines fixen Graphen in einem für jeden Graphen natürlich definierten Vektorraum. Schliesslich werden wir ähnliche Betrachtungen im sogenannten Matchinggitter, das ist die Menge der Z-Linearkombinationen von perfekten Machtings, anstellen.