We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Lengths of words in transformation semigroups generated by digraphs.

Cameron, Peter J. and Castillo-Ramirez, Alonso and Gadouleau, Maximilien and Mitchell, James D. (2017) 'Lengths of words in transformation semigroups generated by digraphs.', Journal of algebraic combinatorics., 45 (1). pp. 149-170.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Advance online version)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Final published version)
Publisher Web site:
Publisher statement:© The Author(s) 2016. Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (, 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.
Date accepted:25 July 2016
Date deposited:31 August 2016
Date of first online publication:08 August 2016
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar