Saturday, July 20, 2013

Largest semigroup of "nonpermutational" transformations

Let Tn be the set of all transformations of [n]={1,...,n} for each n>0. Tn is a semigroup with product being function composition, i.e. (fg)(x) := g(f(x)) for each f,g Tn and x ∈ A. A subsemigroup of Tn is a subset of Tn which is closed under composition.
Call a transformation f: A→A nonpermutational if f(B)={f(x): x∈B}=B implies |B| ≤ 1 for any BA. (Equivalently, if A is finite, then f is nonpermutational if it has a unique fixed point Fix(f) and no more cycles saving the loop on Fix(f).)
The nonpermutational transformations of [n] do not form a semigroup. The question is, if T is a subsemigroup of Tn consisting of only nonpermutational transformations, how large can T be?

Partial results so far:

Probably there will be a follow-up on this subject soon -- stay tuned... ;-)

1 comment: