Question on a proof of Ramsey's Theorem

Question

How do some Ramsey's Theorem proofs get to proving the inequality:

$R(s, t) \le R(s − 1, t) + R(s, t − 1)$

I get how the result shows, in the end, that there is a finite $R(s,t)$ but what's the intuition behind that step. In other words how does one think of such an inequality?

Answer 1

Recall how we prove $R(3,3)=6$. We fix a point $p$ of $K_6$ in which all edges are randomly and independently colored by red or blue.

There are $5$ edges out of $p$. By pigeonhole principle, at least $3$ or them are in the same color, say red. We denote the endpoints of these three edges distinct from $p$ by $p_1,p_2,p_3$.

Apparently, either $p_1,p_2,p_3$ form a blue triangle, or there is an edge, say $p_1p_2$ is red. Then $pp_1$, $pp_2$ and $p_1p_2$ form a red triangle. Therefore, we can either get a red triangle or a blue triangle in $K_6$, so $R(3,3)\leq 6$. In particular, we can find a counterexample in $K_5$, so $R(3,3)=6$.

The proof of such inequality is similar. Again, we fix a point $p$ of $K_n$ whose edges are randomly and independently colored by red or blue, where $$n=R(s,t-1)+R(s-1,t).$$

We then partition the neighbors (of course all the vertices in $K_n$ other than $p$) into two sets: $A$ and $B$ such that the edges between $p$ and vertices in $A$ are colored in red and the edges between $p$ and vertices in $A$ are colored in blue. As we can see, either \begin{equation} |A|\geq R(s-1,t)\quad\text{or}\quad|B|\geq R(s,t-1). \end{equation}

If $|A|\geq R(s-1,t)$, consider the clique induced by $A$. Such clique either contains a red $K_{s-1}$, which, together with $p$, form a red $K_s$, or a blue $K_t$. Similarly, if $|B|\geq R(s,t-1)$, then the clique induced by $B$ either contains a blue $K_{t-1}$ or a red $K_s$. That is, we can either find a red $K_s$ or a blue $K_t$ in such $K_n$, hence $$R(s,t)\leq R(s,t-1)+R(s-1,t).$$

P.S. Let $$f(s,t)=\binom{s+t-2}{s-1}$$ By Pascal's triangle, we have $$\binom{s+t-2}{s-1}=\binom{s+t-3}{s-2}+\binom{s+t-3}{s-1}.$$ That is, $$f(s,t)=f(s-1,t)+f(s,t-1).$$ In particular, we have $R(2,t)=t=f(2,t)$ and $R(s,2)=s=f(s,2)$. Such inequality tells us $$R(s,t)\leq f(s,t)=\binom{s+t-2}{s-1},$$ giving an upper bound for the Ramsey number.

But this bound is not tight for large $s$ and $t$ , say if $s=t$, this bound becomes $$R(s,s)\leq\binom{2s-2}{s-1}\sim\left(\frac{2s-2}{s-1}\right)^{s-1}=2^{s-1}.$$ It grows exponentially as $s$ increases.