Satz von Ramsey
aus Wikipedia, der freien Enzyklopädie
Der Satz von Ramsey (nach Frank Plumpton Ramsey) beantwortet die Frage, ob in einem Graphen zwingend gewisse Unterstrukturen auftreten. Genauer werden gefärbte vollständige Graphen auf das Auftreten monochromatischer Teilgraphen hin betrachtet, und es stellt sich heraus, dass solche für hinreichend große Graphen tatsächlich auftreten müssen.
Erheblich schwieriger als die reine Existenzaussage gestaltet sich die genaue Quantifizierung, was hierbei als „hinreichend groß“ zu betrachten ist, d. h. die genaue Berechnung oder wenigstens Abschätzung der Ramsey-Zahlen.
Inhaltsverzeichnis |
[Bearbeiten] Aussage des Satzes
Wir betrachten einen vollständigen Graphen mit n Ecken, dessen Kanten mit zwei Farben, etwa rot und blau, gefärbt wurden. Gibt es hierin r Ecken, so dass alle Kanten zwischen diesen rot sind, so sagen wir, der Graph enthalte einen roten r-Teilgraphen, entsprechend für blaue Teilgraphen. Mit diesen Bezeichnungen behauptet der Satz von Ramsey:
Seien r,b natürliche Zahlen. Jeder hinreichend große vollständige Graph, dessen Kanten rot oder blau gefärbt wurden, enthält einen roten r-Teilgraphen oder einen blauen b-Teilgraphen. „Hinreichend groß“ bedeutet hierbei 
für eine von r und b abhängige Zahl N. Die kleinstmögliche Zahl, die für N gewählt werden kann, heißt Ramsey-Zahl und wird mit R(r,b) bezeichnet. Umgekehrt ist es also möglich, den vollständigen Graphen mit R(r,b) − 1 Ecken so zu färben, dass man weder einen roten r-Teilgraphen, noch einen blauen b-Teilgraphen erzeugt.
Der Satz gilt auch in verallgemeinerter Form für mehr als zwei Farben. Entsprechend gibt es auch zu Färbungen mit c Farben gehörige Ramsey-Zahlen 
.
[Bearbeiten] Beispiele
- Allgemein gilt R(r,b) = R(b,r), wie man durch Vertauschen der Farben erkennt.
- R(k,1) = 1: Jeder Teilgraph mit nur einer Ecke ist automatisch monochrom.
- R(k,2) = k: Entweder sind alle Kanten rot oder es gibt eine blaue Kante.
[Bearbeiten] Berechnung von R(3,3)
Das nebenstehende Bild zeigt, dass es möglich ist, den K5, also den vollständigen Graphen mit fünf Ecken, so mit zwei Farben rot und blau zu färben, dass weder ein rotes noch ein blaues Dreieck auftritt. Folglich gilt gewiß R(3,3) > 5 bzw. 
.
Betrachtet man umgekehrt einen auf beliebige Weise rot-blau gefärbten K6 und hierin eine beliebige Ecke v, so tritt bei den fünf in v endenden Kanten eine der beiden Farben, oBdA. rot, mindestens dreimal auf (Schubfachprinzip). Ist eine der Kanten zwischen den drei entsprechenden Endpunkten rot, so haben wir ein rotes K3. Andernfalls sind alle Kanten zwischen diesen drei Endpunkten blau und wir haben ein blaues K3. In jedem rot-blau-gefärbten K6 findet man also ein rotes K3 oder ein blaues K3, d. h. es gilt 
.
Insgesamt ergibt sich also der exakte Wert R(3,3) = 6.
Die hier gemachten Überlegungen zeigen bereits wesentliche Gedanken für einen Beweis des Satzes sowie eine einfache rekursive Abschätzung für Ramsey-Zahlen, die jedoch für eine exakte Bestimmung der Ramsey-Zahlen nicht ausreicht:
[Bearbeiten] Veranschaulichung
Die Ramsey-Zahl R(r,b) beantwortet die Frage, wieviele Personen man z. B. zu einer Party einladen muss, damit sich r Gäste untereinander nicht kennen oder b Gäste sich kennen. „Kennen“ ist in diesem Beispiel eine symmetrische Relation, d. h. wenn A B kennt, so kennt B auch A.
Betrachten wir beispielsweise R(3,2) = 3. Mit r = 3 und b = 2 folgt R(3,2) = 3 = N (siehe oben).
Haben wir also N = 3 Gäste, so können wir nun den vollständigen Graphen K3 zeichnen und das Färben beginnen. Man muss jede Kante entweder rot oder blau färben (rot: Gäste kennen sich nicht, blau: Gäste kennen sich) und erreicht folgende mögliche Färbungen:
- alle Kanten werden rot gefärbt
- alle Kanten werden blau gefärbt
- zwei Kanten werden blau gefärbt und eine rot
- zwei Kanten werden rot gefärbt und eine blau
Für die drei Gäste bedeutet dies:
- Es kennen sich also entweder alle drei oder niemand kennt jemand anderes
- Eine Person kennt zwei Personen die einander vorher nicht kannten
- Zwei Personen kennen sich, aber die dritte Person nicht
Diese Beschreibung dient lediglich zur Veranschaulichung. Die Analogie zu den Gästen behandelt nicht Probleme, die durch seltsame „Kennen sich (nicht)“-Beziehungen haben (alle kennen sich nicht, zwei kennen sich, aber wer ist der 3.) Ebenso wird nicht berücksichtigt, dass evtl. A B kennt aber B A nicht kennt. Außerdem werden keine transitiven Beziehungen dargestellt.
[Bearbeiten] Literatur
- F. P. Ramsey: On a problem of formal logic. In: Proc. London Math. Soc. series 2, Bd. 30 (1930), S. 264–286
