How to generate a list of two-element sets that make all possible four-elements sets?

Question

I have a list of 6 elements (A...F) that I need to organize into the smallest number of unique two-element combinations (AB, AC, etc) possible so that they form all possible four-element combinations (AB + CD = ABCD). The order of the elements is unimportant and I can use each two-element combination as many times as possible (i.e. AB + CD, but also AB + EF)

I know that:

-There are fifteen possible 4-way combinations and -it should be solvable with 9 two-element combinations

...but I can't figure out conceptually how to generate my list of two-element combinations.

Any ideas on how I could get started on this?

Answer 1

Let's formalize your problem a little:

Given a Universe $U= \{A_1,...,A_n\}$, we're searching for the smallest $C\subseteq \binom{U}{2}$ so that $\binom U 4\subseteq P(C)$.

(Here, $\binom{U}{k} := \{M\subseteq U\mid |M| = k\}$ i.e. $\binom{U}{k}$ consists of all sets of $k$-element subsets of $U$.)

This already gives us a way to brute-force the whole thing:

• Compute $P(\binom{U}{2})$, i.e. the set of all possible combinations of 2-element pairs
• For each element $M\in P(\binom{U}{2})$, test $\binom{U}{4}\subseteq \{K\mid \ \exists S_1,S_2\in M: S_1\cup S_2 = K \}$
• Choose the smallest $M$ that fulfills this test.

Note that this is the raw brute-force algorithm. There are many optimizations, both obvious and unobvious to improve this algorithm.

Answer 2

Workable solution: $AB,\ AC,\ AD,\ EF,\ BC,\ BE,\ CF,\ DE$ and $ DF$.

This was mostly done by brute force but with some insights:

Every letter has to appear at least 3 times in one of the nine pairs. Suppose it did not and we only had $AB$ and $AC$, then $ADEF$ could not be formed. Since there are only $18$ letters in $9$ pairs this means that every letter has to appear exactly $3$ times.

This gives us a start with $AB$, $AC$ and $AD$. It follows we need $EF$. To make $ABCD$ we need to add $BC$, $CD$ or $EF$. Due to symmetry the choice is arbitratry so we can pick $BC$. The rest of the pairs have to contain either $E$ or $F$ to ensure those appear often enough, giving us $BE$, $CF$, $DE$ and $DF$.

Answer 3

You can solve this problem via integer programming as follows. Let binary variable $x_{ij}$ indicate whether pair $\{i,j\}$ (with $i < j$) is selected, and let binary variable $y_{i j k\ell}$ represent the product $x_{ij} x_{k\ell}$, where $\{i,j\} \cap \{k,\ell\} = \{\}$ and $i<k$. Let $Q = \{(i,j,k,\ell):i<j<k<\ell\}$. Then the problem is to minimize $\sum_{i,j} x_{ij}$ subject to \begin{align} y_{i j k\ell} &\le x_{ij} &&\text{for all } i,j,k,\ell\\ y_{i j k\ell} &\le x_{k\ell} &&\text{for all } i,j,k,\ell\\ \sum_{\{i',j',k',\ell'\}=\{i,j,k,\ell\}} y_{i'j'k'\ell'} &\ge 1 &&\text{for all } (i,j,k,\ell)\in Q \end{align} For $n = 6$, this minimum is 9. For general $n \ge 3$, the first several values match $n(n-3)/2$. Maybe one of the interpretations in OEIS entry A000096 applies.