To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Erdős–Szekeres theorem

From Wikipedia, the free encyclopedia

A path of four upward-sloping edges in a set of 17 points. By the Erdős–Szekeres theorem, every set of 17 points has a path of this length that slopes either upward or downward.  The 16-point subset with the central point removed has no such path.
A path of four upward-sloping edges in a set of 17 points. By the Erdős–Szekeres theorem, every set of 17 points has a path of this length that slopes either upward or downward. The 16-point subset with the central point removed has no such path.

In mathematics, the Erdős–Szekeres theorem is a finitary result that makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that every infinite sequence of distinct real numbers contains 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 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.[1]

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, 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 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 ⌊n-1⌋ 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 patterns as stating that every permutation of length at least rs + 1 must contain either the pattern 1, 2, 3, ..., r + 1 or the pattern s + 1, s, ..., 2, 1.

Proofs

The Erdős–Szekeres theorem can be proved in several different ways; Steele (1995) surveys six different proofs of the Erdős–Szekeres theorem, including the following two.[2] Other proofs surveyed by Steele include the original proof by Erdős and Szekeres as well as those of Blackwell (1971),[3] Hammersley (1972),[4] and Lovász (1979).[5]

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 i < j and ninj then ai < aj, and on the other hand if ninj then bi < bj. 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 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.

Steele (1995) credits this proof to the one-page paper of Seidenberg (1959) and calls it "the slickest and most systematic" of the proofs he surveys.[2][6]

Dilworth's theorem

Another of the proofs uses Dilworth's theorem on chain decompositions in partial orders, or its simpler dual (Mirsky's theorem).

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 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

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.

Recall that the Robinson–Schensted correspondence associate to each sequence a Young tableau 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

References

  1. ^ Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry", Compositio Mathematica, 2: 463–470, doi:10.1007/978-0-8176-4842-8_3, Zbl 0012.27010.
  2. ^ a b Steele, J. Michael (1995), "Variations on the monotone subsequence theme of Erdős and Szekeres", in Aldous, David; Diaconis, Persi; Spencer, Joel; Steele, J. Michael (eds.), Discrete Probability and Algorithms (PDF), IMA Volumes in Mathematics and its Applications, 72, Springer-Verlag, pp. 111–131, ISBN 0-387-94532-6.
  3. ^ Blackwell, Paul (1971), "An alternative proof of a theorem of Erdős and Szekeres", American Mathematical Monthly, 78 (3): 273–273, doi:10.2307/2317525, JSTOR 2317525.
  4. ^ Hammersley, J. M. (1972), "A few seedlings of research", Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, pp. 345–394. As cited by Steele (1995).
  5. ^ Lovász, László (1979), "Solution to Exercise 14.25", Combinatorial Problems and Exercises, North-Holland. As cited by Steele (1995).
  6. ^ Seidenberg, A. (1959), "A simple proof of a theorem of Erdős and Szekeres" (PDF), Journal of the London Mathematical Society, 34: 352, doi:10.1112/jlms/s1-34.3.352[dead link].

External links

This page was last edited on 7 May 2021, at 18:45
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.