On the minimum number of triangles in balanced tripartite graphs with large minimum degree

Abstract

Let $f(n,t)$ be the minimum number of triangles in a tripartite graph with $n$ vertices in each part and minimum degree at least $n+t$. In 1975, Bollobás, Erdős and Szemerédi proved that $f(n,1)=\min \{4,n\}$. They further remarked that it is ``very likely'' that $f(n,t)\ge 4t^3$ for $n\ge 5t$. They also proved that $f(n,t)\ge t^3$ for all integers $n\ge t\ge 1$. We construct graphs showing that, for all integers $t\ge 1$ and $n\ge 3t+2\lceil (1+\sqrt{5})t/2\rceil$, \[ f(n,t)\le(1+\sqrt5)t^3+\left(1+\frac1{\sqrt5}\right)t^2. \] Here $1+\sqrt{5}\approx 3.236<4$, and the displayed upper bound is strictly less than $4t^3$ for every $t\ge 2$, disproving their proposed bound. We also improve their lower bound $t^3$ by showing that $f(n,t)\ge \frac{12}{5}{t}^3$ for all integers $t\ge 2$ and $n\ge 18t^6$.

arXiv comment17 pages, 2 figures. Comments welcome