1 results
HOW MANY TRIANGLES CAN A GRAPH HAVE?
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society , First View
- Published online by Cambridge University Press:
- 14 November 2024, pp. 1-11
-
- Article
-
- You have access
- HTML
- Export citation
-
We investigate the set
$T_{n}$ of the possible number of triangles in a graph on n vertices. The first main result says that every natural number less than 
$\binom {n}{3} - (\sqrt {2}+o(1) )n^{3/2} $ belongs to 
$T_{n}$. On the other hand, we show that there is a number 
$m = \binom {n}{3}-( \sqrt {2} +o(1))n^{3/2}$ that is not a member of 
$T_{n}$. In addition, we prove that there are two interlacing sequences 
$\binom {n}{3} - ( \sqrt {2} + o(1) )n^{3/2} = c_{1} \le d_{1} \le c_{2} \le d_{2} \le \cdots \le c_{s} \le d_{s} = \binom {n}{3}$ with 
$| c_{t} - d_{t}| = n-2-\binom {s - t +1}{2}$ such that 
$( c_{t}, d_{t} ) \cap T_{n} = \emptyset $ for all t. Moreover, we obtain a generalisation of these results for the set of the possible number of copies of a connected graph H in a graph on n vertices.
