---
tag: 0SNJM8HSD3
kind: statement
role: theorem
name: Erdős–Szekeres theorem
msc: [05A05]
uses: [0BY7GN3449]
sources:
  - url: https://en.wikipedia.org/wiki/Erdős–Szekeres_theorem
    locator: lead section
same_as:
  wikidata: Q976607
  wikipedia: Erdős–Szekeres theorem
---

## Statement

Let $r$ and $s$ be positive integers.
Let $a_1, a_2, \dots, a_N$ be a sequence of $N = (r - 1)(s - 1) + 1$ distinct real numbers.
Then the sequence has an increasing subsequence of length $r$ or a decreasing subsequence of length $s$.

## Remarks

The bound is sharp: some sequence of $(r - 1)(s - 1)$ distinct numbers has neither type of subsequence.
For $r = s = 3$: each sequence of $5$ distinct numbers has a monotone subsequence of length $3$.
A short proof labels each term with the lengths of the longest increasing and decreasing subsequences that end at it. The labels are distinct, and the [[pigeonhole principle|0HGVCWQGY3]] finishes the proof.

## History

Paul Erdős and George Szekeres proved the theorem in 1935.

## Explanations

### L1 human

A long enough list of different numbers always contains a long subsequence that goes up or one that goes down. The terms need not be adjacent.
For example, $3, 1, 4, 5, 2$ has the increasing subsequence $3, 4, 5$.