COMBINATORIAL TECHNIQUES FOR DETERMINING RANK AND IDEMPOTENT RANK OF CERTAIN FINITE SEMIGROUPS

Abstract

Abstract Let $\tau$ be a partition of the positive integer $n$. A partition of the set $\{1,2,\dots,n\}$ is said to be of type $\tau$ if the sizes of its classes form the partition $\tau$ of $n$. It is known that the semigroup $S(\tau)$, generated by all the transformations with kernels of type $\tau$, is idempotent generated. When $\tau$ has a unique non-singleton class of size $d$, the difficult Middle Levels Conjecture of combinatorics obstructs the application of known techniques for determining the rank and idempotent rank of $S(\tau)$. We further develop existing techniques, associating with a subset $U$ of the set of all idempotents of $S(\tau)$ with kernels of type $\tau$ a directed graph $D(U)$; the directed graph $D(U)$ is strongly connected if and only if $U$ is a generating set for $S(\tau)$, a result which leads to a proof if the fact that the rank and the idempotent rank of $S(\tau)$ are both equal to $$ \max\biggl\{\binom{n}{d},\binom{n}{d+1}\biggr\}. $$ AMS 2000 Mathematics subject classification: Primary 20M20; 05A18; 05A17; 05C20