Ytukyg

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 ${nchoose 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 $ADelta B=(Asetminus B)cup (Bsetminus A)$ of sets $A$ and $B$. Namely, put $$Delta(mathcal D)=frac 12min{| ADelta B |: A,Binmathcal D,, Ane B}.$$ Clearly, $1le Delta(mathcal D)le x$ for each $(n,x,y)$-design $mathcal D$.

Assume that $Delta(mathcal D)ge d$. There are ${nchoose x-d+1}$ different subsets of the base set of size $x-d+1$. Ot the other hand, each member of $mathcal D$ has ${xchoose 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)<d$. This gives us an inequality $s{xchoose x-d+1}le {nchoose 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-1choose x-1})$-design and $Delta(mathcal D)=1$.

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