CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  Eventssee all events
Events        
next up previous
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 tn,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 t7,13=3.

Trivially, tn,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 tn,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 tn,e triangles, then Gc is not connected. Barnhart and I verified this when $n\le14$. If true for all n, one can recursively find tn,e. This would give analytic proofs of all results above plus a new bound similar to Fisher's when $e>{n^2\over3}$.


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

© Canadian Mathematical Society, 2017 : https://cms.math.ca/