Erdős–Szekeres theorem

In mathematics, the Erdős–Szekeres theorem is a finitary result, which makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that any sequence of distinct real numbers contains "either" a monotonically increasing infinite subsequence, "or" a monotonically decreasing infinite subsequence, the result proved by Paul Erdős and George 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 a polygonal 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 j. 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'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 координат, теорема Эрдёша Секереша гарантирует, что существует либо цепь такого ти …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.