Thread: Erdos-Szekeres theorem

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?

b.

Obtain on following sequence: (there is no increasing sequence of length

We start with:



then,



and so on to:




Obtain on following sequence: (there is no decreasing sequence of length


We start with:



proceed with:


and so on to:




Actually we proved that theorem is "Tightly bound"


Good-Luck!