\documentstyle[quietpsfig]{article}

\setlength{\textwidth7in}
\setlength{\textheight10in}
\setlength{\oddsidemargin0in}
\setlength{\topmargin-0.3in}
\setlength{\unitlength}{1cm}

\begin{document}
\section{Posets: 10 points}
%Theory Ken Doll is trying to get dressed in the morning, and he realizes
%that the order in which he puts on clothes are subject to precedence
%constraints, just like in recitation! Please help our plastic friend
%rest easier by answering a few basic questions he has about posets. 

We learned in lecture that a poset can be thought of as a digraph where
every vertex corresponds to an element in the poset, and every edge
$(a,b)$ corresponds to the the precedence constraint $a \preceq
b$. Since the precedence relation is transitive, we leave out the edges
which can be inferred by transitivity and reflexivity. This digraph is
called the $Haase$ diagram for the poset.

Let $A, B$ be posets with associated ordering operation
$\preceq$. Define $A \oplus B$ to be the poset consisting of 
all the elements of $A$ and $B$, all the precedence constraints of $A$ and $B$,
as well as all the additional precedence constraints necessary to insure
that $\forall a \in A, b \in B, a \preceq b$, without changing the
precedence constraints within $A$ or $B$.

Recall that a minimal element of $X$ is an element $x_1 \in X$ such that
$\forall x_2 \in X, x_1 \ne x_2, x_1 \preceq x_2, $ or $x_1$ and $x_2$ are
incomparable. A maximal element of $X$ is an element $x_1 \in X$ such
that $\forall x_2 \in X, x_1 \ne x_2, x_2 \preceq x_1, $ or $x_1$ and $x_2$
are incomparable.\\

Figure 1: A = \{a,b,c\}, \{(a,c),(b,c)\} 
B = \{1,2,3,4\}, \{(1,3),(2,3),(1,4)\}
%include figure here
\begin{figure}[h]
\centerline{\psfig{file=fig1.ps,height=1in}} 
\caption{}
\end{figure}

Figure 2: A = \{a,b,c,d\}, \{(a,b),(a,c),(c,d)\} 
B = \{1,2,3,4\}, \{(1,4),(2,4),(3,4)\}
%include figure here
\begin{figure}[h]
\centerline{\psfig{file=fig2.ps,height=1in}} 
\caption{}
\end{figure}


\begin{itemize}
\item[a.] (1 point) Given the posets $A, B$ in figure 1, how many edges must be
added to form $A \oplus B$?

{\bf Soln.} We must add $(c,1), (c,2)$ for a total of 2 edges.

\item[b.] (1 point) Given the posets $A, B$ in figure 2, how many edges must be
added to form $A \oplus B$?

{\bf Soln.} We must add $(b,1), (b,2), (b,3), 
(d,1), (d,2), (d,3)$ for a total of 6 edges.

\item[c.] (3 points) If $x = |\{a : a \mbox{ is a minimal element of }
A\}|$ and $y = |\{b : b \mbox{ is a maximal element of } B\}|$, 
how many edges must be added to form $A \oplus B$ in terms of $|A|,
|B|, x, $ and $y$?

{\bf Soln.} $xy$

\item[d.] (5 points) Prove your answer from part (c).

{\bf Soln.} Let $E = \{(a,b) : a \mbox{ is a minimal element of } A \mbox{ and $b$
is a maximal element of $B$}\}$. Clearly $|E| = xy$. First note that $E$
satisifies the necessary constraints (i.e., it's big enough). Now we
prove that we need every single element of $E$.

Consider two elements $c$, $d$, where $c$ is a minimal element of $A$,
and $d$ is a minimal
element of $B$. Let $e$ be the edge between them in $E$. Can we take away $e$?
We could only if $c \preceq d$ was inferrable from other edges. (I.e., it
was a transitive consequence of other precedence constraints.) If we can
infer this from some other set of edges, that means we can find
precedence constraints
$(c,e)$ and $(e,d)$. Since $c$ is a minimal 
element of $A$, $e$ must be in $B$. However, since $d$ is a maximal element of
$B$, $e$ must be in $A$. Thus no such $e$ exists, and thus we need every edge
in $E$.

Thus exactly $xy$ additional edges are needed to form $A \oplus B$.
\end{itemize}

\end{document}
