\documentclass[12pt,twoside]{article}
\usepackage{graphics}
\input{macros-course}
\begin{document}

\newcommand{\solution}[1]{}
\pset{3}{September 22, 1998}{Start of class on September 29, 1988}

%\newcommand{\solution}[1]{#1}
%\psol{3}{September 22, 1998}

\begin{problems}

\problem {\bf (5 points)} Let $R$ be a binary relation on the set $\{ a, b, c, d, e \}$
defined as follows:

\begin{eqnarray*}
R & =  \{ & (a, a), (a, b), (a, d), (b, a), (b, b), (b, c), (b, d), \\
  & \mbox{} & (c, b), (c, c), (c, d), (d, b), (d, c), (d, d), (e, e) \quad \}
\end{eqnarray*}

Answer yes or no to each of the following questions; if you answer no,
then defend your answer.

\begin{problemparts}
\problempart Is $R$ reflexive?

\solution{
Yes.
}

\problempart Is $R$ symmetric?

\solution{
No. $R$ contains $(a, d)$, but
not $(d, a)$.
}

\problempart Is $R$ transitive?

\solution{
No. $R$ contains $(d, b)$ and $(b, a)$, but not $(d, a)$.  }

\end{problemparts}


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

\problem {\bf (10 points)} A relation $R$ on a set $A$ is {\em weakly
transitive} if for all $a, b, c, d \in A$, the relations $aRb$, $bRc$,
and $cRd$ imply the relation $aRd$.

Prove or disprove the following statements.

\begin{problemparts}

\problempart Every symmetric, weakly transitive relation is transitive.

\solution{
The claim is false.  The diagram below shows a counterexample.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-relation-cx.eps}}}
\end{figure}
}

\problempart Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

\solution{
\begin{proof}
The relation $R$ is an equivalence relation if it is reflexive,
symmetric, and transitive.  The first two properties hold by
assumption; all that remains is to show that $R$ is a transitive
relation.  Suppose that the relations $aRb$ and $bRc$ hold.  Because
$R$ is reflexive, the relation $aRa$ also holds.  Because $R$ is
weakly transtive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}
}

\end{problemparts}

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

\problem {\bf (10 points)} 
Let $G_n$ be a directed graph with vertices numbered $0, 1,
\ldots, n-1$.  There is a directed edge from vertex $i$ to vertex $j$
if and only if $j \equiv i^2 + i + 1 \pmod{n}$.  (See page 119 of
Rosen for a definition of $\equiv$ and $\pmod{n}$.  As a hint,
however, no number theory is required to solve this problem.)

\begin{problemparts}

\problempart Draw the directed graphs $G_1$, $G_2$, and $G_3$.

\solution{
\begin{figure}[h!]
\centerline{\resizebox{4.0in}{!}{\includegraphics{ps3-digraph.eps}}}
\end{figure}
}

\problempart Prove that if $n \geq 1$, then $G_n$ is not a directed
acyclic graph.

\solution{
\begin{proof}
Consider the following sequence of vertices in graph $G_n$.

\begin{eqnarray*}
v_1 & = & 0 \\
v_2 & = & v_1^2 + v_1 + 1 \pmod{n} \\
v_3 & = & v_2^2 + v_2 + 1 \pmod{n} \\
\ldots & & \ldots \\
v_{n+1} & = & v_n^2 + v_n + 1 \pmod{n}
\end{eqnarray*}

Note that there is a directed edge from $v_i$ to $v_{i+1}$ for all $1
\leq i \leq n$.  Not all of the vertices $v_1, \ldots, v_{n+1}$ can
be distinct, since the graph contains only $n$ vertices.  Suppose
$v_j$ is the first vertex in the sequence to appear a second time, and
$v_k$ was the initial appearance of that vertex.  Than the sequence of
vertices $v_k, v_{k+1}, \ldots, v_{j-1}$ forms a directed cycle.
Therefore, $G_n$ is not a directed acyclic graph.
\end{proof}
}

\end{problemparts}

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

\begin{figure}[t]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial.eps}}}
\end{figure}

\problem {\bf (20 points)} 
A {\em linear extension} of a poset is a
total order consistent with the partial order.  That is, if $x > y$ in
the partial order, then $x > y$ in the total order also.  For example,
in the poset defined by the Hasse diagram above, the following
relationships hold: $a > b$, $a > c$, $a > d$, $a > e$, $b > c$, and
$b > d$.

This poset has eight linear extensions, which are listed in the table below.  To
clarify the notation, the upper-left entry represents the total order
where $a$ is the largest element, $b$ the second largest, and so
forth.  Note that all of the relationships that hold in the poset also
hold for all the total orders listed below.

\[
\begin{array}{ccc}
a > b > c > d > e	& \quad \quad &		a > b > d > c > e \\
a > b > c > e > d	&	&		a > b > d > e > c \\
a > b > e > c > d	&	&		a > b > e > d > c \\
a > e > b > c > d	&	&		a > e > b > d > c
\end{array}
\]

\begin{problemparts}

\problempart List all the linear extensions of the poset represented by the
Hasse diagram below.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-partial2.eps}}}
\end{figure}

\solution{
\[
\begin{array}{ccc}
a > b > c > e > d	& \quad \quad &		a > c > b > e > d \\
a > b > c > d > e	&	&		a > c > b > d > e \\
a > b > d > c > e
\end{array}
\]
}

\problempart  After considering the above examples, Theory Pig formulated
the following claim.

\bigskip

{\bf Claim.} The number of linear extensions of a partially ordered
set with $n$ elements always divides $n!$.

\bigskip

Either prove that his claim is correct for all posets or else draw
the Hasse diagram of a counterexample and list all linear extensions.

\bigskip

\solution{
The claim is false.  The 4-element poset depicted below has 5 linear
extensions.  This is a counterexample, because 5 does not divide 4!.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-poset-cx.eps}}}
\end{figure}

\[
\begin{array}{ccc}
a > b > c > d	& \quad \quad &		a > b > d > c \\
b > a > c > d   &	&		b > a > d > c \\
b > d > a > c
\end{array}
\]
}

\end{problemparts}

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

\problem {\bf (15 points)} 
An {\em automorphism} of a graph is a relabeling of the
vertices that preserves adjacency.  For example, the graph on the left
side of the figure below has the automorphism $a \rightarrow b, b
\rightarrow a, c \rightarrow c, d \rightarrow d$.  (Here the
notation $x \rightarrow y$ means that the vertex labeled $x$ is
relabeled $y$.)  The relabeled graph is shown on the right side of the
figure.  This relabeling is an automorphism because adjacency is
preserved; that is, in the relabeled graph, just as in the original,
$a$ is adjacent to $b$ and $c$; $b$ is adjacent to $a$ and $c$; $c$ is
adjacent to $a$, $b$, and $d$; and $d$ is adjacent to $c$.  Every
graph has a {\em trivial automorphism} that assigns each node its
original label.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-auto.eps}}}
\end{figure}

\begin{problemparts}

\problempart List all non-trivial automorphisms of the graph below using the
$x \rightarrow y$ notation as in the example.

\begin{figure}[h!]
\centerline{\resizebox{!}{2.0in}{\includegraphics{ps3-findauto.eps}}}
\end{figure}

\solution{
\[
\begin{array}{c}
a \rightarrow e, b \rightarrow f, c \rightarrow c, d \rightarrow d,
e \rightarrow a, f \rightarrow b, g \rightarrow g, h \rightarrow h \\

a \rightarrow e, b \rightarrow f, c \rightarrow c, d \rightarrow d,
e \rightarrow a, f \rightarrow b, g \rightarrow h, h \rightarrow g \\

a \rightarrow a, b \rightarrow b, c \rightarrow c, d \rightarrow d,
e \rightarrow e, f \rightarrow f, g \rightarrow h, h \rightarrow g
\end{array}
\]
}

\problempart Draw a graph with at least 2 nodes that has only the trivial
automorphism.

\solution{
\begin{figure}[h!]
\centerline{\resizebox{!}{1.0in}{\includegraphics{ps3-noauto.eps}}}
\end{figure}
}

\end{problemparts}

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

\problem {\bf (15 points)} 
An $n$-node graph is said to be {\em tangled} if there is an edge
leaving every set of $\lceil\frac{n}{3}\rceil$ or fewer vertices.  As
a special case, the graph consisting of a single node is considered
tangled.  (Recall that the notation $\lceil x \rceil$ refers to the
smallest integer greater than or equal to $x$.)

\begin{problemparts}

\problempart Find the error in the proof of the following claim.

\bigskip

{\bf Claim.} Every non-empty, tangled graph is connected.

\bigskip

\begin{proof}
The proof is by strong induction on the number of vertices in the
graph.  Let $P(n)$ be the propostion that if an $n$-node graph is
tangled, then it is connected.  In the base case, $P(1)$ is true
because the graph consisting of a single node is defined to be tangled
and is trivially connected.

In the inductive step, for $n \geq 1$ assume $P(1), \ldots, P(n)$ to
prove $P(n+1)$.  That is, we want to prove that if an $(n+1)$-node
graph is tangled, then it is connected.  Let $G$ be a tangled,
$(n+1)$-node graph.  Arbitrarily partition $G$ into two pieces so that
the first piece contains exactly $\lceil\frac{n}{3}\rceil$ vertices,
and the second piece contains all remaining vertices.  Note that since
$n \geq 1$, the graph $G$ has a least two vertices, and so both pieces
contain at least one vertex.  By induction, each of these two pieces
is connected.  Since the graph $G$ is tangled, there is an edge
leaving the first piece, joining it to the second piece.  Therefore,
the entire graph is connected.  This shows that $P(1), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by strong induction.
\end{proof}

\solution{
The error is in the statement, ``By induction, each of these two
pieces is connected.''  This is not what the induction hypothesis
says; the induction hypothesis states that {\em if a graph is
tangled}, then it is connected.

In abstract terms, we are proving an induction hypothesis of the form
``if (this), then (that)''.  However, we erroneously use the induction
hypothesis as if it were simply of the form ``(that)'.
}

\problempart Draw a tangled graph that is not connected.

\solution{
\begin{figure}[h!]
\centerline{\resizebox{!}{1in}{\includegraphics{ps3-tangled-cx.eps}}}
\end{figure}
}

\problempart An $n$-node graph is said to be {\em mangled} if there is an edge
leaving every set of $\lceil\frac{n}{2}\rceil$ or fewer vertices.
Again, as a special case, the graph consisting of a single node is
considered mangled.  Prove the following claim.

\bigskip

{\bf Claim.} Every non-empty, mangled graph is connected.

\solution{
\begin{proof}
The proof is by contradiction.  Assume for the purpose of
contradiction that these exists an $n$-node graph that is mangled, but
not connected.  Then the graph must have at least two connected
components.  However, there can be at most one connected component
with more than $\lceil\frac{n}{2}\rceil$ vertices, since the graph has
only $n$ vertices in total.  Therefore, there exists a connected
component with $\lceil\frac{n}{2}\rceil$ or fewer vertices.  Since the
graph is mangled, there is an edge leaving this component.  But this
contradicts the definition of a connected component.
\end{proof}
}

\end{problemparts}

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

\problem {\bf (15 points)} 
Let $G$ and $H$ be undirected graphs with no self-loops.  The {\em
product graph} $P = G \times H$ is defined as follows.  The vertex set
of $P$ is the cartesian product of the vertex set of $G$ and the
vertex set of $H$.  Thus, each vertex of $P$ is an ordered pair $(v,
w)$ where $v$ is a vertex of $G$ and $w$ is a vertex of $H$.  The
edges in the product graph $P$ are of two types.  First, for every
edge $(v_1, v_2)$ in $G$ and vertex $w$ in $H$, there is an edge
between $(v_1, w)$ and $(v_2, w)$ in $P$.  Second, for every vertex
$v$ in $G$ and edge $(w_1, w_2)$ in $H$, there is an edge between $(v,
w_1)$ and $(v, w_2)$ in $P$.  Note that these two sets of edges are
disjoint.

\begin{problemparts}

\problempart Draw the product of the two graphs shown below.  
Your diagram must be tidy to receive full credit.  In particular,
label all the vertices, e.g. $(b, 3)$, and use two different colors or
line styles (e.g. dashed and solid) to distinguish the two types of
edge defined above.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1in}{\includegraphics{ps3-twographs.eps}}}
\end{figure}

\solution{
\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{ps3-product.eps}}}
\end{figure}
}

\problempart Let $G$ be the graph consisting of two vertices connected
by an edge.  Let $G^n$ be the product of $n$ copies of $G$.  Use
induction to prove that $G^n$ has $2^n$ vertices and $n 2^{n-1}$
edges.  (You may assume without proof that the $\times$ operation is
associative.)

\solution{
\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
$G^n$ has $2^n$ vertices and $n 2^{n-1}$ edges.  In the base case,
$P(1)$ is true because $G^1$ has $2^1 = 2$ vertices and $1 \cdot
2^{1-1} = 1$ edge.

In the inductive step, for $n \geq 1$ assume that $G^n$ has $2^n$
vertices and $n 2^{n-1}$ edges to prove that $G^{n+1}$ has $2^{n+1}$
vertices and $(n+1) 2^n$ edges.  The remainder of the argument uses
the fact that $G^{n+1} = G^n \times G$.

The vertex set of $G^{n+1}$ is the cartesian product of the vertex set
of $G^n$ and the vertex set of $G$.  There are $2^n$ vertices in $G^n$
by induction, and there are 2 vertices in $G$ by the definition of the
graph.  Therefore, there are $2^n \cdot 2 = 2^{n+1}$ vertices in
$G^{n+1}$.

The edges of $G^n \times G$ are of two types.  First, for each edge
$(v_1, v_2)$ in $G^n$ and vertex $w$ in $G$, there is an edge between
$(v_1, w)$ and $(v_2, w)$ in $G^{n+1}$.  Thus, the number of edges of
the first type is equal to the number of edges in $G^n$ multiplied by
the number of vertices in $G$, which gives $n 2^{n-1} \cdot 2 = n
2^n$.

Second, for each vertex $v$ in $G^n$ and edge $(w_1, w_2)$ in $G$,
there is an edge between $(v, w_1)$ and $(v, w_2)$ in $G^{n+1}$.
Thus, the number of edges of the second type is equal to the number of
vertices in $G^n$ multiplied by the number of edges in $G$, which
gives $2^n \cdot 1= 2^n$.  Since these two sets of edges are disjoint,
the total number of edges in $G^{n+1}$ is equal to $n 2^n + 2^n =
(n+1) 2^n$.

This shows that $P(n)$ implies $P(n+1)$, and the claim is proved by
induction.
\end{proof}
}

\end{problemparts}

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

\problem {\bf (10 points)} 
John Dunagan, one of the 6.042 TAs, gave our friend Theory Pig a new
toy for his birthday.  The toy consists of a $3 \times 3$ grid of
squares, where each square contains one of the letters in THEORY PIG.
Each row can be rotated right or left and each column can be rotated
up or down.  The effects of such rotations are explained in the figure
below.

\[
\begin{array}{|c|c|c|}
\hline
H & E & Y \\ \hline
P & I & G \\ \hline
R & O & T \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
R & E & Y \\ \hline
H & I & G \\ \hline
P & O & T \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
R & E & Y \\ \hline
I & G & H \\ \hline
P & O & T \\ \hline
\end{array}
\]

The first picture shows Theory Pig's new toy configured as he first
received it.  The leftmost column is then rotated downward to give the
middle picture.  The $H$ and $P$ move down, and the $R$ rotates back
up to the top.  Then the middle row is rotated leftward to produce the
final picture.  The $I$ and $G$ move left, and the $H$ rotates back
around to the right.

Naturally, Theory Pig wants to arrange the letters so as to spell his
name.

\[
\begin{array}{|c|c|c|}
\hline
T & H & E \\ \hline
O & R & Y \\ \hline
P & I & G \\ \hline
\end{array}
\]

Based on prior experience, Theory Pig is afraid that the toy might be
specially designed to make this delightful combination utterly
impossible, no matter what sequence of row and column rotations he
attempts.

\begin{problemparts}

\problempart Model Theory Pig's toy as a state machine.

\solution{
\begin{itemize}

\item The set of states $Q$ consists of all arrangements of the letters in
THEORY PIG on a $3 \times 3$ grid.

\item The set of start states $Q_0$ consists of the single arrangement HEY PIG,
ROT!

\item The set $\delta \subseteq Q \times Q$ consists of all pairs of states
$(q_1, q_2)$ such that $q_2$ can be obtained from $q_1$ by a row or
column rotation.

\end{itemize}
}

\problempart Given the initial configuration of the toy indicated above,
prove that Theory Pig can never spell his name.

\solution{
\begin{proof}
The proof uses the Invariant Theorem.  We prove the following
invariant: the number of inversions in the letter sequence relative to
HEY PIG, ROT is always even.

The invariant holds in the single start state, because the number of
inversions is initially 0, which is even.

The invariant is maintained for each transition $q_1 \rightarrow q_2
\in \delta$.  In general, swapping two elements of a permutation alters
the number of inversions by an odd amount.  Thus, in particular,
swapping any two letters in the toy alters the number of inversions by
an odd amount.  However, a row or column rotation can be accomplished
with two swaps, which changes the number of inversions by an $ODD +
ODD = EVEN$ amount.  Therefore, if the number of inversions in $q_1$
is even, then the number of inversions in $q_2$ is even.

Thus the invariant is established by the Invariant Theorem.

Note, however, that THEORY PIG has an odd number of inversions
relative to HEY PIG, ROT.  Therefore, the state THEORY PIG is
unreachable.
\end{proof}
}
\end{problemparts}
\end{problems}
\end{document}
