Steiner-Tripelsysteme

Erdös-Vermutung nach 50 Jahren gelöst

Robert Klatt

Mathematiker haben ein Steiner-Tripelsystem mit beliebiger Taillenweite erschaffen und somit die Erdös-Vermutung nach 50 Jahren bewiesen.

Klosterneuburg (Österreich). Der Mathematiker Paul Erdös gilt aufgrund seiner zahlreichen Vermutungen und Sätze in der Zahlentheorie und Kombinatorik als einer der wichtigsten Mathematiker des 20. Jahrhunderts. Beschäftigt hat sich Erdös unter anderem mit der geometrischen Ordnung von Graphen. Ein Teil dieser kombinatorischen Entwürfe hat nicht nur bei abstrakte Zusammenhängen Relevanz, sondern wird auch für Computercodes und Experimente verwendet.

Dazu gehört etwa das sogenannte Steinersche Tripelsystemen, das die Anzahl möglicher Dreier-Kombinationen unter einschränkenden Bedingungen beschreibt. Ein Beispiel dafür ist sieben Menschen, die Dreiergruppen bilden sollen. Jede Person darf in diesem Fall zu mehreren Tripeln gehören, aber jedes Paar darf nur Teil einer Dreiergruppe sein. Wenn diese Bedingung mit wenigen Personen und einer hohen Anzahl von Tripeln erfüllt wird, spricht man in der Mathematik von einer großen Taillenweite.

Beweis für Tripelsysteme

Laut Erös sind solche Tripelsystem möglich. Bisher konnte die Mathematik aber nur Tripelsysteme mit maximal sechs Personen beweisen. „Probleme dieses Typs sind im Allgemeinen ungeheuer schwierig zu beweisen und es erschient fast weit außerhalb unserer Reichweite, die Zahl der Tripel präzise zu charakterisieren, die es für eine vorgegebene Konfiguration gibt“, erklärt Matthew Kwan vom Institute of Science and Technology Austria (ISTA).

Großes Tripelsystem durch kombinierte Methoden

Laut einer Publikation auf dem Preprint-Server arXiv ist es den Wissenschaftlern des ISTA nun gelungen, ein Steiner-Tripelsystem mit beliebiger Taillenweite zu beweisen. „Um ihre Existenz zu beweisen, muss man die Algebra vermeiden und Methoden aus der Wahrscheinlichkeitstheorie, der Probabilistik. Das ist uns gelungen“, erklärt Kwan.

Die Wissenschaftler kombinierten dazu verschiedene mathematische Verfahren auf Basis der probabilistischen 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 die Sparsification, eine Art Ausdünnung, die alle Herausforderungen der retrospektiven Analyse beseitigt“ so Kwan.

Erdös-Vermutung bewiesen

Die vor 50 Jahren erdachte Erdös-Vermutung ist somit bewiesen. „Wir können unter anderem beweisen, wo die Untergrenze für die Zahl der r-sparsamen Steiner-Tripelsysteme bei einem gegebenen Satz von Eckpunkten liegt“, erklären die Autoren. Dies belegt, dass bei sieben Eckpunkten exakt sieben Tripel ohne doppelte Paare gebildet werden können.

Möglich war diese Leistung, durch die Anwendung von Methoden aus unterschiedlichen Teildisziplinen der Mathematik. „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“, konstatiert Kwan.

arXiv, doi: 10.48550/arXiv.2201.04554

Spannend & Interessant
VGWortpixel