Jinyoung Park, Huy Tuan Pham: A proof of the Kahn-Kalai Conjecture


The threshold of an increasing property of a random set (or random graph) is the density at which a random set transitions from unlikely satisfying to likely satisfying the property. Thresholds for increasing properties of random structures are of central interest in probabilistic combinatorics and related areas. Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold. The Kahn-Kalai conjecture directly implies a number of difficult results in probabilistic combinatorics and random graph theory, such as Shamir’s problem on hypergraph matchings, or the threshold for containing a bounded degree spanning tree. We will discuss recent work that resolves the Kahn-Kalai conjecture. 



Based on 



Password Protected

This video is password-protected. Please verify with a password to unlock the content.