2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I dont quite understand you want that they are not equal ? Since $\leq$ is trivial right ? $\endgroup$ – Rene Schipperus Jun 12 '14 at 14:10
  • $\begingroup$ $R(n,2)=n$ as you know so better say $s_i >2$. $\endgroup$ – Rene Schipperus Jun 12 '14 at 14:21
  • $\begingroup$ As I understand, equality may hold when some $s_{j}$'s can take the value 1 hence $s_{i}\geq 2$. But I don't know if this is the only case where we can obtain equality. So yes, ultimately, I am looking for a proof that this holds strictly. $\endgroup$ – Sylin Jun 12 '14 at 14:39
  • $\begingroup$ I don't understand why we need $s_{i} > 2$ from $R(n,2)=n$. $R(n,2)<R(n+1,2)$ is fine as it is? $\endgroup$ – Sylin Jun 12 '14 at 14:45
2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Your very first sentence is like Moses spreading all the waters to make a path! Allow me to try and understand the rest. $\endgroup$ – Sylin Jun 12 '14 at 15:10
  • $\begingroup$ Ah! Ok, so if there's no $i$-homogeneous $K_{s_{i}}$ for some $i$, then the colour $i$ can be safely added to the graph so its counter-example-ness is carried over to a colouring of $K_{R(s_{1},\ldots ,s_{n})}$, hence the contradiction. $\endgroup$ – Sylin Jun 12 '14 at 16:32
  • 1
    $\begingroup$ If your coloring has no $i$-homogeneous copy of $K_{s_i-1}$, adding a point and extending the coloring (no matter how) cannot result in an $i$-homogeneous $K_{s_i}$, as $s_i-1$ of its vertices would have to form an $i$-homogeneous $K_{s_i-1}$ under the original coloring. If, in addition, all newly added edges are colored $i$, then any homogeneous set for any color other than $i$ (and with at least 2 points) was already present before the new point was added. $\endgroup$ – Andrés E. Caicedo Jun 12 '14 at 16:34
  • $\begingroup$ ah, I meant to say $K_{s_{i}-1}$ in my second comment $\endgroup$ – Sylin Jun 12 '14 at 17:20

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.