Lengths of words in transformation semigroups generated by digraphs
Peter J. Cameron, Alonso Castillo-Ramirez, Maximilien Gadouleau, James D. Mitchell · Journal of Algebraic Combinatorics · 2016
Given a simple digraph D on n vertices (with $$n\ge 2$$ ), there is a natural construction of a semigroup of transformations $$\langle D\rangle $$ . For any edge (a, b) of D, let $$a\rightarrow b$$ be the idempotent of rank $$n-1$$ mapping a to b and fixing all vertices other than a; then, define $$\langle D\rangle $$ to be the semigroup generated by $$a \rightarrow b$$ for all $$(a,b) \in E(D)$$ . For $$\alpha \in \langle D\rangle $$ , let $$\ell (D,\alpha )$$ be the minimal length of a word in E(D) expressing $$\alpha $$ . It is well known that the semigroup $$\mathrm {Sing}_n$$ of all transformations of rank at most $$n-1$$ is generated by its idempotents of rank $$n-1$$ . 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 \langle K_n\rangle = \mathrm {Sing}_n$$ ; however, no analogous non-trivial results are known when $$D e 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 \langle D\rangle $$ , or $$\ell (D,\alpha ) = n - \mathrm {fix}(\alpha )$$ for all $$\alpha \in \langle D\rangle $$ , or $$\ell (D,\alpha ) = n - \mathrm {rk}(\alpha )$$ for all $$\alpha \in \langle D\rangle $$ . We also obtain bounds for $$\ell (D,\alpha )$$ when D is an acyclic digraph or a strong tournament (the latter case corresponds to a smallest generating set of idempotents of rank $$n-1$$ of $$\mathrm {Sing}_n$$ ). We finish the paper with a list of conjectures and open problems.