We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Dr Maximilien Gadouleau

Cameron, Peter J., Castillo-Ramirez, Alonso, Gadouleau, Maximilien & Mitchell, James D. (2017). Lengths of words in transformation semigroups generated by digraphs. Journal of Algebraic Combinatorics 45(1): 149-170.

Author(s) from Durham


Given a simple digraph D on n vertices (with n≥2n≥2 ), there is a natural construction of a semigroup of transformations ⟨D⟩⟨D⟩ . For any edge (a, b) of D, let a→ba→b be the idempotent of rank n−1n−1 mapping a to b and fixing all vertices other than a; then, define ⟨D⟩⟨D⟩ to be the semigroup generated by a→ba→b for all (a,b)∈E(D)(a,b)∈E(D) . For α∈⟨D⟩α∈⟨D⟩ , let ℓ(D,α)ℓ(D,α) be the minimal length of a word in E(D) expressing αα . It is well known that the semigroup SingnSingn of all transformations of rank at most n−1n−1 is generated by its idempotents of rank n−1n−1 . When D=KnD=Kn is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate ℓ(Kn,α)ℓ(Kn,α) , for any α∈⟨Kn⟩=Singnα∈⟨Kn⟩=Singn ; however, no analogous non-trivial results are known when D≠KnD≠Kn . In this paper, we characterise all simple digraphs D such that either ℓ(D,α)ℓ(D,α) is equal to Howie–Iwahori’s formula for all α∈⟨D⟩α∈⟨D⟩ , or ℓ(D,α)=n−fix(α)ℓ(D,α)=n−fix(α) for all α∈⟨D⟩α∈⟨D⟩ , or ℓ(D,α)=n−rk(α)ℓ(D,α)=n−rk(α) for all α∈⟨D⟩α∈⟨D⟩ . We also obtain bounds for ℓ(D,α)ℓ(D,α) when D is an acyclic digraph or a strong tournament (the latter case corresponds to a smallest generating set of idempotents of rank n−1n−1 of SingnSingn ). We finish the paper with a list of conjectures and open problems.