Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X$ be a ground set, and consider a collection $\mathscr{S}$ of subsets of $X$, $\mathscr{S} = \{S_1, \dots, S_n\}$.

We would like to find a collection $\mathscr{S}'$ with the property that for all $S \in \mathscr{S}$, there is some $S' \in \mathscr{S}'$ such that $S' \subseteq S$. We might also want $\mathscr{S}'$ to satisfy additional properties, such as that elements of $\mathscr{S}'$ have a certain minimum cardinality.

Is there any name for this type of design? It is similar to the set cover problem or hitting-set problems, but doesn't seem to fit exactly. Any references would be appreciated.

share|cite|improve this question
It would appear to be a generalization of a covering design. – Chris Godsil Feb 14 '13 at 14:47
I find the notation confusing as it appears $S'$ has two meanings. – hardmath Feb 14 '13 at 14:50
It also appears that there's a condition missing, since the collection $\{\emptyset\}$ appears to satisfy the minimum cardinality condition. – hardmath Feb 14 '13 at 14:54
I stated that there may be additional requirements on $\mathcal S'$, such as a minimum cardinality for its elements, but I want to be vague about those extra requirements. – David Harris Feb 14 '13 at 14:57
@DavidHarris : by being vague about those extra requirements do you actually mean the extra requirements could vary? Please let me know if in this case actually being vague is intentional by design to satisfy a specific generalisation in the solution. If so that would be intresting – Arjang Feb 14 '13 at 20:51

Your Answer


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

Browse other questions tagged or ask your own question.