Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

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.

share|improve this answer
    
thanks for the lead! however, i don't understand why $$\frac1{20}\binom{n}3$$ = $binom{n}3$ - (2m+1)m^2/2 –  Gogol Nov 4 '12 at 23:15
    
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 –  Gogol Nov 5 '12 at 1:02
    
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... –  Gerry Myerson Nov 5 '12 at 1:49
    
(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. –  Gerry Myerson Nov 5 '12 at 1:50
    
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. –  Gerry Myerson Nov 5 '12 at 1:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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