Erdős–Szekeres theorem

Erdős–Szekeres theorem The Erdős–Szekeres theorem is a foundational result in Paul Erdős and George Szekeres's work on combinatorial sequences and order theory, asserting that any sufficiently long sequence of distinct real numbers contains a long monotone subsequence. Originating in 1935, it connects ideas from Ramsey theory, Dilworth's theorem, Sperner's theorem, Van der Waerden's theorem, and has influenced research by Paul Turán, Pál Erdős, József Komlós, Endre Szemerédi, and Alfréd Rényi.

Statement

The original formulation by Paul Erdős and George Szekeres states: for positive integers r and s, any sequence of (r−1)(s−1)+1 distinct real numbers contains an increasing subsequence of length r or a decreasing subsequence of length s. This quantitative claim is closely related to classical results such as Dilworth's theorem on partially ordered sets, Sperner's theorem on antichains in the Boolean algebra of subsets, and later developments by Richard Rado, C. St. J. A. Nash-Williams, and Tibor Gallai.

History and motivation

The theorem was proved in a 1935 paper by Paul Erdős and George Szekeres as part of investigations related to the Happy Ending problem for points in the plane and questions raised by Esther Klein. The motivation drew on problems considered by John von Neumann, Pál Turán, and Paul Turán concerning monotone subsequences and the combinatorial structure of sequences, paralleling concurrent work in graph theory by Frank Harary and W. T. Tutte. Its origins also intersect with geometric configurations studied by Gábor Fejes Tóth and combinatorial geometry explored by Béla Grünbaum.

Proofs and variations

Erdős and Szekeres provided an elementary double-counting and pigeonhole argument; subsequent proofs have used techniques from Ramsey theory as developed by Frank P. Ramsey and structural decompositions akin to Dilworth's theorem proved by Robert P. Dilworth. Alternative proofs employ the Erdős–Szekeres monotone subsequence lemma approach, connections to Sperner's theorem as refined by László Lovász, and bijective methods inspired by G. H. Hardy and John Littlewood. Variations include bounds improvements for special sequences studied by Endre Szemerédi and extremal constructions related to Turán-type problems investigated by Zoltán Füredi and Paul Turán.

Generalizations and related results

The theorem generalizes to multidimensional permutations and posets studied by Richard Stanley, Miklós Bóna, and Svenja Huneke; its multidimensional forms relate to results by Richard Rado and extensions by László Lovász and Neil Robertson. Generalizations include sequence Ramsey-type statements connected to Van der Waerden's theorem and structural analogues in Erdős–Gallai theory and the work of József Komlós on subsequence selection. Related combinatorial principles include Sperner's theorem, Mirsky's theorem, and decomposition results by Tibor Gallai.

Applications and examples

Applications span combinatorial geometry, computer science, and discrete analysis: the theorem underlies proofs in the Happy Ending problem and bounds in planar point set problems studied by Paul Erdős and George Szekeres; it informs algorithmic analyses in work by Donald Knuth and Edmonds on longest increasing subsequence algorithms; and it appears in probabilistic combinatorics developed by Alfréd Rényi and Erdős's collaborators. Concrete examples include minimal sequences demonstrating tightness of the bound constructed in the style of Erdős and Szekeres and extremal examples considered by Pál Erdős's school.

Category:Combinatorics