# Math Help - Erdos-Szekeres theorem

1. ## Erdos-Szekeres theorem

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

a) Prove: For m,n $\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 $x_{1},x_{2},\ldots,x_{mn+1}$, place these elements into a set of ordered columns as follows:

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

The elements of any column correspond to an increasing subsequence. Also note that we only shift to a later column when the $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?

2. ## My way to...

b.

Obtain on following sequence: (there is no increasing sequence of length $n+1$

$(m-1)n+1,(m-1)n+2,...,(m-1)n+n=mn$

then,

$(m-2)n+1,(m-2)n+2,...,(m-2)n+n=(m-1)n$

and so on to:

$1,2,...,n$

Obtain on following sequence: (there is no decreasing sequence of length $m+1$

$m,2m,...,nm$

proceed with:

$m-1,2m-1,...,nm-1$
and so on to:

$1,m+1,(n-1)m+1$

Actually we proved that theorem is "Tightly bound"

Good-Luck!