Connections

A small story about how these things work. This is a paper with six authors, which has just been accepted for publication in the diamond journal Combinatorial Theory.

James East and three other semigroupists, Des FitzGerald (my classmate at the University of Queensland some time ago), James Mitchell (my colleague now in St Andrews), and Thomas Quinn-Gregson, were working on the problem: every finite semigroup can be embedded in a complete transformation semigroup (the analogue of Cayley’s Theorem for groups); but what is the smallest degree of a complete transformation semigroup embeddiing a given semigroup S?

The question for groups has been studied by various people including, most successfully, Babai, Goodman and Pyber in the 1990s. Roughly paraphrased, the obstruction to a group having a fathful permutation representation of small degree is the existence of an abelian subgroup of small index.

Perhaps one cannot expect general results of this sort for semigroups; in any case, the authors decided to restrict their attention to specific semigroups. Most of the effort went into variants of complete transformation semigroups. (The variant of the semigroup S defined by the element a is the semigroup with the same underlying set but with multiplication given by x*y = xay.) For the full transformation semigroup T_n, the minimum degree was known to be between n and 2n−1; the paper considerably improves these bounds.

However, as a sideline, they tackled some other semigroups such as bands. In this case, the problem is entirely combinatorial, and James thought that I might be interested in it. I was able to translate it into a hypergraph colouring problem, and come up with a conjecture about the value, with some evidence for it. So I decided to pass it on, and publicised it on this blog. This had the intended result: Luke Pebody got interested in it, and proved the conjecture, making up the set of six authors.

PS: I learned the word “semigroupist” from João Araújo, a semigroupist who can use the English language in constructive ways.