\documentclass[12pt]{article}
\usepackage{../light}

\hidesolutions
%\showsolutions

\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

\begin{document}

\recitation{7}{October 1, 2004}

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

\section*{The Chemist and The Maltster}

\begin{problem}

At Guiness brewery in the early 1900's, W. S. Gosset (a chemist) and
E. S. Beaven (a ``maltster'') were working to improve barley.  Gosset
and Beavan planned to grow several varieties of barley in a field and
compare the yields.  However, local variations in the fertility of the
field might skew the results.  Their solution was to divide the field
into many small plots and grow each crop in several different places.

Similar thinking led to the use of {\em Latin squares} in experiment
design.  A Latin square is an $n \times n$ array of numbers such that
each row and each column contains every number from $1$ to $n$.  For
example, here is a $4 \times 4$ Latin square:

{\Large
\[
\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\ \hline
3 & 4 & 2 & 1 \\ \hline
2 & 1 & 4 & 3 \\ \hline
4 & 3 & 1 & 2 \\ \hline
\end{array}
\]
}

You can imagine that this array is an agricultural field where each
square is a small plot, and the number inside indicates the variety of
barley planted there.

There are some nice connections between Latin squares and graph
theory.  For example, see if you can construct a graph $G_n$ such that
there is a one-to-one correspondence between $n \times n$ Latin
squares and valid $n$-colorings of $G_n$.

\solution{Create a vertex in $G$ for each entry in the Latin Square.
Then connect each vertex to every other vertex in the same row and to
every other vertex in the same column.  Now color the graph with $n$
colors, each corresponding to a number between 1 and $n$.

Notice that every pair of vertices in the same row are connected, so
no two vertices in the same row can get the same color.  Similarly,
since every pair of vertices in the same column are connected, no two
vertices in the same column can get same color either.  These coloring
constraint match the constraints on Latin squares, so there is a
one-to-one correspondence between colorings of $G$ and $n \times n$
Latin squares.}

\end{problem}

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

\instatements{\newpage}

\section*{The Chemist and The Maltster}

\begin{problem}
The next question about Latin squares will require a corollary of
Hall's Theorem.  A bipartite graph is {\em regular} if every vertex on
the left has degree $c$ and every vertex on the right has degree $d$.
Prove the following:

\begin{corollary*}
A regular bipartite graph has a matching for the vertices on the left
if $c \geq d > 0$.
\end{corollary*}

For your reference, here is the statement of Hall's Theorem.

\begin{theorem}[Hall's Theorem]
Let $G = (L \cup R, E)$ be a bipartite graph such that every edge has
one endpoint in $L$ and one endpoint in $R$.  There is a matching for
the $L$ vertices if $\size{N(S)} \geq \size{S}$ for every set $S
\subseteq L$.
\end{theorem}

If $S$ is a set of vertices, then $N(S)$ is the set of neighboring
vertices; that is, the all vertices that are adjacent to a vertex in
$S$, but not actually in $S$.  And example is shown in the figure
below.

\mfigure{!}{2in}{rec7-matching}

A \term{matching} for the $L$ vertices is a subset of the edges such
that exactly one edge is incident to each vertex in $L$ and at most
one edge is incident to each vertex in $R$.  The edges shown in bold
in the example above form such a matching.

\solution{We use Hall's Theorem.  Let $L$ denote the set of vertices
on the left and $R$ denote the set of vertices on the right.  We must
show that every set of vertices $L' \subseteq L$ on the left is
adjacent to a set of vertices $R' \subseteq R$ such that $\size{L'}
\leq \size{R'}$.  If this condition holds, then Hall's theorem implies
that a matching for the vertices on the left exists.

Let $L' \subseteq L$ be a subset of vertices on the left, and let $R'
\subseteq R$ be the set of all vertices on the right adjacent to some
vertex in $L$.  Thus, every edge incident to a vertex in $L'$ is also
incident to a vertex in $R'$.  Therefore, the sum of the degrees of
the vertices in $L'$ is at most the sum of the degrees of vertices in
$R'$.  Thus, we have:

\begin{eqnarray*}
c \cdot \size{L'} & \leq & d \cdot \size{R'}
\end{eqnarray*}

Since $c \geq d > 0$ by assumption, this implies $\size{L'} \leq
\size{R'}$.  Thus, the desired condition holds.}
\end{problem}

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

\instatements{\newpage}

\section*{Completing Latin Squares}

\begin{problem}
Now we return to Quadra\footnote{Get it?  That's Latin for
``squares''.  Latin -- squares?  HAHAHA! Haha...  Heh.  Okay, just
shut up do the problem.}.

\bparts

\ppart Suppose your teammate wrote only three lines of a $5 \times 5$
Latin square before deciding to chuck it all and become a maltster:

{\Large
\[
\begin{array}{|c|c|c|c|c|}
\hline
2 & 4 & 5 & 3 & 1 \\ \hline
4 & 1 & 3 & 2 & 5 \\ \hline
3 & 2 & 1 & 5 & 4 \\ \hline
  &   &   &   &   \\ \hline
  &   &   &   &   \\ \hline
\end{array}
\]
}

Can you fill in the last two lines to extend this ``Latin rectangle''
to a complete Latin square?

\solution{
Here is one possible solution:

{\Large
\[
\begin{array}{|c|c|c|c|c|}
\hline
2 & 4 & 5 & 3 & 1 \\ \hline
4 & 1 & 3 & 2 & 5 \\ \hline
3 & 2 & 1 & 5 & 4 \\ \hline
1 & 5 & 2 & 4 & 3 \\ \hline
5 & 3 & 4 & 1 & 2 \\ \hline
\end{array}
\]
}
}

\ppart Show that filling in the next row of a Latin rectangle is
equivalent to finding a matching in some bipartite graph.

\solution[\vspace{2in}]{Construct a bipartite graph as follows.  The
vertices on the left are the columns of the Latin rectangle, and the
vertices on the right are the numbers $1$ to $n$.  Put an edge between
a column and a number if the number has {\em not yet appeared} in the
column.  Thus, a matching in this graph would associate each column
with a distinct number that has not yet appeared in that column.
These numbers would form the next row of the Latin rectangle.}

\ppart Prove that a matching must exist in this bipartite graph and,
consequenctly, a Latin rectangle can always be extended to a Latin
square.

\solution{First, we show that the bipartite graph described above has
a matching.  Each column-vertex on the left has degree $n - k$ and
each number-vertex on the right has degree $n - k$ as well.
Therefore, a matching for the columns exists by the corollary in the
preceding problem.  This implies that we can add rows to the Latin
rectangle by the procedure described above as long as $k < n$.  At
that point, we have a Latin square.}

\eparts

\end{problem}

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

\end{document}
