Elegant Six-Page Proof Reveals the Emergence of Random Structure
A pair of young mathematicians have astonished their colleagues with a full proof of the Kahn-Kalai conjecture - a sweeping statement about how structure emerges in random sets and graphs.
Jeff Kahn and Gil Kalai first posed the "expectation threshold" conjecture in 2006
No one could prove it false, and it became one of the most important open problems in the field
Now, more than 15 years later, a pair of researchers at Stanford University have done what Kahn and Kalai thought borderline impossible
In a surprisingly short preprint posted online just a few weeks ago, Jinyoung Park and Huy Tuan Pham have provided a complete proof
The result automatically proves hundreds of more specific statements that would each be very difficult to prove alone
Freezing a Graph
The Kahn-Kalai conjecture is very broad - it's written in the abstract language of sets and their elements - but it can be understood by considering a simple case of a graph: a set of points, or vertices, connected by lines, or edges.
To make a random graph, take a biased coin and flip it once for a given pair of vertices. If the coin lands on heads, connect those vertices with an edge; if it lands on tails, don't. Repeat this process for every possible pair of edges.
If the probability of the coin turning up heads is low, edges will be rare, and properties like Hamiltonian cycles are not likely to arise. But if you dial up the probability, something strange happens: the emergence of a particular property suddenly becomes extremely likely as more edges get added to the graph.
The Sunflower Path
The methods that would eventually lead to the new proof of the Kahn-Kalai conjecture began with a breakthrough on a seemingly unrelated problem.
In 2019, Lovett was part of a team that came very close to a full solution of the sunflower problem.
The weaker version of the conjecture, formulated by the French mathematician Michel Talagrand, replaced Kahn Kalai's expectation threshold with a "fractional" expectation threshold - essentially a different way of taking a weighted average.
This suggested that the two conjectures might be more or less the same - that the values of the fractional and original expectation thresholds were basically equivalent.
A Surprise Approach
Park and Pham rewrote the Kahn-Kalai conjecture in a way that let them make use of covers
The original conjecture puts constraints on what the probability of a weighted coin landing on heads should be in order to guarantee that a random graph or set contains some property
If such a property is not likely to emerge, then the probability assigned to the weighted coin is lower than the expectation threshold multiplied by a logarithmic factor
To prove this, they needed to show that if a random set is unlikely to contain one target structure, there must exist a small cover for all such target structures
