Ab einer gewissen Größe ordnet sich eine Menge selbst.

 
aus spektrum.de, 4. 4. 2024                                                      Auch wenn es manchmal anders wirkt, kann es aus mathematischer Sicht kein völliges Chaos geben.                                                                     zu Jochen Ebmeiers Realien

Ramsey-Theorie:

Ein großer Schritt bei der Zähmung des Chaos

Wie Frank Ramsey vor fast 100 Jahren vermutete, ist das Universum ordentlicher als gedacht. Fachleuten haben die verborgene Ordnung jetzt ein gutes Stück fassbarer gemacht.

 

von Manon Bischoff

Völliges Chaos existiert nicht. Mit dieser Erkenntnis erstaunte der Mathematiker Frank Ramsey in den 1920er Jahren die Fachwelt. Er studierte damals Mengen, de-ren Elemente bestimmte Beziehungen zueinander haben – und fand heraus, dass sich ab einer bestimmten Mengengröße zwangsläufig eine gewisse Ordnung ein-schleicht. Wie groß die Mengen dafür genau sein müssen, ist extrem schwer heraus-zufinden. 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 ver-anschaulichen. 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 Ord-nung (ein Dreiergespann aus Bekannten oder Fremden) taucht erst bei größeren Ver-anstaltungen auf.

 

• Adolphe Quételet: Der mittlere Mensch

 

Um das zu visualisieren, greifen Mathematiker auf Netzwerke (so genannte Gra-phen) 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 Struk-turen 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 ent-weder drei rote (s) oder drei blaue (t) Kanten miteinander verbunden sind – es gibt also immer ein einfarbiges Dreieck.

Freunde und Fremde / CC BY-SA 3.0 CC BY-SA (Ausschnitt) Graphen mit sechs Knoten | Eine Auswahl an Netzwerken mit sechs Knoten, die alle miteinander verbunden sind. Die Kanten können entweder blau oder rot sein.

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 wer-den, 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 Rechteck 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 Per-sonen gibt es beispielsweise insgesamt 15 Kanten. Jede dieser Verbindungen kann entweder rot oder blau eingefärbt wer-den, das heißt, es gibt 2¹⁵ = 32 768 verschie-dene Färbungen, die möglich sind. Man müsste also alle 32 768 unterschiedlich ko-lorierten Netzwerke durchgehen, um zu prüfen, ob in jedem davon ein gleichfar-biges 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 Mathe-matik«). 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 zusam-mentrifft, 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 Rechteck mit Dia-gonalen) 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 Ver-straete. »Und es gab viele Momente, in denen wir nicht weiterkamen und uns frag-ten, 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 Mathema-tiker Paul Erdős, der 1996 verstarb, hatte zudem ein Preisgeld auf die Berechnung von R(4, t) ausgesetzt: 250 US-Dollar. Die Professorin Fan Chung von der Univer-sity of California in San Diego hat Verstraete bereits zugesichert, dass er seine Be-lohnung erhalten wird.

 

Nota. - Die Formulierung in der Überschrift 'ordnet sich selbst' ist natürlich krumm und schief. Die vorgegebene Menge tut gar nichts. Es kommen vielmehr neue Ele-mente hinzu, die ab einem bestimten Punkt 'nicht anders können, als' ein in der übergroßen Masse vorfindliches Muster zu wiederholen. Und so weiter immer fort. Schließlich ist kein Muster unwiederholt geblieben. Es ergibt sich nach und nach eine Gesamtmuster. Bleibt im konkreten Fall als ein wirkliches Problem immer die Aufgabe, jenen gewissen Punkt aufzufinden, und das kann man immer nur versu-chen.

* 

Das hat eine metaphysische Dimension. Denn so und nicht anders werden soge-nannte Naturgesetze im Universum aufgefunden. Die Frage, wer sie erlassen hat, stellt sich nun nicht mehr: Es ist das Gesetz der großen Zahl. Es werden freilich auch immer wieder aber immer weniger Elemente hinzukommen, die nirgends reinpassen. Die zunehmende Ordnung der Gesamtmenge können sie aber nur verzögern und nicht aufhalten, geschweige denn rückgängig machen.
JE