\magnification=\magstep1
\overfullrule=0pt
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Extra Credit Problem Set}
\centerline{April 15, 2005}
\bigskip
\noindent
I.  Here is an application of Hall's Theorem related to Question I
on Problem Set 8.  A {\it doubly stochastic}
matrix $M$ is an $n\times n$ real matrix with nonnegative entries and
row and column sums equal to 1.  For instance, the matrix on the left
is doubly stochastic:
$$\pmatrix{ .5 & .5 & 0 \cr
           .5 & 0 & .5\cr
           0 & .5 & .5\cr} = (.5)T_{12} + (.5)T_{23}$$
In the sum on the right, $T_{12}$ and $T_{23}$ are the $3\times 3$ permutation matrices 
from question I.  In general we will call a linear combination $\sum_i c_i P_i$ of 
permutation matrices a {\it convex combination} if the $c_i \ge 0$ for all $i$, 
and $\sum_i c_i = 1$.  Prove that every doubly stochastic matrix is a convex
combination of permutation matrices.  (Hints: you can structure the proof by
induction on the number of nonzero entries.  Problem 27 from Chapter 9 in the
text is also connected to this!)  

\bigskip
\noindent
II.  In this problem we will see another proof of:

\proclaim Cayley's Tree Theorem.  There are $n^{n-2}$ different
labeled trees with vertex set $\{1,2,\ldots, n\}$.  \par

\noindent
We can study structures similar to 
our graphs, but where each edge {\it has a specified
direction\/}.  We might call these {\it directed graphs\/}, 
or {\it digraphs\/} for short.
Pictorially, we could draw an arrowhead on each 
edge of an ordinary graph to indicate the direction of the edge.
\bigskip
\item{A)}  Consider any function 
$$f : \{2,3,4,\ldots,n-1\} \to \{1,2,3,\ldots,n\}$$
We can construct a digraph $(V,E_f)$ representing the function by 
taking the vertex set to be $V = \{1,2,3,\ldots,n\}$  and
the edge set $E_f$ to consist of the collection of directed 
edges from $i$ to $f(i)$ for each $i \in \{2,3,4,\ldots,n-1\}$.
For example, consider the function (with $n = 21$) defined by
$$\matrix{f(2) = 5&f(3) = 4&f(4) = 5&f(5) = 3& f(6) = 21& f(7) = 7&\cr
     f(8) = 12&f(9) = 1&f(10) = 4&f(11) = 4&f(12) = 20&f(13)=19&f(14)=19\cr
     f(15)=6&f(16)=1&f(17)=16&f(18)=6&f(19)=7&f(20)=12&\cr}$$
Construct the directed graph $(V,E_f)$ for this function, and 
draw a picture of it.  

\bigskip
\item{B)} Your directed graph from A should {\it not\/} be a directed 
{\it tree}!  But its structure can be summarized as in 1,2 below.
Show in fact that all ``function digraphs'' constructed as in A
have the following structure:
\medskip
\itemitem{1)}  The vertices 1 and $n$ may have edges ``coming in''
but have none ``going out.''  (Why not?)  The connected pieces
of the graph containing the vertices $1$ and $n$ are trees (possibly
just a disconnected vertex if $1$ or $n$ is not in the range of $f$.)
\itemitem{2)}  Each other connected piece of the function digraph
consists of a cycle (with $c \ge 1$ edges), possibly with
several directed trees ``leading into'' the cycle.  (Could there
conceivably be more than one cycle in a connected piece?  Why or
why not?)

\bigskip
\item{C)}  There is a systematic way to get a tree from a
function digraph, using the observations in B: 
\bigskip
\item{$\bullet$}  Redraw the graph so that in 
each connected piece with a cycle, the cycle is ``stretched
flat'' across the top of that piece, with the smallest number 
in the cycle {\it at the right\/}. If there are 
$k$ of these pieces, call the rightmost vertices
$r_1, \ldots, r_k$.  Draw any trees leading into
the cycle below the cycle.  Arrange the pieces left to right
so that $r_1 < r_2 < r_3 < \cdots\ $, and put the tree
leading into 1 at the left, and the tree leading into $n$ at the right.
\item{$\bullet$}  Call the {\it leftmost\/} vertex in the cycle in the 
$i$th connected piece with a cycle $\ell_i$ (so there is an edge
from $r_i$ back to $\ell_i$ in the cycle.)
\item{$\bullet$}  To get a tree, delete the edges from $r_i$ 
to $\ell_i$ in the cycles, and add edges from 1 to $\ell_1$, 
from $r_i$ to
$\ell_{i+1}$, and from $r_k$ to $n$, to connect everything up.  
\bigskip
Do this with the digraph you constructed in C, and draw the 
resulting tree.

\bigskip
\item{D)}  Show that the process of C {\it always\/} yields
a (directed) tree if you apply it to one of our function 
digraphs.  

\bigskip
\item{E)}  Given the directed tree on the vertex set $\{1,2,3,\ldots,n\}$
produced by the process from C, 
how can you reverse the process to recover the digraph and the function $f$? 
Explain.  (Hint: Consider the path from vertex 1 to vertex $n$ in the
tree.)  

\bigskip
\item{F)}  Show that there are {\it the
same number of trees with vertex set $V = \{1,2,3,\ldots,n\}$ as functions 
$$f : \{2,3,4,\ldots,n-1\} \to \{1,2,3,\ldots,n\}$$
(Important Note: there is a slight subtlety here because
the trees we produced in C are directed trees.  You might want to 
argue, for instance, that given a non-directed tree, there
is {\it one and only one way\/} to assign directions to the edges
so that the resulting directed tree could have been produced by 
the process in C.)}
How many of these functions are there?  Your answer should conclude this
proof of Cayley's Theorem!

\bye