Erdős–Szekeres theorem (monotone subsequences)

Every sequence of at least (r−1)(s−1)+1 distinct real numbers contains an increasing subsequence of length r or a decreasing subsequence of length s. The bound is sharp.

Pigeonhole principle: If more objects are assigned to fewer containers, some container holds at least two objects. The proof assigns each term a pair of subsequence lengths; too many terms force a repeated pair.
Paul Erdős: A Hungarian mathematician known for prolific collaboration and contributions across discrete mathematics. He co-authored the 1935 paper that established the theorem with George Szekeres.
Schur's theorem: A theorem stating that every finite coloring of the positive integers has a monochromatic solution to x + y = z. Its use of finite colorings and unavoidable patterns reflects a broader Ramsey-style viewpoint.
Ramsey's theorem: A family of theorems guaranteeing homogeneous substructures in sufficiently large structures. The sequence result is a small, explicit instance of unavoidable order patterns.
Longest increasing subsequence: A longest subsequence of a sequence whose terms increase strictly. The increasing-coordinate of each term measures its longest increasing subsequence ending there.
George Szekeres: A Hungarian-Australian mathematician whose work included combinatorics and geometry. He co-authored the theorem’s first proof and independently posed its geometric counterpart.
Dilworth's theorem: A finite partially ordered set has maximum chain size equal to its minimum chain-cover size. Both results turn restrictions on chains into guarantees about ordered subsequences or decompositions.
Sperner's theorem: The largest antichain in the Boolean lattice of subsets of an n-element set has size \(\binom{n}{\lfloor n/2\rfloor}\). It studies a different extremal constraint on order, rather than monotone subsequences in a linear sequence.
Longest decreasing subsequence: A longest subsequence of a sequence whose terms decrease strictly. The decreasing-coordinate completes the pair used to bound how many terms can occur.
Erdős–Szekeres theorem (convex polygons): A theorem guaranteeing a convex polygon among sufficiently many points in general position. The 1935 paper introduced this geometric problem alongside the monotone-subsequence result.

Linked from 3 pages

Ramsey theoryRelated: It is a classic sequence result with a Ramsey-style guarantee of order.