Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
If T is empty, then $C \cdot |T| = 0$ which cannot exceed $|S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_C}|$. So maybe you want to assume $T$ is not empty? Or make the inequality non-sharp? Likewise, if $T=\\{1,\cdots,N\\}$ then $|T| = N = |S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_C}|$ so that would preclude the possibility $C=1$. Maybe this is intentional, though? Moreover, if $C>N$ then your inequality is automatically satisfied (except for the edge cases I mentioned above). Again, possibly intentional? Perhaps you could clarify a bit what you intended in these edge cases? –  Max Horn Sep 9 '10 at 22:26

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.