Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Fix $i,j$. I want a bound $F(i,j)$ on the following:

$\sum_{n=1}^\infty$ (the number of 2-colorings of the edges of $K_n$ such that the MAX RED clique is size exactly $i$ (that's an $i$ not a 1) and the MAX BLUE clique is of size exactly $j$.


1) If $n=3$ then coloring (1,2) RED, (2,3) RED, (1,3) BLUE is counted DIFF from coloring (2,3) RED, (3,1) RED, (1,2) BLUE.

2) The sum does not really go to infinity since when $n\ge$ RAMSEY$(i+1,j+1)$ it will be 0.

3) It might be that having MAX RED CLIQUE $\le i$ and MAX BLUE CLIQUE $\le j$ doesn't change things much and is easier to compute.

share|improve this question
I took the liberty of LaTeX'ing your posting. –  Joseph O'Rourke Aug 9 '11 at 0:11
I found some introductory material. There are a few people on MO who do combinatorics, anyway en.wikipedia.org/wiki/Clique_%28graph_theory%29 en.wikipedia.org/wiki/Ramsey_theory math.cmu.edu/~af1p/Teaching/Combinatorics/Slides/ChRam.pdf –  Will Jagy Aug 9 '11 at 4:02
I also found this other stuff, as i am trying to figure out whether the OP was getting a bachelor's degree in mathematics at Stony Brook at the same time I was, late 1970's...cs.umd.edu/~gasarch/ramsey/ramsey.html –  Will Jagy Aug 9 '11 at 4:53

Your Answer


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

Browse other questions tagged or ask your own question.