# Erdős–Szekeres theorem

In

mathematics , the**Erdős–Szekeres theorem**is a finitary result, which makes precise one of the corollaries ofRamsey's theorem . While Ramsey's theorem makes it easy to prove that any sequence of distinct real numbers contains "either" a monotonically increasing infinitesubsequence , "or" a monotonically decreasing infinite subsequence, the result proved byPaul Erdős andGeorge Szekeres goes further. For given "r", "s" they showed that any sequence of length at least:"rs" − "r" − "s" + 2

contains "either" a monotonically increasing subsequence of length "r", "or" a monotonically decreasing subsequence of length "s". The proof appeared in the same 1935 paper that mentions the

Happy Ending problem . Steele (1995) contains "six or more" proofs of the theorem.**Example**For "r" = 3 and "s" = 2, the formula tells us that any permutation of three numbers has an increasing subsequence of length three or a decreasing subsequence of length two. Among the six permutations of the numbers 1,2,3:

* 1,2,3 has an increasing subsequence consisting of all three numbers

* 1,3,2 has a decreasing subsequence 3,2

* 2,1,3 has a decreasing subsequence 2,1

* 2,3,1 has two decreasing subsequences, 2,1 and 3,1

* 3,1,2 has two decreasing subsequences, 3,1 and 3,2

* 3,2,1 has three decreasing length-2 subsequences, 3,2, 3,1, and 2,1.**Geometric interpretation**One can interpret the positions of the numbers in a sequence as "x"-coordinates of points in the

Euclidean plane , and the numbers themselves as "y"-coordinates; conversely, for any point set in the plane, the "y"-coordinates of the points, ordered by their "x"-coordinates, forms a sequence of numbers. With this translation between sequences and point sets, the Erdős–Szekeres theorem can be interpreted as stating that in any set of at least "rs" − "r" − "s" + 2 points we can find apolygonal path of either "r" - 1 positive-slope edges or "s" - 1 negative-slope edges. For instance, taking "r" = "s" = 5, any set of at least 17 points has a four-edge path in which all slopes have the same sign.An example of "rs" − "r" − "s" + 1 points without such a path, showing that this bound is tight, can be formed by applying a small rotation to an ("r" - 1) by ("s" - 1) grid.

**Proof by the Pigeonhole principle**We prove the theorem by contradiction.We label each number, $n\_i$, in the sequence with a pair $(a\_i,b\_i)$, where $a\_i$ is the length of the longest monotonically increasing subsequence ending with $n\_i$ and $b\_i$ is the length of the longest monotonically decreasing subsequence ending with $n\_i$. If we don't have a monotonically increasing or decreasing subsequence of the desired length, then each $a\_i$ is between 1 and $r-1$ and each $b\_i$ is between 1 and $s-1$. So, there are $(r-1)(s-1)=rs-r-s+1$ possible $(a\_i,b\_i)$ pairs. Since there are $rs-r-s+2$ numbers in the sequence, the

Pigeonhole principle guarantees that two numbers in the sequence, say $n\_j$ and $n\_k$, have the same $(a\_i,b\_i)$pairs. However, this is impossible for the following reason. Assume $jmath>.\; If$ n\_j\; leq\; n\_k$,\; then\; we\; can\; append$ n\_k$to\; the\; monotonically\; increasing\; subsequence\; ending\; at$ n\_j$to\; get\; a\; longer\; monotonic\; subsequence.\; If$ n\_j\; geq\; n\_k$,\; then\; we\; can\; append$ n\_k$to\; the\; monotonically\; decreasing\; subsequence\; ending\; at$ n\_j$to\; get\; a\; longer\; monotonic\; subsequence.\; In\; each\; case,\; we\; reach\; a\; contradiction.\; So\; the\; assumption\; that\; we\; didn\text{'}t\; have\; a\; monotonic\; subsequence\; of\; the\; desired\; length\; was\; false.\; This\; proves\; the\; theorem.$**Proof via Dilworth's theorem**The Erdős–Szekeres theorem can be proved in several different ways; one of the proofs uses

Dilworth's theorem on chain decompositions in partial orders, or its simpler dual.To prove the theorem, define a partial ordering on the members of the sequence, in which "x" is less than or equal to "y" in the partial order if "x" ≤ "y" as numbers and "x" is not later than "y" in the sequence. A chain in this partial order is a monotonically increasing subsequence, and an antichain is a monotonically decreasing subsequence. By the dual of Dilworth's theorem, either there is a chain of length "r", or the sequence can be partitioned into at most "r" - 1 antichains; but in that case the largest of the antichains must form a decreasing subsequence with length at least:$leftlceilfrac\{rs-r-s+2\}\{r-1\}\; ight\; ceil=s.$

Alternatively, by Dilworth's theorem itself, either there is an antichain of length "s", or the sequence can be partitioned into at most "s" - 1 chains, the longest of which must have length at least "r".

**See also***

Longest increasing subsequence problem **References***cite journal

author = Erdős, Paul; Szekeres, George

title = A combinatorial problem in geometry

journal = Compositio Mathematica

volume = 2

pages = 463–470

year = 1935

url = http://www.numdam.org/item?id=CM_1935__2__463_0*cite conference

author = Steele, J. Michael

title = Variations on the monotone subsequence problem of Erdős and Szekeres

booktitle = Discrete Probability and Algorithms

editor = Aldous, Diaconis, and Steele, eds.

pages = 111–132

publisher = Springer-Verlag

location = New York

year = 1995

url = http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf**External links***

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**George Szekeres**— Infobox Scientist name = George Szekeres |300px image width = 300px caption = George Szekeres, 2001 birth date = birth date|1911|5|29|mf=y birth place = Budapest, Hungary death date = death date and age|2005|8|28|1911|5|29|mf=y death place =… … Wikipedia**Paul Erdős**— auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch Erdős Pál; * 26. März 1913 in Budapest, Österreich Ungarn; † 20. September … Deutsch Wikipedia**Paul Erdos**— Paul Erdős auf einem Seminar in Budapest (Herbst 1992) Paul Erdős [ˈɛrdøːʃ] (ungarisch: Erdős Pál) (* 26. März 1913 in Budapest, Ungarn; † 20. September 1996 in Warschau, Polen) war … Deutsch Wikipedia**Dilworth's theorem**— In mathematics, in the areas of order theory and combinatorics, Dilworth s theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician … Wikipedia**List of things named after Paul Erdős**— The following were named after Paul Erdős:* Erdős number * Erdős cardinal * Erdős conjecture a list of numerous conjectures named after Erdős ** Erdős conjecture on arithmetic progressions ** Cameron–Erdős conjecture ** Erdős–Burr conjecture **… … Wikipedia**George Szekeres**— (* 29. Mai 1911 in Budapest; † 28. August 2005 in Adelaide) war ein ungarisch australischer Mathematiker, der sich mit Kombinatorik beschäftigte. Leben und Werk Szekeres studierte Chemie … Deutsch Wikipedia**Happy Ending problem**— The Happy Ending problem (so named by Paul Erdős since it led to the marriage of George Szekeres and Esther Klein) is the following statement::Theorem. Any set of five points in the plane in general position [In this context, general position… … Wikipedia**List of mathematics articles (E)**— NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… … Wikipedia**Теорема Эрдёша-Секереша**— Цепь из четырёх рёбер с положительным наклоном на множестве из 17 точек. Если образовать последовательность y координат этих точек, в порядке их x координат, теорема Эрдёша Секереша гарантирует, что существует либо цепь такого типа, либо цепь той … Википедия**Теорема Эрдёша**— Цепь из четырёх рёбер с положительным наклоном на множестве из 17 точек. Если образовать последовательность y координат этих точек, в порядке их x координат, теорема Эрдёша Секереша гарантирует, что существует либо цепь такого ти … Википедия