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 Tn, 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.

About Peter Cameron

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

1 Response to Connections

  1. Robin Whitty says:

    João Araújo has every right to introduce neologisms into algebra but ‘semigroupist’ implies ‘groupist’ which I find ugly. Besides, there is an existing word ‘groupie’ which is ready to take on new meanings: https://en.wikipedia.org/wiki/Groupie_(disambiguation)
    I think João Araújo is a semigroupie.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.