Lengths of words in transformation semigroups generated by digraphs
P.J. Cameron1 , A. Castillo-Ramirez∗2 , M. Gadouleau2 , and J.D. Mitchell1

arXiv:1602.00935v1 [] 2 Feb 2016

1

School of Mathematics and Statistics, University of St Andrews, St Andrews, Fife KY16 9SS,
U.K.
2
School of Engineering and Computing Sciences, Durham University, South Road, Durham
DH1 3LE, U.K.
April 4, 2018

Abstract
Given a simple digraph D on n vertices (with n ≥ 2), there is a natural construction of a
semigroup hDi associated with D. For any edge (a, b) of D, let a → b be the idempotent of
defect 1 mapping a to b and fixing all vertices other than a; then define hDi to be the semigroup
ha → b : (a, b) ∈ E(D)i. For α ∈ hDi, let ℓ(D, α) be the minimal length of a word in E(D)
expressing α. When D = Kn is the complete undirected graph, Howie and Iwahori, independently,
obtained a formula to calculate ℓ(Kn , α), for any α ∈ hKn i = Singn ; however, no analogous
nontrivial results are known when D 6= Kn . In this paper, we characterise all simple digraphs D
such that either ℓ(D, α) is equal to Howie-Iwahori’s formula for all α ∈ hDi, or ℓ(D, α) = n − fix(α)
for all α ∈ hDi, or ℓ(D, α) = n − rk(α) for all α ∈ hDi. When D is an acyclic digraph and α ∈ hDi,
we find a tight upper bound for ℓ(D, α). Finally, we study the case when D is a strong tournament
(which corresponds to a smallest generating set of idempotents of defect 1 of Singn ), and we propose
some conjectures.

1

Introduction

For any n ∈ N, n ≥ 2, let Singn be the semigroup of all singular (i.e. non-invertible) transformations
on [n] := {1, ..., n}. It is well-known (see [3]) that Singn is generated by its idempotents of defect
1 (i.e. the transformations α ∈ Singn such that α2 = α and rk(α) := |Im(α)| = n − 1). There are
exactly n(n − 1) such idempotents, and each one of them may be written as (a → b), for a, b ∈ [n],
a 6= b, where, for any v ∈ [n],
(
b if v = a,
(v)(a → b) :=
v otherwise.
Motivated by this notation, we refer to these idempotents as arcs.
In this paper, we explore the natural connections between simple digraphs on [n] and subsemigroups
of Singn ; explicitly, for any simple digraph D with vertex set V (D) = [n] and edge set E(D), we
associate the semigroup
hDi := h(a → b) ∈ Singn : (a, b) ∈ E(D)i .
We say that a subsemigroup S of Singn is arc-generated by a simple digraph D if S = hDi.
For the rest of the paper, we use the term ‘digraph’ to mean ‘simple digraph’ (i.e. a digraph with
no loops or multiple edges). A digraph D is undirected if its edge set is a symmetric relation on V (D),
and it is transitive if its edge set is a transitive relation on V (D). We shall always assume that D is
connected (i.e. for every pair u, v ∈ V (D) there is either a path from u to v, or a path from v to u)
because otherwise hDi ∼
= hD1 i × · · · × hDk i, where D1 , . . . , Dk are the connected components of D.
We say that D is strong (or strongly connected) if for every pair u, v ∈ V (D), there is a directed path
∗

Corresponding author: alonso.castillo-ramirez@durham.ac.uk

1

from u to v. We say that D is a tournament if for every pair u, v ∈ V (D) we have (u, v) ∈ E(D) or
(v, u) ∈ E(D), but not both.
Many famous examples of semigroups are arc-generated. Clearly, by the discussion of the first
paragraph, Singn is arc-generated by the complete undirected graph Kn . In fact, for n ≥ 3, Singn is
arc-generated by D if and only if D contains a strong tournament (see [4]). The semigroup of orderpreserving transformations On := {α ∈ Singn : u ≤ v ⇒ uα ≤ vα} is arc-generated by an undirected
path Pn on [n], while the Catalan semigroup Cn := {α ∈ Singn : v ≤ vα, u ≤ v ⇒ uα ≤ vα} is
arc-generated by a directed path P~n on [n] (see [11, Corollary 4.11]). The semigroup of non-decreasing
transformations OIn := {α ∈ Singn : v ≤ vα} is arc-generated by the transitive tournament T~n on [n]
(Figure 1 illustrates T~5 ).

1

2

3

4

5

Figure 1: T~5
Connections between subsemigroups of Singn and digraphs have been studied before (see [11, 12,
13, 14]). The following definition, which we shall adopt in the following sections, appeared in [14]:
Definition 1. For a digraph D, the closure D̄ of D is the digraph with vertex set V (D̄) := V (D)
and edge set E(D̄) := E (D) ∪ {(a, b) : (b, a) ∈ E (D) is in a directed cycle of D}.
Say that D is closed if D = D̄. Observe that hDi = hD̄i for any digraph D.
Recall that the orbits of α ∈ Singn are the connected components of the digraph on [n] with edges
{(x, xα) : x ∈ [n]}. In particular, an orbit Ω of α is called cyclic if it is a cycle with at least two
vertices. An element x ∈ [n] is a fixed point of α if xα = x. Denote by cycl(α) and fix(α) the number
of cyclic orbits and fixed points of α, respectively. Denote by ker(α) the partition of [n] induced by
the kernel of α (i.e. the equivalence relation {(x, y) ∈ [n]2 : xα = yα}).
We introduce some further notation. For any digraph D and v ∈ V (D), define the in-neighbourhood
and the out-neighbourhood of v by
N − (v) := {u ∈ V (D) : (u, v) ∈ E(D)} and N + (v) := {u ∈ V (D) : (v, u) ∈ E(D)},
S
respectively. We extend these definitions to any subset C ⊆ V (D) by letting N ǫ (C) := c∈C N ǫ (c),
where ǫ ∈ {+, −}. The in-degree and out-degree of v are deg− (v) := |N − (v)| and deg+ (v) := |N + (v)|,
respectively, while the degree of v is deg(v) := |N − (v) ∪ N + (v)|. For any two vertices u, v ∈ V (D),
the D-distance from u to v, denoted by dD (u, v), is the length of a shortest path from u to v in
D, provided that such a path exists. The diameter of D is diam(D) := max{dD (u, v) : u, v ∈
V (D), dD (u, v) is defined}.
Let D be any digraph on [n]. We are interested in the lengths of transformations of hDi viewed
as words in the free monoid D ∗ := {(a → b) : (a, b) ∈ E(D)}∗ . Say that a word ω ∈ D ∗ expresses (or
evaluates to) α ∈ hDi if α = ωφ, where φ : D ∗ → hDi is the evaluation semigroup morphism. For any
α ∈ hDi, let ℓ(D, α) be the minimum length of a word in D ∗ expressing α. For r ∈ [n − 1], denote
ℓ(D, r) := max {ℓ(D, α) : α ∈ hDi, rk(α) = r} ,
ℓ(D) := max {ℓ(D, α) : α ∈ hDi} .
The main result in the literature in the study of ℓ(D, α) was obtained by Howie and Iwahori,
independently, when D = Kn .

2

Theorem 1.1 ([5, 7]). For any α ∈ Singn ,
ℓ(Kn , α) = n + cycl(α) − fix(α).




Therefore, ℓ(Kn , r) = n + 21 (r − 2) , for any r ∈ [n − 1], and ℓ(Kn ) = ℓ(Kn , n − 1) = 32 (n − 1) .

In the following sections, we study ℓ(D, α), ℓ(D, r), and ℓ(D), for various classes of digraphs. In
Section 2, we characterise all digraphs D on [n] such that either ℓ(D, α) = n + cycl(α) − fix(α) for all
α ∈ hDi, or ℓ(D, α) = n − fix(α) for all α ∈ hDi, or ℓ(D, α) = n − rk(α) for all α ∈ hDi. In Section
3, we are interested in the maximal possible length of a transformation in hDi of rank r among all
digraphs D on [n] of certain class C; we denote this number by ℓCmax (n, r). In particular, when C
is the class of acyclic digraphs, we find an explicit formula for ℓCmax (n, r). When C is the class of
strong tournaments, we find upper and lower bounds for ℓCmax (n, r) (and for the analogously defined
ℓCmin (n, r)), and we provide some conjectures.

2

Arc-generated semigroups with short words

Let D be a digraph on [n], n ≥ 3, and α ∈ hDi. Theorem 1.1 implies the following three bounds:
ℓ(D, α) ≥ n + cycl(α) − fix(α) ≥ n − fix(α) ≥ n − rk(α).

(1)

The lowest bound is always achieved for constant transformations.
Lemma 2.1. For any digraph D on [n], if α ∈ hDi has rank 1, then ℓ(D, α) = n − 1.
Proof. It is clear that ℓ(D, α) ≥ n − 1 because α has n − 1 non-fixed points. Let Im(α) = {v0 } ⊆ [n].
Note that, for any v ∈ [n], there is a directed path in D from v to v0 (as otherwise, α 6∈ hDi). For any
d ≥ 1, let
Cd := {v ∈ [n] : dD (v, v0 ) = d}.
Sm
Clearly, [n] \ {v0 } = d=1 Cd , where m := maxv∈[n] {dD (v, v0 )} and the union is disjoint. For any
v ∈ Cd , let v ′ be a vertex in Cd−1 such that (v → v ′ ) ∈ D. For any distinct v, u ∈ Cd and any choice
of v ′ , u′ ∈ Cd−1 , the arcs (v → v ′ ) and (u → u′ ) commute; hence, we can decompose α as
α=

1
d=m

v∈Cd

(v → v ′ ),

where the composition of arcs is done from m down to 1.
Inspired by the previous lower bounds, in this section we characterise the all connected digraphs
D on [n] satisfying the following conditions:

2.1

∀α ∈ hDi, ℓ(D, α) = n + cycl(α) − fix(α);

(C1)

∀α ∈ hDi, ℓ(D, α) = n − fix(α);

(C2)

∀α ∈ hDi, ℓ(D, α) = n − rk(α).

(C3)

Digraphs satisfying condition (C1)

Theorem 1.1 says that Kn satisfies (C1). In order to characterise all digraphs satisfying (C1), we
introduce the following property on a digraph D:
(⋆) If dD (v0 , v2 ) = 2 and v0 , v1 , v2 is a directed path in D, then N + ({v1 , v2 }) ⊆ {v0 , v1 , v2 }.
We shall study the strong components of digraphs satisfying property (⋆). We state few observations that we use repeatedly in this section.
Remark 1. Suppose that D satisfies property (⋆). If v0 , v1 , v2 is a directed path in D and deg+ (v1 ) >
2, or deg+ (v2 ) > 2, then (v0 , v2 ) ∈ E(D). Indeed, if (v0 , v2 ) 6∈ E(D), then dD (v0 , v2 ) = 2, so, by
property (⋆), N + ({v1 , v2 }) ⊆ {v0 , v1 , v2 }; this contradicts that deg+ (v1 ) > 2, or deg+ (v2 ) > 2.
3

Remark 2. Suppose that D satisfies property (⋆). If v0 , v1 , v2 is a directed path in D and either v1
or v2 have an out-neighbour not in {v0 , v1 , v2 }, then (v0 , v1 ) ∈ E(D).
Remark 3. If D satisfies property (⋆), then diam(D) ≤ 2. Indeed, if v0 , v1 , . . . , vk is a directed path
in D with dD (v0 , vk ) = k ≥ 3, then v0 , v1 , v2 is a directed path in D and v2 has an out-neighbour
v3 6∈ {v0 , v1 , v2 }; by Remark 2, (v0 , v2 ) ∈ E(D), which contradicts that dD (v0 , vk ) = k.
Note that digraphs satisfying property (⋆) are a slight generalisation transitive digraphs.
Let D be a digraph and let C1 and C2 of be two strong components of D. We say that C1 connects
to C2 if (v1 , v2 ) ∈ E(D) for some v1 ∈ C1 , v2 ∈ C2 ; similarly, we say that C1 fully connects to C2 if
(v1 , v2 ) ∈ E(D) for all v1 ∈ C1 , v2 ∈ C2 . The strong component C1 is called terminal if there is no
strong component C 6= C1 of D such that C1 connects to C.
Lemma 2.2. Let D be a closed digraph satisfying property (⋆). Then, any strong component of D
is either an undirected path P3 or complete. Furthermore, P3 may only appear as a terminal strong
component of D.
Proof. Let C be a strong component of D. Since D is closed, C must be undirected. The lemma is
clear if |C| ≤ 3, so assume that |C| ≥ 4. We have two cases:
Case 1: Every vertex in C has degree at most 2. Then C is a path or a cycle. Since |C| ≥ 4 and
diam(D) ≤ 2, then C is a cycle of length 4 or 5; however, these cycles do no satisfy property (⋆).
Case 2: There exists a vertex a ∈ C of degree 3 or more. Any two neighbours of a are adjacent:
indeed, for any u, v ∈ N (a), u, a, v is a path and deg+ (a) > 2, so (u, v) ∈ E(D) by Remark 1.
Hence, the neighbourhood of a is complete and and every neighbour of a has degree 3 or more.
Applying this rule recursively, we obtain that every vertex in C has degree 3 or more, and the
neighbourhood of every vertex is complete. Therefore, C is complete because diam(D) ≤ 2.
Finally, if P3 is a strong component of D, there cannot be any edge coming out of it because of
property (⋆), so it must be a terminal component.
Lemma 2.3. Let D be a closed digraph satisfying property (⋆). Let C1 and C2 be strong components
of D, and suppose that C1 connects to C2 .
(i) If C2 is nonterminal, then C1 fully connects to C2 .
(ii) Let |C2 | = 1. If either |C1 | =
6 2, or the vertex in C1 that connects to C2 has out-degree at least 3,
then C1 fully connects to C2 .
(iii) Let |C2 | = 2. If not all vertices in C1 connect to the same vertex in C2 , then C1 fully connects
to C2 .
(iv) If |C2 | ≥ 3, then C1 fully connects to C2 .
Proof. Recall that C1 and C2 are undirected because D is closed. If |C1 | = 1 and |C2 | = 1, clearly C1
fully connects to C2 . Henceforth, we assume |C1 | ≥ 2 or |C2 | ≥ 2. Let c1 ∈ C1 and c2 ∈ C2 be such
that (c1 , c2 ) ∈ E(D). As C1 is a nonterminal, Lemma 2.2 implies that C1 is complete.
(i) As C2 is nonterminal, there exists d ∈ D \ (C1 ∪ C2 ) such that (c2 , d) ∈ E(D). Suppose that
|C1 | ≥ 2. Then, for any c′1 ∈ C1 \ {c1 }, c′1 , c1 , c2 is a directed path in D with d ∈ N + (c2 ), so
Remark 2 implies (c′1 , c2 ) ∈ E(D). Suppose now that |C2 | ≥ 2. Then, for any c′2 ∈ C2 \ {c2 },
c1 , c2 , c′2 is a directed path in D with d ∈ N + (c2 ), so again (c1 , c′2 ) ∈ E(D). Therefore, C1 fully
connects to C2 .
(ii) Suppose that |C1 | ≥ 2. If |C1 | > 2, then deg+ (c1 ) > 2, because C1 is complete. Thus, for each
c′1 ∈ C1 \ {c1 }, c′1 , c1 , c2 is a directed path in D with deg+ (c1 ) > 2, so (c′1 , c2 ) ∈ E(D) by Remark
1. As |C2 | = 1, this shows that C1 fully connects to C2 .

4

(iii) Let C2 = {c2 , c′2 } and let c′1 ∈ C1 \ {c1 } be such that (c′1 , c′2 ) ∈ E(D). For any b, d ∈ C1 , b 6= c1 ,
d 6= c′1 , both b, c1 , c2 and d, c′1 , c′2 are directed paths in D with c′2 ∈ N + (c2 ) and c2 ∈ N + (c′2 );
hence, (b, c2 ), (d, c′2 ) ∈ E(D) by Remark 2.
(iv) Suppose that C2 = P3 . Say C2 = {c2 , c′2 , c′′2 } with either dD (c2 , c′′2 ) = 2 or dD (c′2 , c′′2 ) = 2. In
any case, c1 , c2 , c′2 is a directed path in D with c′′2 ∈ N + ({c2 , c′2 }), so (c1 , c′2 ) ∈ E(D) by Remark
2; now, c1 , c′2 , c′′2 is a directed path in D with c2 ∈ N + ({c′2 , c′′2 }), so (c1 , c′′2 ) ∈ E(D). Hence,
c1 is connected to all vertices of C2 . As C1 is complete, a similar argument shows that every
c′1 ∈ C1 \ {c1 } connects to every vertex in C2 .
Suppose now that C2 = Km for m ≥ 3. By a similar reasoning as the previous paragraph, we
show that (c1 , v) ∈ E(D) for all v ∈ C2 . Now, for any c′1 ∈ C1 \ {c1 }, v ∈ C2 , c′1 , c1 , v is a
directed path in D so (c′1 , v) ∈ E(D) by Remark 2.

Lemma 2.4. Let D be a closed digraph satisfying property (⋆). Let Ci , i = 1, 2, 3, be strong components
of D, and suppose that C1 connects to C2 and C2 connects to C3 . If C1 does not connect to C3 , then
|C2 | = |C3 | = 1, C3 is terminal in D, and C2 is terminal in D \ C3 .
Proof. By Lemma 2.3 (i), C1 fully connects to C2 . Assume that C1 does not connect to C3 . Let
ci ∈ Ci , i = 1, 2, 3, be such that (c1 , c2 ), (c2 , c3 ) ∈ E(D). If C2 has a vertex different from c2 , Remark
2 ensures that (c1 , c3 ) ∈ E(D), which contradicts our hypothesis. Then |C2 | = 1. The same argument
applies if C3 has a vertex different from c3 , so |C3 | = 1. Finally, Remark 2 applied to the path c1 , c2 , c3
also implies that C3 is terminal in D and C2 is terminal in D \ C3 .
The following result characterises all digraphs satisfying condition (C1).
Theorem 2.5. Let D be a connected digraph on [n]. The following are equivalent:
(i) For all α ∈ hDi, ℓ(D, α) = n + cycl(α) − fix(α).
(ii) D is closed satisfying property (⋆).
Proof. In order to simplify notation, denote
g(α) := n + cycl(α) − fix(α).
First, we show that (i) implies (ii). Suppose ℓ(D, α) = g(α) for all α ∈ hDi. We use the one-line
notation for transformations: α = (1)α (2)α . . . (k)α, where x = (x)α for all x > k, x ∈ [n]. Clearly,
if D is not closed, there exists an arc α ∈ hDi\D, so 1 < ℓ(D, α) 6= g(α) = 1. In order to prove that
property (⋆) holds, let 1, 2, 3 be a shortest path in D. If (2 → v) ∈ hDi, for some v ∈ [n] \ {1, 2, 3},
then α = 3v3v ∈ hDi, but g(α) = 2 6= ℓ(D, α) = 3. If (3 → v) ∈ hDi, then α = 3vvv ∈ hDi, but
g(α) = 3 6= ℓ(D, α) = 4. Therefore, N + ({2, 3}) ⊆ {1, 2, 3}, and (⋆) holds.
Conversely, we show that (ii) implies (i). Let α ∈ hDi. We remark that any cycle of α belongs to
a strong component of D.
Claim 2.6. Let C be a strong component of D. Then either α fixes all vertices of C or |(Cα)∩C| < |C|.
Proof. Suppose that α|C , the restriction of α to C, is non-trivial and |(Cα) ∩ C| = |C|. Then α|C is a
permutation of C. Let u ∈ C and suppose that (u → v) is the first arc moving u in a word expressing
α in D ∗ . If v ∈ C, we have uα = vα, which contradicts that α|C is a permutation. If v ∈ C ′ for some
other strong component C ′ of D, then uα ∈
/ C which again contradicts our assumption.
Claim 2.7. Let u, v ∈ [n] be such that uα = v. If dD (u, v) = 2, then:
1. v is in a terminal component of D.
2. There is a path u, w, v of length 2 in D such that wα = vα = v; for any other path u, x, v of
length 2 in D, we have xα ∈ {x, v}.
5

Proof. Let C1 and C2 be strong components of D such that u ∈ C1 and v ∈ C2 . We analyse the
four possible cases in which dD (u, v) = 2. In the first three cases, we use the fact that hP3 i ∼
= O3 ,
hence we can order u < w < v and α is an increasing transformation of the ordered set {u, w, v}; thus
uα = wα = vα = v.
Case 1: C1 = C2 . By Lemma 2.2, C1 ∼
= P3 and it is a terminal component. Therefore, 2. holds as
there is a unique path from u to v.
Case 2: C1 connects to C2 and |C2 | =
6 2. As dD (u, v) = 2, C1 does not fully connect C2 , so, by
Lemma 2.3, |C2 | = 1, C2 is terminal, |C1 | = 2, and the vertex w ∈ C1 connecting to C2 = {v}
has out-degree 2. Then, by property (⋆), u, w, v is the unique path from u to v.
Case 3: C1 connects to C2 and |C2 | = 2. As dD (u, v) = 2, C1 does not fully connect C2 , so, by
Lemma 2.3, C2 is terminal and u, w, v is the unique path of length two from u to v, where w is
the other vertex of C2 .
Case 4: C1 does not connect to C2 . Since dD (u, v) = 2, there exist strong components C (1) , . . . , C (k)
such that C1 connects to C (i) and C (i) connects to C2 , for all 1 ≤ i ≤ k. By Lemma 2.4,
C (i) = {xi }, C2 = {v} is terminal and N + (xi ) = {v} for all i. Thus u, xi , v are the only paths
of length two from u to v; in particular, xi α ∈ {xi , v} for all xi . As uα = v, there must exist
1 ≤ j ≤ k such that w := xj is mapped to v.

Now we produce a word ω ∈ D ∗ expressing α of length g(α). Define
U := {u ∈ D : dD (u, uα) = 2}.
For every u ∈ U , let u′ be a vertex in D such that u, u′ , uα is a path and u′ α = uα. The existence of
u′ is guaranteed by Claim 2.7. Define a word ω0 ∈ D ∗ by
ω0 :=

u∈U (u

→ u′ )(u′ → uα).

Sort the strong components of D in topological order: C1 , . . . , Ck , i.e. for i 6= j, Ci connects to Cj
only if j > i. For each 1 ≤ i ≤ k, define
Si := {v ∈ Ci \ (U ∪ U ′ ) : vα ∈ Ci },
where U ′ := {u′ : u ∈ U }, and consider the transformation βi : Ci → Ci defined by
(
xα if x ∈ Si
xβi =
x
otherwise.
∼ P3 , then cycl(βi ) = 0 and βi can be computed with |Ci |−fix(βi ) arcs. Otherwise, Ci
If |Ci | ≤ 2 or Ci =
is a complete undirected graph. If βi ∈ Sing(Ci ), then by Theorem 1.1, there is a word ωi ∈ Ci∗ ⊆ D ∗
of length |Ci | + cycl(βi ) − fix(βi ) expressing βi . Suppose now that βi is a non-identity permutation of
Ci . By Claim 2.6, α does not permute Ci and there exists hi ∈ Ci \ (Ci α). Note that hi ∈ Ci \ Si .
Define β̂i ∈ Sing(Ci ) by

xα if x ∈ Si

xβ̂i = ai if x = hi


x
otherwise,
where ai is any vertex in Si . Then α|Si = β̂|Si . Again by Theorem 1.1, there is a word ωi ∈ Ci∗ ⊆ D ∗
of length |Ci | + cycl(β̂i ) − fix(β̂) = |Ci | + cycl(βi ) − fix(βi ) expressing β̂i .
The following word maps all the vertices in [n] \ (U ∪ U ′ ∪ Ci ) that have image in Ci :

ωi′ =
(a → aα) : a ∈ [n] \ (U ∪ U ′ ∪ Ci ), aα ∈ Ci .
6

Finally, let
ω := ω0 ωk ωk′ . . . ω1 ω1′ ∈ D ∗ .
Pk
Pk
It is easy to check that ω indeed expresses α. Since
i=1 fix(βi ) = fix(α) +
i=1 |Ci \ Si | and
Pk
P
k
′
′
i=1 ℓ(ωi ) =
i=1 |Ci \ (U ∪ U ∪ Si )|, we have
ℓ(ω) = 2|U | +

k
X

(ℓ(ωi ) + ℓ(ωi′ )) = n +

cycl(βi ) − fix(α) = g(α).

i=1

i=1

2.2

k
X

Digraphs satisfying condition (C2)

The characterisation of connected digraphs satisfying condition (C2) is based on the classification of
connected digraphs D such that cycl(α) = 0, for all α ∈ hDi.
For k ≥ 3, let Θk be the directed cycle of length k. Consider the digraphs Γ1 , Γ2 , Γ3 and Γ4 as
illustrated below:
1

2

3

4

5

4

4

2

5

3

Γ1

Γ2

1

5

3

2

1

1

4

2

3

Γ3

Γ4

Lemma 2.8. Let D be a connected digraph on [n]. The following are equivalent:
(i) For all α ∈ hDi, cycl(α) = 0.
(ii) D has no subdigraph isomorphic to Γ1 , Γ2 , Γ3 , Γ4 , or Θk , for all k ≥ 5.
Proof. In order to prove that (i) implies (ii), we show that if Γ is equal to Γi or Θk , for i ∈ [4], k ≥ 5,
then there exists α ∈ hΓi such that cycl(α) 6= 0.
• If Γ = Γ1 , take
α := (3 → 4)(4 → 5)(1 → 4)(4 → 3)(2 → 4)(4 → 1)(3 → 4)(4 → 2) = 21555.
• If Γ = Γ2 , take
α := (3 → 4)(4 → 5)(1 → 3)(3 → 4)(2 → 3)(3 → 1)(4 → 3)(3 → 2) = 21555.
• If Γ = Γ3 , take
α := (3 → 4)(2 → 3)(1 → 2)(3 → 1) = 2144.
• If Γ = Γ4 , take
α = (3 → 4)(4 → 5)(2 → 3)(3 → 4)(1 → 2)(4 → 1) = 21555.

7

• Assume Γ = Θk for k ≥ 5. Consider the following transformation of [k]:
(u ⇒ v) := (u → u1 ) . . . (ud−1 → v),
where u, u1 , . . . , ud−1 , v is the unique path from u to v on the cycle Θk . Take
α := (1 ⇒ k − 3)(k ⇒ k − 4)(k − 1 ⇒ 1)(k − 2 ⇒ k)(k − 3 ⇒ k − 1)(k − 4 ⇒ k − 2).
Then, α = (k − 1)(k − 1) . . . (k − 1) k 1 (k − 2), where (k − 1) appears k − 3 times, has the cyclic
component (k − 2, k).
Conversely, assume that D satisfies (ii). If n ≤ 3, it is clear that cycl(α) = 0, for all α ∈ hDi, so
suppose n ≥ 4. We first obtain some key properties about the strong components of D̄.
Claim 2.9. Any strong component of D̄ is an undirected path, an undirected cycle of length 3 or 4,
or a claw K3,1 (i.e. a bipartite undirected graph on [4] = [3] ∪ {4}). Moreover, if a strong component
of D is not an undirected path, then it is terminal.
Proof. Let C be a strong component of D̄. Clearly, C is undirected and, by (ii), it cannot contain a
cycle of length at least 5. If C has a cycle of length 3 or 4, then the whole of C must be that cycle
and C is terminal (otherwise, it would contain Γ3 or Γ4 , respectively). If C has no cycle of length 3
and 4, then C is a tree. It can only be a path or K3,1 , for otherwise it would contain Γ1 or Γ2 ; clearly,
K3,1 may only appear as a terminal component.
Suppose there is α ∈ hDi that has a cyclic orbit (so cycl(α) 6= 0). This cyclic orbit must be
contained in a strong component C of D̄, and Claim 2.9 implies that C ∼
= Γ, where Γ ∈ {K3,1 , Θ̄s , Pr :
s ∈ {3, 4}, r ∈ N}. If Γ = K3,1 or Γ = Θ̄s , then C is a terminal component, so α acts on C as some
transformation β ∈ hΓi; however, it is easy to check that no transformation in hΓi has a cyclic orbit.
If Γ = Pr , for some r, then α acts on C as a partial transformation β of Pr . Since hPr i = Or , β has
no cyclic orbit.
We introduce a new property of a connected digraph D:
(⋆⋆) For every strong component C of D, |C| ≤ 2 if C is nonterminal, and |C| ≤ 3 if C is terminal.
Lemma 2.10. Let D be a closed connected digraph on [n] satisfying property (⋆). The following are
equivalent:
(i) D satisfies property (⋆⋆).
(ii) D has no subdigraph isomorphic to Γ1 , Γ2 , Γ3 , Γ4 , or Θk , for some k ≥ 5.
Proof. If (i) holds, it is easy to check that D does not contain any subdigraphs isomorphic to Γ1 , Γ2 ,
Γ3 , Γ4 , or Θk for some k ≥ 5.
Conversely, suppose that (ii) holds. Let C be a strong component of D. If C is non-terminal,
Lemma 2.2 implies that C is complete; hence, |C| ≤ 2 as otherwise D would contain Γ4 as a subdigraph.
If C is terminal, Lemma 2.2 implies that C is complete or P3 ; hence, |C| ≤ 3 as otherwise D would
contain Γ3 as a subdigraph.
Theorem 2.11. Let D be a connected digraph on [n]. The following are equivalent:
(i) For all α ∈ hDi, ℓ(D, α) = n − fix(α).
(ii) D is closed satisfying properties (⋆) and (⋆⋆).
Proof. Clearly, D satisfies (i) if and only if it satisfies condition (C1) and cycl(α) = 0, for all α ∈ hDi.
By Theorem 2.5, Lemma 2.8 and Lemma 2.10, D satisfies (i) if and only if D satisfies (ii).

8

2.3

Digraphs satisfying condition (C3)

The following result characterises digraphs satisfying condition (C3).
Theorem 2.12. Let D be a connected digraph on [n]. The following are equivalent:
(i) For every α ∈ hDi, ℓ(D, α) = n − rk(α).
(ii) hDi is a band, i.e. every α ∈ hDi is idempotent.
(iii) Either n = 2 and D ∼
= K2 , or there exists a bipartition V1 ∪ V2 of [n] such that (i1 , i2 ) ∈ E(D)
only if i1 ∈ V1 , i2 ∈ V2 .
Proof. Clearly (i) implies (ii): if ℓ(D, α) = n − rk(α), then rk(α) = fix(α) by inequality (1), so α is
idempotent.
Now we prove that (ii) implies (iii). If there exist u, v, w ∈ [n] pairwise distinct such that
(u, v), (v, w) ∈ E(D) , then α = (v → w)(u → v) is not an idempotent. Therefore, for n ≥ 3, if
every α ∈ hDi is idempotent, then a vertex in D either has in-degree zero or out-degree zero: this
corresponds to the bipartition of [n] into V1 and V2 .
We finally prove that (iii) implies (i). Let n ≥ 3 and suppose that there exists a bipartition V1 ∪ V2
of [n] such that (i1 , i2 ) ∈ E(D) only if i1 ∈ V1 , i2 ∈ V2 . Then for any α ∈ hDi, all elements of V2 are
fixed by α and i1 α ∈ {i1 } ∪ N + (i1 ) for any i1 ∈ V1 . In particular, any non-fixed point of α is mapped
to a fixed point, so r := rk(α) = fix(α). Let J := {v1 , . . . , vn−r } ⊆ V1 be the set of non-fixed points of
α; therefore
α = (v1 → v1 α) . . . (vn−r → vn−r α),
where each one of the n − r arcs above belongs to hDi. The result follows by inequality (1).

3

Arc-generated semigroups with long words

Fix n ≥ 2. In this section, we consider digraphs D that maximise ℓ(D, r) and ℓ(D). For r ∈ [n − 1],
define
ℓmax (n, r) := max {ℓ(D, r) : V (D) = [n]} ,
ℓmax (n) := max {ℓ(D) : V (D) = [n]} .
Problem 1. Is ℓmax (n) upper bounded by a polynomial in n?
n\r
2
3
4
5
6

1
1
2
3
4
5

2

3

4

5

6
11
18
26

13
24
42

33
51

66

Table 1: First values of ℓmax (n, r)
The first few values of ℓmax (n, r), calculated with the GAP package Semigroups [9], are given in
Table 1. By Lemma 2.1, ℓmax (n, 1) = n − 1 for all n ≥ 2; henceforth, we shall always assume that
n ≥ 3 and r ∈ [n − 1] \ {1}.
In the following sections, we restrict the class of digraphs that we consider in the definition of
ℓmax (n, r) and ℓmax (n) to two important cases: acyclic digraphs and strong tournaments.

9

3.1

Acyclic digraphs

For any n ≥ 3, let Acyclicn be the set of all acyclic digraphs on [n], and, for any r ∈ [n − 1], define
ℓAcyclic
max (n, r) := max {ℓ(A, r) : A ∈ Acyclicn } ,
ℓAcyclic
max (n) := max {ℓ(A) : A ∈ Acyclicn } .
Without loss of generality, we assume that any acyclic digraph A on [n] is topologically sorted, i.e.
(u, v) ∈ E(A) only if v > u.
In this section, we establish the following theorem.
Theorem 3.1. For any n ≥ 3 and r ∈ [n − 1] \ {1},
(n − r)(n + r − 3)
+ 1,
2
1 2
Acyclic
ℓAcyclic
max (n) = ℓmax (n, 2) = (n − 3n + 4).
2

ℓAcyclic
max (n, r) =

First of all, we settle the case r = n − 1, for which we have a finer result.
Lemma 3.2. Let n ≥ 3 and A ∈ Acyclicn . Then, ℓ(A, n − 1) is equal to the length of a longest path
in A. Therefore,
ℓAcyclic
max (n, n − 1) = n − 1.
Proof. Let v1 , . . . , vl+1 be a longest path in A. Then α ∈ hAi defined by
(
vi+1 if v = vi , i ∈ [l],
vα :=
v
otherwise,
has rank n − 1 and requires at least l arcs, since it moves l vertices.
Conversely, let α ∈ A be a transformation of rank n − 1, and consider a word expressing α in A∗ :
α = (u1 → v1 )(u2 → v2 ) . . . (us → vs ).
Since α has rank n − 1, we must have v2 = u1 and by induction vi = ui−1 for 2 ≤ i ≤ s. As A is
acyclic, us , us−1 , . . . , u1 , v1 forms a path in A, so s ≤ l.
The following lemma shows that the formula of Theorem 3.1 is an upper bound for ℓAcyclic
max (n, r).
Lemma 3.3. For any n ≥ 3 and r ∈ [n − 1] \ {1},
ℓAcyclic
max (n, r) ≤

(n − r)(n + r − 3)
+ 1.
2

Proof. Let A be an acyclic digraph on [n], let α ∈ hAi be a transformation of rank r ≥ 2, and let
L ⊂ V (A) be the set of terminal vertices of A. For any u, v ∈ [n], denote the length of a longest path
from u to v in A as ψA (u, v).
P
Claim 3.4. ℓ(A, α) ≤ v∈[n] ψA (v, vα).

Proof. Let ω = (a1 → b1 ) . . . (al → bl ) be a shortest word expressing α in A∗ , with l = ℓ(A, α). Say
that the arc (ai → bi ), i ≥ 2, carries v ∈ [n] if v(a1 → b1 ) . . . (ai−1 → bi−1 ) = ai (assume that a1 → b1
only carries a1 ). Every arc (ai → bi ) carries at least one vertex, for otherwise we could remove that
arc form the word ω and obtain a shorter word still expressing α. Let v ∈ [n], and denote v0 = v and
vi = v(a1 → b1 ) . . . (ai → bi ) (and hence vl = vα). Let us remove the repetitions in this sequence: let
j0 = 0 and for i ≥ 1, ji = min{j : vj 6= vji−1 }. Then the sequence v = vj0 , vj1 , . . . , vjl(v) = vα forms a
path in A of length l(v), and hence l(v) ≤ ψ(v, vα). For each v ∈ [n], there are l(v) arcs in ω carrying
v, so the length of ω satisfies
n
X
X
l(v) ≤
ψA (v, vα).
l≤
v=1

v∈[n]

10

Claim 3.5. If |L| ≥ 2, then

P

v∈[n] ψA (v, vα)

≤

(n−r)(n+r−3)
.
2

Proof. As |L| ≥ 2, and A is topologically sorted, we have {n, n − 1} ⊆ L, and any α ∈ hAi fixes both
n − 1 and n, i.e. ψA (v, vα) = 0 for v ∈ {n − 1, n}. For any v ∈ [n − 2], we have
ψA (v, vα) ≤ min{n − 1, vα} − v.
Hence
X

X

ψA (v, vα) =

v∈[n]

ψA (v, vα)

v∈[n−2]

X

≤

(min{n − 1, vα} − v)

v∈[n−2]

X

=

w∈[n−2]α


min{n − 1, w}|wα−1 | − Tn−2 ,

where Tk = k(k+1)
. The summation is maximised when |nα−1 | = n − r and |wα−1 | = 1 for n − r + 1 ≤
2
w ≤ n − 2, thus yielding
X
ψA (v, vα) ≤ (n − 1)(n − r) + (Tn−2 − Tn−r ) − Tn−2
v∈[n]

=

Claim 3.6. If |L| = 1, then ℓ(A, α) ≤

(n − r)(n + r − 3)
.
2

(n−r)(n+r−3)
2

+ 1.

Proof. As A is topologically sorted, L = {n}. We use the notation from the proof of Claim 3.4. We
then have l(n) = 0. We have three cases:
Case 1: (n − 1) is fixed by α. Then, l(n − 1) = 0 and l(v) ≤ min{n − 1, vα} − v for all v ∈ [n − 2].
.
By the same reasoning as in Claim 3.5, we obtain ℓ(A, α) ≤ (n−r)(n+r−3)
2
Case 2: (n − 1)α = n and vα ≤ n − 1 for every v ∈ [n − 2]. Then again l(v) ≤ min{n − 1, vα} − v,
for all v ∈ [n − 2], and ℓ(A, α) ≤ (n−r)(n+r−3)
.
2
Case 3: n has at least two pre-images under α. Let ω = (a1 → b1 ) . . . (al → bl ) be a shortest word
expressing α in A∗ , and denote α0 = id and ǫi = (ai → bi ), αi = ǫ1 . . . ǫi for i ∈ [l]. We partition
nα−1 into two parts S and T :
S = {v ∈ nα−1 : vl(v)−1 = n − 1},

T = nα−1 \ S.

For all v ∈ S, if the arc carrying v to n − 1 is ǫj , then (n − 1)α−1
j−1 ⊆ S (v can only collapse
with other pre-images of α). Then the arc (n − 1 → n) occurs only once in the word ω (if it
occurs multiple times, then remove all but the last occurrence of that arc to obtain a shorter
word expressing α). If we do not count that arc, we have l′ (v) ≤ n − 1 − v arcs carrying v if
v ∈ S, l(v) ≤ n − 1 − v arcs carrying v if v ∈ T , and l(v) ≤ vα − v if vα 6= n. Again, we obtain
+ 1.
ℓ(A, α) ≤ (n−r)(n+r−3)
2

The following lemma completes the proof of Theorem 3.1.

11

Lemma 3.7. For any n ≥ 3 and r ∈ [n − 1] \ {1}, there exists an acyclic digraph Qn on [n] and a
transformation βr ∈ hQn i of rank r such that
ℓ(Qn , βr ) ≥

(n − r)(n + r − 3)
+ 1.
2

Proof. Let Qn be the acyclic digraph on [n] with edge set
E(Qn ) := {(u, u + 1) : u ∈ [n − 1]} ∪ {(n − 2, n)} .
For any r ∈ [n − 1] \ {1}, define βr ∈ hQn i by


n − r + v if v ∈ [r − 2],


n − 1
if v ∈ [n − 1] \ [r − 2], n − v ≡ 0
vβr :=

n
if v ∈ [n − 1] \ [r − 2], n − v ≡ 1



n
if v = n.

mod 2,
mod 2,

Let βr be expressed as a word in Q∗n of minimum length as

βr = (a1 → b1 ) . . . (al → bl ),
where l = ℓ(Qn , βr ). Denote α0 := id, ǫi := (ai → bi ), and αi := ǫ1 . . . ǫi , for i ∈ [l]. Say that ǫi carries
u ∈ [n] if uαi−1 = ai and hence uαi =
6 uαi−1 .
Claim 3.8. For each i ∈ [l], the arc ǫi carries exactly one vertex.
Proof. First, (a1 , b1 ) ∈ E(Qn ) and a1 βr = b1 βr imply that a1 = n − 1 and b1 = n. Suppose that there
is an arc ǫj , j ∈ [l], that carries two vertices u < v; take j to be minimal index with this property. We
remark that v ≤ n − 2 and uαj−1 = vαj−1 imply uβr = vβr . Then w := u + 1 satisfies wβr 6= uβr ,
so w is not carried by ǫj . If wαj−1 ≤ n − 2, then uαj−1 < wαj−1 < vαj−1 since u < w < v and the
graph induced by [n − 2] in Qn is the directed path P~n−2 ; this contradicts that uαj−1 = vαj−1 . Hence
wαj−1 ≥ n − 1 and vαj−1 ≥ n − 1. If vαj−1 = n or vβr = n − 1, then ǫj does not carry v. Thus,
vαj−1 = n − 1 and vβr = n. Then, in order to carry v to n − 1, we have ǫs = (n − 2 → n − 1) for at
least one s ∈ [l], and ǫj = (n − 1 → n). For s ∈ [j − 1], replace all occurrences ǫs = (n − 2 → n − 1)
with ǫ′s := (n − 2 → n) and delete ǫj : this yields a word in Q∗n of length l′ < l expressing βr , which is
a contradiction.
P
For all i ∈ [l], denote δ(i) :=
v∈[n] dQn (vαi , vβr ). We then have δ(l) = 0, and by the claim,
δ(i) ≥ δ(i − 1) − 1 for all i ∈ [l]. Thus l ≥ δ(0), where
X
δ(0) =
dQn (v, vβr )
v∈[n]

=

n−2
r−2
X
X
(n − 1 − v) + 1
(n − r) +
v=1

v=r−1

(n − r)(n + r − 3)
=
+ 1.
2

3.2

Strong tournaments

Let n ≥ 3. Recall that if T is a strong tournament on [n], then {a → b : (a, b) ∈ E(T )} is a minimal
generating set of Singn . Let Tourn denote the set of all strong tournaments on [n]. For r ∈ [n − 1],
define
ℓTour
max (n, r) := max{ℓ(T, r) : T ∈ Tourn },
ℓTour
max (n) := max{ℓ(T ) : T ∈ Tourn }.
12

Tour
Tour
Tour
Define analogously ℓTour
min (n, r) and ℓmin (n). The first few values of ℓmin (n, r) and ℓmax (n, r),
calculated with the GAP package Semigroups [9] using data from [8], are given by Table 2. The
calculation of these values has been the inspiration for the results and conjectures of this section.

Lemma 3.9. Let n ≥ 3 and T ∈ Tourn .
1. For any partition P of [n] into r parts, there exists an idempotent α ∈ Singn with ker(α) = P
such that ℓ(T, α) = n − r.
2. For any r-subset S of [n], there exists an idempotent α ∈ Singn with Im(α) = S such that
ℓ(T, α) = n − r.
Proof.
1. Let P = {P1 , . . . , Pr }. For all 1 ≤ i ≤ r, the digraph T [Pi ] induced by Pi is a tournament,
so it is connected and there exists a vertex vi reachable by any other vertex in Pi : let α map
the whole of Pi to vi . Then α, when restricted to Pi , is a constant map, which can be computed
using |Pi | − 1 arcs. Summing for i from 1 to r, we obtain that ℓ(T, α) = n − r.
2. Without loss of generality, let S = [r] ⊆ [n]. For every v ∈ [n], define
s(v) := min{s ∈ S : dT (s′ , v) ≥ dT (s, v), ∀s′ ∈ S}.
In particular, if v ∈ S, then s(v) = v. Moreover, if v = v0 , v1 , . . . , vd = s(v) is a shortest path
from v to s(v), with d = dT (v, s(v)), then s(vi ) = s(v) for all 0 ≤ i ≤ d. For each v ∈ [n], fix a
shortest path Pv from v to s(v), and consider the digraph D on [n] with edges
E(D) := {(a, b) : (a, b) ∈ E(Pv ) for some v ∈ [n]}.
Then, D is acyclic and the set of vertices with out-degree zero in D is exactly S. Let sort [n] so
that D has reverse topological order: (a, b) ∈ E(D) only if a > b. Note that S is fixed by this
sorting. Let α be given by vα := s(v); hence, with the above sorting
α=

r+1
v=n (v

→ v1 ).

Lemma 3.10. Let n ≥ 3, T ∈ Tourn , and α := (u → v) ∈ Singn , for (u, v) 6∈ E(T ). Then
ℓ(T, α) = 4dT (u, v) − 2.
Proof. Let u = v0 , v1 , . . . , vd = v be a shortest path from u to v in T , where d := dT (u, v). As
(u, v) 6∈ E(T ) and T is a tournament, we must have (v, u) ∈ E(T ). By the minimality of the path, for
any j + 1 < i, we have (vj , vi ) 6∈ E(T ), so (vi , vj ) ∈ E(T ). Then, the following expresses α with arcs
in T ∗ :
(v0 → vd ) =(vd → v0 )(vd−1 → vd )(vd−2 → vd−1 ) · · · (v1 → v2 )(v0 → v1 )
((v2 → v0 )(v1 → v2 )) ((v3 → v1 )(v2 → v3 )) · · · ((vd → vd−2 )(vd−1 → vd ))
(vd−2 → vd−1 ) · · · (v0 → v1 ).
n\r
3
4
5
6
7

2
(6, 6)
(8, 8)
(6, 11)
(8, 13)
(8, 16)

3

4

5

(11, 11)
(8, 14)
(10, 18)
(10, 22)

(10, 17)
(11, 21)
(11, 26)

(13, 24)
(13, 29)

6

(15, 32)

Tour
Table 2: First values of ℓTour
min (n, r), ℓmax (n, r) .
13

So ℓ(T, α) ≤ 4d − 2. For the lower bound, we note that any word in T ∗ expressing (u → v) must
begin with (v → u). Then, u has to follow a walk in T towards v; say this walk has length l ≥ d. All
the vertices on the walk must be moved away (as otherwise they would collapse with u) and have to
come back to their original position (since α fixes them all); as the shortest cycle in a tournament has
length 3, this process adds at least 3(l − 1) symbols to the word. Altogether, this yields a word of
length at least
1 + l + 3(l − 1) = 4l − 2 ≥ 4d − 2.

Let n = 2m + 1 ≥ 3 be odd, and let κn be the circulant tournament on [n] with edges E(κn ) :=
{(i, (i + j) mod n) : i ∈ [n], j ∈ [m]}. Figure 2 illustrates κ5 . In the following theorem, we use κn to
Tour
provide upper and lower bounds for ℓTour
min (n, r) and ℓmax (n, r) when n is odd.
5

4

1

3

2

Figure 2: The circulant tournament κ5 .
Theorem 3.11. For any n odd, we have
n + r − 2 ≤ ℓTour
min (n, r) ≤ n + 8r,
(r̂ + 1)(n − r̂) − 1 ≤ ℓTour
max (n, r) ≤ 6rn + n − 10r.
where r̂ = min{r − 1, ⌊n/2⌋}.
Proof. Let T ∈ Tourn and 2 ≤ r ≤ n − 1. We introduce the following notation:
[n]r := {u := (u1 , . . . , ur ) : ui 6= uj , ∀i, j},
)
( r
X
dT (ui , vi ) : u, v ∈ [n]r .
∆(T, r) := max
i=1

The result follows by the next claims.
Claim 3.12. r ′ (diam(T )−r ′ +1)+r−r ′ ≤ ∆(T, r) ≤ rdiam(T ), where r ′ = min{r, ⌊(diam(T )+1)/2⌋}.
Proof. The upper bound is clear. For the lower bound, let u, v ∈ [n] be such that dT (u, v) = diam(T ),
and let u = v0 , v1 , . . . , vd = v be a shortest path from u to v, where d = diam(T ). Then, dT (vi , vj ) = j−
i, for all 0 ≤ i ≤ j ≤ D. If 1 ≤ r ≤ ⌊(d + 1)/2⌋, consider u′ = (v0 , . . . , vr−1 ) and v′ = (vd−r+1 , . . . , vd ),
so we obtain ∆(T, r) ≥ r(d − r + 1). If r ≥ ⌊(d + 1)/2⌋, simply add vertices u′j and vj′ such that
/ T.
(u′j , vj′ ) ∈
Claim 3.13. min{∆(T, r) : T ∈ Tour(n)} = ∆(κn , r) = 2r.
Proof. Let u = (u1 , . . . , un ) form a Hamiltonian cycle, and choose v = (un , u1 , . . . , un−1 ). Then
dT (ui , vi ) ≥ 2 for all i. Conversely, since diam(κn ) = 2, we have ∆(κn , r) = 2r.
Claim 3.14. n − r + ∆(T, r − 1) ≤ ℓ(T, r) ≤ n + 6rdiam(T ) − 4r.

14

Proof. For the lower bound, consider α ∈ Singn as follows. Let u = (u1 , . . . , ur−1 ) and v =
(v1 , . . . , vr−1 ) achieve ∆(T, r − 1), and let v ∈
/ {v1 , . . . , vr−1 }; define
(
vi if x = ui ,
xα =
v otherwise.
Let ω = e1 . . . el (where ei = (ai → bi )) be a shortest word expressing α, where l := ℓ(T, α). Recall
that an arc ei carries a vertex c if ce1 . . . ei−1 = ai . By the minimality of ω, every arc carries at least
one vertex. Moreover, if c and d are carried by ei , then cα = dα; therefore, we can label every arc ei
of ω by an element c(ei ) ∈ Im(α) if ei carriesPvertices eventually mapping to c(ei ). Denote the number
of arcs labelled c as l(c), we then have l = c∈Im(α) l(c). For any u ∈ V , there are at least dT (u, uα)
arcs carrying u. Therefore,
l=

X

l(c) ≥

c∈Im(α)

r−1
X

dT (ui , vi ) +

i=1

X

dT (a, v) ≥ ∆(T, r − 1) + n − r.

a∈u
/

For the upper bound, we can express any α ∈ Singn of rank r in the following fashion. By Lemma
3.9, there exists β ∈ Singn with the same kernel as α such that ℓ(T, β) = n − r. Suppose that
Im(α) = {v1 , . . . , vr } and Im(β) = {u1 , . . . , ur }, where ui β −1 = vi α−1 , for i ∈ [r]. Let h ∈ [n] \ Im(β).
Define a transformation γ of [n] by


vi if x = ui ,
xγ = v1 if x = h,


x otherwise.
Then α = βγ, where γ ∈ Singn , and by Theorem 1.1

ℓ(Kn , γ) = n − fix(γ) + cycl(γ) ≤ r +

3r
r
= .
2
2

By Lemma 3.10, each arc associated to Kn may be expressed in at most 4diam(T ) − 2 arcs associated
to T ; therefore,
3r
ℓ(T, γ) ≤ (4diam(T ) − 2) = 6rdiam(T ) − 3r.
2
Thus,
ℓ(T, α) ≤ ℓ(T, β) + ℓ(T, γ) ≤ n + 6rdiam(T ) − 4r.

We finish this section by proposing two conjectures. Let πn be the tournament on [n] with edges
E(πn ) := {(i, (i + 1) mod n) : i ∈ [n]} ∪ {(i, j) : j + 1 < i}. Figure 3 illustrares π5 .

1

2

3

Figure 3: π5

15

4

5

Conjecture 3.15. For every n ≥ 3, r ∈ [n − 1], and T ∈ Tourn , we have
ℓ(T, r) ≤ ℓ(πn , r) = ℓTour
max (n, r),
with equality if and only if T ∼
= πn . Furthermore,
ℓ(πn ) = ℓTour
max (n) =

n2 + 3n − 6
,
2

which is achieved for α := n (n − 1) . . . 2 n.
Tournament πn has appeared in the literature before: it is shown in [10] that πn has the minimum number of strong subtournaments among all strong tournaments on [n]. On the other hand,
it was shown in [1] that, for n odd, the circulant tournament κn has the maximal number of strong
subtournaments among all strong tournaments on [n].
Conjecture 3.16. For every n ≥ 3 odd, r ∈ [n − 1], and T ∈ Tourn , we have
ℓTour
min (n, r) = ℓ(κn , r).
Furthermore,
Tour
ℓTour
min (n, 2) = n + 1 and ℓmin (n, r) = n + r,

for all 3 ≤ r ≤

n+1
2 .

References
[1] L. W. Beineke and F. Harary, The maximum number of strongly connected subtournaments,
Canad. Math. Bull. 8 (1965) 491–498.
[2] A. E. Evseev and N. E. Podran, Semigroups of transformations generated by idempotent of given
defect, Izv. Vyssh. Uchebn. Zaved. Mat. 2(177) (1972) 44–50.
[3] J.M. Howie, The subsemigroup generated by the idempotents of a full transformation semigroup,
J. Lond. Math. Soc., 41 (1966) 707–716.
[4] J.M. Howie, Idempotent generators in finite full transformation semigroups, Proc. R. Soc. Edinb.
81A (1978) 317–323.
[5] J.M. Howie, Products of idempotents in finite full transformation semigroups, Proc. R. Soc.
Edinb. 86A (1980) 243–254.
[6] J.M. Howie and R. B. McFadden, Idempotent rank in finite full transformation semigroups, Proc.
R. Soc. Edinb. 114A (1990) 161–167.
[7] N. Iwahori, A length formula in a semigroup of mappings, J. Fac. Sci. Univ. Tokyo Sect. 1A
Math. 24 (1977) 255–260.
[8] B. McKay, Catalog of directed graphs (online), September, 2015. Retrieved from:
https://cs.anu.edu.au/people/Brendan.McKay/data/digraphs.html
[9] J.D. Mitchell et al., Semigroups - GAP package, Version 3.0, September, 2015.
[10] J. W. Moon, On subtournaments of a tournament, Canad. Math. Bull. 9 (1966) 297–301.
[11] A. Solomon, Catalan Monoids, Monoids of Local Endomorphisms, and Their Presentations,
Semigroup Forum 53 (1996) 351–368.
[12] T. You and X. Yang, A Classification of the Maximal Idempotent-Generated Subsemigroups of
Finite Singular Groups, Semigroup Forum 64 (2002) 236–242.
16

[13] X. Yang and H. Yang, Maximal Regular Subsemibands of Singn , Semigroup Forum 72 (2006)
75–93.
[14] X. Yang and H. Yang, Isomorphisms of transformation semigroups associated with simple digraphs, Asian-European Journal of Mathematics 2(4) (2009) 727–737.
[15] P. Zhao, H. Hu and T. You, A note on maximal regular subsemigroups of the finite transformation
semigroups T (n, r), Semigroup Forum 88 (2014) 324–332.

17

