How many ways are there to form a complete graph as the union of triangles?

Question

Consider the complete graph on n vertices. How many ways are there to form this graph by unioning together triangles?

The triangles are distinct but may overlap.

Answer 1

For $3\le n\le 12$:
1, 5, 388, 477965, 19199206747, 48058624241034238, 14791854612528152343049939, 112039538006858119010793653395340973, 42077073837090084518028123082446810913910363417140, 1580746220785841888200914891451910938106730059214980821153579470917.

The next value is computable but expensive. I added it to OEIS as A302394.

Let $\mathcal{G}_n$ be the set of unlabelled graphs of order $n$. For $G\in\mathcal{G}_n$, let $a(G)$ be the order of its automorphism group, $e(G)$ be the number of edges in its complement, and $t(G)$ be its number of triangles. Then the number of sets of triangles which cover every vertex-pair is $$ \sum_{G\in\mathcal{G}_n} \frac{n!}{a(G)} (-1)^{e(G)} 2^{t(G)}.$$

The formula is a standard inclusion-exclusion. $n!/a(G)$ is the number of labelled graphs isomorphic to $G$. An event is a vertex-pair that is not covered. $2^{t(n)}$ is the number of sets of triangles that don't cover any edge in the complement of $G$.

If $t_r=t_r(n)$ is the contribution to the above sum for $e(G)=r$, apart from the $(-1)^{e(G)}$, then the summation $t_0-t_1+t_2-\cdots$ has the Bonferroni property: its partial sums alternate above and below the full sum. I calculate: $$\eqalign{ t_0 &= 2^{\binom n3} \\ t_1 &= t_0 \, (n-1)\,n\,2^{1-n} \\ t_2 &= t_0 \, (n-1)(n-2)(n+5)\,n \,2^{1-2n} \\ t_3 &= t_0 \, \tfrac13\,(n-1)(n-2)(n^3+12n^2+39n-220)\,n\,2^{2-3n}, }$$ which gives very narrow bounds already.

Answer 2

Leaving the cases of $n \lt 3$ to others, I note there is exactly one such subset of triangles when $n=3$ and 5 subsets (whose edge union is the set of all edges of $K_n$) when $n=4$. I am guessing the name of the game is to enumerate such distinct subsets (effectively meaning the edges are labelled).

For $n=5$, the game becomes a challenge. $K_5$ contains 10 triangles, and of the collections of triangles at most four in number, one finds 10 subsets which cover. This is because such covers require three triangles to share an edge. Every subset of 8 or more triangles cover, while only 10 subsets of 7 triangles do not cover. For each of these 10 subsets of 7 triangles, there are 7 subsets of six which also do not cover and 21 subsets of 5, of which six of these 21 are involved in double counting, giving 10 + 70 + 150 + 6*10/2 = 260 subsets of five to seven triangles which do not cover. Combine this with the 1+ 10 + 45 +120 + (210-10) small subsets which do not cover gives 636 non covering subsets of triangles, meaning 388 subsets do cover for $n=5$.

For larger n, the fraction of all subsets that do not cover is less than (n choose 2)/2^(n-2), which is less than 1 for $ n \gt 5 $, and decreases almost exponentially. Thus for n at least ten, greater than 80% of all the subsets of triangles cover the graph, so 2^(n choose 3) is within a small multiplicative factor of the correct number of covering subsets. Assuming montonicity of the growth of this ratio for n greater than 3, at least 5/16 of all subsets of triangles cover the graph.

Gerhard "That's A Lot Of Subsets" Paseman, 2018.04.05.