Park et Pham ont résolu la conjecture de Kahn-Kalai en une preuve de six pages via les couvertures

Les graphes aléatoires acquièrent des propriétés comme les triangles ou les cycles hamiltoniens de façon abrupte : en dessous d'une certaine probabilité, la structure n'apparaît presque jamais ; juste au-dessus, elle apparaît presque toujours. Les seuils exacts sont difficiles à calculer, aussi les mathématiciens utilisent-ils une borne inférieure facile, le seuil d'espérance ; en 2006, Jeff Kahn et Gil Kalai ont conjecturé que le seuil réel ne dépasse jamais celui-ci de plus d'un facteur logarithmique. L'affirmation semblait trop forte même à ses auteurs, qui ont passé des années à chercher des contre-exemples, mais elle est devenue un problème ouvert central car elle trancherait les questions de seuil de manière presque mécanique.

La voie acceptée vers la conjecture passait par une version plus faible proposée par Michel Talagrand, qui remplace le seuil d'espérance par une variante fractionnaire. Kahn, Jinyoung Park et des collègues ont prouvé cette version en 2021, important des techniques de la percée de 2019 sur les tournesols et une notion appelée dispersion ; Kahn lui-même a déclaré qu'il avait toujours pensé que prouver cette équivalence était le seul moyen d'atteindre la conjecture complète. Pendant ce temps, Park et Huy Tuan Pham travaillaient sur un autre problème de Talagrand lorsqu'ils ont réalisé que leurs idées étaient plus puissantes qu'elles n'en avaient l'air.

Au cours d'une seule nuit blanche en mars 2022, ils ont trouvé l'argument direct. Au lieu de la dispersion, qui ne fournit aucun point de départ pour la conjecture originale, ils ont changé de perspective et réécrit l'affirmation en termes de couvertures : si un ensemble aléatoire a peu de chances de contenir une structure cible, alors la famille de structures possède une petite couverture dont la contribution au seuil d'espérance est faible. Ils ont construit cette couverture en échantillonnant pièce par pièce et ont terminé par un argument de comptage, puis ont publié l'article de six pages une semaine plus tard, le 31 mars 2022.

Les collègues ont réagi avec étonnement : Kalai l'a qualifiée de remarquablement simple et ingénieuse, Jacob Fox a qualifié la preuve de magique, et David Conlon a dit qu'elle transperçait directement la feuille de route supposée. Comme la conjecture est formulée sur des ensembles abstraits, la preuve tranche des centaines d'énoncés de seuil spécifiques à la fois et laisse une technique que d'autres comptent réutiliser. Quanta a rapporté le résultat le 25 avril 2022, et Park et Pham ont commencé à appliquer la méthode à la question plus fine de savoir quand l'écart entre les seuils est plus petit que le pire cas.

Reformuler avec des couvertures et les compter directement

Les couvertures opèrent directement sur le seuil d'espérance original : une petite couverture des structures cibles est une petite contribution à la moyenne pondérée, donc rien n'avait besoin d'être affaibli en un substitut fractionnaire.

Réécrire l'affirmation par contraposition a transformé une garantie probabiliste en une tâche de construction : construire une petite couverture, ce que l'échantillonnage pièce par pièce pouvait accomplir.

L'argument de comptage a fourni l'impulsion manquante, de sorte que la preuve n'a jamais eu besoin de l'équivalence dispersion-fractionnaire que le domaine croyait être le seul pont.

Six pages signifiaient que toute la communauté pouvait lire et adopter l'argument d'un coup, ce qui explique pourquoi des mathématiciens chevronnés l'ont qualifiée de magique plutôt que simplement correcte.

Quand tout le monde suppose qu'un détour par une version plus faible est la seule voie, remettez l'hypothèse en question : changer la façon de représenter le problème peut rendre l'attaque directe courte

Le duo a publié A Proof of the Kahn-Kalai Conjecture sur arXiv le 31 mars 2022 (révisé le 13 avril 2023). Quanta Magazine en a rendu compte le 25 avril 2022 comme d'une élégante preuve de six pages de l'émergence de la structure aléatoire, et l'histoire a recueilli 589 points et 166 commentaires sur Hacker News le 26 avril 2022. Park et Pham ont ensuite appliqué la méthode à la question plus fine de savoir quand l'écart entre le seuil d'espérance et le seuil réel est plus petit que le pire cas logarithmique, que le domaine devait encore traiter au cas par cas.