Proving an 'obvious' Ramsey upperbound

384 Views Asked by At

Here I want to prove the following:
$$R(s_{1},s_{2},\ldots ,s_{k}) < R(s_{1}+1,s_{2},\ldots ,s_{k})$$ For $s_{1},\ldots ,s_{k} \in \mathbb{N}$, $s_{i}\geq 2$.
(Or can it hold with equality in some cases?)


Try contradiction:
Suppose $\exists s_{1},\ldots ,s_{k} \in \mathbb{N}$, $s_{i}\geq 2$, for which $R(s_{1},s_{2},\ldots ,s_{k})\geq R(s_{1}+1,s_{2},\ldots ,s_{k})$.
Then consider an $k$-colouring of the edges of $K_{R(s_{1}+1,s_{2},\ldots ,s_{k})}$ with colours $c_{1},\ldots c_{k}$.
Then we either have a $c_{1}$ $K_{s_{1}+1}$, in which case we would also have a $c_{1}$ $K_{s_{1}}$, or a $c_{2}$ $K_{s_{2}}$, ... , or a $c_{k}$ $K_{s_{k}}$.
So the assumption is satisfied with equality.

Now I suppose we could get a contradiction from the minimality of $R(s_{1},s_{2},\ldots ,s_{k})$, so consider removing an edge:
Let $C$ be an $k$-colouring of the edges of $K_{R(s_{1}+1,\ldots ,s_{k})-1}$.

But now we can't say anything about the existence of any complete monochromatic subgraph of the appropriate sizes..


Try induction:

Let me start with $k=2$ for now and assume WLOG $s_{1} := s \leq t =: s_{2}$.
[Base Case]
$2=s \leq t$. Then $R(2,t) = t$.
Now $R(3,t) \geq 3(t-1)$ $> t$ for $t \geq 2$.

[Induction step] Assume $3 \leq s \leq t$.
It suffices to exhibit a red-blue colouring of edges of $K_{R(s,t)}$ with no red $K_{s+1}$ and no blue $K_{t}$.
But by definition, any red-blue colouring of edges of $K_{R(s,t)}$ contains either a red $K_{s}$ or a blue $K_{t}$. So consider those colouring in which we have a red $K_{s}$ and no blue $K_{t}$.
But this move is not possible in general because we can't assume that we have an exclusive or for all of the colourings so these colourings we choose may be empty.

1

There are 1 best solutions below

4
On BEST ANSWER

By definition, there is a coloring of $K_{R(s_1,\dots,s_n)-1}$ without an $i$-homogeneous copy of $K_{s_i}$ for each $i$. Note that any such coloring has $i$-homogeneous copies of $K_{s_i-1}$ for each $i$. Else, if the $i$-th copy is avoided, add a point and color all its edges with color $i$, and we contradict the definition of $R(s_1,\dots,s_n)$.

OK. Given such a coloring, add a point, and color all its edges with color $1$. This coloring does not have $i$-homogeneous copies of $K_{s_i}$ for $i>1$, and has $1$-homogeneous copies of $K_{s_1}$ but not of $K_{s_1+1}$.