The following problem has come up while working on the relationship between certificate and randomized decision tree complexities of boolean functions. However, I think it is of interest by itself and some variants of it might have already been studied:

Given $k$ finite sets $C_1, ..., C_k$, such that $|C_j| \geq c$ for every $1 \leq j \leq k$. Let $\mathcal{F}$ be a family of sets $S_1, ..., S_m \subseteq \{1,...,n\}$ with $s = \max_{1 \leq j \leq m} |S_j|$ such that for any $\epsilon m$ distinct indexes $i_1 ... i_{\epsilon m}$ there exists a $1 \leq j \leq k$ such that $C_j \subseteq S_{i_1} \cup ... \cup S_{i_{\epsilon m}}$.

What is the minimal $s$ as a function of $c,k,m\;\text{and}\;n$?

Some further (optional or obvious constraints)

• $c \leq n$ and in general $c$ is a function of $n$.
• $k$ can be anything and is a function of $n$ and $c$. Usually $k$ is greater than $n$ and $c$, although even the case of $k = 2$ is interesting.
• $m$ can be anything, but the more interesting case is when $m >> n$.
• $\epsilon$ can be assumed to be any constant strictly less than $1/2$. Although non-trivial results for $\epsilon = l/m$ with some constant integer $l$ are also interesting.

If $k = 1$ then $s \geq (1 - \epsilon)|C_1|$ by a simple pigeon hole argument. I don't know any non-trivial bound for $k = 2$, but obviously we are interested in the case of $C_1 \cap C_2 = 0$.

Alternatively, if $C_1, ..., C_k$ are all the $(\lfloor n/2 \rfloor + 1)$-element subsets then there exists an $\mathcal{F}$ such that $s = 3$. What happens if $C_1,...,C_k$ are all the $r$-element subsets?

This seems like a relatively natural question, and I would be surprised if something similar has not been asked before. Any pointers to the literature or partial results are appreciated. If this has not been studied, then can you recommend any tools or approaches with which to answer this question?

As per request, a more formal statement:

Let $n,m$ be positive integers, and $0 \leq \epsilon < 1/2$ -- a constant.

Fix $C_1, ..., C_k \subseteq \{1,...,n\}$.

Solve:

$s = \min_{S_1, ..., S_m \subseteq \{1,...,n\}} \max_{1 \leq j \leq m} |S_j|$

such that:

$\forall I \subseteq \{1,...,m\} \; \exists j \in \{1,..,k\} \quad (|I| \geq \epsilon m) \Rightarrow (C_j \subseteq \bigcup_{i \in I} S_i)$

The question also works if we replace $\max_j |S_j|$ by $\mathbb{E}_j[|S_j|]$ or by assuming that $|S_i| = |S_j|$ for any $1\leq i < j \leq m$, but I am not sure how that helps.