Der langerwartete Graphen-Sandwich-Beweis

Kristina Armitage/ Quanta Magazine

Im Jahr 2004 hypothetisierten zwei Mathematiker eine mächtige Art von Sandwich.

Sie untersuchten Graphen. Das sind Sammlungen von Punkten, die man Scheitelpunkte nennt, und Linien, die man Kanten nennt. Graphen können alles von sozialen Gruppen bis zum Internet bis zu Neuronen im Gehirn darstellen. Die Mathematiker hofften, Eigenschaften einer Art von Graph zu verstehen. Diese Art ist in Mathematik und Informatik allgegenwärtig, aber schwer zu analysieren. Man kann sie auf eine mathematisch strenge Weise zwischen zwei einfachen Graphen „schichten“.

Wenn Forscher die Existenz eines solchen Sandwiches beweisen könnten, würden sie nicht nur zeigen, dass der mittlere Graph eine interessante Eigenschaft hat. Sie würden zeigen, dass er alle möglichen wichtigen Eigenschaften hat. Damit würden sie auch zeigen, dass zwei sehr verschiedene Zufallsprozesse, die Mathematiker gerne untersuchen, auf eine tiefere und elegantere Weise verbunden sind, als sie sich vorgestellt hatten.

„Der Begriff ist so schön“, sagte Pu Gao, ein Mathematiker an der University of Waterloo in Kanada, der an dem Problem gearbeitet hat. „Was mich am meisten anzieht, ist eigentlich die Schönheit davon.“

In den letzten zwei Jahrzehnten machten Mathematiker Fortschritte bei der „Sandwich-Vermutung“. Sie besagt, dass man, solange der Graph, an dem man interessiert ist, groß genug ist, immer das benötigte Sandwich erstellen kann. Aber niemand konnte es vollständig beweisen. Dann fanden 2025 drei Mathematiker eine Möglichkeit, die Techniken ihres Feldes an ihre Grenzen zu bringen, und vollendeten die Suche.

Graphen mit verschiedenen Geschmäckern

In den späten 1950er Jahren untersuchte der amerikanische Mathematiker Edgar Gilbert Telefongesellschaften bei den Bell Labs. Um diese Netzwerke besser zu verstehen, entwickelte er ein einfaches Modell eines „zufälligen“ Graphen. Bei diesem verbinden sich Scheitelpunkte zufällig mit anderen Scheitelpunkten. (Die Mathematiker Paul Erdős und Alfréd Rényi entwickelten unabhängig voneinander etwa zur gleichen Zeit ein ähnliches Modell.)

Um einen dieser Graphen zu erstellen, beginnen Sie mit einer Menge von Scheitelpunkten. Wählen Sie jedes beliebige Paar von Scheitelpunkten in Ihrer Menge aus und werfen Sie eine (möglicherweise verzerrte) Münze. Wenn Sie Kopf bekommen, zeichnen Sie eine Kante zwischen ihnen, andernfalls gehen Sie weiter. Wiederholen Sie diesen Schritt für jedes Paar von Scheitelpunkten im Graphen.

Diese Graphen, die als zufällige Binomialgraphen bekannt sind, erwiesen sich als nützliche – wenn auch unvollkommene – Möglichkeit, Netzwerke darzustellen. Sie waren relativ einfach zu analysieren, und Mathematiker bewiesen viele interessante Dinge über sie. In den 1970er Jahren entdeckten sie zum Beispiel, unter welchen Bedingungen ein zufälliger Binomialgraph einen Hamiltonkreis enthält. Das ist ein Pfad, der jeden Scheitelpunkt genau einmal besucht.

Aber das ist nicht die einzige Art von Zufallsgraphen. Mathematiker waren auch neugierig auf Zufallsgraphen, bei denen alle Scheitelpunkte die gleiche Anzahl von Kanten haben. Diese sogenannten regulären Graphen bieten ein besseres Verständnis zufälliger Strukturen als Binomialgraphen. Und sie sind oft viel genauer beim Modellieren realer Netzwerke.

Aber weil ihre Kanten strengere, voneinander abhängige Muster bilden, sind sie auch viel schwerer zu analysieren. Es dauerte zusätzliche 20 Jahre, nachdem die Frage nach Hamiltonkreisen für Binomialgraphen beantwortet wurde, bis Mathematiker dasselbe für reguläre Graphen tun konnten.

Aber was ist, wenn man zufällige reguläre Graphen mit zufälligen Binomialgraphen approximieren kann? Wenn das möglich ist, können Mathematiker viele schwer zu beweisende Eigenschaften eines regulären Graphen aus dem passenden Binomialgraphen „kostenlos“ bekommen.

Anfang der 2000er zeigten Jeong Han Kim, damals bei Microsoft Research, und Van Ha Vu, damals an der University of California, San Diego, wie das geht, indem sie einen Graphen-Sandwich machten.

Die Idee, grob gesagt, war, ein einziges Rezept zu finden. Das ist ein Zufallsprozess, um einen Binomialgraphen und einen regulären Graphen gleichzeitig zu erstellen. Dieses Rezept muss nicht nur die richtigen Arten von Graphen erzeugen, sondern diese Graphen müssen auch auf die richtige Weise zusammenpassen. Wenn das gelingt, dann gelten die Ergebnisse über den Binomialgraphen, der relativ einfach zu analysieren ist, auch für den regulären Graphen.

In der Sandwich-Analogie ist das so, als würde man Dinge über eine der Brotscheiben beweisen und wissen, dass diese Ergebnisse auch für den Käse in der Mitte gelten.

Aber wie müssen diese Graphen genau zusammenpassen? Man muss ein Rezept entwickeln, das den Käse auf jede Brotscheibe getrennt schichtet.

Zuerst braucht man ein Rezept, das einen regulären Graphen liefert, der einen Binomialgraphen enthält. Das bedeutet, die Kanten des Binomialgraphen bilden eine Teilmenge der Kanten, die den regulären Graphen ausmachen. Wenn dieser Binomialgraph eine Eigenschaft hat, die wahrscheinlicher erscheint, wenn man Kanten hinzufügt, dann hat Ihr regulärer Graph auch diese Eigenschaft. Dies ist die untere Hälfte des Sandwiches von Kim und Vu.

Mark Belan/ Quanta Magazine

Ähnlich braucht man ein Rezept, das einen regulären Graphen liefert, der in einem Binomialgraphen enthalten ist. Wenn dieser größere Binomialgraph Eigenschaften hat, die wahrscheinlicher erscheinen, wenn man Kanten entfernt, dann muss Ihr regulärer Graph auch diese Eigenschaften haben. Dies ist die obere Hälfte Ihres Sandwiches.

Kim und Vu vermuteten, dass solange Sie