TOPICS
Search

Fractional Expectation Threshold

Let F subset= 2^V be an increasing family. It is weakly p-small if there are weights lambda_S>=0, indexed by subsets S subset= V, such that

sum_(S subset= I)lambda_S>=1 for every I in F
(1)

and

sum_(S subset= V)lambda_Sp^(|S|)<=1/2.
(2)

The fractional expectation threshold is

q_f(F)=sup{p:F is weakly p-small}.
(3)

It is the linear-programming relaxation of the expectation threshold, so q(F)<=q_f(F). Talagrand's expectation-threshold conjecture asks whether the reverse inequality holds up to a universal constant.

See also

Expectation Threshold, Linear Programming

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.

Cite this as:

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

Subject classifications