In mathematics, 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. It 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. 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 ⌊⌋ 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