Park and Pham settled the Kahn-Kalai conjecture in a six-page proof via covers

Random graphs acquire properties like triangles or Hamiltonian cycles abruptly: below some probability the structure almost never appears, just above it almost always. Exact thresholds are hard to compute, so mathematicians use an easy lower bound, the expectation threshold; in 2006 Jeff Kahn and Gil Kalai conjectured the real threshold never exceeds it by more than a logarithmic factor. The claim seemed too strong even to its authors, who spent years hunting counterexamples, yet it became a central open problem because it would settle threshold questions almost mechanically.

The accepted route to the conjecture ran through a weaker version proposed by Michel Talagrand, which replaces the expectation threshold with a fractional variant. Kahn, Jinyoung Park and colleagues proved that version in 2021, importing techniques from the 2019 sunflower breakthrough and a notion called spread; Kahn himself said he always thought proving that equivalence was the only way to the full conjecture. Meanwhile Park and Huy Tuan Pham were working on another Talagrand problem when they realized their ideas were more powerful than they looked.

Over a single sleepless night in March 2022 they found the direct argument. Instead of spread, which gives no starting point for the original conjecture, they switched perspective and rewrote the claim in terms of covers: if a random set is unlikely to contain any target structure, then the family of structures has a small cover whose contribution to the expectation threshold is small. They constructed that cover by sampling piece by piece and finished with a counting argument, and posted the six-page paper a week later, on 31 March 2022.

Colleagues reacted with astonishment: Kalai called it strikingly simple and ingenious, Jacob Fox called the proof magical, and David Conlon said it punched straight through the assumed roadmap. Because the conjecture is written over abstract sets, the proof settles hundreds of specific threshold statements at once and leaves a technique others expect to reuse. Quanta reported the result on 25 April 2022, and Park and Pham began applying the method to the finer question of when the gap between thresholds is smaller than the worst case.

Reformulate with covers and count them directly

Covers operate directly on the original expectation threshold: a small cover of target structures is a small contribution to the weighted average, so nothing needed weakening to a fractional stand-in.

Rewriting the claim contrapositively turned a probability guarantee into a construction task: build a small cover, which piece-by-piece sampling could accomplish.

The counting argument supplied the missing push, so the proof never needed the spread-to-fractional equivalence that the field believed was the only bridge.

Six pages meant the whole community could read and adopt the argument at once, which is why senior mathematicians called it magical rather than merely correct.

When everyone assumes a detour through a weaker version is the only route, question the assumption: changing how you represent the problem can make the direct attack short

The pair posted A Proof of the Kahn-Kalai Conjecture to arXiv on 31 March 2022 (revised 13 April 2023). Quanta Magazine covered it on 25 April 2022 as an elegant six-page proof of the emergence of random structure, and the story drew 589 points and 166 comments on Hacker News on 26 April 2022. Park and Pham then turned the method on the finer question of when the gap between expectation threshold and true threshold is smaller than the logarithmic worst case, which the field still had to work out case by case.