MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The $k$-color Ramsey number of the complete graph $K_n$, denoted with $R_k(n)$, is defined to be the smallest integer $t$, such that in any $k$-coloring of the edges of $K_t$, there is a complete subgraph $K_n$ all of whose edges have the same color.

I'm looking for results (if exist) that link together Ramsey numbers of increasing number of colors; in particular, constructive ways to prove lower bounds.

For example: suppose that we have an instance of $K_{r_1}$ that proves $R_{k_1}(n_1) \gt r_1$ then we can build an instance of $ K_{r_2}$ that proves $R_{k_2}(n_2) \gt r_2$ for some particular $k_2 \lt k_1$ and $n_2 \gt n_1$

Can you give me some results / references?

(or results of the same type that applies to particular class of graphs, for example complete bipartite graphs)

share|cite|improve this question
I'm not an expert of Ramsey Theory, let me know if the question is too generic – Vor Oct 12 '11 at 8:59
I suggest the following for inspiration, even though it concerns a different problem. The website called the )a Jolla Covering Repository has collections of subsets of v elements such that every subset has size t and also that every subset of size n is contained in one of the t. Subsets. It has a paper mentioning old and new constructions to make more efficient coverings from known coverings. Greg Kuperberg is one of the authors. Good Luck! Gerhard "Ask Me About System Design" Paseman, 2011.10.12 – Gerhard Paseman Oct 12 '11 at 17:24

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.