\documentclass[12pt,twoside]{article}
\input{macros-course}

%% Latex asks whether or not to include solutions
\askaboutsolutions


\begin{document}

%% TUTORIAL 4: Partial Orders, DAGS, Graphs (Rad, Fall01)
\ifshowsolutions
  \tutsol{4}{September 27, 2001}{\stamp}
\else
  \tutprobn{4}{September 27, 2001}{\stamp}
\fi

\begin{problems}

%-------------------------------------------------------------
% source: spring00 ps3 
% topics: critical path, DAGs, topological sort

\problem A pair of 6.042 students, Eleni and Paris,
have decided to devote some of their spare time this term to
establishing dominion over the entire galaxy.  Recognizing this as an
ambitious project, they worked out the following table of tasks on the
back of Paris' copy of the notes for tutorial 3.

\begin{enumerate}
\item {\bf Devise a logo} and cool imperial theme music - 8 days.
\item {\bf Build a fleet} of Hyperwarp Stardestroyers out of eating
  paraphernalia swiped from Lobdell - 18 days.
\item {\bf Seize control} of the United Nations - 9 days, after task \#1.
\item {\bf Get shots} for Eleni's cat, Emilios - 11 days, after task \#1.
\item {\bf Open a Starbucks chain} for the army to get their caffeine - 10 
days, after task \#3
\item {\bf Train an army} of elite interstellar warriors by dragging
people to see {\em The Phantom Menace} dozens of times - 4 days, after
tasks \#3, \#4, and \#5.
\item {\bf Launch the fleet} of Stardestroyers, crush all sentient
alien species, and establish a Galactic Empire - 6 days, after tasks \#2 and
\#6.
\item {\bf Defeat Microsoft} - 8 days, after tasks \#2 and \#6.
\end{enumerate}

\problempart Express the information in the task list using some type
of graph (label the vertices to reflect task lengths).

\solution{%
    The information in the table is represented in the
    Figure~\ref{fig:tasks} in the form of a directed acyclic graph.
    Each vertex represents a task, and the weight of a vertex is the
    completion time.  Each directed edge represents a dependency
    between tasks.

    \begin{figure}[htbp]
    \begin{center}
    \unitlength=0.047pt
    \input{figures/ps4-1.latex}
    \end{center}
%      \centerline{\resizebox{!}{3.0in}{\includegraphics{figures/ps4-1.latex}}}
    \caption{Graph representing the task precedence constraints.}
    \label{fig:tasks}
    \end{figure}
}

\problempart Give some valid order in which the tasks might be
completed.

\solution{
We can easily find several of them. The most natural one is valid, too:
\#1, \#2, \#3, \#4, \#5, \#6, \#7, \#8.
}

\bigskip

Eleni and Paris want to complete all these tasks in the shortest
possible time.  However, they have agreed on some constraining work
rules.
\begin{itemize}

\item Only one person can be assigned to a particular task; they can
not work together on a single task.

\item Once a person is assigned to a task, that person must work
exclusively on the assignment until it is completed.  So, for example,
Eleni cannot work on building a fleet for a few days, run get shots
for Emilios, and then return to building the fleet.

\end{itemize}

For each task, the table above lists the time required for completion
and which other tasks must be finished before the given task is begun.

\problempart Eleni and Paris want to know how long conquering the
galaxy will take.  Paris suggests dividing the total number of days of
work by the number of workers, which is two.  What lower bound on the
time to conquer the galaxy does this give, and why might the actual
time required be greater?

\solution{
\begin{eqnarray*}
\frac{8 + 18 + 9 + 11 + 10 + 4 + 6 + 8}{2} & = & 37 \text{ days}
\end{eqnarray*}

If working together and interrupting work on a task were permitted,
then this answer would be correct.  However, the rules may prevent
Eleni and Paris from both working all the time.}

\problempart Eleni proposes a different method for determining the
duration of their project.  She suggests looking at the duration of
the ``critical path'', the most time-consuming sequence of tasks
such that each depends on the one before.  What lower bound does this
give, and why might it also be too low?

\solution{The longest sequence of tasks is devising a logo (8 days),
seizing the U. N. (9 days), opening a Starbucks (10 days), training
the army (4 days), and then defeating Microsoft (8 days).  Since these
tasks must be done sequentially, galactic conquest will require at
least 39 days.

If there were enough workers, this answer would be correct; however,
with only two workers, Eleni and Paris may be unable to make progress
on the critical path every day.}

\problempart What is the minimum number of days that Eleni and Paris
need to conquer the galaxy?  No proof is required.

\solution{
40 days.  Tasks could be divided as follows:

Paris: \#1 (days 1-8), \#3 (days 9-17), \#4 (days 18-28), \#8 (days 33-40).

Eleni: \#2 (days 1-18), \#5 (days 19-28), \#6 (days 29-32), \#7 (days 33-38).
}

%-----------------------------------------------------------------%
% source: not sure, also has been used for many terms as a tutorial problem
% topic: graphs, false proofs

\problem
Let $L_n$ be the $n+1$-vertex simple ``line'' graph consisting of a
single simple path of length~$n$.  For example, $L_4$ is shown in the
figure below:

\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}

\centerline{The line graph $L_4$}
\end{figure}

Let's say a simple graph has ``two ends'' if it has exactly two
vertices of degree~one, and all its other vertices have degree~two.
In particular, for $n \ge 1$, the graph~$L_n$ has two ends.

\problempart
Draw a diagram of the smallest simple graph with two ends which is not
isomorphic to any line graph.
%\hint See part (d).

%%  What is the smallest $n \ge 1$ such that there is an
%%  $n+1$-vertex simple graph with two ends which is \emph{not} isomorphic
%%  to~$L_n$? \hint See part (d).\brule{2em}

\solnospace{
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
The smallest two-ended graph not isomorphic to any line graph.
\end{center}}

\problempart
Explain briefly, but clearly, what is wrong with the following
argument:

\paragraph{False theorem:}
Every simple graph with two ends is isomorphic to~$L_n$ for some~$n~\ge~1$.

\paragraph{False proof:}
We prove by induction on the number, $n \ge 1$, of edges in a simple
graph, that every two-ended graph with $n$ edges is isomorphic
to~$L_n$.

(Base case $n = 1$): A simple graph with one edge can only consist of
the two vertices connected by that edge and some number of vertices
not attached to  any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge must consist solely of the two vertices
connected by the edge, which makes it isomorphic to~$L_1$.

(Induction case): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Now let $G_n$ be any two-ended
graph with $n \ge 1$ edges.  By hypothesis, $G_n$ is isomorphic
to~$L_n$.  Suppose an edge is added to~$G_n$ to form a two-ended
graph~$G_{n+1}$.

Since $G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  That is, the resulting $n+1$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.  Q.E.D.

\solnospace{
The inductive case is argued in an incorrect way.  The inductive case
must consist of a proof for any $n\ge{1}$ that if $G_{n+1}$ is
two-ended then $G_{n+1}\sim L_{n+1}$ ($A\sim{B}$ is a notation for ``$A$
is isomorphic to $B$''), using the assumption that for every two-ended
$G_n$, $G_n\sim{L_n}$ (alternatively, in strong induction, we can use
an assumption that for every $k$, $1\ge{k}\ge{n}$, if $G_k$ two-ended
then $G_k\sim{L_k}$).  

The false proof above does not argue that at all.  Instead, it states
that if one takes a two-ended $G_n$ which is isomorphic to $L_n$, and
extends it by an edge to form a two-ended $(n+1)$-edge graph $G'$,
then $G'\sim{L_{n+1}}$.  This is true, but to transform this argument
into an inductive proof, one would have to argue that every two-ended
$(n+1)$-edge graph $G_{n+1}$ can be formed in this way, i.e. by adding
another edge to some two-ended graph $G_n$.  However, this cannot be
argued because it is not true.  For example, in the solution to part
(a), we have a two-ended graph $G_4$ which cannot be formed by adding
an edge to some two-ended $G_3$.
}

\problempart
Here is another argument for the same False Theorem as in part~(b).
Explain exactly where it goes wrong.

\paragraph{False proof 2:}
Same induction hypothesis and base case as in part~(b).

(Induction case): For any $n\geq 1$, let $G_{n+1}$ be any two-ended graph
with $n+1$ edges.  Let $G_n$ be the graph which results from removing one
of the degree-one vertices~$v$ of~$G_{n+1}$ and the edge~$\{v,w\}$
attached to it.  So $G_n$ no longer has the vertex, $v$, of degree~one.
But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$, so
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.  Therefore $G_n$ is also two-ended.  By induction $G_n$
consists of a simple path of length~$n$.  But $G_{n+1}$ is obtained by
attaching an edge from one end of the path to a vertex~$v$ not on the
path, thereby lengthening the path by one.  So $G_{n+1}$ is isomorphic to
a simple path of length~$n+1$; that is, it is isomorphic to~$L_{n+1}$.
Q.E.D.

\solnospace{
The claim
\begin{quotation}\noindent
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.
\end{quotation}
is wrong.  The degree of $w$ is one less
in~$G_n$ than it was in~$G_{n+1}$, hence it can be equal to one if it
was two in $G_{n+1}$, but it can also be equal to zero if it was one
in $G_{n+1}$.  The false proof above is wrong because it ignores this
this second possibility.  For example, if we take $G_{n+1}=G_4$ from
the solution to part (a):\\
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(00,20){w}
\put(20,20){v}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
Graph $G_{n+1}$
\end{center}
We see that if you remove $v$ then $w$ will have degree zero in a
resulting graph $G_n$:
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}}
\put(00,20){w}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
Graph $G_{n}$
\end{center}
Obviously, $G_n$ is not two-ended.}


\problempart
Describe how to make a small revision to one of the false proofs above
so that it becomes a correct proof of the theorem ``Every
\emph{connected} simple graph with two ends is isomorphic to~$L_n$ for
some~$n \ge 1$.''

\solnospace{
The proof in part (c) can be easily fixed if the graphs are connected,
because then the quoted false claim will be true.  Here is an
example of how one could inject into the proof from part (c) an
argument justifying the claim for the case of connected
graphs:
\begin{quotation}
[...But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$.]
Since $G_{n+1}$ was two-ended, $w$ must be of degree either one or two
in $G_{n+1}$.  However, it cannot be of degree one because then
vertices $v$ and $w$ would be connected only to each other and
disconnected from the rest of the graph, which would contradict the
assumption that $G_{n+1}$ is connected.  Therefore, $w$ must have
degree two in $G_{n+1}$, and hence has degree one in $G_n$.
Hence, [ $G_n$ still has two vertices of degree~one and one fewer
vertex of degree~two.  Therefore...]
\end{quotation}

The false proof in part (b) cannot be easily fixed.  If we tried to
use its structure to prove that all connected two-ended graphs are
linear graphs, we would have to supply the argument that every
connected two-ended graph can be formed by adding an edge to some
connected two-ended graph with one less edge.  To argue that would be
as complicated as the above proof.
}

\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.

\bparts
\ppart  Verify that $a \preceq b$ is a partial order on the elements
of the sequence. 

\solnospace{
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.


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

\solnospace{
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.
}

\ppart Prove the Claim.

\solnospace{
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.}

\ppart 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}

\solnospace{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.}

\eparts


%-----------------------------------------------------------------%
% source: karger tutorial spring 01
% used previous as pset, but was too hard apparently (see comment)
% topic: Dilworths theorem

% old comment:
% this problem appeared in a problem set in fall 00
% very few people who didn't go to office hours got it right, even though
% it's not particularly difficult. Perhaps doing it in tutorial is a better idea

% \problem
% \textbf{REWRITE FOR CURRENT NUMBER OF STUDENTS!!!}
% At last count, our 6.042 class contains 180 students.
% Prove that the class must contain either: 

% \begin{enumerate} 
% \item A set $S$ of 15 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 13 students such that, if they line up in size
% places, they are also arranged in decreasing order of age.  
% \end{enumerate}

% To eliminate some confusion: the sequence $\{2, 2, 3, 4\}$ is in
% increasing order, but not in strictly increasing order.

% \solnospace{
% For each student, we can assign a pair $(s,a)$ where $s$ represents
% the size (height) of the student and $a$ represents the age of the
% student. We then get a set $U$ of 180 such pairs. We can define the
% following binary relation $R$, denoted by $\preceq$, between two pairs
% $P_{1}$ and $P_{2}$: $P_{1}\preceq P_{2}$ iff $s_{1}\leq s_{2}$ and
% $a_{1}\leq a_{2}$.

% For example, if $P_{1}=(180, 20)$, $P_{2} = (180, 21)$, $P_{3}= (185,
% 19)$, we have $P_{1}\preceq P_{2}$ but $P_{3}$ and $P_{1}$ are
% incomparable.

% It is easy to check that $R$ is reflexive, transitive and
% antisymmetric. Thus, it defines a partial order on the set $U$. By
% Dilworth's Theorem, since $U$ has 180 elements, it must either have a
% chain of size$>14$ or an antichain of size $\geq \frac{180}{14}$.

% \subparagraph{Case 1}
% $U$ has a chain of size $> 14$. Then it has a chain of size at least
% 15. This means that we can find 15 pairs which satisfy the relation
% $P_{1}\preceq P_{2}\preceq P_{3}\ldots \preceq P_{15}$. From the
% definition of our binary relation $(\preceq)$, this implies that
% $s_{1}\leq s_{2}\leq s_{3}\leq \ldots \leq s_{15}$ AND $a_{1} \leq
% a_{2} \leq a_{3}\leq\ldots\leq a_{15}$. Therefore, if we place the
% corresponding 15 students in the same order, they will be lined up in
% in increasing order of size AND in increasing order of age.

% \subparagraph{Case 2} 
% $U$ has an antichain of size $\geq\frac{180}{14}$, so, since
% antichains only come in integer lengths, it has an antichain of size
% at least 13. Therefore, we can find 13 pairs which are
% incomparable. We can line them up in order of increasing size
% (ignoring age), and come up with an order $P_{1}\ldots P_{13}$ so that
% $s_{i} \leq s_{i+1} (i= 1\ldots 12)$. Since for all $i$, $s_{i}\leq
% s_{i+1}$ and $P_{i}, P_{i+1}$ are incomparable, we can conclude that
% $a_{i}> a_{i+1}$ (because if not, $a_{i}\leq a_{i+1}$ so for that $i$,
% $s_{i}\leq s_{i+1},$ $a_{i}\leq a_{i+1}$, therefore $P_{i}\preceq
% P_{i+1}$, so $P_{i}$ and $P_{i+1}$ would NOT be incomparable.) If we
% take the students corresponding to $P_{1}\ldots P_{13}$ and line them
% up in that order, they will be in increasing order of size (since
% $s_{i}\leq s_{i+1}$) and in decreasing order of age (since we
% established that $a_{i}>a_{i+1}$).

% } % end solution

\end{problems}
\end{document}

