What are some important applications of the Erdős-Szekeres Theorem?

Question

Erdős-Szekeres Theorem: Any finite sequence of $n^2+1$ real numbers contains a monotonic subsequence of length at least $n+1$.

I was wondering what are the most important applications of the Erdős-Szekeres Theorem.

For example, I have seen the use of the theorem in monotone sequences where one can claim that any sequence contains a monotone subsequence. In other words, one asserts that it is always certain to find ordered substructures of large disordered structures.

Does anyone know any other applications of the above theorem?

Thank you.

Answer 1

In fact, there is a more general form of the Erdős-Szekeres theorem:

Let $m,n \in \mathbb{Z}^{+}$. Every sequence of $mn + 1$ real numbers contains a monotonically increasing subsequence of $m+1$ terms or a monotonically decreasing subsequence of $n+1$ terms (or both).

Perhaps the best reference for this is Michael J. Steele's paper "Variations on the monotone subsequence theme of Erdős and Szekeres" (The link is taken from the wikipedia page for the Erdős–Szekeres theorem)

The connection between the Erdős–Szekeres theorem and the Dillworth's theorem is astonishing. Especially when you consider Dillworth's theorem in the following form:

In any partial order on a set of $mn+1$ elements, there exists a chain of length $m+1$ or an antichain of size $n+1$.

Then one can solve exersices like

1. Let $0<a_{1}<a_{2}<\cdots<a_{mn+1}$ be $mn+1$ integers. Prove that you can select either $m+1$ of them no one of which divides any other, or $n+1$ of them each dividing the following one.
2. For any $n^{2}+1$ closed intervals of $\mathbb{R}$, prove that $n+1$ of the intervals share a point or $n+1$ of the intervals are disjoint.

One should also check Section 3.5 Sequences and partial orders of the book Introduction to Combinatorics by Martin J. Erickson. (The above exersices are from there!) This may not be a complete answer to your question but I hope that I helped you.

Answer 2

Assume that we are given 26 distinct positive integers. Show that either there exist 6 of them $x_1<x_2<x_3<x_4<x_5<x_6$, with $x_1$ dividing $x_2$, $x_2$ dividing $x_3$, $x_3$ dividing $x_4$, $x_4$ dividing $x_5$ and $x_5$ dividing $x_6$ or there exist six of them, with no one dividing another one of these six.

A possibly good start is to assume that, in every six of these numbers, there exists at least one dividing another one of the same six.

Update. I have found a solution of the problem (for 17 numbers though) in a Russian site. As unbelievable as it may sound, this problem was a question in a 1983 Soviet Mathematics contest (Турниры Городов) for student of 7-8 grades!