Völliges Chaos existiert nicht. Mit dieser Erkenntnis erstaunte der Mathematiker Frank Ramsey in den 1920er Jahren die Fachwelt. Er studierte damals Mengen, deren Elemente bestimmte Beziehungen zueinander haben – und fand heraus, dass sich ab einer bestimmten Mengengröße zwangsläufig eine gewisse Ordnung einschleicht. Wie groß die Mengen dafür genau sein müssen, ist extrem schwer herauszufinden. Doch nun haben die Mathematiker Jacques Verstraete und Sam Mattheus von der University of California in San Diego 90 Jahre nach Ramseys Erkenntnis einen bedeutenden Fortschritt bei der Abschätzung dieser Größen geleistet. Ihre Ergebnisse sind im März 2024 in den prestigeträchtigen »Annalen der Mathematik« erschienen.

Die Ideen der Ramsey-Theorie lassen sich durch die Dynamik auf einer Party veranschaulichen. Wie Ramsey erkannte, gibt es bei einer Feier mit sechs Gästen zwangsläufig eine Gruppe von mindestens drei Personen, die sich untereinander völlig fremd sind – oder sich bereits alle kennen. Falls man aber eine Veranstaltung mit nur fünf Gästen ausrichtet, ist das nicht mehr gewährleistet. Diese Art der Ordnung (ein Dreiergespann aus Bekannten oder Fremden) taucht erst bei größeren Veranstaltungen auf.

Um das zu visualisieren, greifen Mathematiker auf Netzwerke (so genannte Graphen) zurück. Die Personen werden dabei als Punkte dargestellt, und jeder Punkt wird mit jedem anderen durch eine Kante verbunden. Die Kanten symbolisieren die Beziehungen der Menschen untereinander. Kennen sich zwei Personen bereits, kann man die Kante beispielsweise blau einfärben, sind sie sich hingegen fremd, wählt man eine rote Farbe. Nun kann man sich fragen, welche einfarbigen Strukturen aus s roten und t blauen Kanten zwangsläufig bei n Punkten entstehen. Im oben genannten Party-Beispiel gibt es für n = 6 immer drei Punkte, die durch entweder drei rote (s) oder drei blaue (t) Kanten miteinander verbunden sind – es gibt also immer ein einfarbiges Dreieck.

Die Mindestanzahl an n Punkten, die nötig sind, um zwangsläufig eine Struktur aus ausschließlich s roten oder t blauen Kanten zu enthalten, ist durch die Ramsey-Zahl R(s, t) gegeben. Bisher sind nur sehr wenige Ramsey-Zahlen bekannt. Das Party-Beispiel liefert R(3, 3) = 6: Sechs Punkte sind also mindestens nötig, damit ein blaues oder rotes Dreieck zwangsläufig auftaucht. Es konnte auch gezeigt werden, dass R(4, 4) = 18: Man muss mindestens 18 Gäste einladen, damit es stets eine Gruppe aus vier Bekannten oder Fremden gibt. In einem Graph macht sich das durch ein gleichfarbiges Viereck mit Diagonalen bemerkbar. Hingegen ist unklar, wie groß R(5, 5) ist. Immerhin konnten Fachleute das Ergebnis eingrenzen: Man weiß inzwischen, dass 43 ≤ R(5, 5) ≤ 49.

Jenseits jeder Vorstellungskraft

Der Grund für die Schwierigkeiten hat mit der enormen Vielfalt an Möglichkeiten zu tun, mit der man ein Netzwerk färben kann. Beim Party-Problem mit sechs Personen gibt es beispielsweise insgesamt 15 Kanten. Jede dieser Verbindungen kann entweder rot oder blau eingefärbt werden, das heißt, es gibt 2¹⁵ = 32 768 verschiedene Färbungen, die möglich sind. Man müsste also alle 32 768 unterschiedlich kolorierten Netzwerke durchgehen, um zu prüfen, ob in jedem davon ein gleichfarbiges Dreieck entsteht. Ramsey hat das Problem auf andere Weise gelöst (mehr Details dazu gibt es in einem Beitrag der Kolumne »Die fabelhafte Welt der Mathematik«). Doch bei Netzwerken mit mehr Punkten versagt auch Ramseys Ansatz. 90 Jahre lang gab es daher kaum Fortschritte auf dem Gebiet.

Nun haben Verstraete und Mattheus eine Formel für R(4, t) gefunden. Sie gibt an, wie viele Gäste man mindestens braucht, damit sich auf einer Feier entweder vier Personen gegenseitig völlig fremd sind oder eine Gruppe von t Menschen zusammentrifft, die sich alle kennen. Dafür griffen die beiden Mathematiker auf zufällig erzeugte Graphen zurück, die dabei helfen, die Ramsey-Zahl einzugrenzen. Wenn man beispielsweise ein zufällig eingefärbtes Netzwerk mit n Punkten erzeugt, das die gewünschte Struktur (etwa ein einfarbiges Dreieck oder ein Viereck mit Diagonalen) nicht enthält, dann muss die gesuchte Ramsey-Zahl größer als n sein.

»Es gab viele Momente, in denen wir nicht weiterkamen und uns fragten, ob wir es überhaupt lösen können«Jacques Verstraete, Mathematiker

Eine geeignete Auswahl solcher zufälliger Netzwerke zu erzeugen – und diese auch für eine beliebige Größe von n Punkten zu analysieren –, erwies sich als überaus schwierig. »Es hat uns wirklich Jahre gekostet, das Problem zu lösen«, sagte Verstraete. »Und es gab viele Momente, in denen wir nicht weiterkamen und uns fragten, ob wir es überhaupt lösen können. Aber man sollte niemals aufgeben, egal wie lange es dauert.« Die Mühe hat sich ausgezahlt: Wie die beiden Forscher beweisen konnten, wächst die Anzahl benötigter Punkte R(4, t) mit t³ an. Wenn man auf einer Party also garantiert entweder Grüppchen aus vier Bekannten oder aus t Fremden antreffen will, muss man etwa t³ Gäste einladen.

Die beiden Mathematiker freuen sich nicht nur über ihr Ergebnis, das nun in einem der renommiertesten Journale des Fachs erscheinen wird. Der berühmte Mathematiker Paul Erdős, der 1996 starb, hatte zudem ein Preisgeld auf die Berechnung von R(4, t) ausgesetzt: 250 US-Dollar. Die Professorin Fan Chung von der University of California in San Diego hat Verstraete bereits zugesichert, dass er seine Belohnung erhalten wird.