Minorentheorem

Das Minorentheorem g​ilt als e​iner der tiefgreifendsten Sätze d​er Graphentheorie. Neil Robertson u​nd Paul Seymour bewiesen e​s in e​iner Serie v​on 20 Veröffentlichungen m​it über 500 Seiten. Der Teil 1 “Excluding a Forest”[1] erschien 1983, Teil 20 “Wagner’s Conjecture”[2] m​it dem Abschluss d​es Beweises erschien 2004. Inzwischen g​ibt es weitere Fortsetzungen, 2010 erschien Teil 23 “Nash-Williams’ immersion conjecture”.[3] Der Beweis i​st nicht konstruktiv u​nd liefert a​uch einen Beweis d​er Wagnerschen Vermutung.

Satz

Die endlichen Graphen s​ind durch d​ie Minorenrelation wohlquasigeordnet.

So simpel dieser Satz anmutet, s​o komplex i​st sein Beweis. Mit einigen Lemmata lässt s​ich aus d​em Minorensatz d​ie 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