TOPICS
Search

Expectation Threshold


Let V be a finite set and let F subset= 2^V be an increasing family. The family is p-small if there is a collection G subset= 2^V such that every member of F contains a member of G and

 sum_(S in G)p^(|S|)<=1/2.

The expectation threshold is

 q(F)=sup{p:F is p-small}.

The name comes from the first-moment obstruction: in the binomial random subset V_p, the expected number of members of G contained in V_p is the sum above.

Allowing nonnegative fractional weights on the witness sets gives the fractional expectation threshold q_f(F). Talagrand conjectured that q(F)>=q_f(F)/L for a universal constant L. Dubroff, Kahn, and Park (2026) prove the restricted statement in which the fractional witness is supported on sets of bounded size, with a constant depending on that bound.


See also

Fractional Expectation Threshold

Explore with Wolfram|Alpha

References

Dubroff, Q.; Kahn, J.; and Park, J. "Note on a Conjecture of Talagrand: Expectation Thresholds vs. Fractional Expectation Thresholds." Electron. J. Combin. 33, P3.77, 2026. https://doi.org/10.37236/14247.Kahn, J. and Kalai, G. "Thresholds and Expectation Thresholds." Combin. Probab. Comput. 16, 495-502, 2007.

Cite this as:

Weisstein, Eric W. "Expectation Threshold." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ExpectationThreshold.html

Subject classifications