Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
show 1 more comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.