This concerns a more general version of the Erdos-Szekeres theorem.

a) Prove: For m,n$\displaystyle \geq$1, if S is a sequence of mn + 1 distinct real numbers, then S contains either an increasing subsequence of length m + 1 or a decreasing subsequence of length n + 1.

Given a sequence S of mn + 1 distinct real numbers $\displaystyle x_{1},x_{2},\ldots,x_{mn+1}$, place these elements into a set of ordered columns as follows:

Place $\displaystyle x_{1}$ at the top of the first column. For each subsequent $\displaystyle x_{i}$, if $\displaystyle x_{i}$ is greater than the value that is on top of a column, put that $\displaystyle x_{i}$ on top of the first such column, otherwise start a new column with that $\displaystyle x_{i}$.

The elements of any column correspond to an increasing subsequence. Also note that we only shift to a later column when the $\displaystyle x_{i}$ was smaller than all the top numbers of the previous columns. The top numbers of the columns form a decreasing subsequence. By the pigeon hole principle, if we have n or fewer columns then at least one of the columns must contain greater than m members since we started with mn+1 elements. Similarly, if every column contains m or fewer members we must have greater than n columns. QED

b) Prove that this result is best possible by showing that the result doesn't necessarily hold when mn + 1 is replaced by mn.

Using the same argument as above we could have n columns but only m members in each column. Therefore we could only guarantee subsequences of m increasing and n decreasing members. QED

Is the reasoning for a and b correct?