Hypergraphen zeigen eine Lösung für ein 50 Jahre altes Drawback

quanta Hypergraphs 2880x1620 Lede scaled


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 Artwork 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 Artwork 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 Relaxation des Techniques 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 huge 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 Drawback von Erdős struggle selbst bei iterativer Absorption schwierig. „Es wurde ziemlich schnell klar, warum dieses Drawback nicht gelöst wurde“, sagte Mehtaab Sawhney, einer der vier Forscher, die es gelöst haben, zusammen mit Ashwin Sah, der wie Sawhney ein Doktorand am Massachusetts Institute of Expertise ist; Michael Simkin, Postdoktorand am Zentrum für mathematische Wissenschaften und Anwendungen der Harvard College; und Matthew Kwan, Mathematiker am Institute of Science and Expertise Austria. „Es gab ziemlich interessante, ziemlich schwierige technische Aufgaben.“

Bei anderen Anwendungen der iterativen Absorption können Sie zum Beispiel, wenn Sie eine Menge fertig abgedeckt haben – entweder mit Dreiecken für Steiner-Tripelsysteme oder mit anderen Strukturen für andere Probleme –, diese 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 umfassen.

„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, struggle, 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 Drawback hinaus erweitert werden kann. Sie haben ihre Strategie bereits auf ein Drawback mit lateinischen Quadraten angewendet, 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 Drawback lösen kann, hat sie seit ihrer Einführung einen langen Weg zurückgelegt, sagte Maya Stein, die stellvertretende Direktorin des Zentrums für mathematische Modellierung an der Universität von Chile. „Das ist wirklich toll zu sehen, wie sich diese Methoden weiterentwickeln.“

Ursprüngliche Geschichte Nachdruck mit freundlicher Genehmigung von Quanta-Magazin, eine redaktionell unabhängige Publikation der Simons-Stiftung dessen Aufgabe es ist, das öffentliche Verständnis der Wissenschaft zu verbessern, indem Forschungsentwicklungen und -trends in der Mathematik und den Natur- und Biowissenschaften behandelt werden.

admin

Leave a Reply

Your email address will not be published.