Generalized Cayley graphs of semigroups II

Abstract

Following Zhu (Semigroup Forum, 2011, doi:10.1007/s00233-011-9368-9), we study generalized Cayley graphs of semigroups. The Cayley D-saturated property, a particular combinatorial property, of generalized Cayley graphs of semigroups is considered and most of the results in Kelarev and Quinn (Semigroup Forum 66:89–96, 2003), Yang and Gao (Semigroup Forum 80:174–180, 2010) are extended. In addition, for some basic graphs and their complete fission graphs, we describe all semigroups whose universal Cayley graphs are isomorphic to these graphs.

1 Introduction

The Cayley graphs of semigroups have been investigated by many authors, see, for example, [1, 4, 6, 7, 9, 12–14, 17]. Some of the earliest references on this subject are [2] and [18]. The Cayley graphs of semigroups are closely related to finite state automata and have many valuable applications (see [5, 11]). Combinatorial properties of semigroups defined in terms of their Cayley graphs were considered in [8, 10].

The concept of generalized Cayley graphs of semigroups was first introduced by the author in [19], where some fundamental properties of generalized Cayley graphs of semigroups were studied.

Following [19], in the present paper, we continue discussion of generalized Cayley graphs of semigroups. In Sect. 3, we describe the semigroups whose universal Cayley graphs are some basic graphs or their complete fission graphs, and in Sect. 4, we study the D-saturated property, a particular combinatorial property, of generalized Cayley graphs of semigroups. Some results of [19] are used in this paper.

2 Preliminaries

Recall that if S is an ideal of a semigroup T, then we call T an ideal extension of S. Let T ¹ be the semigroup T with an identity adjoined if necessary.

Definition 2.1

[19]

Let T be an ideal extension of a semigroup S and ρ⊆T ¹×T ¹. The Cayley graph Cay(S,ρ) of S relative to ρ is defined as the graph with vertex set S and edge set E(Cay(S,ρ)) consisting of those ordered pairs (a,b), where xay=b for some (x,y)∈ρ. We also call the Cayley graphs defined in this way the generalized Cayley graphs, in order to distinguish them from the usual ones.

Assume that S is a semigroup and a∈S. Then J(a)=S ¹ aS ¹ (L(a)=S ¹ a, R(a)=aS ¹) is the principal (left, right) ideal generated by a. For other notations and notions of semigroup theory, we refer the reader to [3, 15, 19, 20]. Let ω _l =S ¹×{1} (the left universal relation on S ¹), ω _r ={1}×S ¹ (the right universal relation on S ¹) and ω=S ¹×S ¹ (the universal relation on S ¹). Then the generalized Cayley graphs Cay(S,ω _l ), Cay(S,ω _r ) and Cay(S,ω) are called left universal, right universal and universal Cayley graphs of S, respectively.

We use standard terminology of graph theory following, e.g., [16]. Throughout the paper, graphs are directed graphs without multiple edges, but possibly with loops, or digraphs in terms of [1, 13]. A directed graph without loops and multiple edges is called simple. We may equate two graphs each of which is isomorphic to the other one. For a graph Γ, denote by V(Γ) and E(Γ) its vertex set and edge set, respectively. For any a∈V(Γ), Let

$$ \overrightarrow{a}=\{b\in V(\varGamma )|(a, b)\in E(\varGamma )\},\qquad \overleftarrow{a}=\{b\in V(\varGamma )|(b, a)\in E(\varGamma )\}.$$

(2.1)

Assume that T is an ideal extension of a semigroup S and ρ⊆T ¹×T ¹. Let

(2.2)

(2.3)

We call ρ(a)¹ the ρ-class of a. It is evident that (a,b)∈E(Cay(S,ρ)) if and only if b∈ρ(a). So by (2.1), we obtain

$$ \rho (a)=\overrightarrow{a}.$$

(2.4)

Lemma 2.2

[19]

Let T be an ideal extension of a semigroup S, ρ⊆T ¹×T ¹ and a,b∈S. If ρ ¹(a)⊇ρ ¹(b) and a≠b, then (a,b)∈E(Cay(S,ρ)).

Definition 2.3

[19]

Let T be a semigroup and ρ⊆T×T. If (a,b),(c,d)∈ρ for any a,b,c,d∈T always implies (ca,bd)∈ρ, then we call ρ inversely compatible, or briefly, I-compatible.

Definition 2.4

[19]

Let Γ be a graph. If (a,b),(b,c)∈E(Γ) for a,b,c∈V(Γ) always implies that (a,c)∈E(Γ), then Γ is said to be edge-transitive.

Proposition 2.5

[19]

Assume that T is an ideal extension of a semigroup S. If ρ⊆T ¹×T ¹ is I-compatible, then Cay(S,ρ) is edge-transitive.

Corollary 2.6

[19]

Assume that T is an ideal extension of a semigroup S and ρ⊆T ¹×T ¹ is I-compatible. If (a,b)∈E(Cay(S,ρ)), then ρ(a)⊇ρ(b) and ρ ¹(a)⊇ρ ¹(b).

Definition 2.7

[19]

Assume that T is an ideal extension of a semigroup S and ρ⊆T ¹×T ¹. An element a of S is called stable under ρ if a∈ρ(a). If all elements of S are stable under ρ, then S is called stable under ρ.

Let (Y,≥) be a partially ordered set. For any a∈Y, set

$$ a\downarrow=\{b\in Y|a\geq b\},\qquad a\uparrow=\{b\in Y|b\geq a\}.$$

(2.5)

The relation graph of the inverse relation ≥ of the natural order ≤ on a semilattice is called a semilattice graph. A complete graph with loops is defined as a graph Γ with the edge set E(Γ)={(x,y)|x,y∈V(Γ)}. Assume that T is an ideal extension of a semigroup S and ρ⊆T ¹×T ¹. If ρ ¹(a)=ρ ¹(b) for all a,b∈S, then S is called ρ-simple.

Recall that a totally ordered set is also called a chain. The relation graph of a chain is called a linear graph or chain graph. A finite chain graph of length n could be indicated by the set L _n ={0,1,…,n} with edge set {(i,j)|i≥j}, where ≥ is the usual order on natural numbers.

Theorem 2.8

[19]

Assume that T is an ideal extension of a semigroup S and ρ⊆T ¹×T ¹ is an I-compatible relation such that S is stable under ρ. Then the following conditions are equivalent:

• (1) Cay(S,ρ) is a chain of complete graphs with loops;

• (2) S is a chain of ρ-simple semigroups.

Lemma 2.9

[19]

For any semigroup S, the following conditions are equivalent:

• (1) (a,b)∈E(Cay(S,ω));

• (2) J(a)⊇J(b).

A partially ordered set (Y,≥) is called a strong partially ordered set if for any α,β∈X, there is γ∈Y such that α≥γ and β≥γ. If (Y,≥) is a partially ordered set and Y is a semigroup such that for any α,β∈Y, α,β≥αβ, then we call the semigroup Y a partially ordered semigroup, and we call the partially ordered set Y a semigroup-partially-ordered set. If B is a partially ordered semigroup that is also a band (i.e., an idempotent semigroup), then we call B a band-partially-ordered set or a partially ordered band. If (Y,≥) is a partially ordered set, Y is a semigroup, T is an ideal extension of Y and ρ⊆T ¹×T ¹ such that for any α∈Y, ρ ¹(α)=α↓ where by α↓ we denote the set {β|α≥β}, then we call the semigroup Y a ρ-semigroup, and we call the partially ordered set Y a ρ-partially-ordered set. For example, if ρ=S ¹×S ¹, a ρ-partially-ordered set or ρ-semigroup is called a $\mathcal{J}$ -partially-ordered set or $\mathcal{J}$ -semigroup. The relation graph of a strong partially ordered set (rep. semigroup-partially-ordered set, $\mathcal{J}$-partially-ordered set, etc.) is called a strong partially ordered graph (rep. semigroup-partially-ordered graph, $\mathcal{J}$ -partially-ordered graph, etc.)

For a graph Γ define a relation ∼ on V(Γ) by setting a∼b if and only if (a,b)∈V(Γ) and (b,a)∈V(Γ). If ∼ is an equivalence such that the quotient graph Γ/∼ is a strong partially ordered graph (resp. semigroup-partially-ordered graph, $\mathcal{J}$-partially-ordered graph, semilattice graph, etc.), then we call Γ a strong partial order (resp. semigroup-partial order, $\mathcal{J}$ -partial-order, semilattice, etc.) of complete graphs with loops. A strong partial order Γ of complete graphs Γ _α (α∈Y) with loops is called nonidempotent-trivial if Γ _α is trivial (i.e., |V(Γ _α )|=1) for every nonidempotent α of Y. It is easy to show that Cay(S,ω)/∼ is a strong partially ordered graph.

Lemma 2.10

[19]

For any semigroup S, Cay(S,ω) is a strong partial order of complete graphs with loops.

Theorem 2.11

[19] The following statements are valid:

• (1) if S is a completely regular semigroup, then Cay(S,ω) is a semilattice of complete graphs with loops;

• (2) if Γ is a semilattice of complete graphs with loops, then there is a (commutative) completely regular semigroup such that Cay(S,ω)=Γ.

Theorem 2.12

[19]

The following statements hold:

• (1) For any semigroup S, Cay(S,ω) is a strong partial order of complete graphs with loops, and for each a∈S and all b∈J(a), (a,b)∈E(Cay(S,ω));

• (2) Let Γ be a nonidempotent-trivial $\mathcal{J}$-partial order Y of complete graphs with loops. Then there is a semigroup S such that Cay(S,ω)=Γ. Moreover, if Y is a commutative semigroup, then S can be chosen to be commutative.

3 Some basic graphs as universal Cayley graphs of semigroups

In this section, for some simple and important special kinds of graphs such as k-partite complete chain graph with loops and their complete fission graphs, we construct the corresponding semigroups whose generalized Cayley graphs are the given ones. At last, we give a necessary and sufficient condition for the universal Cayley graph of a semigroup to be a finite linear graph.

First, we introduce two new notions.

Definition 3.1

Assume that A ₁,A ₂,…,A _k are some pairwise disjoint nonempty sets. Let Γ be a graph with vertex set $V(\varGamma )=\bigcup _{i=1}^{k}A_{i}$ and edge set

$$E(\varGamma )=\{(a,b)|a\in A_i, b\in A_j, \mbox{ and } i<j\}\cup\{(a,a)|a\in V(\varGamma )\}.$$

Then we call Γ a k-partite complete chain graph with loops, denoted by K(A ₁,…,A _k ). If |A _i |=α _i for i=1,…,k, then K(A ₁,A ₂,…,A _k ) is also denoted by K(α ₁,…,α _k ). For an arbitrary cardinality α, K(1,α) is also called a down-claw with α toes, and K(α,1) is called an up-claw with α toes. For an infinite cardinality α, we can define similarly α-partite complete chain graphs with loops.

Definition 3.2

Let Γ be a graph and A={a _i |i∈I}⊆V(Γ), and {A _i } _i∈I a class of pairwise disjoint sets, each of which is disjoint with V(Γ). A complete fission graph by splitting Γ at points of A is defined as a graph Γ ^∗ with the vertex set V(Γ ^∗)=(V(Γ)∖A)∪(⋃ _i∈I A _i )}, and edge set

Note that if |A|,|B|>1, then K(A,B,C) is a partially ordered graph but not a semilattice graph, so it is worth being considered. If K(A,B,C) is a generalized Cayley graph of a semigroup, then by Lemma 2.10, it is a strong partially ordered graph which implies that |C|=1. Thus we may suppose that |C|=1 when studying K(A,B,C), as we do in the sequel.

Theorem 3.3

For any positive integers m and n, there is a commutative semigroup S such that Cay(S,ω)=K(m,n,1). Moreover, if Γ is a fission graph of K(A,B,C) with sets A,B,C and that |C|=1 by splitting up at any points of B∪C, then there exists a commutative semigroup T such that Cay(T,ω)≃Γ.

Proof

Let S={0,1,2,…,n,a ₁,a ₂,…,a _m }. Define the multiplication on S by the Cayley table, Table 1.

Table 1 Cayley table used to prove Theorem 3.3

It is easy to verify that S is a semigroup. Since Table 1 is symmetric, S is commutative. Simple computation shows that J(0)={0}, J(k)={0,k} for k=1,2,…,n, and J(a _k )={0,1,…,n,a _k } for k=1,2,…,m. Thus by Lemma 2.9, Cay(S,ω)=K(m,n,1).

Suppose without loss of generality that A={a ₁,a ₂,…,a _m }, B={1,2,…,n} and C={0}. Then K(A,B,C)=K(m,n,1)=S is a semigroup in view of the above. According to Lemma 2.10, K(A,B,C) is a strong-partially-ordered graph. Furthermore, a direct verification shows that K(A,B,C) is a $\mathcal{J}$-partially-ordered graph. Since Γ is a complete fission graph of K(A,B,C) by splitting up at the idempotents {0,1,2,…,n}=B∪C, Γ is a nonidempotent-trivial $\mathcal{J}$-partial order of complete graphs with loops by Definition 3.2. In light of Theorem 2.12, there exists a commutative semigroup T such that Cay(T,ω)≃Γ, which completes the proof. □

Theorem 3.4

If m and n are positive integers such that m≥n≥2, then there exists a noncommutative semigroup S with a zero 0 such that Cay(S,ω)=K(m,n,1). Moreover, if Γ is a fission graph of K(A,B,C) with sets A,B,C and that C={0} by splitting up at 0, then there exists a noncommutative semigroup T such that Cay(T,ω)≃Γ.

Proof

The arguments are similar to those in the proof of Theorem 3.3, so we just give the Cayley table, Table 2.

Table 2 Cayley table used to prove Theorem 3.4

 □

Similarly, we have

Theorem 3.5

For any positive integer n, there is a noncommutative semigroup S such that Cay(S,ω)=K(2,n,1). Moreover, if Γ is a fission graph of K(A,B,C) with sets A,B,C and that |C|=1 by splitting up at any points of A∪C, then there exists a noncommutative semigroup T such that Cay(T,ω)≃Γ.

Recall that if {S _α } _α∈I is a class of 0-subsemigroups of S satisfying that S=⋃ _α∈I S _α and for α≠β, S _α ∩S _β =S _α S _β ={0}, then we say that S is the 0-direct union of S _α ’s. If E is a semilattice, i.e., a commutative idempotent semigroup, then the natural order on E is defined by setting e≤f if and only if ef=fe=e. A semilattice E with a zero 0 is called 0-primitive, if every nonzero element of E is 0-primitive, that is, minimal in E∖{0}. Now we can characterize the up-claws K(α,1) as follows.

Theorem 3.6

Let S be a semigroup whose cardinality is α+1 with α>1. Then Cay(S,ω)=K(α,1) if and only if S is either a 0-primitive semilattice, or a null semigroup, or a 0-direct union of both of them.

Proof

Sufficiency: Without loss of generality, let S be a 0-direct union of a 0-primitive semilattice and a null semigroup with zero 0. Then J(0)={0}, and J(a)={0,a} for each a∈S∖{0}. Hence, by Lemma 2.9, Cay(S,ω)=K(α,1).

Necessity: Assume that Cay(S,ω)=K(α,1). Then Cay(S,ω) has a lower bound which we denote by 0, i.e., (a,0)∈E(Cay(S,ω)) for all a∈S. By (2.4), $J(a)=\overrightarrow{a}$ for every a∈S. It follows that J(0)={0} which means that 0 is a zero of S. Also J(a)={0,a} for all a∈S∖{0}. Hence for all a≠b∈S, ab∈J(a)∩J(b)={0}. For any a∈S∖{0}, a ²∈J(a)={0,a}. Thus a ²=0 or a ²=a. If the first case occurs for all a∈S, then S is null. Otherwise, there exists a∈S such that a ²=a≠0. Let E be the set of all idempotents of S and let F=(S∖E)∪{0}. Then F is a null semigroup. Let e,f∈E such that e≠0 and e≠f. Then e ²=e and ef=0=fe, and so e is a 0-primitive idempotent. Furthermore, E is a 0-primitive semilattice. It is clear that for all e∈E and n∈F, en=ne=0. Thus S is a 0-direct union of E and F. In particular, if F={0}, then S=E is a 0-primitive semilattice. So the theorem is proved. □

Theorem 3.7

For a semigroup S=L _n , Cay(S,ω)=L _n if and only if there exists a total order ≥ on S such that the following conditions are satisfied:

• (1) for any i,j∈L _n , min(i,j)≥ij;

• (2) for all i≠j, |J(i)|≠|J(j)|.

Proof

Necessity: Assume that S=L _n is a semigroup such that Cay(S,ω)=L _n . The natural order ≥ for natural numbers may be taken as the total order on S. Then for any i∈L _n , $J(i)=\overrightarrow{i}=i\downarrow =\{0,1,\ldots,i\}$. Thus that |J(i)|=|J(j)| implies that i=j, and (2) follows. For any i,j∈L _n , ij∈J(i)∩J(j)=J(min(i,j))=min(i,j)↓, hence min(i,j)≥ij and (1) follows.

Sufficiency: Assume S={0<1<2<⋯<n} is a total set with the total order ≤ such that the two conditions presented in the theorem are satisfied. Then J(0)={0}, J(1)={0,1}, J(2)={0,1,2}, and J(n)={0,1,2,…,n}. Thus by Lemma 2.9, Cay(S,ω)=L _n as desired. □

Remark 3.8

• (1) The next question remains open: Is it true that the countably-infinite-partite complete chain graph with loops

  $$K(\{a_1,a_2\},\ldots,\{3\},\{2\},\{1\},\{0\},\{-1\},\{-2\},\{-3\},\ldots)$$

  is a $\mathcal{J}$-partially-ordered graph, where {a ₁,a ₂}∩ℤ=∅?

• (2) It may be interesting to characterize semigroups S such that Cay(S,ω _l )=Cay(S,ω _r ).

4 D-saturated property of the Cayley graphs of semigroups

The following combinatorial property was introduced in [9] and was investigated further in [17] for the Cayley graphs of semigroups. A semigroup S is said to be Cayley D-saturated with respect to a subset T of S if, for all infinite subsets V of S, there exists a subgraph of Cay(S,T) isomorphic to D with all vertices in V. In this section, we study the Cayley D-saturated property of a generalized Cayley graph and generalize the corresponding results of [9, 17].

Let ℕ be the set of all natural numbers. An infinite ascending (resp. descending) chain A _∞ (resp. D _∞) is the graph with the set N as its vertex set and with edges (i,j) such that i<j (rep. i>j). An infinite complete symmetric graph K _∞ is the graph with the set ℕ as vertex set and with edges (i,j) for all distinct i,j∈ℕ. The null graph is a graph with no edges. Recall that a finite graph D has no cycles if and only if D can be embedded in A _∞ or D _∞, and that any finite graph can be embedded in K _∞.

Lemma 4.1

[9]

Every infinite graph contains an infinite set of vertices which induces a null subgraph, A _∞, D _∞ or K _∞.

If S is a finite semigroup, then it is vacuously true that S is Cayley D-saturated with respect to all relations ρ on T ¹, where T is an ideal extension of S. If D is null, then all semigroups S are Cayley D-saturated with respect to all relations ρ on T ¹. If S is an infinite semigroup, ρ is the empty relation but D is not null, then it is obvious that S is not Cayley D-saturated with respect to ρ. So in the sequel, we only need to consider the case where S is an infinite semigroup, D is not a null graph and ρ is a nonempty relation. We first consider the case where D has no cycles.

Theorem 4.2

Assume that D is a finite simple graph with no cycles, T is an ideal extension of an infinite semigroup S and ρ⊆T ¹×T ¹ is a nonempty relation. Then the following conditions are equivalent:

• (1) S is Cayley D-saturated with respect to ρ;

• (2) every infinite subset of V(Cay(S,ρ)) induces a subgraph of Cay(S,ρ) which is not null.

Proof

(1) ⇒ (2): Suppose towards a contradiction that there is an infinite subset V⊆S such that V induces a null subgraph in Cay(S,ρ). Then D is not embeddable in the subgraph of Cay(S,ρ) induced by V, which contradicts the assumption that S is Cayley D-saturated with respect to ρ.

(2) ⇒ (1): Let V be an infinite subset of S. Then V induces an infinite subgraph Γ of Cay(S,ρ). By Lemma 4.1, there is an infinite subset U⊆V which induces a subgraph of Γ that is either null, or isomorphic to D _∞, A _∞ or K _∞. Since the first case is excluded by condition (2) and D can be embedded in D _∞, A _∞ or K _∞, the graph D can be embedded in the subgraph Γ induced by U. Thus D can be embedded in the graph induced by V in Cay(S,ρ) and so S is D-saturated with respect to ρ. □

Two sets are incomparable if neither one is contained in the other. As a consequence of Theorem 4.2, we have the following

Corollary 4.3

Assume that D is a finite simple graph with no cycles, T is an ideal extension of an infinite semigroup S and ρ⊆T ¹×T ¹ is a nonempty I-compatible relation. Then the following conditions are equivalent:

• (1) S is Cayley D-saturated with respect to ρ;

• (2) S does not have an infinite set {ρ ¹(s _i )|i∈ℕ} such that ρ ¹(s _i ) and ρ ¹(s _j ) are incomparable for all distinct i,j∈ℕ.

Proof

(1) ⇒ (2): Suppose by way of contradiction that there is an infinite set A={ρ ¹(s _i )|i∈ℕ} such that ρ ¹(s _i ) and ρ ¹(s _j ) are incomparable for all distinct i,j∈ℕ. Then there is an infinite set V such that V induces a subgraph of Cay(S,ρ) which is not null by (2) of Theorem 4.2, since S is Cayley D-saturated with respect to ρ. Thus there are distinct i,j∈ℕ such that (s _i ,s _j )∈E(Cay(S,ρ)). Since ρ is I-compatible, it follows from Corollary 2.6 that ρ ¹(s _i )⊇ρ ¹(s _j ), which contradicts that ρ ¹(s _i ) and ρ ¹(s _j ) are incomparable.

(2) ⇒ (1): Let V={v _i |i∈ℕ} be an infinite subset of S. From (2), it follows that there are i≠j∈ℕ such that ρ ¹(v _i )⊇ρ ¹(v _j ). By Lemma 2.2, (v _i ,v _j )∈E(Cay(S,ρ)) since v _i ≠v _j . Thus V does not induce a null subgraph of Cay(S,ρ) and so S is Cayley D-saturated with respect to ρ by (2) of Theorem 4.2. □

Corollary 4.4

Let D be a finite simple graph with no cycles, S an infinite semigroup. Then the following conditions are equivalent:

• (1) S is Cayley D-saturated with respect to S×S (resp. S×{1}, {1}×S);

• (2) S is Cayley D-saturated with respect to S ¹×S ¹ (resp. S ¹×{1}, {1}×S ¹);

• (3) S does not have an infinite set of pairwise incomparable principal ideals (resp. principal left ideals, principal right ideals).

Remark 4.5

The corresponding results remain correct if S ¹×S ¹ is replaced by S ¹×S or by S×S ¹ in Corollary 4.4.

Next we consider the case where the graph D has a cycle.

Theorem 4.6

Assume that D is a finite simple graph which has a cycle, T is an ideal extension of an infinite semigroup S and ρ⊆T ¹×T ¹ is a nonempty relation. Then the following conditions are equivalent:

• (1) S is Cayley D-saturated with respect to ρ;

• (2) every subgraph of Cay(S,ρ) induced by an infinite subset of S contains a subgraph isomorphic to K _∞;

• (3) for any infinite subset U⊆S, there is an infinite subset W⊆U such that W⊆ρ(a) for any a∈W.

Proof

(1) ⇒ (2): Let V be an infinite subset of S. Then V induces an infinite subgraph Γ of Cay(S,ρ). By Lemma 4.1, there is an infinite subset U⊆V such that U induces a subgraph of Γ that is a null graph, D _∞, A _∞, or K _∞. Since D has a cycle and S is Cayley D-saturated with respect to ρ, the first, second and third cases are excluded. Thus U induces K _∞ in Cay(S,ρ) and so the subgraph of Cay(S,ρ) induced by V contains K _∞.

(2) ⇒ (3): Let U be an infinite subset of S. Then by (2) there is an infinite subset W⊆U such that W induces K _∞ in Cay(S,ρ). Let a,b∈W. Then (a,b)∈E(Cay(S,ρ)) and so b∈ρ(a). Thus W⊆ρ(a), as required.

(3) ⇒ (1): Let V be an infinite subset of S. Then by (3), there is an infinite subset W⊆V such that W⊆ρ(a) for any a∈W. Thus (a,b)∈E(Cay(S,ρ)) for any b∈W and so W induces K _∞ in Cay(S,ρ). Since D can be embedded in K _∞, D can be embedded in the subgraph of K _∞ induced by V. Therefore, S is Cayley D-saturated with respect to ρ and the theorem is proved. □

Corollary 4.7

Let D be a finite simple graph which has a cycle, T an ideal extension of an infinite semigroup S and ρ⊆T ¹×T ¹ a nonempty relation. If S is Cayley D-saturated with respect to ρ, then there exist elements s ₀,s ₁,…,s _n ∈S such that S=ρ ¹(s ₀)∪ρ ¹(s ₁)∪⋯∪ρ ¹(s _n ).

Proof

Let s ₀∈S and consider the set S∖ρ ¹(s ₀). If the set S∖ρ ¹(s ₀) is finite, then the result is true. If the set S∖ρ ¹(s ₀) is infinite, let s ₁∈S∖ρ ¹(s ₀) and consider the set S∖(ρ ¹(s ₀)∪ρ ¹(s ₁)). Repeating the same process, if the process terminates after some finite steps, then the result follows. Otherwise, we can get an infinite set {ρ ¹(s _i )|i∈ℕ} such that s _i ∈S∖⋃_0≤j<i ρ ¹(s _j ) for all i>0. Let V={s _i |i∈ℕ}. Since S is Cayley D-saturated with respect to ρ, the subgraph induced by V in Cay(S,ρ) contains a subgraph K isomorphic to K _∞ by (2) of Theorem 4.6. Without loss of generality, let s ₀∈V(K). Then there is a positive i such that s _i ∈V(K). It follows that (s ₀,s _i )∈E(Cay(S,ρ)), and so s _i ∈ρ(s ₀). Therefore, s _i ∈ρ ¹(s ₀) which contradicts the choice of s _i . □

Corollary 4.8

Let D be a finite simple graph which has a cycle, T an ideal extension of an infinite semigroup S and ρ⊆T ¹×T ¹ a nonempty relation. If S is Cayley D-saturated with respect to ρ, then the following statements hold:

• (1) the set ρ is infinite;

• (2) if ρ is I-compatible, then the set of ρ-classes of S is finite;

• (3) if ρ is I-compatible, then the set {ρ(a)|a∈S} is finite.

Proof

Let U be an infinite subset of S. Since S is Cayley D-saturated with respect to ρ, there is an infinite subset W⊆U such that W⊆ρ(a) for any a∈W by (3) of Theorem 4.6. Thus ρ must be infinite and (1) holds.

To show (2), suppose toward a contradiction that the set A of ρ-classes of S is infinite. Let A={ρ ¹(s _i )|i∈ℕ} be an infinite set, and set V={s _i |i∈ℕ}. Then V induces an infinite subgraph of Cay(S,ρ), and so there is an infinite subset U⊆V such that U induces a subgraph in Cay(S,ρ) which is isomorphic to K _∞ by (2) of Theorem 4.6. Thus there are s _i ≠s _j ∈U such that (s _i ,s _j ),(s _j ,s _i )∈E(Cay(S,ρ)). Hence by Corollary 2.6, ρ ¹(s _i )=ρ ¹(s _j ), which contradicts that s _i and s _j are in different ρ-classes. Therefore (2) holds. Similarly, we can prove (3). □

Recall that the union of two graphs Γ ₁ and Γ ₂, denoted by Γ ₁∪Γ ₂, is the graph with the vertex set V(Γ ₁)∪V(Γ ₂) and the edge set E(Γ ₁)∪E(Γ ₂). Furthermore, if V(Γ ₁)∩V(Γ ₂)=∅, we call Γ ₁∪Γ ₂ the disjoint union of Γ ₁ and Γ ₂.

Theorem 4.9

Let D be a finite simple graph which has a cycle, T an ideal extension of an infinite semigroup S and ρ⊆T ¹×T ¹ a nonempty I-compatible relation. Then the following conditions are equivalent:

• (1) S is Cayley D-saturated with respect to ρ;

• (2) Cay(S,ρ) is the finite disjoint union of complete symmetric graphs;

• (3) the set {ρ ¹(s)|s∈S} is finite.

Proof

(1) ⇒ (2): Since S is Cayley D-saturated with respect to ρ, every subgraph of Cay(S,ρ) induced by an infinite subset of S contains a subgraph isomorphic to K _∞ by (2) of Theorem 4.6. Let A ₀ be the set of complete symmetric subgraphs of Cay(S,ρ). For Γ ₁,Γ ₂∈A ₀, define a partial order ≤ on A ₀ by setting Γ ₁≤Γ ₂ if and only if V(Γ ₁)⊆V(Γ ₂). Suppose that Γ ₁≤Γ ₂≤⋯ is a chain of A ₀. Then ⋃ _i∈ℕ Γ _i is an upper bound of the chain in A ₀. So by Zorn’s Lemma, there is a maximal element H ₀∈A ₀. Now we consider the set S∖V(H ₀). If the set S∖V(H ₀) is finite, then the result is true. If the set S∖V(H ₀) is infinite, let A ₁ be the set of complete symmetric subgraphs of the subgraph induced by S∖V(H ₀) in Cay(S,ρ). With a similar argument, there is a maximal element H ₁ in A ₁. Repeating the same process, if the process terminates after some finite steps, then the result follows. Otherwise, we can obtain an infinite set {H _i |i∈ℕ}, where each H _i is maximal in the set of complete symmetric subgraphs of the subgraph induced by S∖⋃_1≤j<i V(H _j ) in Cay(S,ρ). Let v _i ∈H _i and V={v _i |i∈ℕ}. Since S is Cayley D-saturated with respect to ρ, V contains an infinite complete symmetric subgraph K by (2) of Theorem 4.6. Let I={i|v _i ∈V(K)}. Without loss of generality, let 0∈I. Then there is a positive integer j∈I, which means that v _j ∈V(K) and (v ₀,v _j ),(v _j ,v ₀)∈E(Cay(S,ρ)). Since ρ⊆T ¹×T ¹ is I-compatible, then Cay(S,ρ) is edge-transitive according to Proposition 2.5. Now for any v∈V(H ₀)∖{v ₀}, we have (v,v ₀),(v ₀,v)∈E(Cay(S,ρ)) and thus (v,v _j ),(v _j ,v)∈E(Cay(S,ρ)). It follows that V(H ₀)∪{v _j } induces a complete symmetric subgraph in Cay(S,ρ), which contradicts that H ₀ is maximal in A ₀ since $v_{j}\bar{\in}H_{0}$.

(2) ⇒ (3): Let Cay(S,ρ)=K ₀∪K ₁∪⋯∪K _n where n is finite and all K _i ’s are complete symmetric subgraphs. Let u,v∈K _i and u≠v. Then (u,v),(v,u)∈E(Cay(S,ρ)). In light of Corollary 2.6, we have ρ ¹(u)⊇ρ ¹(v) and ρ ¹(v)⊇ρ ¹(u). Immediately, ρ ¹(u)=ρ ¹(v), which implies that the cardinality of the set {ρ ¹(s)|s∈S} is at most n. Thus the set {ρ ¹(s)|s∈S} is finite.

(3) ⇒ (1): Let V be an infinite subset of S. Since the set {ρ ¹(s)|s∈S} is finite, there is an infinite subset U⊆V such that ρ ¹(u)=ρ ¹(v) for any u≠v∈U. By Lemma 2.2, (u,v),(v,u)∈E(Cay(S,ρ)). So U induces a complete symmetric subgraph K in Cay(S,ρ). Consequently, V contains K and D can be embedded in the subgraph of Cay(S,ρ) induced by V. Therefore, S is Cayley D-saturated with respect to ρ. □

Remark 4.10

If we drop the assumption that ρ is I-compatible from the above theorem, then the implication (3) ⇒ (1) remains true.

Corollary 4.11

Let D be a finite simple graph which has a cycle, T an ideal extension of an infinite semigroup S and ρ⊆T ¹×T ¹ a nonempty I-compatible relation. Then the following conditions are equivalent:

• (1) S is Cayley D-saturated with respect to S×S (rep. S×{1}, {1}×S);

• (2) S is Cayley D-saturated with respect to S ¹×S ¹ (rep. S ¹×{1}, {1}×S ¹);

• (3) the number of principal ideals (rep. principal left ideals, principal right ideals) of S is finite.

Remark 4.12

The corresponding results remain correct if S ¹×S ¹ is replaced by S ¹×S or by S×S ¹ in the Corollary 4.11.

Corollary 4.13

Let T be an ideal extension of an infinite semigroup S and let ρ⊆T ¹×T ¹ be a nonempty I-compatible relation. If for a finite simple graph D ₁ with a cycle, S is Cayley D ₁-saturated with respect to ρ, then for any finite simple graph D, S is Cayley D-saturated with respect to ρ.

Proof

Since D ₁ has a cycle and S is Cayley D ₁-saturated with respect to ρ, Cay(S,ρ) is a finite disjoint union of complete symmetric graphs by (2) of Theorem 4.9. Let D be a finite graph and V an infinite subset of S. Then there is an infinite subset U⊆V such that the elements of U lie in a same complete symmetric subgraph, and so U induces a subgraph in Cay(S,ρ) which is isomorphic to K _∞. This implies that D can be embedded in the subgraph of Cay(S,ρ) induced by U. Therefore D can be embedded in the subgraph of Cay(S,ρ) induced by V and so S is Cayley D-saturated with respect to ρ. □