×

On the ranks of certain monoids of transformations that preserve a uniform partition. (English) Zbl 1290.20053

Summary: The rank of a semigroup, an important and relevant concept in Semigroup Theory, is the cardinality of a least-size generating set. Semigroups of transformations that preserve or reverse the order or the orientation as well as semigroups of transformations preserving an equivalence relation have been widely studied over the past decades by many authors. The purpose of this article is to compute the ranks of the monoid \(\mathcal{OR}_{m\times n}\) of all orientation-preserving or orientation-reversing full transformations on a chain with \(mn\) elements that preserve a uniform \(m\)-partition and of its submonoids \(\mathcal{OP}_{m\times n}\) of all orientation-preserving transformations and \(\mathcal{OD}_{m\times n}\) of all order-preserving or order-reversing full transformations. These three monoids are natural extensions of \(\mathcal O_{m\times n}\), the monoid of all order-preserving full transformations on a chain with \(mn\) elements that preserve a uniform \(m\)-partition. Given \(m,n\geq 2\), we show that the rank of \(\mathcal{OP}_{m\times n}\) is equal to \(2n+\lceil\tfrac{n-1}2\rceil+1\), for \(m>2\), and equal to \(n+\lceil\tfrac{n-1}2\rceil+1\), for \(m=2\), the rank of \(\mathcal{OD}_{m\times n}\) is equal to \(\lceil\tfrac{mn}2\rceil+\lceil\tfrac{(m-1)n}2\rceil+1\) and the rank of \(\mathcal{OR}_{m\times n}\) is equal to \(\lceil\tfrac n2\rceil+\lceil\tfrac{n-1}2\rceil+2\), for \(m>2\), and equal to \(\lceil\tfrac n2\rceil+\lceil\tfrac{n-1}2\rceil+2\), for \(m=2\). These results have quite nontrivial proofs and were intuited by performing massive calculations with GAP [The GAP Group (2008). GAP – Groups, Algorithms, and Programming, Version 4.4.12. http://www.gap-system.org], a system for computational discrete algebra. Moreover, in this article, we also determine the ranks of certain semigroups of orientation-preserving full transformations with restricted ranges.

MSC:

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

Software:

GAP
Full Text: DOI

References:

[1] Aĭzenštat A. Y., Uch. Zap. Leningr. Gos. Pedagog. Inst. 238 pp 38– (1962)
[2] Aĭzenštat A. Y., Sb. Math. 3 pp 161– (1962)
[3] DOI: 10.1007/s00233-008-9122-0 · Zbl 1176.20059 · doi:10.1007/s00233-008-9122-0
[4] DOI: 10.1007/s10012-000-0001-1 · Zbl 0973.20049 · doi:10.1007/s10012-000-0001-1
[5] Catarino , P. M. ( 1998 ). Monoids of orientation-preserving transformations of a finite chain and their presentations.Proc. of the Conference in St Andrews, Scotland, 1997, pp. 39–46 . · Zbl 0968.20033
[6] DOI: 10.1007/s002339900014 · Zbl 0919.20041 · doi:10.1007/s002339900014
[7] DOI: 10.1080/00927870008827033 · Zbl 0952.20048 · doi:10.1080/00927870008827033
[8] DOI: 10.1081/AGB-200047446 · Zbl 1072.20079 · doi:10.1081/AGB-200047446
[9] DOI: 10.1017/S0017089505002648 · Zbl 1083.20056 · doi:10.1017/S0017089505002648
[10] DOI: 10.1016/j.jalgebra.2008.11.005 · Zbl 1167.20035 · doi:10.1016/j.jalgebra.2008.11.005
[11] DOI: 10.1007/s00233-010-9220-7 · Zbl 1207.20059 · doi:10.1007/s00233-010-9220-7
[12] DOI: 10.1080/00927872.2010.492043 · Zbl 1235.20056 · doi:10.1080/00927872.2010.492043
[13] Fernandes V. H., Bull. Malays. Math. Sci. Soc. (2012)
[14] DOI: 10.1007/BF03025769 · Zbl 0769.20029 · doi:10.1007/BF03025769
[15] DOI: 10.1017/S0013091500026936 · Zbl 0226.20072 · doi:10.1017/S0013091500026936
[16] DOI: 10.1007/s00233-004-0135-z · Zbl 1100.20043 · doi:10.1007/s00233-004-0135-z
[17] DOI: 10.1081/AGB-200040921 · Zbl 1072.20082 · doi:10.1081/AGB-200040921
[18] DOI: 10.1007/s00233-005-0514-0 · Zbl 1101.20031 · doi:10.1007/s00233-005-0514-0
[19] DOI: 10.1080/00927879808826145 · Zbl 0893.20045 · doi:10.1080/00927879808826145
[20] DOI: 10.1007/s00233-007-0704-z · Zbl 1124.20044 · doi:10.1007/s00233-007-0704-z
[21] The GAP Group ( 2008 ).GAP – Groups, Algorithms, and Programming, Version 4.4.12; (http://www.gap-system.org) .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.