Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $r,s,n$ be positive integers with $r < s < n$. Let $U = \{1,\ldots,n\}$.

Let $S$ contain $s$-element subsets of $U$ (of our choosing). What is that smallest we can make $S$ such that every $r$-element subset of $U$ is a subset of some element in $S$?

I'm curious what the best known upper and lower bounds are on the smallest we can make $S$, and I am especially interested in the case where $r << s << n$. I am more worried about asymptotic behavior than exact bounds.

This can also be viewed as a special case of a set-cover problem that has a lot of symmetry. I'm afraid/hoping there's something simple from graph theory that solves my problem.

EDIT: Thanks to @Gerhard, I see this is a well known problem called covering numbers / covering designs.

share|improve this question
3  
www.ccrwest.org/cover.html , the La Jolla covering repository, should be your first stop. Let us know what it does not answer. Gerhard "Ask Me About System Design" Paseman, 2010.10.13 –  Gerhard Paseman Oct 14 '10 at 5:23
add comment

1 Answer 1

up vote 8 down vote accepted

What you are looking for is an $(r,s,n)$-covering design. A good starting point might be the La Jolla Covering Repository or in fact, any book on design theory. In general, the smallest possible size for your covering design is given by $\binom{n}{r}/\binom{s}{r}$ in which case every $r$ -element subset is contained in exactly one $s$-element subset and the design is then called a $(r,s,n)$-Steiner system. There are necessary conditions for Steiner systems to exist such as $\binom{s-i}{r-i} | \binom{n-i}{r-i}$ for all $i$. Quite a lot is known about the existence of $(2,3,n)$-Steiner systems, and $(3,4,n)$-Steiner systems, but in general their existence is an open question.

share|improve this answer
    
Thank you -- this is perfect. It seems Erdos and Spencer give an upper bound of (1+\ln(C(s,r)))C(n,r)/C(s,r), which is perfect for my purposes! If I had enough reputation, I would upvote your answer : –  Lev Reyzin Oct 14 '10 at 5:40
add comment

Your Answer

 
discard

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

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