Mathematics 357 – Combinatorics Extra Credit Problem Set April 15, 2005

I. Here is an application of Hall’s Theorem related to Question I on Problem Set 8. A doubly stochastic matrix M is an n × n real matrix with nonnegative entries and row and column sums equal to 1. For instance, the matrix on the left is doubly stochastic:

( \begin{matrix}.5 & .5 & 0 \\ .5 & 0 & .5 \\ 0 & .5 & .5 \end{matrix} ) = (.5)T_{12} + (.5)T_{23}

In the sum on the right, T_{12} and T_{23} are the 3 × 3 permutation matrices from question I. In general we will call a linear combination ∑_{i} c_{i}P_{i} of permutation matrices a convex combination if the c_{i} ≥ 0 for all i, and ∑_{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!)

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

Cayley’s Tree Theorem. There are n^{n−2} different labeled trees with vertex set {1, 2, …, n}.

We can study structures similar to our graphs, but where each edge has a specified direction. We might call these directed graphs, or digraphs for short. Pictorially, we could draw an arrowhead on each edge of an ordinary graph to indicate the direction of the edge.

A) Consider any function

f : {2, 3, 4, …, n − 1} → {1, 2, 3, …, n}

We can construct a digraph (V, E_{f}) representing the function by taking the vertex set to be V = {1, 2, 3, …, n} and the edge set E_{f} to consist of the collection of directed edges from i to f(i) for each i ∈ {2, 3, 4, …, n−1}. For example, consider the function (with n = 21) defined by

f(2) = 5 f(3) = 4 f(4) = 5 f(5) = 3 f(6) = 21 f(7) = 7
f(8) = 12 f(9) = 1 f(10) = 4 f(11) = 4 f(12) = 20 f(13) = 19 f(14) = 19
f(15) = 6 f(16) = 1 f(17) = 16 f(18) = 6 f(19) = 7 f(20) = 12

Construct the directed graph (V, E_{f}) for this function, and draw a picture of it.

B) Your directed graph from A should not be a directed 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:

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.)

2) Each other connected piece of the function digraph consists of a cycle (with c ≥ 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?)

C) There is a systematic way to get a tree from a function digraph, using the observations in B:

• 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 at the right. If there are k of these pieces, call the rightmost vertices r_{1}, …, 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} < ⋯, and put the tree leading into 1 at the left, and the tree leading into n at the right.

• Call the leftmost vertex in the cycle in the ith connected piece with a cycle ℓ_{i} (so there is an edge from r_{i} back to ℓ_{i} in the cycle.)

• To get a tree, delete the edges from r_{i} to ℓ_{i} in the cycles, and add edges from 1 to ℓ_{1}, from r_{i} to ℓ_{i+1}, and from r_{k} to n, to connect everything up.

Do this with the digraph you constructed in C, and draw the resulting tree.

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

E) Given the directed tree on the vertex set {1, 2, 3, …, 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.)

F) Show that there are the same number of trees with vertex set V = {1, 2, 3, …, n} as

functions

f : {2, 3, 4, …, n − 1} → {1, 2, 3, …, 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 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!