# form subsets such that each pair of elements occurs in a subset equally often

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?

• For $n=6$, $k=3$, I think $123, 145, 346, 256, 126, 146, 135, 356, 245, 234$ works. – 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)$$.