Generators and ranks in finite partial transformation semigroups
We extend the concept of path-cycle, to the semigroup Pn, of all partial maps on Xn={1,2,…,n}, and show that the classical decomposition of permutations into disjoint cycles can be extended to elements of Pn by means of path-cycles. The device is used to obtain information about generating sets for...
Gespeichert in:
| Datum: | 2017 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2017
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/156026 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Generators and ranks in finite partial transformation semigroups / G.U. Garba, A.T. Imam // Algebra and Discrete Mathematics. — 2017. — Vol. 23, № 2. — С. 237-248. — Бібліогр.: 16 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-156026 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1560262019-06-18T01:30:53Z Generators and ranks in finite partial transformation semigroups Garba, G.U. Imam, A.T. We extend the concept of path-cycle, to the semigroup Pn, of all partial maps on Xn={1,2,…,n}, and show that the classical decomposition of permutations into disjoint cycles can be extended to elements of Pn by means of path-cycles. The device is used to obtain information about generating sets for the semigroup Pn\Sn, of all singular partial maps of Xn. Moreover, we give a definition for the (m,r)-rank of Pn\Sn and show that it is n(n+1)/2. 2017 Article Generators and ranks in finite partial transformation semigroups / G.U. Garba, A.T. Imam // Algebra and Discrete Mathematics. — 2017. — Vol. 23, № 2. — С. 237-248. — Бібліогр.: 16 назв. — англ. 1726-3255 2010 MSC:20M20. http://dspace.nbuv.gov.ua/handle/123456789/156026 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We extend the concept of path-cycle, to the semigroup Pn, of all partial maps on Xn={1,2,…,n}, and show that the classical decomposition of permutations into disjoint cycles can be extended to elements of Pn by means of path-cycles. The device is used to obtain information about generating sets for the semigroup Pn\Sn, of all singular partial maps of Xn. Moreover, we give a definition for the (m,r)-rank of Pn\Sn and show that it is n(n+1)/2. |
| format |
Article |
| author |
Garba, G.U. Imam, A.T. |
| spellingShingle |
Garba, G.U. Imam, A.T. Generators and ranks in finite partial transformation semigroups Algebra and Discrete Mathematics |
| author_facet |
Garba, G.U. Imam, A.T. |
| author_sort |
Garba, G.U. |
| title |
Generators and ranks in finite partial transformation semigroups |
| title_short |
Generators and ranks in finite partial transformation semigroups |
| title_full |
Generators and ranks in finite partial transformation semigroups |
| title_fullStr |
Generators and ranks in finite partial transformation semigroups |
| title_full_unstemmed |
Generators and ranks in finite partial transformation semigroups |
| title_sort |
generators and ranks in finite partial transformation semigroups |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2017 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/156026 |
| citation_txt |
Generators and ranks in finite partial transformation semigroups / G.U. Garba, A.T. Imam // Algebra and Discrete Mathematics. — 2017. — Vol. 23, № 2. — С. 237-248. — Бібліогр.: 16 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT garbagu generatorsandranksinfinitepartialtransformationsemigroups AT imamat generatorsandranksinfinitepartialtransformationsemigroups |
| first_indexed |
2025-07-14T08:17:04Z |
| last_indexed |
2025-07-14T08:17:04Z |
| _version_ |
1837610087626047488 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 23 (2017). Number 2, pp. 237–248
c© Journal “Algebra and Discrete Mathematics”
Generators and ranks
in finite partial transformation semigroups
Goje Uba Garba and Abdussamad Tanko Imam
Communicated by V. Mazorchuk
Abstract. We extend the concept of path-cycles, defined
in [2], to the semigroup Pn, of all partial maps on Xn = {1, 2, . . . , n},
and show that the classical decomposition of permutations into
disjoint cycles can be extended to elements of Pn by means of path-
cycles. The device is used to obtain information about generating
sets for the semigroup Pn \ Sn, of all singular partial maps of Xn.
Moreover, by analogy with [3], we give a definition for the (m, r)-rank
of Pn \ Sn and show that it is n(n+1)
2 .
1. Introduction
Since the work of Howie [7], establishing that every singular map in
the full transformation semigroup Tn on the finite set Xn = {1, 2, . . . , n}
is expressible as a product (that is composition) of idempotent singular
maps, there have been many articles concerned with this idea in Tn (see
for example, [1–3,8–10,12,13,15]).
Evseev and Podran [5] established that even in the larger semroup Pn,
consisting of all partial maps on Xn, all elements (other than permutations)
are expressible as products of idempotents. Garba [6] extended all the
results of [9–11,15] to Pn using a result of Vagner [16] quoted in [4, p.254].
2010 MSC: 20M20.
Key words and phrases: path-cycle, (m, r)-path-cycle, m-path, generating set,
(m, r)-rank.
238 Generators and ranks in Pn
In analysing elements of Tn, there are many variations in notations.
Lipscomb [14] developed what might be called a linear notation for ele-
ments of Pn. Recently, Ayik et al. [2] described an alternative approach,
to the Lipscomb’s linear notation for elements of Tn, which generalised
the concept of cycle notation for permutations in the symmetric group Sn.
In this paper we show that this idea can be further generalise to the
larger semigroup Pn via Vagner’s result. The technique is used to obtain
information about generators for Pn \ Sn.
It is known (see [6, Theorem 4.1]) that the rank of Pn \ Sn, defined by
rank(Pn \ Sn) = min{|A| : 〈A〉 = Pn \ Sn},
is equal to n(n+1)/2. The idempotent rank of Pn \Sn is the cardinality of
a smallest generating set for Pn \ Sn consisting solely of idempotents, and
this too equals n(n+1)/2. For any fixed m and r such that 2 6 r 6 m 6 n,
we give a definition for (m, r)-rank of Pn \ Sn, analogous to the definition
given in [3] for Tn \ Sn, and show that it is once again equal to n(n+1)
2 .
This article is a direct translation of the results in [2,3] for Tn to similar
results concerning Pn. Thus, many of our proofs are direct modifications
of the corresponding proofs in [2, 3].
2. Preliminaries
Let Xn = {1, . . . , n} and let Pn be the partial transformation semi-
group on Xn. For a subset {x1, . . . , xm} of Xn let α ∈ Pn be such that
xiα = xi+1(1 6 i 6 m − 1) and xα = x (x ∈ Xn \ {x1, . . . , xm}). If:
i) xmα = xr for some 1 6 r 6 m, α is called an (m, r)-path-cycle and
is denoted by α = [x1, . . . , xm|xr];
ii) xm /∈ dom(α), α is called an (m, 0)-path-cycle, or an m-chain and
is denoted by α = [x1, . . . , xm].
An element of Pn is called a path-cycle of size m if it is either an
(m, r)-path-cycle or an m-chain. An (m, r)-path-cycle is called: an r-cycle
if r = 1; a proper path-cycle if r 6= 1; and an m-path if m = r.
We let X0
n = Xn ∪ {0} and denote the semigroup of all full transfor-
mations of X0
n by TX0
n
. For each α ∈ Pn the map α∗, defined by
α∗ =
{
xα if x ∈ dom(α),
0 if x /∈ dom(α),
G. U. Garba, A. T. Imam 239
belongs to TX0
n
. Let P∗
n be the set of all elements in TX0
n
that fixed 0
and let S∗
n be the set of all permutations in P∗
n. It is clear that P∗
n is a
subsemigroup of TX0
n
and from [6, Lemma 2.4] it is regular.
For convenience we record the following result due to Vagner [16] (also
to be found in [4, p.254]).
Theorem 1. For each α ∈ Pn and each β ∈ P∗
n, the mappings α 7→ α∗
and β 7→ β|Xn
(the restriction of β to Xn) are mutually inverse isomor-
phisms of Pn onto P∗
n and vice-verse.
Here we make the following important remark which will be effectively
used throughout the next sections.
Remark 1. i) For 1 6 r < m 6 n, an (m, r)-path-cycle [x1, . . . , xm|xr]
in P∗
n corresponds in these isomorphisms to an (m, r)-path-cycle
[x1, . . . , xm|xr] in Pn, while an m-path [x1, . . . , xm|xm] in P∗
n corresponds
either to an m-path [x1, . . . , xm|xm] in Pn if xm 6= 0, or to an (m−1)-chain
[x1, . . . , xm−1] in Pn if xm = 0.
ii) A set of elements in Pn generates Pn if and only if its image under
the isomorphisms generates P∗
n and vice-verse.
3. Generating sets
In this section we identify many generating sets of path-cycles for the
semigroup Pn \ Sn. First, we start by generating Pn using path-cycles.
Theorem 2. Each element of Pn is expressible as a product of path-cycles
in Pn.
Proof. Let α ∈ Pn. The associated map α∗ ∈ P∗
n is expressible as a
product α∗ = α1 · · · αP of path-cycles in TX0
n
using the algorithm described
in [2]. Since 0α∗ = 0, the algorithm ensures that 0αi = 0 for all i. Hence,
αi = δ∗
i for some path-cycle δi in Pn. Therefore, by the isomorphism
α = δ1 · · · δp.
As in [2], the integer p is called the path-cycle rank of α and is denoted
by pcr(α). By [2, Theorem 2], we have that pcr(α∗) = def(α∗) + cycl(α∗),
where def(α∗) = |X0
n\im(α∗)|, the defect of α∗ and cycl(α∗) is the number
of cycles in the decomposition. It has also been observed in [6, Lemma
2.2 & 2.3] that cycl(α∗) = cycl(α) and def(α∗) = def(α) for all α ∈ Pn.
Thus, we have the following observation.
240 Generators and ranks in Pn
Lemma 1. Let α ∈ Pn. Then pcr(α) = def(α) + cycl(α).
Next, we have
Theorem 3. For each α ∈ Pn \ Sn, there exists proper path-cycles
γ1, . . . , γk in Pn \ Sn such that α = γ1 · · · γk.
Proof. Let α ∈ Pn\Sn. By [2, Theorem 4], the associated map α∗ ∈ P∗
n\S∗
n
is expressible as a product α∗ = β1 · · · βk of proper path-cycles in TX0
n
and
since 0α∗ = 0, the method of factorisation ensures that each of the proper
path-cycles βi is in P∗
n \ S∗
n. Hence, by the isomorphism, α = γ1 · · · γk,
where for each i, γ∗
i = βi and each γi is a path-cycle in Pn \ Sn. It is also
clear that each γi is a proper path-cycle.
Theorem 4. The set of all 2-paths and 1-chains in Pn \ Sn together
generates Pn \ Sn.
Proof. By [2, Theorem 5], each element of P∗
n \ S∗
n is a product of 2-paths
in P∗
n \S∗
n. Thus, the result follows from the Isomorphisms between Pn \Sn
and P∗
n \ S∗
n, and Remark 1.
Theorem 5. For each m ∈ {2, . . . , n}, the semigroup Pn \ Sn can be
generated by path-cycles of size m or m − 1.
Proof. Since, for each m ∈ {2, . . . , n}, the semigroup P∗
n \ S∗
n is generated
by its path-cycles of size m. It remains to show that each path-cycle of
size m in P∗
n \ S∗
n corresponds to path-cycles of size m or m − 1 under
the isomorphism. But this is the content of Remark 1.
Theorem 6. Let m ∈ {2, . . . , n}. Then the set of all m-paths and all
m-chains in Pn \ Sn generates Pn \ Sn.
Proof. For any x1, x2 ∈ Xn, we observe that
[x1, x2|x2] = [xm, xm−1, . . . , x3, x1, x2|x2][x1, x3, x4, . . . , xm, x2|x2],
[x1] = [xm, xm−1, . . . , x1][x1, x2, . . . , xm].
Thus the result follows from Theorem 4.
Theorem 7. Let m ∈ {2, . . . , n} and r ∈ {2, . . . , m}. Then the set of all
(m, r)-path-cycles and all m-chains in Pn \ Sn generates Pn \ Sn.
G. U. Garba, A. T. Imam 241
Proof. By Theorem 4 it suffices to show that each 2-path [x, y|y] and each
1-chain [x] in Pn \ Sn can be expressed as a product of (m, r)-path-cycles
and m-chains Pn \ Sn respectively. But, as in [3, Theorem 5], we have
[x, y|y] = [x1, x2, . . . , xm|xr][xr−1, xr−2, . . . , x1, xm, xm−1, . . . , xr|xm]
where {x1, x2, . . . , xm} ⊆ Xn, xr−1 = x and xm = y. Also, as in Theo-
rem 6,
[x] = [xm, xm−1, . . . , x1][x1, x2, . . . , xm]
where x1 = x.
Remark 2. Each 1-chain [x] in Pn \ Sn can be expressed as a product
of 2 k-paths, for each k ∈ {2, . . . , n}, simply by choosing k − 1 distinct
points x2, x3, . . . , xk ∈ Xn \ {x} and observing that
[x] = [xk, xk−1, . . . , x][x, x2, . . . , xk].
Thus, for any fixed k, m ∈ {2, . . . , n} and r ∈ {2, . . . , m}, the set of all
(m, r)-path-cycles and all k-chains in Pn \ Sn generates Pn \ Sn.
4. Rank properties
For any fixed m and r such that 2 6 r 6 m 6 n, we define the (m, r)-
rank of Pn \ Sn, denoted by rankm,r(Pn \ Sn), to be the cardinality of a
smallest generating set for Pn \ Sn consisting solely of (m, r)-path-cycles
and (m − 1)-chains. In the light of Remarks 1 and 2, the corresponding
(m, r)-rank of P∗
n \ S∗
n, denoted by rankm,r(P∗
n \ S∗
n), is define to be the
cardinality of a smallest generating set for P∗
n\S∗
n consisting solely of (m, r)-
path-cycles and m-paths. In this section, we show that rankm,r(Pn \ Sn)
is equal to n(n + 1)/2. Since rankm,r(Pn \ Sn) is at least as large as
rank(Pn \ Sn), it is sufficient to prove that rankm,r(Pn \ Sn) 6 n(n + 1)/2.
A digraph Γ with n vertices is called complete if, for all i 6= j in the set
of vertices, either i → j or j → i is an edge. It is called strongly connected
if, for any two vertices i and j, there is a path from i to j. A vertex i in
a digraph is called a sink if, for all vertices j, j → i is an edge and i → j
is not an edge.
In the semigroup P∗
n, idempotents of defect 1 are 2-paths of type
[i, j|j] where i, j ∈ X0
n and 0 6= i 6= j. There are n2 such 2-paths in P∗
n.
To each set I∗ of 2-paths in P∗
n we associate a digraph △(I∗) with n + 1
242 Generators and ranks in Pn
vertices, in which i → j is a directed edge if and only if [i, j|j] ∈ I∗. First,
we prove the following.
Theorem 8. A set I∗, of 2-paths in P∗
n \ S∗
n (n > 3), is a generating set
for P∗
n \ S∗
n if and only if 0 is a sink in △(I∗) and the digraph △(I∗) − 0
is strongly connected and complete.
Proof. Suppose that I∗ is a set of 2-paths in P∗
n \S∗
n that generates P∗
n \S∗
n.
First, we observe that, for all i = 1, . . . , n, the 2-paths [0, i|i] cannot be in
I∗ since [0, i|i] /∈ P∗
n \ S∗
n. Thus, for all i = 1, . . . , n, 0 → i is not an edge
in △(I∗). Therefore, degout(0) = 0. Also, by Remark 1, the image set I of
I∗ (under the isomorphisms in Theorem 1) is a generating set for Pn \ Sn,
consisting of 2-paths and 1-chains. Since each 2-path and each 1-chain is
an idempotents of defect 1, by [10, Lemma 1], we must have [i] ∈ I, for
all i = 1, . . . , n. Thus, again by Remark 1, [i, 0|0] ∈ I∗ for all i = 1, . . . , n
and so, i → 0 is an edge in △(I∗) for all i = 1, . . . , n. Therefore 0 is a
sink in △(I∗).
Now, we show that △(I∗) − 0 is strongly connected and complete. It
is not difficult to observe that the image set I \ {[i] : i = 1, . . . , n} of
I∗ \ {[i, 0|0] : i = 1, . . . , n} (under the isomorphisms in Theorem 1) is a
generating set for the semigroup Tn\Sn, of all singular full transformations
of Xn. Thus, by Howie (1078, Theorem 1), △(I \ {[i] : i = 1, . . . , n}) =
△(I∗ \ {[i, 0|0] : i = 1, . . . , n}) = △(I∗) − 0 must be strongly connected
and complete.
Conversely, suppose that 0 is a sink in △(I∗) and that the digraph
△(I∗) − 0 is strongly connected and complete. Observe that each map
α∗ ∈ P∗
n \ S∗
n can be expressed as
α = [i1, 0|0][i2, 0|0] · · · [im, 0|0]α1,
where i1, i2, . . . , im ∈ Xn are non-zero pre-images of 0 under α∗, and α1
is a map in P∗
n defined by
xα1 =
{
x if x ∈ {0, i1, . . . , im},
xα if x /∈ {0, i1, . . . , im}.
Now, since iα1 = 0 if and only if i = 0, it is clear that for any
β1, β2, . . . , βk ∈ I∗,
α1 = β1β2 · · · βk if and only if α1|Xn
= β1|Xn
β2|Xn
· · · βk|Xn
. (1)
G. U. Garba, A. T. Imam 243
But, since △(I∗) − 0 is strongly connected and complete, it follows from
[8, Lemma 1] that I \ {[i] : i = 1, 2, . . . , n} is a generating set for Tn \ Sn.
Thus, by (2) and the isomorphisms, α1 is a product of element in I∗ and
so α is generated by I∗.
Next, we make use of the following result from [6, Theorem 4.1].
Theorem 9. For n > 3, rank2,2(P∗
n \ S∗
n) = n(n + 1)/2.
It follows from Theorems 8 and 9 that a digraph associated with a
minimal generating set of 2-paths in P∗
n \ S∗
n is complete and contains
n(n + 1)/2 edges. Consequently, the underlying (undirected) graph of
such a generating set is, upto isomorphism, the complete graph K∗
n with
vertices 0, 1, . . . , n.
The following definition is from [3].
Definition 1. Let G be a graph with vertex set V (G) and edge set
E(G). If |E(G)| is even, let A and B be disjoint subsets of E(G) such
that |A| = |B| = |E(G)|/2; the triple (A, B, ϕ) is called a pairing of G if
ϕ : A → B is a bijection such that, for each e ∈ A, e and ϕ(e) have no
vertices in common. If |E(G)| is odd, a pairing of G is defined to be a
pairing of G − e, for some e ∈ E(G).
From [3, Lemma 3] we deduce the following.
Lemma 2. For all n > 3, there exists a pairing of K∗
n.
Proof. For each n > 3, form a pairing (A, B, ϕ) of the complete graph
Kn+1 on the vertex set {1, 2, . . . , n + 1} using the construction described
in [3, Lemma 3]. In each of the disjoint subsets A, B of E(Kn+1) replace
each edge (i, j) by (i, j)∗ = (i − 1, j − 1) to obtain subsets A∗, B∗ of
E(K∗
n). Then (A∗, B∗, ϕ∗), where ϕ∗(i − 1, j − 1) = (ϕ(i, j))∗, is a pairing
of K∗
n.
Before we prove our next theorem stating that rankm,r(P∗
n \ S∗
n) =
n(n+1)
2 , it is convenient to deal with two particular cases.
Lemma 3. For each n > 3 and each 2 6 m 6 n,
rankm,2(P∗
n \ S∗
n) =
n(n + 1)
2
.
244 Generators and ranks in Pn
Proof. From Theorem 9, we know that the result holds when m = 2. Let I∗
be a generating set for P∗
n \S∗
n consisting of 2-paths with |I∗| = n(n+1)/2.
Them, from Theorem 8, [i, 0|0] ∈ I∗, for all i = 1, 2, . . . , n. If n is even, then
we form n/2 distinct pairs of {[i, 0|0] : i = 1, 2, . . . , n} and corresponding
to each pair [i, 0|0] ↔ [j, 0|0] (with i 6= j) define m-paths
α = [j, x2, x3, . . . , xm−2, i, 0|0] , (2)
β = [i, xm−2, xm−3, . . . , x2, j, 0|0] , (3)
where the m − 3 elements x2, x3, . . . , xm−2 are distinct elements in Xn \
{i, j}. Then αβ = [i, 0|0] and βα = [j, 0|0]. For each [i, j|j] ∈ I∗ \ {[i, 0|0] :
i = 1, 2, . . . , n} we associate an (m, 2)-path-cycle
αij = [i, x2, x3, . . . , xm−1, j|x2] . (4)
Then αm−1
ij = [i, j|j]. Thus, in equalities (2), (3) and (4), we have found
n(n + 1)/2 (m, 2)-path-cycles and m-paths that generate elements in I∗.
Now, if n is odd, then we form (n − 1)/2 distinct pairs of {[i, 0|0] : i =
1, 2, . . . , n − 1} and corresponding to each pair define m-paths α and β
as in equalities (2) and (3) respectively. For the 2-path [n, 0|0], we choose
a 2-path [k, l|l] ∈ I∗ \ {[i, 0|0] : i = 1, 2, . . . , n} and define m-paths
γ = [k, x2, x3, . . . , xm−2, n, 0|0] , (5)
δ = [n, xm−2, xm−3, . . . , x2, k, l|l] . (6)
Then, γδ = [n, 0|0] and δγ = [k, l|l]. Lastly, for each [i, j|j] ∈ I∗ \
{[k, l|l], [i, 0|0] : i = 1, 2, . . . , n} we associate an (m, 2)-path-cycle αij
given in equality (4). Thus, again, in equalities (2-6), we found n(n + 1)/2
(m, 2)-path-cycles and m-paths that generate elements in I∗.
Lemma 4. rank3,3(P∗
3 \ S∗
3 ) = 6.
Proof. From Theorems 8 and 9, we know that
I∗ = {[1, 0|0], [2, 0|0], [3, 0|0], [1, 3|3], [2, 1|1], [3, 2|2]}
is a minimal generating set for P∗
3 \ S∗
3 . Define (3, 3)-path-cycles as α1 =
[2, 1, 0|0], α2 = [3, 2, 0|0], α3 = [1, 3, 0|0], β1 = [1, 2, 3|3], β2 = [2, 3, 1|1] and
β3 = [3, 1, 2|2]. Then the set {α1, α2, α3, β1, β2, β3} is a minimal generating
set for P∗
3 \ S∗
3 , since α1β1 = [1, 0|0], α2β2 = [2, 0|0], α3β3 = [3, 0|0],
β2β3β1 = [1, 3|3], β3β1β2 = [2, 1|1] and β1β2β3 = [3, 2|2].
G. U. Garba, A. T. Imam 245
Theorem 10. For each n > 3 and each 2 6 r 6 m 6 n,
rankm,r(P∗
n \ S∗
n) =
n(n + 1)
2
.
Proof. By virtue of Lemmas 3 and 4, we only need to consider the case
when n > 4 and r > 3. Thus, suppose that n > 4 and 3 6 r 6 m 6 n. Let
P{[1, n|n], [1, n − 1|n − 1], [m − r + 2, n|n]}
and
Q = {[n, 1|1], [n − 1, 1|1], [n, m − r + 2|m − r + 2]}.
Then define
I∗ = {[i, 0|0] : 1 6 i 6 n} ∪ ({[i, j|j] : 1 6 i < j 6 n} \ P ) ∪ Q.
Since |P | = |Q| = 3, it is clear that
|I∗| = n + |{[i, j|j] : 1 6 i < j 6 n}| = n +
(
n
2
)
=
n(n + 1)
2
,
and that 0 is a sink in the associated digraph △(I∗). Also, observe that,
when m − r + 2 6= n − 1, the digraph △(I∗) − 0 has a Hamiltonian cycle
1 → 2 → · · · → n − 1 → n → 1
and, when m − r + 2 = n − 1, the digraph △(I∗) − 0 has a Hamiltonian
cycle
n → n − 1 → 1 → 2 → · · · → n − 3 → n − 2 → n.
Thus in both cases the digraph △(I∗) − 0 is strongly connected. It is easy
to see that the digraph is complete, and so, by Theorem 8, △(I∗) is a
generating set for P∗
n \ S∗
n.
Suppose that |I∗| is even. By Lemma 2, we can pair elements of I∗ in
such a way that
[i, j|j] ↔ [k, l|l] =⇒ {i, j} ∩ {k, l} = ∅. (7)
There are two cases: (i) r = m; (ii) 3 6 r 6 m − 1. In case (i), for each
pair of type (7), let
α = [i, x2, x3, . . . , xm−2, k, l|l] (8)
246 Generators and ranks in Pn
and
β = [k, xm−2, xm−3, . . . , x2, i, j|j] , (9)
where the m − 3 elements x2, x3, . . . , xm−2 are fixed distinct elements of
∈ Xn \ {i, j, k, l}. Then
αβ = [k, l|l] and βα = [i, j|j],
and so, in equalities (8) and (9), we have found n(n+1)
2 m-paths that
generate P∗
n \ S∗
n.
In case (ii), where 3 6 r 6 m − 1, if both j 6= 0 and l 6= 0 hold, we
define, for each pair of type (7),
γ =
[i, k, j, x4, . . . , xm−1, l|j] if r = 3
[i, x2, . . . , xm−3, k, j, l|j] if r = m − 1
[i, x2, . . . , xr−2, k, j, xr+1, . . . , xm−1, l|j] if 3 < r < m − 1
(10)
and
δ =
[k, i, l, xm−1, . . . , x4, j|l] if r = 3
[k, xm−3, . . . , x2, i, l, j|l] if r = m − 1
[k, xr−2, . . . , x2, i, l, xm−1, . . . , xr+1, j|l] if 3 < r < m − 1,
(11)
where the m − 4 elements x2, . . . , xr−2, xr+1, . . . , xm−1 are fixed distinct
elements of Xn \ {i, j, k, l}. Then, in all the situations,
γδ = [k, l|l] and δγ = [i, j|j].
And so, we have found n(n+1)
2 (m, r)-path-cycles and/or m-paths that
generate P∗
n \ S∗
n.
So far we have dealt with the case where |I∗| is even. Suppose now
that |I∗| is odd. By Lemma 2, we have a pairing of the elements of
J = I∗ \ {[n, 1|1]}. By the above argument we can ensure that, for all
3 6 r 6 m, all elements of J are products of (m, r)-path-cycles and
m-paths of the forms (8) and (9), or (10) and (11). In particular with
those generators, we obtain ξ = [n, m − r + 2|m − r + 2]. We now define
η =
{
[2, 3, . . . , m − 1, 1, n|n] if r = m
[m−r+2, m−r+3, . . . , m−1, 1, 2, . . . , m−r+1, n|2] if r < m.
G. U. Garba, A. T. Imam 247
Then
(ηξ)m−1 = [n, 2, 3, . . . , m − 1, 1|2]m−1 = [n, 1|1].
The (m, r)-path-cycle η (if r < m) or m-path η (if r = m) does not appear
in the list of elements (8), (9), (10) and (11); for otherwise we would have
found a generating set with fewer than n(n+1)
2 elements. Hence, adding
η to the generating elements already described gives a generating set
consisting of n(n+1)
2 (m, r)-path-cycles and m-paths.
Now, using Theorem 10 and Remark 1, we have proved the next
theorem.
Theorem 11. For each n > 3 and each 2 6 r 6 m 6 n,
rankm,r(Pn \ Sn) =
n(n + 1)
2
.
References
[1] Andre, J. M. (2004). Semigroups that contain all singular transformations. Semi-
group Forum 68:304-307.
[2] Ayik, G., Ayik, H., Howie, H. M. (2005). On factorisations and generators in
transformations semigroups. Semigroup Forum 70(2):225-237.
[3] Ayik, G., Ayik, H., Ünlü, Y., Howie, H. M. (2008). Rank properties of the semigroup
of singular transformations on a finite set. Communications in Algebra 36:2581-
2587.
[4] Clifford, A. H., Preston, G. B. (1967). The Algebraic Theory of Semigroups,
Mathematical Surveys of the American Mathematical Society, Vol. 2, Providence,
R. L.
[5] Evseev, A. E., Podran, N. E. (1970). Semigroup of transformations of a finite set
generated by idempotents with given projection characteristics. Izv. Vyssh. Zaved
Mat. 12(103):30-36; translated in Amer. Math. Soc. Transl. (1988) 139(2):67-76.
[6] Garba, G. U. (1990). Idempotents in partial transformation semigroup. Proc. Roy.
Soc. Edinburgh 116A:359-366.
[7] Howie, J. M. (1966). The subsemigroup generated by the idempotents of a full
transformation semigroup. J. London Math. Soc. 41:707-716.
[8] Howie, J. M. (1978). Idempotent generators in finite full transformation semigroups.
Proc. Roy. Soc. Edinburgh 81A:317-323.
[9] Howie, J. M. (1980). Products of idempotents in a finite full transformation
semigroup. Proc. Roy. Soc. Edinburgh 86A:243-254.
[10] Howie, J. M., McFadden, R. B. (1990). Idempotent rank in finite full transformation
semigroups. Proc. Roy. Soc. Edinburgh 116A:161-167.
[11] Howie, J. M., Lusk, E. L., McFadden, R. B. (1990). Combinatorial results relating
to products of idempotents in finite full transformation semigroups. Proc. Roy.
Soc. Edinburgh 115A:289-299.
248 Generators and ranks in Pn
[12] Howie, J. M., Robertson, R. B., Schein, B. M. (1988). A combinatorial property
of finite full transformation semigroups. Proc. Roy. Soc. Edinburgh 109A:319-328.
[13] Kearnes, K. A., Szendrei, A., Wood, J. (2001). Generating singular transformations.
Semigroup Forum 63:441-448.
[14] Lipscomb, S. (1996). Symmetric Inverse Semigroups, Mathematical Surveys of the
American Mathematical Society, Vol. 46, Providence, R. L.
[15] Saito, T. (1989). Products of idempotents in finite full transformation semigroups.
Semigroup forum 39:295-309.
[16] Vagner, V. V. (1956). Representations of ordered semigroups. Mat. Sb. (N.S.)
38:203-240; translated in Amer. Math. Soc. Transl. (1964) 36(2):295-336.
Contact information
G. U. Garba,
A. T. Imam
Department of Mathematics,
Ahmadu Bello University, Zaria-Nigeria
E-Mail(s): gugarba@yahoo.com,
atimam@abu.edu.ng
Received by the editors: 20.12.2015
and in final form 03.04.2016.
|