Conjectura de Kahn-Kalai

A conjectura de Kahn–Kalai, também conhecida como conjectura do limiar de expectativa, é uma conjectura no campo da teoria dos grafos e da mecânica estatística, proposta por Jeff Kahn e Gil Kalai em 2006.

Fundo

Essa conjectura diz respeito ao problema geral de estimar quando ocorrem transições de fase em sistemas. Por exemplo, em uma rede aleatória com $N$ nós, onde cada aresta é incluída com probabilidade $p$, é improvável que o gráfico contenha um caminho hamiltoniano se $p$ é menor que um valor limite $(\log N)/N$, mas altamente provável se $p$ excede esse limite.

Os valores de limite geralmente são difíceis de calcular, mas um limite inferior para o limite, o "limite de expectativa", geralmente é mais fácil de calcular. A conjectura Kahn-Kalai é que os dois valores são geralmente próximos de uma forma definida com precisão, ou seja, que existe uma constante universal $K$ para o qual a razão entre os dois é menor do que $K\log \ell (ℱ)$ onde $\ell (ℱ)$ é o tamanho do maior elemento mínimo de uma família crescente $ℱ$ de subconjuntos de um conjunto de potência.

Prova

Em 2022, Jinyoung Park e Huy Tuan Pham lançaram um artigo contendo uma proposta de prova da conjectura. A prova foi elogiada por sua elegância e concisão.