The Kahn–Kalai conjecture, also known as the expectation threshold conjecture, is a

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...

in the field of graph theory and

statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...

, 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

N

nodes, where each edge is included with probability

p

, it is unlikely for the graph to contain a Hamiltonian cycle if

p

is less than a threshold value

(\log N)/N

, but highly likely if

p

exceeds that threshold. 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 A physical constant, sometimes fundamental physical constant or universal constant, is a physical quantity that is generally believed to be both universal in nature and have constant value in time. It is contrasted with a mathematical constant ...

K

for which the ratio between the two is less than

K \log

where

\ell(\mathcal)

is the size of a largest minimal element of an increasing family

\mathcal

of subsets of a power set.

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.

Background

Proof

References

See also