The question: How did Erdös - Szekeres came up with a close form with a binomial for the upper bound: Where does the idea behind $R(2,2)=\binom{2+2-2}{2-1}$ - I do see that $R(2,2)=2$ - or $\binom{s+t-3}{s-1}\left(\text{or }\binom{s+t-3}{s-2}\right)$ come from? And how is the induction over $s$ and $t$ work?
What I understand:
- I see that $R(s,t) \leq R(s-1,t)+R(s,t-1)$
- I understand that ${\displaystyle {\binom {r+s-3}{r-2}}+{\binom {r+s-3}{r-1}}={\binom {r+s-2}{r-1}}}$ - Pascal's triangle.
- I also see that $\forall s, t ∈ \mathbb N,$ the relationship $R(s, t) = R(t, s)$ holds.
- And I get it that $R(s,2)=R(2,s)=s.$
The problem: There are tons of sites where the proof of the inequality above is readily available, including one of the answers to this post. However, when the inequality is proven, the binomial formula seems to appear out of thin air like it is self-evident, typically with a short justification such as: easily proven by induction on $s$ and $t.$ But how does this work? How did they come up with this binomial to begin with? This binomial coefficient appears before testing the base cases.
Background info:
For instance, in here:
Since $R(r, s) ≤ R(r − 1, s) + R(r, s − 1)$ so this automatically gives an upper bound, although not in the closed form that we expect.
The closed form expression is ${\displaystyle R(r,s)\leq {\binom {r+s-2}{r-1}}}.$ To derive this use double induction on $r$ and $s.$ The base case $r = s = 2$ is easily established as $${\displaystyle R(2,2)=2\leq {\binom {2+2-2}{2-1}}=2}.$$
Now assume the expression holds for $R(r − 1, s)$ and $R(r, s − 1).$ Then
$${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1)\leq {\binom {r+s-3}{r-2}}+{\binom {r+s-3}{r-1}}={\binom {r+s-2}{r-1}}}$$ gives us our upper bound. Note that we have used Pascal's relation in the last equivalence.
But why did they start already applying the binomial formula they intend to prove in ${\displaystyle R(2,2)=2\leq {\binom {2+2-2}{2-1}}=2},$ and how does the inductive process proceed from that point?
I see there are related questions, and in fact, I have tried to contribute with a possible answer as to the proof of a finite Ramsey number for every combination of two natural numbers here to get feedback.
However, I still have problems with the immediately related proof of the inequality (theorem of Erdős-Szekeres):
$$R(s,t) \leq \binom{s+t-2}{s-1}$$
as in here:
I see that this inequality is fulfilled by the base cases, as well as $s+t<5,$ but I presume other inequalities could also be fulfilled by the first Ramsey numbers.
In the following two answers that I found online it seems as though the Ramsey number on, say $(r,t),$ i.e. $R(r,t)$ is somewhat just replaced by $r$ and $t$ in the combinatorics solution. So I don't get the analogy to Pascal's triangle...
Solution 1:
The answer can be found here:
$$R(k,l) \leq \binom{k+l-2}{k-1}$$
because the recurrence $$R(k,l) \leq R(k-1,l) + R(k,l-1) $$ can be seen as the paths from a point $R(k,l)$ on the grid below to $(1,1):$
and the number of ways to get to a point on a lattice $(x,y)$ taking off from $(0,0)$ are:
$$\binom{x+y}{x}$$
Here we are moving in the opposite direction, and stopping at $(1,1),$ which reduces the count to:
$$\binom{(x-1)+(y-1)}{x-1}=\binom{x+y-2}{x-1}$$
"We’ve placed the value $1$ at each position $(k, 1)$ or $(1, l)$ in this grid, corresponding to the base case $r(k, 1) = r(1, l) = 1$ of our induction. At the point $(k, l)$ in the grid, we know that the value $r(k, l)$ at that point is upper-bounded by the sum of the values immediately below and immediately to the left. Applying this same recurrence to these adjacent nodes, we see that every left/down path from $(k, l)$ to the boundary will contribute $1$ in the final sum (corresponding to the value $1$ at the boundary points). Thus, $r(k, l)$ is upper-bounded by the number of left/down paths to the boundary, which is in turn equal to the number of left/down paths from $(k, l)$ to $(1, 1),$ which is exactly $\binom{k+l-2}{k-1}."$
Solution 2:
From here:
To see the upper bound, you are closest with your solution 1.
We have:
$$R(r,b)\le R(r-1,b) + R(r,b-1)$$
(I am using $r$ for red and $b$ for blue - I find it easier to remember!).
Using the idea of Pascal's triangle, we can extend this into:
$$R(r,b)\le \left(R(r-2,b) + R(r-1,b-1)\right) + \left(R(r-1,b-1) + R(r,b-2)\right)$$
or:
$$R(r,b)\le R(r-2,b) + 2R(r-1,b-1) + R(r,b-2)$$
The step takes us to:
$$R(r-3,b)+3R(r-2,b-1)+3R(r-1,b-2)+R(r,b-3)$$
with the next step involving $1,4,6,4,1$, and continue using binomial coefficients, except where we hit the boundaries at $R(1,b)=R(r,1)=1$ and then $R(0,b)=R(r,0)=0$, and this leaves the binomial in question.
From Known Ramsey numbers, you can see the pattern by looking at the anti-diagonals.