hen the mathematicians Jeff Kahn and Gil Kalai first posed their “expectation threshold” conjecture in 2006, they didn’t believe it themselves. Their claim — a broad assertion about mathematical objects called random graphs — seemed too strong, too all-encompassing, too bold to possibly be true. It felt more like wishful thinking than a reflection of mathematical truth. Even so, no one could prove it false, and it quickly became one of the most important open problems in the field.
Now, more than 15 years later, a pair of young mathematicians 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 of the conjecture.