# Subsets of equal size, where each element appears an equal number of times

Suppose I have a set of N unique elements, let's say 12:

{A, B, C, D, E, F, G, H, I, J, K, L}

I would like to construct unique subsets of size X (let's say 3), such that every element in N appears in a subset exactly Y number of times. Order does not matter -- {A, B, C} is the same as {C, B, A}.

1. How would I go about finding the minimum number of subsets required for a given X, Y, and N, or whether such an arrangement is even possible? (Obviously there are cases when it would not be possible -- if X = 1 then Y cannot be greater than 1, etc.)

2. Relatedly: How would I go about finding the minimum number of subsets that are as dissimilar as possible? So for instance, if we choose {A, B, C}, then {A, B, D}, {A, B, E}, etc. should be avoided unless absolutely necessary.

3. Finally: Given an N, and given X>1 and Y>1, how would I go about choosing X and Y such that the minimum is reasonably small? By "reasonably" here I don't necessarily mean a mathematical definition but a practical one.

I've read about the set covering problem and related problems, but none seem to be exactly what I am looking for.

(This isn't homework. It's for a design problem: I have N characters, and I want to come up with traits that apply to X number of characters, such that every character is represented equally with as few traits as possible. So #2 exists to make things the most interesting, and #3 exists so I don't have to write content for hundreds of traits.)

This answer provides a general framework for your problem and considers its partial cases.

A family $$\mathcal D$$ of subsets of a given base set of size $$n$$ consisting of subsets of size $$x$$ such that every element of the base set is contained in exactly $$y$$ subsets of $$\mathcal D$$ we shall call a $$(n,x,y)$$-design. The number $$s=|\mathcal D|$$ of members of an $$(n,x,y)$$-design is uniquely defined by an equality $$ny=sx$$, which counts the number of total occurrences of elements of the base in members of $$\mathcal D$$. Also $$|\mathcal D|$$ is at most the number $${n\choose x}$$ of all subsets of of the base set of size $$x$$.

A natural dissimilarity measure $$\Delta$$ of a design $$\mathcal D$$ can be based on a symmetric difference $$A\Delta B=(A\setminus B)\cup (B\setminus A)$$ of sets $$A$$ and $$B$$. Namely, put $$\Delta(\mathcal D)=\frac 12\min\{| A\Delta B |: A,B\in\mathcal D,\, A\ne B\}.$$ Clearly, $$1\le \Delta(\mathcal D)\le x$$ for each $$(n,x,y)$$-design $$\mathcal D$$.

Assume that $$\Delta(\mathcal D)\ge d$$. There are $${n\choose x-d+1}$$ different subsets of the base set of size $$x-d+1$$. Ot the other hand, each member of $$\mathcal D$$ has $${x\choose x-d+1}$$ such subsets, and none of these subsets can belong to distinct members $$A$$, $$B$$ of $$\mathcal D$$, because otherwise $$\Delta(A, B). This gives us an inequality $$s{x\choose x-d+1}\le {n\choose x-d+1}$$. It becames an equality iff $$\mathcal D$$ is a Steiner system $$S(x-d+1,x,n)$$.

There are known designs $$\mathcal D$$ for some particular cases.

An $$(n,x,1)$$-design exists iff $$x$$ is a divisor of $$n$$. Such designs $$\mathcal D$$ are exactly partitions of the base set into subsets of size $$x$$ and $$\Delta(\mathcal D)=2x$$ for each such $$\mathcal D$$.

A family $$\mathcal D$$ of all subsets of size $$x$$ of the base set is $$(n,x,{n-1\choose x-1})$$-design and $$\Delta(\mathcal D)=1$$.

Maybe later I’ll expand this answer a bit providing more designs.