Mathematiker entdecken neue Methode zur Vorhersage der Struktur in Diagrammen | Quanta-Magazin

Es war ein aufregendes Jahr in der kombinatorischen Forschung. Anfang 2023 waren Mathematiker fassungslos, als zwei von größte Probleme vor Ort wurden in ebenso vielen Monaten gelöst. Nun sei eine dritte große Frage mit einem 14-seitigen Beweis gelöst worden, „der absolut alle richtigen Ideen enthält“, sagte er Mehtaab Sawhney vom Massachusetts Institute of Technology, der hinzufügte: „Es ist völlig schockierend.“

Bei dieser Frage geht es um sogenannte Ramsey-Zahlen – Grundgrößen, die die Grenzen möglicher Unordnung widerspiegeln. Diese Zahlen messen die Größe, die Ansammlungen von Eckpunkten und Kanten, sogenannte Graphen, erreichen können, bevor daraus zwangsläufig Muster und Strukturen entstehen.

Seit fast einem Jahrhundert beschäftigen sich Mathematiker mit Ramsey-Zahlen, die bekanntermaßen schwer zu bestimmen sind. Dabei haben sie Techniken entwickelt, die zu Fortschritten in einer Vielzahl von Disziplinen über die Graphentheorie hinaus geführt haben, darunter Zahlentheorie und Kryptographie.

Aber der neue Beweis, Anfang des Monats online gestelltmarkiert eine Abkehr von diesen Techniken. Es löst nicht nur ein Problem, das sich mehr als 40 Jahre lang dem Fortschritt widersetzt hat, sondern präsentiert auch einen neuartigen Fahrplan dafür, wie Mathematiker künftig Ramsey-Probleme angehen könnten.

Partyplanung trifft auf Graphentheorie

Um zu verstehen, was eine Ramsey-Zahl ist, stellen Sie sich vor, Sie veranstalten eine Party.

Wie viele Personen müssten Sie einladen, um sicherzustellen, dass es eine Gruppe von Menschen gibt, die sich alle kennen, oder eine Gruppe, die alle fremd sind? Sie können diese Frage in der Sprache der Graphen kodieren. Weisen Sie jeder Person einen Eckpunkt zu. Für n Leute, versteht ihr n Eckpunkte. Verbinde jedes Eckpunktpaar mit einer Kante. Färben Sie den Rand rot, wenn sich die betreffenden Personen kennen, und blau, wenn es sich um Fremde handelt.

Eine Gruppe gemeinsamer Bekannter oder Fremder wird durch eine Struktur namens Clique dargestellt: eine Reihe von Eckpunkten, die durch gleichfarbige Kanten verbunden sind. Die Ramsey-Zahl r(s, t) ist die Mindestanzahl an Personen, die Sie einladen müssen, damit es unmöglich ist, die Einbeziehung einer Gruppe zu vermeiden s Bekannte bzw t Fremde – in der Sprache der Graphentheorie eine rote Clique der Größe s oder eine blaue Clique von Größe t.

Das wissen wir zum Beispiel r(4, 5) = 25. Sie können also eine Party mit 24 Personen veranstalten, von denen sich einige untereinander kennen, ohne eine Gruppe von vier gemeinsamen Bekannten oder fünf Fremden einzubeziehen. Aber wenn man noch eine weitere Person hinzufügt, kommt man nicht umhin, mindestens eine dieser Strukturen zu schaffen.

Einer der früheren Durchbrüche in diesem Jahr in der Kombinatorik ergab eine engere Obergrenze für „symmetrische“ Ramsey-Zahlen, bei denen die roten und blauen Cliquen gleich groß sind. Mit asymmetrischen Ramsey-Zahlen – dem Gegenstand des neuen Ergebnisses – legen Mathematiker die Größe der roten Clique fest und fragen sich, was passiert, wenn die Größe der blauen Clique beliebig groß wird.

Mathematiker konnten nur eine Handvoll der kleinsten Ramsey-Zahlen genau berechnen. Das haben sie bewiesen r(4, 5) = 25 im Jahr 1995. Aber niemand kennt den Wert von r(4, 6). Ähnlich verhielt es sich Anfang der 1980er Jahre: Sie zeigten zur Verbesserung der Gesundheitsgerechtigkeit r(3, 9) = 36, aber r(3, 10) bleibt ein offenes Problem. (Der symmetrische Fall ist genauso schwierig: r(4) = 18, aber der Wert von r(5) ist nicht bekannt.)

Und so versuchen Mathematiker stattdessen, Ramsey-Zahlen zu schätzen und legen Ober- und Untergrenzen für ihre Werte fest.

In den 1990er Jahren verwendeten sie Techniken zur zufälligen Generierung von Diagrammen, um zu beweisen, dass, wenn die rote Clique auf 3 festgelegt ist und die blaue immer größer wird, die Größe der Ramsey-Zahl mit dem Quadrat der Größe der blauen Clique wächst. Mit anderen Worten, r(3, t) etwa t².

Der neue Beweis fragt, was passiert, wenn die Größe der roten Clique auf 4 statt auf 3 festgelegt wird. In den 1930er Jahren wurde dies festgestellt r(4, t) wächst nicht schneller als ca t³. Aber die beste Untergrenze, die in den 1970er Jahren gefunden wurde, liegt bei etwa t^5/2 – deutlich kleiner.

Versuche, die Lücke durch eine Anhebung der Untergrenze oder eine Absenkung der Obergrenze zu schließen, scheiterten jahrzehntelang, bis ein Mathematikerpaar eine entscheidende Zutat hinzufügte.

Versteckt in Sichtweite

In 2019, Sam Mattheus, damals Doktorand an der Freien Universität Brüssel (VUB), suchte nach Inspiration. Sein Fachgebiet war die endliche Geometrie, das Studium der Anordnung von Punkten, Linien und anderen Strukturen in speziell definierten Räumen. Doch obwohl er die Arbeit interessant fand, fühlte er sich durch die Strenge und Genauigkeit dieser geometrischen Konstruktionen eingeschränkt.

Dann sah er ein Papier von zwei Mathematikern, Dhruv Mubayi der University of Illinois, Chicago und Jacques Verstraete der University of California, San Diego. Sie überlegten, wie sie Ramsey-Probleme angehen sollten. Während herkömmliche Techniken die zufällige Generierung von Diagrammen beinhalten, um gute Schätzungen der Ramsey-Zahlen zu erhalten, begannen Mubayi und Verstraete mit „pseudozufälligen“ Konstruktionen, die zufällig aussehen, es aber nicht sind.

Etwas machte bei Mattheus Klick. Vielleicht, dachte er, könnte seine geometrische Perspektive helfen. Während er seine Abschlussarbeit abschloss, behielt er diese Idee in den nächsten Jahren im Hinterkopf. Anschließend bewarb er sich um ein Fulbright-Stipendium, das ihm eine Postdoc-Stelle bei Verstraete in den USA ermöglichen würde

Im Jahr 2022, kurz nachdem Mattheus mit dem Fulbright-Preis ausgezeichnet wurde (zusammen mit eine weitere Gemeinschaft), wechselte er zur UCSD und begann dort mit Verstraete zusammenzuarbeiten r(4,t). Die Mathematiker wollten die Untergrenze anheben, um die bekannte Obergrenze zu erreichen. Dazu müssten sie ein Diagramm mit „fast“ finden t³ Scheitelpunkte, die keine roten Cliquen der Größe 4 oder blaue Cliquen der Größe hatten t.

Um ihren Beweis zum Laufen zu bringen, formulierten sie das Problem neu. Stellen Sie sich vor, Sie würden einfach jeden blauen Rand löschen. Das Ziel besteht nun darin, einen Graphen ohne rote Cliquen der Größe 4 und ohne unabhängige Mengen der Größe zu finden t (das heißt, Mengen von t Eckpunkte ohne Kanten).

Die Arbeit von Mubayi und Verstraete aus dem Jahr 2019 implizierte, dass man, wenn man einen pseudozufälligen Graphen ohne rote Cliquen der Größe 4 konstruieren kann, zufällige Teile davon nehmen kann, um kleinere Graphen ohne große unabhängige Mengen zu erhalten. Genau das wollten Mattheus und Verstraete finden. Indem sie mit einem noch größeren Diagramm begannen, hofften sie, ein Diagramm mit fast zu finden t³ Scheitelpunkte, die ihre Kriterien erfüllten. „In diesen Diagrammen verbergen sich bessere Ramsey-Diagramme“, sagte Verstraete.

Das Problem bestand zunächst darin, die richtige pseudozufällige Konstruktion herauszufinden.

Die Mathematiker mussten den Weg dorthin über Umwege zurücklegen. Sie begannen nicht mit einem pseudozufälligen Diagramm. Sie begannen überhaupt nicht mit einer Grafik.

Stattdessen erinnerte sich Mattheus an ein seltsames Objekt namens hermitesches Unital, etwas, mit dem endliche Geometer sehr vertraut sind – dem aber ein Mathematiker, der sich mit Kombinatorik beschäftigt, wahrscheinlich nie begegnen würde.

Ein hermitescher Unitalwert ist eine spezielle Menge von Punkten auf einer Kurve sowie Linien, die in bestimmten Konfigurationen durch diese Punkte verlaufen. Entscheidend ist, dass es auch als Diagramm dargestellt werden kann, das aus vielen großen, sich aber kaum überlappenden Cliquen besteht.

Dieser Graph ist gut bekannt und viele seiner Eigenschaften wurden untersucht. Aber es wurde nie im Kontext der Ramsey-Probleme betrachtet. „Es ist sehr spezifisch für dieses Geschäft mit endlicher Geometrie“, sagte Mattheus.

Die Grafik mag auf den ersten Blick nicht nützlich erscheinen, da sie so viele große Cliquen enthält. Ein wesentliches Merkmal des Hermiteschen Unitals besteht jedoch darin, dass es nur Cliquen der Größe 4 enthält, deren Eckpunkte auf atypische Weise gruppiert sind. Aufgrund dieser Eigenschaft war es für die Mathematiker relativ einfach, diese unerwünschten Cliquen durch zufälliges Löschen von Kanten zu zerstören.

Durch diese Löschungen erhielten sie einen neuen Graphen ohne Cliquen der Größe 4 – der jedoch immer noch große unabhängige Mengen enthielt. Mattheus und Verstraete mussten nun beweisen, dass dieser Graph pseudozufällig war. Damit konnten sie den Beweis aus dem Jahr 2019 endlich wie erhofft nutzen. Sie haben zufällige Teilgraphen mit ungefähr genommen t³ Scheitelpunkte und könnte garantieren, dass diese Teilgraphen frei von unabhängigen Größensätzen sind t.

Damit war der Beweis abgeschlossen. „Diese Konstruktion ist absolut wunderschön“, sagte Sawhney.

Die Arbeit kündigt einen Wandel in der Art und Weise an, wie Mathematiker über Ramsey-Probleme denken. „Es ist sehr, sehr natürlich, den Zufall zu nutzen, um Dinge durchzusetzen und so gute Grenzen wie möglich zu erzielen“, sagte er David Conlon des California Institute of Technology. „Aber was das wirklich zeigt, ist, dass man mit Zufälligkeit nur bedingt weit kommt.“