Is it possible to have t triangles in some graph on n vertices?

Question

Fix $n>4$. Is there a characterization of the set $T_n$ of all natural numbers $t$ such that there is some graph on $n$ vertices with exactly $t$ distinct triangles? For example, it's clear that {$1,2,\ldots,n$} $\subseteq T_n$ and $\binom{n}{3}-1 \notin T_n$; what else can we say?

Answer 1

I will argue that the following are true:

• For any $\epsilon \gt 0$ and all large enough $n$, $T_n$ contains all integers less than $\binom{n}{3}-\epsilon n^2.$

• For any fixed positive integer $c$ there is a finite list of expressions which accounts for all numbers larger than $\binom{n}{3}-cn-n/2$ provided that $n$ is large enough.

For $n \gt 14$ the largest members of $T_n$ are precisely

• $\binom{n}{3}$ then

• $\binom{n}{3}-n+2$ then

• $\binom{n}{3}-2n+r $ for $r=4,5$ then

• $\binom{n}{3}-3n+r $ for $r=6,7,8,9$ then

• $\binom{n}{3}-4n+r $ for $r=8,9,10,11,12,14$

A simple construction and simple bounds are enough to show that $T_n$ contains all integers less than $\binom{n}{3}-n^2.$ The same simple construction with more sophisticated bounds evidently shows that for any $\epsilon \gt 0$ and all large enough $n$, $T_n$ contains all integers less than $\binom{n}{3}-\epsilon n^2.$

First a side result. Every integer can be expressed as a sum of three triangular numbers. I asked elsewhere : What is the smallest positive integer $s=s_m$ which can not be written in the form $$s=\binom{a}{2}+\binom{b}{2}+\binom{c}{2}$$ subject to $\max(a,b,c) \le m?$ For now I will say that obviously, for all $m $, $s_m \ge \binom{m+1}{2} .$

Consider this simple construction: Start with $K_{n-3}$ which already has $\binom{n-3}{3}$ triangles. Adjoin three further vertices $u,v,w$ with no edges between them but allow each to be connected to all, some or none of the other $n-3$ vertices. This will allow all triangle counts of the form $\binom{n-3}{3}+\binom{a}{2}+\binom{b}{2}+\binom{c}{2}$ subject to $\max(a,b,c) \le n-3$ and hence at least everything from $\binom{n-3}{3}$ up to $\binom{n-3}{3}+\binom{n-2}{2}-1=\binom{n}{3}-(n^2-5n+8).$ We may assume by inductive hypothesis and a few very small examples that using $n-1$ or less vertices we can get all counts up to $\binom{n-1}{3}-((n-1)^2-5(n-1)+8)=\binom{n-3}{3}+n-5.$ Hence we can get all counts from $0$ up to $\binom{n}{3}-(n^2-5n+8)$ using this construction.

---

If I understand a rather impressive answer (in a comment) to my question, for any $\epsilon \gt 0$, $s_m \ge (3/2-\epsilon)m^2$ for all large enough $m.$ Hence for large enough $n$ we can get all counts up to $\binom{n-3}{3}+(3/2-\epsilon)(n-3)^2=\binom{n}{3}-(\epsilon n^2+O(n)).$

---

Consider now the largest counts in $T_n.$ They must result from removing only a few edges from $K_n$. Suppose that $c$ edges are removed and let $H$ be the graph formed by the removed edges. If $H$ is $c$ disjoint edges, this kills $c(n-2)$ triangles. In general the number of killed triangles is $c(n-2)-p-2t$ where $t$ is the number of triangles in H (since these triples get counted three times by $c(n-2)$) and $p$ is the number of paths of length two in $H$ which are not part of a triangle in $H.$ To find the exact spectrum of values requires not an enumeration but simply a classification of which triples $c,p,t$ represent possible values for the edge,path and triangle count of graph. Hence all triangle free graphs with $v$ vertices, $c$ edges and degree sequence $d_1,d_2,\cdots,d_v$ give (when removed) the same count: $\binom{n}{3}-\sum_1^v\binom{d_i}{2}.$ We need not know how many ways a certain degree sequence can be obtained, only if it can be realized in at least one one.

Answer 2

As Gerhard Paseman mentions, this may be as hard as enumerating all graphs. If that is indeed the case, you may want to check out this paper by Alon, Yuster and Zwick. In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication. They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$. An elegant technique in this area is the so-called colour-coding method.

Edit 1. A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large). To see this choose $j$ maximal such that $\binom{j}{3} \leq k$. By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$. After some number crunching, this is possible provided $k \leq n^{3/2}$.

Edit 2. Here is some information for $k$ which are not in $T_n$. As Gerhard notes, removing an edge from $K_n$ destroys exactly $n-2$ triangles. Thus, $\binom{n}{3} - t \notin T_n$ for all $t=1, \dots, n-3$. The next triangle-densest graph is obtained by removing two incident edges, which destroys $2n-5$ triangles. Thus, $\binom{n}{3} - t \notin T_n$, for $t=n-1, n, \dots, 2n-6$. The next two triangle-densest graphs are obtained by removing a matching of size 2, which destroys $2n-4$ triangles, or the edges of a triangle, which destroys $3n-8$ triangles. Thus, $\binom{n}{3}-t \notin T_n$ for $t=2n-3, 2n-2, \dots, 3n-9$.

Answer 3

We can give a construction showing that all counts up to $(1+o(1))\binom n3$ can be obtained, confirming Terry's probabilistic approach. Consider graphs consisting, apart from isolated vertices, of a sequence of cliques of size 3 or more, where each clique overlaps the previous one in two edges and otherwise has new vertices. If the cliques have size $k_1,k_2,\ldots,k_m$, then the number of triangles is $t=\sum_{i=1}^m \binom{k_i}{3}$ and the number of vertices is $n\ge 2+\sum_{i=1}^m (k_i-2)$. So the question is, for which $n,t$ do these inequalities have a solution $k_1,k_2,\ldots,k_m$?

Turn it around and ask: given $t$, what is the least $n$ for which there is a solution? (Larger $n$ are obtained by adding isolated vertices.) An upper bound is given by the greedy solution $n=N(t)$: choose $k_1$ to be as large as possible with $\binom{k_1}{3}\le t$ and continue recursively in the same manner. Since $t-\binom{k_1}{3}=O(t^{2/3})$, the $k_1$-clique dominates $N(t)$. To get an explicit bound needs some care, but wouldn't be difficult. I'm pretty sure it shows that, for large $n$, there is a solution for $0\le t\le\binom n3-O(n^2)$.

ADDED: Here are some tentative values of $[n,\Delta_n]$, where the first missing number of triangles is $\binom n3-\Delta_n$. From $n=13$ onwards, I won't swear to them. I just computed all the graphs within 16 edges of a complete graph and counted their triangles. Most seriously, I only eye-balled the output for missing values and could have missed some. The larger values are wobbling around near 0.3 $n^2$.

[4, 1], [5, 4], [6, 6], [7, 11], [8, 19], [9, 23], [10, 27], [11, 31], [12, 42], [13, 47], [14, 52], [15, 66], [16, 72], [17, 78], [18, 98], [19, 105], [20, 112]

Answer 4

I don't know that it would be as hard as enumerating all graphs. There are more than $2^{\binom{n}2}/n!$ graphs but less than $\binom{n}{3}$ possiblities for the number of triangles. Perhaps not a lot fewer though.

$T_4=\{0,1,2,4\}.$ Removing $k=0,1,2$ disjoint edges yields $\binom{n}{3}-k(n-2)$ triangles and removing $2$ non-disjoint edges $\binom{n}{3}-2(n-2)+1.$ These will be the largest four numbers in $T_n$ so $T_5=\{0,1,2,3,4,5,7,10\}.$

It starts to seem easier to have $U_n=\{x \mid 0 \lt\binom{n}{3}-x \notin T_n \}$ so $U_5=\{1,2,4\}.$ The previous comment is that $U_n$ contains all the integers from $1$ to $2n-6$ with the exception of $n-2.$

Once $n \ge 6$ there are $4$ possible cases for removing $3$ edges yielding $\binom{n}{3}-3(n-2)+j$ for $j=0,1,2,3$ Putting this together with the previous observations and the fact that $T_5 \subset T_6$ is enough to establish that $T_6=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,16,20\}$ so $U_6=\{1,2,3,5,6\}$

The reference given by arun, if correct (which I have no reason to doubt) gives

$U_7=\{1,2,3,4,6,7,8,11 \}$ and $U_8=\{1,2,3,4,5,7,8,9,10,13,14,19\}.$ I'll let someone else check the intermediate cases. The last one (if I have not made an error) says that $U_{12}=\{1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,21,22,23,24,25,26,31,32,33,35,41,42\}$ f

LATER As Gerhard notes, so far I used an enumeration of all graphs with 3 edges along with a reported enumeration of all graphs with up to $12$ nodes (although only the statistics which gave non-zero counts, not the counts themselves). However less detailed constructions might yield most of the values. Here is one:

Consider splitting $n$ nodes into two groups, of sizes $3$ and $m=n-3.$ Decree a complete graph $K_m$ on the $m$ nodes and no edges joining two of the other $3.$ Then with the between group edges one can obtain any triangle count $\binom{m}{3}+\sum_{i=1}^3\binom{m_i}{2}$ for any choices of $m_i \le m.$ This (together with the fact that $T_{n-1} \subset T_n$) shows that $T_n$ contains all integers up to $\binom{n-2}{3}$ (and further but not all the way to $\binom{n-1}{3})$ (Any integer is a sum of three or less triangular numbers). So this gets us to $O(\binom{n}{3})$ without any enumeration. Other constructions might get further.

Answer 5

Is it true that for sufficiently large $n$, $\{1,...,n^2\}\subset T_n$?

The number of unlabelled graphs with a given number of triangles is explicitly detailed here for $n \in \{1,...,12\}$: http://www.win.tue.nl/~aeb/graphs/cospectral/triangles.html