1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Max Horn
    Sep 9, 2010 at 22:26

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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