Minorentheorem

mathematischer Satz

Das Minorentheorem gilt als einer der tiefgreifendsten Sätze der Graphentheorie. Neil Robertson und Paul Seymour bewiesen es in einer Serie von 20 Veröffentlichungen mit über 500 Seiten. Der Teil 1 “Excluding a Forest”[1] erschien 1983, Teil 20 “Wagner’s Conjecture”[2] mit dem Abschluss des Beweises erschien 2004. Inzwischen gibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”.[3] Der Beweis ist nicht konstruktiv und liefert auch einen Beweis der Wagnerschen Vermutung.

Die endlichen Graphen sind durch die Minorenrelation wohlquasigeordnet.

So simpel dieser Satz anmutet, so komplex ist sein Beweis. Mit einigen Lemmata lässt sich aus dem Minorensatz die Wagnersche Vermutung folgern.

Wagnersche Vermutung (Satz von Robertson-Seymour)

Bearbeiten

Jede unendliche abzählbare Menge   von endlichen Graphen, die abgeschlossen bzgl. der Bildung von Minoren ist (d. h., alle Minoren von Graphen in   sollen ebenfalls zu   gehören) lässt sich durch eine endliche Menge „verbotener Minoren“ definieren, d. h., es gibt eine endliche Menge   endlicher Graphen, so dass   übereinstimmt mit der Menge aller endlichen Graphen, die keinen Graphen aus   als Minor enthalten.

Beispiel

Bearbeiten

Ein Beispiel ist die Menge   aller in die Ebene einbettbaren Graphen (also der planaren Graphen). Die planaren Graphen sind abgeschlossen bezüglich Minorenbildung, also gibt es eine endliche Menge von verbotenen Minoren, durch die sich alle planaren Graphen charakterisieren lassen. In diesem Fall ist nach dem Satz von Kuratowski  .

Auch für jede andere Fläche   ist die Menge   der in   einbettbaren Graphen abgeschlossen bzgl. der Bildung von Minoren, es gibt also eine endliche Menge   von „verbotenen Minoren“, die alle in   einbettbare Graphen charakterisieren.

Die einzige Fläche  , außer Ebene und Sphäre, für welche man die Menge   bisher explizit bestimmen konnte, ist die projektive Ebene. Hier besteht   aus 103 verbotenen Minoren.[4]

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Robertson, Seymour: Graph Minors. I. Excluding a Forest, Journal of Combinatorial Theory B, Band 35, 1983, S. 39–61
  2. Graph Minors. XX. Wagner's Conjecture, Journal of Combinatorial Theory B, Band 92, 2004, S. 325–357
  3. Graph Minors. XXIII. Nash-Williams' immersion conjecture, Journal of Combinatorial Theory B, Band 100, 2010, S. 181–205
  4. Dan Archdeacon: A Kuratowski Theorem for the Projective Plane. Graph Theory, Band 5, 1981, S. 243–246