I have written here about the lovely formula for the length of the longest chain of subgroups in the symmetric group Sn: take n, increase it by 50% (rounding up if necessary), subtract the number of ones in the base 2 representation of n, and subtract another 1, to get the answer.
Last year, James Mitchell and I, talking about possible projects, wondered whether we could get a similar nice formula for the length of the longest chain of sub-semigroups in the full transformation semigroup Tn.
We didn’t succeed in getting a formula. But soon after that, Max Gadouleau came to visit, and got interested; he came up with a method which produces long chains.
Briefly, it goes like this. We look for a long chain among the semigroup of transformations of given rank m (with an added zero, so that if the product of two maps has rank less than m, we re-define it to be zero). Now in a zero semigroup (one with all products zero), any subset is a semigroup, so there is a chain of length one less than the order of the semigroup. So the trick is to find large zero semigroups.
This is done as follows. A map of rank m has an image (a subset of size m) and a kernel (a partition with m parts); the product fg will have rank less than m (so be zero in our semigroup) if and only if the image of f is not a transversal for the kernel of g. So we need a large collection of m-sets and a large collection of m-partitions such that no subset is a transversal for any of the partitions. Max invented the term league for this combinatorial object; the content of a league is the product of the numbers of subsets and partitions.
By finding leagues with large content, we were able to show that the longest chain of sub-semigroups of Tn has length at least a positive fraction 1/e2 of the whole semigroup. (A sharp contrast with groups, where the length of a subgroup chain is bounded by the logarithm with the group order.)
At this point the investigation broadened, and involved James’ former student Yann Peresse, as we tried our hand at various other semigroups. In some cases we were able to find exact results (either as an explicit formula, or in terms of the length of various groups involved). These cases include the inverse semigroup In of partial 1–1 maps on an n-set, another close analogue of the symmetric group.
Our paper has just appeared on the arXiv.