0
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Exchange the colours red and blue, which are arbitrarily assigned. $\endgroup$ – Mark Bennet Jun 10 '19 at 7:19
  • $\begingroup$ 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? $\endgroup$ – bof Jun 10 '19 at 7:39
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.