Cycles and trees

The cycle has taken us up through forests …

Robert M. Pirsig, Zen and the Art of Motorcycle Maintenance

Here is a little nugget, and a problem. Nothing new but it might entertain you.

Every permutation is a product of transpositions, as is well known. The smallest number of transpositions required to express an n-cycle is n−1. So we could ask:

In how many ways can an n-cycle be written as the product of n−1 transpositions?

There is a beautiful answer: nⁿ⁻². The proof is quite short.

We can think of a transposition as an edge of an undirected graph. Now it is easy to see that the product of n−1 transpositions is an n-cycle if and only if the transpositions are the edges of a tree. Now there are nⁿ⁻² trees on the vertex set {1,…,n}, and the transpositions can be ordered in (n−1)! ways. So the number of pairs consisting of an n-cycle and an expression for it as a product of n−1 transpositions is nⁿ⁻²(n−1)!.

But there are (n−1)! cycles, and all are conjugate in the symmetric group, so each has the same number of expressions as the product of n−1 transpositions.

Given this nice result, and the fact that the number of trees on {1,…,n} is also nⁿ⁻², it would be natural to wonder if perhaps, given any labelled tree, every cycle can be obtained (uniquely) by ordering the edges suitably.

In the case of the star, with edges (1,i) for 2 ≤ i ≤ n, this is true; this follows from the fact that

(1,a₁)(1,a₂)… = (1,a₁,a₂,…),

the standard expression used to show that a cycle can be written as a product of transpositions.

However, this example is misleading:

Theorem Let T be a tree on the vertices {1,…n}. Then every n-cycle arises from a unique ordering of the edges of T if and only if T is a star.

The reason is very simple. For any tree which is not a star, there are two disjoint edges (a,b) and (c,d). Consider an ordering of the edges in which these two are consecutive. Since these transpositions commute, we can reverse them without changing the product. So some cycles occur more than once, whence necessarily some occur not at all (since the average number of occurrences is 1.)

Problem Given a tree, what is the distribution of numbers of occurrences of cycles as products of its transpositions in some order?

For example, if T is the 4-vertex path, then of the six 4-cycles, two occur twice, two occur once, and two do not occur at all.

PS I am sure that once, while walking in England, I saw a sign saying “xxxx Forest: No cycles”; but I didn’t have a camera with me, and I can’t recall which forest it was.

Advertisements