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 distinct real numbers contains a monotone subsequence of length . That is 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 distinct reals contains an increasing subsequence of length or a decreasing subsequence of length . Setting gives the first version. The first version appears in the archive as the monotone subsequence problem, and the general form as its version.
Two small cases to calibrate. Any distinct numbers contain a monotone run of length . Any distinct numbers contain a monotone run of length , since .
The proof: two labels
Let the sequence be with . For each term attach a pair of numbers:
- , the length of the longest increasing subsequence that ends at ;
- , the length of the longest decreasing subsequence that ends at .
Suppose, for a contradiction, that there is no increasing subsequence of length and no decreasing one of length . Then and , so there are at most possible pairs . There are terms. Two terms share a pair.
That is impossible. Take . If , then you can extend any increasing subsequence ending at by , so . If , the same argument gives . 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 numbers: . Compute the labels for each term, left to right.
The labels, term by term, are , , , , , , , , , . All ten are different, as the proof says they must be. Because , some label has to reach , and three of them do. The term has , an increasing run such as . The term has , a decreasing run such as .
The theorem is sharp
You cannot lower the number . A sequence of numbers can avoid any monotone run of length . For take . 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 , and the longest decreasing run takes one term per block, which is . Nine numbers, and no run of length .
The same construction works for any and : take blocks of length , so that each block increases and the blocks decrease from one to the next. The longest increasing run is and the longest decreasing run is . So numbers is not enough, and is exactly the threshold.
When to reach for it
- A sequence, a permutation, or a list of distinct numbers, and a claim that a long monotone subsequence exists.
- A row of people with different heights. The classic form: from people in a row you can ask to step out so that the remaining eleven stand in order of height, either increasing or decreasing. That is , with .
- Items with two numbers each. Say height and weight, all distinct. Sort by height and the weights form a sequence. A long increasing run is a chain where both go up, and a long decreasing run is a chain where height goes up and weight goes down.
- A long chain or a large antichain. The same idea, sorting elements by the longest chain that ends at them, shows that any finite partial order with elements has a chain or an antichain of size .
Traps
The numbers must be distinct. With repeats the statement needs care: in a list of equal numbers there is no strictly monotone run longer than . The fix is to make one direction non-strict: any sequence of reals has a non-decreasing subsequence of length or a strictly decreasing one of length . 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 terms, and find the monotone run of length that the theorem promises. The problem archive has more problems of this type.
Related guides
- Ramsey problems for beginners: one move, four levelsRamsey olympiad problems in order of difficulty, from six people to three colours and number puzzles. One vertex, pigeonhole its edges, then look inside.
- Extremal graph problems for beginners: the bound and the exampleAn extremal graph problem is two problems: a bound nobody can beat and an example that reaches it. How to spot one, and which vertex to pick first.
- How to spot a pigeonhole problem in under a minutePigeonhole is easy to understand and hard to recognise. Four signals that tell you to reach for it, and the three questions that turn a signal into boxes.
- How many practice problems should you do a day?The daily count is the wrong target. How to size a practice session from your miss rate and review time, and why a mixed set beats a bigger one.
- Greedy arguments in olympiad combinatorics: when they workGreedy is the first idea on every construction problem and the one most often marked zero. How to tell when it works, and the two proofs it always owes.
Techniques in this guide
- Pigeonhole PrincipleMore pigeons than holes means a shared hole.
Competitions this guide helps with
- AMC 825 multiple-choice questions · 40 minutes
- UKMT Junior Challenge25 multiple-choice questions · 60 minutes
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