Lengths of words in transformation semigroups generated by digraphs

P. J. Cameron, A. Castillo-Ramirez, M. Gadouleau, J. D. Mitchell

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)
2 Downloads (Pure)


Given a simple digraph D on n vertices (with n≥2), there is a natural construction of a semigroup of transformations ⟨D⟩. For any edge (a, b) of D, let ab be the idempotent of rank n−1 mapping a to b and fixing all vertices other than a; then, define ⟨D⟩ to be the semigroup generated by ab for all (a,b)∈E(D). For α∈⟨D⟩, let ℓ(D,α) be the minimal length of a word in E(D) expressing α. It is well known that the semigroup Singn of all transformations of rank at most n−1 is generated by its idempotents of rank n−1. When D=Kn is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate ℓ(Kn,α), for any α∈⟨Kn⟩=Singn; however, no analogous non-trivial results are known when DKn. In this paper, we characterise all simple digraphs D such that either ℓ(D,α) is equal to Howie–Iwahori’s formula for all α∈⟨D⟩, or ℓ(D,α)=n−fix(α) for all α∈⟨D⟩, or ℓ(D,α)=n−rk(α) for all α∈⟨D⟩. We also obtain bounds for ℓ(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−1 of Singn). We finish the paper with a list of conjectures and open problems
Original languageEnglish
Pages (from-to)149-170
JournalJournal of Algebraic Combinatorics
Issue number1
Early online date8 Aug 2016
Publication statusPublished - Feb 2017


  • Transformation semigroup
  • Simple digraph
  • Word length


Dive into the research topics of 'Lengths of words in transformation semigroups generated by digraphs'. Together they form a unique fingerprint.

Cite this