Vorlesungsankündigung:
SS 99: VL Matroidtheorie
gehalten von Prof. Dr. Dr. h.c. mult. 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.