Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any non-trivial 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.
This video is part of the Institute for Advanced Study‘s Members’ colloquium.
