What is the minimum number of covering subsets?

Question

Fix a positive integer constant $C$.

Let $S_1, S_2, \cdots , S_k$ be subsets of $\{ 1, 2, \cdots , N \}$. Let us call $S_1, S_2, \cdots , S_k$ a $C$-cover if for every subset $T$ of $\{ 1, 2, \cdots , N \}$, there exists $i_1, i_2, \cdots , i_C$ not necessarily distinct such that $T\subseteq S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_C}$ and $C \cdot |T| > |S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_C}|$

For all positive integers $N$, What is smallest such $k$ so that there exists $k$ subsets that form a $C$-cover.

I'm not looking for an exact answer but rather asymptotic bounds. Specifically, I'm wondering if the minimal $k$ is polynomial in $N$.

I'm sorry if I'm stating this really badly.

Answer 1

Let $C=2$. Consider sets $T$ of some fixed cardinality $m$. There are $\binom Nm$ of such sets. Each of them must be covered by some set of the form $S_{i_1}\cup S_{i_2}$ of cardinality at most $2m$. A set of cardinality $\le 2m$ can cover no more than $\binom{2m}m\le 2^{2m}$ sets of cardinality $m$. Hence you need at least $2^{-2m}\binom Nm$ of distinct sets of the form $S_{i_1}\cup S_{i_2}$. But there are only $k(k+1)/2\le k^2$ sets of the form $S_{i_1}\cup S_{i_2}$. Hence $k\ge 2^{-m}{\binom Nm}^{1/2}$.

For a fixed $m$ and $N\to\infty$, $\binom Nm\sim c(m)N^m$, hence $k$ grows faster than a polynomial of degree $m/2$. And since $m$ is arbitrary, $k$ grows faster than any polynomial. To get an explicit exponential lower bound, take $m=N/4$ and use Stirling's formula to estimate the binomial coefficients.

For a larger $C$, the same argument shows that $k$ grows faster than any polynomial (the only difference is that you get degree $m/C$ rather than $m/2$). I have not checked the exponential lower bound but I am sure a suitable choice of $m$ will do it.

Answer 2

Thanks for the response. Yes, $T$ is nonempty. The $>$ should be a $\ge$.

So $C$ is constant, but $N$ is not. I guess it's safe to assume that $N >> C$.

Sorry I didn't take note of the edge cases. I'm really only interested in an asymptotic bound for the minimum $k$ in terms of $N$ and $C$ and the constructions for the bounds.