TOPICS
Search

Talagrand's Discrete Convexity Conjecture

Talagrand's discrete convexity conjecture asserts that a sufficiently likely family of subsets of a finite set covers, by a universal number of unions of its members, every set outside an exceptional family with inexpensive containment witnesses (Talagrand 2021, Research Problem 13.3.2). For a positive integer N, put [N]={1,...,N}. For 0<p<1, let mu_p be the product measure on the power set 2^([N]) obtained by including each element independently with probability p. For an arbitrary family D subset= 2^([N]) and a positive integer k, put

E_k(D)={S subset= [N]:S !subset= D_1 union ... union D_k for every (D_1,...,D_k) in D^k}.

The chosen members may repeat and need not be disjoint. For example, if D consists of all subsets with at most m elements for a nonnegative integer m, then E_k(D) consists of those with at least km+1 elements.

A family A is p-small if there is a family G subset= 2^([N]) such that every S in A contains some I in G and sum_(I in G)p^(|I|)<=1/2. This is the covering notion used to define the expectation threshold and implies mu_p(A)<=1/2 by the first of the Bonferroni inequalities. The conjecture states that some universal positive integer k satisfies

mu_p(D)>=1-1/k implies that E_k(D) is p-small.

The same parameter p is used for the starting product measure and the covering cost.

See also

Expectation Threshold, Power Set

Explore with Wolfram|Alpha

References

Talagrand, M. Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems, 2nd ed. Cham, Switzerland: Springer, 2021. https://doi.org/10.1007/978-3-030-82595-9.

Cite this as:

Weisstein, Eric W. "Talagrand's Discrete Convexity Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TalagrandsDiscreteConvexityConjecture.html

Subject classifications