# Combinatorial optimization and graph coloring

I am considering the following problem:

(i) Fix $n$ and color the edges of $K_n$ red and blue arbitrarily.

(ii) Let $M$ be the set of monochromatic triangles in $K_n$ and define $g:M\rightarrow \mathbb{N}$ as $g(T_{xyz})$= $|N_r(x)\cap N_r(y)\cap N_r(z)|$ if $T_{xyz}$ is red and $|N_b(x)\cap N_b(y)\cap N_b(z)|$ otherwise. Here $T_{xyz}$ is a monochromatic triangle with vertices $x$, $y$ and $z$.

(iii) Consider the problem Max $g(T_{xyz})$ s.t. $T_{xyz}\in M$. What is a lower bound for this maximum?

Any advice as to how this problem may be tackled would be much appreciated.

Thanks

Update: As per a conjecture of A. Thomason (1979) $r(K_m+\bar{K_n})\le 2^m(m+n-2)+2$ where $r(G)$ is the diagonal ramsey number.

-
Isn't this maximized by taking all red or all blue? –  Will Sawin Jan 15 '12 at 7:42
The graph has been colored arbitrarily. My question is how much is this max-value at least? I have edited the question. –  Shahab Jan 15 '12 at 7:52
It is linear in $n$ (since we have about $Cn^4$ monochromatic full quadrilaterals, so one of $n(n-1)(n-2)/6$ triangles belongs to at least $24C\cdot n$ of them). Are you interested in sharp constant or in exact value for each $n$? –  Fedor Petrov Jan 15 '12 at 10:06
What does $N_r(x)$ mean? –  Gerry Myerson Jan 15 '12 at 10:50
Can you solve the problem for some small values of $n$ and then look up the results in the Online Encyclopedia of Integers Sequences? –  Gerry Myerson Jan 15 '12 at 10:52
Linear lower bound. For any For any 18 vertices we have a monochromatic quadrilateral by Ramsey theorem. It follows that the total number of monochromatic quadrilaterals is not less then ${n\choose 18}/{n-4\choose 14}$. Then one of triangles is contained in at least at least $4{n\choose 18}/({n-4\choose 14}\cdot {n\choose 3})=(n-3)/{18\choose 4}$ monochromatic quadrilaterals.