        \problemdata       % Takes 5 *mandatory* arguments
        {posets-orderings}             % latex-friendly label for the prob.
        {relations}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut4-3} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
In the lecture notes (section on scheduling) we proved

\begin{theorem}\label{antichain-partition}
If $t$ is the size of the longest chain in a poset $(A, \preceq)$
then $A$ can be partitioned into $t$ antichains.
\end{theorem}

Review: {\bf chain}: all elements comparable (total order); {\bf
antichain}: all elements incomparable.

We can use this 
%along with Pigeonholing 
to prove a famous result about posets:

\begin{theorem}
(Dilworth) If $t$ is the size of the longest chain in a poset with $n$
elements, then the poset has an antichain of size $\geq n/t$.
\end{theorem}

\begin{proof}
By Theorem~\ref{antichain-partition}, the $n$ elements can be
partitioned into $t$ antichains.
%The pigeons are the $n$ elements.  The holes are the $t$ antichains.
%By Strong Pigeonholing, 
All the $t$ antichains can't be smaller than $n/t$ or the total number of
elements would be less than $t(n/t) = n$, so some antichain must have at
least $n/t$ elements.
\end{proof}

Posets arise in all sorts of contexts, and when they do Dilworth's
theorem can have interesting implications.  As you will show in this
problem.

\textbf{Claim}:
In any sequence of $n$ different numbers, there is either an increasing
subsequence of length $> \sqrt{n}$ or a decreasing subsequence of length
$\geq \sqrt{n}$.

For example
\[ 6 4 7 9 1 2 5 3 8\]
has the decreasing sequence
\[6 4 1\]
and the increasing sequence
\[1 2 3 8.\]
That is, it has ``long'' subsequences of both kinds.

Consider some sequence of $n$ distinct numbers.  To prove the
claim, say for numbers $a,b$ in the sequence, that $a \preceq b$ iff 
both $a \leq b$ and $b$ doesn't come before $a$ in the sequence.

\begin{problemparts}
\problempart  Verify that $a \preceq b$ is a partial order on the elements
of the sequence. 

\solution{
Let's use $a\textbf{ cb }b$ to denote that $a$ comes before $b$ in the
sequence. Then, $b$ doesn't come before $a$ iff $a\textbf{ cb }b\vee
a=b$. Let's denote this last fact as $a\textbf{ cb$_{=}$ }b$. It is
easy to check that \textbf{cb$_{=}$} is a total order. The same is
obviously true for $\leq$. The relation $\preceq$ is the intersection
of these orders. It's easy to verify that the intersection of two
partial orders is always a partial order, so $\preceq$ is a partial
order.  
}
%There are two total orders involved here: numerical $<$ and ``comes
%before'' in the sequence.  Let's abbreviate ``comes before'' as
%\textbf{ cb }.  The relation $\preceq$ is the intersection of these orders.
%It's easy to verify that the intersection of two partial orders is always
%a partial order, so $\preceq$ is a partial order.


\problempart What kind of subsequences are chains in this poset? \dots antichains?
Prove it.

\solution{
Increasing chains under $\preceq$ are the same as increasing subsequence,
because by definition, $a_1 \prec a_2 \prec \cdots \prec a_t$ iff both
\[a_1 < a_2 < \cdots < a_t,\]
and also
\[a_1 \mbox{\textbf{ cb }} a_2 \mbox{\textbf{ cb }} \cdots \mbox{\textbf{ cb }} a_t.\]

On the other hand, antichains are decreasing subsequences.  To prove this,
note:
\begin{lemma}\label{prec}
If $a,b$ are $\preceq$-incomparable and $a > b$, then $a
\mbox{\textbf{ cb }} b$.
\end{lemma}

\begin{proof}
If $b$ comes before $a$, then since $b < a$, we would also have $b \prec
a$, contradicting the assumption that $a$ and $b$ are incomparable.
\end{proof}

\begin{lemma}
If 
\[a_1 > a_2 > \dots > a_t,\]
and $a_1, a_2, \cdots, a_t$ are $\preceq$-incomparable,
then $a_1, a_2, \cdots a_t$ is a decreasing subsequence.
\end{lemma}

\begin{proof}
Since $a_i > a_{i+1}$, the next to last Lemma implies that $a_i$ comes
before $a_{i+1}$, that is, $a_1, a_2, \cdots a_t$ is a subsequence.
\end{proof}

So given an antichain, arrange the elements in decreasing order and this
will be a decreasing subsequence.
}

\problempart Prove the Claim.

\solution{
If there is no increasing subsequence of length $> \sqrt{n}$, then the
$\preceq$ partial order does not have a chain of length $> \sqrt{n}$.  By
Dilworth's Theorem, it must have an antichain of length at least
$n/\sqrt{n} = \sqrt{n}$.  But the elements of an antichain determine a
decreasing subsequence.}

\problempart Show that our 6.042 class of 100 students must contain either:

\begin{enumerate} 
\item 
a set $S$ of 10 students such that, if they line up in size
places, they are also arranged in increasing order of age, or

\item a set $T$ of 10 students such that, if they line up in size
places, they are also arranged in decreasing order of age.  
\end{enumerate}

\solution{Let $\preceq$ be ``is not younger than.''  The Claim implies
one or the other kind of sequence of length $\sqrt{100}$ will exist.}

%\emph{NOTE: Could change this to say that if we arranged the students
%alphabetically then it must contain either an increasing or decreasing
%height sequence of 10.}

\end{problemparts}


\end{problem}
