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

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?

• If you just need this one case I would start with brute force. Write down all $15$ subsets of $4$ (in alphabetical order) and then play with breaking them down into pairs of pairs. Jul 30, 2019 at 15:56
• That's been the strategy thus far, but it's proving a little more challenging than I thought! Also, I'd like to be able to develop at least a rudimentary area of how to approach it because I will have other similar problems like this to solve in the future. Jul 30, 2019 at 16:01
• Fair enough. I don't know where your "should be solvable with $9$" comes from. I have my doubts. Upvoting the question. Jul 30, 2019 at 16:04
• Thanks, the idea was that each element would have to appear at least three times, but each each two-element set would count as two, so (6*3)/2 = 9. IT's quite possible that my logic is faulty here! Jul 30, 2019 at 16:11
• It isn't, I've got a nine pair solution, just writing down the reasoning. Lot of educated guess work though. Jul 30, 2019 at 16:12

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

• this is amazing. Thanks so much! Jul 30, 2019 at 16:30

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.

• this is great. thanks so much! Jul 30, 2019 at 16:31

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. Let $$Q = \{(i,j,k,\ell):i. 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.