The Erdős-Szekeres Theorem

What is a Monotonic Subsequence?

Before we state the theorem, let's be precise about our terms. A sequence is an ordered list of numbers. A subsequence is formed by deleting zero or more elements from the original sequence, while keeping the remaining elements in their original relative order.

A sequence is called monotonic if it is either non-decreasing (always going up or staying the same) or non-increasing (always going down or staying the same). The Erdős-Szekeres theorem is usually stated for distinct numbers, so we'll focus on strictly increasing or strictly decreasing subsequences.

Let's watch a short video segment that defines these terms with clear examples.

The Erdős-Szekeres Theorem

With those definitions in hand, we can now state the theorem.

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

This means that for any positive integer $n$, if you give me a sequence of $n^2+1$ different numbers, I can always find either an increasing subsequence of length $n+1$ or a decreasing subsequence of length $n+1$.

For example, if $n=3$, the theorem states that any sequence of $3^2+1=10$ distinct numbers must contain either an increasing or a decreasing subsequence of length $3+1=4$. This is a powerful guarantee of structure within randomness.

Proving the Theorem

The proof is a masterpiece of applying the Pigeonhole Principle. The main difficulty in many PHP proofs is not the principle itself, but cleverly defining the pigeons and pigeonholes.

Let's walk through the argument, which is one of the most famous in combinatorics. The core idea is to associate a special label with every element in our sequence. This label will capture information about the subsequences that end at that element.

The following reading from Yunian Pan's blog presents this proof with exceptional clarity. We will work through its logic here, and then you can read it to solidify your understanding.

Let's break down the proof from the reading.

1. The Setup:
We start with a sequence of $n^2+1$ distinct real numbers: $x_1,x_2,\dots ,x_{n^2+1}$.

2. The Clever Labeling (Defining the Pigeons):
For each element $x_k$ in the sequence (where $k$ goes from 1 to $n^2+1$), we assign a pair of integers as a label: $(a_k,b_k)$.

• $a_k$ is the length of the longest increasing subsequence that ends with $x_k$.
• $b_k$ is the length of the longest decreasing subsequence that ends with $x_k$.

At a minimum, any element by itself forms a subsequence of length 1, so $a_k\ge 1$ and $b_k\ge 1$.

3. The Crucial Insight: All Labels are Unique
This is the heart of the argument. Let's take any two elements from the sequence, say $x_i$ and $x_k$, where $i<k$. Because the numbers are distinct, there are only two possibilities for their values:

• Case 1: $x_i<x_k$. We can take the longest increasing subsequence ending at $x_i$ (which has length $a_i$) and append $x_k$ to it. This creates a new increasing subsequence ending at $x_k$ with length $a_i+1$. The longest one ending at $x_k$ must be at least this long. So, $a_k\ge a_i+1$. This directly implies that $a_k\ne a_i$.
• Case 2: $x_i>x_k$. By the same logic, we can take the longest decreasing subsequence ending at $x_i$ (length $b_i$) and append $x_k$. This gives a decreasing subsequence ending at $x_k$ of length $b_i+1$. Therefore, $b_k\ge b_i+1$, which implies $b_k\ne b_i$.

In either case, the label $(a_i,b_i)$ cannot be the same as the label $(a_k,b_k)$. Since this is true for any pair $i\ne k$, all $n^2+1$ labels must be unique. These unique labels are our pigeons.

4. The Contradiction (Defining the Pigeonholes):
Let's assume, for the sake of contradiction, that the theorem is false. This means there is no monotonic subsequence of length $n+1$.

What does this assumption imply about our labels?

• If there's no increasing subsequence of length $n+1$, then the length of any increasing subsequence must be at most $n$. So, for all $k$, $1\le a_k\le n$.
• Similarly, if there's no decreasing subsequence of length $n+1$, then for all $k$, $1\le b_k\le n$.

This assumption severely restricts the possible labels we can have. The first number in the pair, $a_k$, can only be one of $n$ values $\{1,\dots ,n\}$. The second number, $b_k$, can also only be one of $n$ values. This gives a total of $n\times n=n^2$ possible unique pairs $(a_k,b_k)$. These possible pairs are our pigeonholes.

5. Applying the Pigeonhole Principle:
Here's the contradiction:

• We have $n^2+1$ pigeons (the labels for each element, which we proved are all unique).
• We have only $n^2$ pigeonholes (the possible label values under our assumption).

By the Pigeonhole Principle, it's impossible to fit $n^2+1$ unique items into $n^2$ slots. Our assumption must have been wrong.

Therefore, there must be at least one monotonic subsequence of length $n+1$ or greater. This completes the proof.

Is the Theorem "Best Possible"?

The theorem guarantees a result for a sequence of length $n^2+1$. Could we do it with just $n^2$ numbers? The answer is no. To show this, we need to construct a counterexample: a sequence of length $n^2$ that has no monotonic subsequence of length $n+1$.

Consider this construction for $n=3$ (a sequence of length $3^2=9$):

Now, arrange these numbers in decreasing blocks:

• Longest increasing subsequence: To make an increasing subsequence, you can pick at most one number from each block. Since there are only $n=3$ blocks, the longest increasing subsequence has length at most 3.
• Longest decreasing subsequence: To make a decreasing subsequence, you must stay within a single block. Each block has length $n=3$, so the longest decreasing subsequence has length at most 3.

In this sequence of 9 numbers, no monotonic subsequence has length 4. This demonstrates that the bound $n^2+1$ is "tight" or "best possible."

You can see a more general visualization of this counterexample at the end of the Shahriari video.

Reflection

The primary goal of this lesson was to understand and internalize the proof. To ensure the concepts have settled, consider these questions:

1. A Generalization: The theorem we proved is a special case of a more general result: a sequence of $mn+1$ distinct real numbers has an increasing subsequence of length $m+1$ or a decreasing subsequence of length $n+1$. How would you adapt the proof we just saw to prove this? (Hint: Think about the pigeonholes. What would their dimensions be?)
2. The Role of "Distinct": Our proof relied on the numbers being distinct to ensure that if $x_i\ne x_k$, then either $x_i<x_k$ or $x_i>x_k$. What happens if numbers can be repeated? The theorem still holds if we look for a non-decreasing subsequence of length $n+1$ or a non-increasing subsequence of length $n+1$. How would the inequalities in the proof change to accommodate this?

Conclusion

Today, we've reached a high point in our study of the Pigeonhole Principle by proving the celebrated Erdős-Szekeres theorem. This result beautifully illustrates the power of combinatorial arguments to find order in chaos.

Key Takeaways:

• The Erdős-Szekeres Theorem guarantees that any sequence of $n^2+1$ distinct numbers contains a monotonic subsequence of length at least $n+1$.
• The proof is a classic application of the Pigeonhole Principle, using a clever labeling scheme.
• The core strategy was to assign a pair-label $(a_k,b_k)$ to each element $x_k$, representing the lengths of the longest increasing and decreasing subsequences ending at that element.
• By showing all $n^2+1$ labels are unique (pigeons) and that a contradiction implies only $n^2$ possible labels exist (pigeonholes), the theorem is proved.
• The bound of $n^2+1$ is tight; it is possible to construct a sequence of length $n^2$ with no monotonic subsequence of length $n+1$.

This concludes our module on the Pigeonhole Principle. You've seen how a surprisingly simple idea can lead to profound and powerful results.

In our next module, we will explore another fundamental tool in combinatorics: The Principle of Inclusion-Exclusion. This principle provides a systematic way to count the elements in the union of several sets, carefully correcting for overcounting, and it is essential for solving a wide range of complex counting problems.