1968 bewiesen Ringel und Young die Heawood-Vermutung für Flächen höheren Geschlechts, also die Formel für die Anzahl benötigter Farben in Abhängigkeit vom Geschlecht. Beispielsweise braucht man – was schon Heawood bewiesen hatte – immer sieben Farben, um eine Karte auf dem Torus zu färben.

Zum klassischen Vier-Farben-Problem in der Ebene hatte seit den 30er Jahren aber eigentlich nur noch Heinrich Heesch gearbeitet. Er war in Göttingen Assistent von Hermann Weyl gewesen, hatte damals über Gruppen und Ornamente gearbeitet und als Reaktion auf die politischen Säuberungen 1933 seine Stelle an der Universität aufgegeben, dann bis einige Jahre nach dem Krieg als Privatgelehrter im Kieler Haus seiner Eltern gewohnt. Neben anderen Forschungen hatte er schon vor dem Krieg als erster den ursprünglichen Ansatz im Vier-Farben-Problem wieder aufgenommen und große Fortschritte sowohl im Reduzibilitätsaspekt wie in der Analyse unvermeidlicher Mengen erzielt. (Über die Struktur eines minimales Gegenbeispiel war durch Birkhoff einiges bekannt: jede Ecke hat Grad mindestens 5, nach Polyederformel gibt es mindestens 12 Ecken von Grad 5, also mindestens so viele wie im Gerüstgraph des Ikosaeders, es gibt keinen trennenden Graph der Länge < 5 und bei einem trennendem Kreis der Länge 5 ist eines der Gebiete nur eine Ecke. Gesucht war in Birkhoffs Programm dann eine unvermeidbare Menge reduzierbarer Konfigurationen. Eine Reihe von Arbeiten hatten reduzierbare Konfigurationen gefunden, aber man war weit entfernt von einer unvermeidbaren Menge.) Heesch war bald klar geworden, dass eine unvermeidliche Menge möglicherweise tausende, jedenfalls zu viele, Konfigurationen enthalten musste, um ohne Rechenhilfe bewältigt werden zu können. Demzufolge wurde die Geschichte des Vier-Farben-Problems eine Geschichte der Entwicklung von Hochleistungsrechnern. Nachdem er eine Lehrtätigkeit an der Technischen Hochschule Hannover aufgenommen hatte, leistete Heesch später auch grundlegende Beiträge zu einer computergestützten Lösung des Vier-Farben-Problems. Gelöst wurde das Problem aber nicht von ihm, sondern von Appel und Haken. Haken, der die Theorie der Normalflächen in der dreidimensionalen Topologie eingeführt und unter anderem einen theoretischen Algorithmus zur Klassifikation von Haken-Mannigfaltigkeiten entwickelt hatte, trug zur Lösung des Vier-Farben-Problems die konzeptionellen Ideen bei, während Appel den Großteil der Programmierung durchführte. In ihrem ersten Beweis fanden sie 1825 unvermeidbare Strukturen, in einer späteren Version kamen sie mit 1478 aus. Der Beweis der Unvermeidbarkeit dieser Strukturen kam durch massiven Computereinsatz zustande und konnte nur per Computer verifiziert werden. Sie benötigten 1200 Stunden Rechenzeit auf einer IBM 360 mit 64 kB Arbeitsspeicher - solche Ressourcen hatte Heesch in Hannover nicht zur Verfügung gehabt. Die Universität Illinois brachte zur Feier des Beweises einen Poststempel "Vier Farben genügen!" heraus. 1996 fanden Robertson, Sanders, Seymour und Thomas einen Beweis mit ‘nur’ 633 unvermeidbaren Strukturen, der aber auch nur von einem Computer geprüft werden kann. Trotz seiner Bekanntheit nimmt das Vier-Farben-Problem eine einsame Stelle in der Mathematik ein, weil der Beweis unangemessen lang und ohne Beziehungen zu anderen Teilen der Mathematik ist. Bild: https://commons.wikimedia.org/wiki/File:Wolfgang_Haken_2008.jpg

1 / 2

Kommentare (5)

  1. #1 Joachim
    29. April 2021

    Wirklich vielen Dank für diese Serie.

    Allerdings fällt es mir wirklich nicht leicht, den Ausführungen zu folgen. Entweder ist man Mathematiker. Dann dürfte man den Artikel eigentlich nicht benötigen oder man ist es nicht, dann braucht man doch – untertrieben – etwas länger. So frage ich mich, für wen ist das eigentlich? Das ich das gut finde kann der Autor ja nicht ahnen. Der Gedanke “für mich” ist vermessen. Oder ist das wie Jazz, die Freude am Spielen? So oder so, ich mag Jazz.

    Vielleicht wäre es irgendwann sinnvoll, etwas zu Computer gestützten Beweisen zu sagen. Auch wenn es hier beim Vier-Farben-Problem keinen Zweifel gibt, etwa np-Vollständigkeit, das Halteproblem usw spielen hier keine Rolle. Es kann aber immer “ein Bit kippen”. Die Wahrscheinlichkeit, dass immer der selbe Fehler immer wieder auftritt ist ungeheuer klein, doch nicht Null. So ist das einfach kein mathematischer Beweis.

    Eins noch wo ich schmunzeln musste: Das Geschlecht einer Fläche letztlch als die Anzahl Löcher zu definieren ist … Wer (Alfred Clebsch) denkt sich denn sowas aus?

  2. #2 Lausbub
    30. April 2021

    Die Antwort lautet 42, meine Herren.

  3. #3 Joachim
    30. April 2021

    @Lausbub: Nach meiner Analyse ist das falsch. 42 war die Fehlermeldung des Rechners beim Speicherüberlauf des Programms zur Suche nach der Antwort auf alle Fragen. Der Speicher war so knapp, dass er sogar die Frage löschen musste. Und so…

  4. #4 Jere
    30. April 2021

    @Joachim: Ich kann die Frage nach dem Zielpublikum nicht beantworten, aber ich glaube, der Gedanke, als Mathematikerin “dürfte man den Artikel eigentlich nicht benötigen” ist ein bisschen zu viel der Ehre: Die wenigsten kennen sich wirklich in allen Gebieten perfekt aus.

    Ich selbst finde tatsächlich spannend, wie ich bei manchen Artikeln, die näher bei meinen Schwerpunkten liegen, querlesen kann, ohne dass irgendwas unklar bleibt, während ich vor anderen vermutlich mit dem selben Unverständnis und Faszination sitze wie “der Laie”

  5. #5 Joachim
    30. April 2021

    @Jere #4: diese Antwort finde ich plausibel.

    Allerdings, und das spricht aus meiner Sicht sehr für diesen Blog, werden sehr viele sehr fundamentale oder für Mathematiker wichtige Themen und deren Geschichte angesprochen. In sehr vielen Fällen kann ich mir nicht vorstellen, dass ein Mathematiker da nun gar nicht mitkommt.

    Dennoch, beruhigend, dass nicht nur ich da so manchmal (nee meistens!) das Hirn einschalten und nachdenken/nachschlagen muss. Das ist es sogar, was ich hier so schätze.

    “Another fine tune, you’ve got me into” (Gilgamesh, 1978) um es mal musikalisch auszudrücken.