# Ramsey number: why is R(s, t)=R(t, s)?

So let's assume that $$s \leq t$$, and we use the following definition: the Ramsey number $$R(s, t)$$ is the smallest value of $$N$$ such that under every red-blue coloring of $$K_{N}$$, there is a red $$K_s$$ or a blue $$K_t$$.

All graph theory books and lecture notes I can find say that "it is obvious that $$R(s, t) = R(t, s)$$", but unfortunately I can't see this.

So let's say $$R(s, t) = N$$, and under a certain red-blue coloring of $$K_N$$, we have a blue $$K_t$$, then clearly we have a red $$K_s$$ since $$s \leq t$$. However, if we have another red-blue coloring of $$K_N$$ that only yields a red $$K_s$$ but no blue $$K_t$$, then how can we assure that we can certainly obtain a red $$K_t$$ or a blue $$K_s$$?

I appreciate any help.

• Exchange the colours red and blue, which are arbitrarily assigned. – Mark Bennet Jun 10 '19 at 7:19
• So there is a red-blue Ransey number $R_{\text{red,blue}}(s,t)$ which guarantees a red $K_s$ or a blue $K_t$, and a blue-red Ransey number, and a black-orange Ramsey number, and so on, for millions of different pairs of colors? And no reason why any of them should be the same? – bof Jun 10 '19 at 7:39

Fix a red-blue colouring of $$K_N$$ and construct a new colouring by exchanging the colour red with the colour blue. This new colouring either contains a red $$K_s$$ or a blue $$K_t$$ by definition of $$N$$. Hence the original colouring contains a red $$K_t$$ or a blue $$K_s$$ as required.
Fix a red-blue colouring $$c$$ of $$K_N$$ where $$N=R(s,t)$$.
So $$c$$ is a map from $$E_N$$ (the edges of $$K_N$$, i.e. all unordered pairs $$\{i,j\}$$ where $$i \neq j \in \{1,\ldots, N\} = V_N$$, the vertices of $$K_N$$) to $$\{r,b\}$$, the set of "colours". The "swap map" on the colours can be defined as $$s: \{r,b\}\to \{r,b\}$$ with $$s(r) = b, s(b)= r$$.
Define $$c': E_N \to \{r,b\}$$ by $$c'(\{i,j\}) = s(c(\{i,j\}))$$, and this is another colouring of $$K_N$$. By definition of $$R(s,t)$$ there is either a red $$K_s$$ or a blue $$K_t$$ for $$c'$$. A red $$K_s$$ is just a subset $$A \subset V_N$$ such that $$|A| = s$$ and $$\forall i\neq j \in S: c'(\{i,j\}) = r$$, and as $$c'(\{i,j\})=r$$ iff $$C(\{i,j\})=b$$, we in fact have a blue $$K_s$$ for $$c$$, or (similarly) a red $$K_t$$ for $$c$$ (when we have a blue $$K_t$$ for $$c'$$).
So in summary of the previous paragraphs: any red-blue colouring of $$K_N$$ has a red $$K_t$$ or blue $$K_s$$. As $$R(t,s)$$ is the minimal number of vertices that this holds for, we have $$R(t,s) \le N= R(s,t)$$.
Now the same argument starting with $$N= R(t,s)$$ will give $$R(s,t) \le R(t,s)$$ and we're done.