Research Repository

# Lengths of words in transformation semigroups generated by digraphs

## Authors

Peter J. Cameron

Alonso Castillo-Ramirez

James D. Mitchell

### Abstract

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.

### Citation

Cameron, P. J., Castillo-Ramirez, A., Gadouleau, M., & Mitchell, J. D. (2017). Lengths of words in transformation semigroups generated by digraphs. Journal of Algebraic Combinatorics, 45(1), 149-170. https://doi.org/10.1007/s10801-016-0703-9

Journal Article Type Article Jul 25, 2016 Aug 8, 2016 Feb 1, 2017 Aug 26, 2016 Aug 31, 2016 Journal of Algebraic Combinatorics 0925-9899 1572-9192 Springer Peer Reviewed 45 1 149-170 https://doi.org/10.1007/s10801-016-0703-9

#### Files

Accepted Journal Article (346 Kb)
PDF