Strengthening of a lemma in Ramsey Theory: $R(m, n) \le R(m-1, n) + R(m, n-1)-1$ if both numbers are even

Question

A cool lemma in Ramsey theory is the following:

$$R(m, n) ≤ R(m-1, n) + R(m, n-1).$$

It is not hard to prove it. However, a friend of mine said that, if $R(m-1, n)$ and $R(m, n-1)$ are both even, then

$$R(m, n) ≤ R(m-1, n) + R(m, n-1)-1.$$

How can I prove it?

Answer 1

Consider that you have a graph of $R(m-1,n)+R(m,n-1)-1$ points. And you want a clique or an independent set.

Now take any point if it has an edge with $\geq R(m-1,n)$ points then by induction you are done. If it has an edge with $\leq R(m-1,n)-2$ points then it will have a non edge with $\geq R(m,n-1)$ points and again you are done. So one is left with the case where the chosen point has exactly $R(m-1,n)-1$ edges.

In the language of graph theory it has degree $R(m-1,n)-1$. Now you are able to chose this beginning point at will, thus if at least one point does not have degree $R(m-1,n)-1$, you are done.

Finally the case where all points have degree $R(m-1,n)-1$ is impossible since $$2(\text{# of edges})=(\text{# of vertices}) \cdot \text{degree}$$ $$=(R(m-1,n)+R(m,n-1)-1)(R(m-1,n)-1)$$ and under your assumptions this last number is odd so it cannot be $2(\text{# of edges})$ thus at leas one point does not have degree $R(m-1,n)-1$.

An example of this is $R(3,4)=9$.

But $R(2,4)+R(3,3)=4+6=10$.

Answer 2

We will use $N=R(m-1,n)+R(m,n-1)$ for convenience. It is given that $R(m-1,n)$ and $R(m,n-1)$ are even. So, $N$ is also even.

Consider any blue-red colouring of the edges of $K_{n-1}$. Now, choose a vertex $v\in V$ such that $d(v)$ is even i.e., $v$ is of even degree. Note that this choice is possible because the sum of degrees of all vertices in a graph is twice the number of edges in the graph and $(N-1)$ is odd. Define \begin{align*} B&=\{x\in V: xv\in E, \;xv\text{ is coloured blue}\}\\ R&=\{x\in V: xv\in E, \;xv\text{ is coloured red}\} \end{align*} So, $$|B|+|R|=N-2$$ So, by the Pigeon Hole Principle, either $|B|\geq R(m-1,n)$ or $|R|\geq R(m,n-1)$. If it's the former, then $K_{n-1}$ must contain a blue $K_m$. And if it's the later, since $d(v)$ is even, $K_{n-1}$ must contain a red $K_n$.

This completes the proof.