Lengths of words in transformation semigroups generated by digraphs

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

doi:10.1007/s10801-016-0703-9

Lengths of words in transformation semigroups generated by digraphs

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

Authors

Peter J. Cameron

Alonso Castillo-Ramirez

Dr Maximilien Gadouleau m.r.gadouleau@durham.ac.uk
Associate Professor

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
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

Files

Accepted Journal Article (346 Kb)
PDF

Copyright Statement
© The Author(s) 2016. Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.