Park und Pham bewiesen die Kahn-Kalai-Vermutung in einem sechsseitigen Beweis über Überdeckungen

Zufällige Graphen erwerben Eigenschaften wie Dreiecke oder Hamiltonkreise abrupt: unterhalb einer bestimmten Wahrscheinlichkeit tritt die Struktur fast nie auf, knapp darüber fast immer. Exakte Schwellenwerte sind schwer zu berechnen, daher verwenden Mathematiker eine leicht zu bestimmende untere Schranke, den Erwartungsschwellenwert; im Jahr 2006 vermuteten Jeff Kahn und Gil Kalai, dass der tatsächliche Schwellenwert diesen nie um mehr als einen logarithmischen Faktor übersteigt. Die Behauptung erschien selbst ihren Urhebern zu stark, die jahrelang nach Gegenbeispielen suchten, doch sie wurde zu einem zentralen offenen Problem, weil sie Schwellenwertfragen nahezu mechanisch klären würde.

Der anerkannte Weg zur Vermutung führte über eine schwächere Version, die Michel Talagrand vorgeschlagen hatte und die den Erwartungsschwellenwert durch eine fraktionale Variante ersetzt. Kahn, Jinyoung Park und Kollegen bewiesen diese Version im Jahr 2021 und griffen dabei Techniken aus dem Durchbruch von 2019 über Sonnenblumen sowie einen Begriff namens Spread auf; Kahn selbst sagte, er habe immer geglaubt, der Beweis dieser Äquivalenz sei der einzige Weg zur vollständigen Vermutung. Währenddessen arbeiteten Park und Huy Tuan Pham an einem anderen Problem von Talagrand, als ihnen klar wurde, dass ihre Ideen mächtiger waren, als sie aussahen.

In einer einzigen schlaflosen Nacht im März 2022 fanden sie das direkte Argument. Statt Spread, das keinen Ausgangspunkt für die ursprüngliche Vermutung liefert, wechselten sie die Perspektive und formulierten die Behauptung in Begriffen von Überdeckungen um: Wenn eine zufällige Menge unwahrscheinlich irgendeine Zielstruktur enthält, dann besitzt die Familie der Strukturen eine kleine Überdeckung, deren Beitrag zum Erwartungsschwellenwert klein ist. Sie konstruierten diese Überdeckung durch stückweises Sampling und schlossen mit einem Zählargument ab, und veröffentlichten die sechsseitige Arbeit eine Woche später, am 31. März 2022.

Kollegen reagierten mit Erstaunen: Kalai nannte sie verblüffend einfach und genial, Jacob Fox nannte den Beweis magisch, und David Conlon sagte, er habe die angenommene Roadmap geradewegs durchstoßen. Da die Vermutung über abstrakte Mengen formuliert ist, klärt der Beweis Hunderte spezifischer Schwellenwertaussagen auf einmal und hinterlässt eine Technik, die andere wiederverwenden wollen. Quanta berichtete am 25. April 2022 über das Ergebnis, und Park und Pham begannen, die Methode auf die feinere Frage anzuwenden, wann die Lücke zwischen den Schwellenwerten kleiner ist als der schlimmste Fall.

Mit Überdeckungen umformulieren und diese direkt zählen

Überdeckungen wirken direkt auf den ursprünglichen Erwartungsschwellenwert: Eine kleine Überdeckung der Zielstrukturen ist ein kleiner Beitrag zum gewichteten Mittel, sodass nichts zu einem fraktionalen Ersatz abgeschwächt werden musste.

Die kontrapositive Umformulierung der Behauptung verwandelte eine Wahrscheinlichkeitsgarantie in eine Konstruktionsaufgabe: eine kleine Überdeckung bauen, was stückweises Sampling leisten konnte.

Das Zählargument lieferte den fehlenden Anstoß, sodass der Beweis nie die Spread-zu-fraktional-Äquivalenz benötigte, die das Feld für die einzige Brücke hielt.

Sechs Seiten bedeuteten, dass die gesamte Gemeinschaft das Argument sofort lesen und übernehmen konnte, weshalb leitende Mathematiker es magisch statt bloß korrekt nannten.

Wenn alle annehmen, ein Umweg über eine schwächere Version sei der einzige Weg, die Annahme hinterfragen: Die Art, wie man das Problem darstellt, zu ändern, kann den direkten Angriff kurz machen

Das Paar veröffentlichte A Proof of the Kahn-Kalai Conjecture am 31. März 2022 auf arXiv (überarbeitet am 13. April 2023). Quanta Magazine berichtete am 25. April 2022 darüber als eleganten sechsseitigen Beweis für die Entstehung zufälliger Struktur, und die Geschichte erzielte am 26. April 2022 auf Hacker News 589 Punkte und 166 Kommentare. Park und Pham wandten die Methode anschließend auf die feinere Frage an, wann die Lücke zwischen Erwartungsschwellenwert und tatsächlichem Schwellenwert kleiner ist als der logarithmische schlimmste Fall, was das Feld noch Fall für Fall ausarbeiten musste.