The number of monochromatic triangles

Question

It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula $$M(n)=\binom n3-\left\lfloor\frac n2\left\lfloor\left(\frac{n-1}2\right)^2\right\rfloor\right\rfloor;$$ see OEIS sequence A014557 or the original paper by A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783, or my answer to this math.stackexchange question.

Is there any literature on the more general question, what is the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ with a prescribed number of edges of each color?

...

Is there any literature on the related question, given natural numbers $n$ and $k$, what is the minimum value of the quantity $m+kb$ over all red/blue colorings of the edges of the complete graph $K_n$, where $m$ is the number of monochromatic triangles (of either color) and $b$ is the number of blue edges?

Answer 1

Here are results, obtained via integer linear programming, for the first question for $n \le 10$ and $b$ blue edges, where $b \le \binom{n}{2}/2$: \begin{matrix} n\backslash b & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline 2 & 0 \\ 3 & 1 & 0 \\ 4 & 4 & 2 & 0 & 0 \\ 5 & 10 & 7 & 4 & 2 & 1 & 0 \\ 6 & 20 & 16 & 12 & 8 & 6 & 4 & 2 & 2 \\ 7 & 35 & 30 & 25 & 20 & 16 & 13 & 10 & 7 & 6 & 5 & 4 \\ 8 & 56 & 50 & 44 & 38 & 32 & 28 & 24 & 20 & 16 & 14 & 12 & 10 & 8 & 8 & 8 \\ 9 & 84 & 77 & 70 & 63 & 56 & 50 & 45 & 40 & 35 & 30 & 27 & 24 & 21 & 18 & 16 & 15 & 14 & 13 & 12 \\ 10 & 120 & 112 & 104 & 96 & 88 & 80 & 74 & 68 & 62 & 56 & 50 & 46 & 42 & 38 & 34 & 30 & 28 & 26 & 24 & 22 & 20 & 20 & 20 \\ \end{matrix}

And here are results for the second question: \begin{matrix} n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 4 & 0 & 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 5 & 0 & 5 & 8 & 10 & 10 & 10 & 10 & 10 & 10 & 10 & 10 \\ 6 & 2 & 8 & 14 & 17 & 20 & 20 & 20 & 20 & 20 & 20 & 20 \\ 7 & 4 & 14 & 21 & 28 & 32 & 35 & 35 & 35 & 35 & 35 & 35 \\ 8 & 8 & 20 & 32 & 40 & 48 & 52 & 56 & 56 & 56 & 56 & 56 \\ 9 & 12 & 30 & 44 & 57 & 66 & 75 & 80 & 84 & 84 & 84 & 84 \\ 10 & 20 & 40 & 60 & 75 & 90 & 100 & 110 & 115 & 120 & 120 & 120 \\ \end{matrix} For $k=0$, the minimum is $m+0=M(n)$. For large enough $k$, all edges are red, yielding $m=\binom{n}{3}$ and $b=0$.

Answer 2

Suppose that the red degree of each vertex is denoted by $r_x$, and the total number of red edges is $R=\frac{1}{2}\sum_x r_x$. Then the number of monochromatic triangles is exactly $$ \binom{n}{3}-(n-1)R+\frac{1}{2}\sum_xr_x^2.$$

The minimum value can be derived from this, but the answer will be a little messy according as $2R$ is divisible by $n$ or not. If $2R$ is divisible by $n$, the minimum this can be is when all the $r_x$ are equal (so $=2R/n$), and so for example in this case the minimum number of monochromatic triangles is

$$ \binom{n}{3}-(n-1)R+\frac{2R^2}{n}.$$

(Note this is indeed attainable by taking red edges to be a regular graph. Also this is always a lower bound for the number of monochromatic triangles by Cauchy-Schwarz, but will not be achievable if $R$ is not divisible by $n$.)

The first formula is just a rearrangement of Goodman's more general formula, which says that for all coloured $K_n$ the number of monochromatic triangles is equal to

$$ \frac{1}{2}\left(\sum_x \binom{r_x}{2}+\sum_x\binom{n-1-r_x}{2}-\binom{n}{3}\right).$$

(The proof of which is just to note that if we count all monochromatic pairs of edges from each vertex then each monochromatic triangle is counted 3 times and non-monochromatic triangles are counted once.)