Let $D= \{a_1,a_2,...,a_n\}$ be a set of constants. For any subset of $D$ of cardinality $3$, we define another set (we call it hyper-edge) containing all $3 \choose 2$ pair-wise combinations (we call them nodes) of the constants. How can I compute the minimum number of hyper edges required to cover all such pair-wise combinations of constants in $D$ in general ?
I did the first non-trivial example:
Example: $D = \{a_1,a_2,a_3,a_4\}$, In this case you have $4$ possible subsets, each giving us 3 nodes in a hyper edge, and picking any three such hyper-edges or any three such subsets gives us a complete cover. I list all possible hyper edges below:
- ${a_1a_2 , a_1a_3, a_2a_3}$
- ${a_1a_2 , a_1a_4, a_2a_4}$
- ${a_2a_3,a_3a_4,a_2a_4}$
- ${a_1a_4,a_1a_3,a_3a_4}$
You can take any three of these subsets and it has all the pairwise nodes.
What you are looking for is known in the literature as a covering design. You want $C(n,3,2)$, where $C(v,k,t)$ is the minimum number of $k$-element subsets which cover all $t$-element subsets of a given $v$-element set.
It is proven in the CRC Handbook of Combinatorial Designs (2nd ed.) that $$ C(n,3,2)=\left\lceil\frac{n}3\left\lceil\frac{n-1}2\right\rceil\right\rceil. $$ It is easy to prove that at least this many triangles are necessary. There are $n-1$ edges at each vertex, and each triangle covers at most two edges of a given vertex. Therefore, each vertex has a quota of $\left\lceil\frac{n-1}2\right\rceil$ triangles, for a total quota of $n\cdot \left\lceil\frac{n-1}2\right\rceil$, and each triangle contributes $3$ points to the total quota.
Finding these optimal covering designs is the hard part. When $n\equiv 1$ or $3\pmod 6$, you can use a Steiner triple system of order $n$, whose construction is described in [Skolem]. For the other congruence classes $\pmod 6$, the constructions are described in detail in the CRC Handbook on Combinatorial Designs (2nd ed), chapter $11$, section $5$, subsection $11.41$. They are too complicated for me to describe here.
If you just need some explicit designs for small $n$, they can be at Dan Gordon's web page, or the La Jolla covering repository (these give the same data).