Transcript
Westfälische Willhelms-Universität Münster Fachbereich 10 Mathematik und Informatik Seminar „Graphentheorie“ Sommersemester 2015 Dozent: Dr. Thomas Timmermann
Die Ramsey-Zahlen 01.06.15
Kirsten Voß
[email protected] Zwei-Fach- Bachelor Mathematik und Anglistik Fachsemester 6
0
Inhaltsverzeichnis
1) Einleitung
1
2) Ramsey Zahlen
4
3) Anwendung: Konvexe Polygone
8
4) Quellen- und Abbildungsverzeichnis
10
1
1) Einleitung
Frank Plumpton Ramsey, geboren 1903 in Cambridge und gestorben 1930 in London war ein englischer Mathematiker, nach dem die Ramsey Theorie und die dazugehörigen Ramsey Zahlen benannt wurden. Er schrieb 1925 eine Ausarbeitung mit dem Thema Foundations of Mathematics, welcher einige weitere Werke folgten. In dieser Ausarbeitung mit dem Thema „Ramsey-Zahlen“ beziehe ich mich auf die Werke von Béla Bollobás,John M. Harris, Jeffry L. Hirst, und Michael J. Mossinghoff, Reinhard Diestel und Manfred Dobrowolksi und habe wichtige Sätze und Beweise zusammengefasst. Frank Plumpton Ramsey beschäftigte sich im Wesentlichen mit der Erweiterung des Schubfachprinzips1. In der Literatur wird das Thema der Ramsey-Zahlen oft mithilfe eines Beispiels eingeleitet. Es geht hier um das sogenannte Partyproblem.
1.1)
Das Partyproblem
Es soll eine Antwort auf folgende Frage gefunden werden: Auf einer Party kennen sich zwei Besucher oder sie kennen sich nicht. Wie viele Menschen müssen mindestens auf einer Party sein, sodass sich mindestens 3 Besucher kennen oder sich mindestens 3 Besucher nicht kennen? Um sich einer Antwort zu nähern kann man nun annehmen, dass drei Besucher auf der Party sind. Dazu identifiziert man die drei Besucher mit den drei Knoten des K3. Analog geht man für vier Besucher vor. Um nun zu zeigen, dass drei bzw. vier Besucher nicht ausreichen, färbt man die Kanten des K3 bzw. K4 in den Farben blau und rot. Rot soll dabei für eine Bekanntschaft der beiden verbundenen Personen und Blau für eine Nicht- Bekanntschaft der beiden verbundenen Personen stehen. Ein einfarbiges Dreieck in einem Graphen würde nun also für Bekanntschaft bzw. Nicht- Bekanntschaft stehen.
1
Geht auf das Prinzip zurück, bei dem n>m Elemente auf m Schubfächre verteilt werden. In einem Schubfach sind dann mindestens zwei Elemente.
2
Wir versuchen also ein solches einfarbiges Dreieck zu vermeiden um sicherzugehen, dass weder eine Bekanntschaft, noch eine Nicht-Bekanntschaft zwischen drei Personen möglich ist. Im Graphen K3 (ein Dreieck) ist es möglich, die Kanten so zu färben, dass kein einfarbiges Dreieck entsteht. Ebenso im Graphen K4. Auch für den Graphen K5, der also 5 Besucher auf der Party repräsentiert, ist dies möglich, wie Abbildung 1 zeigt.
1 Abbildung
Für sechs Personen auf der Party kann man analog vorgehen. Wir versuchen ein einfarbiges Dreieck zu vermeiden und färben die Kanten des dazugehörigen Graphen K6. Dazu färben wir drei Kanten, weil wir wissen, dass andernfalls ein blaues Dreieck entstehen würde. (Schubfachprinzip). Allerdings entsteht dennoch ein einfarbiges Dreieck, wie Abbildung 2 zeigt.
2 Abbildung
Wir haben also gezeigt, dass mindestens sechs Personen auf der Party sein müssen, damit mindestens drei Personen sich kennen bzw. nicht kennen.
3
Hinsichtlich der Theorie von Ramsey würde man die Fragestellung wie folgt formulieren: Bestimme eine Zahl n, sodass der vollständige Graph Kn bei jeder Blau-Rot-Färbung einen Graphen K3, der nur aus blauen Kanten besteht, oder einen K3, der nur aus roten Kanten besteht, enthält.
2) Die Ramsey-Zahlen
2.1 Definition: Seien s und t positive ganze Zahlen. R(s,t) ist dann die kleinste ganze Zahl n sodass jede Färbung der Kanten mit zwei Farben von Kn entweder einen roten Graphen Ks oder einen blauen Graphen Kt als Teilgraphen enthält Allgemein kann man für Ramsey- Zahlen bermerken, dass gilt R(s,t)= R(t,s). Falls in diesem Fall s=t gilt, wird die Ramsey-Zahl R(s,s)= R(s) diagonal genannt. Definiert man in diesem Fall die Ramsey-Zahl, so folgt folgende Bemerkung.
2.2 Bemerkung: Die diagonale Ramsey Zahl R(s) ist die kleinste ganze Zahle n, sodass jeder ̅ s als induzierten Graph der Ordnung mindestens n entweder Ks oder 𝐾 Teilgraphen besitzt.
Am Beispiel R(1,3) wird die Definition einer Ramsey- Zahl verdeutlicht und nachvollzogen. 2.3 Beispiel: Berechnung von R(1,3) Um bei einer Färbung mit zwei Farben des Kn einen roten K1 bzw. einen blauen K3 zu erhalten, benötigt man nur einen Knoten, also einen K1. Also ist die kleinstmögliche Zahl n=1.
2.3 Bemerkung: Allgemein gilt R(1,t)=1 4
Beweis:
Ein Teilgraph, der nur einen Knoten hat, ist automatisch einfarbig.
Soll nun davon ausgehend, ein einfarbiger K2 gefunden werden, so lässt sich durch eine Unterscheidung von zwei Aspekten, analog zum Partyproblem, die Ramsey Zahl berechnen.
2.4 Bemerkung: Es gilt R(2,t)=t Beweis:
Wir wollen zeigen, dass t die kleinste Zahl ist, sodass jede Färbung mit zwei Farben eines Kt entweder einen roten K2 oder einen blauen Kt enthält. Dazu zeigen wir folgende zwei Punkte: 1. Es gibt eine Färbung, sodass Kt-1 weder einen roten K2 noch blauen Kt enthält. 2. Jede Färbung der Kanten von Kt enthält entweder einen K2 oder Kt als Teilgraphen. Zu 1. Ein Graph mit t-1 Knoten enthält keinen roten K2, wenn alle Kanten blau sind; außerdem trivialerweise keinen blauen Kt. Zu 2. Wir nehmen eine beliebige Färbung an. Wenn eine Kante rot ist, erhalten wir einen roten K2. Andernfalls einen blauen Kt
Wie bereits im Partyproblem berechnet, folgt dass die kleinste Zahl, sodass ein einfarbiger K 3 entsteht, sechs beträgt. 2.5 Bemerkung: Es gilt R(3,3)=6 Beweis:
Dies haben wir durch das anfängliche Partyproblem gezeigt. Die anderen Fälle, für unterschiedliche Färbungen der Kanten, gelten analog.
5
2.6 Definition: Ein Graph wird trivial genannt, wenn er entweder vollständig oder leer ist. Um die Existenz der Ramsey-Zahlen zu beweisen, wurde von Frank Plumpton Ramsey im Jahr 1930 folgender Beweis geliefert, welcher sich auf diagonale Ramsey- Zahlen bezieht. 2.7 Theorem: Ramsey (1930) Für jedes s Є ℕ existiert ein n Є ℕ, sodass jeder Graph von mindestens ̅ s als induzierten Teilgraphen besitzt. Ordnung n, entweder Ks oder 𝐾 Beweis2:
Die Behauptung ist trivial für s≤ 1. Sei s ≥2 und n:= 2s-3 und G ein Graph von mindestens Ordnung n. Wir definieren uns eine Folge von Mengen V1,…,V2s-2. Und wählen Knoten vi Є Vi mit folgenden Eigenschaften: i)
lVil = 22s-2-i
ii)
Vi ⊆ Vi-1\ {vi-1}
iii)
Vi-1 ist benachbart zu allen Knoten in Vi oder zu keinem Knoten in Vi (i=2,…,2r-2)
Es sei V1 Є V(G) eine Menge von 22s-3 Knoten und wähle v1 Є V1 beliebig. Dann gelten im Fall i=1 die Aussagen i) und ii) trivialerweise. Wir nehmen an, dass Vi-1 und vi-1 Є Vi-1 so gewählt wurden, dass i)-iii) für i-1, wenn 1
