Topologie von Flächen CLXVII

Kreuzungen vermeiden (nicht bei Tomaten oder Garnelen, eher schon bei der Chip-Herstellung).

Wir hatten in den letzten Wochen über den Jordanschen Kurvensatz und den Satz von Schönflies geschrieben, die man letztlich braucht um die Klassifikation der Flächen zu beweisen. (Vor allem, um die Triangulierbarkeit von Flächen zu beweisen.) Eine andere Anwendung des Jordanschen Kurvensatzes war die Beantwortung der Frage, welche Graphen sich (kreuzungsfrei) in die Ebene einbetten lassen. Auch wenn das jetzt ein wenig vom Thema wegführt heute noch ein Einschub zu der analogen Frage nach der Einbettbarkeit von Graphen in anderen Flächen als der Ebene.

Letzte Woche hatten wir darüber geschrieben, daß man keinen Graphen in die Ebene einbetten kann, der die unten abgebildeten Graphen K_3,3 oder K₅ (oder eine ihrer Unterteilungen) als Teilgraphen enthält.

Wenn man einen Graphen in die Ebene einbetten kann, dann kann man ihn natürlich auch in jede andere Flächen einbetten. (Denn jede Fläche ist aus Karten zusammengesetzt, die Karten sind jeweils homöomorph zur Ebene, also kann man den in der Ebene eingebetteten Graphen dann auch in die in der Fläche liegende Karte einbetten.)

Aber natürlich hat man auf komplizierteren Flächen noch mehr Möglichkeiten, kompliziertere Graphen einzubetten, die sich in der Ebene nicht einbetten ließen.

Zum Beispiel kann man den Graphen K_3,3 zwar nicht in der Ebene, aber in den Torus einbetten:

Und auch den Graphen K₅ kann man in den Torus einbetten:

(DIe Bilder stammen von www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/embedding.htm.)

Und natürlich kann man diese beiden Graphen dann auch in die Brezel oder in Flächen mit noch mehr Henkeln einbetten: man denke sich einfach in obigem Bild weitere Henkel so an den Torus geklebt, daß sie den eingebetteten Graphen nicht berühren.

In der Ebene ließen sich Graphen genau dann einbetten, wenn sie keine Unterteilung von K_3,3 oder K₅ enthalten. Man kann sich fragen, ob es einen analogen Satz auch für den Torus oder andere kompliziertere Flächen gibt, also ob man zu einer gegebenen Fläche S eine Menge von Graphen G₁,…,G_n hat, so daß ein Graph G sich genau dann in S einbetten läßt, wenn er keine Unterteilung eines G_i als Teilgraphen enthält.

Diese Frage ist ein Spezialfall der sogenannten Wagner-Vermutung: wenn eine Menge M von Graphen abgeschlossen bzgl. Teilgraphen und Unterteilungen ist, dann gibt es eine endliche Menge von Graphen G₁,…,G_n, so daß ein Graph G genau dann zu M gehört, wenn er keine Unterteilung eines G_i als Teilgraphen enthält.

Diese Vermutung wurde von Robertson und Seymour in einem 20-teiligen Artikel im J.Combin.Theory B bewiesen. (Teil 1 “Excluding a Forest” erschien 1983, Teil 20 “Wagner’s Conjecture” mit dem Abschluß des Beweises erschien 2004. Inzwischen gibt es noch Fortsetzungen, letztes Jahr erschien Teil 23 “Nash-Williams’ immersion conjecture”.)

Wenn man zum Beispiel als Menge M die Menge aller Graphen nimmt, die sich in den Torus einbetten lassen, dann sagt der Satz von Robertson-Seymour (die Wagner-Vermutung) also, daß es endlich viele verbotene Graphen gibt, die ein in den Torus einzubettender Graph nicht als Teilgraphen haben darf (und auch keine ihrer Unterteilungen.)

Der Beweis von Robertson und Seymour ist aber nicht konstruktiv, man kennt diese Menge verbotener Teilgraphen für Einbettungen in den Torus bisher nicht. Man kann aber beweisen, daß diese Menge aus mehr als 800 Graphen bestehen muß.
Etwas irritierend: obwohl es einfacher ist, einen Graphen in den Torus einzubetten als in die Ebene, sind die Bedingungen für die Einbettbarkeit in den Torus viel komplizierter als für Einbettungen in die Ebene. Für die Ebene gab es nur zwei verbotene Teilgraphen (die sich aber beide in den Torus einbetten lassen), für den Torus hat man eine Liste von mehr als 800 verbotenen Teilgraphen, und man kennt diese Liste noch nicht einmal explizit.

Es gibt außer der Ebene (bzw. der Sphäre) überhaupt nur eine Fläche, für die man eine explizite Liste verbotener Teilgraphen kennt, nämlich für die projektive Ebene (TvF 155): für diese hatten Glover, Huneke und Wang 1978 eine Liste von 103 verbotenen Teilgraphen angegeben und Archdiacon bewies dann in einer 1981 veröffentlichten Arbeit, daß diese Liste vollständig ist.

Flötotto:”Embeddability of graphs…”, S.7-10

Robertson, N., & Seymour, P. (2004). Graph Minors. XX. Wagner’s conjecture Journal of Combinatorial Theory, Series B, 92 (2), 325-357 DOI: 10.1016/j.jctb.2004.08.001