Just a cool theorem about monotonic subequences.

Below is a pretty neat theorem which basically states that sufficiently long sequences must have long monotonic subsequences.

Erdos-Szekeres theorem: Given any sequence of $N^2+1$ real numbers $n_1, n_2, ..., n_{N^2+1}$, there must be a monotonically increasing subsequence of length $N$ or a monotonically decreasing subsequence of length $N$.

proof. Label each $n_i$ with a pair $(a_i, b_i)$ where $a_i$ is the length of the largest monotonically increasing subsequence ending at $n_i$ and $b_i$ is the length of the largest monotonically decreasing subsequence ending at $n_i$.

Now suppose for contradiction that the longest monotonically increasing and decreasing subsequences of $n_1, n_2, ..., n_{N^2+1}$ have length $\leq N$.

Obs 1: We have $N^2$ possible pairs $(a_i, b_i)$.

proof. We assumed that each $a_i, b_i \leq N$, the observation then follows.

Obs 2: For each $1\leq i<j\leq N^2+1$ we have that $(a_i, b_i) \not= (a_j, b_j)$.

proof. Fix any $1\leq i<N^2+1$, with pair $(a_i, b_i)$. For any $j>i$ we have two possible cases:

1. Either $n_i \leq n_j$, or
2. $n_i\geq n_j$.

Case $(1)$ implies that $a_i\not= a_j$ since we can extend the largest monotonically increasing subsequence ending at $n_i$ by adding $n_j$ on the end. Similarly, case $(2)$ implies that $b_i\not= b_j$.

Thus for the sequence $n_1, n_2, ..., n_{N^2+1}$, observation $2$ implies there are $N^2+1$ distinct pairs $(a_i, b_i)$, but observation $1$ states that we only have $N^2$ pairs to choose from. Thus there must be two identical pairs by the pigeonhole principle, a contradiction. This completes the proof.