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.

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.

share|improve this question
add comment

2 Answers

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]

share|improve this answer
    
Good answer, and thanks for the lost links. –  Byron Schmuland Jan 5 '11 at 15:49
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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