Last week, Max Gadouleau and Alonso Castillo-Ramirez visited St Andrews. With James Mitchell, we worked on a problem about generating the semigroup of singular maps on a set (the full transformation semigroup minus the symmetric group). As usual in this situation, I want to write about the background, just to make sure I understand it!
Introduction
Let Sing_{n} be the semigroup of singular maps on the set {1,…n}. The first thing to note is that maps of rank n−1 cannot be generated by maps of smaller rank; so a generating set for the whole semigroup must yield all the maps of maximum rank. But it is not hard to see that the maps of rank n−1 do indeed generate the whole semigroup. So, if we are looking for a minimal generating set, we can concentrate on these.
The situation is still too complicated, so we will concentrate on idempotents of rank n−1 (that is, maps f satisfying f^{2} = f. Such a map only moves one point, say a; everything else (including the image of a) is fixed. So, if the image of a is b, we can write the map as a→b (a directed arc from a to b).
Now think about how these maps compose. If we compose a sequence
a_{1}→a_{2}→…→a_{k},
from left to right, then all the elements in the sequence pile up on a_{k}. Interesting, but not what we want if we are trying to generate maps of rank n−1.
In fact, if we insist on producing maps of maximum rank, then after the first move we have in effect a sliding block puzzle. Apply the transformation a→b. This leaves a “hole” in position a, into which we can now move another element; the tail of its arrow will then be the hole, and so on. Thus, we compose the arrows in the reverse of the natural order.
Tournaments and idempotent generators
A tournament is a directed graph in which, between any two vertices, there is an arc in one direction (only). Think of this graph as recording the result of a tournament in which any two teams play once, and an arrow a→b indicates that a beats b.
A tournament is strongly connected (or just strong) if there is a directed path between any two of its points.
I will use two facts about tournaments, which I will explain at the end. In what follows, only the first of these is used; but the second is useful in similar arguments.
- Any tournament has a Hamiltonian path (a path including all vertices).
- A strongly connected tournament has a Hamiltonian cycle (a cycle including all vertices).
The theorem (I am not sure who proved it) is the following.
Theorem: A set of rank n−1 idempotents is a minimal generating set for Sing_{n} if and only if the corresponding arcs form a strongly connected tournament.
What follows is not a detailed proof, but an explanation of this theorem. I will only describe one direction, that the arcs of a strongly connected tournament do give a minimal generating set.
As explained earlier, our task is to show that we can generate any map of rank n−1. This is an easy sliding-block puzzle if we can show that we can generate all of the idempotents. For example, to swap a and b, move a into the hole, b into the hole left by a, and then a from the original hole to the position vacated by b.
So, if a→b is in our set, we have to be able to generate b→a.
For this, take a directed path from b to a (this exists, by strong connectedness), and compose its elements (in the “wrong order”, as explained). The result is a map of rank n−1 which has the correct kernel and image but may not be an idempotent. But some power of it will indeed be an idempotent, so we are done!
This also explains why, in a minimal generating set, we don’t need arcs in both directions between two points. Why do we need a tournament rather than a digraph with fewer edges? If we compose a sequence of maps of rank n−1 and the result still has rank n−1, then its kernel is equal to the kernel of the first map in the sequence. So each possible kernel must be present among the generators. The kernel of a rank n−1 map is a partition with one part of size 2 and the rest singletons; so every 2-set must occur as a kernel, that is, every pair must carry an arc in one direction at least.
Now, to generate an arbitrary map f, we can use the following strategy. First, we produce a map with the right kernel classes. Take each kernel class. It induces a sub-tournament, which by one of our earlier facts contains a Hamiltonian path. Pushing forward along this path, we pile up all the elements on a single one. Once we have done this for all kernel classes (this requires n−r steps, where r is the rank), we simply have to move these piles of counters to their correct final positions.
I haven’t even got to the point where we started our work; but I think I understand the background a bit better now!
Two facts about tournaments
1. Let T be any tournament, and take a path in T of maximum length, say v_{1}→…→v_{k}. If there is a vertex w not on this path, there are three possibilities:
- w→v_{1}. Then we get a longer path by adding w at the beginning.
- v_{k}→w. Then we get a longer path by adding w at the end.
- If neither of these hold, let i be minimal such that w→v_{i}. Then i > 1, and so v_{i−1}→w; so we may replace the arc v_{i−1}→v_{i} by a diversion via w.
2. Let T be a strongly connected tournament, and take a cycle C in T of maximum length. If there is a point w not on the cycle, there are two possibilities:
- There are arcs in both directions between w and C. Somewhere, an arc from C to w is followed by an arc from w to the next point. Then we may extend C with a detour.
- This never happens. Then every point outside C either dominates or is dominated by C. If there were an arc from a point dominated by C to a point dominating C, we could find a longer cycle. Otherwise, the strong connectedness is contradicted. I leave the details as an exercise.
Here is a nice application of the second fact.
Proposition: Given a minimal generating set of idempotents for Sing_{n} as described above, any rank 1 map can be written as a product of n−1 generators (and no fewer).
At least n−1 generators are required, since each one reduces the rank by at most 1. To achieve this, choose a Hamiltonian cycle in the tournament. Starting one step after the position of the image of the required map, move around the cycle until this position is reached.
I have a lot of transformation semigroup code laying around if you could find use in any of it, http://chadbrewbaker.github.io . Most curious to me was that the idempotents of Tn and the iterated functions that go into them form nice connected components. The biggest open question for me is what is the smallest T_(z(n)) we can fit $n \times n$ binary matrix multiplication into (viewing each matrix as an abstract transformation of some semigroup)? Or more generally for all pure functions on finite sets, by embedding them in the smallest possible T_(z(n)) can we get tight computational complexity guarantees?
Peter, the Theorem above was proved by J.M.Howie, in his paper ‘Idempotent generators in finite full transformation semigroups’, Proc. Roy. Soc. Edinburgh Sect. A, 81(3-4):317–323, 1978. There is a brief survey of this and related stuff in our recent joint paper with James East, http://arxiv.org/pdf/1407.3312v2.pdf