5
$\begingroup$

Let $A_1,A_2,\ldots,A_m,B_1,B_2,\ldots, B_m$ be (not necessarily distinct) subsets of $[n]=\{1,2,\ldots,n\}$. Suppose that each $i\in [n]$ appears in at least $k$ of these $2m$ sets.

I want to find a family of $m$ sets $\{C_i\}_{1\le i\le m}$ to cover $[n]$ (that is $C_1\cup\cdots\cup C_m=[n]$), where $C_i=A_i$ or $C_i=B_i$ for each $1\le i\le m$.

How large $k$ (as a function of $n$) is sufficent for the existence of such a family $\{C_i\}_{1\le i\le m}$. I wonder whether $k>\log_2(n)$ is sufficient.

Is it an 'old' problem? Are there any references? Thanks in advance for any suggestions.

$\endgroup$
14
$\begingroup$

$2^k>n$ is sufficuent. Choose $C_i=A_i$ or $C_i=B_i$ at random, with equal probabilities. The probability that we do not cover given element $s$ is at most $2^{-k}$, thus the expectation of the number of not covered elements is at most $n/2^{k}$, strictly less than 1. Therefore sometimes all elements are covered.

But if $n=2^{k}$, $m=k$, it is not always possible. Consider the vertices of a cube $\{0,1\}^k$ and all $2k$ facets ($A_i$, $B_i$ are parallel facets).

$\endgroup$
  • $\begingroup$ @Petrov. Great, your short answer is very impressive. Thanks a lot. $\endgroup$ – W. Wang May 7 '16 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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