Ein sehr großer kleiner Sprung nach vorne in der Graphentheorie

Am 15. März sorgten spannende Seminarankündigungen für Aufruhr auf dem Gebiet der Kombinatorik, der mathematischen Lehre vom Zählen. Drei Mitarbeiter planten, am nächsten Tag koordinierte Vorträge zu halten. Julian Sahasrabudhe Mathematiker in Cambridge, England, dabei ansprechen würden Simon Griffiths würde die Nachrichten in Rio de Janeiro teilen und Marcel Campos in São Paulo. Alle drei Vorträge hatten identische Titel und kryptische Abstracts mit zwei Sätzen, die sich auf „jüngste Fortschritte bei einem alten Problem von Erdős“ bezogen. Während Paul Erdős, ein ungarischer Mathematiker, der 1996 starb, posierte Hunderte von Problemen Während seiner Karriere erahnten Kombinatoristen schnell das spezifische Thema, über das das Trio sprechen wollte. Es kursierten Gerüchte über die sogenannte Ramsey-Zahl, eine der am schwierigsten zu berechnenden Größen in der gesamten Mathematik.

Ramsey-Zahlen haben eine ganze Disziplin namens Ramsey-Theorie hervorgebracht, die in einer Vielzahl von Systemen nach unausweichlichen Mustern sucht.

Angenommen, Sie versuchen, alle ganzen Zahlen auf eine Reihe von Buckets zu verteilen, und Sie möchten vermeiden, dass Sie Zahlenfolgen mit gleichmäßigen Abständen in einem der Buckets platzieren. Die Ramsey-Theorie zeigt, dass Sie scheitern werden (es sei denn, Sie haben unendlich viele Eimer). Die Theorie kann auf fast alles angewendet werden, was Sie zählen können. Seine zentrale Lehre ist, dass „man kein völlig chaotisches System schaffen kann“, sagte Benny Sudakov, Mathematiker an der Eidgenössischen Technischen Hochschule Zürich.

Die Ramsey-Zahl quantifiziert, wie groß ein paradigmatisches Beispiel sein muss, bevor zwangsläufig bestimmte Muster entstehen. Aber trotz ihrer zentralen Bedeutung war niemand in der Lage, die Ramsey-Zahl für alle außer der zu berechnen einfachste Fälle. Das Beste, was sie tun konnten, war, Grenzen (oder Grenzen) dessen zu finden, was es sein könnte. Selbst damals hatte sich die Obergrenze, die Erdős und ein Mitarbeiter vor fast einem Jahrhundert erstmals aufgestellt hatten, kaum verändert.

Dann gaben die Forscher in den Seminaren vom 15. März und in einem später am Abend veröffentlichten Papier bekannt, dass sie die obere Grenze der Ramsey-Zahl um einen exponentiellen Betrag verbessert hatten.

„Ich war platt“, sagte er Yuval Wigderson, Mathematiker an der Universität Tel Aviv, als er von dem neuen Ergebnis hörte. „Ich habe eine halbe bis eine Stunde lang buchstäblich gezittert.“

Die Parteilinien

Die Ramsey-Theorie stellt am häufigsten Fragen entweder zu den ganzen Zahlen oder zu Graphen. Ein Graph bezieht sich in diesem Zusammenhang auf Ansammlungen von Punkten, die als Knoten bezeichnet werden und durch Linien, die als Kanten bezeichnet werden, verbunden sind und Eigenschaften wie Länge oder – wie im Fall der Ramsey-Zahlen – Farbe haben können.

Ein vollständiger Graph ist sowohl kompliziert als auch einfach – jeder Knoten ist mit jedem anderen Knoten verbunden. Die Ramsey-Zahl beschreibt, wie viele Knoten ein vollständiger Graph enthalten muss, um eine bestimmte Struktur zu erzwingen. Angenommen, den Kanten eines vollständigen Diagramms wird eine von zwei Farben zugewiesen: rot oder blau. Angenommen, Sie versuchen, die Kanten so einzufärben, dass vermieden wird, eine Gruppe von Knoten mit Kanten derselben Farbe zu verbinden. Im Jahr 1930 bewies Frank Ramsey, dass es bei einem Graphen, der groß genug ist, unmöglich wird, das zu erzeugen, was Mathematiker eine monochromatische Clique nennen – eine Gruppe von Knoten, deren gemeinsame Kanten entweder alle rot oder alle blau sind.

Wie groß muss ein Graph genau sein, bevor eine monochromatische Clique entsteht? Die Antwort hängt von der Größe der Clique ab. Ramsey zeigte, dass es eine Zahl gibt, die jetzt als Ramsey-Zahl bezeichnet wird und die Mindestanzahl von Knoten darstellt, für die eine monochromatische Clique einer bestimmten Größe existieren muss, unabhängig davon, wie die Kanten gefärbt sind.

Aber die Größe der Ramsey-Zahl ist schwer zu bestimmen. 1935, fünf Jahre nachdem Ramsey gezeigt hatte, dass es sie gibt, lieferten Erdős und George Szekeres eine neue, strengere Obergrenze dafür, wie groß die Ramsey-Zahl für eine Clique einer bestimmten Größe ist. Doch seither konnten die Mathematiker die Rechnung von Erdős und Szekeres kaum noch verbessern.

Um eine bessere Vorstellung davon zu bekommen, was dies bedeutet, betrachten Sie ein klassisches Beispiel, in dem Knoten Gäste auf einer Party darstellen. Färben Sie die Kante zwischen zwei beliebigen Gästen rot, wenn sie sich schon einmal getroffen haben, und blau, wenn sie sich noch nicht getroffen haben. Sie können jede Cliquengröße auswählen, die Sie mögen – laden Sie genügend Leute zur Party ein, und Sie können nicht vermeiden, entweder eine Gruppe von Leuten einzuladen, die sich alle kennen (eine Clique im mehrfachen Sinne des Wortes), oder eine Gruppe von Leuten einzuladen, die sich kennen sind uns noch nie begegnet.

„Das Einfachste, was man in einem Graphen haben kann, ist eine monochromatische Clique“, sagte er Maria Chudnovsky, Mathematiker an der Princeton University. „Es ist irgendwie erstaunlich, dass man in jedem riesigen Diagramm ein großes davon finden kann. Es ist völlig unklar.“

Die ersten paar Ramsey-Zahlen sind relativ einfach zu berechnen. Nehmen wir an, Sie möchten die Größe des kleinsten Graphen wissen, der unvermeidlich eine Clique der Größe zwei oder R(2) für Mathematiker halten muss. Da ein vollständiger Graph mit zwei Knoten nur zwei Knoten sind, die durch eine Kante verbunden sind, und diese Kante entweder rot oder blau sein muss, ist R(2) gleich 2. Allgemeiner ist R(k) oder die Ramsey-Zahl von k, ist die minimale Anzahl von Knoten, über die hinaus ein Graph nicht vermeiden kann, eine Clique der Größe zu enthalten k.

Es ist nicht so schwer zu zeigen, dass die Ramsey-Zahl für eine Clique der Größe 3 oder R(3) 6 ist (siehe Grafik). Aber erst 1955 wurde R(4) auf 18 festgelegt. R(5) bleibt unbekannt – es ist mindestens 43 und nicht größer als 48. Obwohl diese Zahlen klein sind, ist es out, alle möglichen Färbungen zu sichten der Frage, sagte David Conlon vom California Institute of Technology. Betrachten Sie die Anzahl der Färbungen auf einem vollständigen Graphen mit 43 Knoten. „Sie haben 903 Kanten; Jeder von ihnen kann auf zwei Arten gefärbt werden“, erklärte er. „Du bekommst also 2⁹⁰³, das ist einfach astronomisch groß.“

Mit zunehmender Größe der Clique wird die Aufgabe, die Ramsey-Nummer festzunageln, nur noch schwieriger. Erdős witzelte, dass ein totaler Krieg mit mathematisch anspruchsvollen Außerirdischen einfacher wäre, als es zu versuchen Finde R(6) heraus, die irgendwo zwischen 102 und 165 liegt. Die Unsicherheitsspanne wächst schnell: Laut Schätzungen von Stanisław Radziszowski, R(10) könnte so klein wie 798 und so groß wie 23,556 sein. Aber die Ziele der Mathematiker reichen weit über die Ramsey-Zahl von 10 hinaus. Sie wollen eine Formel, die eine gute Schätzung von R(k), sogar – oder besonders – wann k ist extrem groß.

„Ich kenne niemanden in der Kombinatorik, der nicht zumindest ein bisschen über dieses Problem nachgedacht hat“, sagte Wigderson. „Dieses Problem ist meiner Meinung nach etwas ganz Besonderes.“

Ordnung im Gericht

Frank Ramsey war eine vielseitige, brillante Figur, die im Alter von 26 Jahren starb. Nur wenige Wochen vor seinem Tod, der Verfahren der London Mathematical Society veröffentlicht das Papier in dem er Ramsey-Zahlen einführte. In dieser Arbeit ging es nicht einmal um Graphen, sondern um ein Problem in der mathematischen Logik. Ramsey hat bewiesen, dass eine Aussage, die bestimmte Bedingungen erfüllt, zumindest manchmal wahr sein muss. Eine dieser Bedingungen war, dass es ein großes „Universum“ von Szenarien gibt, in denen die Aussage getestet werden kann. Als Sprungbrett für dieses Ergebnis zeigte Ramsey, dass die Ramsey-Zahl endlich ist.

Fünf Jahre später zeigten Erdős und Szekeres, dass die Ramsey-Zahl von k ist weniger als 4^k. Und 12 Jahre danach Erdős zeigte dass es größer ist als etwa $latex sqrt{2}^k$. Dazu berechnete er die Chancen, dass ein Graph mit zufällig gefärbten Kanten eine monochromatische Clique enthält. Diese „probabilistische“ Technik wurde in der Graphentheorie massiv einflussreich. Es hat auch R(k) zwischen zwei exponentiell wachsenden Torpfosten: $latex sqrt{2}^k$ und $latex 4^k$.

Im Laufe der Jahrzehnte versuchten zahlreiche Mathematiker, die Kluft zwischen den möglichen Werten der Ramsey-Zahl zu verringern. Einigen gelang es: 1975 Joel Spencer die Untergrenze verdoppelt. Und eine Reihe von Artikeln von Conlon, Andreas Thomasson und Ashwin Sah die Obergrenze nach unten gedrückt um einen Faktor von etwa $latex 4^{log(k)^2}$ bis 2020. Aber im Vergleich zu den Grenzen der Ramsey-Zahl waren diese Anpassungen gering. Im Gegensatz dazu ist jede Reduktion auf die 4 in Erdős und Szekeres' Formel R(k) < 4^k wäre eine exponentielle Verbesserung, wächst schnell wie k wird größer.

„Es scheint nur eine nette kleine Frage zu sein“, sagte er Rob Morris, ein Mathematiker am IMPA, dem brasilianischen Institut für reine und angewandte Mathematik, in Rio de Janeiro, der das neue Ergebnis gemeinsam mit Campos, Griffiths und Sahasrabudhe verfasst hat. “Es ist ein wenig subtil zu schätzen. Aber die Leute kümmern sich wirklich darum.“ Dies ist möglicherweise eine Untertreibung. „Hätten sie es 1936 bewiesen, hätten die Leute gesagt: OK, also, was ist die große Sache?“ sagte Béla Bollobás, Doktorvater von Morris und Sahasrabudhe an der Universität von Memphis. „Seitdem hat sich gezeigt, dass es sich um ein sehr großes Problem handelt, denn im Laufe der Jahre wurden mehrere tausend Artikel zu verschiedenen Varianten des Ramsey-Problems verfasst.“ Als Liana Yepremyan, ein Mathematiker an der Emory University, sagte: „Die Ramsey-Zahlen schaffen diese Brücke zwischen Kombinatorik und Wahrscheinlichkeit und Geometrie.“

Spieltheorie

 Im August 2018 war Sahasrabudhe Postdoktorand bei Morris am IMPA. Die beiden hatten gehofft, mit Griffiths, der an der nahe gelegenen Päpstlichen Katholischen Universität lehrt, ein neues Projekt zu starten ein Artikel von Conlon ihre Aufmerksamkeit erregt. Das Papier skizzierte eine mögliche Strategie, um eine exponentielle Verbesserung der Ramsey-Zahl zu erreichen. Griffiths, Morris und Sahasrabudhe begannen mit der Idee zu spielen.

„Am Anfang war es wirklich aufregend“, erinnerte sich Sahasrabudhe. Sie brauchten nur etwa einen Monat, sagte er, um eine Skizze ihrer Argumentation zu entwerfen.

Ihr Plan war es, auf Ideen aufzubauen, die im ursprünglichen Beweis von Erdős und Szekeres verwendet wurden, dass $latex R(k) < 4^k$ ist. Um zu beweisen, dass die Ramsey-Zahl höchstens $latex 4^k$ beträgt, stellen Sie sich vor, Sie spielen ein Spiel auf einem vollständigen Graphen mit $latex 4^k$-Knoten. Das Spiel hat zwei Spieler. Zuerst färbt Ihr Gegner jede Kante entweder rot oder blau und hofft, die Kanten so zu färben, dass keine monochromatische Clique entsteht k Knoten.

Sobald Ihr Gegner mit dem Ausmalen fertig ist, ist es Ihre Aufgabe, nach einer einfarbigen Clique zu suchen. Wenn Sie einen finden, gewinnen Sie.

Um dieses Spiel zu gewinnen, können Sie einer einfachen Strategie folgen. Es hilft, (metaphorisch) darüber nachzudenken, wie Sie Ihre Knoten in zwei Eimer sortieren. Die Knoten in einem Eimer bilden eine blaue Clique, und die Knoten im anderen bilden eine rote Clique. Einige Knoten werden gelöscht, von denen nie wieder etwas zu hören ist. Zu Beginn sind beide Eimer leer und jeder Knoten ist ein Kandidat, um in einen von beiden zu gehen.

Beginnen Sie mit einem beliebigen Knoten, der Ihnen gefällt. Betrachten Sie dann die Verbindungskanten. Wenn die Hälfte oder mehr der Kanten rot sind, löschen Sie alle blauen Kanten und die Knoten, mit denen sie verbunden sind. Legen Sie dann Ihre ursprüngliche Wahl in den „roten“ Eimer. Alle roten Kanten dieses Knotens sind noch lebendig und gesund und klammern sich aus dem Eimer an den Rest des Diagramms. Wenn mehr als die Hälfte der Kanten blau sind, löschen Sie analog die roten Kanten und Knoten und legen sie in den blauen Eimer.

Wiederholen Sie dies, bis Sie keine Knoten mehr haben. (Da der Graph vollständig ist, ist jeder verbleibende Knoten an einem beliebigen Punkt mit beiden Eimern verbunden, bis er in einen von ihnen platziert wird.)

Wenn Sie fertig sind, schauen Sie in die Eimer. Da ein Knoten erst in den roten Eimer gelangt ist, nachdem seine blauen Nachbarn eliminiert wurden, sind alle Knoten im roten Eimer durch rote Kanten verbunden – sie bilden eine rote Clique. Ebenso bildet der blaue Eimer eine blaue Clique. Wenn Ihr ursprüngliches Diagramm mindestens $latex 4^k$-Knoten hat, ist es möglich zu beweisen, dass einer dieser Buckets mindestens enthalten muss k Knoten, was eine monochromatische Clique im ursprünglichen Graphen garantiert.

Dieses Argument ist clever und elegant, aber es lässt Sie zwei Cliquen aufbauen – eine blaue und eine rote – obwohl Sie eigentlich nur eine brauchen. Es wäre effizienter, immer rot zu werden, erklärte Conlon. Bei dieser Strategie würden Sie bei jedem Schritt einen Knoten auswählen, seine blauen Kanten löschen und ihn in den roten Eimer werfen. Der rote Eimer würde sich dann schnell füllen, und Sie würden eine rote Clique anhäufen k Knoten in der Hälfte der Zeit.

Aber Ihre Strategie muss für jede Rot-Blau-Färbung funktionieren, und es ist schwer zu wissen, ob Sie immer einen Knoten mit vielen roten Kanten finden können. Das Befolgen von Conlons Vorschlag läuft also Gefahr, auf einen Knoten zu stoßen, an dem fast keine roten Ränder angebracht sind. Das würde Sie dazu zwingen, einen großen Teil des Diagramms auf einmal zu löschen, und Sie müssten sich bemühen, Ihre Clique aufzubauen, bevor Ihnen die Knoten ausgehen. Um Conlons Vorschlag auszuführen, mussten Griffiths, Morris und Sahasrabudhe beweisen, dass dieses Risiko vermeidbar war.

Eine Open-Book-Prüfung

Bei der Aktualisierung ihres Gameplays folgten Griffiths, Morris und Sahasrabudhe einem etwas umständlicheren Weg. Anstatt direkt eine monochromatische Clique aufzubauen, indem sie Knoten in ihre roten und blauen Eimer werfen, konzentrierten sie sich zunächst auf den Aufbau einer Struktur, die als rotes Buch bezeichnet wird.

In der Graphentheorie besteht ein Buch aus zwei Teilen: Es gibt eine monochromatische Clique, die als „Rücken“ bezeichnet wird, und eine zweite, unterschiedliche Gruppe von Knoten, die als „Seiten“ bezeichnet werden. In einem roten Buch sind alle Kanten, die Knoten innerhalb des Buchrückens verbinden, rot, ebenso wie die Kanten, die den Buchrücken mit den Seiten verbinden. Die Kanten, die Knoten innerhalb der Seiten verbinden, können jedoch jede Kombination von Farben sein. Conlon hatte in seiner Arbeit von 2018 angemerkt, dass man, wenn man eine rote Clique in den Seiten eines Buches findet, sie mit dem Buchrücken kombinieren könnte, um eine größere rote Clique zu erhalten. Auf diese Weise können Sie eine Suche nach einer großen roten Clique in zwei einfachere Suchen zerlegen. Suchen Sie zuerst nach einem roten Buch. Suchen Sie dann auf den Seiten des Buches nach einer Clique.

Griffiths, Morris und Sahasrabudhe wollten den Spielgewinnalgorithmus so anpassen, dass er statt einer roten Clique ein rotes Buch aufbaut. Obwohl sie sich nur wenige Wochen nach Beginn ihres Projekts auf diesen Plan geeinigt hatten, würde es Jahre dauern, bis er funktionierte. Sie mussten immer noch die Gefahr abwehren, alle ihre roten Ränder zu verlieren.

„Wir steckten sehr lange fest“, sagte Campos, der 2021 in das Projekt einstieg.

Diesen Januar einigten sich die vier Mathematiker darauf, zu einer anderen Version des Problems zu wechseln. Diese Version klingt komplizierter, stellte sich aber als einfacher heraus.

Die ganze Zeit über hatte sich das Team auf die Ramsey-Zahl R(k), auch bekannt als „diagonale“ Ramsey-Zahl. Ein Graph der Größe R(k) muss enthalten k Knoten, die alle durch Kanten derselben Farbe verbunden sind, aber es spielt keine Rolle, ob diese Farbe rot oder blau ist. Andererseits ist die „außerdiagonale“ Ramsey-Zahl R(k, l) misst, wie groß ein Graph sein muss, bevor er entweder eine rote Clique mit enthält k Knoten oder eine blaue Clique mit l Knoten. Anstatt weiter an dem Diagonalproblem herumzuhacken, entschied sich die Gruppe, die Version ohne Diagonale auszuprobieren. Dies erwies sich als aufschlussreich.

„Lange Zeit fühlte es sich an, als ob jede Tür, die man aufdrückte, entweder verriegelt oder zumindest ziemlich schwer zu durchkommen wäre“, sagte Griffiths. „Und nach dieser Veränderung hattest du einfach das Gefühl, dass alle Türen offen stehen. Irgendwie schien einfach alles zu funktionieren.“ In der nicht-diagonalen Version fanden sie einen Weg, eine Reihe blauer Kanten auf einmal zu löschen, indem sie einem bestimmten Protokoll folgten, was die Dichte der roten Kanten erhöhte und zu einer verbesserten Begrenzung der nicht-diagonalen Ramsey-Zahl führte. Diese Methode, die als „Dichteinkrement“-Argument bezeichnet wird, wurde zuvor zur Lösung verwendet andere wichtige Probleme der Kombinatorik, aber es wurde nicht für das Ramsey-Zahlenproblem verwendet.

Die vier Mathematiker nutzten dann die neue Schranke der Ramsey-Zahl außerhalb der Diagonale, um den Weg für das Diagonalergebnis freizumachen. Bis Anfang Februar hatten sie endlich die Grenze der Ramsey-Zahl um einen exponentiellen Faktor gesenkt, eine Errungenschaft, nach der Mathematiker fast ein Jahrhundert lang gesucht hatten. Und sie taten es, indem sie dieselbe Argumentationslinie modernisierten, die Erdős und Szekeres 1935 vorgebracht hatten.

Epsilon, Epsilon

Nach den Gesprächen am 16. März begannen die Teilnehmer, die Gerüchte zu bestätigen. Fotos von Sahasrabudhes Vortrag kursierten durch Telefonanrufe und private Nachrichten – sogar in einem vage, aber suggestiver Beitrag im Blog des Mathematikers Gil Kalai. Campos, Griffiths, Sahasrabudhe und Morris behaupteten, gezeigt zu haben, dass $latex R(k) < 3.993^k$ ist. An diesem Abend die vier Autoren haben ihr Papier online gestellt, sodass Mathematiker den neuen Beweis selbst sehen können.

„Ich denke, viele von uns haben im Grunde nicht erwartet, eine solche Verbesserung in ihrem Leben zu sehen“, sagte er Matija Bucic, Mathematiker an der Princeton University und dem Institute for Advanced Study. "Ich denke, es ist ein absolut erstaunliches Ergebnis."

Viele Experten hoffen, dass nach dem Fallen der exponentiellen Barriere schnell weitere Fortschritte folgen werden. Die Autoren des neuen Papiers haben ihre Methode bewusst nicht an ihre Grenzen gebracht, um ihre Argumentation nicht mit unnötigen Details zu vernebeln. „Ich bin sehr daran interessiert, wie weit die Methode tatsächlich gehen kann, weil ich keine Ahnung habe“, sagte Campos.

„Es ist ein absolut genialer, absolut wunderbarer Beweis und ein echter Durchbruch. Also erwarte ich jetzt, dass die Schleusen geöffnet werden“, sagte Bollobás. „Ich bin überzeugt, dass es in drei Jahren um mögliche Verbesserungen gehen wird. Können wir 3.993 auf 3.9 verbessern? Vielleicht auf 3.4? Und was ist mit 3?“

Der neue Beweis umfasst 56 Seiten, und es wird Wochen dauern, bis jedes Detail von der Kombinatorik-Community vollständig verifiziert ist. Aber die Kollegen sind optimistisch. „Diese Gruppe von Autoren sind sehr ernste Menschen. Und es sind Leute, die sehr, sehr gut in sehr technischen Dingen sind“, sagte Wigderson.

Wenn es um seine Mitarbeiter geht, stimmt Griffiths zu. „Es ist ein Privileg, mit brillanten Leuten zusammenzuarbeiten, nicht wahr? Und ich glaube, dafür bin ich sehr dankbar“, sagte er. „Wenn sie es mir überlassen hätten, hätte ich vielleicht weitere fünf Jahre gebraucht, um die Details richtig zu machen.“