2
$\begingroup$

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

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ I guess the simplest way is to observe that, since every $2$-coloring of $E(K_6)$ contains at least $2$ monochromatic triangles, for $n\ge6$ every $2$-coloring of $E(K_n)$ contains at least $$\frac2{\binom63}\binom n3=\frac1{10}\binom n3\sim\frac{n^3}{60}$$ monochromatic triangles. $\endgroup$
    – bof
    Feb 16, 2022 at 4:55
  • $\begingroup$ Thanks for the comments. Could I ask what it is in my answer that makes it not generalizable to an arbitrary coloring? Is it the probability $p$? $\endgroup$ Feb 16, 2022 at 10:35
  • $\begingroup$ @JoshNg Your answer does not begin with "Take an arbitrary coloring"; it begins with "Take a coloring at random". If you take a coloring at random, and say that with positive probability it works, that's consistent with the existence of colorings that don't work. $\endgroup$ Feb 16, 2022 at 15:37
  • 1
    $\begingroup$ For example, with positive probability (and a very high probability at that) a random coloring will have at least one red edge. That is not a proof of the claim "Every red-blue coloring of $E(K_n)$ has at least one red edge", because there's the extremely unlikely all-blue coloring. $\endgroup$ Feb 16, 2022 at 15:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .