13.2 Ramsey-Zahlen
Sei \(n\ge 1\) eine natürliche Zahl. Der vollständige Graph mit \(n\) Ecken ist der Graph \(K_n\) mit Eckenmenge \(\mathbb E = \{ 1, \dots , n\} \) und Kantenmenge \(\{ \{ i, j\} ;\ i, j = 1,\dots , n,\ i\ne j\} \), d.h. je zwei verschiedene Punkte sind durch eine Kante verbunden.
Zum Beispiel ist der Graph \(K_3\) einfach ein »Dreieck«, d.h. er besteht aus drei Ecken, die jeweils durch eine Kante miteinander verbunden sind. Mit wachsendem \(n\) steigt die Anzahl der Kanten in \(K_n\) allerdings sehr schnell.
![\begin{tikzpicture} [transform shape,line width=0.2pt, scale=.6]
\pgfmathsetmacro{\numnodes}{12}
\foreach \x in {1,...,\numnodes}{%
\pgfmathparse{(\x-1)*720/\numnodes+floor(\x/(\numnodes/2+1))*360/\numnodes}
\node[fill,circle,inner sep=0.15cm] (N-\x) at (\pgfmathresult:5.4cm) [thick] {};
}
\foreach \x [count=\xi from 1] in {2,...,\numnodes}{%
\foreach \y in {\x,...,\numnodes}{%
\path (N-\xi) edge[-] (N-\y);
}
}
\end{tikzpicture}](images/img-0049.svg)
Sei \(n\ge 1\) eine fixierte natürliche Zahl. Wir wollen nun als zusätzliche Information in dem Graphen \(K_n\) jede Kante entweder blau oder rot einfärben, wie im Beispiel \(n=5\) in Abbildung 13.2 gezeigt. Die Frage, die wir dann betrachten, ist, ob der eingefärbte Graph \(K_n\) einen Teilgraphen der Form \(K_m\) hat, dessen Kanten alle blau oder alle rot sind. In dieser Sache gilt der folgende Satz.
Seien \(b, r \ge 1\) natürliche Zahlen. Dann existiert eine Zahl \(N\), so dass für alle \(n\ge N\) und jede blau/rote Kantenfärbung des Graphen \(K_n\) ein roter \(r\)-Teilgraph oder ein blauer \(b\)-Teilgraph existiert.
Die kleinste solche Zahl \(N\) nennen wir die Ramsey-Zahl zu \(b\) und \(r\) und bezeichnen sie mit \(R(b, r)\).
Man kann dies durch Induktion nach \(b+r\) beweisen, siehe zum Beispiel Ramsey’s theorem (Wikipedia).
![\begin{tikzpicture} [line width=0.1pt, scale=2]
\coordinate (A) at (0, 1);
\coordinate (B) at (0.95106, 0.30902);
\coordinate (C) at (-0.95106, 0.30902);
\coordinate (D) at (-0.58779, -0.80902);
\coordinate (E) at (0.58779, -0.80902);
\draw[ultra thick, color=blue] (E) -- (A);
\draw[ultra thick, color=red] (A) -- (C);
\draw[ultra thick, color=red] (D) -- (E);
\draw[ultra thick, color=red] (A) -- (C) -- (E);
\draw[ultra thick, color=red] (A) -- (B) -- (D);
\draw[ultra thick, color=blue] (E) -- (B);
\draw[ultra thick, color=blue] (B) -- (C) -- (D) -- (A);
\node[fill, circle, inner sep=0.08cm] at (A) {};
\node[fill, circle, inner sep=0.08cm] at (B) {};
\node[fill, circle, inner sep=0.08cm] at (C) {};
\node[fill, circle, inner sep=0.08cm] at (D) {};
\node[fill, circle, inner sep=0.08cm] at (E) {};
\end{tikzpicture}](images/img-0050.svg)
Es ist \(R(3, 3) = 6\). In der Tat zeigt Abbildung 13.2, dass \(R(3,3){\gt}5\) sein muss. Es ist daher nur noch zu zeigen, dass es in jedem rot/blau gefärbten Graphen \(K_6\) ein rotes Dreieck oder ein blaues Dreieck gibt.
Wir fixieren eine Färbung der Kanten von \(K_6\). Sei \(i\) eine fixierte Ecke. Wie jede Ecke in \(K_6\) ist sie mit \(5\) anderen Ecken verbunden, und von diesen Kanten können wir mindestens \(3\) finden, die dieselbe Farbe haben. Indem wir rot und blau vertauschen, falls erforderlich, können wir für das Argument ohne Einschränkung annehmen, dass von \(i\) drei rote Kanten ausgehen. Wenn von den Verbindungen zwischen den drei Endpunkten dieser Kanten eine rot ist, dann haben wir ein rotes Dreieck gefunden. Sind die Verbindungen alle drei blau, dann bilden sie ein blaues Dreieck.
Wir können der Aussage folgendermaßen einen Alltagsbezug geben (auch wenn der Nutzen fragwürdig ist): Stellen Sie sich vor, auf einer Party sind mindestens \(6\) Personen anwesend, von denen je zwei entweder miteinander bekannt, oder einander unbekannt sind. Dann gibt es eine Dreiergruppe von Personen, die sich alle gegenseitig kennen, oder eine Dreiergruppe von Personen, die sich gegenseitig nicht kennen.
Die Ramsey-Zahl \(R(5, 5)\) ist nicht bekannt!
Man kann zeigen, dass
es handelt sich also nicht um eine besonders große Zahl. Dennoch ist die Berechnung so komplex, dass sie bisher nicht gelungen ist. (Das Problem ist, dass zum Beispiel \(K_{43}\) insgesamt \(946\) Kanten hat und damit die Zahl der möglichen Kantenfärbungen astronomisch hoch ist.)