Make 1000 USD from simple combinatorics (M. Talagrand)

Problem's Description

Make 1000 USD from simple combinatorics. This is Research Problem 12.5.6 of the book Upper and Lower Bounds. You have to have a look at the book to get the connection between this problem and stochastic processes, but the problem can be understood without knowing anything about this book.

Consider a number $\delta \leq 1/2$, an integer $N$, and the product measure $P$ on $\{0, 1\}^N$, when on each factor one gives mass $\delta$ to $1$ and $1-\delta$ to $0$. Given an integer $q$ and a set $D \subset \{0,1\}^N$, we define ($x= (x_1, \dots, x_N) $) $$ D(q) = \{x \in \{0,1\}^N; \forall (x_1, \dots, x_{qN}), \dots, (x_{q1}, \dots, x_{qN}) \in D, \exists i \leq N, x_i = 1, x_{1i}, \dots, x_{qi} = 0\}. $$ If one identifies points in $\{0, 1\}^N$ with subsets of $\{1, \dots, N \}$, then $D(q)$ is simply the collection of subsets of $\{1, \dots, N \}$ that cannot be covered by $q$ elements of $D$. Also, $P$ is the law of a random set $J$ obtained as follows: for each $i \in \{1, \dots, N\}$, the probability that $i \in J$ is $\delta$, and these probabilities are independent over $i$.

Given a subset $I$ of $\{0, 1\}^N$, we denote $$ B(I) = \{(x_1, \dots, x_N) \in \{0,1\}^N; \forall i \in I, x_i = 1\}. $$ This is simply the collection of subsets of $\{1, \dots, N \}$ that contain $I$.

Problem. Can one find a number $q$, independent of $N$ and $\delta$, such that for each set $D$ with $P(D) \geq 1 - 1/q$ we can find a family $G$ of subsets of $\{1, \dots, N\}$ such that $$ D(q) \subset \bigcup_{I \in G} B(I) \quad \text{and} \quad \sum_{I \in G} X_{\delta}^{\text{card}I} \leq 1/2? $$ If, rather than the above condition, you obtain the weaker condition that $$ \sum_{I \in G} X_{\delta'}^{\text{card}I} \leq 1/2, $$ where $\delta'$ depends on $\delta$ only, you get the money. (The case $\delta = 1/2$ won’t get you anything; $q = 2$ works.)

This problem is discussed in great detail in Are many small sets explicitly small?, STOC '10 Proceedings of the 2010 ACM International Symposium on Theory of Computing, 1335, ACM, New York, 2010. Problems related to this one (but in some sense less basic) are explained in my paper Are all sets of positive measure essentially convex ? Operator theory: Advances and applications. Vol. 77, Birkhäuser, 1995, p. 295-310.

1. OtherIs an originMake $ 1000 from simple combinatorics

   • Michel Talagrand

   fulltext