\documentclass[11pt,twoside]{article}
\usepackage{graphics}
\usepackage{macros-course-lectures}

\newcommand{\power}{\mathcal{P}}              % The power set
\newcommand{\R}{\mathop{\mbox{$R$}}\nolimits} % Is related to

\begin{document}

\onlystudents

\lecture{notes6}{Partitions and Partial Orders}{February 27, 2000}

\section{Equivalence relations and partitions}

Now we consider an important special type of relation, called an
\emph{equivalence relation}\.  We give an important special
case---modular arithmetic\.  We show an application to RSA.

\subsection{Definitions}

\begin{definition}
  An \emph{equivalence relation} is a relation that is reflexive,
  symmetric and transitive.
\end{definition}
For example, the ``roommates'' relation is an equivalence relation.
So is ``same size as'', and ``on same Ethernet hub''\.
A trivial example is ``='' relation on natural numbers\. 
The hallmark of equivalence relations is the word ``same''\.  It
provides a way to ``hide'' unimportant differences\.
Equivalence relations partition the universe into subsets in a natural
way:
\begin{definition}
  A \emph{partition} of a set $A$ is a collection of subsets
  $\{A_1,\ldots,A_k\}$ such that any two of them are disjoint (for any
  $i\neq j$, $A_i\cap A_j=\emptyset$) and such
  that their union is $A$.
\end{definition}
That is, every element of $A$ is in exactly one subset\.
Now fix an equivalence relation $R$ on $A$\.
For an element $a\in A$, let $[a]$ denote the set $\{b\in A \given
a\sim_R b\}$\.
We call this set the \emph{equivalence class of $a$ under $R$}\.
We call $a$ a \emph{representative} of $[a]$.
\begin{lemma}
  \label{lem:partition}
  The sets $[a]$ for $a\in A$ constitute a partition of $A$.  That is,
  for every $a,b\in A$, either $[a]=[b]$ or $[a]\cap [b]=\emptyset$.
\end{lemma}
\begin{proof}
  Consider some arbitrary $a,b\in A$\. If either $[a]=[b]$ or $[a]
  \cap [b]=\emptyset$ then we are done, so suppose not\.  Let $c$ be
  any element that is in one of the sets but not the other\.  Without
  loss of generality we can assume that $c \in [b]-[a]$.  (We know
  that either $c \in [b]-[a]$ or $c \in [a]-[b]$. In the latter case
  we can simply swap $a$ and $b$ and reduce to the first case.)  Let
  $d$~be any element in $d \in [a] \cap [b]$\.  We will get a
  contradiction by showing that $a\sim_R c$ and therefore that $c\in
  [a]$\. First, $a\sim_R d$ because $d\in [a]$ (note that $d=a$ is a
  possibility but this is ok because $R$ is reflexive)\.  Second,
  $d\sim_R b$ and $b\sim_R c$ because both $c,d\in [b]$ and $R$ is
  symmetric\.  This implies, by transitivity, that $d\sim_Rc$\.
  Finally, by transitivity, $a\sim_R c$ because $a\sim_R d$ and
  $d\sim_R c$.
\end{proof}
Note that all three properties of equivalence relations were used in
this proof\. Checking that the proof uses all available assumptions if
usually a good sanity check when writing proofs---if one of the
properties you assumed were not needed, you have either made a mistake
or proven a much more strong theorem than you thought---\eg, if you
didn't use transitivity anywhere in the proof of
Lemma~\ref{lem:partition}, you would be proving that any reflexive
symmetric relation produces a partition, which is false.
\begin{lemma}
  Any partition $\{A_1,\ldots,A_k\}$ of~$A$ defines an equivalence
  relation by letting $a \sim_R b$ iff $a$ and $b$ are in the same
  $A_i$.
\end{lemma}
\begin{proof}
  Reflexivity: for all $a$ we know $a\in A_i$ for some $i$, by
  definition of partition. Clearly $a$ and $a$ are in the same $A_i$,
  \ie, $a\sim_R a$.

  Symmetry: Assume $a\sim_R b$, that is $a$ and~$b$ are in the 
  same $A_i$. Also $b$ and~$a$ are in the same~$A_i$
  and therefore $b\sim_R a$.

  Transitivity: Assume $a\sim_R b$ and $b\sim_R c$.
  By definition of $\sim_R$, $a$ and $b$ are in the same 
  $A_i$ for some $i$, and $b$ and $c$ are in the same $A_j$
  for some $j$.
  But by definition of partition $b$ cannot be in two different $A_i$'s.
  So, it must be $A_i=A_j$ and $a$ and $c$ are in the same 
  $A_i$, proving $a\sim_R c$.
\end{proof}
Therefore, we can look at partitions and at equivalence relations as
the same thing. 



\subsection{Integers modulo $m$}

Now we discuss an important equivalence relation on integers
(positive, negative and $0$): 
\begin{definition}
  If $a$ and $b$ are integers, then we say that $a \equiv b \pmod
  m$---which is pronounced ``$a$~is equivalent to~$b$
  modulo~$m$''---if $m \divides (a-b)$.
\end{definition}
An equivalent formulation says that $a=b+km$ for some integer $k$.  
\begin{theorem}
  Equality modulo $m$ is an equivalence relation.
\end{theorem}
\begin{proof}
  We need to show that the relation is reflexive, symmetric, and
  transitive.

  Reflexive: Clearly $m \divides (a-a) = 0$, so $a \equiv a \pmod m$.

  Symmetric: If $a=b+km$ then $b=a+(-k)m$.
  
  Transitive: Suppose $a \equiv b \pmod m$ and $b \equiv c \pmod m$\.
  Then $m \divides (a-b)$ and $m \divides (b-c)$\.  So $(a-b)=k_1 m$
  and $(b-c)=k_2 m$\.  So $(a-c)=(a-b)+(b-c)=(k_1+k_2)m$\.  Therefore
  $m \divides (a-c)$.
\end{proof}
The equivalence class of $a$ is simply the set $[a] = \{ b \in
\integers \divides a \equiv b \pmod m \}$, or $\{ km + a \divides k
\in \integers\}$.

It turns out that we can extend a lot of standard arithmetic to work
modulo $m$\.
In fact, we can define notions of sum and product for the equivalence
classes mod $m$\.
For example, we define $[a]+[b]$, given two equivalence classes mod
$m$, to be the equivalence class $[a+b]$\.
This is not as obvious as it seems: notice
that the result is given in terms of $a$ and $b$, two selected
representatives from the equivalence classes, but that it is supposed
to apply to the equivalence classes themselves\.
To prove that this works, we have to show that it doesn't matter which
representatives of the equivalence classes we choose:
\begin{lemma}
  If $a \equiv x \pmod m$ and $b \equiv y \pmod m$ then $(a+b) \equiv
  (x+y) \pmod m$.
\end{lemma}
\begin{proof}
  $m \divides (a-x)$ and $m \divides (b-y)$ so $m \divides ((a-x)+(b-y)) =
  (a+b)-(x+y)$,  
\end{proof}
It follows that if we are interested only the result of the addition
modulo $m$---which is the case, for example, in the RSA
cryptosystem---then we can at any time replace a given number with a
different number equivalent to it, without changing the value
(equivalence class) of the final answer.

The same fact can be proven for multiplication\.
This is the basis of the fast exponentiation algorithm presented in
the next subsection.



\subsection{Fast Exponentiation}

Recall that for RSA we wanted to compute the remainder of $x^a$\ on
division by $b$---that is, the equivalence class $\bmod~b$ of $x^a$.

In the section on recursive algorithms, we already saw how to reduce
the number of multiplications substantially\.  But there is still a
problem: $x^a$ is a really big number\.  It is bigger than $2^a$, so
has $2^{2^{128}}$ bits if we use a 128-bit key $a$\.  It will take a
long time to write this number down (if we could find a place to fit
it)\.  

But notice that we only care about the remainder modulo $b$.  So using
modular arithmetic we can solve the large-number problem\.  Whenever
the number we are computing gets too big, replace it with a smaller
representative of the same equivalence class\.  What is the smallest
representative?  The remainder on division by $b$\.  We've argued that
switching representatives doesn't change the answer\.  But now all our
math is done on number smaller than $b$, \ie, 128-bit numbers.



\section{Partial Orders}

Partial orders are a particular type of binary relation that is 
important in computer science\.
They have applications to task scheduling,
database concurrency control,
and logical time in distributed computing,



\subsection{Definitions}

\subsubsection{Partial Order Definition}

\begin{definition} 
  A binary relation $\R \subseteq A \times A$ is a
  \emph{partial order} if it is reflexive, transitive, and
  antisymmetric.
\end{definition}
Quick review:
\begin{itemize}
\item reflexive: $a \R a$
\item transitive: $a \R b \wedge b \R c \Rightarrow a \R c$
\item symmetric: $a \R b \Rightarrow b \R a$
\item antisymmetric: $a \R b \wedge b \R a \Rightarrow a=b$.  \ie,
  $\forall a \neq b, a \R b \Rightarrow \neg b \R a$. Means
  \emph{never} symmetric!
\end{itemize}
For comparison:
Recall that a relation that is reflexive, transitive, and symmetric
is an equivalence relation.

The reflexivity, antisymmetry and transitivity properties are abstract
properties that generally describe ``ordering'' relationships.

So we often write an ordering-style symbol like $\preceq$, instead of
just a letter like~$R$, for a partial order relation.  This lets us use
notation similar to $\le$.  For example, we write $a \prec b$ if
$a \preceq b$ and $a \ne b$.  Similarly, we write $b \succeq a$ as
equivalent to $a \preceq b$.

But this could be misleading, note that $\geq$ is a partial order
on natural numbers, as well as $\leq$\.
If we use the $\preceq$ symbol for $\geq$,
things look really funny.\ 
In cases like this it is better to use $R$\.

A partial order is always defined on some set $A$.  The set together
with the partial order is called a ``poset'':
\begin{definition}
  A set $A$ together with a partial order $\preceq$ is called a 
  \emph{poset}  $(A, \preceq)$.
\end{definition}
\begin{example}
  Consider the following relations:
  \begin{itemize}
  \item $A=\naturals, R=\leq$, easy to check reflexive, transitive,
    antisymmetric
  \item $A=\naturals, R=\geq$, same.
  \item $A=\naturals, R=<$, \emph{not} because not reflexive
  \item $A=\naturals, R=|$ (divides), easy to check reflexive,
    transitive, antisymmetric
  \item $A=\power(\naturals), R=\subseteq$, check reflexive: $S
    \subseteq S$, transitive: $S \subseteq S' \wedge S' \subseteq S''
    \Rightarrow S \subseteq S''$, antisymmetric: $S \subseteq S'
    \wedge S' \subseteq S \Rightarrow S = S'$.
  \item $A=$ ``set of all computers in the world'', $R=$ ``is
    (directly or indirectly) connected to''.  \emph{not} a partial
    order because it is not true that $a \R b \wedge b \R a
    \Rightarrow a=b$.  In fact, it is symmetric and transitive.
    Equivalence relation.
  \item $A=$ ``set of all propositions'', $R=\Rightarrow$, {\bf not} because
    it's not antisymmetric. Not symmetric either, so not equivalence
    relation.
  \end{itemize}
\end{example}



\subsubsection{Directed Acyclic Graphs}

A common source of partial orders in computer science is in ``task
graphs''\.  You have a set of tasks $A$, and a relation $R$ in which
$aRb$ means ``$b$ cannot be done until $a$ is finished''\.
Implicitly, ``if all the things that point at $b$ are done, I can do
$b$.''
This can be nicely drawn as a graph\.  We draw an arrow from $a$ to
$b$ if $a \R b$\.
\begin{samepage}
  For example, below is a graphs that describes the order in which one
  would put on clothes\. The set is of clothes, and the edges say what
  should be put on before what.
  \begin{center}\includegraphics{figures/clothes.mps}\end{center}
\end{samepage}
The ``depends on'' graph imposes an ordering on tasks.  But is it a
partial order\?  No, because it isn't reflexive or transitive\.  But
there is a natural extension: the reflexive transitive closure
\emph{is} a partial order\.  It gives the relation ``must be done
before.''

Wait, we know the reflexive transitive closure is reflexive and
transitive, but is it antisymmetric\?
What if I add a relation edge from belt to underwear\?  In that case my
dependency graph stops making sense: there is no way to get dressed!
What goes wrong?  A cyclic dependency.
\begin{definition}
  A \emph{cycle} is a path that ends where it started (\ie, the last
  vertex equals the first).
\end{definition}
\begin{definition}
  A \emph{directed acyclic graph (DAG)} is a directed graph with no
  cycles.
\end{definition}
\begin{lemma}
  Any partial order is a DAG.
\end{lemma}
\begin{proof}
  Suppose the graph representation of a partial order~$\preceq$ has a
  cycle $a_1,\ldots,a_k,a_1$\. Then by transitivity of~$\preceq$
  (with an induction hiding inside) we have $a_1 \preceq a_k$. We
  also have $a_k \preceq a_1$. This violates the antisymmetry of
  $\preceq$, a contradiction.
\end{proof}
We saw above that the reverse of the above lemma doesn't hold, since
there are DAGs that are not partial orders. However, every DAG can be
extended to a partial order.
\begin{lemma}
  The transitive reflexive closure of a DAG is a partial order.
\end{lemma}
\begin{proof}
  Let the DAG be~$R$ and its transitive reflexive closure~$S$\.
  $S$~is transitive and reflexive; we just need to prove that it is
  antisymmetric\. We do so by contradiction. Suppose that there exists
  some $a,b$ such that $a \neq b$, $a \sim_S b$, and $b \sim_S a$\. In
  other words, there is a path from $a$ to~$b$ and a path from $b$
  to~$a$ in~$R$\. If we attach these two paths, we get a path from $a$
  to $a$ in~$R$, \ie, $R$~contains a cycle\. This contradicts the
  assumption that $R$~is acyclic.
\end{proof}



\subsubsection{Hasse Diagrams}

If we draw the graph of a poset, we may get \emph{lots} of edges
(consider the $\le$ order on some natural numbers)\.  But a lot of
those edges are ``implicit'' from the transitivity of the order\.  
We can get a much less messy picture by leaving out these arrows.

Consider the clothing example\.  Under the transitive closure,
underwear precedes belt\.  But we don't need to see that edge to know
it is there\.
Similarly loops (which express reflexive relationships) aren't shown.
\begin{definition}
  A \emph{Hasse diagram} for a poset $(A,\preceq)$ is a graph: \\
  -- whose vertices are the elements of $A$, \\
  -- whose edges (arrows) represent pairs $(a,b)$, where $a \prec b$, \\
  -- if $ a \prec b$, the $a$~vertex is below the $b$~vertex, \\
  -- that contains no ``transitive edges'', \\
  -- for which all pairs in $\preceq$ are obtainable by transitivity from
  edges in the diagram.
\end{definition}
It's a ``transitive disclosure'' of the poset\.
To convert the diagram above to an ``official form'' Hasse diagram,
we must remove the pants $\rightarrow$ jacket arrow:
\begin{center}\includegraphics{figures/clotheshasse.mps}\end{center}
\begin{samepage}
  The divisibility relation over $\{1,2,\ldots,12\}$, represented by
  the digraph
  \begin{center}\includegraphics{figures/divide12.mps}\end{center}  
\end{samepage}
\begin{samepage}
  has the following Hasse diagram:
  \begin{center}\includegraphics{figures/divide12hasse.mps}\end{center}
\end{samepage}



\subsubsection{Partial vs. Total Orders}

A partial order is called \emph{partial} because it is not necessary
that an ordering exist between every pair of elements in the set.
\begin{example}
  Lshoe and Rshoe have no prescribed ordering between them.
\end{example}
\begin{example}
  For two sets, it's not necessary that either be a subset of the
  other.
\end{example}
When there is no prescribed order between two elements we say that they
are ``incomparable''. 
\begin{definition}
  We say that $a$ and~$b$ are \emph{incomparable} if neither $a
  \preceq b$ nor $b \preceq a$, and that they are \emph{comparable} if
  $a \preceq b$ or $b \preceq a$.
\end{definition}
\begin{example}
  For subsets of $\naturals$, $\{ 1,2,3 \}$ and $\{ 2,3,4 \}$ are
  incomparable.
\end{example}
However, a partial order need not have incomparable elements\.  As a
special case, we can have a partial order in which there is a
specified order between every pair of elements\.
\begin{definition}
  A poset $(S, \preceq)$ is \emph{totally ordered} if $(\forall a,b
  \in S) [ a \preceq b \vee b \preceq a ]$.
\end{definition}
The Hasse diagram of a total order looks like a line.

\forlecture{%
Examples:
\begin{itemize}
\item $S=\naturals, \preceq = \leq$,
\item $S=\naturals, \preceq = \divides$, NOT because neither
  $3\divides5$ nor $5\divides3$
\item $S=P(\naturals), \preceq = \subseteq$, NOT because neither $\{3\}
  \subseteq \{5\}$ nor $\{5\} \subseteq \{3\}$ 
\item Lexicographic order on pairs of natural numbers, defined by:
  $(a_1,a_2) \preceq (b_1,b_2)$ if and only if either $a_1 < b_1$,
  or else $a_1 = b_1$ and $a_2 \leq b_2$. \\
  \forlecture{Do some examples here. $(2,37) \preceq (2,38) \preceq
    (3,2)$\.}  ``Lexicographic'' because like dictionary.
\end{itemize}

This has been the basic material. \\
Book has a bit more: \\
lower bounds, upper bounds (for a subset---$\leq$ everything in the
subset, or $\geq$) \\
lub, glb, \\
lattices. \\
Read these parts. 
}



\subsection{Topological Sorting}

Sometimes when we have a partial order, \eg, of tasks to be
performed, we want to obtain a consistent total order\.  That is, an
order in which to perform all the tasks, one at a time, so as not to
conflict with the precedence requirements. 

The task of finding an ordering that is consistent with a partial
order is known as \emph{topological sorting}---probably because the
sort is based only on the shape, \ie, topology, of the poset, and not
on the actual values.
\begin{definition}
  A \emph{topological sort} of a finite poset $(A, \preceq)$ is a
  total ordering of all the elements of $A$, $a_1, a_2, \cdots, a_n$
  in such a way that for all $i < j$, either $a_i \preceq a_j$ or
  $a_i$ and~$a_j$ are incomparable.
\end{definition}
For example, underwear, shirt, Lsock, Rsock, pants, sweater, Lshoe, Rshoe,
belt, jacket is a topological sort of how to dress\.
One of the nice facts about posets is that such an ordering always
exists and is even easy to find:
\begin{theorem}
  \label{thm:topological}Every finite poset has a topological sort.
\end{theorem}
The basic idea to prove this theorem is to pick off a ``first''
element and then proceed inductively.
\begin{definition}
  A \emph{minimal} element $a$ in a poset $(A, \preceq)$ is one for
  which $(\forall b \in A) [a \preceq b \lor \mbox{$a$ and $b$ are
    incomparable}]$.  Equivalently, it is an element~$a$ for which
  $(\nexists b \in A) [b \prec a]$.
\end{definition}
\begin{lemma}
  Every finite poset $(A,\preceq)$ has a minimal element.
\end{lemma}
\begin{proof}
  For every element $a \in A$, let $p_a = \{b \in A \given b \prec
  a\}$, \ie, $p_a$~is the set of predecessors of~$a$ according to the
  partial order\. It is enough to show that there exists an $a \in A$
  such that $p_a = \emptyset$; to accomplish this, we use
  well-ordering.
  
  Let $P = \{p_a \given a \in A\}$\. Now let $a'$~be an element
  corresponding to a set $p_{a'}$~of minimum cardinality\. We now that
  such an~$a'$ exists by applying the well-ordering principle to the
  subset $\{|p| : p \in P\}$ of~$\naturals$\. There can be several sets
  in~$P$ of minimum cardinality, but that doesn't matter---we pick
  $p_{a'}$~to be one of the sets\. We now prove by contradiction that
  $p_{a'} = \emptyset$.
  
  Suppose that $|p_{a'}| > 0$, \ie, that $p_{a'} \neq \emptyset$\.
  Then there exists some $b' \in A$~such that $b' \prec a'$\. Consider
  the set~$p_{b'}$\. We now claim that $p_{b'} \subset p_{a'}$\. Since
  $c \in p_{b'}$ implies that $c \prec b'$, we obtain, by
  transitivity, that $c \in p_{b'}$ implies that $c \prec a'$, \ie,
  every element in~$p_{b'}$ is also an element of~$p_{a'}$, or,
  equivalently, $p_{b'} \subseteq p_{a'}$\. Furthermore, $b' \in
  p_{a'}$ since $b' \prec a'$, but $b' \notin p_{b'}$ since $b' \nprec
  b'$. Thus $p_{b'} \subset p_{a'}$\. But this contradicts our
  assumption that $p_{a'}$ is a set of minimum cardinality. Thus,
  $p_{a'} = \emptyset$.
\end{proof}
If you don't like well-ordering, there is a proof by induction in
Velleman (\S~6.2). For comparison, we also show you a third proof
below:
\begin{proof}
  Suppose no element of~$A$ is minimal\. So every element has
  one preceding it\.  We derive a contradiction\.  Take some element $a
  \in A$ and define the following sequence recursively.  $a_0=a$, and
  for $i > 0$, $a_i$ is some element that precedes~$a_{i-1}$\.

  This definition is a bit odd because it is nondeterministic\. But it
  doesn't matter which preceding element you pick at each step\.  The
  key is that it defines some $a_i$ for every $i$\.
  
  Now note that the sequence $a_{n+1},\ldots,a_0$ is a walk of length
  $n+1$\.  This means some element is repeated: $a_i=a_j$ for some $i
  < j$\.  But this means $a_i,\ldots,a_j$ is a cycle, which is
  impossible in a poset\.  So we have a contradiction.
\end{proof}
\begin{remark}
  Notice that there can be more than one minimal element. There are
  four in the clothes example: Lsock, Rsock, underwear, and shirt.
\end{remark}
\begin{remark}
  An infinite poset might have no minimal element. Consider~$\integers$.
\end{remark}
Now we can prove the existence of the topological sort.
\begin{proof}[Proof of Theorem~\ref{thm:topological}]
  Let $P(n)$ be ``any poset with $n$ elements has a topological
  sort''\.  Base case: for a poset with one element the one element
  makes a topological sort\.

  Inductive step: Assume $P(n)$. Consider a poset of $n+1$ elements\.
  By the previous lemma it has a minimal element $u$\. 
  Consider the same relation on $A-\{u\}$\. 
  It is easy to check that it is still reflexive, transitive, and
  anti-symmetric\.
  So by the inductive hypothesis, $A-\{u\}$ has a topological sort\. 
  We put $u$ first and now have a topological sort on the whole thing\.
  (According to the definition of topological sort, $u$~can't be in
  the wrong order w.r.t. any of the later elements.)

  Thus every finite poset has a topological sort, by induction.
\end{proof}
\begin{example}
  Consider the dressing example\.  Construct an ordering by picking
  one item at a time\.  At each step, look at the poset formed by the
  remaining elements\.  Lsock, shirt, sweater, Rsock, underwear,
  pants, Lshoe, belt, jacket, Rshoe
\end{example}
\begin{example}
  Subsets of $\{ 1,2,3,4 \}$:

  $\emptyset$ is the unique minimal element, then we have choices, \eg, do: \\
  $\{ 1 \}$, $\{ 2 \}$, $\{ 1,2 \}$,
  $\{ 3 \}$, $\{ 1,3 \}$, $\{ 2,3 \}$, $\{ 1,2,3 \}$, \\
  $\{ 4 \}$, $\{ 1,4 \}$, $\{ 2,4 \}$, $\{ 3,4 \}$, 
  $\{ 1,2,4 \}$, $\{ 1,3,4 \}$, $\{ 2,3,4 \}$, $\{ 1,2,3,4 \}$
\end{example}

\forlecture{%
  Infinite posets also always have topological sorts, but the
  proof of that fact is hard, at least according to Velleman.}



\subsection{Parallel Task Scheduling}

When elements of a poset are tasks that need to be done and the
partial order is precedence constraints, topological sorting provides
us with a legal way to execute tasks sequentially, \ie, without
violating any precedence constraints\.  But what if we have the
ability to execute more than one task at the same time\?  For example,
say tasks are programs, partial order indicates data dependence, and
we have a parallel machine with lots of processors instead of a
sequential machine with only one\.  How should we schedule the tasks\?
Our goal should be to minimize the total \emph{time} to complete all
the tasks\.  (For simplicity, let's say all the tasks take the same
amount of time and all the processors are identical.)

So, given a finite poset of tasks, how long does it take to do them
all, in an optimal parallel schedule\?  We can use partial order
concepts to analyze this problem\.

On the clothes example, we could do all the minimal elements first
(Lsock, Rsock, underwear, shirt), remove them and repeat\.  (We'd need lots
of hands, or maybe dressing servants)\. We can do pants and sweater
next, and then Lshoe, Rshoe, and belt, and finally jacket\. 

We can't do any better, because the sequence shirt, pants, belt, jacket
must be done in that order\. 
A sequence like this is called a chain.
\begin{definition}
  A \emph{chain} in a poset is a sequence of elements of the domain,
  each of which is smaller than the next in the partial order
  ($\preceq$ and $\neq$). The \emph{length} of a chain is the number
  of elements in the chain.
\end{definition}
Note that a chain is just a path in the corresponding graph\.

Clearly, the parallel time is at least length of any chain\.  For if
we used less time, then two tasks in the chain would have to be done
at the same time\.  (This is ``obvious,'' but is formalized as an
application of the ``pigeonhole principle'' we will study shortly.) 
But by definition of chains this violates
precedence constraints\.  A longest chain is also known as a
\emph{critical path}\.  So we need at least $t$~steps, where $t$~is
the length of the longest chain\.  Fortunately, it is always possible
to use only~$t$:
\begin{theorem}
  \label{thm:parallel}
  Given any finite poset $(A, \preceq)$ for which the longest chain
  has length~$t$, it is possible to partition~$A$ into $t$~subsets,
  $A_1, A_2, \cdots, A_t$ such that 
  \begin{displaymath}
    (\forall i \in \{1,2,\ldots,t\})
    (\forall a \in A_i) 
    (\forall b \prec a) 
    \bigl[b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} \bigr].
  \end{displaymath}
\end{theorem}
That is, we can divide up the tasks into $t$~groups so that for each
group~$A_i$, all tasks that have to precede tasks in~$A_i$ are in
smaller-numbered groups.
\begin{corollary}
  For $(A, \preceq)$ and $t$~as above, it is possible to schedule all
  tasks in $t$~steps.
\end{corollary}
\begin{proof}
  For all~$i$, schedule all elements of~$A_i$ at time~$i$\. 
  This satisfies the precedence requirements, because all tasks that
  must precede a task are scheduled at preceding times. 
\end{proof}
\begin{center}\includegraphics{figures/clothesparallel.mps}\end{center}
\begin{corollary}
  parallel time = length of longest chain
\end{corollary}
So it remains to prove the partition theorem:
\begin{proof}[Proof of Theorem~\ref{thm:parallel}]
  Construct the sets~$A_i$ as follows:
  \begin{displaymath}
    A_i = \{a \in A \given \mbox{longest chain ending in~$a$ has length~$i$}\}.
  \end{displaymath}
  This gives just $t$~sets, because the longest chain has length~$t$\.
  Also, each $a \in A$ belongs to exactly one~$A_i$\.
  To complete the proof, we also need to show
  \begin{displaymath}
    (\forall i \in \{1,2,\ldots,t\})
    (\forall a \in A_i) 
    (\forall b \prec a) 
    \bigl[b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} \bigr].
  \end{displaymath}
  The proof is by contradiction\. Assume that $a \in A_i$ and that
  there exists a $b \notin A_1 \cup A_2 \cup \cdots \cup A_{i-1}$ such
  that $b \prec a$\. Then there is a chain of length exceeding $i-1$ ending
  in~$b$\. This means, since $b \prec a$, that there is a chain of
  length $>i$ ending in~$a$, which means that $a \notin A_i$.
\end{proof}
So with an unlimited number of processors, the time to complete all
the tasks is the length of the longest chain\.
It turns out that this theorem is good for more than parallel
scheduling. It is usually stated as follows.
\begin{definition}
  An \emph{antichain} is a set of incomparable elements.
\end{definition}
\begin{corollary}
  \label{cor:parallel}
  If $t$~is the length of the longest chain in a poset $(A, \preceq)$
  then $A$~can be partitioned into $t$~antichains.
\end{corollary}
\begin{proof}
  Let the antichains be the sets~$A_i$ defined as in the proof of
  Theorem~\ref{thm:parallel}. We now claim that the elements in those
  sets are incomparable. Suppose that there exists $a,b \in A_i$ such
  that $a \neq b$ and $a$ and~$b$ are comparable. Then either $a \prec
  b$ or $b \prec a$, which---again by the proof of
  Theorem~\ref{thm:parallel}---contradicts the assumption that $a$
  and~$b$ are in the same~$A_i$.
\end{proof}
\forlecture{%
  Review:
  \begin{itemize}
  \item \emph{chain}: all elements comparable (total order)
  \item \emph{antichain}: all elements incomparable
  \end{itemize}}



\subsubsection{Dilworth's Theorem}

We can use the above corollary to prove a famous result about posets:
\begin{theorem}[Dilworth]
  \label{thm:Dilworth}
  For all~$t$, every poset with $n$~elements must have either a chain
  of size greater than~$t$ or an antichain of size at least $n / t$.
\end{theorem}
\begin{proof}
  Assume there is no chain of length greater than~$t$\.
  So, longest chain has length at most~$t$\.
  Then by Corollary~\ref{cor:parallel}, the $n$~elements can be
  partitioned into at most~$t$ antichains\.
  Let $\ell$~be the size of the largest antichain\.
  Since there are at most~$t$ antichains, every antichain contains
  at most $\ell$~elements, and an element belongs
  to exactly one antichain, $\ell t \geq n$\.
  So there is an antichain with at least $n / t$ elements.
\end{proof}
\begin{corollary}
  \label{cor:Dilworth}
  Every poset with $n$ elements has a chain of length greater
  than~$\sqrt{n}$ or an antichain of size at least~$\sqrt{n}$.
\end{corollary}
\begin{proof}
  Set $t = \sqrt{n}$ in Theorem~\ref{thm:Dilworth}.
\end{proof}
\begin{example}
  In the dressing poset, $n = 10$\.
  Try $t = 3$.  Has a chain of length~$4$\.
  Try $t = 4$.  Has no chain of length~$5$, but has an antichain of size 
  $4 \geq 10 / 4$.
\end{example}
Posets arise in all sorts of contexts, and when they do, Dilworth's
theorem can have interesting implications.



\subsubsection{Increasing and Decreasing Sequences}

\begin{theorem}
  In any sequence of $n$~different numbers, there is either an
  increasing subsequence of length greater than~$\sqrt{n}$ or a
  decreasing subsequence of length at least~$\sqrt{n}$.
\end{theorem}
\begin{example}
  $\langle6,4,7,9,1,2,5,3,8\rangle$ has the decreasing sequence
  $\langle6,4,1\rangle$ and the increasing sequence
  $\langle1,2,3,8\rangle$.  
\end{example}
We can prove this using Dilworth's theorem; the trick is to define the 
appropriate poset\.
The domain is the set of values in the sequence\.
For the ordering, define $a \preceq b$ if either $a = b$, or else
($a < b$ and $a$ comes before $b$ in the sequence)\.
You should check that his is reflexive (stated explicitly), 
transitive, and antisymmetric\.
A chain corresponds to a sequence that increases in value and moves to
the right, that is, an increasing sequence\.
But what does an antichain correspond to?
\begin{lemma}
  If $a$ and $b$ are incomparable (under the partial order) and $a > b$ (as
  numbers) then $a$ precedes~$b$ in the 
  sequence.
\end{lemma}
\begin{proof}
  By contradiction\.
  Assume $b$ precedes~$a$ in the sequence\.
  Then $b < a$ and $b$ precedes~$a$ in the sequence, so $b \preceq a$
  in the partial order\.
  This contradicts our assumption that $a$ and~$b$ are incomparable.
\end{proof}
We extend this lemma to more than 2 elements:
\begin{lemma}
  If $a_1, a_2, \cdots , a_t$ are incomparable and $a_1 > a_2 > \cdots
  > a_t$ then $a_1, a_2, \cdots a_t$ form a decreasing subsequence.
\end{lemma}
\begin{proof}
  For all~$i$, the fact that $a_i > a_{i+1}$ implies that $a_i$
  precedes $a_{i+1}$ in the sequence, by the previous lemma.
\end{proof}
So given an antichain, arrange the elements so that they are in
decreasing order and the ``left of'' relation follows, giving a
decreasing subsequence\.
Dilworth's theorem implies that there is either a chain of size 
greater than~$\sqrt{n}$ or an antichain of size at most~$\sqrt{n}$\.
By the analysis above, this yields either an increasing sequence of
length greater than~$\sqrt{n}$
or a decreasing subsequence of length at most~$\sqrt{n}$. 


\end{document}

\endinput



\subsubsection{Number of Comparisons for Database Setup and Searching}

Consider a database of records with (distinct) numerical keys\.
Suppose when records are inserted, some comparisons of these keys
occur, and the database maintains a record of these comparisons\.
\begin{example}
  At one extreme, database could be kept totally sorted\.
  The other extreme, totally unsorted.  
\end{example}
Each comparison costs something---the time to perform it\.
Now suppose that after this setup, a search is to be performed on the
database to determine if a record with a particular key~$k$ appears
anywhere in the database\.
The search is supposed to be based on comparisons only\.
Then the worst-case number of comparisons it takes depends on the
database partial order.
\begin{example}
  If the database is totally sorted, we can compare with middle
  elements, then middle of halves, etc\.
  Binary search\.
  Approximately $\log n$ comparisons needed.  
\end{example}
\begin{example}
  If database totally unsorted, then in the worst case, have to compare
  with every element\.
  This is because each comparison with an element in the database gives no
  information about whether the sought element might be any of the
  others in the database\.
\end{example}
In fact, if there is an antichain of size~$k$, then in the worst case,
the new key could be any of the elements of the antichain\.
So in the worst case, have to compare with all~$k$, since each one
gives no information about the others.

See what Dilworth's theorem says about the database partial order.
For any~$t$, either have a chain of length $> t$, or an antichain of
size $\geq \frac{n}{t}$\.
Setting up a chain of length $> t$ requires at least $t$~comparisons\.
The antichain requires at least $\frac{n}{t}$ comparisons\.
So this says that we have to pay the cost sometime,
either we do $> t$ comparisons while setting up the database, or at
least $\frac{n}{t}$ in the worst case to search the database.

More refined analysis is possible\.
That's because reliably setting up a long chain, say length~$t$, in
the database actually requires \emph{more} than $t$~comparisons\.
Because in the worst case, the comparisons won't come out in the most
desirable way, setting up a linear chain.
\begin{example}
  Compare $a$ and~$b$, find out $a > b$\.  Then compare $b$ and~$c$\.
  Would be nice if we found out $b > c$\.  But we might not---might get
  $c > b$\.  Then we don't have a chain of length~$3$, but still an
  antichain of size~$2$\.  To get a chain, need an additional
  comparison.
\end{example}



\subsection{Logical Time in Distributed Systems}

One last use of partially ordered sets\.
No use of powerful theorems here---just showing an important place
where a poset is used as a mathematical model for a real computational
situation\.

A distributed computation consists of a sequence of ``steps''
occurring at each of a collection of ``processes''\.
In addition to performing local steps, the processes can send messages
to each other\.
So, have send steps and receive steps\.

The processes are mostly working independently\.
The only interaction is by means of the messages\.
So, the only dependence among steps (feeding data from one to another,
using results to make decisions, etc.) is by:
\begin{enumerate}
\item Successive steps of same process.
\item Send vs. receive of same message.
\end{enumerate}
Taking reflexive transitive closure leads to partial order describing
the dependence among the computation steps.

Basic theorem: Any topological sort of this partial order 
describes a possible
sequence in which all the distributed steps could occur\.
(No changes in what happens based on reordering incomparable steps.)

Example of what one might do with this partial order:
Assign ``logical time'' to every step\.
Instead of an actual real time\.
The time is just any assignment of real numbers to the steps that is
consistent with the partial order:  when one step precedes another in
the partial order,
it must have a smaller logical time\.

Behaves like real time:  Formally, can reorder the steps in logical
time order, still consistent with the partial order\.
Then the system is behaving as if the logical time were actually real
time\.
Can be maintained by simple distributed algorithm\.
(Piggybacks time on message, adjusts local times in response to what
is heard in some messages.)
Although logical time isn't the same as actual real time, for many
purposes, it can be used as an adequate substitute\.
Logical time can be used, \eg, to timestamp files to keep updated
copies consistent.

This notion of logical time was invented by Lamport.
In 2000, the original (late 1970s) paper containing this idea won an
award for the most influential paper ever, in distributed computing
theory.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


Problems based on this lecture:

1. (Some basic p.o. defs -- minimal and maximal elements, lower and
upper bounds, etc.)
Section 6.6, Problem 20
and/or Section 6.2, Problem 22

2. (Parallel task scheduling)
Recall the theorem from class that says that if a task graph is 
a partial order with maximum chain length $t$, then the
whole set of tasks can be performed by an unlimited collection of
parallel processors in time $t$.
This theorem was only for the case where all tasks take the same
amount of time, say $1$ time unit.
(a) Apply this theorem to produce an optimal schedule for the
following task graph.
[[[give some graph.  Don't need to make up a cute story -- just some
letters will do]]]
(b) Generalize the theorem to the case where some tasks take $1$ time
unit and others take $2$ times units.
[[[Seems this should work by splitting the time-$2$ tasks into two
tasks, using this to come up with a new length measure for chains,
then applying the old theorem. 
Should take some arguing that everything works, but it seems nice.???]]]

3. This doesn't actually use Dilworth's theorem.
But the students will get to think about chains and antichains.

Suppose a database is stored using a partial order on keys.  
Your job is to design a search strategy to determine if a new key $k$
appears in the database.  
The only thing you are allowed to do in the strategy is to compare two
keys (either two within the database, or the new key $k$ vs. a key in
the database).
The result of such a comparison adds extra edges to the partial order.
The results of earlier comparisons can be used to determine which
comparisons are made later.

For each of the partial orders given below, describe a strategy for
searching for an arbitrary key $k$ in the database.
Your strategy should be designed to use the minimum number you can
achieve, of comparisons, in the worst case.
Say how many comparisons it takes in the worst case, and explain why.

(a) Consists of $2$ antichains $A$ and $B$, each with $5$ elements. 
Each of the $5$ elements of $A$ is known to be less than each of the
$5$ elements of $B$.
[[[Can draw diagram]]]

[[[I get 10 comparisons.  Can achieve by direct comparison of new key
with each element.  Doesn't seem we can better than, though -- every
key needs to be compared to $k$ directly or indirectly.  If we assume
$k$ is between all the elements of $A$ and all the elements of $B$,
then it seems we get no help from the existing edges.  Re-think this
-- if it looks too hard, we could default to the simpler case where we
are only allowed to compare $k$ to an element of the database.]]]

(b) Consists of $2$ chains, each of length $5$.  No relationships are
known between elements of the $2$ chains, however.
[[[Can draw diagram]]]

[[[Here I get $6$, by treating the two chains separately.]]]
\end{document}

