Mathematik: „Party“-Problem geknackt

Nach fast 100 Jahren endlich gelöst? Mathematiker könnten die Lösung für ein seit Jahrzehnten offenes mathematisches Problem gefunden haben – einen der sogenannten Ramsey-Sätze. Mit ihm kann man beispielsweise vorhersagen, wie viele Leute auf einer Party sein müssen, damit sich eine Gruppe schon vorher kennt, eine andere nicht. Mathematisch ausgedrückt geht es jedoch darum, innerhalb eines Netzwerks aus Linien und Punkten bestimmte Gesetzmäßigkeiten vorherzusagen. Für das Problem r(4,t) haben Forscher jetzt eine Lösungsmethode gefunden, die auch bei weiteren Varianten dieses Problems helfen könnte.

Mathematische Graphen aus Linien und Punkte sind keineswegs nur eine abstrakte Spielart der Kombinatorik – sie haben ganz praktischen Nutzen. Denn anhand solcher Knotennetze lassen sich beispielsweise Routen, logistische Computercodes oder Befüllungen von Behältern berechnen. Auch das berühmte Problem eines Handlungsreisenden hat mit kombinatorischen Graphen zu tun.

Cliquenbildung auf einer Party

Eine spezielle Spielart dieses mathematischen Ansätze ist die Ramsey-Theorie. Diese vom britischen Mathematiker Frank Ramsey aufgestellten Sätze postulieren, dass es innerhalb eines Graphen immer eine bestimmte Form der Ordnung oder „Cliquenbildung“ gibt – beispielsweise in Form von Punkten ohne verbindende Linien zwischen sich (t) oder Punkten, die alle über Linien direkt miteinander verknüpft sind (s). Die Frage ist, welche Größe ein Netzwerk haben muss, damit diese Cliquen auftreten können.

Was kompliziert klingt, lässt sich an einer Party veranschaulichen. Der Ramsey-Satz r(3,3) fragt, wie viele Leute man zur Party einladen muss, damit verschiedene Cliquen mit mindestens drei Mitgliedern entstehen: eine, in der jeder jeden schon vorher kannte oder eine, in der sich die Gäste alle untereinander fremd sind. Für kleine Zahlen lässt sich die Lösung dieses Problems durch Einfärben der Kanten im Graphen finden. Die schon in den 1930er Jahren ermittelte Lösung für r(3,3) ist sechs.

„Es spielt keine Rolle, welche Situation oder welche sechs Leute man auswählt“, erklärt Jacques Verstraete von der University of California in San Diego. Mathematisch betrachtet sei es garantiert, dass mindestens drei Leute in einer oder der anderen Gruppe landen.

Was ist die Lösung für r(4,t)?

Doch wie sieht es für größere Zahlen aus? Bisher haben Mathematiker nur die Ramseyzahlen für dieses Problem bis zu r(4,5) gefunden, darüber hinaus sind nur grobe Abschätzungen möglich. Eines dieser ungelösten Ramsey-Probleme ist r(4,t), an dem schon der berühmte ungarische Mathematiker Paul Erdös in den 1930erJahren scheiterte. Es stellt die Frage, wie hoch die Zahl r sein muss, damit man mindestens vier untereinander bekannte Menschen erhält oder eine beliebige unbestimmte Zahl von sich nicht kennenden Personen.

„Schon viele Menschen haben über r(4,t) gegrübelt – es ist seit mehr als 90 Jahren ein offenes Problem, erklärt Verstraete. „Doch solange man keine neue Idee dazu hat, kommt man einfach nicht weiter.“ Genau diese hatte Verstraete jedoch vor einigen Jahren: Er entdeckte, dass man sogenannte pseudozufällige Graphen dazu nutzen kann, um die gesuchte Ramseyzahl näher einzugrenzen. 2019 konnte er so r(3,t) lösen.

Problem geknackt?!

Der nächste Schritt ist nun Verstraete gemeinsam mit seinem Kollegen Sam Mattheus von der Freien Universität Brüssel gelungen. Durch Kombination von pseudozufälligen Graphen und finiter Geometrie stellten sie fest, dass die Lösung von r(4,t) fast kubisch mit t wächst. Anders ausgedrückt: Man benötigt näherungsweise t³ Menschen, damit auf der Party in jedem Fall vier sich gegenseitig kennende Personen oder t sich nicht kennende Personen sind. Damit ist die Untergrenze von r(4,t) erstmals genauer eingegrenzt.

„Wir haben buchstäblich Jahre gebraucht, um dieses Problem zu knacken“, berichtet Verstraete. „Es gab viele Momente, in denen wir feststeckten und uns fragten, ob wir das überhaupt lösen können. Aber man sollte nie aufgeben, egal wie lange es dauert.“ Erdös bot einst 250 US-Dollar Prämie für denjenigen, der r(4,t) als erstes knackt. Diese Prämie könnten die beiden Forscher nun erhalten. Dies wird zurzeit geprüft. (Annals of Mathematics, 2024; doi: 10.4007/annals.2024.199.2.8)

Quelle: University of California – San Diego

Korrekturhinweis: In einer früheren Fassung des Artikels wurde r(s,t)  falsch erklärt (beide Cliquen mit und verknüpft statt oder). Das ist nun geändert.