Lemma › Guides › Erdős–Szekeres theorem: monotone subsequences and the proof
Guide

Erdős–Szekeres theorem: monotone subsequences and the proof

Take any list of distinct numbers in any order. If the list is long enough, you are forced to find a long run that only goes up or only goes down, with gaps allowed. The Erdős–Szekeres theorem says exactly how long the list has to be. The proof is a short pigeonhole argument that you can rebuild whenever you need it.

The statement

Any sequence of n2+1n^2 + 1 distinct real numbers contains a monotone subsequence of length n+1n + 1. That is n+1n + 1 terms, taken in order from the sequence and not necessarily next to each other, that either increase all the way or decrease all the way.

The general form has two parameters. Any sequence of mn+1mn + 1 distinct reals contains an increasing subsequence of length m+1m + 1 or a decreasing subsequence of length n+1n + 1. Setting m=nm = n gives the first version. The first version appears in the archive as the monotone subsequence problem, and the general form as its mn+1mn + 1 version.

Two small cases to calibrate. Any 55 distinct numbers contain a monotone run of length 33. Any 1010 distinct numbers contain a monotone run of length 44, since 10=32+110 = 3^2 + 1.

The proof: two labels

Let the sequence be x1,x2,…,xNx_1, x_2, \dots, x_N with N=mn+1N = mn + 1. For each term xix_i attach a pair of numbers:

Suppose, for a contradiction, that there is no increasing subsequence of length m+1m + 1 and no decreasing one of length n+1n + 1. Then 1≤ai≤m1 \le a_i \le m and 1≤di≤n1 \le d_i \le n, so there are at most mnmn possible pairs (ai,di)(a_i, d_i). There are mn+1mn + 1 terms. Two terms share a pair.

That is impossible. Take i<ji < j. If xi<xjx_i < x_j, then you can extend any increasing subsequence ending at xix_i by xjx_j, so aj≥ai+1a_j \ge a_i + 1. If xi>xjx_i > x_j, the same argument gives dj≥di+1d_j \ge d_i + 1. The numbers are distinct, so one of the two happens, and the pairs differ. So the pigeonhole is a contradiction, and a long run exists.

A worked example

Here is a sequence of 1010 numbers: 7,2,9,4,1,8,5,10,3,67, 2, 9, 4, 1, 8, 5, 10, 3, 6. Compute the labels (ai,di)(a_i, d_i) for each term, left to right.

The labels, term by term, are (1,1)(1,1), (1,2)(1,2), (2,1)(2,1), (2,2)(2,2), (1,3)(1,3), (3,2)(3,2), (3,3)(3,3), (4,1)(4,1), (2,4)(2,4), (4,3)(4,3). All ten are different, as the proof says they must be. Because 10=32+110 = 3^2 + 1, some label has to reach 44, and three of them do. The term 1010 has a=4a = 4, an increasing run such as 2,4,8,102, 4, 8, 10. The term 33 has d=4d = 4, a decreasing run such as 9,8,5,39, 8, 5, 3.

The theorem is sharp

You cannot lower the number n2+1n^2 + 1. A sequence of n2n^2 numbers can avoid any monotone run of length n+1n + 1. For n=3n = 3 take 7,8,9,4,5,6,1,2,37, 8, 9, 4, 5, 6, 1, 2, 3. It is built from three blocks. Inside a block the numbers go up. From block to block they go down. The longest increasing run lives inside a block, which is 33, and the longest decreasing run takes one term per block, which is 33. Nine numbers, and no run of length 44.

The same construction works for any mm and nn: take nn blocks of length mm, so that each block increases and the blocks decrease from one to the next. The longest increasing run is mm and the longest decreasing run is nn. So mnmn numbers is not enough, and mn+1mn + 1 is exactly the threshold.

When to reach for it

Traps

The numbers must be distinct. With repeats the statement needs care: in a list of n2+1n^2 + 1 equal numbers there is no strictly monotone run longer than 11. The fix is to make one direction non-strict: any sequence of n2+1n^2 + 1 reals has a non-decreasing subsequence of length n+1n + 1 or a strictly decreasing one of length n+1n + 1. The same labels prove it.

The run is a subsequence, so it need not be contiguous. People sometimes look for consecutive terms and conclude the claim is false.

The labels must be the length of the longest run ending at each term. Using the longest run anywhere in the sequence gives labels that can repeat freely, and the pigeonhole argument no longer separates the terms.

Finally, the bound is on the length, and you get no information about where the run sits. If the problem wants the run in a particular place, you need a different argument.

Where it sits

This is pigeonhole with a clever choice of pigeonholes: the boxes are the pairs, and the pigeons are the terms. In other problems you invent the labels yourself. Ask what quantity you can attach to each term so that two terms can never share it. For practice, state the labels for a sequence of your own with 1717 terms, and find the monotone run of length 55 that the theorem promises. The problem archive has more problems of this type.

Related guides

Techniques in this guide

Competitions this guide helps with

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level