3
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ I found a related question on MO. The discussion is about covers by 4-cycles, but I think that the reasoning in the accepted answer can be adapted to the 3-cycle case. If my understanding is correct, the minimum should be $\lceil {n \choose 2} /3 \rceil$ in favorable cases. $\endgroup$ Commented Feb 18, 2021 at 0:51
  • 1
    $\begingroup$ Hmm, no, that post is about covering the edges of the underlying complete graph. Take the OP's $K_5$ example: draw 5 points on a piece of paper, draw the cycles as he listed them, and you'll get a fully connected graph. $\endgroup$ Commented Feb 18, 2021 at 10:16
  • 1
    $\begingroup$ By the way, Peter Heinig's first comment to the question explains precisely what the question (and solution) is about. $\endgroup$ Commented Feb 18, 2021 at 10:18
  • 1
    $\begingroup$ Thanks alot, I think you are right, but the guess of $\lceil{{n\choose 2}/3}\rceil$ seems highly unlikely given that for the provided example it would mean only 2 of the subsets would suffice to create a cover, but It seems almost impossible to me. $\endgroup$ Commented Feb 18, 2021 at 10:33
  • 2
    $\begingroup$ As long as $n\equiv 1$ or $3\pmod 6$, you can achieve $\binom{n}2/3$ triangles using a Steiner triple system of order $n$. See doi.org/10.7146/math.scand.a-10551 for the details. $\tag*{}$For other values of $n$, you can take a the smallest $m\ge n$ such that $m\equiv 1$ or $3\pmod 6$, take a Steiner triple system of order $m$, and restrict all of the triangles to a subset of size $n$. For example, if $n=10$, choose $m=13$, and then if e.g. the triangle $\{1,4,12\}$ appears, replace it with $\{1,4,x\}$ for some $x\in \{1,\dots,10\}$. $\endgroup$ Commented Feb 18, 2021 at 16:34

1 Answer 1

Reset to default
2
$\begingroup$

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

Charles J. Colbourn and Jeffrey H. Dinitz. 2006. Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications). Chapman & Hall/CRC.

Skolem, T. (1958). Some Remarks on the Triple Systems of Steiner. MATHEMATICA SCANDINAVICA, 6, 273-280. https://doi.org/10.7146/math.scand.a-10551

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.