Park e Pham resolveram a conjectura de Kahn-Kalai em uma prova de seis páginas por meio de coberturas

Grafos aleatórios adquirem propriedades como triângulos ou ciclos hamiltonianos de forma abrupta: abaixo de certa probabilidade a estrutura quase nunca aparece, logo acima dela quase sempre. Os limiares exatos são difíceis de calcular, então os matemáticos usam um limite inferior fácil, o limiar de expectativa; em 2006 Jeff Kahn e Gil Kalai conjecturaram que o limiar real nunca o excede em mais do que um fator logarítmico. A afirmação parecia forte demais até para seus autores, que passaram anos caçando contraexemplos, mas tornou-se um problema aberto central porque resolveria questões de limiar quase mecanicamente.

A rota aceita para a conjectura passava por uma versão mais fraca proposta por Michel Talagrand, que substitui o limiar de expectativa por uma variante fracionária. Kahn, Jinyoung Park e colegas provaram essa versão em 2021, importando técnicas do avanço dos girassóis de 2019 e uma noção chamada spread; o próprio Kahn disse que sempre pensou que provar essa equivalência era o único caminho para a conjectura completa. Enquanto isso, Park e Huy Tuan Pham trabalhavam em outro problema de Talagrand quando perceberam que suas ideias eram mais poderosas do que pareciam.

Em uma única noite em claro, em março de 2022, eles encontraram o argumento direto. Em vez do spread, que não oferece ponto de partida para a conjectura original, mudaram de perspectiva e reescreveram a afirmação em termos de coberturas: se é improvável que um conjunto aleatório contenha qualquer estrutura-alvo, então a família de estruturas tem uma cobertura pequena cuja contribuição para o limiar de expectativa é pequena. Eles construíram essa cobertura amostrando peça por peça e terminaram com um argumento de contagem, e publicaram o artigo de seis páginas uma semana depois, em 31 de março de 2022.

Os colegas reagiram com espanto: Kalai chamou-a de surpreendentemente simples e engenhosa, Jacob Fox chamou a prova de mágica, e David Conlon disse que ela atravessou diretamente o roteiro pressuposto. Como a conjectura é formulada sobre conjuntos abstratos, a prova resolve centenas de afirmações de limiar específicas de uma só vez e deixa uma técnica que outros esperam reutilizar. A Quanta relatou o resultado em 25 de abril de 2022, e Park e Pham começaram a aplicar o método à questão mais fina de quando a lacuna entre os limiares é menor do que o pior caso.

Reformular com coberturas e contá-las diretamente

As coberturas operam diretamente sobre o limiar de expectativa original: uma cobertura pequena das estruturas-alvo é uma contribuição pequena para a média ponderada, então nada precisou ser enfraquecido para um substituto fracionário.

Reescrever a afirmação de forma contrapositiva transformou uma garantia probabilística em uma tarefa de construção: construir uma cobertura pequena, o que a amostragem peça por peça podia realizar.

O argumento de contagem forneceu o empurrão que faltava, então a prova nunca precisou da equivalência entre spread e fracionário que o campo acreditava ser a única ponte.

Seis páginas significaram que toda a comunidade pôde ler e adotar o argumento de imediato, e é por isso que matemáticos seniores a chamaram de mágica, e não apenas correta.

Quando todos assumem que um desvio por uma versão mais fraca é a única rota, questione a suposição: mudar a forma como você representa o problema pode tornar o ataque direto curto

A dupla publicou A Proof of the Kahn-Kalai Conjecture no arXiv em 31 de março de 2022 (revisado em 13 de abril de 2023). A Quanta Magazine cobriu o caso em 25 de abril de 2022 como uma elegante prova de seis páginas da emergência de estrutura aleatória, e a história atraiu 589 pontos e 166 comentários no Hacker News em 26 de abril de 2022. Park e Pham então voltaram o método para a questão mais fina de quando a lacuna entre o limiar de expectativa e o limiar verdadeiro é menor do que o pior caso logarítmico, que o campo ainda precisava resolver caso a caso.