Das mathematische Problem, dessen Lösung fast ein Jahrhundert dauerte

Wir alle kennen das: Wir starren auf einen Mathetest mit einem Problem, das scheinbar unmöglich zu lösen ist. Was wäre, wenn die Lösung eines Problems fast ein Jahrhundert dauern würde? Für Mathematiker, die sich mit der Ramsey-Theorie beschäftigen, ist dies durchaus der Fall. Tatsächlich wurden seit den 1930er Jahren kaum Fortschritte bei der Lösung der Ramsey-Probleme erzielt.

Jetzt haben die Forscher Jacques Verstraete und Sam Mattheus von der University of California San Diego die Antwort auf r(4,t) gefunden, ein langjähriges Ramsey-Problem, das die Mathematikwelt seit Jahrzehnten verwirrt.

Was war überhaupt Ramseys Problem?

Im mathematischen Sprachgebrauch ist ein Graph eine Reihe von Punkten und die Linien zwischen diesen Punkten. Die Ramsey-Theorie geht davon aus, dass man, wenn der Graph groß genug ist, mit Sicherheit irgendeine Art von Ordnung darin vorfindet – entweder eine Menge von Punkten ohne Linien zwischen ihnen oder eine Menge von Punkten mit allen möglichen Linien dazwischen (diese Mengen werden „…“ genannt). „Cliquen“). Dies wird als r(s,t) geschrieben, wobei s die Punkte mit Linien und t die Punkte ohne Linien sind.

Für diejenigen unter uns, die sich nicht mit Graphentheorie befassen: Das bekannteste Ramsey-Problem, r(3,3), wird manchmal als „Theorem über Freunde und Fremde“ bezeichnet und anhand einer Partei erklärt: in a In einer Gruppe von sechs Personen gibt es mindestens drei Personen, die sich alle kennen, oder drei Personen, die sich alle nicht kennen. Die Antwort auf r(3,3) ist sechs.

„Es ist eine Tatsache der Natur, eine absolute Wahrheit“, sagt Verstraete. „Es spielt keine Rolle, wie die Situation ist oder welche sechs Personen Sie auswählen – Sie werden drei Personen finden, die sich alle kennen, oder drei Personen, die sich alle nicht kennen. Möglicherweise können Sie mehr finden, aber Sie sind es.“ garantiert, dass es in der einen oder anderen Clique mindestens drei gibt.

Was geschah, nachdem Mathematiker herausfanden, dass r(3,3) = 6 ist? Natürlich wollten sie r(4,4), r(5,5) und r(4,t) wissen, wobei die Anzahl der Punkte, die nicht verbunden sind, variabel ist. Die Lösung für r(4,4) ist 18 und wird mit einem Satz bewiesen, der in den 1930er Jahren von Paul Erdös und George Szekeres aufgestellt wurde.

Derzeit ist r(5,5) noch unbekannt.

Ein gutes Problem wehrt sich

Warum ist etwas, das so einfach zu sagen ist, so schwer zu lösen? Es stellt sich als komplizierter heraus, als es scheint. Nehmen wir an, Sie wussten, dass die Lösung für r(5,5) irgendwo zwischen 40 und 50 liegt. Wenn Sie mit 45 Punkten beginnen würden, müssten mehr als 10.234 Diagramme berücksichtigt werden.

„Da diese Zahlen bekanntermaßen schwer zu finden sind, suchen Mathematiker nach Schätzungen“, erklärte Verstraete. „Das ist es, was Sam und ich in unserer jüngsten Arbeit erreicht haben. Wie finden wir nicht die genaue Antwort, sondern die besten Schätzungen dafür, wie hoch diese Ramsey-Zahlen sein könnten?“

Mathematikstudenten lernen Ramsey-Probleme schon früh kennen, daher war r(4,t) die meiste Zeit seiner beruflichen Laufbahn auf Verstraetes Radar. Tatsächlich sah er das Problem zum ersten Mal in gedruckter Form in Erdös on Graphs: His Legacy of Unsolved Problems, geschrieben von zwei Professoren der UC San Diego, Fan Chung und dem verstorbenen Ron Graham. Das Problem ist eine Vermutung von Erdös, der der ersten Person, die es lösen konnte, 250 Dollar anbot.

„Viele Menschen haben über r(4,t) nachgedacht – es ist seit über 90 Jahren ein offenes Problem“, sagte Verstraete. „Aber es stand nicht im Vordergrund meiner Forschung. Jeder weiß, dass es schwierig ist und jeder hat versucht, es herauszufinden. Wenn man also keine neue Idee hat, wird man wahrscheinlich nicht weiterkommen.“

Dann, vor etwa vier Jahren, arbeitete Verstraete mit einem Mathematiker an der University of Illinois-Chicago, Dhruv Mubayi, an einem anderen Ramsey-Problem. Gemeinsam entdeckten sie, dass pseudozufällige Graphen das aktuelle Wissen über diese alten Probleme erweitern könnten.

Im Jahr 1937 entdeckte Erdös, dass die Verwendung von Zufallsgraphen gute Untergrenzen für Ramsey-Probleme liefern kann. Was Verstraete und Mubayi herausfanden, war, dass Stichproben aus Pseudozufallsgraphen häufig bessere Grenzen für Ramsey-Zahlen liefern als Zufallsgraphen. Diese Grenzen – Ober- und Untergrenzen der möglichen Antwort – engten den Bereich der Schätzungen ein, die sie vornehmen konnten. Mit anderen Worten: Sie kamen der Wahrheit näher.

Im Jahr 2019 verwendeten Verstraete und Mubayi zur Freude der Mathematikwelt pseudozufällige Graphen, um r(3,t) zu lösen. Allerdings hatte Verstraete Schwierigkeiten, einen pseudozufälligen Graphen zu erstellen, der bei der Lösung von r(4,t) helfen könnte.

Er begann, sich mit verschiedenen Bereichen der Mathematik außerhalb der Kombinatorik zu beschäftigen, darunter endliche Geometrie, Algebra und Wahrscheinlichkeit. Schließlich schloss er sich mit Mattheus zusammen, einem Postdoktoranden in seiner Gruppe, dessen Hintergrund in der endlichen Geometrie lag.

„Es stellte sich heraus, dass der von uns benötigte Pseudozufallsgraph in endlicher Geometrie gefunden werden konnte“, erklärte Verstraete. „Sam war die perfekte Person, um mitzuhelfen, das aufzubauen, was wir brauchten.“

Nachdem sie den Pseudozufallsgraphen erstellt hatten, mussten sie noch mehrere mathematische Teile lösen. Es dauerte fast ein Jahr, aber schließlich erkannten sie, dass sie eine Lösung hatten: r(4,t) liegt nahe an einer kubischen Funktion von t. Wenn Sie eine Party wollen, bei der immer vier Personen anwesend sind, die sich alle kennen, oder zwei Personen, die sich alle nicht kennen, müssen ungefähr drei Personen anwesend sein. Es gibt ein kleines Sternchen (eigentlich ein O), denn denken Sie daran, dass es sich hierbei um eine Schätzung und nicht um eine genaue Antwort handelt. Aber t3 kommt der genauen Antwort sehr nahe.

Die Ergebnisse werden derzeit mit dem überprüft Annalen der Mathematik. Ein Vorabdruck kann sein angesehen An arXiv.

„Wir haben wirklich Jahre gebraucht, um das Problem zu lösen“, erklärte Verstraete. „Und oft steckten wir fest und fragten uns, ob wir das überhaupt lösen könnten. Aber man sollte niemals aufgeben, egal wie lange es dauert.“

Verstraete betont die Bedeutung von Ausdauer – etwas, woran er seine Schüler oft erinnert. „Wenn Sie feststellen, dass das Problem schwierig ist und Sie nicht weiterkommen, bedeutet das, dass es ein gutes Problem ist. Fan Chung sagte, ein gutes Problem wehrt sich. Man kann nicht erwarten, dass es sich einfach offenbart.“

Verstraete weiß, dass solch beharrliche Entschlossenheit gut belohnt wird: „Ich bekam einen Anruf von Fan, der sagte, sie schulde mir 250 Dollar.“