This concerns a more general version of the Erdos-Szekeres theorem.
a) Prove: For m,n 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 , place these elements into a set of ordered columns as follows:
Place at the top of the first column. For each subsequent , if is greater than the value that is on top of a column, put that on top of the first such column, otherwise start a new column with that .
The elements of any column correspond to an increasing subsequence. Also note that we only shift to a later column when the 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?