Is the following known? It seems related to codes and/or Ramsey theory.

Given $r$, for what values of $n,k$, does there exist a collection of $n$ sets whose union contains $k$ elements such that none of these sets is contained in the union of at most $r$ of the sets.

For example given $r<3$ choosing $n=3$, $k=4$ satisfies the requirement, because of $\{\{1,2\},\{2,3\},\{3,4\}\}$. More generally if $r=2$ then any $n$ and $k>n$ satisfies the requirement by generalizing this example.

For $r=1$ with any $n$, and $k>\lceil \log_2(n)\rceil$ one can satisfy the requirement by numbering the sets in order and using the binary representation of their number (like a Hamming code). This argument can be used to show (information theoretic) lower bounds of $k>\lceil r \log_2(n)\rceil$.


Erdos Frankl and Furedi, "Families of finite sets in which no set is covered by the union of r others} Israel Journal of Mathematics 51 (1–2): 79–89, 1985.

Let $f_r(n,k)$ be the maximum number of $k-$subsets of an $n$-set satisfying the condition above. Then $$ f_r(n,r(t-1)+1+d)\leq \frac{\binom{n-d}t}{\binom{k-d}t}, $$ for $n$ sufficiently large whenever $d=0,1$ or $d\leq \frac{r}{2t^2}$ with equality holding iff there exists a Steiner Triple System $S(t,r(t-1)+1,n-d)$.

One application is non-adaptive group testing, and the area has been recently active as well. For example see

Indyk, Ngo, Rudra. "Efficiently decodable non-adaptive group testing". Proceedings of the 21st ACM-SIAM Symposium on discrete algorithms (SODA), 2010.


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.