Thresholds and expectation thresholds

OpenAI's proofs (2026) of four conjectures on thresholds: the second Kahn–Kalai conjecture (containment thresholds of graphs within a logarithm of the expectation threshold), Talagrand's conjecture that integral and fractional expectation thresholds agree up to a constant, Talagrand's discrete convexity conjecture, and the Ascoli–He–Park–Talagrand decomposition of graphs into pieces that appear at a constant multiple of the integral expectation threshold. Planted resampling, tree covering, multiscale selectors, biased Fourier weights and embedding arguments, all proved in the course.

Eight lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. Random sets, covers and expectation thresholds
2. Resampling a spread family
3. Covering a probability tree
4. The second Kahn–Kalai conjecture
5. Integral and fractional expectation thresholds
6. The discrete convexity conjecture
7. Embedding sparse graphs in random graphs
8. Graph decompositions at the expectation threshold

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• Contracting averages and sparse assignments (Amenability and unitarizability)
• Biased Fourier analysis and hypercontractivity (Sharp thresholds for graph properties)
• Concentration and the discrete cube (The Gaussian moat problem)
• Finite probability: independence, conditional probability, expectation, Markov's and Chebyshev's inequalities.
• Graphs, subgraphs and isomorphisms.