Park y Pham resolvieron la conjetura de Kahn-Kalai en una prueba de seis páginas mediante cubiertas

Los grafos aleatorios adquieren propiedades como triángulos o ciclos hamiltonianos de forma abrupta: por debajo de cierta probabilidad la estructura casi nunca aparece, justo por encima casi siempre. Los umbrales exactos son difíciles de calcular, por lo que los matemáticos usan una cota inferior fácil, el umbral de expectativa; en 2006 Jeff Kahn y Gil Kalai conjeturaron que el umbral real nunca lo supera en más de un factor logarítmico. La afirmación parecía demasiado fuerte incluso para sus autores, que pasaron años buscando contraejemplos, pero se convirtió en un problema abierto central porque resolvería las cuestiones de umbral casi mecánicamente.

La ruta aceptada hacia la conjetura pasaba por una versión más débil propuesta por Michel Talagrand, que reemplaza el umbral de expectativa por una variante fraccionaria. Kahn, Jinyoung Park y colegas probaron esa versión en 2021, importando técnicas del avance del girasol de 2019 y una noción llamada dispersión; el propio Kahn dijo que siempre pensó que probar esa equivalencia era la única vía hacia la conjetura completa. Mientras tanto, Park y Huy Tuan Pham trabajaban en otro problema de Talagrand cuando se dieron cuenta de que sus ideas eran más poderosas de lo que parecían.

En una sola noche de insomnio en marzo de 2022 encontraron el argumento directo. En lugar de la dispersión, que no da un punto de partida para la conjetura original, cambiaron de perspectiva y reescribieron la afirmación en términos de cubiertas: si es improbable que un conjunto aleatorio contenga alguna estructura objetivo, entonces la familia de estructuras tiene una cubierta pequeña cuya contribución al umbral de expectativa es pequeña. Construyeron esa cubierta muestreando pieza por pieza y terminaron con un argumento de conteo, y publicaron el artículo de seis páginas una semana después, el 31 de marzo de 2022.

Los colegas reaccionaron con asombro: Kalai lo calificó de llamativamente simple e ingenioso, Jacob Fox dijo que la prueba era mágica, y David Conlon afirmó que atravesaba directamente la hoja de ruta asumida. Como la conjetura está formulada sobre conjuntos abstractos, la prueba resuelve cientos de afirmaciones de umbral específicas a la vez y deja una técnica que otros esperan reutilizar. Quanta informó del resultado el 25 de abril de 2022, y Park y Pham comenzaron a aplicar el método a la cuestión más fina de cuándo la brecha entre umbrales es menor que el peor caso.

Reformular con cubiertas y contarlas directamente

Las cubiertas operan directamente sobre el umbral de expectativa original: una cubierta pequeña de estructuras objetivo es una contribución pequeña al promedio ponderado, así que no hacía falta debilitar nada a un sustituto fraccionario.

Reescribir la afirmación de forma contrapositiva convirtió una garantía probabilística en una tarea de construcción: construir una cubierta pequeña, algo que el muestreo pieza por pieza podía lograr.

El argumento de conteo aportó el empujón que faltaba, así que la prueba nunca necesitó la equivalencia entre dispersión y fraccionario que el campo creía que era el único puente.

Seis páginas significaron que toda la comunidad pudo leer y adoptar el argumento de inmediato, y por eso matemáticos veteranos lo llamaron mágico y no meramente correcto.

Cuando todos asumen que un rodeo por una versión más débil es la única ruta, cuestiona esa suposición: cambiar cómo representas el problema puede hacer que el ataque directo sea breve

La pareja publicó A Proof of the Kahn-Kalai Conjecture en arXiv el 31 de marzo de 2022 (revisado el 13 de abril de 2023). Quanta Magazine lo cubrió el 25 de abril de 2022 como una elegante prueba de seis páginas de la aparición de estructura aleatoria, y la historia atrajo 589 puntos y 166 comentarios en Hacker News el 26 de abril de 2022. Park y Pham dirigieron entonces el método a la cuestión más fina de cuándo la brecha entre el umbral de expectativa y el umbral verdadero es menor que el peor caso logarítmico, que el campo todavía tenía que resolver caso por caso.