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