Show that there exists a $c > 0$ and a $n^*$ such that for $n \geq n^*$, every two coloring of $E(K_n)$ contains $cn^3$ monochromatic triangles.
I’m wondering whether this statement could be proved probabilistically. The following is my attempt. Please give some comments.
For sufficiently large $n$, let $c$ be a $2$-coloring of the edges of $K_n$, with each of the colors red/blue having probability of appearing $\frac{1}{2}$. Now let $X$ be the random variable counting the number of bicolor triangles in this coloring, and $Y$ counting the number of monochromatic triangles. Clearly $X + Y = {n \choose 3}$.
I’m thinking of using Markov’s inequality, which says that, for $a > 0$, $Pr(X \geq a) \leq \frac{E[X]}{a}$. The idea is that I’d let $X$ be defined as above, and $a = {n \choose 3} - cn^3$. If this probability is less than $1$, there would be a coloring of $K_n$ (with the given probability) such that the number of monochromatic triangles is at least $cn^3$.
To that end, consider a triple of vertices. The probability that the induced triangle is bicolor is $\frac{3}{4}$, so $E[X] = \frac{3}{4} {n \choose 3}$. The above probability then becomes: $$Pr \left(X \geq {n \choose 3} - cn^3 \right) \leq \frac{3}{4} \cdot \frac{n \choose 3}{{n \choose 3} - cn^3}$$
So I’d need $\frac{n \choose 3}{{n \choose 3} - cn^3} < \frac{4}{3}$, or $4cn^3 < {n \choose 3}$. But this is clearly possible, given that we have the freedom of choosing both $c$ and $n$.