Why transformation monoids are harder than permutation groups

For permutation groups (or transformation monoids), we don’t need to assume the associative law, since composition of functions is always associative. So a permtation group is a set of mappings satisfying the identity, inverse and closure axioms. This implies that its orbit structure (given by the relation “lie in the same orbit”) is reflexive, symmetric, and transitive. You get from x to x by the identity; if you can get from x to y, then you can get back again by the identity; and if you can get from x to y and from y to z, then you can get from x to z by composition.

Now a reflexive, symmetric and transitive relation is an equivalence relation, and its job is simple: it partitions the domain into equivalence classes, which are the orbits of the group. There is the first structure theorem for group actions.

Around the 1960s, various people took this further. How do we describe the action of a group on the ordered pairs of elements of its domain? I will use the terminology that Donald Higman brought in then. The set of ordered pairs is, of course, partitioned into orbits. The set of orbits has three further properties: the diagonal is a union of orbits; the set of orbits is closed under transposition; and there is a counting condition, asserting that given three orbits O_i, O_j, O_k, and a pair (x,y) in the third orbit, the number of points z for which (x,z) lies in the first orbit and z,y in the second depends only on i,j,k and not on the choice of x and y. This leads to the possibility of using algebraic and combinatorial methods in the study, which Higman and others did very successfully.

The orbits of a group on ordered pairs are called the orbitals of the group.

Monoids, on the other hand, satisfy the closure and identity laws but not the inverse law. How does this change things?

We see that the orbit structure of a monoid is a reflexive and transitive relation which is not necessarily symmetric. Such a relation is called a partial preorder or preferential arrangement. (You are comparing various things; some pairs may be incomparable, but you may be indifferent about the relation of other pairs.) A partial preorder is significantly more complicated than a partition or equivalence relation. That is why transformation monoids are harder! Partial preorders are equivalent to topologies on a finite set.

But something can be done. Call two elements equivalent if the relation holds between them both ways round. Now it is not hard to show that this equivalence is an equivalence relation, so it does partition the domain; moreover, the equivalence classes (which are called indifference classes) are partially ordered by the relation.

So can we copy what Higman and the others did for the action on ordered pairs? I think there might be an interesting research project here, if someone wants to take it up.

First off, we have a partition of the ordered pairs into equivalence classes. It is easy to see that the first two conditions for a coherent configuration are ssatisfied. Does the third also hold? I haven’t thought carefully about this; it may be quite an easy question, but it is one that I don’t know the answer to.

Then we have the partial order on the indifference classes or orbitals, as we may call them. How do these structures fit together? Can one define the monoid analogue of Higman’s coherent configurations including this extra structure? What properties does it have? Is there interesting combinatorics there?