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

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}$$.

• Using a different color for each edge will certainly work, as there will then be no monochromatic triangles. Did you leave out some part of the statement like "with two colors"?
– bof
Apr 3, 2020 at 8:09
• Assuming you can only use two colors, your construction is almost optimal. However, if $n=4t+1$, you can do slightly better with a coloring that has each vertex incident with exactly $2t$ edges of each color; in other words, the red edges form a $2t$-regular spanning subgraph of $K_n$, and of course the same goes for the blue edges.
– bof
Apr 3, 2020 at 8:25

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$$
• Less computationally, what we have to show is that, if we choose three vertices at random without replacement, the probability that all three have the same parity is less than $1/4$. Well, the probability that the second vertex has the same parity as the first is at most $1/2$, and given that the first two vertices have the same parity, the conditional probability that the third vertex also has the same parity is less than $1/2$.
• I'm confused as to where the 1/4 term comes from. These equalities don't hold because $2\frac{k(k-1)(k-1/2)}{6}=\frac{2k(2k-2)(2k-1)}{6}$ not $\frac{1}{4}\frac{2k(2k-2)(2k-1)}{6}$ Apr 3, 2020 at 16:11
• But it's not true. $$\binom{\lfloor n/2\rfloor}3+\binom{\lceil n/2\rceil}3\not<\frac{1}{4}2\frac{k(k-1)(k-1/2)}{6}$$ Apr 3, 2020 at 16:15