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

Question

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.

Answer 1

Are covering numbers what you had in mind? Their (v,k,t) corresponds to your (N,X,K), if I'm not mistaken. Generally these covering numbers are very hard to compute, even for moderate values of (N,X,K). But perhaps asymptotic results are known that would help with the particular very large sizes that interest you.

Answer 2

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.

Added: Lost Links

[New Constructions for Covering Designs -- Gordon et al, 1995]

[Asymptotically Optimal Covering Designs -- Gordon et al, 1995]

[Handbook of Combinatorial Design, chapter excerpt by Gordon and Stinson]