Lengths of words in transformation semigroups generated by digraphs

Abstract

Given a simple digraph $D$ on $n$ vertices (with $n\ge 2$), there is a natural construction of a semigroup $⟨D⟩$ associated with $D$. For any edge $(a,b)$ of $D$, let $a\to b$ be the idempotent of defect $1$ mapping $a$ to $b$ and fixing all vertices other than $a$; then define $⟨D⟩$ to be the semigroup $⟨a\to b:(a,b)\in E(D)⟩$. For $\alpha \in ⟨D⟩$, let $\ell (D,\alpha )$ be the minimal length of a word in $E(D)$ expressing $\alpha$. When $D=K_n$ is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate $\ell (K_n,\alpha )$, for any $\alpha \in ⟨K_n⟩={\text{Sing}}_n$; however, no analogous nontrivial results are known when $D\ne K_n$. In this paper, we characterise all simple digraphs $D$ such that either $\ell (D,\alpha )$ is equal to Howie-Iwahori's formula for all $\alpha \in ⟨D⟩$, or $\ell (D,\alpha )=n-\text{fix}(\alpha )$ for all $\alpha \in ⟨D⟩$, or $\ell (D,\alpha )=n-\text{rk}(\alpha )$ for all $\alpha \in ⟨D⟩$. When $D$ is an acyclic digraph and $\alpha \in ⟨D⟩$, we find a tight upper bound for $\ell (D,\alpha )$. Finally, we study the case when $D$ is a strong tournament (which corresponds to a smallest generating set of idempotents of defect $1$ of ${\text{Sing}}_n$), and we propose some conjectures.

17 pages