Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Here's one about complete graphs:

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.

share|improve this question
1  
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
add comment

2 Answers

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.

share|improve this answer
    
so they rediscovered Ramsey theory in the context of these "convexity" problems, which are different from these increasing subsequence problem? –  john mangual Jun 9 '12 at 14:40
    
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
1  
The convex polygon theorem is also known as The Happy Ending Theorem --- the happy ending being the marriage of George Szekeres and Esther Klein, another student who brought the problem to the attention of Erdos and Szekeres. –  Gerry Myerson Jun 10 '12 at 6:29
add comment

Firstly, I second Qiaochu's remark that I've never heard the Ramsey theorem referred to as Erdős-Szekeres' theorem.

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.