# Minimum number of X-subsets needed to cover all K-subsets

Assume I have a universe of N elements.

The question is: How many sets of size $X$ are needed to assure that every set of K elements is a subset of (at least) one of these sets (where $K \ll X \lt N$). And also, how can these sets be chosen to obtain this minimum?

In particular, the sizes that interest me are: \begin{align*} N &= O(2^{n^{c_1}}),\\ X &= O(2^n),\\ K &= O(n^{c_2}), \end{align*} where $n$ is a variable, $c_1$ and $c_2$ are constants.

-

What you are asking about are called covering designs. A more standard notation in combinatorics defines $(v,k,t)$-covering design to mean:

$v =$ total number of points (your universe N)
$k =$ size of subsets (blocksize, your set size X)
$t =$ size of covered combinations (your K elements)

There is a special case where each t-subset is covered exactly once, and these are known as Steiner systems. Obviously in those cases the number of blocks used is a minimum.

The minimum number of blocks ($k$-subsets) needed to cover all $t$-subsets of a "universe" of size $v$ is termed $C(v,k,t)$, and there is no general formula for it. In fact not much is known for values of $t$ more than ten.

There is a well-known general lower bound for $C(v,k,t)$ called the Schönheim inequality:
$$C(v,k,t) \ge \lceil (v/k) * C(v-1,k-1,t-1) \rceil$$ which can be applied recursively down to the case $t=1$, where trivially: $$C(v,k,1) = \lceil v/k \rceil$$

I think it is known that this lower bound is fairly tight for sufficiently large $v$. The La Jolla Covering Repository (linked above) has some good papers on constructing covering designs, but they seems to have gotten hidden when the site underwent a redesign awhile back. I'll see if I can ferret them out and post those lost links.