Minorentheorem

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.

Satz

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)

Jede unendliche abzählbare Menge ${\displaystyle {\mathcal {G}}=\{G_{1},G_{2},\dotsc \}}$ von endlichen Graphen, die abgeschlossen bzgl. der Bildung von Minoren ist (d. h., alle Minoren von Graphen in ${\displaystyle {\mathcal {G}}}$ sollen ebenfalls zu ${\displaystyle {\mathcal {G}}}$ gehören) lässt sich durch eine endliche Menge „verbotener Minoren“ definieren, d. h., es gibt eine endliche Menge ${\displaystyle {\mathcal {H}}=\{H_{1},\dotsc ,H_{n}\}}$ endlicher Graphen, so dass ${\displaystyle {\mathcal {G}}}$ übereinstimmt mit der Menge aller endlichen Graphen, die keinen Graphen aus ${\displaystyle {\mathcal {H}}}$ als Minor enthalten.

Beispiel

Ein Beispiel ist die Menge ${\displaystyle {\mathcal {G}}}$ 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 ${\displaystyle {\mathcal {H}}=\left\{K_{5},K_{3,3}\right\}}$.

Auch für jede andere Fläche ${\displaystyle {\mathcal {S}}}$ ist die Menge ${\displaystyle {\mathcal {G}}}$ der in ${\displaystyle {\mathcal {S}}}$ einbettbaren Graphen abgeschlossen bzgl. der Bildung von Minoren, es gibt also eine endliche Menge ${\displaystyle {{\mathcal {H}}_{\mathcal {S}}}}$ von „verbotenen Minoren“, die alle in ${\displaystyle {\mathcal {S}}}$ einbettbare Graphen charakterisieren.

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

Literatur

• Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0 (Online-Version der englischen Ausgabe)
• Laszlo Lovasz: Graph Minor Theory, Bulletin AMS, Band 43, 2005, S. 75–86, PDF

Einzelnachweise

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