On certain finite semigroups of order-decreasing transformations. I.

DOI10.1007/S00233-004-0101-9MaRDI QIDQ706041zbMATH OpenOpenAlexFDO

Publication date 16 February 2005

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00233-004-0101-9

Green relations products of idempotents transformation semigroups

Exact enumeration problems, generating functions (05A15) Free semigroups, generators and relations, word problems (20M05) Semigroups of transformations, relations, partitions, etc. (20M20)

Review text

Let \(X_n=\{1,2,\dots,n\}\) and denote by \(T_n\) the full transformation semigroup on \(X_n\). A transformation \(\alpha\in T_n\) is `order-decreasing' if \(x\alpha\leq x\) for all \(x\in X_n\) and it is `order-increasing' if \(x\alpha\geq x\) for all \(x\in X_n\). The transformation \(\alpha\) is `order-preserving' if \(x\alpha\leq y\alpha\) whenever \(x\leq y\) for all \(x,y\in X_n\). The symbol \(D_n\) denotes the semigroup of all order-decreasing transformations on \(X_n\) and the symbol \(C_n\) denotes the semigroup of all order-preserving transformations on \(X_n\). For \(1\leq r\leq n\), let \(D(n,r)=\{\alpha\in D_n:|X_n\alpha|\leq r\}\) and let \(C(n,r)=\{\alpha\in C_n:|X_n\alpha|\leq r\}\). For \(r\geq 2\), let \(DP_r(n)=D(n,r)/D(n,r-1)\) and let \(CP_r(n)=C(n,r)/C(n,r-1)\). The authors prove that every element in \(DP_r(n)\) is a product of idempotents and, similarly, every element in \(CP_r(n)\) is a product of idempotents. Let \(\mathcal H\), \(\mathcal L\), \(\mathcal R\), \(\mathcal D\), and \(\mathcal J\) denote the usual Green's relations. The authors show that \({\mathcal H}={\mathcal R}\) and \({\mathcal L}={\mathcal D}={\mathcal J}\) on \(DP_r(n)\) and \({\mathcal H}={\mathcal L}={\mathcal R}={\mathcal D}={\mathcal J}\) on \(CP_r(n)\). Recall that the relation \({\mathcal L}^*\) on a semigroup \(S\) is defined by \((a,b)\in{\mathcal L}^*\) if and only if \((a,b)\in{\mathcal L}\) where \({\mathcal L}^*\) is Green's \({\mathcal L}\)-relation on some semigroup \(T\) which contains \(S\) as a subsemigroup. The \({\mathcal R}^*\)-relation is defined dually and \({\mathcal H}^*\) and \({\mathcal D}^*\) are defined by \({\mathcal H}^*={\mathcal L}^*\cap{\mathcal R}^*\), and \({\mathcal D}^*={\mathcal L}^*\vee{\mathcal R}^*\). A subsemigroup \(T\) of \(S\) is referred to as an `inverse ideal' (which need not be an ideal) if for each element \(a\in T\) there exists an element \(b\in S\) such that \(aba=a\) and \(ab,ba\in T\). The authors prove that both \(DP_r(n)\) and \(CP_r(n)\) are inverse ideals of \(P_r(n)\). They go on to determine the \({\mathcal L}^*\), \({\mathcal R}^*\), and \({\mathcal H}^*\) relations on both \(DP_r(n)\) and \(CP_r(n)\). They then show that \(|CP_r(n)|=\tfrac 1{n-r-1}{n-1\choose r-1}{n\choose r}+1\). The rank of a finite semigroup \(S\) is denoted by \(\text{rank\,}S\) and defined by \(\text{rank\,}S=\min\{|A|: A\subseteq S\) and \(\langle A\rangle=S\}\). Similarly, if \(S\) is generated by its set \(E\) of idempotents, the idempotent rank of \(S\) is denoted by \(\text{idrank\,}S\) and defined by \(\text{idrank\,}S=\min\{|A|:A\subseteq E\) and \(\langle A\rangle=S\}\). In the main result of the concluding section of the paper, the authors prove that if \(1\leq r\leq n-1\), then \(\text{rank\,}C(n,r)=\text{idrank\,}C(n,r)=\text{rank\,}CP_r(n)= \text{idrank\,} CP_r(n)={n-1\choose r-1}\).

Recommendations

Cited in

(31)

This page was built for publication: On certain finite semigroups of order-decreasing transformations. I.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q706041)