For given $n$ and $k$, I want to form subsets with $k$ elements each from a base set of $n$ elements such that each pair of different elements $(e_i,e_j)$ is contained in the same subset equally often. As this is part of larger project in which I will have to do some computations for each subset I would like to find a solution with as few subsets as possible.

Some solutions for small n and k may help to illustrate the problem and what kind of solution I am searching for:

A trivial solution for all n and $n\ge k \ge2$ is to take all $\binom{n}{k}$ subsets. For this solution we need $\binom{n}{k}$ subsets, but all pairs of elements occur equally often, namely in $\binom{n-2}{k-2}$ subsets.

For $k=2$ this is also the best we can do, as there are $\binom{n}{2}$ pairs and we only cover one pair for each subset with two elements.

As a very concrete example for $n=4$ and $k=3$ with elements 1,2,3,4 we have to do the following 4 subsets: 123, 124, 134, 234 in which each pair occurs twice.

The smallest number, where I am currently unsure of the answer are $n=6$ and $k=3$. Is there a solution which requires only 10 instead of 20 subsets?

But how does this look in general? Are there any solutions which need less than $\binom{n}{k}$ subsets?

  • 1
    $\begingroup$ For $n=6$, $k=3$, I think $123, 145, 346, 256, 126, 146, 135, 356, 245, 234$ works. $\endgroup$ – Jaap Scherphuis Aug 28 '20 at 14:52

A family of $k$-subsets where each pair occurs $\lambda$ times is called a $2$-design or BIBD or more specifically a $(n, k, \lambda)$-design. They are a special case (and it seems historically the first case?) of block designs.

If I understand correctly, you seem to be seeking, for given $n, k$, the smallest $\lambda$ (which would of course determine the smallest such family). This question is not specifically addressed by that wikipedia article, but since the field is almost a century old hopefully you can find the results somewhere else now that you have some search terms. However, I would not be surprised if you cannot find a general formula for arbitrary $(n, k)$.

Good luck!

  • $\begingroup$ Thanks, This is indeed helpful as a guide for where to look! The btw is wrong though, all pairs which are in separate subsets do not occur... $\endgroup$ – Xenon Aug 30 '20 at 13:21
  • $\begingroup$ Hahaha, of course, what was I thinking! :D I deleted that part now. Sorry! $\endgroup$ – antkam Aug 30 '20 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.