Question about Ramsey numbers

260 Views Asked by At

My book on combinatorics defines the Ramsey number as:

$R(q_1,\dots,q_n)$ is the number such that for any $p$ $\geqq$ R($q_1$,$q_2$,...,$q_n$) for at least one $0$ $<$ $i$ $<$ $n$($i$ $\in$ $N$) $ , $$G_p$$ $ contains at least one monochromatic $G_{q_i}$.

Okay, so that means that, for example $R(2,3)$ is the number such that, if I were to take a graph of that many vertices, no matter how I colour its edges, there will be a graph of 3 vertices which has all edges of the same colour. Great. But later in the book, it introduces another number $R_{n}(q)$ such that every $n$-colouring of a graph of $R_{n}(q)$ vertices forces a monochromatic graph of $q$ vertices. So basically my question is what is the difference between $R(3)$ and $R_{n}(3)$? What was the need to have 2 different definitions of the Ramsey number, especially since the first definition is way stronger than the second one?

1

There are 1 best solutions below

2
On BEST ANSWER

$R(2,3)=k$ means that, with $k$ vertices and so $\frac12k(k-1)$ edges, if you colour all the edges using two colours, either $2$ of the vertices are joined with a edge of the first colour or $3$ of the vertices are joined only with edges of the second colour, and $k$ is the smallest value for which this is true. In this example $R(2,3)=3$ and this is easy to check.

$R(q_1,\dots,q_n)$ is the essentially the same but with $n$ colours.

$R_n(q)$ means $R\underbrace{(q,q, \ldots,q)}_\text{$n$ times}$, i.e. where there are $n$ identical $q$s. This definition builds on the previous definition.

So for example $R(3,3)=6$ and $R(3,3,3)=17$ but you can write these as $R_2(3)=6$ and $R_3(3)=17$. I suppose you could say $R_1(3)=R(3)=3$, showing $R_n(3)\not=R(3)$ when $n>1$.