Matroide

Inhalt

In der Matroidtheorie wird der Begriff der linearen Unabhängigkeit und seiner Derivate wie Basis, Dimension, Hülle verallgemeinert. Dies erlaubt die Betrachtung so verschiedenartiger Objekte wie Vektorräume, Graphen, Repräsentantensystemen uvm. von einer gemeinsamen, kombinatorischen Warte aus.

Die Matroidtheorie ist inspiriert von ihren Spezialisierungen, entsprechend reich ist ihr Methodenschatz. Umgekehrt gibt sie mitunter sehr einfache und essentielle Beweise ansonsten schwieriger Sätze zurück, wie etwa den Baumpackunssatz an die Graphentheorie oder Kriterien für die Existenz gemeinsamer Repräsentantensysteme an die Kombinatorik. Dieses Wechselspiel ist einer ihrer faszinierendsten Aspekte.

Vorkenntnisse

Lineare Algebra im Rahmen einer Grundvorlesung.

Gelegentliche Ausflüge in die Algebra, Graphentheorie, kombinatorische Optimierung oder Topologie immer inklusive ortskundiger Reiseleitung.

Skript

Die Vorlesung wird von meinem Skript (deutsch) begleitet.

Eine PostScript-Datei der ersten acht Seiten steht hier.

Das vollständige Skript mit Inhaltsverzeichnis und Index habe ich an alle Hörer verschickt, wer es nicht bekommen hat, möge sich melden. Auch an dieser Stelle ein herzliches Dankeschön für die zahlreichen Kommentare und Anregungen!

Verlauf

Übungsaufgaben (Numerierung nach dem Skript):

• Aufgaben zum 5ten Juli 2006: 3.4: 1,2
• Aufgaben zum 28ten Juni 2006: 2.11: 14,15,16,17
• Aufgaben zum 21ten Juni 2006: 2.11: 10,11(+),12(-)
• Aufgaben zum 14ten Juni 2006: 2.11: 5,6,7,8(+),9
• Aufgaben zum 31ten Mai 2006: 2.11: 1,2,3,4
• Aufgaben zum 24ten Mai 2006: Wiederholung von Kapitel 1
• Aufgaben zum 17ten Mai 2006: 1.17: 6(+),24,25,28
• Aufgaben zum 10ten Mai 2006: 1.17: 21,22,23
• Aufgaben zum 3ten Mai 2006: 1.17: 18,19,20
• Aufgaben zum 26ten April 2006: 1.17: 4,15,16(+),17
• Aufgaben zum 19ten April 2006: 1.17: 8,9(+),10,13(-)
• Aufgaben zum 12ten April 2006: 1.17: 1(-),2,5,7

Literatur

Wesentliche Teile der Theorie sind in den folgenden drei Lehrbüchern dargestellt.

1. J. Oxley, Matroid Theory, Oxford University Press (1992).

2. A. Schrijver, Combinatorial Optimization, Springer-Verlag Berlin-Heidelberg (2003).

3. D. J. A. Welsh, Matroid Theory, Academic Press London (1976).