Chains of semigroups

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.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems, symmetric group and tagged , , , , , , . Bookmark the permalink.

7 Responses to Chains of semigroups

  1. Hi Peter, thanks for another great post! The link to the paper points to the your blog post on the length of the longest chain of subgroups in the symmetric group $S_n$, and not the arXiv. –>Our paper has just appeared on the arXiv.

    • Thanks. Not sure how that happened. Probably I forgot to press the copy button before I pasted the address in, so it pasted the one before… Fixed now.

  2. I was playing around trying on a similar problem looking at chains of iterated permutations. On the transformation semi-group on n elements, for “free” you get the longest chain in Sn as a lower bound. If you have a S_{n-k} with a longest chain the same size as your longest in Sn, you can extend it by adding some forgetful functions that collapse into it. I would be curious to see any constructions of large chains that have more than one idempotent transformation.

  3. Irfan says:

    How we can prove that kernal of a congruence of an inverse semigroup A is inverse subsemigroup of A? How the trace of a congruence of an inverse semigroup A is defined in the form a a set?

  4. Des FitzGerald says:

    The kernel you ask about is defined as the set of elements of A which map to an idempotent (this is a straightforward extension of the idea in groups). As such, A is closed under multiplication (because idempotents commute, a product is still idempotent) and inversion (because the map respects inversion too). This makes A an inverse subsemigroup.

    Unlike a group kernel, A does not uniquely determine the associated map. For this one also needs to know which idempotents map to the same element; this information is contained in an equivalence relation, which is known as the trace. It is regrettable that these words are used for different concepts in other fields, but there just are not enough suitable words to go around! There is another idea of kernel which is used in semigroup theory—it is the congruence relation associated with the map. Sometimes the first use of kernel above is written as Kernel to distinguish the two.

    • Irfan says:

      My question was about the idea of a kernel of congruence in an inverse semigroup A. Which may be defined as ker(ρ) = {a ∈ A : ∃(e ∈ E(A) :(a,e) ∈ ρ} =U{eρ : e ∈ E(A)} where ρ is a congruence on an inverse semigroup A and E(A) is semilattice of idempotents.
      1. My 1st question is how we can prove that ker(ρ) is closed under inverses and how we can prove that it is closed under multiplication.
      2. My 2nd question is how tr(ρ) is written in the form of a set.

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