1
$\begingroup$

Given a transformation $t$ from the transformation semigroup $T_{n}$, if you take powers of $t$ under composition you get a length $s$ stem followed by a cycle. Permutations by definition have a length zero stem.

Are the terms "stem" and "cycle" common, or is some other terminology used in the literature?

$\endgroup$

1 Answer 1

1
$\begingroup$

This question seems a bit ill-posed to me. There are two possible interpretations here.

(1) If $s$ is an element of a finite semigroup, then $s^i=s^{i+p}$ where there is a minimal such $i$ and $p$. What is the common terminology for $i,p$?

The "official" terminology is that $i$ is the index and $p$ is the period. Or one might call the elements $\lbrace s,..,s^{i-1}\rbrace$ the nilpotent part and $\lbrace s^i,..,s^{i+p-1}\rbrace$ the maximal subgroup or minimal ideal.

This in any event has nothing to do with transformations.

(2) You are interested in the analogue of cycle decomposition for a transformation. In this case, the situation is more complicated than a stem and cycle.

The transformation $f$ has a set of recurrent points (also called the eventual image) on which $f$ acts like a permutation and hence decomposes into cycles. There may be several of them. Attached to each cycle are some number of trees which are directed toward the cycle. There is a only a stem followed by a cycle if there is a point from which every other point can be reached. The terminology is not so standard for this setup. I think there is a good chapter in Peter Higgins book Techniques of semigroups on this sort of thing.

$\endgroup$
6
  • $\begingroup$ s= [3, 3, 1, 0], s^2= [0, 0, 3, 3], s^3=[3, 3, 0, 0], s^4=[0, 0, 3, 3], ... The stem is [3, 3, 1, 0], the next two form the a cycle with period two. So "nilpotent" for [3, 3, 1, 0], and "maximal subgroup/minimal ideal" for {[0, 0, 3, 3], [3, 3, 0, 0]}? Hmm. I'll try to track down a copy of Higgins. $\endgroup$ May 15, 2013 at 19:08
  • $\begingroup$ Ben, you seem like just the person to ask a related question I posted on CSTheory: cstheory.stackexchange.com/questions/17326/name-this-digraph $\endgroup$ May 15, 2013 at 19:26
  • $\begingroup$ Yep, index and period seem to be standard: en.wikipedia.org/wiki/Monogenic_semigroup $\endgroup$ May 15, 2013 at 19:50
  • $\begingroup$ @Chad, it seems then that it is the cycle/stem in the semigroup you are interested in. The situation I refer to in 2 is s=[1,2,1,2]. Then on the level on {0,1,2,3} one has s cycles {1,2} and has two branches 0->1 and 2<-3. But on the semigroup it is still index 2, period 2. $\endgroup$ May 15, 2013 at 19:58
  • $\begingroup$ I am not on cstheory stackexchange. The answer to your question is the directed power graph of the semigroup, or at least groupprops.subwiki.org/wiki/Directed_power_graph_of_a_group says this is the name in group theory for this. I think the undirected version is more commonly studied, see this paper sciencedirect.com/science/article/pii/S0012365X10000531 by Peter Cameron et al. $\endgroup$ May 15, 2013 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.