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 of $n$ nodes, and every edge is either blue or red. I'm trying to find $T_n$, which is the lower bound for the number of monochromatic triangles in $K_n$ (monochromatic meaning triangles whose 3 edges are of the same color).

I'm trying this approaches:

A. Let $v_i$ a vertex in $K_n$. This triangle belongs to $\binom{n-1}{2} $ different triangles. Let $r$ be the number of red edges that $v_i$ belongs $b$ the number of blue edges. Of course, $$r + b = n-1$$ So, the number of non-monochromatic (dual/stereo-chromatic?) triangles is $r \cdot b$, and so our bound would be (for vertex $V_i$)

$$T_n \le \binom{n-1}{2} - r \cdot b$$

Question is - how do I know when $r \cdot b$ is the maximal possible number? Also, this would give me the upper bound, how do I find the lower bound?

Thanks in advance!

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

Here's a proof, from Wikipedia, that $K_6$ has at least 2 monochromatic triangles. You may find that this method of proof generalizes to give you the lower bound you want.

"An alternate proof works by double counting. It goes as follows: Count the number of ordered triples of vertices $x, y, z$ such that the edge $(xy)$ is red and the edge $(yz)$ is blue. Firstly, any given vertex will be the middle of either $0\times5=0$ (all edges from the vertex are the same color), $1\times4=4$ (four are the same color, one is the other color), or $2\times3=6$ (three are the same color, two are the other color) such triples. Therefore there are at most $6\times6=36$ such triples. Secondly, for any non-monochromatic triangle $(xyz)$, there exist precisely two such triples. Therefore there are at most 18 non-monochromatic triangles. Therefore at least 2 of the 20 triangles in the $K_6$ are monochromatic."

On the other hand, if you want all the work done for you, there is an answer in A W Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959) 778-783, also in Frank Harary, The two-triangle case of the acquaintance graph, Math. Mag. 45 (1972) 130-135.

share|improve this answer
add comment

If you take $G = K_n$, $n\geq 3$ and colour each edge red with probability 1/2 and blue otherwise. Define $X$ to be the random variable counting the number of monochromatic triangles. Then

$E[X] = \binom{\binom{n}{2}}{3}\left(\frac{1}{2}\right)^3$

Hence, there is a colouring of $G$ such that there are least this many.

share|improve this answer
    
How does that help with a lower bound? –  mjqxxxx Jan 24 '12 at 16:18
add comment

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.