Talagrand's fractional expectation-threshold conjecture (proved by Frankston–Kahn–Narayanan–Park, 2019)

Statement

Let $X$ be a finite set and $\mathcal F\subseteq 2^X$ an increasing family ($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)^{|X\setminus S|}$). Define:

- Threshold $p_c(\mathcal F)$: the unique $p$ with $\mu_p(\mathcal F)=1/2$. - $\mathcal F$ is $p$-small if some $\mathcal G\subseteq 2^X$ has $\mathcal F\subseteq\langle\mathcal G\rangle:=\{T:\exists S\in\mathcal G,\,S\subseteq T\}$ and $\sum_{S\in\mathcal G}p^{|S|}\le 1/2$; expectation-threshold $q(\mathcal F):=\max\{p:\mathcal F\text{ is }p\text{-small}\}$. - $\mathcal F$ is weakly $p$-small if there is $g:2^X\to\mathbb R_{\ge0}$ with $\sum_{S\subseteq T}g(S)\ge1$ for every $T\in\mathcal F$ and $\sum_{S\subseteq X}g(S)p^{|S|}\le1/2$; fractional expectation-threshold $q_f(\mathcal F):=\max\{p:\mathcal F\text{ weakly }p\text{-small}\}$. - $\ell(\mathcal F)$ := the largest size of a minimal member of $\mathcal F$.

Always $q(\mathcal F)\le q_f(\mathcal F)\le p_c(\mathcal F)$ (the expectation-threshold is a trivial, cheaply-computable lower bound on the true threshold). Talagrand (Conjectures 8.3/8.5 of his "Are many small sets explicitly small?" line of work) conjectured a matching upper bound up to a $\log$ factor in the fractional relaxation: $$p_c(\mathcal F)\;=\;O\big(q_f(\mathcal F)\cdot\log\ell(\mathcal F)\big).$$ (This is a weakening of the harder, non-fractional Kahn–Kalai 2006 "expectation-threshold conjecture" $p_c(\mathcal F)=O(q(\mathcal F)\log\ell(\mathcal F))$, which remained open until Park–Pham 2022, arxiv.org/abs/2203.17207 — see Related.)

Facts

- Origin: M. Talagrand, "Are many small sets explicitly small?", *Proc. STOC 2010* (ref [28] in the FKNP paper), Conjectures 8.3 and 8.5, posed as a tractable fractional relaxation of the 2006 Kahn–Kalai expectation-threshold conjecture (Kahn, J., Kalai, G., "Thresholds and expectation-thresholds," *Combin. Probab. Comput.* 2007) — per arxiv.org/abs/1910.13433 introduction and en.wikipedia.org/wiki/Kahn–Kalai_conjecture. - Status: SOLVED. Proved by Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park (all Rutgers Math at the time), arXiv:1910.13433, submitted 29 Oct 2019, revised 10 Dec 2019; published as *Annals of Mathematics* 194 (2021), no. 2, 475–495 (annals.math.princeton.edu/2021/194-2/p02, projecteuclid.org/journals/annals-of-mathematics/volume-194/issue-2). - The trivial direction $q_f\le p_c$ always holds; the content of the theorem is the reverse direction up to the universal-constant, $\log\ell(\mathcal F)$-factor loss — and this log factor is necessary in general (matches known lower-bound examples, e.g. cliques in random graphs), so the bound is tight in form. - Consequences proved as easy corollaries in the same paper (previously each required separate, hard, bespoke arguments): thresholds for perfect matchings in random $r$-uniform hypergraphs / "Shamir's problem" (reproving Johansson–Kahn–Vu), thresholds for containing bounded-degree spanning trees (reproving Montgomery 2019) and bounded-degree spanning structures more generally, and a resolution of the "axial" random multi-dimensional assignment problem (new result, e.g. $Z^A_d(n)=\Theta(n^{-(d-2)})$) — per arxiv.org/abs/1910.13433 abstract/intro and gilkalai.wordpress.com writeup. - Related/downstream: the (harder) non-fractional Kahn–Kalai conjecture, $p_c=O(q\log\ell)$, was proved 3 years later by Jinyoung Park and Huy Tuan Pham, "A proof of the Kahn–Kalai conjecture," arXiv:2203.17207 (2022), published *J. Amer. Math. Soc.* 2024 — mathematics.stanford.edu/news/jinyoung-park-and-huy-tuan-pham-prove-kahn-kalai-conjecture. Park was a co-author of the earlier fractional result, and the Park–Pham proof directly reuses/extends the "spread" machinery introduced by FKNP (see Solution below).

Answer

yes — the conjectured logarithmic-gap bound holds. FKNP prove (Theorem 1.1 of arxiv.org/abs/1910.13433): $$p_c(\mathcal F)\le K\cdot q_f(\mathcal F)\cdot\log\ell(\mathcal F)$$ for a universal constant $K$, for every increasing family $\mathcal F$ on every finite $X$.

The transferable technique — "spread" hypergraphs + randomized sunflower-style peeling.

1. *Reduction to a purely combinatorial statement about "spread" hypergraphs.* Call a hypergraph $\mathcal H$ on $X$ $\kappa$-spread if for every $S\subseteq X$, $|\mathcal H\cap\langle S\rangle|\le \kappa^{-|S|}|\mathcal H|$ (quoted exactly from ar5iv.labs.arxiv.org/html/1910.13433) — i.e. no set of size $s$ is contained in more than a $\kappa^{-s}$-fraction of the edges; edges are "spread out," not concentrated on any small core. The paper's Proposition 1.5 shows: if $q_f(\mathcal F)\le q$, the fractional-cover witness $g$ can be turned into a probability measure on $2^X$ supported on $\mathcal F$ that is $(2q)$-spread. This converts an analytic/LP-type quantity ($q_f$, defined via a fractional covering weight $g$) into a purely combinatorial object (a spread *hypergraph* of actual sets). 2. *The core theorem (Theorem 1.6):* there is a universal $K$ such that for any $\ell$-bounded, $\kappa$-spread hypergraph $\mathcal H$ on $X$, a uniformly random subset of $X$ of size $K\kappa^{-1}\log\ell\cdot|X|$-scaled lies in $\langle\mathcal H\rangle$ with high probability — i.e. a random set of that density is guaranteed (w.h.p.) to contain some edge of $\mathcal H$. Combined with step 1 this immediately gives $p_c(\mathcal F)=O(q_f(\mathcal F)\log\ell(\mathcal F))$. 3. *How Theorem 1.6 is proved — the "sunflower-free peeling" idea, the actual transferable technique.* The authors build on and sharpen the Alweiss–Lovett–Wu–Zhang breakthrough on the Erdős–Rado sunflower conjecture (bounding sunflower-free family sizes). Concretely (Lemma 3.1, an improvement of a lemma from ALWZ), they run an iterative randomized covering/peeling algorithm: starting from $\mathcal H_0=\mathcal H$, at each step sample a random subset $W_i$ of size $\approx n p$; for each surviving edge $S$, replace the "remainder" $S\setminus W_i$ by a smaller "good" set $\chi_i(S,W_i)=\psi(S\cup W_i)\setminus W_i$ whenever one exists, i.e. once part of an edge has already been hit by the random sample, look for a *smaller* set that would still complete it — this is exactly the sunflower-style trick of trading a large petal for a smaller one. The spread condition is what guarantees this replacement keeps working at every stage: "a general $S\setminus W$, while not itself small, will, in consequence of the spread assumption, typically contain some small $S'\setminus W$" (quoted from the paper via ar5iv fetch). The proof separates "nonpathological" contributions (bounded via a density estimate) from rare "pathological" ones (bounded via Markov's inequality plus the spread hypothesis), which is the specific technical sharpening beyond ALWZ that yields the needed quantitative bound. 4. *Why this is the reusable idea for open problems downstream:* the "spread $\Rightarrow$ random-set-hits-an-edge-w.h.p." principle (the spread lemma) decouples the *combinatorial* difficulty (bounding thresholds for a specific random structure — spanning trees, matchings, Latin squares, etc.) from a *single, general-purpose, structure-agnostic engine*. Any threshold problem reduces to (a) exhibiting a good fractional cover / spread measure on the target family (usually an easy first-moment / weighting computation) and (b) invoking the spread lemma as a black box. This exact template — verify spread, invoke a spread-type lemma — is what Park–Pham then pushed further (dropping the "fractional" relaxation entirely) to settle the full, harder Kahn–Kalai conjecture in 2022 (arxiv.org/abs/2203.17207), and what a large wave of follow-up threshold papers (Latin squares/Steiner systems bounds, arxiv.org/abs/2206.14472; "smoother notion of spread hypergraphs," arxiv.org/abs/2106.11882; second-moment proof of the spread lemma, arxiv.org/abs/2209.11347) reuse directly.

Related

- concept/spread-hypergraph — the $\kappa$-spread condition and the spread lemma (Theorem 1.6): the reusable combinatorial engine at the center of the proof; downstream open threshold problems typically reduce to "find a spread measure on this family." - concept/expectation-threshold — the underlying $q(\mathcal F)$ vs $q_f(\mathcal F)$ vs $p_c(\mathcal F)$ hierarchy that frames the whole line of work. - concept/sunflower-lemma / concept/alweiss-lovett-wu-zhang-sunflower-bound — the Erdős–Rado sunflower-conjecture breakthrough (arXiv 1909.04077) whose randomized peeling technique FKNP sharpen and adapt into Lemma 3.1. - solved/kahn-kalai-conjecture-park-pham — the harder, non-fractional Kahn–Kalai conjecture, proved by Park–Pham (2022, arxiv.org/abs/2203.17207) by extending exactly this spread machinery; the natural "next problem" this page's technique feeds into. - concept/random-hypergraph-matching-threshold — Johansson–Kahn–Vu "Shamir's problem" threshold, reproved as an easy corollary here. - concept/bounded-degree-spanning-tree-threshold — Montgomery's bounded-degree spanning-tree threshold, reproved as an easy corollary here.