View source for Kahn–Kalai conjecture

{{Short description|Mathematical proposition}}
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 (mathematician)|Jeff Kahn]] and [[Gil Kalai]] in 2006.<ref name=":0">{{Cite web |date=2022-04-18 |title=Jinyoung Park and Huy Tuan Pham Prove the Kahn-Kalai Conjecture - IAS News |url=https://www.ias.edu/news/park-and-pham-prove-kahn-kalai-conjecture |access-date=2022-04-25 |website=Institute for Advanced Study |language=en}}</ref><ref>{{cite arXiv |last1=Kahn |first1=Jeff |last2=Kalai |first2=Gil |date=2006-04-02 |title=Thresholds and expectation thresholds |eprint=math/0603218 }}</ref> It was proven in a paper published in 2024.<ref name=pp24/>

== Background ==
This conjecture concerns the general problem of estimating when [[phase transition]]s occur in systems.<ref name=":0" /> For example, in a [[random network]] with <math>N</math> nodes, where each edge is included with probability <math>p</math>, it is unlikely for the graph to contain a [[Hamiltonian cycle]] if <math>p</math> is less than a threshold value <math>(\log N)/N</math>, but highly likely if <math>p</math> exceeds that threshold.<ref name=":1" />

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

== Proof ==
[[Jinyoung Park (mathematician)|Jinyoung Park]] and Huy Tuan Pham announced a proof of the conjecture in 2022; it was published in 2024.<ref name=":1">{{Cite web |last=Cepelewicz |first=Jordana |date=2022-04-25 |title=Elegant Six-Page Proof Reveals the Emergence of Random Structure |url=https://www.quantamagazine.org/elegant-six-page-proof-reveals-the-emergence-of-random-structure-20220425/ |access-date=2022-04-25 |website=Quanta Magazine |language=en}}</ref><ref name=pp24>{{cite journal
 | last1 = Park | first1 = Jinyoung
 | last2 = Pham | first2 = Huy Tuan
 | arxiv = 2203.17207
 | doi = 10.1090/jams/1028
 | issue = 1
 | journal = Journal of the American Mathematical Society
 | mr = 4654612
 | pages = 235–243
 | title = A proof of the Kahn-Kalai conjecture
 | volume = 37
 | year = 2024}}</ref>

== References ==
{{reflist}}

== See also ==
* [[Percolation theory]]

[[Category:Conjectures]]
[[Category:21st century in mathematics]]
[[Category:Statements in graph theory]]
[[Category:Statistical mechanics]]
[[Category:2006 in science]]


{{DEFAULTSORT:Kahn-Kalai conjecture}}