Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem)

Statement

Let $X$ be a finite set, $|X|=n$, and let $\mathcal F\subseteq 2^X$ be an increasing (monotone / upward-closed) property: $B\supseteq A\in\mathcal F\Rightarrow B\in\mathcal F$. For $p\in[0,1]$ let $\mu_p$ be the product measure on $2^X$, $\mu_p(S)=p^{|S|}(1-p)^{n-|S|}$ (each element of $X$ included independently with probability $p$). Since $\mu_p(\mathcal F)$ is nondecreasing in $p$, there is a unique threshold $$p_c(\mathcal F) := \{p : \mu_p(\mathcal F)=1/2\}.$$

Call $\mathcal F$ $p$-small if there exists a family of "seed"/certificate sets $\mathcal G\subseteq 2^X$ such that (a) every member of $\mathcal F$ contains some $A\in\mathcal G$, and (b) $\sum_{A\in\mathcal G}p^{|A|}<1/2$. The expectation threshold $q(\mathcal F)$ is the supremum of $p$ for which $\mathcal F$ is $p$-small. Condition (a)+(b) plus a union bound immediately give $\mu_q(\mathcal F)<1/2$, so $q(\mathcal F)\le p_c(\mathcal F)$ always holds — trivially, cheaply, and constructively (Kahn & Kalai, "Thresholds and expectation thresholds," §1, PDF read in full).

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

Kahn–Kalai Conjecture (2006/2007): there is a universal constant $K$ (independent of $\mathcal F$, $X$, $n$) such that for every nontrivial increasing $\mathcal F$, $$p_c(\mathcal F) \;\le\; K\, q(\mathcal F)\, \log \ell(\mathcal F).$$

I.e. the trivial, purely combinatorial lower bound $q(\mathcal F)$ is *never* off from the true threshold $p_c(\mathcal F)$ by more than a universal log factor. The original paper phrased this as Conjecture 1 (factor $\log n$, since $\ell(\mathcal F)\le n$ trivially) and a sharper Conjecture 2 specific to fixed subgraph-containment properties (factor $\log|V(H)|$ for a fixed graph $H$, which can be $O(1)$ even as $n\to\infty$ — much stronger than $\log n$ in that case). The theorem finally proved unifies and sharpens both, replacing $\log n$ throughout by $\log\ell(\mathcal F)$.

Theorem (Park–Pham, 2022): the Kahn–Kalai conjecture is TRUE: $p_c(\mathcal F)=O(q(\mathcal F)\log\ell(\mathcal F))$ for every nontrivial increasing $\mathcal F\subseteq 2^X$. (J. Park, H. T. Pham, "A Proof of the Kahn-Kalai Conjecture," arXiv:2203.17207, submitted 31 Mar 2022; J. Amer. Math. Soc. 37(1):235–243 (2024).)

Facts

- Origin: J. Kahn, G. Kalai, "Thresholds and expectation thresholds," *Combinatorics, Probability and Computing* 16(3) (2007) 495–502 (PDF: math.huji.ac.il/~kalai/030406.pdf). Kahn and Kalai themselves flagged the conjecture as "extremely strong" and wrote it "would probably be more sensible to conjecture" it false — they could not find a counterexample and thought one "would also be quite interesting" (verbatim from the PDF). - Canonical illustrating gap (from the original paper): perfect matchings and Hamiltonicity in $G(n,p)$. The expectation threshold is $\Theta(1/n)$ (driven purely by the trivial obstruction "every vertex needs $\ge1$ (resp. $\ge2$) incident edges"), but the true threshold is $\Theta(\log n/n)$ — exactly a $\log n$ gap, the type of gap the conjecture says can never be worse. (Matchings: Erdős–Rényi; Hamiltonicity: Korshunov / Komlós–Szemerédi; both cited in the original Kahn-Kalai PDF as [12], [27], [24].) This example also shows the $\log$ factor in the theorem is not removable in general — the bound is tight in form. - Weaker "fractional" relaxation proved first: K. Frankston, J. Kahn, B. Narayanan, J. Park, "Thresholds versus fractional expectation-thresholds," arXiv:1910.13433, *Annals of Mathematics* 194(2) (2021) 475–495 — proves a conjecture of M. Talagrand ("Are many small sets explicitly small?", STOC 2010) that $p_c(\mathcal F)=O(q_f(\mathcal F)\log\ell(\mathcal F))$, where $q_f(\mathcal F)\ge q(\mathcal F)$ is a fractional/LP-relaxed expectation threshold (a weighting function $g$ with $\sum_{S\subseteq T}g(S)\ge1$ for all $T\in\mathcal F$, in place of a 0/1 cover). This paper already implies, as one-line corollaries, several previously-hard results: perfect hypergraph matchings / "Shamir's problem" (reproving Johansson–Kahn–Vu), bounded-degree spanning trees (reproving Montgomery), and new bounds for bounded-degree spanning subgraphs generally. - Full (non-fractional, sharp) proof: Park & Pham, arXiv:2203.17207 (2022); *J. Amer. Math. Soc.* 37(1):235–243 (2024). Proves the *integral* $q(\mathcal F)$ version directly (does not go through Talagrand's fractional relaxation as an intermediate step) — whether $q(\mathcal F)$ and $q_f(\mathcal F)$ are always comparable is itself a separate, still-open Talagrand question. The proof is celebrated as unusually short (~6 pages) and elementary, discovered by Park and Pham in a single working session in March 2022 (Quanta Magazine, "Elegant Six-Page Proof Reveals the Emergence of Random Structure," 25 Apr 2022). - Genealogy of the technique: the proof descends from the "spread-family" method Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang introduced to bound the Erdős–Ko–Rado sunflower conjecture (arXiv:1908.08483, 2019/2020) — see Erdős #20 — sunflower conjecture, exponential bound for f(n,k). FKNP (2021) adapted spread-families into a fractional threshold theorem; Park–Pham (2022) then found a more direct "cover-building via random restriction + counting" argument that gets the full integral statement without the fractional detour. - Once proved, the result is often called the Park–Pham theorem in later literature. - This is a *black-box, universal-constant* tool: once $q(\mathcal F)$ is estimated (usually an easy hand calculation — see Technique), the theorem hands back the true threshold's order of magnitude for free, replacing what used to require a bespoke second-moment or absorption-method argument for each new random structure.

Technique

When it applies: $\mathcal F$ must be an increasing (monotone) property of subsets of a finite ground set — containment of a fixed or spanning subgraph, perfect matchings, Hamiltonicity, connectivity, containing a Latin square / Steiner triple system, $k$-colorability-type properties via monotone complements, etc. Essentially any "does a $p$-random combinatorial object contain structure X" threshold-location question. It does not apply to non-monotone properties directly (though monotonization tricks sometimes rescue such cases), and it does not give a *sharp* threshold (the exact constant / the precise $(1+o(1))$-location) — only the order of magnitude up to $O(\log\ell(\mathcal F))$. Sharp thresholds remain a separate, harder, usually problem-specific question (the Kahn–Kalai *sharp*-threshold conjecture is a distinct, further, largely open refinement).

How to use it to prove a threshold theorem (the reusable recipe): 1. Lower-bound step is free. Any covering family $\mathcal G$ of "obstructions" — small certificate sets each of which forces membership in $\mathcal F$ once contained in the random set, chosen so every member of $\mathcal F$ contains one — with small total weight $\sum_{A\in\mathcal G}p^{|A|}$ gives $q(\mathcal F)\ge p$ by a trivial union bound. In practice this is a first-moment / expected-count computation: e.g. for spanning-tree or Hamiltonicity-type properties, the natural obstruction is "some vertex has too low degree," and $q(\mathcal F)$ is exactly the density at which the expected number of low-degree vertices drops below a constant. 2. The theorem supplies the upper bound "for free." Once $q(\mathcal F)$ (or an upper bound estimate of it) is known, the Kahn–Kalai/Park–Pham theorem immediately gives $p_c(\mathcal F)=O(q(\mathcal F)\log\ell(\mathcal F))$ — i.e., a matching-up-to-log-factor threshold, without needing a bespoke second-moment or absorption argument. 3. Sharper form via "spread measures" (the mechanism used inside the proof, and directly reusable when a cover isn't obvious): call a probability measure $\nu$ on the minimal members ("edges") of $\mathcal F$ $r$-spread if for every $S\subseteq X$, $\nu(\{A : A\supseteq S\})\le r^{-|S|}$ — i.e., no small partial structure is disproportionately over-represented among the witnessing sets. If such an $r$-spread measure exists, the spread lemma (the technical core shared by FKNP 2021 and Park–Pham 2022) gives $p_c(\mathcal F)=O(r^{-1}\log\ell(\mathcal F))$ directly. This turns "find the threshold" into "exhibit a spread-out probability distribution over witnessing structures" — e.g. the uniform distribution over all spanning trees of a near-regular degree sequence, or over Latin squares / Steiner triple systems built via nibble/absorption methods, then check no small partial substructure is over-counted. This reduces an analytic threshold-location problem to a purely combinatorial spreadness estimate. 4. Proof idea behind why it works (Park–Pham 2022, reported at the level of expositions, not independently verified line-by-line here): rather than Talagrand's LP/fractional-relaxation route used by FKNP, or the hypergraph-container method, the proof directly and iteratively builds a small covering family $\mathcal G$ by repeatedly sampling a random restriction $W\subseteq X$ and, for each not-yet-covered witnessing set $S$, tracking its smallest "remaining fragment" relative to $W$; sets whose fragment is already small get folded into the cover, the rest recurse on the shrunk ground set. A sharp counting argument bounds the total weight of the resulting cover after $O(\log\ell(\mathcal F))$ rounds. This "sample a random restriction, peel off the easy witnesses, recurse" skeleton is genealogically the same trick (a sharpening of it) that ALWZ used for the sunflower bound. 5. Caveat on what NOT to expect: the theorem never removes the need to compute $q(\mathcal F)$ itself (or find a spread measure) — that combinatorial estimate is still problem-specific, just usually much easier than a full threshold proof. And the $\log\ell(\mathcal F)$ factor is generically unavoidable (matching-cycle/Hamiltonicity example above), so the theorem is not a route to *sharp* thresholds.

Related

- Erdős #20 — sunflower conjecture, exponential bound for f(n,k) — Erdős–Ko–Rado sunflower (Δ-system) problem; the Alweiss–Lovett–Wu–Zhang spread-family sunflower bound (arXiv:1908.08483) is the direct technical ancestor of the spread/cover machinery used to prove this conjecture; that problem's page cites this concept as shared derivation fuel. - Kahn–Kalai conjecture — threshold vs. expectation-threshold for monotone properties — the full solved-problem narrative page in this wiki (history, proof sketch, downstream corollaries) for the Park–Pham result; this concept page is the technique-reference companion. - Talagrand's fractional expectation-threshold conjecture (proved by Frankston–Kahn–Narayanan–Park, 2019) — the predecessor fractional theorem (Frankston–Kahn–Narayanan–Park 2021) whose spread-hypergraph machinery this theorem's proof builds on and sharpens. - R-spread set families (ALWZ/Rao's central reduction device) — the $r$-spread condition on a measure/hypergraph, the reusable combinatorial engine underlying both the fractional (FKNP) and full (Park–Pham) theorems. - concept/first-moment-method — the trivial-but-essential union-bound computation of $q(\mathcal F)$ itself, which every application of this theorem starts from. - concept/hypergraph-containers — a structurally distinct (but often-competing/complementary) general-purpose technique for extremal/threshold-type problems in random discrete structures.