DerVier-Farben-Satz - uni-frankfurt.deacoghlan/night_of... · 2013. 6. 24. · Landkartenf arbung Warum Beweise?Sechs-Farben-SatzGeschichte DerVier-Farben-Satz Amin Coja-Oghlan, Samuel

Landkartenfärbung Warum Beweise? Sechs-Farben-Satz Geschichte

Der Vier-Farben-Satz

Amin Coja-Oghlan, Samuel Hetterich, Felicia Raßmann

Goethe-Universität Frankfurt, Institut für Mathematik

21.Juni 2013

Der Vier-Farben-Satz Amin Coja-Oghlan

Wieviele Farben braucht man zum Färben einer Landkarte?

Spielregeln

Länder mit einer gemeinsamen Grenze bekommen unterschiedliche Farben.

Die Länder müssen zusammenhängend sein.

Wieviele Farben braucht man zum Färben einer Landkarte?

Spielregeln

Länder mit einer gemeinsamen Grenze bekommen unterschiedliche Farben.

Die Länder müssen zusammenhängend sein.

Bei all diesen Karten genügen vier Farben:

Funktioniert das immer?

Die Vier-Farben-Vermutung

Vermutung [Guthrie 1852]

Vier Farben genügen!

Das können wir glauben.

Aber können wir es auch beweisen?

Vielleicht haben wir eine Landkarte, die mehr Farben braucht, nur noch nichtgefunden?

Die Vier-Farben-Vermutung

Vermutung [Guthrie 1852]

Vier Farben genügen!

Das können wir glauben.

Aber können wir es auch beweisen?

Vielleicht haben wir eine Landkarte, die mehr Farben braucht, nur noch nichtgefunden?

Warum Beweise?

Vermutung [Euler 1769]

Es gibt keine ganzen Zahlen a, b, c , d > 0, so dass a4 + b4 + c4 = d4.

Gegenbeispiel [Elkies 1986]

26824404 + 153656394 + 187967604 = 206156734

Warum Beweise?

Vermutung [Euler 1769]

Es gibt keine ganzen Zahlen a, b, c , d > 0, so dass a4 + b4 + c4 = d4.

Gegenbeispiel [Elkies 1986]

26824404 + 153656394 + 187967604 = 206156734

Formalisierung des Problems

Die Landkarte wird in einen planaren Graphen verwandelt.

−→ −→

−→

Sechs-Farben-Satz

Sechs Farben genügen.

Die Eulersche Polyederformel

Für einen (zusammenhängenden) planaren Graphen mit

v = Anzahl der Knoten

e = Anzahl der Kanten

f = Anzahl der Flächen

gilt immer:

v − e + f = 2

KnotenFlächeKante

Sechs-Farben-Satz

Sechs Farben genügen.

Für einen (zusammenhängenden) planaren Graphen mit

v = Anzahl der Knoten

e = Anzahl der Kanten

f = Anzahl der Flächen

gilt immer:

v − e + f = 2

KnotenFlächeKante

v − e + f = 2

Beispiele:

v = 3 e = 3 f = 2

f1

f2

3− 3 + 2 = 2

v = 4 e = 5 f = 3

f1

f2f3

4− 5 + 3 = 2

Beweis der Eulerschen Polyederformel

Beweisidee: Induktion.

Operation 1 Lösche eine Kante und ihren Endknoten, der keine weitere Kanteberührt.

v = 4 e = 4 f = 2

4− 4 + 2 = 2

Operation 1−→

v = 3 e = 3 f = 2

3− 3 + 2 = 2

Ein Knoten und eine Kante verschwinden; v − e + f bleibt gleich.

Beweis der Eulerschen Polyederformel

Beweisidee: Induktion.

Operation 1 Lösche eine Kante und ihren Endknoten, der keine weitere Kanteberührt.

v = 4 e = 4 f = 2

4− 4 + 2 = 2

Operation 1−→

v = 3 e = 3 f = 2

3− 3 + 2 = 2

Ein Knoten und eine Kante verschwinden; v − e + f bleibt gleich.

Operation 2 Lösche eine Kante, die auf einem Kreis liegt.

v = 3 e = 3 f = 2

3− 3 + 2 = 2

Operation 2−→

v = 3 e = 2 f = 1

3− 2 + 1 = 2

Eine Kante und eine Fläche verschwinden; v − e + f bleibt gleich.

Korollar

Es gibt immer einen Knoten mit weniger als 6 Nachbarn.

Beweis durch Widerspruch.

Wenn jeder Knoten mindestens sechs Nachbarn hätte, wäre

6v ≤ 2e ⇒ v ≤ 13

e

Außerdem wissen wir

3f ≤ 2e ⇒ f ≤ 23

e

Zusammen mit der Eulerschen Polyederformel wäre dann

Korollar

6v ≤ 2e ⇒ v ≤ 13

e

3f ≤ 2e ⇒ f ≤ 23

e

Korollar

6v ≤ 2e ⇒ v ≤ 13

e

3f ≤ 2e ⇒ f ≤ 23

e

Korollar

6v ≤ 2e ⇒ v ≤ 13

e

3f ≤ 2e ⇒ f ≤ 23

e

2 = v − e + f ≤ 13

e − e + 23

e = 0

Korollar

6v ≤ 2e ⇒ v ≤ 13

e

3f ≤ 2e ⇒ f ≤ 23

e

2 = v − e + f ≤ 13

e − e + 23

e = 0

Widerspruch!

Wie färbt man jetzt?

Finde einen Knoten mit weniger als 6 Nachbarn.

Entferne ihn. . .

. . . bis nur noch 6 Knoten übrig sind.

Dann füge die Knoten in umgekehrter Reihenfolge wieder hinzu.

Entferne ihn. . .

Genügen vier Farben wirklich?

1852 - Guthrie: die Grafschaften von England Vermutung.

1878 - Cayley: Problem wird der London Math Society vorgestellt.

1879/80 - Kempe/Tait legen vermeintliche Beweise vor.

1890/91 - die zwei fehlerhaften “Beweise” widerlegt.

1890 - Heawood: Beweis des Fünf-Farben-Satzes.

1960/70er - Heesch: Idee eines Computerbeweises.

1976 - Appel, Haken: Erster Computerbeweis.

1996 - Robertson, Sanders, Seymour, Thomas:Stark vereinfachter Computerbeweis. Weitgehend anerkannt.

2005 - Gonthier, Werner:Formaler Beweis des Satzes mit einem “Beweisassistenten”.

Bis heute kein analytischer Beweis.

Lektüre: R. Wilson: Four colors suffice (2002).

LandkartenfärbungWarum Beweise?Sechs-Farben-SatzGeschichte

Documents

DerVier-Farben-Satz - uni-frankfurt.deacoghlan/night_of... · 2013. 6. 24. · Landkartenf arbung Warum Beweise?Sechs-Farben-SatzGeschichte DerVier-Farben-Satz Amin Coja-Oghlan, Samuel