Es gibt eine Rot-Blau-Kantenfärbung des K5, die kein einfarbiges Dreieck enthält: Wir färben die Kanten 1-2, 2-3, 3-4, 4-5, 1-5 rot und die fünf anderen blau. Andererseits enthält jede Rot-Blau-Färbung des K6 ein einfarbiges Dreieck.
Das obige Beispiel zeigt R(3,3) = 6.
Wir müssen noch zeigen, daß überhaupt immer solche m existieren. Geht aber, indem wir (sehr grobe) obere Schranken angeben.
Das läßt sich ein bißchen verschärfen: Wenn R(a,b+1) und R(a+1,b) beide gerade sind, dann R(a+1,b+1) <= R(a,b+1) + R(a+1,b) - 1. Beispiel: R(3,4) <= R(2,4) + R(3,3) - 1 = 4 + 6 - 1 = 9.
Diese Schranke reicht zum Beweis des Satzes, daß die Ramsey-Zahlen existieren, aber sie ist nur für ein paar kleine Werte wirklich scharf.
Beispiel: 14 = R(3,5) = R(2,5) + R(3,4) = 5 + 9, aber 18 = R(3,6) < R(2,6) + R(3,5) = 6 + 14.
Es bestehen gewisse Chancen, untere Schranken für kleine Ramsey-Zahlen experimentell zu finden, indem man mit Rechnern Färbungen sucht. Aber Vorsicht: blind alle durchzuprobieren verbietet sich. Das sind ganz schön viele, auch das Suchen nach den einfarbigen Cliquen dauert seine Zeit.
Man kann sich aber Tricks ausdenken, die das beschleunigen. Die bisher gefundenen Färbungen stammen daher, daß man von vornherein nur Färbungen mit bestimmten Symmetrien untersucht.
Den Schwierigkeitsgrad schätze ich so: eine bessere untere Schranke = Jahresarbeit oder ähnlich, eine bessere obere = Diplom.