Show that there exists a coloring of the edge set of $K_n$ that has at most $\frac{\binom{n}{3}}{4}$ monochromatic triangles

Question

Show that there exists a coloring of the edge set of $K_n$ that has at most $\frac{\binom{n}{3}}{4}$. monochromatic triangles.

I considered labelling the n vertices as $v_1,v_2,...,v_n$ and coloring RED any edge between two vertices whose indexes have different parity, and coloring BLUE any edge between two vertices whose indexes have the same parity, but that gives me a maximum of $(\binom{n/2}{3})^2$. There are no red triangles, since by the pigeonhole principle there are no three vertices whose indexes all have different parity. However, the blue triangles can only be made up of vertices that all have the same parity. This is $(\binom{n/2}{3})^2$ because we have two disjoint sets of n/2 vertices, from which to form triangles/pick three vertices.

But does this work? I don't see how this relates to $\frac{\binom{n}{3}}{4}$.

Answer 1

Your construction actually produces $\binom{\lfloor n/2\rfloor}3+\binom{\lceil n/2\rceil}3$ monochromatic triangles. It remains to prove that this is less than $\binom n3/4$.

If $n=2k$ (even), $$\binom{\lfloor n/2\rfloor}3+\binom{\lceil n/2\rceil}3=2\binom k3=2\cdot\frac{k(k-1)(k-2)}6$$ $$<2\cdot\frac{k(k-1/2)(k-1)}6=\frac14\cdot\frac{(2k)(2k-1)(2k-2)}6=\frac14\binom n3$$ If $n=2k+1$ (odd), $$\binom{\lfloor n/2\rfloor}3+\binom{\lceil n/2\rceil}3=\binom k3+\binom{k+1}3=\frac{k(k-1)((k-2)+(k+1))}6$$ $$=2\cdot\frac{k(k-1)(k-1/2)}6=\frac14\cdot\frac{(2k)(2k-1)(2k-2)}6=\frac14\binom{n-1}3<\frac14\binom n3$$