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ősand George Szekeresgoes 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.
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.
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 pathof 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, , in the sequence with a pair , where is the length of the longest monotonically increasing subsequence ending with and is the length of the longest monotonically decreasing subsequence ending with . If we don't have a monotonically increasing or decreasing subsequence of the desired length, then each is between 1 and and each is between 1 and . So, there are possible pairs. Since there are numbers in the sequence, the
Pigeonhole principleguarantees that two numbers in the sequence, say and , have the same pairs. However, this is impossible for the following reason. Assume
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 координат, теорема Эрдёша Секереша гарантирует, что существует либо цепь такого ти … Википедия