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 associates 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 Longest increasing subsequence problem References External links Ramsey theory Permutation patterns Theorems in discrete geometry Articles containing proofs Szekeres theorem Theorems in discrete mathematics