Erdős–Szekeres Theorem
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the Erdős–Szekeres theorem asserts that, given ''r'', ''s,'' any sequence of distinct real numbers with length at least (''r'' − 1)(''s'' − 1) + 1 contains 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 In mathematics, the "happy ending problem" (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Szekeres, Esther Klein) is the following statement: This was one of the original results that led to the develop ...
. It is a finitary result that makes precise one of the corollaries of
Ramsey's theorem In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (sa ...
. While Ramsey's theorem makes it easy to prove that every infinite sequence of distinct real numbers contains a monotonically increasing infinite
subsequence In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a ...
''or'' a monotonically decreasing infinite subsequence, the result proved by
Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...
and
George Szekeres George Szekeres AM FAA (; 29 May 1911 – 28 August 2005) was a Hungarian–Australian mathematician. Early years Szekeres was born in Budapest, Hungary, as Szekeres György and received his degree in chemistry at the Technical University of ...
goes further.


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.


Alternative interpretations


Geometric interpretation

One can interpret the positions of the numbers in a sequence as ''x''-coordinates of points in the
Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
, 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 (unless two of the points have equal ''x''-coordinates). 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 In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments co ...
of either ''r'' − 1 positive-slope edges or ''s'' − 1 negative-slope edges. In particular (taking ''r'' = ''s''), in any set of at least ''n'' points we can find a polygonal path of at least ⌊⌋ edges with same-sign slopes. 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.


Permutation pattern interpretation

The Erdős–Szekeres theorem may also be interpreted in the language of
permutation pattern In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of a ...
s as stating that every permutation of length at least (''r'' - 1)(''s'' - 1) + 1 must contain either the pattern 12⋯''r'' or the pattern ''s''⋯21.


Proofs

The Erdős–Szekeres theorem can be proved in several different ways; surveys six different proofs of the Erdős–Szekeres theorem, including the following two.. Other proofs surveyed by Steele include the original proof by Erdős and Szekeres as well as those of , , and .


Pigeonhole principle

Given a sequence of length (''r'' − 1)(''s'' − 1) + 1, label each number ''ni'' in the sequence with the pair (''ai'', ''bi''), where ''ai'' is the length of the longest monotonically increasing subsequence ending with ''ni'' and ''bi'' is the length of the longest monotonically decreasing subsequence ending with ''ni''. Each two numbers in the sequence are labeled with a different pair: if and then , and on the other hand if then . But there are only (''r'' − 1)(''s'' − 1) possible labels if ''ai'' is at most ''r'' − 1 and ''bi'' is at most ''s'' − 1, so by the
pigeonhole principle In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, of three gloves, at least two must be right-handed or at least two must be l ...
there must exist a value of ''i'' for which ''ai'' or ''bi'' is outside this range. If ''ai'' is out of range then ''ni'' is part of an increasing sequence of length at least ''r'', and if ''bi'' is out of range then ''ni'' is part of a decreasing sequence of length at least ''s''. credits this proof to the one-page paper of and calls it "the slickest and most systematic" of the proofs he surveys.


Dilworth's theorem

Another of the proofs uses
Dilworth's theorem In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all ...
on chain decompositions in partial orders, or its simpler dual (
Mirsky's theorem In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for and is closely ...
). 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 In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
is a monotonically decreasing subsequence. By Mirsky'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 :\left\lceil\frac\right\rceil=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''.


Application of the Robinson–Schensted correspondence

The result can also be obtained as a corollary of the
Robinson–Schensted correspondence In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remar ...
. Recall that the Robinson–Schensted correspondence associates to each sequence a
Young tableau In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups an ...
''P'' whose entries are the values of the sequence. The tableau ''P'' has the following properties: * The length of the longest increasing subsequence is equal to the length of the first row of ''P''. * The length of the longest decreasing subsequence is equal to the length of the first column of ''P''. Now, it is not possible to fit (''r'' − 1)(''s'' − 1) + 1 entries in a square box of size (''r'' − 1)(''s'' − 1), so that either the first row is of length at least ''r'' or the last row is of length at least ''s''.


See also

* Longest increasing subsequence problem


References


External links

* {{DEFAULTSORT:Erdos-Szekeres theorem Ramsey theory Permutation patterns Theorems in discrete geometry Articles containing proofs Szekeres theorem Theorems in discrete mathematics