Permutation groups and transformation semigroups

When I first decided to apply to the LMS to run a Durham symposium on Permutation Groups and Transformation Semigroups, I had a fairly clear idea of what I wanted: topics (both finite and infinite) where the techniques and results were not just group theory or semigroup theory but a genuine interaction between the two. In the event, João Araújo put it beautifully in his talk. In the past, he said, semigroup theorists had tended to think that their work was done if they had reduced their problem to one in group theory. He began his lecture with a recent result cast as a conversation between a groupist and a semigroupist in which each contributes at all stages. I think that we achieved that.

I had in mind not a meeting on groups and semigroups, since the actions of these things on sets or structures of various kinds form a distinctive part of the subject. In the finite case, I had in mind synchronization, and also some recent work masterminded by João determining groups G for which, for any non-permutation f, or perhaps every map of a given rank, the semigroup generated by G and f has some interesting property such as regularity; these translate into properties of the permutation group G which are often very subtle. Synchronization was covered by several of the ABCRS collaboration, and João himself mentioned some of the other results.


In the infinite case, I had in mind that homogeneous structures would be the centrepiece. These have interesting automorphism groups and endomorphism monoids, and are closely involved in other areas of mathematics such as Ramsey theory, topological dynamics, and constraint satisfaction (these came up in the talks by Greg Cherlin, Jan Hubička, Dragan Mašulović, Lionel Nguyen Van The, Michael Pinsker, Christian Rosendal, and others). I also wanted to hear about measures concentrated on an isomorphism type of interesting countable structures (the work of Nate Ackerman, Cameron Freer and Rehana Patel which I have mentioned elsewhere, which they described in a series of three beautiful talks).

Lionel sketched the proof of the Kechris–Pestov–Todorcevic theorem, which asserts that an amalgation class has the Ramsey property for embeddings if and only if the automorphism group of its Fraïssé limit is extremely amenable (that is, any continuous action on a compact Hausdorff space has a fixed point). The point of his talk was to play variations on this theme: requiring the Ramsey property only for certain special colourings is equivalent to weakenings of extreme amenability such as strong amenability. The trouble is, as he admitted, either the combinatorial conditions on the colourings or the dynamic conditions on the actions are so complicated that it is not so easy to imagine applications. Dragan cast Ramsey theory in a categorical framework, obtaining new results from hold by means of duality or product theorems. He had even produced a categorical version of KPT, in which the main difficulty was defining the age of a structure in categorical terms.

A parody of the prehistory of group theory is that groups were at first automorphism groups; then permutation groups were invented, so that every automorphism group is a permutation group, and a theorem is proved saying that every permutation group is the automorphism group of something (at least in the finite case); then abstract groups are invented, so that every permutation group is an abstract group, and Cayley’s theorem tells us that every abstract group can be represented as a permutation group.

In the case of infinite permutation groups, another category intervenes. There is a topology on the infinite symmetric group (the topology of pointwise convergence, in which a neighbourhood basis of the identity consists of the pointwise stabilisers of all finite tuples); for countable degree, the topology is derived from a complete metric. Every automorphism group (of a first-order structure) is a closed subgroup of the symmetric group, and conversely. So we have:

Automorphism group → Permutation group → Topological group → Abstract group.

Various reconstruction problems now arise. Can you derive the permutation group structure from the topological group structure? [Yes, up to bi-interpretability.] Can you derive the topological group structure from the abstract group structure? [Yes if and only if the small index property holds: every subgroup of index less than the continuum is the stabiliser of a finite tuple. This holds for the automorphism groups of many nice structures, but not of all structures.]

As well as automorphism groups, we have several flavours of endomorphism monoids of structures, where homomorphisms are required to preserve the relations or functions of the first-order structure. We can consider injective endomorophisms, or surjective endomorphisms, or all endomorphisms. In each case we can complete the row to transformation semigroups, topological semigroups, and abstract semigroups. The reconstruction problem becomes harder, as Christian Pech, John Truss, and Edith Vargas-Garcia described.

There is a further step too. We can replace monoids by clones, which are not just sets of functions from X to X closed under composition and containing the identity, but sets of functions from Xn to X for all n, closed under composition and containing all projection maps. Clones of polymorphisms of relational structures play the role of automorphism groups or endomorphism monoids, and have come into prominence in connection with the constraint satisfaction problem in computer science. Thus we have

Polymorphism clone → Function clone → Topological clone → Abstract clone.

The connections with the CSP push us in that direction, as the talks of Michael Pinsker and others clearly illustrated. This was always part of my vision for the meeting, although adding “polymorphism clones” to the title would have made it a bit unwieldy. There are also other variants of clones, where (for example) we could require the polymorphisms to be surjective.

Of course, not everybody fitted into this neat framework, and this simply enriched the meeting, since other interesting topics were discussed which don’t (yet) link up to this material.

My favourite example of this was the series of talks by Ben Steinberg on representation theory of (finite) monoids, the subject of his forthcoming book. He illustrated by a beautiful example: Tsetlin’s library. The books on a library shelf are ordered; at each time step, a book is selected from the shelf and is returned at the head of the order. If the selection is uniform at random, then we have a random walk, which can be analysed by group theory. But suppose this is not so. (For example, we might be more likely to take a book on group theory than one on partial differential equations). Ben showed us how to analyse this Markov chain using the representation theory he had developed for a certain monoid which he described.

Other things went on behind the scenes. Stuart Margolis gave the CGMP team a tutorial on the Rhodes–Silva theory of Boolean representability. This suggested to me a connection with the theory of irredundant bases for finite permutation groups, which give combinatorial structures more general than matroids, as I have discussed elsewhere. I hope that interesting developments will grow out of this.


Altogether a great conference, in my opinion. It was pleasant to have so many of my collaborators and former students there. Sincere thanks to the people in Durham, both in the mathematics department and in Grey College, and to my co-organisers Dugald Macpherson and James Mitchell, for making it happen!


About Peter Cameron

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

Leave a Reply

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

You are commenting using your 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