\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{5}{October 17, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let $P_n$ denote a directed path on $n$ vertices.  That is, it
is a graph consisting of vertices $v_1, v_2, \ldots, v_n$, and
directed edges $(v_1, v_2), (v_2, v_3), \ldots, (v_{n-1}, v_n)$.

\begin{theorem}
The Hasse diagram of a totally ordered set on $n$ vertices is
equal to $P_n$.
\end{theorem}
\begin{proof}
We prove this by induction on $n$.
Let $Q(n)$ denote the statement, 
``The Hasse diagram of a totally ordered set on $n$ vertices is
equal to $P_n$.''

Base Case: $n=1$.  Here the Hasse diagram is a single vertex with
no edges, which is precisely $P_1$.

Inductive Step.  We assume $Q(n)$, and show $Q(n+1)$.  Let $X$ be
a totally ordered set on $n+1$ elements.
We know that every poset contains a minimal element; let $x$ be
a minimal element of $X$.  Let $X' = X - \{x\}$.  

We claim that $X'$ is a totally ordered set on $n$ elements.  To
see this, note that $X'$ does have exactly $n$ elements, and any
two elements of $X'$ are comparable (since they are comparable in
the larger set $X$).  Thus, by the induction hypothesis, the
Hasse diagram of $X'$ is the graph $P_n$.

Since the Hasse digram of $X'$ is $P_n$, $X'$ contains a unique 
minimal element (the element corresponding to the vertex $v_1$).
Let $x'$ denote this element.  

To construct the Hasse diagram of $X$, we need to add to the Hasse
diagram for $X'$ a vertex representing $x$, with edges from $x$
representing all its comparability relations.  Observe that 
since $X$ is totally ordered, $x \preceq y$ for all $y \in X$.
Additionally, since $X'$ is totally ordered, $x' \preceq y'$ for
all $y' \in X'$.
Thus we need only introduce a single new edge, from the vertex
representing $x$ to the vertex representing $x'$.  All
the remaining comparability relationships involving $x$ will be
implied by transitivity.

So the Hasse digram for $X$ consists of a directed path on $n+1$
vertices, which is precisely $P_{n+1}$.  This completes the proof.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart
We prove this by contradiction.  Suppose that the set of tasks
can be completed in $T < D$ time units.  Let $C$ be a chain in
the poset of maximum length (i.e. $D$) ; then by the pigeonhole principle,
some two tasks in $C$ must be executed in the same time unit.
But since these two tasks are related in the poset, they must
be done in different time units --- a contradiction.

\ppart
We prove this too by contradiction.  Suppose that the set of tasks
can be completed in $T < N/P$ time units.  Then by the pigeonhole
principle, there is some time unit in which more than $P$ jobs
are being performed.  As we have only $P$ processors, we can apply
the pigeonhole principle again to conclude that in this particular
time unit, there is some processor that is performing more than
one task.  But this contradicts the assumption that each processor
can only perform one task per time unit.

\ppart
This part we prove by an actual construction of a schedule for
the processors.  Since the poset has maximum chain length $D$, we
know from class that 
it can be partitioned into antichains $A_1, A_2, \ldots, A_D$,
with the following property:
\begin{itemize}
\item[(*)]
For any $a_i \in A_i$: $b \preceq a_i$ implies 
$b \in A_1 \cup \cdots \cup A_{i-1}$.
\end{itemize}

Suppose that for $i = 1, \ldots, D$, $| A_i | = N_i$.  Our schedule
for the processors is as follows.
\begin{itemize}
\item For $i = 1, 2, \ldots, D$
\begin{itemize}
\item Perform the tasks in antichain $A_i$, $P$ tasks per time unit.
\end{itemize}
\end{itemize}

First we claim this a valid schedule.  This is by property (*) ---
by the time that a task $a$ is executed, all the tasks which $a$
depends on have been executed (in previous antichains).

Let's analyze how long this schedule takes.  To perform the tasks in antichain
$A_i$, since they can be done $P$ at a time, takes 
$\lceil N_i / P \rceil$ time units.  (The ``ceiling'' notation is because 
$N_i$ may not divide $P$ evenly.  So for example, if we have $N_i = 5$
and $P = 4$, it will take us $2$ time units to perform the tasks
in antichain $A_i$.)  Since 
$$\lceil N_i / P \rceil \leq 1 + N_i/P,$$
the total time to perform the tasks in $A_i$ is at most $1 + N_i/P$.

So the total time is at most
\begin{eqnarray*}
\sum_{i=1}^D (1 + N_i/P) & = & \sum_{i=1}^D 1 + (1/P) \sum_{i=1}^D N_i \\
& = & D + N/P
\end{eqnarray*}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart
By a circle, let's say that we mean the ``filled-in'' interior of 
a circle in the plane.

Let $S$ be an arbitrary set of $N$ circles in the plane, labeled
$C_1, \ldots, C_N$.  Put the following relation $\preceq$ on 
circles: we say that $C_i \preceq C_j$ if and only if $C_i$ is
contained in $C_j$.  (That is, if and only if $C_i \subset C_j$.)
We claim this is a partial order, which we
verify as follows.
\begin{itemize}
\item Reflexive: A circle is contained in itself, by the
reflexivity of the subset relation.
\item Anti-Symmetric: If $C_i$ is contained in $C_j$, and 
$C_j$ is contained in $C_i$, then $C_i = C_j$: this follows
from the definition of set equality.
\item Transitive: If $C_i$ is contained in $C_j$, and
$C_j$ is contained in $C_k$, then $C_i$ is contained in $C_k$: 
this follows from the transitivity of the subset relation.
\end{itemize}
Now, in this poset $(S,\preceq)$, a chain corresponds to a
set of circles so that for any pair of them, one is contained
in the other.  This is a {\em good} set.  An antichain corresponds
to a set of circles none of which is contained in any other.
This is a {\em bad set}.  Since any poset contains either a
chain or antichain of size at least $\sqrt{N}$, this proves
the theorem.

\ppart
Let $S$ be a set of $N$ natural numbers, labeled $x_1, \ldots, x_N$.
Put the following relation $\preceq$ on 
circles: we say that $x_i \preceq x_j$ if and only if $x_i | x_j$.
We claim this is a partial order, which we
verify as follows.
\begin{itemize}
\item Reflexive: Since $x_i = 1(x_i)$, $x_i | x_i$ and so
$x_i \preceq x_i$.
\item Anti-symmetric.  Suppose $x_i | x_j$ and $x_j | x_i$.
Then $x_j = a x_i$ and $x_i = b x_j$.  So $x_i = ab x_i$, which
implies that $ab=1$.  Since $a$ and $b$ are positive natural numbers,
this means that $a = b = 1$, and hence that $x_i = x_j$.
\item Transitive: Suppose $x_i | x_j$ and $x_j | x_k$.
So $x_j = a x_i$ and $x_k = b x_j$, so $x_i = ab x_k$, and
we have $x_i | x_k$.
\end{itemize}
Now, in this poset $(S,\preceq)$, a chain corresponds to a
set of numbers so that for any pair of them, one divides
the other.  This is a {\em good} set.  An antichain corresponds
to a set of numbers none of which divides any other.
This is a {\em bad set}.  Since any poset contains either a
chain or antichain of size at least $\sqrt{N}$, this proves
the theorem.

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart 
The graph has two connected components.

\begin{figure}[hb]
\begin{center}
\input{p4}
\end{center}
\end{figure}

\ppart
Nodes $1,2,4$ have degree $1$, nodes $5,6,7,8,9$ have degree $2$,
and node $3$ has degree $3$.

\ppart
\[ \left( \begin{array}{ccccccccc}
0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\
3 & 3 & 0 & 3 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 3 & 1 & 1 & 3 \\
0 & 0 & 0 & 0 & 3 & 0 & 3 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 3 & 0 & 3 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 & 3 & 0 & 3 \\
0 & 0 & 0 & 0 & 3 & 1 & 1 & 3 & 0
	\end{array} \right) \]

This matrix is the cube of the adjacency matrix.
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
By a {\em leaf} in a graph, we mean a vertex of degree $1$.
We first prove that every tree on at least $2$ nodes has a leaf.
(This was actually proved in recitation.)  
Let $T$ be a tree, and let $P$ be a path in $T$ (with no repeated
vertices) of maximum length.  Suppose that $P = \{v_1, v_2 \ldots, v_k\}$
in this order.  We claim that $v_1$ is a leaf.  For if not, then there
is an edge $(v,v_1)$ in $T$, where $v \neq v_2$.  Now if $v \not\in P$,
we can attach $v$ to the end of $P$ to obtain a longer path --- a 
contradiction.  But if $v \in P$, then since $v \neq v_2$, this will 
give a cycle in $T$ --- also a contradiction.

Given this fact, we prove the theorem by induction on $n$.

Base case: $n = 1$.  We can color the single node anything we want,
thereby using at most two colors.

Inductive step.  Suppose that we know that every tree on $n$ nodes
is bipartite, for some $n \geq 1$.  Let $T$ be a tree on $n+1$ nodes;
we need to show how to two-color it.  Since $n+1 \geq 2$, we know
that $T$ has a leaf $v$.  Let $w$ be the unique neighbor of $v$.
Let $T' = T - \{v\}$.  Note that $T'$
is a tree, since it is still connected and has no cycles.
Thus, by the induction hypothesis, we can two-color it.  

Now we define the following two-coloring of $T$.  If $u$ is a vertex
of $T$ not equal to $v$, give $u$ the color that it had in our 
two-coloring of $T'$.  Then give $v$ whichever color we didn't give
to its neighbor $w$.  As this is a valid two-coloring of $T$, this
completes the inductive step and the proof.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
The ``theorem'' is in fact incorrect; consider the graph we
used in question 4 as a counterexample.
This problem was supposed to show an example of the dangers of
``build-up'' error.

The base case is fine --- $P(2)$ really is true.

The trouble with the proof is our ``build-up'' step in the
induction, where we form an $(n+1)$-node graph by attaching 
a vertex to an $n$-node graph of minimum degree at least one.  This does
{\em not} produce all possible $(n+1)$-node graphs of minimum degree 
at least one,
and so the set of graphs for which we end up proving the theorem is
{\em not} the set of all graphs of minimum degree at least one.

For example, the following graph is not produced by this ``building-up''
process: vertices $A,B,C,D$, and two edges $(A,B)$ and $(C,D)$.
(To see this, ask yourself how you could get this from a $3$-node
graph of minimum degree one --- the answer is that you can't.)

\end{problems}

\end{document}





