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]
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]
Jinyoung Park and Huy Tuan Pham announced a proof of the conjecture in 2022; it was published in 2024. [4] [3]
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]
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]
Jinyoung Park and Huy Tuan Pham announced a proof of the conjecture in 2022; it was published in 2024. [4] [3]