Kahn–Kalai conjecture

Short description: Mathematical proposition

The Kahn–Kalai conjecture, also known as the expectation threshold conjecture, is a conjecture in the field of graph theory and statistical mechanics, proposed by Jeff Kahn and Gil Kalai in 2006. It was proven in a paper published in 2024.

Background

This conjecture concerns the general problem of estimating when phase transitions occur in systems. For example, in a random network with [math]\displaystyle{ N }[/math] nodes, where each edge is included with probability [math]\displaystyle{ p }[/math], it is unlikely for the graph to contain a Hamiltonian cycle if [math]\displaystyle{ p }[/math] is less than a threshold value [math]\displaystyle{ (\log N)/N }[/math], but highly likely if [math]\displaystyle{ p }[/math] exceeds that threshold.

Threshold values are often difficult to calculate, but a lower bound for the threshold, the "expectation threshold", is generally easier to calculate. The Kahn–Kalai conjecture is that the two values are generally close together in a precisely defined way, namely that there is a universal constant [math]\displaystyle{ K }[/math] for which the ratio between the two is less than [math]\displaystyle{ K \log{\ell(\mathcal{F})} }[/math] where [math]\displaystyle{ \ell(\mathcal{F}) }[/math] is the size of a largest minimal element of an increasing family [math]\displaystyle{ \mathcal{F} }[/math] of subsets of a power set.

Proof

Jinyoung Park and Huy Tuan Pham announced a proof of the conjecture in 2022; it was published in 2024.

See also

• Percolation theory