14. März 2022

Jahrzehnte alte Erdős-Vermutung geknackt

Jüngstem ISTA-Professor gelingt mathematischer Durchbruch in der kombinatorischen Designtheorie

PiDay Kwan Steiner Triple (c) ISTA
© ISTA

Einige der berühmtesten Probleme der Mathematik bleiben für Jahrhunderte ungelöst. Für Erdős‘ Vermutung dauerte es fünfzig Jahre, bis eine Lösung gefunden wurde. Professor Matthew Kwan vom Institute of Science and Technology Austria (ISTA) und Mathematiker aus Harvard und dem MIT präsentieren einen Beweis, der die Existenz sogenannter Steiner-Tripelsystemen mit hoher Taillenweite belegt.

Als Matthew Kwan während seines Studiums von der Erdős-Vermutung hörte, hätte er niemals gedacht, ein paar Jahre später den Beweis dieses berüchtigten Theorems zu präsentieren. In der neuen Arbeit beweisen Kwan und Kollegen die Existenz von Steiner-Tripelsystemen mit beliebig hoher Taillenweite (engl. high-girth). Für den ausgefeilten Beweis arbeitete das neue ISTA-Fakultätsmitglied Kwan mit dem Kollegen Michael Simkin der Harvard University und den beiden Ausnahmestudenten Ashwin Sah und Mehtaab Sawhney vom Massachusetts Institute of Technology (MIT) zusammen.

Steiner‘sche Tripelsysteme sind grundlegende Typen von kombinatorischen Designs, die ihre Wurzeln im Entwerfen von Experimenten haben. So ist es beispielsweise wichtig zu wissen, welche Getreidesorten auf Böden mit unterschiedlichen Eigenschaften gedeihen können. Wie kann man aber alle Kombinationen effizient testen? Mit geschickter Kombinatorik lässt sich die Zahl der Experimente wesentlich reduzieren. Heutzutage untersucht die kombinatorische Designtheorie abstraktere Zusammenhänge. Ihre Resultate sind für die Theorien hinter Computercode relevant. Nach wie vor sind jedoch grundlegende Probleme ungelöst. Dazu gehörte auch die Erdős-Vermutung – bis jetzt.

Prof. Matthew Kwan, Institute of Science and Technology Austria
Professor Matthew Kwan. Der Mathematiker, der erst seit 2021 am ISTA forscht, erregt bereits jetzt Aufsehen mit dem Beweis der Erdős-Vermutung in Zusammenarbeit mit Kollegen aus Harvard und dem MIT. © Matthew Kwan

Was ist die Erdős-Vermutung?

Die Vermutung bezieht sich auf so genannte Steiner-Tripelsysteme. Angenommen, sieben Personen wollen Dreiergruppen bilden. Jede Person kann Teil mehrerer Tripel sein, aber jedes Personenpaar darf nur Teil von exakt einer Dreiergruppe sein. Ein Individuum A kann daher Teil von drei Tripeln sein, indem es das erste Tripel mit B und C, das zweite mit E und F und das dritte mit D und G bildet. B zum Beispiel darf kein Trio mehr bilden, das A oder C enthält, da die Paare BA und BC schon im Tripel ABC vorkommen. B kann aber immer noch zwei andere Tripel bilden. Tatsächlich sind bei sieben Personen – oder Punkten, wie sie in Designs genannt werden – genau sieben Tripel möglich. In diesem Beispiel liegt ein Steiner-Tripelsystem vor.

The Fano Plane
Die Fano-Ebene ist ein Steiner-Tripelsystem. Jeder Punkt bildet drei Tripel, die durch Verbindungslinien derselben Farbe gekennzeichnet sind, während jedes Punktpaar nur zu exakt einem Tripel gehört. © ISTA

Die Mathematiker zeigten, dass Steiner-Tripelsysteme mit der wünschenswerten Eigenschaft einer hohen Taillenweite tatsächlich existieren. Eine hohe Taillenweite ist eine statistische Bedingung. Wenn sich viele Tripel über eine kleine Anzahl von Punkten erstrecken, ist die Taillenweite niedrig. „Solche dichten Stellen treten bei algebraischen Konstruktionen unweigerlich auf“, erklärt Kwan. „Erdős hat sich gefragt, ob man sie vermeiden kann. Wenn Tripel keine solchen Konfigurationen aufweisen, sagt man, dass das System eine hohen Taillenweite besitzt. Um ihre Existenz zu beweisen, muss man die Algebra vermeiden und Methoden aus der Wahrscheinlichkeitstheorie, der Probabilistik, einführen. Das ist uns gelungen.“

Interdisziplinarität innerhalb der Mathematik

In Designtheorie, diesem vielleicht ältesten Gebiet der Kombinatorik gab es bis vor acht Jahren nur begrenzte Fortschritte bei den fundamentalen Fragen. Kwans Hintergrund in probabilistischer Kombinatorik eröffnete ihm die Vorstöße, die das Gebiet seit den bahnbrechenden Fortschritten im Jahr 2014 revolutionierten. Der neue Beweis umfasst eine breite Palette von Techniken an der Grenze zwischen extremaler und probabilistischer Kombinatorik. „Zusätzlich haben wir zwei neue Methoden benutzt: Die Retrospektive Analyse, die es uns ermöglicht, die Zufälligkeit in früheren Schritten nachzuverfolgen, und Sparsification, eine Art Ausdünnung, die alle Herausforderungen der retrospektiven Analyse beseitigt“, fasst Kwan die technischen Aspekte des Ergebnisses zusammen.

Mehr

Retrospektive Analyse

Die retrospektive Analyse umgeht eine Eigenheit der Erdős-Vermutung, nämlich jene, dass man zwei getrennte Systeme nicht unter Beibehaltung bestimmter Eigenschaften zusammenführen kann. Anstatt sich alle Informationen der vorherigen Schritte zu merken, merkt sich die neue Methode nur die Zufälligkeit. „Das ist eine entscheidende Komponente für den Beweis. Unsere Analyse wäre sonst völlig unpraktikabel“, sagt Kwan.

Sparsification 

Die Sparsification hingegen befasst sich mit den Grenzen der iterativen Absorption (engl. iterative absorption), einer Methode, bei der wiederholt Zufallsprozesse ausgeführt werden, um immer weitere Tripel in einem Design zu konstruieren, während die Steiner-Eigenschaft erhalten bleibt. „Durch iterative Absorption sammelt man Einschränkungen. Indem man die Umgebung vor den Zufallsprozessen ausdünnt, startet man mit weniger Einschränkungen, und das erlaubt es letztlich, zu einer brauchbaren Schlussfolgerung zu gelangen.“

 

Mit seiner Gruppe am ISTA strebt Kwan ein besseres Verständnis der Grundlagen von mathematischen Designs an, insbesondere unter dem Gesichtspunkt der Wahrscheinlichkeitstheorie. „Meine Philosophie: Ich versuche, an verschiedenen Dingen zu arbeiten. Es mag verlockend sein, sich komplett auf ein Teilgebiet zu konzentrieren, aber wenn man sein ganzes Leben lang an verschiedenen Problemen tüftelt, findet man jene Techniken, die einem helfen, in anderen Bereichen Neues zu entdecken.“

Publikation:

Kwan E, Sah A, Sawhney M und Simkin M. 2022. High-girth Steiner triple systems. Preprint. arXiv:2201.04554v3

Weitere Lektüre

Erica Klarreich (2015): A Design Dilemma Solved, Minus Designs. Quanta Magazine. – Populäre Darstellung der Steiner Tripelsysteme und der jüngsten Durchbrüche in der Designtheorie.

Yufei, Zhao (2022): Kwan-Sah-Sawhney-Simkin: High-girth Steiner triple systems.Detaillierter Blog-Eintrag.



Teilen

Nach Oben