Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.


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.

share|cite|improve this question
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

1 Answer 1

up vote 4 down vote accepted

Linear lower bound. 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.

share|cite|improve this answer

Your Answer


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.