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.

Background

This conjecture concerns the general problem of estimating when phase transitions occur in systems. For example, in a random network with nodes, where each edge is included with probability , it is unlikely for the graph to contain a Hamiltonian cycle if is less than a threshold value , but highly likely if exceeds that threshold.

Kahn–Kalai conjecture

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 for which the ratio between the two is less than where is the size of a largest minimal element of an increasing family of subsets of a power set.

Kahn–Kalai conjecture

Proof

In 2022, Jinyoung Park and Huy Tuan Pham released a preprint containing a proposed proof of the conjecture. The proof has been praised for its elegance and conciseness.

Kahn–Kalai conjecture

References

See also

Percolation theory

Conjectures

2000s in mathematics

2020s in mathematics

Graph theory

Statistical mechanics