Given positive integers $m,n$, does the Ramsey number $R(m,n)$ always exist?

Question

I recently read some articles about Ramsey numbers and I found them very interesting, I would like to know if there is a test and where I can find it about the existence of these numbers, that is to say that for any $m,n$ the Ramsey number $R ( m, n)$ always exists.

I found something like this:

We know $\forall n\in N, R(n,1)=R(1,n)=1$.

Assume $\forall r<r_0, s<s_0$, $R(r,s)$ exists. (Induction hypothesis)

Then we want to show $R(r_0,s_0)$ exists.

Then we apply the "Proof for Two Colors" to show that $R(r_0,s_0)≤R(r_0−1,s_0)+R(r_0,s_0−1)$, which implies $R(r_0,s_0)$ exists.

But this uses the inequality theorem, is there another way? Or can you prove existence with that theorem?

Answer 1

You can use this "inequality theorem" to prove the existence of these Ramsey numbers.

Let's define the Ramsey number $R(m,n)$ as the minimum natural number $k$ such that every $2$-coloring of $K_k$ either has a monochromatic $K_m$ in one color or a monochromatic $K_n$ in the other color, if that number $k$ exists. If $S$ is the set of all $k$'s with that property, and if $S$ is nonempty, then $R(m,n) = \min S$.

Since the inequality theorem gives a $k$ with the above property, we know that such an $S$ is nonempty, so $R(m,n)$ exists.

Answer 2

The proof of what you seem to be calling the inequality theorem actually shows the following statement:

If $R(a+1,b)$ and $R(a,b+1)$ exist, then so does $R(a+1,b+1)$ and the following inequality holds: $$ R(a+1,b+1)\le R(a,b+1)+R(a+1,b). $$

[The usual proof, considering the degree of any vertex, explicitly shows that any graph on $R(a,b+1)+R(a+1,b)$ vertices either contains a complete graph on $a+1$ vertices, or an independent graph on $b+1$ vertices, so $R(a+1,b+1)$ exists and has $R(a,b+1)+R(a+1,b)$ as an upper bound.]

Using this, and induction on $r_0+s_0$, it follows that $R(r_0,s_0)$ exists for all $r_0,s_0$. For the base case $r_0+s_0=2$, use that $R(r_0,1)=R(1,s_0)=1$ for all $r_0,s_0$, in particular for $r_0=s_0=1$ (the only pair of positive integers that adds up to two).

Note that this is not an induction quite of the form described in the question: it is not that one assumes the existence of $R(r,s)$ for all $r<r_0$, $s<s_0$. In particular, the proof is not presented as a double induction. Instead, one argue by induction on the single variable $r_0+s_0$.

In some detail: The base case is when $r_0+s_0=2$. Here, $r_0=s_0=1$ and, indeed, $R(1,1)$ exists (and equals $1$).

Now, suppose that $R(r,s)$ exists whenever $r,s\ge1$ and $r+s<r_0+s_0$. We argue that $R(r_0,s_0)$ exists as well. For this, note that either $r_0=1$ (and then $R(r_0,s_0)$ exists and equals $1$), or $s_0=1$ (and, again, $R(r_0,s_0)$ exists and equals $1$), or else $r_0,s_0>1$ and therefore both $R(r_0,s_0-1)$ and $R(r_0-1,s_0)$ exist, by the induction hypothesis.

We can then apply the inequality theorem in the way stated above (with $a+1=r_0$, $b+1=s_0$) to conclude that $R(r_0,s_0)$ exists as well.

It is perhaps worth pointing out that the way the induction was suggested in the body of the question does not appear to suffice. It is certainly not enough to apply the inequality theorem, since we do not have strict inequality in both variables.

---

There are several other proofs. Ramsey's original argument is different, see

MR1576401. Ramsey, F. P. On a Problem of Formal Logic. Proc. London Math. Soc. (2) 30 (1929), no. 4, 264–286.

One can also prove the result using the infinite version of Ramsey's theorem (which can be proved directly) and a compactness argument. There are several questions on this site sketching the argument, see here for example. This is a really useful technique, its main drawback being that it does not provide you with explicit bounds.

The inequality theorem, and the proof of Ramsey's theorem using it, are from

Robert E. Greenwood Jr. and Andrew M. Gleason. Combinatorial relations and chromatic graphs. Canad. J. Math., 7:1–7, 1955.

Curiously, this paper does not reference Ramsey's. Note that from the inequality theorem and induction one gets the bound $R(a+1,b+1)\le\binom {a+b}a$.