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.

Question

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

Answer 1

No, this statement cannot be proven probabilistically - at least, not the way you are doing it.

If you choose a coloring of $E(K_n)$ at random, then even if you prove something nice about that coloring, you have not proven a statement about every coloring of $E(K_n)$. At best, you have proven a statement that there exists a coloring of $E(K_n)$ with that property.

---

If you want to use a random approach, consider the following. We fix an arbitrary coloring of $E(K_n)$ and choose at random three distinct vertices $u,v,w \in V(K_n)$. Define three random variables

• $X_u = 1$ if $uv,uw$ are the same color, and $0$ otherwise.
• $X_v = 1$ if $uv, vw$ are the same color, and $0$ otherwise.
• $X_w = 1$ if $uw, vw$ are the same color, and $0$ otherwise.

For large $n$, $\mathbb E[X_u]$, $\mathbb E[X_v]$, and $\mathbb E[X_w]$ should be close to $\frac12$. For example, you should be able to prove that for $n \ge 11$ we have $\mathbb E[X_u] \ge \frac49$.

However, note that $X_u + X_v + X_w$ is $3$ if $u,v,w$ induce a monochromatic triangle, and $1$ otherwise. So if a $p$ fraction of triangles are monochromatic, then $\mathbb E[X_u + X_v + X_w] = 3 \cdot p + 1 \cdot (1-p) = 1 + 2p$. If you can prove that $\mathbb E[X_u + X_v + X_w]$ is a constant greater than $1$, then it follows that $p$ is bounded below by a constant, and then you are done - because the coloring has $p \binom n3$ monochromatic triangles.

---

The standard approach to this problem is usually not stated in terms of random variables, though it is equivalent to what I've described. For more details, look up Goodman's theorem on monochromatic triangles.