A combinatorial property and Cayley graphs of semigroups (Q1864447): Difference between revisions

Analogously to the Cayley graphs of groups, the Cayley graphs of semigroups are studied here. Let \(S\) be a semigroup and let \(T\) be a subset. The Cayley graph \(\text{Cay}(S,T)\) is the directed graph whose vertex set is \(S\) and in which an edge goes from \(u\) to \(v\) if and only if \(u\neq v\) and \(v=ut\) for some \(t\in T\). Now let \(D\) be a finite digraph. A semigroup \(S\) is said to be Cayley \(D\)-saturated with respect to a subset \(T\) of \(S\), if for each infinite subset \(V\) of \(T\) there exists a subgraph of \(\text{Cay}(S,T)\) isomorphic to \(D\). The main results of the paper are the following two theorems. Theorem 2.1. Let \(D\) be a finite graph which is not null, and let \(S\) be an infinite semigroup. Then the following conditions are equivalent: (i) \(S\) is Cayley \(D\)-saturated with respect to \(S\); (ii) \(S\) does not have an infinite set of pairwise incomparable principal right ideals, and if \(D\) has a cycle, then the number of principal right ideals in \(S\) is finite. Theorem 2.2. Let \(D\) be a finite graph which is not null. Each infinite semigroup \(S\) has an infinite subset \(T\) such that \(S\) is not \(D\)-saturated with respect to \(T\).