A small collection of large subsets covering all small subsets.

Question

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.

Answer 1

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.