Erdős–Szekeres theorem
Sufficiently long sequences of numbers have long monotonic subsequences
Erdős–Szekeres theorem
In mathematics, the Erdős–Szekeres theorem asserts that, given r {\displaystyle r} and s {\displaystyle s} , any sequence of distinct real numbers with length at least ( r − 1 ) ( s − 1 ) + 1 {\displaystyle (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.
Read on Wikipedia · Image David Eppstein, Public domain
Open boosters, collect cards and trade them. Free to play.
Play for free