In 1850, Thomas Penynton Kirkman, ein Mathematiker, als er nicht seiner Hauptaufgabe als Vikar in der Church of England nachkam, beschrieb sein „Schulmädchenproblem“: „Fünfzehn junge Damen in einer Schule gehen sieben Tage hintereinander zu dritt aus der Schule: Es muss arrangiert werden sie täglich, damit niemand zweimal nebeneinander wandelt.“
Für einen modernen Mathematiker stellt man sich diese Art von Problem am besten als Hypergraph vor – eine Reihe von Knoten, die in Gruppen von drei oder mehr zusammengefasst sind. Die 15 Schulmädchen sind Knoten, und jede Gruppe von „drei nebeneinander“ kann als Dreieck mit drei Linien oder Kanten betrachtet werden, die drei Knoten verbinden.
Kirkmans Problem fragt im Wesentlichen, ob es eine Anordnung dieser Dreiecke gibt, die alle Schulmädchen miteinander verbindet, aber mit der zusätzlichen Einschränkung, dass keine zwei Dreiecke eine gemeinsame Kante haben. Edge-Sharing würde bedeuten, dass zwei Schulmädchen mehr als einmal zusammen gehen müssen. Diese Einschränkung bedeutet, dass jedes Mädchen eine Woche lang jeden Tag mit zwei neuen Freunden spazieren geht, sodass jedes mögliche Paar genau einmal zusammenkommt.
Dieses und andere ähnliche Probleme haben Mathematiker in den fast zwei Jahrhunderten fasziniert, seit Kirkman seine Frage gestellt hat. 1973 stellte der legendäre Mathematiker Paul Erdős ein ähnliches auf. Er fragte, ob es möglich sei, einen Hypergraphen mit zwei scheinbar unvereinbaren Eigenschaften zu erstellen. Zunächst muss wie bei den Schulmädchen jedes Knotenpaar durch genau ein Dreieck verbunden sein. Diese Eigenschaft macht den Graphen dicht mit Dreiecken. Die zweite Bedingung zwingt die Dreiecke sehr präzise zu spreizen. (Insbesondere erfordert es, dass es für jede kleine Gruppe von Dreiecken mindestens drei Knoten mehr gibt als Dreiecke.) „Sie haben dieses leicht widersprüchliche Verhalten, bei dem Sie ein dichtes Gesamtobjekt haben, das keine dichten Teile hat“, sagte David Conlon, Mathematiker am California Institute of Technology.
Diesen Januar, in ein komplizierter 50-seitiger Korrekturabzughaben vier Mathematiker bewiesen, dass es immer möglich ist, einen solchen Hypergraphen zu bauen, solange man genügend Knoten hat. „Die Menge an Formalitäten, die [sie] durchgemacht haben, nur um das zu bekommen, war erstaunlich“, sagte er Allan Lo, Mathematiker an der University of Birmingham. Conlon stimmte zu: „Es ist eine wirklich beeindruckende Arbeit.“
Das Forschungsteam baute ein System, das die teuflischen Anforderungen von Erdős erfüllte, indem es mit einem zufälligen Prozess zur Auswahl von Dreiecken begann und es mit äußerster Sorgfalt so konstruierte, dass es seinen Bedürfnissen entspricht. „Die Anzahl der schwierigen Modifikationen, die in den Beweis einfließen, ist tatsächlich überwältigend“, sagte Conlon.
Ihre Strategie bestand darin, den Hypergraphen sorgfältig aus einzelnen Dreiecken aufzubauen. Stellen Sie sich zum Beispiel unsere 15 Schulmädchen vor. Ziehe eine Linie zwischen jedem Paar.
Das Ziel hier ist es, Dreiecke über diesen Linien so zu zeichnen, dass die Dreiecke zwei Anforderungen erfüllen: Erstens teilen sich keine zwei Dreiecke eine Kante. (Systeme, die diese Anforderung erfüllen, werden Steiner-Tripelsysteme genannt.) Und zweitens, stellen Sie sicher, dass jede kleine Teilmenge von Dreiecken eine ausreichend große Anzahl von Knoten verwendet.
Die Art und Weise, wie die Forscher dabei vorgegangen sind, lässt sich vielleicht am besten anhand einer Analogie verstehen.
Angenommen, Sie bauen Häuser aus Legosteinen, anstatt Dreiecke aus Kanten zu machen. Die ersten paar Gebäude, die Sie bauen, sind extravagant, mit strukturellen Verstärkungen und kunstvollen Verzierungen. Sobald Sie damit fertig sind, legen Sie sie beiseite. Sie dienen als „Absorber“ – eine Art strukturierter Vorrat.
Fangen Sie jetzt an, Gebäude aus Ihren verbleibenden Steinen zu bauen, ohne viel zu planen. Wenn Ihr Vorrat an Legos zur Neige geht, finden Sie sich möglicherweise mit einigen verirrten Steinen oder Häusern wieder, die strukturell nicht intakt sind. Aber da die Absorbergebäude so übertrieben und verstärkt sind, kann man hier und da ein paar Steine herausreißen und verwenden, ohne eine Katastrophe zu beschwören.
Im Fall des Steiner-Dreiersystems versuchen Sie, Dreiecke zu erstellen. Ihr Absorber ist in diesem Fall eine sorgfältig ausgewählte Sammlung von Kanten. Wenn Sie den Rest des Systems nicht in Dreiecke sortieren können, können Sie einige der Kanten verwenden, die in den Absorber führen. Wenn Sie damit fertig sind, zerlegen Sie den Absorber selbst in Dreiecke.
Absorption funktioniert nicht immer. Aber Mathematiker haben an dem Prozess herumgebastelt und neue Wege gefunden, um Hindernisse zu umgehen. Beispielsweise teilt eine leistungsstarke Variante namens iterative Absorption die Kanten in eine verschachtelte Folge von Sätzen, sodass jeder als Absorber für den nächstgrößten fungiert.
„In den letzten zehn Jahren gab es massive Verbesserungen“, sagte Conlon. "Es ist so etwas wie eine Kunstform, aber sie haben es zu diesem Zeitpunkt wirklich auf das Niveau der hohen Kunst gebracht."
Das Problem von Erdős war selbst bei iterativer Absorption schwierig. „Es wurde ziemlich schnell klar, warum dieses Problem nicht gelöst worden war“, sagte er Mehtaab Sawhney, einer der vier Forscher, die es gelöst haben, zusammen mit Ashwin Sah, der zusammen mit Sawhney ein Doktorand am Massachusetts Institute of Technology ist; Michael Simkin, Postdoktorand am Zentrum für mathematische Wissenschaften und Anwendungen der Harvard University; und Matthäus Kwan, Mathematiker am Institute of Science and Technology Austria. „Es gab ziemlich interessante, ziemlich schwierige technische Aufgaben.“
Bei anderen Anwendungen der iterativen Absorption können Sie zum Beispiel, wenn Sie eine Menge vollständig abgedeckt haben – entweder mit Dreiecken, für Steiner-Tripelsysteme oder mit anderen Strukturen für andere Probleme – sie als erledigt betrachten und vergessen. Die Bedingungen von Erdős hinderten die vier Mathematiker jedoch daran. Ein problematischer Cluster von Dreiecken könnte leicht Knoten aus mehreren Absorbersätzen beinhalten.
„Ein Dreieck, das Sie vor 500 Schritten ausgewählt haben, Sie müssen sich irgendwie daran erinnern, wie Sie darüber denken“, sagte Sawhney.
Was die vier schließlich herausfanden, war, dass sie, wenn sie ihre Dreiecke sorgfältig auswählten, die Notwendigkeit umgehen konnten, jede Kleinigkeit im Auge zu behalten. „Es ist besser, an eine beliebige kleine Menge von 100 Dreiecken zu denken und sicherzustellen, dass die Menge von Dreiecken mit der richtigen Wahrscheinlichkeit ausgewählt wird“, sagte Sawhney.
Die Autoren der neuen Arbeit sind optimistisch, dass ihre Technik über dieses eine Problem hinaus erweitert werden kann. Sie haben haben ihre Strategie bereits angewendet zu einem Problem über Lateinische Quadrate, die wie eine Vereinfachung eines Sudoku-Rätsels sind.
Darüber hinaus gibt es mehrere Fragen, die letztendlich zu Absorptionsmethoden führen könnten, sagte Kwan. „Es gibt so viele Probleme in der Kombinatorik, besonders in der Designtheorie, wo Zufallsprozesse ein wirklich mächtiges Werkzeug sind.“ Eines dieser Probleme, die Ryser-Brualdi-Stein-Vermutung, betrifft ebenfalls lateinische Quadrate und wartet seit den 1960er Jahren auf eine Lösung.
Obwohl die Absorption möglicherweise weiterentwickelt werden muss, bevor sie dieses Problem lösen kann, hat sie seit ihrer Einführung vor 30 Jahren einen langen Weg zurückgelegt, sagte er Maja Stein, stellvertretender Direktor des Zentrums für mathematische Modellierung an der Universität von Chile. „Das ist wirklich toll zu sehen, wie sich diese Methoden weiterentwickeln.“
