1
$\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!

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
8
  • $\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 1:52
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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