Bisher in diesem Jahr Wie viel hat drei große Fortschritte in der Ramsey-Theorie aufgezeichnet, der Untersuchung, wie man die Entstehung mathematischer Muster vermeiden kann. Der erstes Ergebnis Setzen Sie eine neue Obergrenze dafür, wie groß eine Menge von ganzen Zahlen sein kann, ohne drei gleichmäßig verteilte Zahlen wie {2, 4, 6} oder {21, 31, 41} zu enthalten. Der zweite und dritte Ebenso werden neue Grenzen für die Größe von Netzwerken ohne Cluster von Punkten gesetzt, die entweder alle miteinander verbunden oder alle voneinander isoliert sind.

Die Beweise befassen sich damit, was passiert, wenn die beteiligten Zahlen unendlich groß werden. Paradoxerweise kann dies manchmal einfacher sein, als mit lästigen realen Größen umzugehen.

Betrachten Sie zum Beispiel zwei Fragen zu einem Bruch mit einem wirklich großen Nenner. Sie fragen sich vielleicht, was die Dezimalentwicklung von beispielsweise 1/42503312127361 ist. Oder Sie könnten fragen, ob diese Zahl mit zunehmendem Nenner näher an Null herankommt. Bei der ersten Frage handelt es sich um eine spezifische Frage zu einer realen Größe, und sie ist schwieriger zu berechnen als die zweite, bei der gefragt wird, wie die Größe 1/n wird sich „asymptotisch“ ändern als n wächst. (Es kommt immer näher an 0.)

„Dies ist ein Problem, das die gesamte Ramsey-Theorie plagt“, sagte er Wilhelm Gasarch, ein Informatiker an der University of Maryland. „Die Ramsey-Theorie ist dafür bekannt, dass sie asymptotisch sehr schöne Ergebnisse liefert.“ Aber die Analyse von Zahlen, die kleiner als unendlich sind, erfordert einen ganz anderen mathematischen Werkzeugkasten.

Gasarch hat Fragen der Ramsey-Theorie untersucht, bei denen es um endliche Zahlen geht, die zu groß sind, als dass das Problem mit roher Gewalt gelöst werden könnte. In einem Projekt nahm er sich der endlichen Version des ersten Durchbruchs dieses Jahres an – einem Februar-Artikel von Zander Kelley, ein Doktorand an der University of Illinois, Urbana-Champaign, und Raghu Meka der University of California, Los Angeles. Kelley und Meka haben eine neue Obergrenze dafür gefunden, wie viele ganze Zahlen zwischen 1 und liegen N Sie können sie in einen Satz einteilen und dabei Drei-Term-Progressionen oder Muster gleichmäßig verteilter Zahlen vermeiden.

Obwohl das Ergebnis von Kelley und Meka gilt, selbst wenn N relativ klein ist, ergibt sich in diesem Fall keine besonders nützliche Grenze. Für sehr kleine Werte von N, bleiben Sie besser bei sehr einfachen Methoden. Wenn N ist beispielsweise 5, schauen Sie sich einfach alle möglichen Zahlenmengen zwischen 1 und an N, und wählen Sie den größten progressionsfreien aus: {1, 2, 4, 5}.

Doch die Zahl der unterschiedlichen Antwortmöglichkeiten wächst sehr schnell und macht es zu schwierig, eine so einfache Strategie anzuwenden. Es gibt mehr als 1 Million Sätze, die aus Zahlen zwischen 1 und 20 bestehen. Es gibt über 10⁶⁰ unter Verwendung von Zahlen zwischen 1 und 200. Das Finden des besten progressionsfreien Satzes für diese Fälle erfordert eine beträchtliche Dosis Rechenleistung, selbst mit effizienzsteigernden Strategien. „Man muss in der Lage sein, viel Leistung aus den Dingen herauszuholen“, sagte er James Glenn, Informatiker an der Yale University. Im Jahr 2008 haben Gasarch, Glenn und Clyde Kruskal der University of Maryland ein Programm geschrieben um die größten progressionsfreien Sätze bis zu einem zu finden N von 187. (Vorherige Arbeiten hatten die Antworten auf 150 und auch auf 157 gebracht.) Trotz einer Liste von Tricks habe es Monate gedauert, bis ihr Programm fertig sei, sagte Glenn.

Um die Rechenlast zu verringern, verwendete das Team einfache Tests, die verhinderten, dass das Programm Sackgassensuchen durchführte, und teilten die Mengen in kleinere Teile auf, die sie separat analysierten.

Gasarch, Glenn und Kruskal versuchten auch mehrere andere Strategien. Eine vielversprechende Idee beruhte auf Zufälligkeit. Eine einfache Möglichkeit, eine progressionsfreie Menge zu erstellen, besteht darin, 1 in die Menge einzufügen und dann immer die nächste Zahl hinzuzufügen, die keine arithmetische Folge ergibt. Befolgen Sie dieses Verfahren, bis Sie die Zahl 10 erreichen, und Sie erhalten die Menge {1, 2, 4, 5, 10}. Aber es stellt sich heraus, dass dies im Allgemeinen nicht die beste Strategie ist. „Was ist, wenn wir nicht bei 1 anfangen?“ Sagte Gasarch. „Wenn man an einer beliebigen Stelle anfängt, macht man es tatsächlich besser.“ Forscher hätten keine Ahnung, warum Zufälligkeit so nützlich sei, fügte er hinzu.

Die Berechnung der endlichen Versionen der beiden anderen Ergebnisse der neuen Ramsey-Theorie ist noch schwieriger als die Bestimmung der Größe progressionsfreier Mengen. Bei diesen Ergebnissen handelt es sich um mathematische Netzwerke (sogenannte Graphen), die aus Knoten bestehen, die durch Linien, sogenannte Kanten, verbunden sind. Die Ramsey-Zahl r(s, t) ist die kleinste Anzahl von Knoten, die ein Graph haben muss, bevor es unmöglich wird, die Einbeziehung einer Gruppe von Knoten zu vermeiden s verbundene Knoten bzw t getrennte. Schon allein die Berechnung der Ramsey-Zahl bereitet große Schwierigkeiten r(5, 5) ist unbekannt – es liegt irgendwo zwischen 43 und 48.

In 1981, Brendan McKay, heute Informatiker an der Australian National University, schrieb ein Softwareprogramm namens nauty, das die Berechnung von Ramsey-Zahlen einfacher machen sollte. Nauty sorgt dafür, dass Forscher keine Zeit damit verschwenden, zwei Diagramme zu überprüfen, die nur gespiegelte oder gedrehte Versionen voneinander sind. „Wenn jemand in der Nähe ist und kein Nauty verwendet, ist das Spiel vorbei. „Sie müssen es nutzen“, sagte er Stanislaus Radziszowski, ein Mathematiker am Rochester Institute of Technology. Dennoch ist der Rechenaufwand nahezu unvorstellbar. Im Jahr 2013 haben Radziszowski und Jan Goedgebeur geprüft, dass r(3, 10) beträgt höchstens 42. „Ich glaube, es hat fast 50 CPU-Jahre gedauert“, sagte Goedgebeur, Informatiker an der Universität KU Leuven in Belgien.

Wenn Sie keine exakte Ramsey-Zahl berechnen können, können Sie versuchen, ihren Wert anhand von Beispielen einzugrenzen. Wenn Sie einen Graphen mit 45 Knoten finden würden, ohne fünf Knoten, die alle verbunden wären, und ohne fünf Knoten, die alle getrennt wären, wäre das der Beweis r(5, 5) ist größer als 45. Mathematiker, die Ramsey-Zahlen studieren, dachten früher, dass es einfach sein würde, diese Beispiele, sogenannte Ramsey-Graphen, zu finden, sagte Radziszowski. Aber dem war nicht so. „Es gab die Erwartung, dass schöne, coole mathematische Konstruktionen die bestmöglichen Konstruktionen ergeben würden, und wir brauchen einfach mehr Leute, die daran arbeiten“, sagte er. „Ich habe immer mehr das Gefühl, dass es chaotisch ist.“

Zufälligkeit ist sowohl ein Hindernis für das Verständnis als auch ein nützliches Werkzeug. Geoffrey Exoo, ein Informatiker an der Indiana State University, hat Jahre damit verbracht, Zufallsmethoden zur Erstellung von Ramsey-Graphen zu verfeinern. In ein 2015-Papier Exoo und Milos Tatarevic kündigten Dutzende neuer, rekordverdächtiger Ramsey-Graphen an, generierten Zufallsgraphen und optimierten sie dann nach und nach, indem sie Kanten löschten oder hinzufügten, um die Anzahl unerwünschter Cluster zu reduzieren, bis sie einen Ramsey-Graphen fanden. Exoos Techniken seien jedoch ebenso eine Kunst wie alles andere, sagte Radziszowski. Manchmal erfordern sie, dass er mehrere Methoden kombiniert oder ein Urteil darüber richtet, mit welcher Art von Diagrammen er beginnen soll. „Viele, viele Leute versuchen es, aber sie schaffen es nicht“, sagte Radziszowski.

Die zur Generierung von Ramsey-Graphen entwickelten Techniken könnten eines Tages von größerem Nutzen sein, sagte Goedgebeur, der dies getan hat arbeitete an Erstellen anderer Arten von Diagrammen, beispielsweise Diagrammen, die chemische Verbindungen darstellen. „Es ist nicht unwahrscheinlich, dass diese Techniken auch übertragen und angepasst werden können, um andere Klassen von Diagrammen effizienter zu generieren (und umgekehrt)“, schrieb er in einer E-Mail.

Für Radziszowski ist der Grund für die Untersuchung der kleinen Ramsey-Zahlen jedoch viel einfacher. „Weil es offen ist, weil niemand weiß, wie die Antwort lautet“, sagte er. „Die trivialen Fälle erledigen wir von Hand; etwas größer, man braucht einen Computer, und etwas größer, selbst der Computer ist nicht gut genug. Und so entsteht die Herausforderung.“