# Erdos-Szekeres Theorems

I found two theorems called "Erdos-Szekeres" theorem, I am not sure they're the same. The first one is about ordered sequences of numbers:

For any sequence of (r-1)(s-1)+1 distinct numbers, there is either an increasing sequence of length r or a descreasing subsequence of length s

Given a pair of integers s,t there is an integer, R(s,t) such that any 2-coloring of complete graph on n vertices has a red complete graph on s vertices or a blue complete graph on t vertices.

I have seen this in other contexts, a ramsey theory problem might be graph-theoretic in one version and combinatorial or number-theoretic in the other.

-
I have never heard the second theorem referred to by the name Erdos-Szekeres. That's just Ramsey's theorem. – Qiaochu Yuan Jun 9 '12 at 13:54
A bit late, but the introduction of arxiv.org/abs/1206.4001 mentions two distinct "Erdos-Szekeres" theorems. – js21 Jun 20 '12 at 6:04

They are not the same. Erdős and Szekeres (when they were students) proved that for any $k$ there is $n$ such that among any $n$ points in the plane (in general position) there are $k$ points which form a convex polygon. In the course of the proof they rediscovered Ramsey's theorem (the one that you quote about complete graphs or perhaps a more general version for hypergraphs). Erdős and Szekeres were not aware of Ramsey's work. See also this survey.
John: Yes, I think so. Of course there may exist a connection that I am not aware of. Checking out that survey and the original paper might clarify things. At any rate, the bound is exponential in the convexity problem unlike in the increasing sequence problem. Also the familiar binomial coefficient bound for $R(s,t)$ taught in school nowadays, is due to Erdős-Szekeres as far as I know. It is often called the Erdős-Szekeres bound for the Ramsey numbers. – GH from MO Jun 9 '12 at 16:58
Secondly, it is is true (and actually well-known) that the Ramsey theorem implies a kind of a "weak version" of the Erdős-Szekeres theorem. Namely, given an $n$-term sequence $\{a_1,...,a_n\}$, consider the complete graph on the vertex set $[n]$, coloring the edge $(i,j)$ with $1\le i<j\le n$ blue if $a_i\le a_j$, and red if $a_i>a_j$. Now if $n>R(s,t)$, then our graph has either blue complete subgraph on $s$ vertices, corresponding to a length-$s$ increasing subsequence, or a red complete subgraph on $t$ vertices, corresponding to a length-$t$ decreasing subsequence.