David Fisher - The minimum number of triangles in a graph

Next: Jerrold Griggs - Extremal Up: Extremal Combinatorics / Combinatoire Previous: Jason Brown - The

David Fisher - The minimum number of triangles in a graph

DAVID FISHER, Department of Mathematics, University of Colorado at Denver, Denver, Colorado 80217-3364, USA

The minimum number of triangles in a graph

Given $0\le e\le{n\choose2}$ , what is the minimum number of triangles in a graph with n vertices and e edges? Let t_n,ebe the answer. For example, G has 7 vertices, 13 edges, and 3triangles. =.12in
$\begin{picture}(15,5)(-3,0) \put(-3,0){\makebox(2,5)[r]{$G=$ }} \put(4,0){\circl... ...line(3,2){3}}\put(12,2){\line(-3,1){9}} \put(12,2){\line(-1,1){3}} \end{picture}$

$\begin{picture}(15,5)(-3,0) \put(-3,0){\makebox(2,5)[r]{$G^c=$ }} \put(4,0){\cir... ...{\line(1,0){12}} \put(0,2){\line(6,1){6}}\put(6,3){\line(6,-1){6}} \end{picture}$

Since any graph with 7 vertices and 13 edges has at least 3triangles, we have t_7,13=3.

Trivially, t_n,e=0 if $e\le{n^2\over4}$ . McKay (1963) proved $t_{n,e}\ge{(4e-n^2)e\over3n}$ . Bollobás (1978) improved this by showing t_n,e is at least the piecewise linear function with nodes $\Bigl({k\choose2}({n\over k})^2, {k\choose3}({n\over k})^3\Bigr)$ for $k=1,2,\dots\,$ . Fisher (1989) found a better bound when ${n^2\over4}\le e\le{n^2\over3}$ by proving $t_{n,e} \ge{9en-2n^3-2(n^2-3e)^{3/2}\over27}$ . Nikiforov and Khadzhiivanov (1981) and Lovász and Simonovits (1983) independently found $t_{n,e}= (e- \lfloor{n^2\over4}\rfloor) \lfloor{n\over2}\rfloor$ for $\lfloor{n^2\over4}\rfloor\le e< \lfloor{n^2\over4}\rfloor+\lfloor{n\over2}\rfloor$ .

I have a conjecture: If G has n vertices, $e\ge{n^2\over4}$ edges, and t_n,e triangles, then G^c is not connected. Barnhart and I verified this when $n\le14$ . If true for all n, one can recursively find t_n,e. This would give analytic proofs of all results above plus a new bound similar to Fisher's when $e>{n^2\over3}$ .

Next: Jerrold Griggs - Extremal Up: Extremal Combinatorics / Combinatoire Previous: Jason Brown - The