Say $K_n$ is a complete graph. Show that any coloring of edges of $K_n$ with $n \ge 6$ in two colors contains at least $$\frac1{20}\binom{n}3$$ monochromatic triangles. Any ideas on how to use Ramsey theory to solve this?

Any help is much appreciated!


Let $K_n$ be 2-colored. A bi-angle is a configuration of two edges with different colors meeting at a vertex. If $n=2m+1$ then the greatest possible number of bi-angles involving any particular vertex is $m^2$, so the total number of bi-angles in the coloring is at most $(2m+1)m^2$. The number of triangles in $K_n$ is $n\choose3$. Each nonmonochromatic triangle uses up 2 bi-angles, so the number of nonmonochromatic triangles is at most $(2m+1)m^2/2$. This gives you a lower bound on the number of monochromatic triangles, in the $n$ odd case. A simple modification handles the $n$ even case.

  • $\begingroup$ thanks for the lead! however, i don't understand why $$\frac1{20}\binom{n}3$$ = $binom{n}3$ - (2m+1)m^2/2 $\endgroup$ – Gogol Nov 4 '12 at 23:15
  • $\begingroup$ so, clearly there are $n\choose3$ triangles in $K_n$. I'm still not sure how we get the bi-angles number. is there no way to use Ramsey's theorem to prove this? Please help me $\endgroup$ – Gogol Nov 5 '12 at 1:02
  • $\begingroup$ I don't know whether there is a way to use Ramsey theory here. For the bi-angles, let's look at $n=7$. Each vertex has 6 edges. Some are red, some are blue. How many ways are there to choose 2 of these 6 edges, the two being different colors (that is, how many bi-angles are there at that vertex)? Well, that depends on how many of the 6 edges are red, and how many are blue. But which way of coloring those 6 edges would result in the greatest possible number of bi-angles at that vertex? And how many bi-angles would there then be at that vertex? And if there were the same number of biangles... $\endgroup$ – Gerry Myerson Nov 5 '12 at 1:49
  • $\begingroup$ (continued)...at each vertex, how many would there be in all? And what if instead of 7 vertices, there were $2m+1$? So, that's how you get the number of bi-angles. $\endgroup$ – Gerry Myerson Nov 5 '12 at 1:50
  • $\begingroup$ Then you want to prove $${n\choose3}-{(2m+1)m^2\over2}\ge{1\over20}{n\choose3}$$ and that's just a simple inequality where you multiply everything out and see what you get. $\endgroup$ – Gerry Myerson Nov 5 '12 at 1:52

Gerry Meyerson's answer will actually get you the better result that the number of monochromatic numbers is at least $\frac1{10}\binom n3.$ Here is an easier way to prove the weaker result stated in the question using Ramsey's theorem for $2$-colorings of $K_6.$

Let $M$ be the number of monochromatic triangles. Let $P$ be the number of ordered pairs $(X,Y)$ where $X$ is a monochromatic triangle and $Y$ is a $K_6$ containing $a.$

On the one hand, $P=M\binom{n-3}3,$ since each monochromatic triangle is contained in $\binom{n-3}3\ $ $K_6$'s.

On the other hand, $P\ge\binom n6,$ since each $K_6 contains at least one monochromatic triangle.

It follows that $M\binom{n-3}3\ge\binom n6,$ whence (assuming $n\ge6$) $$M\ge\frac{\binom n6}{\binom{n-3}3}=\frac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{6!}\cdot\frac{3!}{(n-3)(n-4)(n-5)}=\frac{n(n-1)(n-2)\cdot3!}{6!}=\frac{n(n-1)(n-2)}{3!}\cdot\frac{3!}{4\cdot5\cdot6}=\frac1{20}\binom n3.$$

P.S. Actually, if we know that every $2$-edge-colored $K_6$ contains at least two monochromatic triangles, then we know that $P\ge2\binom n6,$ so the final result is improved to $M\ge\frac1{10}\binom n3.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.