Ramsey-Zahlen

Einführung

Ramsey-Zahlen

Für zwei positive ganze Zahlen $n,m$ sei die Ramsey-Zahl $R(n,m)$ die kleinste positive ganze Zahl $r$ mit der folgenden Eigenschaft: Auf einer Party mit $r$ Gästen gibt es auf jeden Fall $n$ (gegenseitig) Bekannte oder $m$ (gegenseitig) Fremde. Oder etwas formaler: Für alle Mengen $X$ mit $\#X = r$ (hier ist $\# X$ die Kardinalität von $X$) und jede Menge $B \subseteq P_2(X)$ von zweielementigen Teilmengen von $X$ gibt es eine Teilmenge $T \subseteq X$ mit 1) $\#T = n$ und $P_2(T) \subseteq B$, oder 2) $\#T = m$ und $P_2(T) \cap B = \emptyset$. Offenbar gilt diese Eigenschaft dann auch für alle $r' \geq r$. Die Existenz von $R(n,m)$ zeigen wir später. Wir können uns $(X,B)$ auch als Graphen mit $r$ Knoten vorstellen. Dann ist $T$ im Fall 1) eine Menge von $n$ Knoten, die jeweils benachbart sind, und im Fall 2) eine Menge von $m$ Knoten, die jeweils nicht benachbart sind. Anstelle des Graphen $(X,B)$ können wir uns auch den vollständigen Graphen $K_r := (X,P_2(X))$ vorstellen (in dem also je zwei Knoten benachbart sind), dessen Kanten in zwei Farben eingefärbt sind: die Kanten in $B$ sind blau und die restlichen Kanten sind rot. Hier ein Beispiel für $r = 5$: In dieser Sprache bedeutet die Definition der Ramsey-Zahl: Es gilt $R(n,m) \leq r$ genau dann, wenn jeder blau und rot gefärbte vollständige Graph $K_r$ auf $r$ Knoten einen blauen $K_n$ oder einen roten $K_m$ enthält. Das Beispiel von $K_5$ oben hat keinen blauen $K_3$ und keinen roten $K_3$, es gilt daher $R(3,3) \geq 6$. Die allgemeine Methode für den Nachweis von $R(n,m) = r$ besteht demnach aus zwei Schritten: Erstens zeigt man $R(n,m) \geq r$, also $R(n,m) \not\leq r-1$, indem man eine Färbung von $K_{r-1}$ angibt, die keinen blauen $K_n$ und keinen roten $K_m$ enthält. Zweitens (und das ist in der Regel viel schwieriger) zeigt man $R(n,m) \leq r$, indem man zeigt, dass jeder blau und rot gefärbte $K_r$ einen blauen $K_n$ oder einen roten $K_m$ enthält. Bevor wir die Existenz von $R(n,m)$ zeigen, hier ein paar Beispiele: Es gilt aus trivialen Gründen $(1) \qquad R(n,1) = 1.$ Außerdem gilt $(2) \qquad R(n,2) = n.$ Beweis. Es gilt $R(n,2) \geq n$, denn wenn wir $K_{n-1}$ komplett blau einfärben, gibt es hier keinen blauen $K_n$ und keinen roten $K_2$. Es gilt $R(n,2) \leq n$, denn in einem gefärbten $K_n$ sind entweder alle Kanten blau, womit wir einen blauen $K_n$ haben, oder mindestens eine Kante ist rot, was ein roter $K_2$ ist. $\checkmark$ Indem man die Färbungen umdreht, sieht man (sofern diese Zahlen existieren) $(3) \qquad R(m,n) = R(n,m)$.

Ramseys Theorem

Kommen wir nun zur Existenz im Allgemeinen: Ramseys Theorem. Für je zwei positive ganze Zahlen $n,m$ existiert $R(n,m)$. Es gilt außerdem für $n,m \geq 2$ die Ungleichung $(4) \qquad R(n,m) \leq R(n-1,m) + R(n,m-1).$ Beweis. Für $n=1$ oder $m=1$ stimmt die Behauptung. Nun seien $n,m \geq 2$. Wir dürfen per Induktion annehmen, dass $R(n-1,m)$ und $R(n,m-1)$ bereits existieren. Wir zeigen nun, dass $r := R(n-1,m) + R(n,m-1)$ die Eigenschaft von $R(n,m)$ besitzt (ohne die Minimalität allerdings). Wir verwenden dazu die erste graphentheoretische Interpretation. Sei also $(X,B)$ ein Graph mit $\#X = r$. Sei $x \in X$ irgendein Knoten. Sei $Y$ die Menge der zu $x$ benachbarten Knoten und $Z$ die Menge der restlichen Knoten (ohne $x$). Es gilt $R(n-1,m) + R(n,m-1) = r = \#Y + \#Z + 1$, also $R(n-1,m) \geq \#Y$ oder $R(n,m-1) \geq \# Z$. Der zweite Fall ist analog zum ersten zu behandeln, also dürfen wir $R(n-1,m) \geq \# Y$ annehmen. Wenden wir die Definition der Ramsey-Zahl auf den Graphen $(Y, B \cap P_2(Y))$ an, so gibt es also eine Teilmenge $T \subseteq Y$, sodass 1) $\#T = n-1$ und je zwei Knoten aus $T$ benachbart sind, oder 2) $\#T = m$ und je zwei Knoten aus $T$ nicht benachbart sind. In Fall 2) sind wir also fertig. In Fall 1) sei $T' = T \cup \{x\}$. Dann gilt $\#T' = n$ und je zwei Knoten in $T'$ sind benachbart: das folgt aus $T \subseteq Y$ und der Definition von $Y$. Damit ist gezeigt, dass $R(n,m)$ existiert und höchstens gleich $R(n-1,m) + R(n,m-1)$ ist. $\checkmark$ Wir ziehen daraus direkt zwei Folgerungen: $(5) \qquad R(n,n) \leq 2 \cdot R(n-1,n)$ $(6) \qquad\displaystyle R(n,m) \leq \binom{n+m-2}{n-1}$ Letzteres folgt induktiv aus der Ungleichung in Ramseys Theorem in Kombination mit der Pascal'schen Identität der Binomialkoeffizienten. In einem Spezialfall lässt sich die Ungleichung noch verschärfen: Schärfere Ungleichung. Sind $n,m \geq 2$ und $ R(n-1,m)$ und $R(n,m-1)$ beide gerade, so gilt die Ungleichung $(7) \qquad R(n,m) \leq R(n-1,m) + R(n,m-1) - 1.$ Beweis. Sei $(X,B)$ ein Graph mit $\#X = R(n-1,m) + R(n,m-1) - 1$. Für $x \in X$ sei $\deg(x) \in \IN$ der Grad von $x$, also die Zahl der zu $x$ benachbarten Knoten im Graphen. Doppeltes Abzählen liefert die allgemeine Gradsummenformel $\displaystyle \sum_{x \in X} \deg(x) = 2 \cdot |B|.$ Weil $\#X$ ungerade ist, muss es daher ein $x \in X$ geben, sodass $\deg(x)$ gerade ist (ansonsten wäre die Summe der Grade nämlich ungerade.) Sei wieder $Y$ die Menge der zu $x$ benachbarten Knoten und $Z$ die Menge der restlichen Knoten (ohne $x$). Es gilt $\#Y \geq R(n-1,m)-1$ oder $\#Z \geq R(n,m-1)$, denn ansonsten folgte der Widerspruch $\#X = \#Y + \#Z + 1 \leq R(n-1,m)-2 + R(n,m-1) - 1 + 1 = R(n-1,m) + R(n,m-1) - 2.$ Weil $\#Y = \deg(x)$ gerade, aber $R(n-1,m)-1$ ungerade ist, gilt sogar $\#Y \geq R(n-1,m)$ oder $\#Z \geq R(n,m-1)$. Jetzt geht der Beweis genauso wie in Ramseys Theorem zu Ende. $\checkmark$

Beispiele

$(8) \qquad R(3,3) = 6$ Beweis. Wir haben bereits oben $R(3,3) \geq 6$ gesehen. Die Ungleichung (5) und die Gleichung (2) liefern außerdem $R(3,3) \leq 2 \cdot R(2,3) = 2 \cdot 3 = 6$. $\checkmark$ $(9) \qquad R(3,4) = 9$ Beweis. Der wie folgt eingefärbte $K_8$ enthält keinen blauen $K_3$ und keinen roten $K_4$: Diese Färbung lässt sich auch algebraisch definieren: Als Knoten wählen wir die Elemente der Restklassengruppe $\IZ/8\IZ$. Eine Kante $\{x,y\}$ sei genau dann rot, wenn $x-y \in \{\pm 1,\pm 2\}$. Andernfalls, also wenn $x-y \in \{\pm 3,4\}$, sei sie blau. Hiermit lässt sich übrigens auch algebraisch beweisen, dass es keinen blauen $K_3$ und keinen roten $K_4$ gibt. Es gilt daher $R(3,4) \geq 9$. Für die andere Richtung verwenden wir die schärfere Ungleichung (7) und die bereits berechneten Werte: Es sind $R(2,4) = 4$ (2) und $R(3,3) = 6$ (8) beide gerade, sodass also $R(3,4) \leq 4 + 6 - 1 = 9$. $\checkmark$ $(10) \qquad R(4,4) = 18$ Beweis. Die Ungleichung (5) und die Berechnung (9) liefern $R(4,4) \leq 2 \cdot R(3,4) = 18$. Um die Ungleichung $R(4,4) \geq 18$ zu zeigen, müssen wir einen zweifach gefärbten $K_{17}$ angeben, der keinen blauen und keinen roten $K_4$ besitzt. Dazu eine allgemeine Konstruktion: Für eine Primzahlpotenz $q$ mit $q \equiv 1 \bmod 4$ definieren wir den Paley-Graphen der Ordnung $q$: Die Knoten seien die Elemente des endlichen Körpers $\IF_q$ mit $q$ Elementen. Es gebe eine Kante $\{a,b\}$, wenn $a-b \in \IF_q^{\times}$ ein Quadrat ist, also $a-b = c^2$ für ein $c \in \IF_q^{\times}$. (Dann ist auch $b-a = (-1) (a-b)$ ein Quadrat, weil $-1$ wegen unserer Annahme an $q$ ein Quadrat ist.) Wir können daraus eine Färbung des $K_q$ machen: die Kante $\{a,b\}$ sei rot, wenn $a-b \in \IF_q^{\times}$ ein Quadrat ist, andernfalls blau. Wir behaupten nun, dass der so gefärbte $K_{17}$ keinen blauen $K_4$ und keinen roten $K_4$ enthält. Die Menge der Quadrate in $\IF_{17}^{\times} = (\IZ/17\IZ)^{\times}$ ist $\{\pm 1, \pm 2, \pm 4, \pm 8\}$; wobei $\pm 8 = \mp 9$. Die Menge der restlichen Elemente ist $\{\pm 3,\pm 5,\pm 6, \pm 7\}$. Der Graph sieht demnach so aus: Der Code ist eine gute Werbung für TikZ. Das Bild hilft allerdings nicht sonderlich dabei, um einen Beweis zu finden. Den müssen wir algebraisch führen. Angenommen, $\{a,b,c,d\}$ ist ein roter $K_4$ im obigen $K_{17}$, das heißt wir haben $4$ Knoten, die im Paley-Graphen jeweils benachbart sind. Weil $x \mapsto x-a$ ein Automorphismus des Paley-Graphen mit $a \mapsto 0$ ist, dürfen wir $a=0$ annehmen. Insbesondere ist $b \neq 0$ und $b$ ist ein Quadrat. Dann ist $x \mapsto b^{-1} \cdot x$ ein Automorphismus des Paley-Graphen mit $0 \mapsto 0$ und $b \mapsto 1$. Wir dürfen daher $b = 1$ annehmen. Nun sind $c$ und $d$ Quadrate derart, dass auch $c-1$ und $d-1$ Quadrate sind. Schaut man sich die Menge der (Nicht-)Quadrate an, so sieht man $c,d \in \{-1,+2,-8\}$. Andererseits muss auch $c-d$ ein Quadrat sein. Die (bis auf Vorzeichen) $3$ Möglichkeiten für diese Differenz sind aber $(-1)-(+2) = -3$, $(-1)-(-8) = +7$ und $(+2) - (-8) = -7$ (wir rechnen modulo $17$), also keine Quadrate. Das ist ein Widerspruch. Die Nichtexistenz eines blauen $K_4$ folgt jetzt bereits, weil nämlich der Paley-Graph der Ordnung $q$ immer zu seinem Komplement (wobei sich also unsere Färbung umdreht) isomorph ist mittels der Abbildung $a \mapsto c \cdot a$, wobei $c$ irgendein Nicht-Quadrat in $\IF_q$ ist. $\checkmark$ $(11) \qquad R(3,5) = 14$ Beweis. Aus der Ungleichung (4) und den berechneten Werten (2),(9) folgt $R(3,5) \leq R(2,5) + R(3,4) = 5 + 9 = 14$. Um $R(3,4)=R(4,3) \geq 14$ zu zeigen, müssen wir eine Färbung von $K_{13}$ finden, die keinen blauen $K_5$ und keinen roten $K_3$ besitzt. Der Paley-Graph für $q=13$ hilft uns nicht direkt weiter, aber wir können ihn abwandeln: Für $a,b \in \IF_{13}$ sei $\{a,b\}$ genau dann rot, wenn $a-b \in \IF_{13}^{\times}$ ein Kubus ist, also $a-b = c^3$ für ein $c \in \IF_{13}^{\times}$. Die Menge der Kuben ist hier konkret $\{\pm 1,\pm 5\}$, das Komplement ist $\{\pm 2,\pm 3,\pm 4,\pm 6\}$. Wir erhalten damit den folgenden Graphen: Am Bild erkennt man, dass es keinen roten $K_3$ gibt. Die blauen $K_4$ haben (bis auf Rotation) folgende Gestalt: Sie lassen sich zu keinem blauen $K_5$ fortsetzen. $\checkmark$

Weitere Beispiele

Abseits von den trivialen Beispielen $R(1,n)=1$ und $R(2,n)=n$ ist nur eine Handvoll weiterer Beispiele von konkreten Ramsey-Zahlen bekannt; siehe dazu die Tabelle bei Wikipedia. Den aktuellen Stand (auch zu verallgemeinerten Ramsey-Zahlen) erfährt man über die Arbeit Small Ramsey Numbers von Radziszowski. Oftmals sind auch nur Abschätzungen bekannt. Zum Beispiel ist $43 \leq R(5,5) \leq 48$, und es wird vermutet, dass sogar $R(5,5) = 43$ gilt, was aber außerordentlich schwer zu prüfen ist. Paul Erdős, der unter anderem zur Ramsey-Theorie geforscht hat, soll dazu folgendes gesagt haben: Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack. Das Zitat ist nun allerdings schon von 1990, die Computerleistung ist in der Zeit enorm gewachsen. Vielleicht wird es ja 2020 etwas.