View source for HR 8832

[[Image:Monotone-subseq-17-5.svg|thumb|240px|A path of four positively sloped edges in a set of 17 points. If one forms a sequence of the ''y''-coordinates of the points, in order by their ''x''-coordinates, the Erdős–Szekeres theorem ensures that there exists either a path of this type or one the same length in which all slopes are&nbsp;≤&nbsp;0.  However, if the central point is omitted, no such path would exist.]]
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 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 length at least (''r''&nbsp;&minus;&nbsp;1)(''s''&nbsp;&minus;&nbsp;1)&nbsp;+&nbsp;1 contains a monotonically increasing subsequence of length&nbsp;''r'' ''or'' a monotonically decreasing subsequence of length&nbsp;''s''. The proof appeared in the same 1935 paper that mentions the [[Happy Ending problem]].<ref>{{Citation
  | author = [[Paul Erdős|Erdős, Paul]]; [[George Szekeres|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
  | postscript = .}}</ref>

== Example ==
For ''r''&nbsp;=&nbsp;3 and ''s''&nbsp;=&nbsp;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 ==
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''&nbsp;&minus;&nbsp;''r''&nbsp;&minus;&nbsp;''s''&nbsp;+&nbsp;2 points we can find a [[polygonal path]] of either ''r''&nbsp;&minus;&nbsp;1 positive-slope edges or ''s''&nbsp;&minus;&nbsp;1 negative-slope edges. For instance, taking ''r''&nbsp;=&nbsp;''s''&nbsp;=&nbsp;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''&nbsp;&minus;&nbsp;''r''&nbsp;&minus;&nbsp;''s''&nbsp;+&nbsp;1 points without such a path, showing that this bound is tight, can be formed by applying a small rotation to an (''r''&nbsp;&minus;&nbsp;1) by (''s''&nbsp;&minus;&nbsp;1) grid.

The Erdős–Szekeres theorem may also be interpreted in the language of [[permutation pattern]]s as stating that every permutation of length at least ''rs''&nbsp;+&nbsp;1 must contain either the pattern 1, 2, 3, ..., ''r''&nbsp;+&nbsp;1 or the pattern ''s''&nbsp;+&nbsp;1, ''s'', ..., 2, 1.

==Proofs==
The Erdős–Szekeres theorem can be proved in several different ways; {{harvtxt|Steele|1995}} surveys six different proofs of the Erdős–Szekeres theorem, including the following two.<ref name="steele">{{citation
 | last = Steele | first = J. Michael | authorlink = J. Michael Steele
 | contribution = Variations on the monotone subsequence theme of Erdős and Szekeres
 | editor1-last = Aldous | editor1-first = David | editor1-link = David Aldous
 | editor2-last = Diaconis | editor2-first = Persi | editor2-link = Persi Diaconis
 | editor3-last = Spencer | editor3-first = Joel | editor3-link = Joel Spencer
 | editor4-last = Steele | editor4-first = J. Michael | editor4-link = J. Michael Steele
 | pages = 111–131
 | publisher = Springer-Verlag
 | series = IMA Volumes in Mathematics and its Applications
 | title = Discrete Probability and Algorithms
 | url = http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf
 | volume = 72
 | year = 1995}}.</ref> Other proofs surveyed by Steele include the original proof by Erdős and Szekeres as well as those of {{harvtxt|Blackwell|1971}},<ref>{{citation
 | doi = 10.2307/2317525
 | last = Blackwell | first = Paul
 | issue = 3
 | journal = American Mathematical Monthly
 | pages = 273–273
 | title = An alternative proof of a theorem of Erdős and Szekeres
 | volume = 78
 | year = 1971
 | jstor = 2317525}}.</ref> {{harvtxt|Hammersley|1972}},<ref>{{citation
 | last = Hammersley | first = J. M. | author-link = John Hammersley
 | contribution = A few seedlings of research
 | pages = 345–394
 | publisher = University of California Press
 | title = Proc. 6th Berkeley Symp. Math. Stat. Prob.
 | year = 1972}}. As cited by {{harvtxt|Steele|1995}}.</ref> and {{harvtxt|Lovász|1979}}.<ref>{{citation
 | last = Lovász | first = László | author-link = László Lovász
 | contribution = Solution to Exercise 14.25
 | publisher = North-Holland
 | title = Combinatorial Problems and Exercises
 | year = 1979}}. As cited by {{harvtxt|Steele|1995}}.</ref>

===Pigeonhole principle===
Given a sequence of length (''r''&nbsp;&minus;&nbsp;1)(''s''&nbsp;&minus;&nbsp;1)&nbsp;+&nbsp;1, label each number ''n<sub>i</sub>'' in the sequence with the pair (''a<sub>i</sub>'',''b<sub>i</sub>''), where ''a<sub>i</sub>'' is the length of the longest monotonically increasing subsequence ending with ''n<sub>i</sub>'' and ''b<sub>i</sub>'' is the length of the longest monotonically decreasing subsequence ending with ''n<sub>i</sub>''. Each two numbers in the sequence are labeled with a different pair: if {{nowrap|''i'' < ''j''}} and {{nowrap|''n<sub>i</sub>'' < ''n<sub>j</sub>''}} then {{nowrap|''a<sub>i</sub>'' < ''a<sub>j</sub>''}}, and on the other hand if {{nowrap|''n<sub>i</sub>'' > ''n<sub>j</sub>''}} then {{nowrap|''b<sub>i</sub>'' < ''b<sub>j</sub>''}}. But there are only (''r''&nbsp;&minus;&nbsp;1)(''s''&nbsp;&minus;&nbsp;1) possible labels in which ''a<sub>i</sub>'' is at most ''r''&nbsp;&minus;&nbsp;1 and ''b<sub>i</sub>'' is at most ''s''&nbsp;&minus;&nbsp;1, so by the [[pigeonhole principle]] there must exist a value of ''i'' for which ''a<sub>i</sub>'' or ''b<sub>i</sub>'' is outside this range. If ''a<sub>i</sub>'' is out of range then ''n<sub>i</sub>'' is part of an increasing sequence of length at least ''r'', and if ''b<sub>i</sub>'' is out of range then ''n<sub>i</sub>'' is part of a decreasing sequence of length at least ''s''.

{{harvtxt|Steele|1995}} credits this proof to the one-page paper of {{harvtxt|Seidenberg|1959}} and calls it "the slickest and most systematic" of the proofs he surveys.<ref name="steele"/><ref>{{citation
 | last = Seidenberg | first = A. | authorlink = Abraham Seidenberg
 | journal = Journal of the London Mathematical Society
 | page = 352
 | title = A simple proof of a theorem of Erdős and Szekeres
 | url = http://jlms.oxfordjournals.org/cgi/reprint/s1-34/3/352.pdf
 | volume = 34
 | year = 1959}}.</ref>

===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''&nbsp;≤&nbsp;''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''&nbsp;&minus;&nbsp;1 antichains; but in that case the largest of the antichains must form a decreasing subsequence with length at least
:<math>\left\lceil\frac{rs-r-s+2}{r-1}\right\rceil=s.</math>

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

== See also ==
* [[Longest increasing subsequence problem]]

== References ==
{{Reflist}}

== External links ==
* {{mathworld | urlname = Erdos-SzekeresTheorem | title = Erdős-Szekeres Theorem}}

{{DEFAULTSORT:Erdos-Szekeres theorem}}
[[Category:Ramsey theory]]
[[Category:Permutation patterns]]
[[Category:Theorems in discrete geometry]]
[[Category:Articles containing proofs]]
[[Category:Paul Erdős|Szekeres theorem]]
[[Category:Theorems in discrete mathematics]]