Generators and relations for subsemigroups via boundaries in Cayley graphs. (Q640935): Difference between revisions

Let \(S\) be a semigroup with a subsemigroup \(T\). The Rees index of \(T\) in \(S\) is defined to be the cardinality of the set \(S \setminus T\). \textit{A. Jura}, in [``Some remarks on non-existence of an algorithm for finding all ideals of a given finite index in a finitely presented semigroup,'' Demonstr. Math. 13, 573--578 (1980; Zbl 0465.20056)], proved that if \(S\) is a finitely generated semigroup and \(T\) is a subsemigroup of \(S\) with finite Rees index then \(T\) is finitely generated. This result was reproved by \textit{N. Ruškuc} in [``On large subsemigroups and finiteness conditions of semigroups,'' Proc. Lond. Math. Soc., III. Ser. 76, No.\,2, 383--405 (1998; Zbl 0891.20036)], where, in addition, it was also shown that subsemigroups of finitely presented semigroups with finite Rees index are themselves finitely presented. In this paper, the authors introduce a new notion of index for subsemigroups which is significantly weaker than the Rees index but is still strong enough to force \(T\) to inherit certain properties from \(S\). Let \(S\) be a finitely generated semigroup with a subsemigroup \(T\). Let \(A\) be a finite generating set of \(S\). Let \(\Gamma_r(A,S)\) and \(\Gamma_l(A,S)\) denote the right and left Cayley graphs of \(S\) with respect to \(A\). The vertices of \(\Gamma_r(A,S)\) are the elements of \(S\) and there is a directed edge from \(s\) to \(t\), labelled with \(a\in A\), if and only if \(sa=t\). The left Cayley graph of \(S\) is defined analogously. Right boundary edges of \(T\) in \(\Gamma_r(A,S)\) are defined as those edges whose initial vertex is in \(U=S-T\) and terminal vertex is in \(T\). Define the right boundary \(\mathcal B_r(A,T)\) of \(T\) in \(S\) with respect to \(A\) to be the set of terminal vertices of the right boundary edges of \(T\) in \(\Gamma_r(A,S)\) together with the elements of \(A\) that belong to \(T\). The left boundary \(\mathcal B_l(A,T)\) of \(T\) in \(S\) with respect to \(A\) is defined similarly. Define the (two-sided) boundary \(\mathcal B(A,T)\) of \(T\) in \(S\) with respect to \(A\) to be the union of the right and left boundaries. The subsemigroup \(T\) is said to have a finite boundary in \(S\) if for some finite generating set \(A\) of \(S\) the boundary \(\mathcal B(A,T)\) is finite. The main results are the following two theorems. If \(S\) is a finitely generated semigroup and \(T\) is a subsemigroup of \(S\) with finite boundary then \(T\) is finitely generated. Let \(S\) be a semigroup and \(T\) be a subsemigroup of \(S\). If \(S\) is finitely presented and \(T\) has a finite boundary in \(S\) then \(T\) is finitely presented. Some illustrative examples, applications and corollaries of the main results are given.