Today, we will discuss a beautiful result of Paul Erdős (1913–1996) and George Szekeres (1911–2005), proved in 1935, about finite sequences of real numbers. The inspiration of the result comes from Ramsey Theory, which, quoting the Wikipedia article,

“Studies the conditions under which order must appear in relation to disorder.”

Today’s problem can be very simply stated as the following game. We start by writing down numbers, one by one, with the only restriction that these numbers have to be distinct. In other words, the same number cannot appear twice. Then, the challenge is to keep writing numbers in such a way, so that no “long” monotone subsequence appears. More precisely, once we have written down Nnumbers, an adversary is allowed to delete some of them, and the ones that remain should not form a “long” monotone (either only increasing or only decreasing) sequence. We will quantify soon what “long” means here. If no such monotone subsequence appears, we win! Otherwise, the adversary wins…

It is well-known that:

Every infinite sequence of distinct real numbers contains a monotonically increasing infinite subsequence or a monotonically decreasing infinite subsequence.

The Erdős-Szekeres theorem makes an analogous claim when the sequence is finite. So, it is a statement about the game we just mentioned above. More formally:

Theorem [Erdős-Szekeres 1935]

For given positive natural numbers s,r, any sequence of distinct real numbers whose length is at least N = s r + 1 contains a monotonically increasing subsequence of length s + 1 or a monotonically decreasing subsequence of length r + 1 (or both).

To make things more concrete, let’s set s =r = n, for some positive natural number n. If we write down N = n² + 1 distinct real numbers, no matter what numbers we write down, then there always will be a monotone subsequence of length n + 1. So, for example, if you write down 10 numbers, then a monotone subsequence of length 4 will always be there. Here is a concrete sequence of 10 numbers:

1, 10, 5, 6, 0, 2, 3, 11, 7, 4.

Going back to our game, if we define “long” to be 4, then the adversary wins in the above sequence, as one can pick 1,5,6,11 (or alternatively, 0, 2,3, 11 — there are other options as well) delete the rest, and there you have it, a monotone subsequence of length 4! If we define “long” to be 5, then there is still hope, and indeed, there is no monotone subsequence of length 5, so we win! This shows that the parameters in the above theorem cannot be improved, or in other words, they are tight.

A Beautiful Proof of the Erdős-Szekeres theorem by Seidenberg (1959)

There are many proofs of the Erdős-Szekeres theorem. Today, we will discuss one of the most beautiful ones, and one that most likely belongs to the BOOK! (if you want to know more about this BOOK, you can read the intro of this article of mine, or the intro of this Wikipedia article).

We are ready to start. We will closely follow the exposition from the beautiful book “Extremal Combinatorics with applications in Computer Science” by Stasys Jukna.

Let

be a sequence of N distinct real numbers, where N = sr + 1, for some positive natural numbers s, r. The first key idea is the following. For each number of the sequence, we associate 2 coordinates (which we will view as points on the plane) as follows:

We clarify that in the above definition of xᵢ and yᵢ, we explicitly ask for subsequences that contain the term aᵢ. An important observation is that

This means that for any two terms of the sequence, the corresponding points, based on the two coordinates defined above, are different. To see this, consider i<j. We do some case analysis:

• aᵢ < aⱼ: In this case, the longest increasing subsequence ending at aᵢ can be extended by aⱼ, and thus, xⱼ ≥ xᵢ + 1.
• aᵢ > aⱼ: In this case, the longest decreasing subsequence starting at aⱼ can be extended by aᵢ, and thus, yᵢ ≥ yⱼ + 1.

We conclude that the above observation is indeed true. Observe here that we crucially used the fact that no two numbers of the sequence are the same.

We are now ready for the second main idea of the proof, which is the celebrated pigeonhole principle!

We construct the following N x N grid.

We now place each number aᵢ on the grid, according to its coordinates (xᵢ, yᵢ). We simply assume that the vertical axis corresponds to the x-coordinate and the horizontal axis to the y-coordinate.

Clearly, 1 ≤ xᵢ ≤ N and 1 ≤ yᵢ ≤ N for every i, so every number will appear in some grid cell. Moreover, by the observation above, no two numbers will end up in the same grid cell. We are almost there. Since N > s r, we have more numbers than the (s r) many grid cells that are shaded with grey in the above picture. So, if all of the numbers ended up in cells of the shaded region, the pigeonhole principle would imply that there exist at least two numbers aᵢ and aⱼ with the same coordinates. Since this is not the case, we conclude that there exists at least one number aᵢ of the sequence which is placed in a cell outside of the shaded area. But, this now implies that either its x-coordinate is strictly larger than s or its y-coordinate is strictly larger than r (or both). Looking again now at the definition of the (x,y)-coordinates, we immediately obtain the statement of the theorem. We are officially done!

Note: The above article contains Amazon Affiliate links.