3 i think this fixes a typo since m = n-3 earlier

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)(m-3)^2=\binom{n}{3}-(\epsilon \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.

2 added 13 characters in body

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)(m-3)^2=\binom{n}{3}-(\epsilon n^2+O(n))$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)$\binom{n}{3}-\sum_1^v\binom{d_i}{2}.$ We don't need to not know how many ways a certain degree sequence can be obtained, only which degree sequences are possibleif it can be realized in at least one one.

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)(m-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 don't need to know how many ways a certain degree sequence can be obtained, only which degree sequences are possible.