0
$\begingroup$

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!

2 Answers 2

2

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.

  • 0
    We aim to please.2012-11-05
0

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