Lengths of words in transformation semigroups generated by digraphs

Cameron, Peter J.; Castillo-Ramirez, Alonso; Gadouleau, Maximilien; Mitchell, James D.

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
• Acceptance Date: Jul 25, 2016
• Online Publication Date: Aug 8, 2016
• Publication Date: Feb 1, 2017
• Deposit Date: Aug 26, 2016
• Publicly Available Date: Aug 31, 2016
• Journal: Journal of Algebraic Combinatorics
• Print ISSN: 0925-9899
• Electronic ISSN: 1572-9192
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 45
• Issue: 1
• Pages: 149-170
• DOI: https://doi.org/10.1007/s10801-016-0703-9
• Public URL: https://durham-repository.worktribe.com/output/1405714