Generating singular maps

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 Singn 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 f2 = 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 ab (a directed arc from a to b).

Now think about how these maps compose. If we compose a sequence

a1a2→…→ak,

from left to right, then all the elements in the sequence pile up on ak. 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 ab. 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 ab 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 Singn 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 ab is in our set, we have to be able to generate ba.

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 nr 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 v1→…→vk. If there is a vertex w not on this path, there are three possibilities:

  • wv1. Then we get a longer path by adding w at the beginning.
  • vkw. Then we get a longer path by adding w at the end.
  • If neither of these hold, let i be minimal such that wvi. Then i > 1, and so vi−1w; so we may replace the arc vi−1vi 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 Singn 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.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , . Bookmark the permalink.

2 Responses to Generating singular maps

  1. 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?

  2. Igor Dolinka says:

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s