1 Introduction
Expectation thresholds measure how cheaply an increasing family can be covered by elementary containment events. Their fractional relaxation allows a member to be covered by a total weight of one, distributed among its subsets. Talagrand conjectured that this relaxation changes the expectation threshold by at most a universal factor [17, Conjecture 6.3]. We prove this conjecture.
Let X be a finite nonempty set and let \F be a nonempty proper increasing subfamily of 2^X. For a family \G\subseteq2^X and a function g:2^X\to[0,1], define
and
Throughout, p\in[0,1] and p^0=1, including when p=0. Thus a cover supplies, inside each member of \F, at least one generator S\in\G. If X_p includes the elements of X independently with probability p, the cost of that generator is \mathbb P(S\subseteq X_p)=p^{|S|}. We say that \F is p-small if there is a family \G with \F\subseteq\langle\G\rangle and c_p(\G)\le1/2. Its integral and fractional expectation thresholds are
In particular, q(\F)\le q_f(\F), by taking g to be the indicator of an integral cover.
These maxima are well-defined. Since \varnothing\notin\F, both feasible parameter sets contain zero. Integral feasibility is a finite union of closed subsets of [0,1]. Fractional feasibility is the projection of the compact set of pairs (p,g) satisfying the displayed constraints in [0,1]\times[0,1]^{2^X}.
Theorem 1.1. For every finite nonempty X and every nonempty proper increasing family \F\subseteq2^X,
Both thresholds use the budget 1/2. The constant is independent of |X|, the sizes of the minimal members of \F, and the support of the fractional cover.
The conclusion preserves the covering budget: every fractional cover of cost at most 1/2 at a parameter r admits an integral cover of cost at most 1/2 at r/(25\cdot512^4).
1.1 Thresholds, selectors, and earlier comparisons
Expectation thresholds arose in the study of when a random set first has a prescribed increasing property. Let p_c(\F) denote the unique parameter for which \mathbb P(X_p\in\F)=1/2. A union bound applied to an integral cover gives q(\F)\le p_c(\F); taking expectations in a fractional cover gives q_f(\F)\le p_c(\F) as well. Kahn and Kalai [10] conjectured the upper bound p_c(\F)=O(q(\F)\log(2|X|)). Frankston, Kahn, Narayanan, and Park [8], building on the sunflower methods of Alweiss, Lovett, Wu, and Zhang [1], proved the fractional bound
Park and Pham [14] proved the corresponding bound with q in place of q_f, resolving the Kahn–Kalai conjecture. These theorems estimate the random-set threshold. Talagrand’s comparison asks whether fractional certificates themselves admit integral replacements at a constant loss.
Early results obtained such replacements by exploiting the structure of the sets with positive fractional weight. Talagrand settled the case of singleton sets [17, Section 6]; DeMarco and Kahn [3] treated clique-counting certificates, and Frankston, Kahn, and Park [9] treated arbitrary weights on pairs. Fischer and Person extended these methods to nearly linear uniform hypergraphs [5] and further clique cases [6]. They also proved the comparison with high probability for constant weights on random uniform supports [7].
Selector processes supply a different route: they seek a member whose assigned vertex mass is substantially captured by a random subset. Park and Pham proved Talagrand’s selector-process conjecture [13], and Bednorz, Martynek, and Meller [2] gave a proof using truncated weights. Dubroff, Kahn, and Park [4, Theorem 1.2] used selector estimates to round any fractional cover whose positive coefficients occur only on sets of cardinality at most t, with a loss depending on t. Pham sharpened this loss to O(\log(2t)) [15, arXiv version 1, Theorem 1.2]. Here t bounds the cardinalities of the weighted sets, not their number or the sizes of the minimal members of \F. For example, for 1\le k\le|X|, the family \{H\subseteq X:|H|\ge k\} has the fractional cover g(\{x\})=1/k, zero elsewhere: its weighted sets are singletons, while its minimal members have cardinality k.
Fischer and Person’s sampling argument for sufficiently large sets [5, Theorem 10], combined with Pham’s logarithmic rounding bound, gives a loss of order \log\log(4|X|). This consequence is recorded in the expanded version of Pham’s paper [16, Corollary 1.8]. More recently, Park [12, Theorem 1.2] obtained the dimension-independent bound
for a universal K. The factor here still grows as q(\F) tends to zero. Theorem 1.1 removes both kinds of dependence. Section 4 applies it to Li’s fractional discrete-convexity theorem [11]: for any class \mathcal A\subseteq2^X with \P(X_p\in\mathcal A)>1/2, the sets not contained in a union of two members of \mathcal A have a small integral cover at a universal constant multiple of p.
Remark 1.2 (Talagrand’s original formulation). For p>0, the weak-smallness probability weights \beta_S in [17, Definition 6.1] give fractional coefficients \beta_S/(2p^{|S|}); capping these at one preserves coverage and does not increase cost. Conversely, the masses 2g(S)p^{|S|} can be completed to a probability distribution by adding the deficit at the empty set. Passing from an arbitrary class to its upward closure preserves both cover constraints. Thus the increasing-family formulation of Theorem 1.1 also resolves Conjecture 6.3 in its original form.
1.2 The selector estimate and the rounding mechanism
Our selector estimate controls one member simultaneously at several scales. Assign to each H\in\F a probability mass \lambda_H supported on H. Independently color the vertices by integers a(x)\in\{1,\ldots,s+1\}, and let A_i=\{x:a(x)\le i\}. Theorem 2.1 specifies geometrically increasing color probabilities for which failure of p-smallness forces, with probability at least 9/10, a single H satisfying
The uncaptured masses are summable, so this member has bounded mean color:
Separate estimates at individual scales could choose different members and would not give this bound for any one member.
To apply the estimate to a fractional cover of cost at most 1/2 at parameter r, distribute each nonempty weight g(S) equally among the vertices of S and normalize on each member, following Pham [15, arXiv version 1, Section 3]. The mean vertex color then equals the weighted mean of the average colors of those sets. Thus a fixed positive amount of fractional weight lies on sets with average color at most four. For a suitable fixed base B>1, the independent variables Y_x=B^{4-a(x)} satisfy \prod_{x\in S}Y_x\ge1 on all these sets. Their common mean can at the same time be made a constant multiple of p by a suitable choice of the number of colors. Taking p to be a sufficiently small constant multiple of r, independence bounds the expectation of
from above using the fractional covering cost, while the selector event bounds it from below. Section 3 makes these bounds incompatible. Only nonemptiness of the weighted sets enters this final comparison, so their cardinalities need no upper bound.
The proof of the selector estimate in Section 2 develops the minimum-fragment method of Park and Pham [13] and Pham’s towers of fragments [15, arXiv version 1, Section 2], together with the maximal truncations of Bednorz, Martynek, and Meller [2, Section 3.1]. For each coloring and each member, we move vertices to earlier colors until a set of truncated inequalities holds, minimizing the total number of color levels moved. The resulting changed sets form a cover. To estimate its cost, we record the final coloring and the numbers of vertices making each possible color change. These data determine one common member satisfying the truncated inequalities for the entire group of original colorings. Maximal truncation bounds the number of candidate vertices at each color, and a weighted AM–GM estimate pays for their allocation among the scales. Keeping all color changes in the same record is what permits the simultaneous estimate.
The random vertex colors used below are independent. We write \lambda_H(A)=\sum_{x\in A}\lambda_H(x). Empty sums are zero and empty products are one.
2 A multiscale selector estimate
The key estimate finds a single member of the family whose mass is captured at every scale. The family in this section need not be increasing. Recall that a family \F\subseteq 2^X is p-small if there is a family \G\subseteq 2^X such that every H\in\F contains some G\in\G and \sum_{G\in\G}p^{|G|}\le 1/2.
The argument combines the minimum-fragment method of Park and Pham [13, Definitions 2.3 and 2.5, Proposition 2.6] and its multiscale development by Pham [15, arXiv version 1, Section 2] with the maximal-cutoff argument of Bednorz, Martynek, and Meller [2, Lemma 3.6]. All the estimates needed here are proved below.
Theorem 2.1 (Multiscale selector estimate). Let X be a finite set, let \F be a nonempty family of nonempty subsets of X, and suppose that \F is not p-small, where 0<p\le 1. For each H\in\F, let \lambda_H be a probability mass function on X supported on H. Set D=256, and let s\ge 0 be an integer such that
Independently color the elements of X by a map a:X\to\{1,\ldots,s+1\}, with color probabilities
For a coloring v, write A_i(v)=\{x\in X:v(x)\le i\}. With probability at least 9/10, there is an H\in\F such that
In particular, with probability at least 9/10, there is an H\in\F for which
For colorings where simultaneous capture fails, the proof will construct covers from sets of vertices moved to earlier colors. We will sum these costs against the probabilities of the failing colorings. The estimate comes from locating the changed vertices within small sets determined by the final coloring and the numbers moved between colors. The following truncation observation supplies the size bound for these sets.
Lemma 2.2 (Maximal truncation). Let \lambda be a probability mass function on a finite set X, let A\subseteq X, and let m\ge 0 and 0<d<1. Call u\in[0,1] admissible if
If there is an admissible cutoff, there is a largest one, \varepsilon, and it satisfies
Proof. The inclusion in (2.4) is equivalent to
The remaining inequality is closed in u, since its two sides are continuous. Thus the nonempty set of admissible cutoffs is compact and has a largest element \varepsilon.
Put R=\{x:\lambda(x)>\varepsilon\}. If \varepsilon=1, then R=\varnothing and the assertion holds. Otherwise, consider
On a sufficiently short interval to the right of \varepsilon, the only unsaturated terms are those indexed by R. Each of these points belongs to A, so the slope on that interval is d|R|-m. This statement also holds when \varepsilon=0 or when \varepsilon equals one of the weights: weights equal to the cutoff remain constant when the cutoff increases. An increase of the cutoff preserves the inclusion in (2.4). If d|R|-m were positive, it would also preserve f(u)\ge 0 for a small increase, contradicting maximality. Hence d|R|\le m.
Proof of Theorem 2.1. If s=0, the only color is 1, and both conclusions are immediate. Assume henceforth that s\ge 1, and put d_i=2^{-i} for 1\le i\le s. Call a coloring a bad if no H\in\F satisfies (2.2). We will prove \P(a\text{ is bad})\le 1/10.
Feasible moves and a cover. We may move vertices to earlier colors, obtaining a coloring z\le a pointwise. Write
Call such a move feasible if there are H\in\F and \varepsilon_1,\ldots,\varepsilon_s\in[0,1] such that, for every i,
The right side charges \varepsilon_i for each vertex in A_i(z)\setminus A_i(a). Removing one of these vertices lowers the truncated sum by at most \varepsilon_i while reducing that charge by exactly \varepsilon_i; hence the inequality survives. If the vertex has mass at most \varepsilon_i, it lies outside R_i, so the inclusion survives as well. We will apply this balance when delaying a vertex from color i to color i+1.
If the unchanged move z=a is feasible, then a is not bad. Indeed, in this case m_i(a,a)=0. Replacing each truncated weight by its original value adds only nonnegative terms to the left side of (2.5): any excess weight lies in R_i\subseteq A_i(a) and has coefficient d_i. The resulting inequality is \lambda_H(A_i(a))-(1-d_i)\ge0, for the same H at every i.
Fix orders on the finite sets of colorings and members of \F. For every a and H_0\in\F, choose a feasible coloring z with U(a,z)\subseteq H_0 minimizing
breaking ties by the fixed order. This minimum exists: the move that sets z(x)=1 on H_0 and leaves other colors unchanged is feasible with H=H_0 and all cutoffs zero. Notice that the witness H in the minimization is otherwise unrestricted; it need not equal H_0.
Let \mathcal Z(a) be the set of chosen colorings, with repetitions removed. The changed sets U(a,z), z\in\mathcal Z(a), cover \F, because each H_0 contains its chosen changed set. Failure of p-smallness therefore implies
This remains true if distinct colorings have the same changed set: the displayed sum is then at least the cost of the cover with its repeated sets removed. Define P(v)=\prod_{x\in X}\pi_{v(x)} for every coloring v. It follows that
Every changed set appearing on the right is nonempty, since a bad coloring has no feasible unchanged move.
A witness determined by the final coloring and the counts. Group the pairs (a,z) on the right of (2.6) by z and the array of counts
We call this array the profile. Put
The profile also determines every quantity in the feasibility tests that depends on a, because
Fix z and a profile occurring in the sum. Choose the first H\in\F that can witness (2.5) with these data. Such a witness exists, and this choice uses only z and the profile. For this fixed H, choose at every i the largest admissible cutoff in (2.5). The choices for the different indices impose no restrictions on one another. Lemma 2.2 gives
The resulting H, cutoffs, and sets R_i are fixed for the entire group. In particular, they witness feasibility for every original coloring a in that group, irrespective of the member H_0 that led to the choice of z.
For each such original coloring we claim that
Suppose instead that a vertex x on the left lies outside R_i. Delay its color in z from i to i+1, obtaining z'. Since a(x)>i, we still have z'\le a. Choose an H_0 for which z was a minimum. The changed set of z' is contained in that of z, so it is still contained in H_0.
Only A_i(z) changes under this delay: it loses x, while all other A_j(z) remain unchanged. Correspondingly, m_i(a,z) decreases by one and all other m_j(a,z) remain unchanged. The inclusion in test i stays true because x\notin R_i. The left side of that test decreases by \min\{\lambda_H(x),\varepsilon_i\}\le\varepsilon_i, whereas its right side decreases by exactly \varepsilon_i. Thus the same H and cutoffs witness feasibility of z'. But L(a,z')=L(a,z)-1, contradicting the defining minimum. This proves (2.9) for every a in the group. Figure 1 illustrates why moving one vertex back by one level changes only one of the feasibility tests.
Figure 1: The one-level delay in the reconstruction argument. A vertex originally colored h>i has been moved to i; delaying it to i+1 removes it from A_i alone. At the same time m_i decreases by one, lowering the right side of (2.5) by \varepsilon_i. Its membership in every other cumulative set A_j stays fixed. The drawing is schematic; h may equal i+1.
Counting the original colorings. Given z and the profile, an original coloring a is determined by its changed vertices of each color i in z, together with their original colors h>i. By (2.9), the number of possibilities is at most
where the second factor is a multinomial coefficient. The sets R_i may overlap and may contain vertices of other colors in z. Counting arbitrary subsets of them only adds possibilities to (2.10); every actual coloring has a unique encoding of the indicated form.
For t>0, (2.8) and \binom{n}{k}\le(en/k)^k give
To see the last inequality, apply weighted AM–GM with weights \alpha_i=t_i/t on the positive rows:
Raising this inequality to the power t yields exactly the second inequality in (2.11). Rows with t_i=0 contribute a factor of one.
For each pair in the group, its probability and cost satisfy the exact identity
All color probabilities are positive. Combining (2.10)–(2.12), the contribution of a fixed z and profile to the right side of (2.6) is at most
The witness and the sets R_i can depend on the full profile, but none of that dependence remains in this bound.
For fixed row sums t_1,\ldots,t_s, we can consequently sum (2.13) over all nonnegative integer profiles with those row sums, including profiles that do not occur. The multinomial theorem gives, for each row,
Finally, summing over all colorings z uses \sum_zP(z)=1. Thus the right side of (2.6) is at most
where both sums run over integer tuples. Put \rho=\sum_{i=1}^s e/64^i. For a fixed total \ell=t_1+\cdots+t_s, each monomial in (2.14) occurs in the expansion of \rho^\ell with a multinomial coefficient at least one. Since
we obtain
Together with (2.6), this proves that the bad probability is at most 1/10.
For every nonbad coloring the same H satisfies all inequalities in (2.2). Since the colors are integers,
This proves (2.3) and completes the proof.
3 Rounding a fractional cover
We convert the color bound into independent numerical variables on the vertices. Their means will be small, while the common member supplied by Theorem 2.1 will force a positive amount of fractional-cover mass onto sets whose products are at least one. Comparing the resulting lower and upper bounds on the same expectation completes the proof. This conversion follows the selector-to-rounding approach of Dubroff, Kahn, and Park [4, Section 2] and Pham [15, arXiv version 1, Section 3]. In particular, the equal distribution of a set’s weight among its vertices in (3.2) is Pham’s construction. The simultaneous color bound supplies the additional control used here for arbitrary set sizes.
Proof of Theorem 1.1. Put
Let r\in(0,1] and suppose that g:2^X\to[0,1] satisfies
Set p=r/C. We prove that \mathcal F is p-small.
First observe that g(\varnothing)\le1/2, since its contribution to the second sum in (3.1) is g(\varnothing). For each H\in\mathcal F, define
The function \lambda_H vanishes off H and is a probability mass function: summing over x counts each nonempty S exactly |S| times.
Suppose, for a contradiction, that \mathcal F is not p-small. Let s be the largest nonnegative integer for which
Such an integer exists: zero satisfies the restriction, and p>0 makes the geometric sums unbounded. Apply Theorem 2.1 to these probability masses and this choice of s. Thus the colors a(x) are independent, with
With probability at least 9/10, there is an H\in\mathcal F such that \sum_x a(x)\lambda_H(x)\le2. Denote this event by \mathcal E, and set
Fix an outcome in \mathcal E and a corresponding member H. Writing \overline a(S)=|S|^{-1}\sum_{x\in S}a(x) for nonempty S, we have
Apply Markov’s inequality to the probability distribution g(S)/M_H on the nonempty subsets of H. It gives
For every set in this sum,
Consequently Z\ge M_H/2\ge1/4 on \mathcal E. This holds for each outcome, although the corresponding H may depend on the coloring. Since Z is nonnegative everywhere,
For the upper bound, maximality of s gives
As B\ge D, it follows that
The variables Y_x are independent and identically distributed, and their common mean \mu satisfies
The same estimates hold when s=0, with the first sums empty. Independence now yields
Here the factor 1/5 is valid because every set in the sum is nonempty. The bounds (3.5) and (3.8) contradict one another.
Thus \mathcal F is r/C-small for every admissible r>0. At r=0, the family \mathcal F itself is a cover of cost zero, since \varnothing\notin\mathcal F. Taking r=q_f(\mathcal F), with this last observation covering the case q_f(\mathcal F)=0, proves
4 A consequence for unions of two sets
The comparison also strengthens a recent bound for sets that cannot be covered by two members of a large class. For \mathcal A\subseteq2^X, write \mu_p(\mathcal A)=\P(X_p\in\mathcal A) and define
When \mu_p(\mathcal A)>1/2, Li’s fractional discrete-convexity theorem [11, Corollary 3.1] provides a fractional cover for this family. Combining that input with Theorem 1.1 gives the following integral conclusion.
Corollary 4.1. Let X be a finite nonempty set, let 0<p<1, and let \mathcal A\subseteq2^X satisfy \mu_p(\mathcal A)>1/2. Set C=25\cdot512^4. There is a family \mathcal G\subseteq2^X such that
In particular, \operatorname{Bad}_2(\mathcal A) is (p/(2C))-small. No monotonicity assumption on \mathcal A is needed.
Proof. If \operatorname{Bad}_2(\mathcal A) is empty, take \mathcal G=\varnothing. Otherwise this is a nonempty increasing family. It is proper because \mathcal A is nonempty and hence \varnothing\notin\operatorname{Bad}_2(\mathcal A). Li’s theorem, in the covering formulation given by Park [12, Theorem 3.4], supplies a fractional cover of \operatorname{Bad}_2(\mathcal A) of cost at most 1/2 at parameter p/2. Its coefficients may be capped at one without affecting coverage or increasing cost. Theorem 1.1 therefore yields an integral cover of cost at most 1/2 at parameter p/(2C).
Park [12, Corollary 3.5] obtained the same conclusion with smallness parameter
for a universal K. Corollary 4.1 removes the double logarithmic loss while retaining unions of two members and the covering budget 1/2.
References
- [1]Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang, Improved bounds for the sunflower lemma, Annals of Mathematics 194 (2021), no. 3, 795–815. doi:10.4007/annals.2021.194.3.5.
- [2]Witold Bednorz, Rafał Martynek, and Rafał Meller, The suprema of selector processes with the application to positive infinitely divisible processes, preprint, 2022; version 3, 2026. arXiv:2212.14636v3. doi:10.48550/arXiv.2212.14636.
- [3]Bobby DeMarco and Jeff Kahn, Note on a problem of M. Talagrand, Random Structures & Algorithms 47 (2015), no. 4, 663–668. doi:10.1002/rsa.20559.
- [4]Quentin Dubroff, Jeff Kahn, and Jinyoung Park, Note on a conjecture of Talagrand: expectation thresholds vs. fractional expectation thresholds, preprint, 2024. arXiv:2412.00917v1. doi:10.48550/arXiv.2412.00917.
- [5]Thomas Fischer and Yury Person, Some results on fractional vs. expectation thresholds, Electronic Journal of Combinatorics 32 (2025), no. 3, Paper P3.39. doi:10.37236/12611.
- [6]Thomas Fischer and Yury Person, Further remarks on fractional vs. expectation thresholds, preprint, 2025. arXiv:2505.21782v1.
- [7]Thomas Fischer and Yury Person, Fractional vs. expectation thresholds: random support case, in 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026), Leibniz International Proceedings in Informatics 381 (2026), 24:1–24:10. doi:10.4230/LIPIcs.AofA.2026.24.
- [8]Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park, Thresholds versus fractional expectation-thresholds, Annals of Mathematics 194 (2021), no. 2, 475–495. doi:10.4007/annals.2021.194.2.2.
- [9]Keith Frankston, Jeff Kahn, and Jinyoung Park, On a problem of M. Talagrand, Random Structures & Algorithms 61 (2022), no. 4, 710–723. doi:10.1002/rsa.21077.
- [10]Jeff Kahn and Gil Kalai, Thresholds and expectation thresholds, Combinatorics, Probability and Computing 16 (2007), no. 3, 495–502. doi:10.1017/S0963548307008474. arXiv:math/0603218v2.
- [11]Chen Li, On p-Spread Measures, preprint, September 8, 2026. arXiv:2609.08967v1.
- [12]Jinyoung Park, A dimension-free comparison between expectation thresholds and fractional expectation thresholds, preprint, September 13, 2026. arXiv:2609.14681v1.
- [13]Jinyoung Park and Huy Tuan Pham, On a conjecture of Talagrand on selector processes and a consequence on positive empirical processes, Annals of Mathematics 199 (2024), no. 3, 1293–1321. doi:10.4007/annals.2024.199.3.6. arXiv:2204.10309v2.
- [14]Jinyoung Park and Huy Tuan Pham, A proof of the Kahn–Kalai conjecture, Journal of the American Mathematical Society 37 (2024), no. 1, 235–243. doi:10.1090/jams/1028.
- [15]Huy Tuan Pham, A sharp version of Talagrand’s selector process conjecture and an application to rounding fractional covers, in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC ’25), ACM, New York, 2025, pp. 322–328. doi:10.1145/3717823.3718256. Preprint version: arXiv:2412.03540v1, 2024.
- [16]Huy Tuan Pham, A sharp version of Talagrand’s selector process conjecture, with applications to rounding fractional covers and Bernoulli Sudakov minoration, expanded preprint, 2026. arXiv:2412.03540v2. doi:10.48550/arXiv.2412.03540.
- [17]Michel Talagrand, Are many small sets explicitly small?, in Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC ’10), ACM, New York, 2010, pp. 13–36. doi:10.1145/1806689.1806693. Author’s version.