Kahn–Kalai conjecture

The Kahn–Kalai conjecture, also known as the expectation threshold conjecture or more recently the Park-Pham Theorem, was a conjecture in the field of graph theory and statistical mechanics, proposed by Jeff Kahn and Gil Kalai in 2006.[1][2] It was proven in a paper published in 2024.[3]

Background

edit

This conjecture concerns the general problem of estimating when phase transitions occur in systems.[1] 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.[4]

Threshold values are often difficult to calculate, but a lower bound for the threshold, the "expectation threshold", is generally easier to calculate.[1] 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.[3]

Proof

edit

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

References

edit
  1. ^ a b c "Jinyoung Park and Huy Tuan Pham Prove the Kahn-Kalai Conjecture - IAS News". Institute for Advanced Study. 2022-04-18. Retrieved 2022-04-25.
  2. ^ Kahn, Jeff; Kalai, Gil (2006-04-02). "Thresholds and expectation thresholds". arXiv:math/0603218.
  3. ^ a b c Park, Jinyoung; Pham, Huy Tuan (2024). "A proof of the Kahn-Kalai conjecture". Journal of the American Mathematical Society. 37 (1): 235–243. arXiv:2203.17207. doi:10.1090/jams/1028. MR 4654612.
  4. ^ a b Cepelewicz, Jordana (2022-04-25). "Elegant Six-Page Proof Reveals the Emergence of Random Structure". Quanta Magazine. Retrieved 2022-04-25.

See also

edit