2
$\begingroup$

I have recently started reading about Ramsey theory, though I'm a bit confused about what does it actually tell us. As long as I understood, it says that in a big enough complete graph one can find a monochromatic edge coloring. But, I'm confused a bit about the purpose of the Ramsey number, $R(r,s)$. I see from the calculations that each Ramsey number has a value, what does the values correspond to? On the other hand, in some places I see it written as "$R(r,s)$, means that we can color the edges of the graph with two colors, where there is no monochromatic $K_r$ of color $1$, and no monochromatic $K_s$ of color $2$", and in some places I see the opposite, that there is a monochromatic complete graph, this confuses me a lot, do we try to ensure that there is no monochromatic complete graph or there is?

$\endgroup$
2
$\begingroup$

The issue here is that "$R(r,s)$ means that we can color..." is not a meaningful sentence, because $R(r,s)$ is just some number, not a statement. A meaningful statement about Ramsey numbers would be "$R(r,s) \geq t$" or "$R(r,s) \leq t$" or "$R(r,s) = t$".

$R(r,s)$ is the smallest $n$ such that every $2$-edge-coloring of $K_n$ has either a monochromatic $K_r$ or a monochromatic $K_s$. To say "$R(r,s) \geq t$" is to say "$K_{t-1}$ has a $2$-edge-coloring with no monochromatic $K_r$ or $K_s$". To say "$R(r,s) \leq t$" is to say "every $2$-edge-coloring of $K_t$ has a monochromatic $K_r$ or $K_s$".

This is probably why you keep seeing statements that appear to be opposite to each other: some are talking about lower bounds on $R(r,s)$, while others are talking about upper bounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy