1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I have never heard the second theorem referred to by the name Erdos-Szekeres. That's just Ramsey's theorem. $\endgroup$
    – Qiaochu Yuan
    Commented Jun 9, 2012 at 13:54
  • $\begingroup$ A bit late, but the introduction of arxiv.org/abs/1206.4001 mentions two distinct "Erdos-Szekeres" theorems. $\endgroup$
    – js21
    Commented Jun 20, 2012 at 6:04
  • $\begingroup$ If you like my answer, please accept it officially (so that it turns green). Thanks in advance! $\endgroup$
    – GH from MO
    Commented Aug 19, 2018 at 23:01

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ so they rediscovered Ramsey theory in the context of these "convexity" problems, which are different from these increasing subsequence problem? $\endgroup$
    – john mangual
    Commented Jun 9, 2012 at 14:40
  • $\begingroup$ 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. $\endgroup$
    – GH from MO
    Commented Jun 9, 2012 at 16:58
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Jun 10, 2012 at 6:29
  • $\begingroup$ the convexity problem seems to be bounded by a corresponding Ramsey problem. $\endgroup$
    – john mangual
    Commented Aug 20, 2018 at 13:44
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Do you have a textbook or article reference for this result? $\endgroup$
    – Favst
    Commented Jun 23, 2022 at 17:44
  • $\begingroup$ @Favst: I am afraid I do not have any specific reference; just google for the "Ramsey theorem" or "Erdős-Szekeres theorem". $\endgroup$
    – Seva
    Commented Jun 23, 2022 at 18:30
  • $\begingroup$ No problem. I was wondering about a reference to resolve the monotonicity vs. strict monotonicity without bugging you too much. But I'll give it a go. Firstly, I was a little confused since you used set notation instead of list notation for the $a_i$, but now I get it's a list. Also, according to your argument, there is either a non-decreasing $s$-length subsequence or a strictly decreasing $t$-length subsequence. Is that what you meant in each case? Finally, I assume that if the integers are distinct, then either subsequence is strictly monotone? Sorry, I'm a technical fellow $\endgroup$
    – Favst
    Commented Jun 23, 2022 at 19:03
  • 1
    $\begingroup$ @Favst: everything you write seems correct to me. Also, the "standard" Erdos-Szekeres theorem deals with a set of pairwise distinct numbers, so you can replace $\le$ with $<$ in my answer to avoid any possibility of confusion. $\endgroup$
    – Seva
    Commented Jun 23, 2022 at 19:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .