# how to cover set of k-combinations of M with subsets of M

I'm working on an application for which I want to take the set $C$ of all the possible $k$-combinations of elements in $M$ (with $||M|| = m$), and cover $C$ with the sets of $k$-combinations of subsets $N_i$ of $M$, with $||N_i|| = n < m$ $\forall$ $N_i$

So there are $m \choose k$ combinations to cover, and each set $Q_i$ of $n$ elements will contain $n \choose k$ combinations.

What I'd like is an algorithm that constructs the sets $Q_i$ such that $q$ is minimized (i.e., as close to $m \choose k$ $/$ $n \choose k$ as possible)

So, for example, if $m = 100$, $k = 3$, and $n = 10$, I would want the smallest set of sets of $10$ elements such that their respective sets of $3$-combinations covered the set of $100 \choose 3$ $3$-combinations of M.

-

## 1 Answer

The magic words are "design" (if the minimum can be realized) and "covering design" otherwise. There is a vast literature and no algorithm.

-
it's amazing how important it is to know which words to search for. thanks chris! i am obviously not a professional mathematician, so i didn't know where to look. –  tvladeck May 30 '12 at 22:00
La Jolla covering repository. And there are algorithms, they are just not guaranteed optimal in all cases. If pretty good is acceptable, there are a few such. A paper by Kuperberg (and Patashnik and others?) provides a good reference point and some algorithms. Gerhard "Ask Me About System Design" Paseman, 2012.05.30 –  Gerhard Paseman May 30 '12 at 22:44
Thanks Gerhard! Pretty good, in this case, is definitely acceptable, and in retrospect I should have made that clear. I will check the La Jolla repository. –  tvladeck May 30 '12 at 23:32