The theorem of Erdös and Szekeres about monotone subsequences was part of their historic joint paper of 1935. It states that every sequence of n²+1 real numbers contains a monotone subsequence of length n. We consider a generalization of this statement and establish bounds for the generalized problem. (Un?)fortunately open questions still remain. We also prove more or less precise bounds for the random version of the problem, as well as for a simpler variant.

This is joint work with Gábor Tardos.