1
$\begingroup$

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.)

$\endgroup$
0
$\begingroup$

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)<d$. 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.

$\endgroup$

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.