\documentstyle[11pt,twoside,macpsfig]{article}
\input{../macros-course}

\addtolength{\topmargin}{-.8in}
\setlength{\textheight}{9in}
\pagestyle{empty}

\begin{document}

Let $x_1, x_2, \ldots, x_k$ be a sequence of $k$ distinct numbers.
Then any sequence of the form $x_{i_1}, x_{i_2}, \ldots, x_{i_h}$
where $1 \leq i_1 < i_2 < \ldots < i_h \leq k$ is said to be a
subsequence of the original sequence $x_1, x_2, \ldots, x_k$.  A
sequence $x_1, x_2, \ldots, x_k$ is said to be increasing if $x_1 <
x_2 < \ldots < x_k$.  Similarly a sequence is said to be decreasing if
$x_1 > x_2 > \ldots > x_k$.

\thm [Erdos-Szekeres 1935] Any sequence of $mn+1$ distinct 
numbers contains an increasing subsequence of length $m+1$ 
or a decreasing subsequence of length $n+1$.  \ethm

\pf Let the sequence be $x_1, x_2, \ldots, x_{mn+1}$. Define the
relation $\preceq$ on the elements of the set $\{x_1, x_2, \ldots,
x_{mn+1}\}$ as follows: $x_i \preceq x_j$ if $ i \leq j$ and $x_i \leq x_j$.
(Verify that $\preceq$ defines a partial order by showing that it is
reflexive, antisymmetric and transitive.) We now show that every
chain is an increasing subsequence and every antichain is a
decreasing subsequence.

\begin{claim}
  The elements of any chain (in $\preceq$) form an increasing subsequence.
% of  the sequence \\ $x_1, x_2, \ldots, x_{mn+1}$.
\end{claim}
\pf Let $\{x_{i_1}, x_{i_2}, \ldots, x_{i_k}\}$ be any chain. Let the
indices $i_1, i_2, \ldots, i_k$ be numbered so that $1 \leq i_1 < i_2
< \ldots < i_k$. We will now show that $x_{i_t} < x_{i_{t+1}}$ for all
$ 1 \leq t \leq k - 1$. Any two elements in a chain are related. But
it cannot be that $x_{i_{t+1}} \preceq x_{i_t}$ because $i_{t+1} >
i_t$. Therefore it must be that $x_{i_t} \preceq x_{i_{t+1}}$ and
$x_{i_t} < x_{i_{t+1}}$. This proves that $x_{i_1}, x_{i_2}, \ldots,
x_{i_k}$ is an increasing subsequence.
\end{proof}

\begin{claim}
  The elements of any antichain (in $\preceq$) form a decreasing subsequence.
% of the sequence $x_1, x_2, \ldots, x_{mn+1}$.
\end{claim}
\pf Let $\{x_{i_1}, x_{i_2}, \ldots, x_{i_k}\}$ be any antichain. Let
the indices $i_1, i_2, \ldots, i_k$ be numbered so that $1 \leq i_1 <
i_2 < \ldots < i_k$. We will now show that $x_{i_t} > x_{i_{t+1}}$ for
all $ 1 \leq t \leq k - 1$. Since any two elements in an antichain are
unrelated it must be the case that $x_{i_t} > x_{i_{t+1}}$ for
otherwise $x_{i_t} \preceq x_{i_{t+1}}$. This proves that $x_{i_1},
x_{i_2}, \ldots, x_{i_k}$ is a decreasing subsequence.
\end{proof}

Now, we invoke Corollary 5 of Lecture 5 Notes, which states that any
partially ordered set on $\geq nm+1$ elements has an antichain of size
$n+1$ or a chain of size $m+1$. But, by the two claims proved above
this is equivalent to saying that there is a decreasing subsequence of
size at least $n+1$ or an increasing subsequence of size at least
$m+1$.

\end{proof}
\end{document}




