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

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?

-
It's not clear to me that {1, 2, ..., n} is contained in $T_n$. How do I get 2 or 3 triangles with just 3 vertices? –  Sridhar Ramesh Sep 23 '12 at 23:52
Many simple statements can be made, two of the most useful are that T_n is contained in T_n+1 and removing an edge from a complete graph affects n-2 triangles. Anything finer is likely not much weaker than enumerating finite graphs. Gerhard "Ask Me About System Design" Paseman, 2012.09.23 –  Gerhard Paseman Sep 23 '12 at 23:54
Sridhar -- good call, thanks. I added the $n>4$ stipulation. Gerhard -- thanks a lot, that's helpful! –  Ben Golub Sep 23 '12 at 23:56
In fact, it should be easy to set up a correspondence: 0 edges removed means 0 triangles removed, a path of length 1 means n-2 triangles, 2-path 2n-6, two 1-paths 2n-5, triangle 3n-10, and so on. If you can readily establish a correspondence, I will bow to the suggestion that this problem is much easier than finite graph enumeration. Gerhard "Don't Need No Suggestion Genuflection" Paseman, 2012.09.24 –  Gerhard Paseman Sep 24 '12 at 21:07
The number of triangles sees very little information from the graph of removed edges. By inclusion-exclusion, it sees at most the number of edges, the number of pairs of edges sharing a vertex, and the number of triangles removed completely. To classify all graphs of a given size takes a lot more than 3 polynomially bounded counts. –  Douglas Zare Sep 27 '12 at 2:49

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.

-

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

-
Once one can get up to $n^{3/2}$ triangles for large n, one can get up to $(1-o(1)) \binom{n}{3}$ triangles as well. Indeed, for any $0 \leq p < 1$, consider an Erdos-Renyi graph on $(1-\varepsilon) n$ vertices with edge density p; the number of triangles is basically $p^3 (1-\varepsilon)^3 \binom{n}{3}$ plus a random fluctuation of standard deviation $O(n^{3/2})$ and distributed close to normally. This already gets within $\varepsilon^{3/2} n^{3/2}$ (say) of any desired triangle count that is significantly smaller than $\binom{n}{3}$, and then using the above construction for the (cont) –  Terry Tao Sep 24 '12 at 21:23
remaining $\varepsilon n$ vertices will then get the desired triangle count exactly on the nose. –  Terry Tao Sep 24 '12 at 21:23
Indeed. Terry, I suspect determining the spectrum for all n will require a good knowledge of finite graphs. Does your intuition say this problem (determining the spectrum exactly) is easier or as hard as finite graph enumeration? Gerhard "Triangulating Minds Want To Know" Paseman, 2012.09.24 –  Gerhard Paseman Sep 24 '12 at 23:51
For small n, one probably has no choice but to do some ad hoc enumeration. Asymptotically, though, I think there is some chance of a complete description, once one understands what is going on when $t$ is reasonably close to $\binom{n}{3}$ (e.g. within $O(n^2)$). –  Terry Tao Sep 25 '12 at 2:34
I could be wrong, but I think that one big clique, up to three vertices with no edges between them and perhaps some isolated vertices gives all counts up to ( and a bit beyond) $\binom{n-2}{3}=\binom{n}{3}-(n-2)^2$. –  Aaron Meyerowitz Sep 25 '12 at 13:11

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]

-
It looks like Ben is happy with your answer, and indeed I am not suprised at the result. However, I suspect there are about n values to be determined (hiding in the O(n^2)), and those n values may require knowing a lot about the graphs on say log n or even sqrt(n) vertices. If I understand Terry's response correctly, his intuition says filling in the missing values will be easier than graph enumeration. Does your intuition tell you something similar to this? Gerhard "We're The Less Than 1%" Paseman, 2012.09.24 –  Gerhard Paseman Sep 25 '12 at 5:01
Oh, and I am guessing the next clique overlaps the previous one in one edge and two vertices. Gerhard "Ask Me About System Design" Paseman, 2012.09.24 –  Gerhard Paseman Sep 25 '12 at 5:13

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.

-
Maybe one needs to know "most" of the n vertex graphs to get the spectrum for the $n^2$ case. I admit to not knowing the asymptotics. Gerhard "Pretty Good At Guessing, However" Paseman, 2012.09.24 –  Gerhard Paseman Sep 24 '12 at 15:16
May I also note that your constructions correspond (in my mind) to enumerating the graphs with at most three edges. Gerhard "Takes Edgy Point Of View" Paseman, 2012.09.24 –  Gerhard Paseman Sep 24 '12 at 15:28

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

-
This should be easily computed. One needs a complete graph on $O(n^{2/3})$ vertices to acheive the upper bound, leaving quite a few vertices to take care of possible gaps. I suspect it should hold for n > 50. Gerhard "Ask Me About System Design" Paseman, 2012.09.24 –  Gerhard Paseman Sep 24 '12 at 7:34
Seeing the data you linked to, I change my guess from 50 to 10. Gerhard "Proving It Shouldn't Be Hard" Paseman, 2012.09.24 –  Gerhard Paseman Sep 24 '12 at 8:17