0
$\begingroup$

Let $K_n$ be a complete graph, I am interested in knowing the minimum number of triangles required to get a edge cover of $K_n$. In case there is no closed-form solution to this problem, then I would like to know the best known upper bound (the naive bound is $n\choose 3$ i.e all possible triangles).

An example:

Let $K_4 = \{1,2,3,4\}$, then any three of the following triangles make a full edge cover on $K_4$:

{1,2,3}

{1,2,4}

{1,3,4}

{2,3,4}


Furthermore, I would also like to add a generalisation i.e you assign a weight $w$ to each triangle such that $w \in [0,1] $, now I want to have a cover that minimises the sum of $w$, given that each edge's weight contribution sums to more than one.

What is the lower bound on this sum ?

$\endgroup$
9
  • 2
    $\begingroup$ Note that this number is asymptotically $\Theta(n^2)$ because there is a trivial ${n \choose 2}$ bound of just covering at least a single new edge in each triangle, and any cover must contain at least $|E|/3 = {n \choose 2}/3$ edges. $\endgroup$ – user3209423940248 Feb 18 at 16:10
  • 1
    $\begingroup$ Each triangle covers only 3 edges. $\endgroup$ – Emil Jeřábek Feb 18 at 16:27
  • 1
    $\begingroup$ A better upper bound is $\lceil\frac12\binom n2\rceil$. If $n$ is odd, then $K_n$ is eulerian; fix an eulerian path, split it in $\frac12\binom n2$ pairs of neighbouring edges, and complete each pair to a triangle. For $n$ even, take a covering of $K_{n-1}$ as above, and use $n/2$ further triangles to cover edges incident to the $n$th vertex. $\endgroup$ – Emil Jeřábek Feb 18 at 16:35
  • 1
    $\begingroup$ Well, these are simple observations, and perhaps someone can figure out the right multiplicative constant yet. Concerning fractional edge covers, this case is much simpler: the $\frac13\binom n2$ lower bound still applies, and now it is in fact the exact optimal value: just take every triangle with weight $1/(n-2)$. $\endgroup$ – Emil Jeřábek Feb 18 at 17:17
  • 3
    $\begingroup$ The sequence is tabulated at oeis.org/A011975, which includes several relevant references and other information. $\endgroup$ – Emil Jeřábek Feb 18 at 18:32
3
$\begingroup$

Let $N(n)$ be the number of triangles needed to cover $K_n$. Because every triangle covers only three of the $n\choose 2$ edges, we have $\frac{1}{3}{n\choose 2}\leq N(n)$ as a lower bound.

Note that the case $n=2$ is degenerate, as $K_2$ has only one edge and no triangles. In the following analysis, I will allow myself to use triangles that cover only one edge (for $n>2$, this is without loss of generality because you can use an arbitrary third vertex to create a triangle).

To obtain an upper bound, we apply divide and conquer as follows. For some $k+m=n$, think of $K_n$ as the union of $K_m$, $K_k$, and $K_{k,m}$. In particular, let's pick $m:=\lfloor n/2\rfloor$ and $k:=\lceil n/2\rceil$. Label the vertices of $K_k$ by $u_0,\dots,u_{k-1}$ and the vertices of $K_m$ by $v_0,\dots,v_{m-1}$. For each edge $\{u_i,u_j\}$ of $K_k$, place the triangle $\{u_i,u_j,v_{i+j\pmod m}\}$. This covers each edge of $K_k$ using $k\choose 2$ triangles, and also covers the edges $\{u_i,v_l\}$ of $K_{k,m}$ as long as $l\neq 2i\pmod m$. We can cover the remaining edges $\{u_i,v_{2i\pmod m}\}$ of $K_{k,m}$ using $k$ triangles.

Now, it remains to cover the edges of $K_m$, which we do recursively. This yields the upper bound $N(n)\leq N(m)+{k\choose 2}+k\leq N(\lfloor n/2\rfloor)+{\lceil n/2\rceil\choose 2}+\lceil n/2\rceil$. For $n\leq 1$, we have $N(n)=0$, so we can write out the recurrence: $$\begin{align}N(n)&\leq \sum_{i=1}^{\log_2 n} \left[{\lceil n/2^i\rceil\choose 2} + \lceil n/2^i\rceil\right]\\ &\leq \sum_{i=1}^{\log_2 n} \left[{\frac{n}{2^i}+1\choose 2} + \frac{n}{2^i} + 1\right]\\ &= \sum_{i=1}^{\log_2 n} \left[\frac{1}{2}(\frac{n}{2^i})^2+\frac{3}{2}\frac{n}{2^i} + 1\right]\\ &= \frac{n^2-1}{6} + \frac{3(n-1)}{2} + \log_2 n\\ &= \frac{1}{3}{n\choose 2} + O(n). \end{align}$$

Therefore, the lower bound is tight up to a linear function of $n$.

$\endgroup$
1
$\begingroup$

If $n$ is congruent to $1$ or $3$ modulo $6$, there is a covering of the complete graph $K_n$ with triangles so that each edge is used exactly in exactly one triangle, so this uses exactly $\frac{1}{3}\binom{n}{2}$ triangles. This is called a Steiner triple system and the answers to this Math Overflow question give some ways to construct Steiner triple systems algorithmically

If $n$ is not congruent to $1$ or $3$ modulo $6$, then you can round it up so that it is, and get a good covering that way, although I believe combinatorists have found even better ones.

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