Im Jahr 2004 vermuteten die Mathematiker Jeong Han Kim und Van Ha Vu, dass jeder hinreichend große zufällige reguläre Graph — ein Graph, bei dem jede Ecke dieselbe Anzahl Kanten hat — zwischen zwei zufälligen binomischen Graphen aus demselben Zufallsprozess eingewickelt werden kann. Wäre das wahr, hieße das, dass Eigenschaften, die für die einfachen binomischen Graphen bewiesen wurden, automatisch für die schwierigeren regulären Graphen gelten — und man übertrüge Jahrzehnte mathematischer Ergebnisse mit einem Schlag.
Die Vermutung wurde nun vollständig bewiesen von Richard Montgomery der University of Warwick sowie Natalie Behague und Daniel Iľkovič. Ihr Beweis konstruiert das Sandwich, indem er beide Graphen Kante für Kante im Tandem aufbaut, mit einer sorgfältig gewichteten Zwei-Münzen-Prozedur: Eine Münze entscheidet, ob dem binomischen Graphen eine Kante hinzugefügt wird, eine zweite, dynamisch gewichtete Münze steuert die Einschränkung des regulären Graphen, dass jede Ecke am Ende dieselbe Gradzahl haben muss.
Die untere Hälfte des Sandwiches — dass ein regulärer Graph immer einen binomischen Untergeometrie enthalten kann — war bereits früher bewiesen worden. Die obere Hälfte, dass ein regulärer Graph immer in einem größeren binomischen Graphen enthalten sein kann, war das fehlende Stück, das der neue Beweis durch Umkehrung des gesamten Konstruktionsprozesses löst.
Das Ergebnis ist das, was Mathematiker Gil Kalai von der Hebrew University of Jerusalem als Metatheorem bezeichnete: Jede Eigenschaft, die mit hoher Wahrscheinlichkeit für zufällige binomische Graphen gilt, gilt nun automatisch für zufällige reguläre Graphen, vorausgesetzt, der Graph ist groß genug. Das bedeutet, dass Dutzende zuvor separater Ergebnisse nun unter einem einzigen Rahmen vereint werden können.
Zufällige reguläre Graphen werden häufig zur Modellierung realer Netzwerke verwendet — von sozialen Verbindungen über das Internet bis hin zu neuralen Pfaden — weil ihre einheitliche Kantenstruktur Einschränkungen erfasst, die binomische Modelle nicht abbilden. Der Sandwich-Beweis eröffnet den Weg, die umfangreiche bestehende Literatur zu binomischen Graphen auf diese realistischeren Modelle anzuwenden, und die neuen Beweistechniken selbst ermöglichen möglicherweise weitere Ergebnisse über Netzwerkstruktur.
Die Mathematiker hoffen, die Sandwich-Idee in Zukunft auf noch komplexere geschichtete Konstruktionen auszuweiten.
