Minimal Generating Sets for Semigroups and Labeled Hamiltonian Cycles

by Inessa Levi

The rank of a finite semigroup $S$ is the cardinality of a minimum generating set for $S$; if $S$ is idempotent generated, the idempotent rank of $S$ is the cardinality of a minimum idempotent generating set for $S$. Given a partition type $\tau$ of [a proper subset of] $X_n=\{1,2,\dots,n\}$, the semigroup $S(\tau)$, generated by all total [partial] transformations of $X_n$ whose kernels are partitions of a given type $\tau$ of weight $r$, is idempotent-generated. It has been shown by Inessa Levi and Steve Seif for total transformations and by George Barnes and Inessa Levi for partial transformations that the rank and idempotent rank of $S(\tau)$ is equal to $\max\{\mathcal{N}(\tau),\binom n r \}$, where $\mathcal{N}(\tau)$ is the number of partitions of a given type $\tau$. If $\tau$ is a partition type of a proper subset of $X_n$, then $\max\{\mathcal{N}(\tau),\binom n r \}=\mathcal{N}(\tau)$. This work is a generalization of a result due to John Howie and Bob McFadden asserting that the semigroup $K(n,r)$ of all transformations of $X_n$ with at most $r$ elements in their image, has rank and idempotent rank equal to $S(n,r)$ (the Stirling number of the second kind). For any $\tau$ with at least two non-singleton classes, a minimal generating set of idempotents of $S(\tau)$ can be constructed by producing a labeled Hamiltonian cycle of the graph whose vertices are all $r$-element subsets of $X_n$, with two vertices being adjacent precisely when the corresponding sets intersect at $r-1$ elements. The existence of such labeled Hamiltonian cycles is a generalization of a long standing (and as yet unsolved) Middle Levels Conjecture attributed to Paul Erdos. The semigroup $S_{\mathcal{O}}(\tau)$ of all order-preserving transformations of the ordered set $X_n$, generated by the order-preserving transformations whose kernels are partitions of $X_n$ of a given partition type $\tau$, may or may not be idempotent-generated. Its rank equals to $\binom n r$ (Barnes and Levi).