Lower bounding the maximum size of sets in a set family with union promise

Question

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.

Answer 1

This problem has enough parameters to easily confuse. I will add some trivial cases to help motivate the problem, and encourage the poster to provide some more.

Of course, arranging that every set in S contains one of the sets in the given collection C shows that there is a solution with $s > c$; what is wanted is $s <= c$.

For $k=2$ and disjoint sets $C_1$ and $C_2$, both of size $c$, getting $s < c$ seems challenging because you have to choose at most half the sets of S. I can imagine a case where epsilon times $m > 2$, and then reducing to the case of $k=1$ and (epsilon times $m$) also being reduced by 1, but this implies constraints on n,m and epsilon and it is not pretty, at least to me. However,a pigeonhole argument should work for the case of $n$ disjoint equinumerous $C_i$ as it does for $n=1$, provided m and epsilon fit some narrow constraints, again getting $s > c(1-$ epsilon).

If C contains all subsets of size $r$ of an $n$ set, one can choose s=1, as long as $m$ and epsilon play nice. If epsilon is less than 1/2, then $2r < n$. For larger $r$, one can try mostly disjoint sets in S of larger size; the problem reminds one of doing certain kinds of covering designs.

As my understanding of the problem develops, I will add to this. It seems to help if one relaxes the constraints on s and epsilon, and then looks for more challenging bits as you try to impose some constraints on groups of parameters. Even so, I encourage Artem to provide more motivation.

Gerhard "Ask Me About System Design" Paseman, 2011.07.15