All maximal congruences on an inverse semigroup of fence-preserving transformations
We study the inverse semigroup of all partial injections on an \(n\)-element set \(\{1,...,n\}\), which preserve the zig-zag order \(1\prec 2\succ 3\prec 4\succ \cdots n\) and the parity for some positive integer \(n\). We characterize all maximal congruences on this inverse semigroup, which are ent...
Gespeichert in:
| Datum: | 2026 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Lugansk National Taras Shevchenko University
2026
|
| Schlagworte: | |
| Online Zugang: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2469 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Algebra and Discrete Mathematics |
| Завантажити файл: |  |
Institution
Algebra and Discrete Mathematics| _version_ | 1870196969461252096 |
|---|---|
| author | Chaichompoo, Utsithon Koppitz, Jörg Mati, Yananan |
| author_facet | Chaichompoo, Utsithon Koppitz, Jörg Mati, Yananan |
| author_institution_txt_mv | [
{
"author": "Utsithon Chaichompoo",
"institution": null
},
{
"author": "Jörg Koppitz",
"institution": null
},
{
"author": "Yananan Mati",
"institution": null
}
] |
| author_sort | Chaichompoo, Utsithon |
| baseUrl_str | https://admjournal.luguniv.edu.ua/index.php/adm/oai |
| collection | OJS |
| datestamp_date | 2026-07-08T07:55:33Z |
| description | We study the inverse semigroup of all partial injections on an \(n\)-element set \(\{1,...,n\}\), which preserve the zig-zag order \(1\prec 2\succ 3\prec 4\succ \cdots n\) and the parity for some positive integer \(n\). We characterize all maximal congruences on this inverse semigroup, which are entirely congruences of index two. |
| doi_str_mv | 10.12958/adm2469 |
| first_indexed | 2026-07-09T01:00:16Z |
| format | Article |
| fulltext |
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 41 (2026). Number 2, pp. 181–200
DOI:10.12958/adm2469
All maximal congruences on an inverse
semigroup of fence-preserving transformations
Utsithon Chaichompoo, Jörg Koppitz,
and Yananan Mati
Communicated by A. Zhuchok
Abstract. We study the inverse semigroup of all partial
injections on an n-element set {1, ..., n}, which preserve the zig-zag
order 1 ≺ 2 ≻ 3 ≺ 4 ≻ · · ·n and the parity for some positive
integer n. We characterize all maximal congruences on this inverse
semigroup, which are entirely congruences of index two.
Introduction
For n ∈ N, let n = {1, 2, . . . , n} be a finite set with n elements and let
F = (n,≺) be a fence, also called zig-zag poset, i.e. a partially ordered
set, in which the order relation ≺ forms a path with alternating orienta-
tion:
1 ≺ 2 ≻ 3 ≺ 4 ≻ · · ·n or 1 ≻ 2 ≺ 3 ≻ 4 ≺ · · ·n.
Each element in F is either maximal or minimal. The fence F is called
up-fence (respectively, down-fence) if 1 ≺ 2 (respectively, 1 ≻ 2). In this
paper, we consider (without loss of generality) an up-fence (see Figure 1).
For a set A ⊆ n, a mapping α : A → n is called partial transformation
on n. The set A is called domain of α (in symbols: A = dom(α)) and
im(α) = {xα : x ∈ dom(α)} is the image (range) of α. The cardinality of
im(α) is called the rank of α, denoted by rank(α) = |im(α)|. For A ⊆ n,
2020 Mathematics Subject Classification: 20M20, 20M05.
Key words and phrases: partial injection, inverse semigroup, zig-zag order,
maximal congruence.
https://doi.org/10.12958/adm2469
182 Congruences on fence-preserving transformations
1
2
3
4
5
· · · n
Figure 1: Up fence
we denote by idA the identity mapping on A. Clearly, if A = n, then
idA = id, the identity mapping on n. The empty transformation will be
denoted by ϕ, i.e. dom(ϕ) = ∅. The set of all partial transformations on
n forms a monoid, denoted by PT n with the identity mapping id and
the zero ϕ (with respect of the composition of mappings). This monoid
is well studied, see for example [1–4].
An α ∈ PT n is called fence-preserving if for all x, y ∈ dom(α) the
following implication holds: x ≺ y implies xα ≺ yα. The set of all
fence-preserving partial (full) transformations on n forms a submonoid
of PT n, denoted by PT Fn (T Fn). The monoid T Fn was first
studied by Currie and Visentin [5] in 1991 as well as by Rutkowski [6] in
1992. The main results of theses papers are concerning the cardinality
of T Fn for even as well as odd n, by different techniques. In the last 10
years, the monoid PT Fn and particular submonoids of PT Fn were
studied, see for example [7–11,16].
The set of all injective partial transformations on n forms a sub-
monoid of PT n, which is denoted by In, the symmetric inverse semi-
group. A semigroup S is called inverse if for all a ∈ S, there is unique
a−1 ∈ S such that aa−1a = a and a−1aa−1 = a−1. The set
I Fn = {α ∈ PT Fn ∩ In : α−1 ∈ PT Fn}
forms a submonoid of In, which contains all regular elements of PT Fn.
In particular, I Fn is an inverse semigroup. The Green’s relations in
I Fn are determined by Dimitrova and Koppitz in [9]. Moreover, the
authors show that I Fn is generated by its transformations with rank
≥ n−2, whenever n is even. For the even case, a generating set of minimal
size is determined in [9], which is unique. Recall that the minimal size of
a generating set of a semigroup S is called the rank of S and is denoted by
rank(S). In particular, rank(I Fn) = n+1 (if n is even). In the case n
is odd, the situation is quite more complex. The rank of I Fn, whenever
n is odd, is determined by Fernandes, Koppitz, and Musunthia in [11].
U. Chaichompoo, J. Koppitz, Y. Mati 183
Further, let < be the canonical order on n. A transformation α ∈
PT n is called order-preserving if for all x, y ∈ dom(α) the following im-
plication holds: x < y implies xα ≤ yα. Let OPT n denote the set of all
order-preserving partial transformations on n. The set I OF par
n = {α ∈
OPT n ∩ I Fn : x and xα have the same parity for all x ∈ dom(α)}
forms a submonoid of I Fn and is an inverse semigroup. In [7], Sa-
reeto and Koppitz characterize the elements in I OF par
n and show that
rank(I OF par
n ) = 3n − 6. The same authors give a presentation for
I OF par
n [7]. In [8], the Green’s relations on I OF par
n are described. In
the same paper, Koppitz and Sareeto characterize the ideals of I OF par
n
and their maximal subsemigroups.
In the present paper, we consider another submonoid of I Fn, namely
the monoid I F par
n ={α ∈ I Fn : x and xα have the same parity for all
x ∈ dom(α)}. In fact, any α∈ I F par
n is a partial injection, which maps
any (maximal) consecutive chain I of dom(α) to a (maximal) consecutive
chain of n (under the canonical order <) such that the maximal element
of I, denoted by b, and bα have the same parity.
The aim of the present paper is the study of the congruences on
I F par
n . If σ is a congruence on a semigroup S, then we shall denote
by S/σ the partition of S induced by σ (as equivalence relation), i.e.
S/σ= {[a]σ : a ∈ S}, and [a]σ is the σ-class containing the element a.
The cardinality of S/σ is called the index of σ. A non-universal con-
gruence σ on S, i.e. σ ̸= S × S, is called maximal if the following
implication holds: if ρ is a non-universal congruence on S with σ ⊆ ρ,
then σ = ρ. The importance of the study of (maximal) congruences on
semigroups was shown by Howie [13]. In particular, he has shown that a
congruence-free semigroup is a simple semigroup if it has at least three
elements but no zero element. In [12], for certain semigroups S of num-
bers and of transformations, Sanwong and Sullivan describe all maximal
congruences on S. In particular, they describe the maximal congruences
on the symmetric inverse semigroup In. Maximal congruences on several
other semigroups of transformations were determined in the last twenty
years, see for example [14,15,17].
In the present paper, we determine the maximal congruences on
I F par
n . It will turn out that all maximal congruences on I F par
n have
index two.
184 Congruences on fence-preserving transformations
1. A class of subsets of n
We define a class A of subsets of n, for which we will show that each set
in A defines a maximal congruence on I F par
n .
Definition 1. Let A be the set of all non-empty subsets A of n, which
satisfy the following condition: For all x ∈ {0, 1, . . . , n − 3} \ A and all
k ∈ {2, . . . ,
⌈n
2
⌉
−
⌊x
2
⌋
} with x+ 2k /∈ A, we have
x+ r ∈ A if and only if x+ 2k − r ∈ A
for all r ∈ {1, . . . , k − 1}.
In this section, we prove several properties of the elements in A .
In the remaining part of this section, we will use a short version of the
application of Definition 1 to any A ∈ A . If we write a, b /∈ A and c ∈ A
imply d ∈ A, then we mean that there is x ∈ n such that a+ x = c ∈ A
(a− x = c ∈ A, respectively) implies that d = b− x ∈ A (d = b+ x ∈ A,
respectively), where b− a (a− b, respectively) is an even positive integer
and |a− b|≥ 4. A dual interpretation has the phrase a, b ∈ A and c /∈ A
imply d /∈ A.
Proposition 2. Let A ∈ A . Then {1, 2}∩A ̸= ∅ and {n−1, n}∩A ̸= ∅.
Proof. We will show that {1, 2}∩A ̸= ∅. The fact that {n−1, n}∩A ̸= ∅
can be shown dually (if n is odd) and by similar arguments (if n is
even), respectively. Assume that {1, 2} ∩ A = ∅. Let k1 =
⌈n
2
⌉
and
n̂ =
{
0 if n is odd,
1 if n is even.
Clearly, n̂, n̂+1 /∈ A. If n is even, then n̂+2k1 =
1 + n. If n is odd, then n̂ + 2k1 = 0 + n + 1. So, n̂ + 2k1 = 1 + n /∈ A.
Then n̂ + 1 /∈ A implies n = (n + 1) − 1 = n̂ + 2k1 − 1 /∈ A. Let
ñ =
{
1 if n is odd,
0 if n is even
and let k2 =
⌈n
2
⌉
−
{
1 if n is odd,
0 if n is even.
Clearly,
ñ, ñ+ 1 /∈ A. If n is odd, then ñ+ 2k2 = 1+ n+ 1− 2 = n. If n is even,
then ñ+2k2 = 0+n. So, ñ+2k2 = n /∈ A. Therefore, ñ+1 /∈ A implies
n − 1 = ñ + 2k2 − 1 = n − 1 /∈ A. Let k3 = k1 − 1 =
⌈n
2
⌉
− 1. Then
n̂ + 2k3 = n̂ + 2k1 − 2 = n + 1 − 2 = n − 1 /∈ A. So, n̂ + 1 /∈ A implies
n− 2 = (n− 1)− 1 = n̂+ 2k3 − 1 /∈ A. If we continue in that way, then
we obtain
zi + 2ki − 1 = n− i+ 1 /∈ A for 1 ≤ i ≤ 2
⌈n
2
⌉
− 3
U. Chaichompoo, J. Koppitz, Y. Mati 185
with zi =
{
n̂ if i is odd,
ñ if i is even
and ki = −
⌊
i− 1
2
⌋
+
{
k1 if i is odd,
k2 if i is even.
It is easy to verify that ki ∈ {2, . . . ,
⌈n
2
⌉
} for 1 ≤ i ≤ 2
⌈n
2
⌉
− 3. This
shows that A = ∅, a contradiction.
As usually, we denote by 2N (2N−1) the set of all even (odd) positive
integers.
Proposition 3. Let A ∈A such that 1 /∈ A and 2 ∈ A. Then 2N∩n ⊆ A.
Proof. Assume that there is c ∈ (2N ∩ n) \ A. Suppose that n is even.
Then 1 + 2
⌈n
2
⌉
= 1 + n /∈ A. So 1 + 1 = 2 ∈ A implies n = 1 +
2
⌈n
2
⌉
− 1 ∈ A. Since c > 2, there is k ∈ {2, . . . ,
⌈n
2
⌉
} with c = 2k. So
0 + 1 = 1 /∈ A implies c − 1 = 0 + 2k − 1 /∈ A. Since c < n, there is
l ∈ {2, . . . ,
⌈n
2
⌉
−
⌊
c− 1
2
⌋
} such that (c − 1) + 2l = n + 1 /∈ A. Then
(c − 1) + 2l − 1 = n ∈ A implies c = (c − 1) + 1 ∈ A, a contradiction.
Suppose now that n is odd. Then 0+2
⌈
n+ 1
2
⌉
= n+1 /∈ A and 0+1 =
1 /∈ A imply n = 2
⌈
n+ 1
2
⌉
− 1 /∈ A. Moreover, 0 + 2 = 2 ∈ A implies
n− 1 = 2
⌈
n+ 1
2
⌉
− 2 ∈ A. By the same argument as in the even case,
we obtain c−1 /∈ A. Since c < n−1, there is p ∈ {2, . . . ,
⌈n
2
⌉
−
⌊
c− 1
2
⌋
}
such that (c−1)+2p = n /∈ A. Then (c−1)+2p−1 = n−1 ∈ A implies
c = (c− 1) + 1 ∈ A, a contradiction.
If n is odd and n /∈ A, then n − 1 ∈ A (by Proposition 2) and we
obtain that 2N∩n ⊆ A with dual arguments. For convenience, we define
ne =
{
n− 1 if n is odd,
n if n is even
and no =
{
n if n is odd,
n− 1 if n is even.
Proposition 4. Let A ∈ A such that ne /∈ A and no ∈ A. Then
(2N− 1) ∩ n = A.
Proof. If n is even then n /∈ A and n− 1 ∈ A. By dual arguments as in
the proof of Proposition 3, we can show that all odd integers in n belong
to A, i.e. (2N−1)∩n ⊆ A. Suppose now that n is odd. Then n ∈ A and
n−1 /∈ A. It is clear that there is k ∈ {2, . . . ,
⌈n
2
⌉
} such that n+1 = 2k,
186 Congruences on fence-preserving transformations
namely k =
⌈n
2
⌉
. Note that 0, 0 + 2k /∈ A. So, 0 + 1 = 1 ∈ A implies
n = n+1−1 ∈ A. Moreover, 0+2k−2 = n−1 /∈ A implies 2 = 0+2 /∈ A.
If 2 ̸= n− 1, then there is l ∈ {2, . . . ,
⌈n
2
⌉
} such that 0+ 2l = n− 1 /∈ A.
So, 0 + 1 = 1 ∈ A implies n − 2 = (n − 1) − 1 = 0 + 2l − 1 ∈ A and
further, 0 + 2 = 2 /∈ A implies n − 3 = 0 + 2l − 2 /∈ A. If 3 ̸= n − 3,
then 0 + 2k − 3 = n − 2 ∈ A implies 3 = 0 + 3 ∈ A and further,
0+2k−4 = n−3 /∈ A implies 4 = 0+4 /∈ A. Continuing this procedure,
we obtain that (2N− 1) ∩ n = A.
From Propositions 2 and 3 (and the remark after Proposition 3, re-
spectively), we obtain:
Corollary 5. Let A ∈ A such that (n \ A) ∩ 2N ̸= ∅. Then 1 ∈ A (and
n ∈ A, whenever n is odd).
From Propositions 2 and 4, we can conclude:
Corollary 6. Let A ∈ A such that (n\A)∩ (2N−1) ̸= ∅. Then ne ∈ A.
Let us give a note to the cardinality of any A ∈ A .
Proposition 7. Let A ∈ A . Then |A| ≥
⌊n
2
⌋
.
Proof. Assume that |A| <
⌊n
2
⌋
. For i ∈ {1, . . . ,
⌊n
2
⌋
− 1}, we put
Ai = {2i − 1, 2i} and A⌊n
2 ⌋ =
{
{n− 1, n} if n is even,
{n− 2, n− 1, n} if n is odd.
We
observe that n =
⌊n
2 ⌋⋃
i=1
Ai. From |A| <
⌊n
2
⌋
, it follows the existence of an
i ∈ {1, . . . ,
⌊n
2
⌋
} such that Ai ∩A = ∅. We observe that i ̸= 1 by Propo-
sition 2. Moreover, Ai ∩ A = ∅ implies (n \ A) ∩ 2N ̸= ∅. Hence, 1 ∈ A
by Corollary 5. Since i > 1, we get 2i > 2, where 0, 0 + 2i /∈ A. Then
0 + 1 = 1 ∈ A implies 0 + 2i− 1 ∈ A, a contradiction to Ai ∩A = ∅.
Let A ∈ A . Then there are d1, d2, ..., dl ∈ n with d1 < d2 < . . . <
dl and l = |A| such that A = {d1, . . . , dl}. We observe that the set
{d1, d1 + 1, d1 + 2, ..., dl} \A consists entirely of maximal interval of size
one or two.
U. Chaichompoo, J. Koppitz, Y. Mati 187
Proposition 8. Let A = {d1, d2, ..., dl} ∈ A for some l ∈ n, where
d1 < d2 < ... < dl. Then
di+1 − di ≤ 3
for all i ∈ {1, ..., l − 1}.
Proof. Assume there exists j ∈ {1, ..., l − 1} such that dj+1 − dj ≥ 4.
Then dj + 1, dj + 2, dj + 3 /∈ A. If dj ∈ 2N− 1, then dj + 1 ≥ 4 is even,
whenever dj > 1. Then dj ∈ A and 0, dj + 1 /∈ A imply 1 ∈ A, whenever
dj > 1. So, 1 ∈ A. Moreover, 0, dj + 3 /∈ A and 1 ∈ A imply dj + 2 ∈ A,
which is a contradiction. If dj ∈ 2N, then 2 ∈ A since 0, dj + 2 /∈ A and
dj ∈ A. Moreover, we obtain 1 /∈ A since dj + 1 /∈ A. By Corollary 5,
we obtain a contradiction since not all even elements of n are contained
in A.
For a non-empty subset A of n, we define a particular partition.
Definition 9. For ∅ ̸= A ⊆ n, let AS be the set of all subsets
{x, x+ 1, ..., x+ r} (x ∈ n, 0 ≤ r ≤ n− x)
of A such that x− 1 /∈ A and x+ r + 1 /∈ A.
In fact, AS is the set of all maximal intervals (blocks) in the set
A ∈ A . Let X,Y ∈ AS . Then we write X < Y if all elements in X
are less than any element in Y with respect to the natural order of N.
Further, we write X ≺ Y if X < Y and for each Z ∈ AS , the following
implication holds: If X ≤ Z ≤ Y , then X = Z or Y = Z. So, any
∅ ̸= A ⊆ n can be written in the following form:
A = [A1 A2 · · · Ak],
where A1 ≺ A2 ≺ · · · ≺ Ak ∈ AS for some k ∈ n. For convenience, we
define
ai = minAi and bi = maxAi
for all i ∈ {1, ..., k}. In particular, we have a1 ≤ b1 < a2 ≤ b2 < ... <
ak ≤ bk. Moreover, we can say that A has k blocks.
From now on, we consider any A ∈ A in the above form. Using this
notation for A ∈ A , Proposition 8 can be represented as follows.
Let A = [A1 A2 · · · Ak] ∈ A for some k ∈ n. Then for all
i ∈ {1, ..., k − 1}, we have
ai+1 − bi = 2 or ai+1 − bi = 3.
188 Congruences on fence-preserving transformations
Lemma 10. Let A ∈ A such that 1 ∈ A. If there exists x ∈ n such that
x, x+ 1 /∈ A, then x ∈ 2N.
Proof. Let x ∈ n such that x, x+1 /∈ A. Assume that x ∈ 2N− 1. Then
x + 1 ∈ 2N. Since 0, x + 1 /∈ A and 1 ∈ A, we obtain x ∈ A. It is a
contradiction with x /∈ A. Hence x ∈ 2N.
Lemma 11. Let A = [A1 A2 · · · Ak] ∈ A for some k ∈ n. If there
exists x ∈ {1, ..., k − 1} such that ax+1 − bx = 3, then ai+1 − bi = 2 for
all i ∈ {1, ..., k − 1} \ {x}.
Proof. Assume that there exists y ∈ {1, ..., k− 1} \ {x} such that ay+1 −
by = 3. Then 1 ∈ A by Corollary 5. Note that bx + 1, bx + 2, by + 1,
by + 2 /∈ A. By Lemma 10, we obtain bx + 1 ∈ 2N and by + 1 ∈ 2N.
Without loss of generality, we suppose x < y. By bx + 1, by + 1 /∈ A
and (bx + 1) + 1 = bx + 2 /∈ A, we have by = (by + 1) − 1 /∈ A, a
contradiction.
Lemma 12. Let A = [A1 A2 · · · Ak] ∈ A for some k ∈ N. If
|Ax|∈ 2N for some x ∈ {1, ..., k}, then
ai+1 − bi = 2
for all i ∈ {1, ..., k − 1}.
Proof. Assume that there exists y ∈ {1, ..., k−1} such that ay+1−by = 3.
Then by + 1, by + 2 /∈ A implies 1 ∈ A by Corollary 5. Since 1 ∈ A and
by + 1, by + 2 /∈ A, we obtain by + 1 ∈ 2N by Lemma 10 and thus
by + 2 ∈ 2N− 1.
Suppose that ax ∈ 2N. Then bx ∈ 2N − 1. If bx < by + 1, then ax − 1,
by+2 /∈ A and (ax−1)+1 = ax ∈ A imply by+1 = (by+2)−1 ∈ A, which
is a contradiction with by +1 /∈ A. If by +2 < ax, then by +1, bx +1 /∈ A
and (by + 2) − 1 = by + 1 /∈ A imply bx = (bx + 1) − 1 /∈ A, which is a
contradiction with bx ∈ A.
Suppose that ax ∈ 2N − 1. Then bx ∈ 2N. Assume that bx + 2 /∈ A.
Since 0 /∈ A and 1 ∈ A, we get bx + 1 = bx + 2− 1 ∈ A, a contradiction.
Hence bx + 2 ∈ A. If bx < by + 1, then by + 1 ̸= bx + 1 since bx, by + 1 ∈
2N. By bx + 1, by + 2 /∈ A and (bx + 1) + 1 = bx + 2 ∈ A, we have
by + 1 = (by + 2) − 1 ∈ A, which is a contradiction with by + 1 /∈ A. If
by + 2 < ax, then ax > 1 and by + 2 ̸= ax − 1 since ax ∈ 2N − 1 and
by + 1 ∈ 2N. Since by + 1, ax − 1 /∈ A and (by + 1) + 1 = by + 2 /∈ A, we
have ax − 2 = (ax − 1)− 1 /∈ A. Then 0, ax − 1 /∈ A implies 1 /∈ A, which
is a contradiction.
U. Chaichompoo, J. Koppitz, Y. Mati 189
Lemma 13. Let A = [A1 A2 · · · Ak] ∈ A for some k ∈ N and let
i, j ∈ {1, ..., k} such that i ̸= j. If |Ai|, |Aj |∈ 2N− 1, ai and aj have the
same parity, then |Ai|= |Aj |.
Proof. Assume |Ai|̸= |Aj |. Without loss of generality, we suppose that
ai < aj and |Ai|< |Aj |. It is easy to see that ai − 1 and bj + 1 have
the same parity and that ai − 1, bj + 1 /∈ A. Since |Ai|< |Aj |, we have
(bj + 1)− (|Ai|+1) ∈ Aj . Thus bi + 1 = ai − 1 + |Ai|+1 ∈ A, which is a
contradiction with bi + 1 /∈ A. Hence |Ai|= |Aj |.
Lemma 14. Let A = [A1 A2 · · · Ak] ∈ A for some k ∈ N. If
|Ai|∈ 2N− 1 for all i ∈ {1, ..., k}, then there is p ∈ {0, 1, ..., k} such that
(1) ai ∈ 2N− 1 for all 1 ≤ i ≤ p and aj ∈ 2N for all p+ 1 ≤ j ≤ k;
(2) |Ai|= |Aj | for all i, j ∈ {1, ..., p} and |Ai|= |Aj | for all i, j ∈ {p+1,
..., k}.
Proof. First, we will show that there exists p ∈ {0, 1, ..., k} such that
ai ∈ 2N − 1 for all 1 ≤ i ≤ p and aj ∈ 2N for all p + 1 ≤ j ≤ k. If
ai ∈ 2N− 1 for all i ∈ {1, ..., k}, then p = k. If there exists c ∈ {1, ..., k}
such that
ac = min{2N ∩ {ai : i ∈ {1, ..., k}}},
then we claim ai ∈ 2N for all i ≥ c. Assume that there exists x ∈ {1, ..., k}
with x > c such that ax ∈ 2N − 1. We have ac − 2, ac − 1 /∈ A because
bc−1 is odd or ac = 2. Since ac − 2, bx +1 /∈ A, (bx +1)− 1 = bx ∈ A, we
have ac − 1 = (ac − 2)+ 1 ∈ A, which is a contradiction with ac − 1 /∈ A.
Thus p = c− 1. The rest of the proof is given by Lemma 13.
Let us assign, to each l ∈ n ∪ {0}, an element of the set {−1, 0, 1} as
follows: For l ∈ n ∪ {0}, let n(l) =
0 if n is even,
1 if n is odd and l ̸= 0,
−1 if n is odd and l = 0.
Theorem 15. Let A = [A1 A2 · · · Ak] ∈ A for some k ∈ N such that
|Ai|∈ 2N− 1 for all i ∈ {1, ..., k}. Then Aα = A for all α ∈ I F par
n with
A ⊆ domα.
Proof. Let α ∈ I F par
n such that A ⊆ domα. By Lemma 14, we can write
A = [A1 · · · Ap Ap+1 · · · Ap+l] for some p ∈ {0, 1, ..., k} and l = k−p,
where |Ai|= r ∈ 2N− 1 for all 1 ≤ i ≤ p and |Ap+j |= s ∈ 2N− 1 for all
1 ≤ j ≤ l. Then
k∑
i=1
|Ai|= pr+ls. Clearly, since a1 ∈ 2N−1 by Lemma 14,
190 Congruences on fence-preserving transformations
we have a1 = 1. Since ai+1 − bi = 2 for all i ∈ {1, ..., p+ l− 1} \ {p} and
ap+1 − bp = 3, we have
k∑
i=1
|Ai|+p+ l + n(l) = pr + ls+ p+ l + n(l) = n.
For i ∈ {1, ..., p + l}, we define Bi = Aiα. Since α ∈ I F par
n , we have
k∑
i=1
|Bi|=
k∑
i=1
|Ai|= pr + ls. Thus
k∑
i=1
|Bi|+p + l + n(l) = n. We put C =
n \Aα. Then n =
k∑
i=1
|Bi|+ |C|.
Suppose that n is even. If l ̸= 0, then
k⋃
i=p+1
Bi =
{
n, . . . , n −(∣∣∣∣ k⋃
i=p+1
Bi
∣∣∣∣ + l
)}
\ {1 + n − y(s + 1) : 1 ≤ y ≤ l}. Otherwise, it is
easy to verify that |C| ≥ p + l + 1. This provides n =
k∑
i=1
|Bi| + |C| ≥(
k∑
i=1
|Bi|+ p+ l
)
+ 1 = n+ 1, a contradiction. If p ̸= 0, then we obtain
p⋃
i=1
Bi = {1, . . . ,
∣∣∣∣ p⋃
i=1
Bi
∣∣∣∣+p}\{y(r+1) : 1 ≤ y ≤ l} by similar arguments.
Suppose now that n is odd. Since 0, n + 1 /∈ A, we obtain that
1 = 0+1 ∈ A if and only if n = (n+1)− 1 ∈ A. If l ̸= 0, then p = 0, i.e.
l = k, and we have
k⋃
i=1
Bi =
{
n − 1, . . . , n − 1 −
(∣∣∣∣ k⋃
i=1
Bi
∣∣∣∣ + k
)}
\ {1 +
n− y(s+ 1) : 1 ≤ y ≤ k}. Otherwise, it is easy to verify that |C|≥ l+ 2.
This provides n =
k∑
i=1
|Bi|+|C|≥
(
k∑
i=1
|Bi|+p + l + 1
)
+ 1 = n + 1, a
contradiction.
If p ̸= 0, then l = 0, i.e. p = k, and we have
k⋃
i=1
Bi = {1, . . . ,
∣∣∣∣ k⋃
i=1
Bi
∣∣∣∣+
k} \ {y(r + 1) : 1 ≤ y ≤ k}. Otherwise, it is easy to verify that |C| ≥ p.
This provides n =
k∑
i=1
|Bi| + |C| ≥
(
k∑
i=1
|Bi|+ p+ l − 1
)
+ 1 = n + 1, a
contradiction.
Now for any n (even as well as odd), we can calculate:
p⋃
i=1
Bi = {1, . . . ,
∣∣∣∣ p⋃
i=1
Bi
∣∣∣∣+ p} \ {y(r + 1) : 1 ≤ y ≤ p}
= {1, . . . ,
p∑
i=1
|Bi|+p} \ {y(r + 1) : 1 ≤ y ≤ p}
= {1, . . . ,
p∑
i=1
|Ai|+p} \ {y(r + 1) : 1 ≤ y ≤ p}
U. Chaichompoo, J. Koppitz, Y. Mati 191
= {1, . . . ,
∣∣∣∣ p⋃
i=1
Ai
∣∣∣∣+ p} \ {y(r + 1) : 1 ≤ y ≤ p}
=
p⋃
i=1
Ai.
Similarly, we obtain
k⋃
i=p+1
Bi =
{
n− n(l), . . . , n−
(∣∣∣∣ k⋃
i=p+1
Bi
∣∣∣∣+ l + 1−
n(l)
)}
\ {1+n−n(l) − y(s+1) : 1 ≤ y ≤ l} =
k⋃
i=p+1
Ai. Therefore, Aα =
k⋃
i=1
Aiα =
k⋃
i=1
Bi =
p⋃
i=1
Bi∪
k⋃
i=p+1
Bi =
p⋃
i=1
Ai∪
k⋃
i=p+1
Ai =
k⋃
i=1
Ai = A.
Now we consider an A = [A1 · · · Ak] ∈ A such that there is
p ∈ {1, ..., k} with |Ap|∈ 2N.
Lemma 16. Let A = [A1 · · · Ak] ∈ A for some k ∈ N. If there exists
p ∈ {1, ..., k} such that |Ap|∈ 2N, then 1, ne ∈ A.
Proof. Let p ∈ {1, ..., k} such that |Ap|∈ 2N. If A = n, then it is clear
that 1, ne ∈ A. Suppose now that A ⊂ n.
If 1 = ap, then bp + 1 ∈ 2N− 1 and bp + 1 /∈ A. This implies ne ∈ A
by Corollary 6. Hence 1, ne ∈ A.
If n = bp and ap ̸= 1, then ne ∈ Ap ⊆ A and ap − 1 ∈ (n \ A) ∩ 2N.
The latter one implies 1 ∈ A by Corollary 5. Hence 1, ne ∈ A.
If 1, ne /∈ Ap, then ap − 1 ∈ n \ A and bp + 1 ∈ n \ A have different
parity. So, (n \ A) ∩ 2N ̸= ∅ and (n \ A) ∩ 2N − 1 ̸= ∅. This implies
1, ne ∈ A by Corollaries 5 and 6.
Lemma 17. Let A = [A1 · · · Ak] ∈ A for some k ∈ N. If there is
unique p ∈ {1, ..., k} such that |Ap|∈ 2N, then for l = k − p, we have
(1) a1, ..., ap ∈ 2N− 1 and ap+1, ..., ap+l ∈ 2N (if l ̸= 0);
(2) |Ai|= |Aj | for all i, j ∈ {1, ..., p}; |Ai|= |Aj | for all i, j ∈ {p + 1,
..., p+ l}.
Proof. Let p be the unique element in {1, ..., k} such that |Ap|∈ 2N. We
have 1, ne ∈ A by Lemma 16. First, we will show that a1, ..., ap ∈ 2N− 1
and ap+1, ..., ap+l ∈ 2N (if l ̸= 0). Note that |Ai|∈ 2N − 1 for all i ∈
{1, ..., p+ l}\{p} and ai+1− bi = 2 for all i ∈ {1, ..., k−1} by Lemma 12.
Moreover, we have a1 = 1 and ai = ai−1 + |Ai−1|+1 for all 2 ≤ i ≤ p.
Since |Ai−1|+1 is even, we obtain ai ∈ 2N− 1 for all 2 ≤ i ≤ p. If l = 0,
192 Congruences on fence-preserving transformations
then all is shown. Suppose now that l > 0. Since ap+1 = ap + |Ap|+1 is
even, we can show that ap+1, ..., ap+l ∈ 2N as above. Thus, we have (1).
By Lemma 13, we obtain (2). This completes the proof.
If n is odd, then 0 and n + 1 are even and do not belong to A. So,
we can conclude that 1 ∈ A if and only if n ∈ A. Lemma 17 implies
that 1 ∈ A and bk ∈ 2N and thus, n is even, whenever there is unique
p ∈ {1, ..., k} with |Ap|∈ 2N.
Theorem 18. Let n be even and let A = [A1 · · · Ak] ∈ A for some
k ∈ N such that there is unique p ∈ {1, ..., k} with |Ap|∈ 2N. Then
Aα = A for all α ∈ I F par
n with A ⊆ dom(α).
Proof. Let α ∈ I F par
n such that A ⊆ dom(α). By Lemma 17, there are
r ∈ 2N−1 (if p > 1), s ∈ 2N−1 (if p < k), and t ∈ 2N such that |Ai|= r,
for all 1 ≤ i ≤ p − 1, |Ap+j |= s, for all 1 ≤ j ≤ k − p = l, and |Ap|= t.
Then
k∑
i=1
|Ai|= (p − 1)r + ls + t. By ai+1 − bi = 2 for all 1 ≤ i ≤ k − 1
and n = bp, we have
k∑
i=1
|Ai|+p+ l− 1 = (p− 1)r+ ls+ t+ p+ l− 1 = n.
For i ∈ {1, ..., p + l}, we define Bi = Aiα. Since α ∈ I F par
n , then
minBi − 1,maxBi + 1 /∈ Aα for all 1 ≤ i ≤ k and
p+l∑
i=1
|Bi|=
p+l∑
i=1
|Ai|=
(p − 1)r + ls + t. Thus
p+l∑
i=1
|Bi|+p + l − 1 = n. We put C = n \ Aα.
Clearly, we have |C|= p+ l− 1, i.e. n =
p+l∑
i=1
|Bi|+|C|. It is easy to verify
that 1, n ∈ Aα. From 1, n ∈ Aα, |C|= p+l−1, and minBi−1,maxBi+1 ∈
C∪{0, n+1}, we can conclude that
p−1⋃
i=1
Bi ⊆ {k : 1 ≤ k ≤
∣∣∣∣p−1⋃
i=1
Bi
∣∣∣∣+p−1},
p+l⋃
i=p+1
Bi ⊆
{
k : n + 1 −
(∣∣∣∣ p+l⋃
i=p+1
Bi
∣∣∣∣ + l
)
≤ k ≤ n
}
, and Bp = n \
(
{k :
1 ≤ k ≤
∣∣∣∣p−1⋃
i=1
Bi
∣∣∣∣+p−1}∪
{
k : n+1−
(∣∣∣∣ p+l⋃
i=p+1
Bi
∣∣∣∣+ l
)
≤ k ≤ n
})
. Since
each Bi, where 1 ≤ i ≤ k, is a maximal interval in n, we can calculate
that
p−1⋃
i=1
Bi = {k : 1 ≤ k ≤
∣∣∣∣p−1⋃
i=1
Bi
∣∣∣∣+ p− 1} \ {y(r + 1) : 1 ≤ y ≤ p− 1}
= {k : 1 ≤ k ≤
p−1∑
i=1
|Bi|+p− 1} \ {y(r + 1) : 1 ≤ y ≤ p− 1}
U. Chaichompoo, J. Koppitz, Y. Mati 193
= {k : 1 ≤ k ≤
p−1∑
i=1
|Ai|+p− 1} \ {y(r + 1) : 1 ≤ y ≤ p− 1}
= {k : 1 ≤ k ≤
∣∣∣∣p−1⋃
i=1
Ai
∣∣∣∣+ p− 1} \ {y(r + 1) : 1 ≤ y ≤ p− 1}
=
p−1⋃
i=1
Ai.
By the same arguments, one can calculate that Bp = n \
(
{k : 1 ≤ k ≤∣∣∣∣p−1⋃
i=1
Bi
∣∣∣∣ + p − 1} ∪
{
k : n + 1 −
(∣∣∣∣ p+l⋃
i=p+1
Bi
∣∣∣∣ + l
)
≤ k ≤ n
})
= Ap and
p+l⋃
i=p+1
Bi =
{
k : n + 1 −
(∣∣∣∣ p+l⋃
i=p+1
Bi
∣∣∣∣ + l
)
≤ k ≤ n
}
\ {1 + n − y(s + 1) :
1 ≤ y ≤ l} =
p+l⋃
i=p+1
Ai. Therefore, Aα =
p+l⋃
i=1
Aiα =
p+l⋃
i=1
Bi =
p−1⋃
i=1
Bi ∪Bp ∪
p+l⋃
i=p+1
Bi =
p−1⋃
i=1
Ai ∪Ap ∪
p+l⋃
i=p+1
Ai =
p+l⋃
i=1
Ai = A.
Finally, we consider the case that dom(α) has more than one maximal
interval with even size.
Lemma 19. Let A = [A1 A2 · · · Ak] ∈ A for some k ∈ N. If there
exist p, q ∈ {1, ..., k} with p ̸= q such that |Ap|, |Aq|∈ 2N, then either
there are t ∈ 2N− 1 and u ∈ n with 2t = n+1− (k− 2)(u+1) such that
A = n \ {t + lu : 0 ≤ l ≤ k − 2} and n is odd or |Ai|= |Aj |∈ 2N for all
i, j ∈ {1, ..., k}.
Proof. Let p, q ∈ {1, ..., k} with p < q such that |Ap|, |Aq|∈ 2N. Suppose
that there exists r ∈ {1, . . . , k} \ {p, q} such that |Ar| ∈ 2N− 1.
First, we assume that r < p. Without loss of generality, we can
assume that r = p − 1 and there is no p + 1 ≤ i ≤ q − 1 with |Ai|∈ 2N.
Then it is easy to see that ar − 1, bq + 1 /∈ A as well as ap − 1 and bq + 1
have the same parity. If |Aq|< |Ar|, then ar−1+(|Aq|+1)=ar+|Aq| ∈ A.
This implies aq−1 = bq+1−(|Aq|+1) ∈ A, a contradiction. If |Ar|< |Aq|,
then bq + 1 − (|Ar|+1) = bq − |Ar|∈ A. This implies br + 1 = ar − 1 +
(|Ar|−1) ∈ A, a contradiction, too. In the case r > q, we obtain a
contradiction in a dually way.
It is easy to verify that the following case remains: 1 = p < r < q = k.
Since 1 ∈ A, we can conclude that bk ∈ 2N−1. Since (n\A)∩(2N−1) ̸= ∅,
we can conclude that ne ∈ A by Corollary 6. Since bk is odd, we can
194 Congruences on fence-preserving transformations
conclude that n is odd. This shows that A = n \ {t1 < t2 < · · · <
tk−1} for some odd t1, t2, . . . , tk−1 ∈ n \ {1, n}. Assume that |A1|̸= |Ak|.
Without loss of generality, we can assume that |A1| < |Ak|. Then we
have 0 + (|A1| + 1) = b1 + 1 /∈ A and (n + 1) − (|A1| + 1) ∈ Ak ⊂ A
since |A1| < |Ak|. But 0, n + 1 /∈ A and 0 + (|A1| + 1) /∈ A imply
(n + 1) − (|A1| + 1) /∈ A, a contradiction. In the same matter, we can
show that there is u ∈ n with u = |Ai| for i = 2, . . . , k − 1. Hence,
A = n \ {t1 + lu : 0 ≤ l ≤ k − 2} with 2t1 = n+ 1− (k − 2)(u+ 1).
Suppose that |Ai|∈ 2N for all i ∈ {1, ..., k}. Assume that there is
i ∈ {1, . . . , k − 1} with |Ai| ̸= |Ai+1|. Without loss of generality, we can
assume that |Ai| < |Ai+1|. Since |Ai| , |Ai+1| ∈ 2N, we can conclude that
ai and bi+1 have the same parity. So ai − 1 and bi+1 + 1 have the same
parity and do not belong toA. Let c = |Ai|+1. Then ai−1+c = bi+1 /∈ A
and bi+1 + 1− c ∈ Ai+1 ⊂ A since |Ai| < |Ai+1|, a contradiction.
Theorem 20. Let A = [A1 A2 · · · Ak] ∈ A for some k ∈ n such that
there are p, q ∈ {1, ..., k} with p ̸= q and |Ap|, |Aq|∈ 2N. Then Aα = A
for all α ∈ I F par
n with dom(α) ∈ A.
Proof. By Lemma 19, we have to consider two cases. Suppose that n is
odd and there are t ∈ 2N− 1 and u ∈ n with 2t = n+ 1− (k− 2)(u+ 1)
such that A = n \ {t+ lu : 0 ≤ l ≤ k − 2}. We put ti = t+ (i− 1)u for
all 1 ≤ i ≤ k − 1. Then A1 = {1, . . . , t1 − 1}, Ak = {tk−1 + 1, . . . , n},
and Ai = {ti−1 +1, . . . , ti − 1} for i = 2, . . . , k− 1 (whenever k ≥ 3). So,
A∩ 2N =n∩ 2N and thus Aα∩ 2N =n∩ 2N. Since 1, n ∈ A and both are
odd, it is easy to verify that either A1α = A1 and Akα = Ak or A1α = Ak
and Akα = A1. Therefore,
k−1⋃
i=2
Aiα as a subset of {t1 + 1, . . . , tk−1 − 1},
consisting entirely of maximal intervals of length u. This shows that
k−1⋃
i=2
Aiα = {t1 + 1, . . . , tk−1 − 1} \ {t1 + lu : l = 1, . . . , k − 3} =
k−1⋃
i=2
Ai.
Consequently, Aα = A.
Suppose now that |Ai|= |Aj |∈ 2N for all i, j ∈ {1, ..., k}. We observe
that there is x ∈ n such that |Ai|= x and bi + 1 ∈ n+ 1 \ A for all
i ∈ {1, ..., k}, where n+ 1 = {1, ..., n + 1}. We have ai+1 − bi = 2 for
all i ∈ {1, ..., k − 1} by Lemma 12. This implies bi + 2 = ai+1 for all
i ∈ {1, ..., k − 1}. Moreover, we have 1, n ∈ A by Corollary 5. Then we
have n+ 1 =
k⋃
i=1
(Ai∪{bi+1}), which implies n+1 =
k∑
i=1
|Ai∪{bi+1}|=
k(x + 1). Hence, A consists entirely of
n+ 1
x+ 1
maximal blocks of length
U. Chaichompoo, J. Koppitz, Y. Mati 195
x. Similarly, Aα consists entirely of
n+ 1
x+ 1
maximal blocks of length x.
Clearly, there is only one possibility to have
n+ 1
x+ 1
maximal blocks of
length x in an n-element set. Therefore, Aα = A for all α ∈ I F par
n
with A ⊆ dom(α).
Let us consider any A = [A1 A2 · · · Ak] ∈ A . Then |Ai|∈ 2N− 1
for all i ∈ {1, ..., k} or there is p ∈ {1, ..., k} with |Ap|∈ 2N. In the
first case, we have Aα = A for all α ∈ I F par
n with A ⊆ dom(α) by
Theorem 15. In the second case, we have to distinguish between p is
unique with that property or not. Then we get Aα = A by Theorems 18
and 20, respectively. So, we obtain the following corollary.
Corollary 21. Let A ∈ A and let α ∈ I F par
n . Then the following
statements are equivalent:
(1) A ⊆ dom(α);
(2) Aα = A;
(3) A ⊆ im(α).
Proof. Suppose that A ⊆ dom(α). Then Aα = A by the previous argu-
mentation. Suppose that Aα = A. Then it is clear that A ⊆ im(α). Sup-
pose that A ⊆ im(α). Then A ⊆ dom(α−1). Recall that α−1 ∈ I F par
n .
This implies Aα−1 = A by (1)→(2), and thus A ⊆ dom(α). This com-
pletes the proof.
2. Maximal congruences on I F par
n
This section provides the main result of this paper, the characterization
of the maximal congruences on I F par
n . Clearly, all congruences with
index two are maximal. It will turn out that all maximal congruences on
I F par
n have index two, that means all of them consisting entirely of two
equivalent classes. First, we will determine all congruences on I F par
n
with index two.
Lemma 22. Let ρ = (Γ × Γ) ∪ (Γ × Γ) be a congruence on I F par
n ,
where Γ ⊂ I F par
n with id ∈ Γ and Γ = I F par
n \Γ. Then the following
statements holds:
(1) ϕ /∈ Γ;
196 Congruences on fence-preserving transformations
(2) α ∈ Γ if and only if α−1 ∈ Γ.
Proof. (1) Assume that ϕ ∈ Γ. Then (id, ϕ) ∈ ρ, which implies (α, ϕ) =
(αid, αϕ) ∈ ρ for all α ∈ I F par
n . So, we have ρ = I F par
n × I F par
n ,
which is a contradiction with ρ = (Γ× Γ) ∪ (Γ× Γ). Hence ϕ /∈ Γ.
(2) Let α ∈ Γ. Assume that α−1 /∈ Γ, i.e. α−1 ∈ Γ. By (1), we have
(α−1, ϕ) ∈ ρ. Since α = αα−1α, we have (α, ϕ) = (αα−1α, αϕα) ∈ ρ, i.e.
α /∈ Γ, which is a contradiction. Hence α−1 ∈ Γ. The converse direction
becomes clear by (α−1)−1 = α.
The following lemma determines the congruences on I F par
n with
index two.
Lemma 23. Let Γ ⊆ I F par
n with id ∈ Γ and let ρ = (Γ× Γ) ∪ (Γ× Γ)
with Γ = I F par
n \ Γ. Then ρ is a congruence on I F par
n if and only if
for all α, β ∈ I F par
n , the following statements are equivalent:
(1) α, β ∈ Γ;
(2) αβ ∈ Γ.
Proof. Suppose that ρ is a congruence on I F par
n and let α, β ∈ I F par
n .
If α, β ∈ Γ, then (α, id) ∈ ρ and we have (αβ, β) = (αβ, idβ) ∈ ρ, which
implies αβ ∈ Γ. Next, let α ∈ Γ. Then (α, ϕ) ∈ ρ. For any β ∈ I F par
n ,
we have (αβ, ϕ) = (αβ, ϕβ) ∈ ρ and (βα, ϕ) = (βα, βϕ) ∈ ρ, which
implies αβ, βα ∈ Γ. This shows that α, β ∈ Γ if and only if αβ ∈ Γ.
Suppose that α, β ∈ Γ if and only if αβ ∈ Γ for all α, β ∈ I F par
n .
Since ρ is an equivalence relation, it remains to show that ρ is a con-
gruence. Let α, β, γ ∈ I F par
n such that (α, β) ∈ ρ. If α, β, γ ∈ Γ,
then we have (γα, γβ), (αγ, βγ) ∈ Γ × Γ ⊆ ρ. Otherwise, we have
(γα, γβ), (αγ, βγ) ∈ Γ× Γ ⊆ ρ. Hence ρ is a congruence.
For any A ∈ A , we define
ΓA = {α ∈ I F par
n : A ⊆ dom(α)}.
We observe that id ∈ ΓA. Clearly, for each A ∈ A , the relation
ρA = (ΓA × ΓA) ∪ (ΓA × ΓA)
with ΓA = I F par
n \ ΓA is an equivalence relation on I F par
n . We aim
to show that ρA is a maximal congruence on I F par
n .
U. Chaichompoo, J. Koppitz, Y. Mati 197
Theorem 24. Let A ∈ A . Then ρA is a maximal congruence on
I F par
n .
Proof. Clearly, ρA is an equivalence relation on I F par
n . So, we will
prove that ρA is a congruence on I F par
n by Lemma 23. Let α, β ∈ ΓA.
Then A ⊆ dom(α) and A ⊆ domβ. By Corollary 21, we obtain Aα = A
and Aβ = A. Thus, Aαβ = Aβ = A. This implies A ⊆ dom(αβ)
by Corollary 21. Hence αβ ∈ ΓA. Conversely, let αβ ∈ ΓA. Then A ⊆
dom(αβ). Moreover, we obtain A ⊆ im(αβ) by Corollary 21. So, we have
A ⊆ dom(αβ) ⊆ dom(α) and A ⊆ im(αβ) ⊆ im(β), i.e. A ⊆ dom(β) by
Corollary 21. Hence α, β ∈ ΓA. This shows that ρA is a congruence on
I F par
n , and since its index is two, we can conclude that ρA is a maximal
congruence on I F par
n .
Next, we will show that any maximal congruence ρ on I F par
n is of
the form ρ = ρA, for a suitable set A ∈ A .
Lemma 25. Let ρ be a congruence on I F par
n and let α ∈ I F par
n . If
α ∈ [id]ρ, then
id|dom(α), id|dom(α−1), α
−1 ∈ [id]ρ.
Proof. Let α ∈ [id]ρ, i.e. (α, id) ∈ ρ. So, we obtain (id|dom(α), α
−1) =
(αα−1, idα−1) ∈ ρ and (id|dom(α−1), α
−1) = (α−1α, α−1id) ∈ ρ. Thus,
(id|dom(α), id|dom(α−1)) ∈ ρ (by transitivity). Together with (α, id) ∈ ρ,
we obtain (α, id|dom(α−1)) = (id|dom(α)α, id|dom(α−1)id) ∈ ρ. Hence, we
obtain id|dom(α), id|dom(α−1), α
−1 ∈ [α]ρ = [id]ρ.
Lemma 26. Let ρ be a non-universal congruence on I F par
n . Then there
exists β ∈ [id]ρ such that ∅ ̸= dom(β) ⊆ dom(α) for all α ∈ [id]ρ.
Proof. Assume that for all β ∈ [id]ρ, there is α ∈ [id]ρ such that dom(β)
⊈ dom(α). It is clear that ϕ /∈ [id]ρ (see also the proof of Lemma 22(1)).
There is α2 ∈ [id]ρ with |dom(α2)|≤ |dom(α)| for all α ∈ [id]ρ. We
observe that dom(α2) ̸= ∅ since α2 ̸= ϕ. Then there is α1 ∈ [id]ρ
with dom(α2) ⊈ dom(α1). Now, we have (α1, id) ∈ ρ, which gives
(id|dom(α2)α1, id|dom(α2)) ∈ ρ. By Lemma 25, we obtain id|dom(α2)∈ [id]ρ
since α2 ∈ [id]ρ. Then id|dom(α2)α1 ∈ [id]ρ with dom(id|dom(α2)α1) ⊆
dom(α2). Since dom(α2) ⊈ dom(α1), we have |dom(id|dom(α2)α1)|<
|dom(α2)|, which is a contradiction with |dom(α2)|≤ |dom(α)| for all
α ∈ [id]ρ.
198 Congruences on fence-preserving transformations
Lemma 27. Let ρ be a non-universal congruence on I F par
n . Then there
exists β ∈ [id]ρ with dom(β) ∈ A such that dom(β) ⊆ dom(α) for all
α ∈ [id]ρ.
Proof. By Lemma 26, there is β ∈ [id]ρ such that ∅ ̸= dom(β) ⊆ dom(α)
for all α ∈ [id]ρ. Let A = dom(β). We claim that β ∈ A . Assume that
there exist x ∈ {0, ..., n−3} and k ∈ {2, ...,
⌈n
2
⌉
−
⌊x
2
⌋
} with x, x+2k /∈ A
such that |{x+ r, x+ 2k − r} ∩ A|= 1 for some r ∈ {1, ..., k − 1}. Then
let
γ =
(
1 · · · x− 1 x+ 1 · · · x+ 2k − 1 x+ 2k + 1 · · · n
1 · · · x− 1 x+ 2k − 1 · · · x+ 1 x+ 2k + 1 · · · n
)
and it is easy to verify that γ ∈ I F par
n . We know that id|dom(β)∈
[id]ρ by Lemma 25, i.e. (id|dom(β), id) ∈ ρ. It implies (γid|dom(β), γ) =
(γid|dom(β), γid) ∈ ρ. Thus (γid|dom(β)γid|dom(β), γγ) ∈ ρ. We put δ =
γid|dom(β)γid|dom(β) for convenience. We can see that dom(β) ⊈ dom(δ)
since (x + r)γ = x + 2k − r, and (x + 2k − r)γ = x + r implies {x + r,
x+ 2k − r} ∩ dom(iddom(β)γiddom(β)) = ∅. Note that dom(β) ⊆ dom(γ)
since x, x + 2k /∈ dom(β) and dom(γ) = n \ {x, x + 2k}. Moreover, we
have γ2 = γγ = id|dom(γ) and (id|dom(β), id|dom(γ)) = (id|dom(β)id|dom(γ),
idid|dom(γ)) ∈ ρ. This implies γ2 = id|dom(γ)∈ [id]ρ. Then δ ∈ [id]ρ since
(δ, γ2) ∈ ρ, which is a contradiction with dom(β) ⊈ dom(δ).
Now we can state the main result of the paper.
Theorem 28. Let ρ be a non-universal congruence on I F par
n . Then ρ
is maximal if and only if there is a set A ∈ A such that ρ = ρA.
Proof. Suppose that ρ is maximal. By Lemma 27, there is β ∈ [id]ρ with
dom(β) ∈ A such that dom(β) ⊆ dom(α) for all α ∈ [id]ρ. Assume
that there is (γ, δ) ∈ ρ with dom(β) ⊆ dom(γ) and dom(β) ⊈ dom(δ),
i.e. γ ∈ Γdom(β) and δ /∈ Γdom(β). Then β = γγ−1β but dom(β) ⊈
dom(δ)γ−1β, i.e. δγ−1β /∈ [id]ρ. Thus (γγ
−1β, δγ−1β) = (β, δγ−1β) /∈ ρ,
a contradiction. Because of the symmetry of ρ, we can conclude that
ρ ⊆ (ΓA×ΓA)∪(ΓA×ΓA) = ρA with A = dom(β) ∈ A . By Theorem 24,
ρA is a maximal congruence on I F par
n and since ρ is maximal, we get
ρ = ρA. The converse direction is given by Theorem 24.
Acknowledgements
The first author gratefully acknowledges the DPST scholarship for its
financial support. Furthermore, the authors would like to express their
U. Chaichompoo, J. Koppitz, Y. Mati 199
gratitude to the Department of Mathematics, Chiang Mai University,
and sincerely thank the reviewer for their insightful comments and con-
structive suggestions, which have significantly enhanced the quality and
clarity of this manuscript.
References
[1] Fernandes, V.H., Gomes, G.M.S., Jesus M.M.: Presentations for some mono-
ids of partial transformations on a finite chain. Comm. Algebra 33(2), 587–604
(2005). https://doi.org/10.1081/AGB-200047446
[2] Zhao, P., Hu, H.: On the monoid of all order-decreasing partial transformations.
Filomat 39(4), 1149–1162 (2025). https://doi.org/10.2298/FIL2504149Z
[3] Cicalò, S., Fernandes, V.H., Schneider, C.: Partial transformation monoids pre-
serving a uniform partition. Semigroup Forum 90, 532–544 (2015). https://doi.
org/10.1007/s00233-014-9629-5
[4] East, J.: Vines and partial transformations. Advances Math. 216(2), 787–810
(2007). https://doi.org/10.1016/j.aim.2007.06.005
[5] Currie, J.D., Visentin, T.I.: The number of order–preserving maps of fences and
crowns. Order 8, 133–142 (1991). https://doi.org/10.1007/BF00383399
[6] Rutkowski, A.: The formula for the number of order-preserving selfmappings of
a fence. Order 9, 127–137 (1992). https://doi.org/10.1007/BF00814405
[7] Sareeto, A., Koppitz, J.: The rank of the semigroup of order-, fence-, and parity-
preserving partial injections on a finite set. Asian-European J. Math. 16(12),
2350223 (2023). https://doi.org/10.1142/S1793557123502236
[8] Sareeto, A., Koppitz, J.: The maximal subsemigroups of the ideals in a monoid of
partial injections. Semigroup Forum 109, 194–204 (2024). https://doi.org/10.100
7/s00233-024-10439-5
[9] Dimitrova, I., Koppitz, J.: On the semigroup of all partial fence-preserving injec-
tions on a finite set. J. Algebra Appl. 16(12), 1750223 (2017). https://doi.org/10.
1142/S0219498817502231
[10] Koppitz, J., Musunthia, T.J.: The rank of the inverse semigroup of partial auto-
morphisms on a finite fence. Semigroup Forum 102, 437–455 (2021). https://doi.
org/10.1007/s00233-020-10150-1
[11] Fernandes, V.H., Koppitz, J., Musunthia, T.: The rank of the semigroup of all
order-preserving transformations on a finite fence. Bull. Malays. Math. Sci. Soc.
42, 2191–2211 (2019). https://doi.org/10.1007/s40840-017-0598-1
[12] Sanwong, J., Sullivan, R.P.: Maximal congruences on some semigroups. Algebra
Coll. 14(2), 255–263 (2007). https://doi.org/10.1142/S1005386707000259
[13] Howie, J.M.: A congruence-free inverse semigroup associated with a pair of infi-
nite cardinals. J. Australian Math. Soc. 31(3), 337–342 (1981). https://doi.org/
10.1017/S1446788700019479
[14] Mendes-Gonçalves, S., Sullivan, R.P.: The ideal structure of semigroups of trans-
formations with restricted range. Bull. Australian Math. Soc. 83(2), 289–300
(2011). https://doi.org/10.1017/S0004972710001814
https://doi.org/10.1081/AGB-200047446
https://doi.org/10.2298/FIL2504149Z
https://doi.org/10.1007/s00233-014-9629-5
https://doi.org/10.1007/s00233-014-9629-5
https://doi.org/10.1016/j.aim.2007.06.005
https://doi.org/10.1007/BF00383399
https://doi.org/10.1007/BF00814405
https://doi.org/10.1142/S1793557123502236
https://doi.org/10.1007/s00233-024-10439-5
https://doi.org/10.1007/s00233-024-10439-5
https://doi.org/10.1142/S0219498817502231
https://doi.org/10.1142/S0219498817502231
https://doi.org/10.1007/s00233-020-10150-1
https://doi.org/10.1007/s00233-020-10150-1
https://doi.org/10.1007/s40840-017-0598-1
https://doi.org/10.1142/S1005386707000259
https://doi.org/10.1017/S1446788700019479
https://doi.org/10.1017/S1446788700019479
https://doi.org/10.1017/S0004972710001814
200 Congruences on fence-preserving transformations
[15] Lohapan, L., Koppitz, J., Worawiset, S.: Congruences on infinite semigroups of
transformations preserving a zig-zag order. J. Algebra Appl. 20(9), 2150167
(2021). https://doi.org/10.1142/S021949882150167X
[16] Passararat, B., Koppitz, J.: The inverse semigroup of all fence-preserving injec-
tions and its maximal subsemigroups. Algebra Discrete Math. 39(2), 225–240
(2025). http://dx.doi.org/10.12958/adm2353
[17] Sripon, K., Laysirikul, E., Chinram, R.: Maximal and minimal congruences on the
semigroup TE(X). Sci. Technology Asia 29(4), 32–38 (2024). https://tci-thaijo.
org/index.php/SciTechAsia
Contact information
U. Chaichompoo,
Y. Mati
Department of Mathematics, Faculty of Science,
Chiang Mai University, Chiang Mai,
Thailand
E-Mail: flash.ex@hotmail.com,
Yananan_Mati@cmu.ac.th
J. Koppitz Institute of Mathematics and Informatics,
Bulgarian Academy of Sciences, Sofia,
Bulgaria
E-Mail: koppitz@math.bas.bg
Received by the editors: 12.02.2026
and in final form 16.06.2026.
https://doi.org/10.1142/S021949882150167X
http://dx.doi.org/10.12958/adm2353
https://tci-thaijo.org/index.php/SciTechAsia
https://tci-thaijo.org/index.php/SciTechAsia
Utsithon Chaichompoo, Jörg Koppitz, and Yananan Mati
|
| id | admjournalluguniveduua-article-2469 |
| institution | Algebra and Discrete Mathematics |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-07-09T01:00:16Z |
| publishDate | 2026 |
| publisher | Lugansk National Taras Shevchenko University |
| record_format | ojs |
| resource_txt_mv | admjournalluguniveduua/86/3235962a55d534868311ae7e6cd14f86.pdf |
| spelling | admjournalluguniveduua-article-24692026-07-08T07:55:33Z All maximal congruences on an inverse semigroup of fence-preserving transformations Chaichompoo, Utsithon Koppitz, Jörg Mati, Yananan partial injection, inverse semigroup, zig-zag order, maximal congruence 20M20, 20M05 We study the inverse semigroup of all partial injections on an \(n\)-element set \(\{1,...,n\}\), which preserve the zig-zag order \(1\prec 2\succ 3\prec 4\succ \cdots n\) and the parity for some positive integer \(n\). We characterize all maximal congruences on this inverse semigroup, which are entirely congruences of index two. Lugansk National Taras Shevchenko University 2026-07-08 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2469 10.12958/adm2469 Algebra and Discrete Mathematics; Vol 41, No 2 (2026) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2469/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2469/1397 https://admjournal.luguniv.edu.ua/index.php/adm/article/downloadSuppFile/2469/1398 Copyright (c) 2026 Algebra and Discrete Mathematics |
| spellingShingle | partial injection inverse semigroup zig-zag order maximal congruence 20M20 20M05 Chaichompoo, Utsithon Koppitz, Jörg Mati, Yananan All maximal congruences on an inverse semigroup of fence-preserving transformations |
| title | All maximal congruences on an inverse semigroup of fence-preserving transformations |
| title_full | All maximal congruences on an inverse semigroup of fence-preserving transformations |
| title_fullStr | All maximal congruences on an inverse semigroup of fence-preserving transformations |
| title_full_unstemmed | All maximal congruences on an inverse semigroup of fence-preserving transformations |
| title_short | All maximal congruences on an inverse semigroup of fence-preserving transformations |
| title_sort | all maximal congruences on an inverse semigroup of fence-preserving transformations |
| topic | partial injection inverse semigroup zig-zag order maximal congruence 20M20 20M05 |
| topic_facet | partial injection inverse semigroup zig-zag order maximal congruence 20M20 20M05 |
| url | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/2469 |
| work_keys_str_mv | AT chaichompooutsithon allmaximalcongruencesonaninversesemigroupoffencepreservingtransformations AT koppitzjorg allmaximalcongruencesonaninversesemigroupoffencepreservingtransformations AT matiyananan allmaximalcongruencesonaninversesemigroupoffencepreservingtransformations |