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ós, onde cada aresta é incluída com probabilidade , é improvável que o gráfico contenha um caminho hamiltoniano se é menor que um valor limite , mas altamente provável se 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 para o qual a razão entre os dois é menor do que onde é 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.
Referências
Categoria:Mecânica estatística Categoria:Teoria dos grafos Categoria:Conjecturas