The Kahn-Kalai conjecture, also known as the expectation threshold conjecture, was proposed by Jeff Kahn and Gil Kalai in 2006 in the field of graph theory and statistical mechanics. It related the threshold at which a random graph property becomes likely to hold to a more easily computed expectation threshold. It was proven in a paper published in 2024, sometimes referred to since as the Park-Pham theorem.
Facts
StatementFor an increasing family of subsets F of a finite ground set, with l(F) the size of the largest minimal element of F, the Kahn-Kalai conjecture asserts that a universal constant K exists such that the ratio between the threshold and the expectation threshold of F is less than K times the logarithm of l(F). 1 Proposed Year Progress Toward ResolutionThe conjecture is proven. Jinyoung Park and Huy Tuan Pham announced a proof in 2022, which was published in 2024; the result is also known as the Park-Pham theorem. 1 Classification
Resolution Status Chronology
Resolved Year Prize Status
Prize Status (category) Connections
In Branch
Source Kahn-Kalai Conjecture (Wikipedia)
Sources
1. Kahn-Kalai Conjecture (Wikipedia)
Lead section
there is a universal constant K for which the ratio between the two is less than K log l(F)
Lead section, attribution
proposed by Jeff Kahn and Gil Kalai in 2006
History section
Jinyoung Park and Huy Tuan Pham announced a proof of the conjecture in 2022; it was published in 2024
In Branch: Graph Theory, Lead sentence
rk-Pham Theorem, was a conjecture in the field of graph theory and statistical mechanics, proposed by Jeff Kahn and Gil Kalai in 2
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.