Kahn–Kalai conjecture — threshold vs. expectation-threshold for monotone properties

Statement

Let $X$ be a finite set and $\mathcal F\subseteq 2^X$ an increasing (upward-closed, "monotone") family. Let $\mu_p$ be the product measure putting each element of $X$ into a random subset independently with probability $p$. By monotonicity, $\mu_p(\mathcal F)$ is nondecreasing in $p$, so there is a well-defined threshold \[ p_c(\mathcal F) := \{p : \mu_p(\mathcal F) = 1/2\}. \]

Call $\mathcal F$ $p$-small if there is a family of "seed" sets $\mathcal G\subseteq 2^X$ such that every member of $\mathcal F$ contains some $S\in\mathcal G$ (i.e. $\mathcal F\subseteq\langle\mathcal G\rangle$) and $\sum_{S\in\mathcal G}p^{|S|}\le 1/2$. The expectation-threshold $q(\mathcal F)$ is the largest $p$ for which $\mathcal F$ is $p$-small. This is a trivial, purely combinatorial first-moment/union-bound quantity — always easy to *estimate* by hand — and always $q(\mathcal F)\le p_c(\mathcal F)$ (arxiv.org/abs/2203.17207, ar5iv full-text fetch, §1 definitions).

Let $\ell(\mathcal F) := \max(2,\ \text{size of the largest minimal member of } \mathcal F)$.

Kahn–Kalai conjecture (J. Kahn, G. Kalai, "Thresholds and expectation thresholds," Combin. Probab. Comput. 16 (2007)): there is a universal constant $K$ such that for every nontrivial increasing $\mathcal F\subseteq 2^X$, \[ p_c(\mathcal F) \le K\, q(\mathcal F)\, \log \ell(\mathcal F). \]

I.e. the cheap, purely combinatorial lower bound $q(\mathcal F)$ is *never* off from the true (often analytically hard) threshold $p_c(\mathcal F)$ by more than a universal $\log\ell$ factor. Kahn and Kalai themselves doubted the conjecture at first — Park–Pham's paper records that Kahn–Kalai wrote it "would probably be more sensible to conjecture" the opposite (arxiv.org/abs/2203.17207, ar5iv fetch, introduction).

Facts

- Origin: Kahn & Kalai 2006/2007, Combin. Probab. Comput. 16. Motivated by explaining why so many random-graph/hypergraph thresholds (Hamiltonicity, perfect matchings, $K_r$-factors, spanning trees, etc.) sit essentially at the naive first-moment estimate, up to a $\log n$-type factor. - Weaker fractional relaxation conjectured by M. Talagrand (convexity work from 1995; the fractional-threshold form appears in his 2010 STOC paper, per gilkalai.wordpress.com, fetched): replace the 0/1 seed collection $\mathcal G$ with a fractional/weighted cover, giving a possibly-larger, more tractable quantity $q_f(\mathcal F)\ge q(\mathcal F)$. - Fractional case proved first: Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park, "Thresholds versus fractional expectation-thresholds," arXiv:1910.13433, Annals of Math. 194 (2021): $p_c(\mathcal F) = O(q_f(\mathcal F)\log\ell(\mathcal F))$. This built directly on the spread-family machinery of Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang's near-resolution of the Erdős–Ko–Rado sunflower conjecture (arXiv:1908.08483, 2019/2020): a family is $R$-spread if no fixed set is contained in more than an $R^{-|S|}$-fraction of its members, and spread families are shown to contain a small, cheap "cover." - Full (integral, non-fractional) conjecture proved by Jinyoung Park and Huy Tuan Pham: "A Proof of the Kahn-Kalai Conjecture," arXiv:2203.17207 (submitted 31 Mar 2022); also FOCS 2022; journal version *Journal of the American Mathematical Society* 37(1):235–243 (2024). (Distinct from Park–Pham's separate *Annals of Mathematics* 199 (2024) paper resolving a related Talagrand selector-process conjecture — not to be conflated.) - Theorem 1.1 (Park–Pham, per ar5iv full-text fetch): there is a universal constant $K$ such that $p_c(\mathcal F)\le K\,q(\mathcal F)\,\log\ell(\mathcal F)$ for every nontrivial increasing $\mathcal F\subseteq 2^X$ — the full conjecture, not just the fractional relaxation. - The proof is celebrated for being extremely short (~6 pages) and elementary — Quanta Magazine's headline: "Elegant Six-Page Proof Reveals the Emergence of Random Structure" (quantamagazine.org, 25 Apr 2022, fetched). - Talagrand's own conjecture that $q(\mathcal F)$ and $q_f(\mathcal F)$ are always comparable (which would make the fractional and integral theorems equivalent) remains open — Park–Pham's proof succeeds without resolving it, by attacking the integral quantity directly (ar5iv fetch, "Conjecture 1.3" note). - Immediate downstream impact: recovers or matches, as a single black-box corollary, sharp/near-sharp thresholds for a huge swath of classical random-graph/hypergraph properties from a cheap first-moment calculation — work that previously needed bespoke second-moment or absorption arguments per problem. - Park was a postdoc (later Stanford faculty), Pham a Stanford PhD student at the time (mathematics.stanford.edu/news, ias.edu/news, fetched). - Follow-up simplifications exist, e.g. arXiv:2303.02144 ("A short proof of Kahn-Kalai conjecture") and a SIAM J. Discrete Math. paper on a "nonuniform" Kahn–Kalai variant (epubs.siam.org/doi/abs/10.1137/23M1587075) — found via search, not read in full, flagged as unverified beyond title/venue.

Solution

Answer: the conjecture is TRUE. $p_c(\mathcal F) = O(q(\mathcal F)\log\ell(\mathcal F))$ for every nontrivial increasing family $\mathcal F$ on a finite ground set (Park & Pham, 2022).

The transferable technique — turn a threshold question into a cheap covering-design problem via "minimum fragments" (a streamlined descendant of the sunflower spread-family method):

1. Reformulate probability as combinatorics. By the definition of $q(\mathcal F)$, proving $p_c(\mathcal F)\le K q(\mathcal F)\log\ell(\mathcal F)$ reduces to *exhibiting* a cheap seed/cover family $\mathcal G$ — with $\mathcal F\subseteq\langle\mathcal G\rangle$ and $\sum_{S\in\mathcal G}p^{|S|}\le 1/2$ — at $p=K q(\mathcal F)\log\ell(\mathcal F)$. A hard analytic/probabilistic threshold statement is converted into a purely combinatorial covering-design construction over the hypergraph $\mathcal H$ of minimal members of $\mathcal F$.

2. Iterative random-greedy construction. Repeatedly sample a random subset $W\subseteq X$ of size $\approx Lpn$. Split the not-yet-covered edges of $\mathcal H$ by the size of their minimum fragment $T(S,W)$: the smallest set $S'\setminus W$ ranging over $S'\in\mathcal H$ with $S'\subseteq W\cup S$. Edges whose minimum fragment is large (relative to $\ell$) get folded directly into the cover; edges with small fragments are passed to the next round on the reduced ground set $X\setminus W$. The key technical bound (Park–Pham's "Lemma 2.1", ar5iv fetch) shows the expected cost of the cover produced at each round, $\mathbb E\big[\sum_{U}p^{|U|}\big]$, is exponentially small in $L$; after $O(\log\ell)$ rounds the accumulated cover is cheap enough to certify $p$-smallness.

3. Why it beats the prior "spread" framework. The ALWZ/Rao/FKNP line needed to define $R$-spread families and case-split into "very spread" vs. "not spread" regimes, with delicate bookkeeping to avoid pathological families. Park–Pham's single minimum-fragment statistic subsumes that case split — it is why the proof collapses to ~6 pages, and (more importantly) why it can attack the full *integral* $q(\mathcal F)$ directly rather than needing Talagrand's fractional relaxation $q_f(\mathcal F)$ as an intermediate stepping-stone (the route every earlier attempt, including FKNP, was forced to take).

4. Portable takeaway. Whenever a problem reduces to "does a $p$-random object avoid every member of a monotone family," this technique supplies a generic, black-box reduction: (a) compute the cheap first-moment expectation-threshold $q(\mathcal F)$, then (b) pay only a universal, structure-independent $O(\log\ell)$ multiplicative penalty to get the true threshold — no per-problem second-moment or absorption argument needed. The genealogy — sunflower spread-families (ALWZ 2019/2020) → fractional threshold theorem (FKNP 2021, Annals of Math.) → full threshold theorem (Park–Pham 2022, JAMS) — is itself the reusable template: "sample a random restriction, split edges by a fragment/spread statistic, fold the easy part into a cover, recurse on the rest" has now cracked several structurally distinct extremal/probabilistic problems and is the leading first-attempt technique for adjacent open covering/threshold questions.

Related

- Erdős #20 — sunflower conjecture, exponential bound for f(n,k) — the Erdős–Ko–Rado sunflower (Δ-system) problem; ALWZ's spread-family sunflower bound (arXiv:1908.08483) is the direct technical ancestor of Park–Pham's proof, sharing the identical random-restriction/covering core (per erdosproblems.com/20 remarks and Rao's arXiv:1909.04774/arXiv:2509.14790 surveys). - R-spread set families (ALWZ/Rao's central reduction device) — the $R$-spread hypothesis at the heart of the ALWZ/FKNP line; Park–Pham's "minimum fragment" is a refinement that removes its case-analysis overhead. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — Rao's Shannon-entropy reproof of the sunflower spread lemma (arXiv:1909.04774), independently recast by Terence Tao (blog); a parallel technique in the same cluster. - concept/random-greedy-algorithm — the general "sample random restriction, cover the easy edges, recurse" skeleton shared by ALWZ, FKNP, and Park–Pham. - Cap-set problem — max progression-free subset of F_3^n — nearest fully-solved sibling in the same extremal-set-theory neighborhood, but via an unrelated technique (polynomial method); useful contrast for which technique family to try first on a new problem.