Vorlesung Matroide

Vorlesung Matroide

2 Std. Di. 10 - 12 Uhr

im Seminarraum des ZPR

Skript: Präliminarien, Kapitel 1 Kapitel 2 Kapitel 3 Kapitel 4 Kapitel 5 Literatur

Matroide wurden 1935 von Hassler Whitney in seiner Arbeit "On the abstract properties of linear dependence" eingeführt. Dabei stellte er eine Struktur vor, die Eigenschaften der Abhängigkeit von den algebraischen Verknüpfungsoperationen abstrahiert. Fundamentale Beispiele sind einerseits Graphen, andererseits Matrizen. In der zweiten Ausgabe der Modernen Algebra (1937) beobachtete van der Waerden diese Struktur in transzendenten Körpererweiterungen. Grundlegend sind ferner die Arbeiten über geometrische Verbände von Birkhoff und MacLane (1935-38).

In diesem Kurs wollen wir eine Einführung in die Matroidtheorie geben, dabei einige der zueinander kryptomorphen Axiomensysteme kennenlernen und ihre Äquivalenz beweisen. Neben fundamentalen Beispielen werden wir algorithmische Aspekte diskutieren. Vorausgesetzt werden gute Kenntnisse der linearen Algebra. Grundkenntnisse in kombinatorischer Optimierung oder Graphentheorie sind nützlich.

Literatur:

J.G. Oxley:

Matroid Theory, Oxford University Press (1992)

M. Aigner:

Kombinatorik II. Matroide und Transversaltheorie, Springer-Verlag (1976)

D.J.A. Welsh:

Matroid Theory, Academic Press (1976)

E. Lawler:

Comb. Optimization: networks and matroids, Holt, Rinehart and Winston (1976)