Suggest a Book

# Erdos-Szekeres Theorem

Level: unknown

posted Jun 05 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...
• Prove that for given integers $r, s$ any sequence of distinct real numbers of length at least $(r - 1)(s - 1) + 1$ contains either a monotonically increasing subsequence of length $r$, or a monotonically decreasing subsequence of length $s$.

• Prove that every sequence of $n^2$ distinct numbers contains a subsequence of length $n$ which is monotone (i.e. either always increasing or always decreasing).

Source: designed by Erdos and Szekeres
delete retag edit

## Stats

Posted: Jun 05 '12

Seen: 75 times

Last updated: Jun 12 '12