Vorlesungsankündigung:

SS 99: VL Matroidtheorie

gehalten von Prof. Dr. Martin Grötschel (ZIB und TU Berlin)

Matroide stellen eine gemeinsame Verallgemeinerung verschiedener Aspekte der Graphentheorie und der linearen Algbebra dar. Sie haben sich als fundamentale Objekte der Kombinatorik erwiesen und sind in den letzten Jahrzehnten intensiv untersucht worden. Insbesondere spielen sie auch eine interessante Rolle in der Kombinatorischen Optimierung. Viele kombinatorische Optimierungsprobleme lassen sich als Optimierungsprobleme über Unabhängigkeitssystemen von Matroiden oder Durchschnitten von Matroiden darstellen. Die Bestimmung von gewichtsmaximalen Zyklen in binären Matroiden hat z.B. Anwendungen im VLSI-Design und in der statistischen Mechanik. Matroide können unter anderem auch durch den Greedy-Algorithmus charakterisiert werden.

In dieser Vorlesung werden die Grundbegriffe und wichtige Konzepte der Matroidtheorie eingeführt. Insbesondere wird auf Repräsentierbarkeitsaspekte von Matroiden und Gesichtspunkte der Optimierungstheorie eingegangen.

Die Vorlesung ist zweistündig, sie beginnt am Montag, dem 19. April 1999.

Ort: MA 642

Zeit: 8.15 Uhr -- 9.45 Uhr

Voraussetzungen: Grundbegriffe der Graphentheorie und Linearen Algebra

Geplante Fortsetzung: keine

Übungen: keine

Scheinkriterien: keine

Auf Wunsch der Teilnehmer findet die Vorlesung gelegentlich zu anderen Terminen statt. In jeder Vorlesung wird der jeweils nächste Termin festgelegt. Termin und Ort werden auf dieser Internetseite angekündigt sowie durch Aushang an der Tür meines Büros MA 602 in der TU.

Literatur zur Vorlesung Matroidtheorie:

Oxley, James G.: Matroid theory; Oxford University Press; 1992
Truemper, K.: Matroid decomposition; Academic Press, Inc., Boston; 1992
Welsh, D. J. A: Matroid theory; L.M.S. Monographs. Vol. 8. London - New York - San Francisco: Academic Press; 1976

Bei der Ausarbeitung der Vorlesung wurden auch die folgenden Artikel bzw. Buchkapitel benutzt:

Barahona, F.; Grötschel, M.: On the cycle polytope of a binary matroid; J. Comb. Theory, Ser. B 40, 40-62 (1986).
Grötschel, M.; Truemper, K.: Decomposition and optimization over cycles in binary matroids; J. Comb. Theory, Ser. B 46, No. 3, 306-337 (1989).
Grötschel, M.; Truemper, K.: Master polytopes for cycles of binary matroids; Linear Algebra Appl. 114 / 115, 523-540 (1989).
Grötschel, Martin; Lovász, Laszlo; Schrijver, Alexander: Geometric algorithms and combinatorial optimization; 2. corr. ed. Berlin, Springer-Verlag (1993), Kapitel 7.5 und Kapitel 10.
Lovász, Laszlo Submodular functions and convexity. in: Bachem, A.; Grötschel, M.; Korte, B. (eds.) Mathematical programming. The state of the art, Bonn 1982. Berlin, Springer-Verlag, 235-257 (1983).

Weiterführende Literatur:

Joseph P. S. Kung A source book in matroid theory; Birkhäuser, Boston, 1986
(Dieses Buch enthält eine Vielzahl von Reprints wichtiger Artikel der Matroidtheorie und Erklärungen zu diesen Papern.)
A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. Ziegler: Oriented Matroids; Cambridge University Press, Cambridge, 1993
(Dieses Buch faßt die Forschung zu orientierten Matroiden, einer Verallgemeinerung von Matroiden, zusammen. Im Rahmen von orientierten Matroiden kann man zum Beispiel den Simplexalgorithmus auf kombinatorische Weise formulieren und verallgemeinern. Orientierte Matroide kann man als geometrische Abstraktionen von verschiedenen Konzepten der Kombinatorik, Konvexität, Topologie, aber auch der algebraischen Geometrie und des Operations Research ansehen. Dieses Buch ist die erste umfassende Aufarbeitung der Theorie orientierter Matroide.)

Vorlesungsinhalt:

1. Vorlesung am 19.4.1999, MA642, 8.15 Uhr - 9.45 Uhr

Kapitel 1: Unbhängigkeitssysteme:
Einführung von Unabhängigkeitssystemen, Zirkuit-Systemen, Basissystemen und der Rangfunktion für allgemeine Unabhängigkeitssysteme, Beispiele von derartigen Systemen: stabile Mengen, Cliquen, Matching, gerichtetes Traveling-Salesman-Problem etc.

2. Vorlesung am 26.4.1999, MA642, 8.15 Uhr - 9.45 Uhr

weiter mit Kapitel 1: Optimierungsprobleme auf Unbhängigkeitssystemen:
gewichtsmaximale unabhängige Menge, gewichtsminimale Basis, minimale abhängige Menge, minimaler Zyklus, maximaler Zirkuit (alles bezüglich Gewichtungen).
Kapitel 2: Matroiddefinitionen:
Drei äquivaltente Defintionssysteme für matroidale Unbhängigkeitssysteme und Beweis ihrer Äquivalenz, zwei Axiomensysteme für Zirkuitsysteme von Matroiden und Beweis ihrer Äquivalenz, fundamentaler Zirkuit.

3. Vorlesung am 4.5.1999, MA645, 8.15 Uhr - 9.45 Uhr

weiter mit Kapitel 2:
Ein Axiom für das Basissystem eine Matroids und Äquivalenzbeweis, Zwei-Axiomen-Systeme für die Rangfunktion eines Matroids, Darstellung eines allgemein Unabhängigkeitssystems als Durchschnitt von matroidalen Unabhängigkeitssystemen, weitere Beispiele von Zirkuitsystemen.
Kapitel 3: Beispiele von Matroiden:
Graphische Matroide, Matrix-Matroide, cographische Matroide.

4. Vorlesung am 17.5.1999, MA642, 8.15 Uhr - 9.45 Uhr

weiter mit Kapitel 3:
Uniforme Matroide, algebraische Matroide, affine Matroide, Matroide abgeleitet aus Abelschen Gruppen, Matroide mit drei oder weniger Elementen, geometrische Darstellung von Matroiden mit Rang 3 in der Euklidischen Ebene, einige konkrete Matroide, das Fano-Matroid, Partitionsmatroide, Transversalmatroide, Matroide und Elementarvektoren.

5. Vorlesung am 27.5.1999, MA645, 8.15 Uhr - 9.45 Uhr

Kapitel 4: Operationen auf/mit Matroiden
In diesem Kapitel werden die wichtigsten Operationen vorgestellt, die man mit oder auf Matroiden durchführen kann:
Restriktion eines Matroids auf eine Teilmenge, Entfernung von Elementen, Abschneiden, Elongation, Kontraktion, duale Matroide, Minorenbildung. Wichtige Beziehungen zwischen diesen Operationen werden formuliert und bewiesen.

6. Vorlesung am 31.5.1999, MA642, 8.15 Uhr - 9.45 Uhr

Kapitel 5: Repräsentierbarkeit von Matroiden
In diesem Kapitel werden die wichtigsten Resultate der Matroidtheorie bezüglich der Repräsentierbarkeit von Matroiden als Matrixmatroide über Körpern dargestellt. Es werden Beispiele für nicht-repräsentierbare Matroide angegeben und Matroide, die über jedem Körper repräsentierbar sind (z.B. graphische und cographische Matroide). Solche Matroide werden regulär genannt und charakterisiert. Darüber hinaus werden wichtige Eigenschaften von binären Matroiden gezeigt, es wird eine Charakterisierung von binären und ternären Matroiden angegeben über verbotene Minoren. Die fundamentale Zirkuit-Matrix und die fundamentale Cozirkuit-Matrix werden eingeführt.

7. Vorlesung am 7.6.1999, MA642, 8.15 Uhr - 9.45 Uhr

weiter mit Kapitel 5.

8. Vorlesung am 14.6.1999, MA642, 8.15 Uhr - 9.45 Uhr

Beendigung des Kapitel 5.
Kapitel 6: Graphische und cographische Matroide
Eindeutigkeit des einem graphischen Matroiden zugehörigen Graphen, falls dieser dreifach zusammenhängend ist, Regularitäat von graphischen und cographischen Matroiden, Charakterisierung von graphischen und cographischen Matroiden durch verbotene Minoren, Charakterisierung von graphischen Matroiden, die durch planare Graphen induziert werden, durch verbotene Minoren.

9. Vorlesung am 21.6.1999, MA642, 8.15 Uhr - 9.45 Uhr

Kapitel 7: Matroid-Eigenschaften: algorithmisch betrachtet
Inputlänge eine Matroids, Matroide, gegeben durch Unabhängigkeitsorakel, Zirkuitorakel, Basisorakel, Rangorakel, Beschreibung aller Möglichkeiten, eines dieser Orakel durch ein anderes in polynomialer Zeit zu simulieren, Angabe von orakelpolynomialen Algorithmen zur Entscheidung, ob ein Matroid graphisch ist oder nicht, cographisch ist oder nicht, regulär ist oder nicht; algorithmisch schwierige Matroidprobleme: Repäsentierbarkeit, Repäsentierbarkeit über einem fest vorgegebenen Körper, Uniformität etc.

10. Vorlesung am 28.6.1999, MA642, 8.15 Uhr - 9.45 Uhr

Kapitel 8: Matroidpolyeder, Optimierung über Matroiden
Diskussion des Greedy-Algorithmus, verschiedene Beweise für die Optimialität des Greedy-Algorithmus für Unabhängigkeitssyteme über Matroiden, Güteabschätzungen bei allgemeinen Unabhängigkeitssytemen, Matroiddurchschnittssatz, Matroidpolyeder und ihre Beschreibung, verschiedene Vollständigkeitsbeweise, Charakterisierung der Facetten des Matroidpolytops, vollständige Beschreibung des Durchschnitts von zwei Matroidpolyedern. Dualitätssätze, total duale Ganzzahligkeit, Spezialfälle: Polytop der Wälder und aufspannenden Bäume, Branching und Aboreszenpolytop.

11. Vorlesung am 5.7.1999, MA642, 8.15 Uhr - 9.45 Uhr

weiter mit Kapitel 8.

12. Vorlesung am 9.7.1999, MA645, 8.15 Uhr - 9.45 Uhr

Beendigung von Kapitel 8
Kapitel 9: Submodulare Funktionen
Verschiedene Charakterisierungen von submodularen Funktionen, Beispiele, Operationen mit submodularen Funktionen, Lovász-Erweiterung, Konvulotion, Dillworth Truncation, Polymatroide und erweiterte Polymatroide, der Greedy-Algorithmus für Polymatroide, Submodularität und Konvexität, Minimierung von submodularen Funktionen mit Hilfe der Ellipsoidmethode.

13. Vorlesung am 12.7.1999, MA642, 8.15 Uhr - 9.45 Uhr

Kapitel 10: Zyklen in binären Matroiden:
Untersuchung des Problems, einen maximalen gewichteten Zyklus in einem binären Matroiden zu finden, polyedrischer Ansatz, der Zykluspolytop, Charakterisierung des Zykluspolytops durch Seymours "Sum of Circuits"-Eigenschaft, verbotene Minorencharakterisierung dieser Eigenschaft, Bestimmung von maximalen Zyklen in binären Matroiden, die die "Sum of Circuits"-Eigenschaft haben, Spezialfall: Bestimmung von maximalen gewichteten Eulerschen Subgraphen, Max-Cut in planaren Graphen, Masterpolytope für Zyklen in binären Matroiden.