Some combinatorial problems in the theory of partial transformation semigroups

A. Umar

Algebra and discrete mathematics, Tome 17 (2014) no. 1, pp. 110-134.

Résumé

Let $X_n = \{1, 2, \ldots , n\}$. On a partial transformation $\alpha : \mathop{\rm Dom}\nolimits \alpha \subseteq X_n \rightarrow \mathop{\rm Im}\alpha \subseteq X_n$ of $X_n$ the following parameters are defined: the breadth or width of $\alpha$ is $\mid\mathop{\rm Dom}\nolimits \alpha\mid$, the collapse of $\alpha$ is $c(\alpha)=\mid\cup_{t \in \mathop{\rm Im}\alpha}\{t \alpha^{-1}: \mid t\alpha^{-1}\mid \geq 2\}\mid$, fix of $\alpha$ is $f(\alpha) = \mid\{x \in X_n: x\alpha = x\}\mid$, the height of $\alpha$ is $\mid\mathop{\rm Im}\alpha\mid$, and the right [left] waist of $\alpha$ is $\max(\mathop{\rm Im}\alpha)\, [\min(\mathop{\rm Im}\alpha)]$. The cardinalities of some equivalences defined by equalities of these parameters on $\mathcal{T}_n$, the semigroup of full transformations of $X_n$, and $\mathcal{P}_n$ the semigroup of partial transformations of $X_n$ and some of their notable subsemigroups that have been computed are gathered together and the open problems highlighted.

Détail

Keywords: full transformation, breadth, collapse, height and right (left) waist of a transformation. Idempotents and nilpotents.
Mots-clés : partial transformation, fix

Bibliographie

[1] Aizenstat, Ya., “Defining relations of the endomorphism semigroup of a finite linearly ordered set”, Sibirsk Mat. Z., 3 (1962), 161–169 (Russian) | MR

[2] Borwein, D., Rankin, S. and Renner, L., “Enumeration of injective partial transformations”, Discrete Math., 73 (1989), 291–296 | DOI | MR | Zbl

[3] Cameron, P. J., “Sequences realized by oligomorphic permutation groups”, J. Integer Seq., 3 (2000), Article 00.1.5 | MR

[4] Catarino, P. M. and Higgins, P. M., “The monoid of orientation-preserving mappings on a chain”, Semigroup Forum, 58 (1999), 190–206 | DOI | MR | Zbl

[5] Clifford, A. H. and Preston, G. B., The algebraic theory of semigroups, v. 1, American Mathematical Society, Providence, R. I., 1961 | MR

[6] Comtet, L., Advanced Combinatorics: the art of finite and infinite expansions, ed. D. Reidel, Publishing Company, Dordrecht, Holland, 1974 | MR | Zbl

[7] Fernandes, V. H., Gomes, G. M. S. and Jesus, M. M., “Congruences on monoids of order-preserving transformations on a finite chain”, Glasgow Math Journal, 47 (2005), 413–424 | DOI | MR | Zbl

[8] Fernandes, V. H., Gomes, G. M. S. and Jesus, M. M., “Congruences on monoids of transformations preserving the orientation of a finite chain”, J. Algebra, 321 (2009), 743–757 | DOI | MR | Zbl

[9] Fernandes, V. H., Gomes, G. M. S. and Jesus, M. M., “The cardinal and idempotent number of various monoids of transformations on a finite chain”, Bull. Malays. Math. Sci. Soc., 34 (2011), 79–85 | MR | Zbl

[10] Ganyushkin, E. and Mazorchuk, V., “On the structure of IOn”, Semigroup Forum, 66 (2003), 455–483 | DOI | MR | Zbl

[11] Ganyushkin, O. and Mazorchuk, V., Classical Finite Transformation Semigroups: An Introduction, Springer, London, 2009 | MR | Zbl

[12] Garba, G. U., “Idempotents in partial transformation semigroups”, Proc. Roy. Soc. Edinburgh, 116A (1990), 359–366 | DOI | MR | Zbl

[13] Garba, G. U., “On the nilpotent ranks of partial transformation semigroups”, Portugal Mathematica, 51 (1994), 163–172 | MR | Zbl

[14] Garba, G. U., “On the nilpotent ranks of certain semigroups of transformations”, Glasgow Math. J., 36 (1994), 1–9 | DOI | MR | Zbl

[15] Garba, G. U., “On the idempotent ranks of certain semigroups of order-preserving transformations”, Portugal Mathematica, 51 (1994), 185–204 | MR | Zbl

[16] Gomes, G. M. S. and Howie, J. M., “On the ranks of certain semigroups of order-preserving transformations”, Semigroup Forum, 45 (1992), 272–282 | DOI | MR | Zbl

[17] Higgins, P. M., Techniques of semigroup theory, Oxford University Press, 1992 | MR | Zbl

[18] Higgins, P. M., “Combinatorial results for semigroups of order-preserving mappings”, Math. Proc. Camb. Phil. Soc., 113 (1993), 281–296 | DOI | MR | Zbl

[19] Higgins, P. M., “Idempotent depth in semigroups of order-preserving mappings”, Proc. Roy. Soc. Edinburgh, 124A (1994), 1045–1058 | DOI | MR | Zbl

[20] Howie, J. M., “The subsemigroup generated by the idempotents of a full transformation semigroups”, J. London Math. Soc., 41 (1966), 707–716 | DOI | MR | Zbl

[21] Howie, J. M., “Products of idempotents in certain semigroups of transformations”, Proc. Edinburgh Math. Soc., 17 (1971), 223–236 | DOI | MR | Zbl

[22] Howie, J. M., “Products of idempotent order-preserving transformations”, J. London Math. Soc., 7 (1973), 357–366 | DOI | MR | Zbl

[23] Howie, J. M., “Idempotent generators in finite full transformation semigroups”, Proc. Roy. Soc. Edinburgh, 81A (1978), 317–323 | DOI | MR | Zbl

[24] Howie, J. M., “Products of idempotents in finite full transformation semigroups”, Proc. Roy. Soc. Edinburgh, 86A (1980), 243–254 | DOI | MR | Zbl

[25] Howie, J. M., “Products of idempotents in finite full transformation semigroups: some improved bounds”, Proc. Roy. Soc. Edinburgh, 98A (1984), 25–35 | DOI | MR

[26] Howie, J. M., Robertson, E. F. and Schein, B. M., “A combinatorial property of finite full transformation semigroups”, Proc. Roy. Soc. Edinburgh, 109A (1988), 319–328 | DOI | MR | Zbl

[27] Howie, J. M. and McFadden, R. B., “Idempotent rank in finite full transformation semigroups”, Proc. Roy. Soc. Edinburgh, 114A (1990), 161–167 | DOI | MR | Zbl

[28] Howie, J. M., Lusk, E. L. and McFadden, R. B., “Combinatorial results relating to product of idempotents in finite full transformation semigroups”, Proc. Roy. Soc. Edinburgh, 115A (1990), 289–299 | DOI | MR | Zbl

[29] Howie, J. M., “Combinatorial and probabilistic results in transformation semigroups”, Words, languages and combinatorics (Kyoto, 1992), v. II, World Sci. Publ., River Edge, NJ, 1994, 200–206 | MR | Zbl

[30] Howie, J. M., Fundamentals of semigroup theory, Clarendon Press, Oxford, 1995 | MR | Zbl

[31] Iwahori, N., “A length formula in a semigroup of mappings”, J. Fac. Sci. Univ. Tokyo, Sect. 1A, 24 (1977), 255–260 | MR | Zbl

[32] Janson, S. and Mazorchuk, V., “Some remarks on the combinatorics of ISn”, Semigroup Forum, 109 (2005), 391–405 | DOI | MR

[33] Lallement, G., Semigroups and combinatorial applications, 1979, Wiley, New York | MR | Zbl

[34] Laradji, A. and Umar, A., “On the number of nilpotents in the partial symmetric semigroup”, Comm. Algebra, 32 (2004), 3017–3023 | DOI | MR | Zbl

[35] Laradji, A. and Umar, A., “On certain finite semigroups of order-decreasing transformations I”, Semigroup Forum, 69 (2004), 184–200 | DOI | MR | Zbl

[36] Laradji, A. and Umar, A., “Combinatorial results for semigroups of order-preserving partial transformations”, Journal of Algebra, 278 (2004), 342–359 | DOI | MR | Zbl

[37] Laradji, A. and Umar, A., “Combinatorial results for semigroups of order-decreasing partial transformations”, J. Integer Seq., 7 (2004), Article 04.3.8 | MR

[38] Laradji, A. and Umar, A., “Combinatorial results for semigroups of order-preserving full transformations”, Semigroup Forum, 72 (2006), 51–62 | DOI | MR | Zbl

[39] Laradji, A. and Umar, A., “Combinatorial results for the symmetric inverse semigroup”, Semigroup Forum, 75 (2007), 221–236 | DOI | MR | Zbl

[40] Laradji, A. and Umar, A., “Some combinatorial properties of the symmetric monoid”, Int. Journal of Alg. and Computations, 21 (2011), 857–865 | DOI | MR | Zbl

[41] Laradji, A. and Umar, A., Combinatorial results for semigroups of order-preserving or order-reversing partial transformations, submitted

[42] Liu, C. L., Introduction to combinatorial mathematics, McGraw Hill Company, New York, 1968 | MR | Zbl

[43] McAlister, D. B., “Semigroups generated by a group element and an idempotent”, Comm. Algebra, 26 (1998), 515–547 | DOI | MR | Zbl

[44] Riordan, J., Combinatorial Identities, John Wiley and Sons, New York, 1968 | MR | Zbl

[45] Saito, T., “Product of four idempotents in finite full transformation semigroups”, Semigroup Forum, 39 (1989), 179–193 | DOI | MR | Zbl

[46] Saito, T., “Products of idempotents in finite full transformation semigroups”, Semigroup Forum, 39 (1989), 295–309 | DOI | MR | Zbl

[47] The On-Line Encyclopedia of Integer Sequences, ed. Sloane, N. J. A., 2011 Available at http://oeis.org/

[48] Solomon, A., “Catalan monoids”, Semigroup Forum, 53 (1996), 351–368 | DOI | MR | Zbl

[49] Stanley, R. P., Enumerative Combinatorics, v. I, Cambridge University Press, 1997 | MR

[50] Tainiter, T., “A characterization of idempotents in semigroups”, J. Combinatorial Theory, 5 (1968), 370–373 | DOI | MR | Zbl

[51] Umar, A., Semigroups of order-decreasing transformations, Ph. D Thesis, University of St Andrews, 1992 | Zbl

[52] Umar, A., “On the semigroups of order-decreasing finite full transformations”, Proc. Roy. Soc. Edinburgh, 120A (1992), 129–142 | DOI | MR | Zbl

[53] Umar, A., “On certain infinite semigroups of order-decreasing full transformations I”, Comm. Algebra, 25 (1997), 2987–2999 | DOI | MR | Zbl

[54] Umar, A., “Enumeration of certain finite semigroups of transformations”, Discrete Math., 89 (1998), 291–297 | DOI | MR

[55] Umar, A., “Some combinatorial problems in the theory of symmetric inverse semigroups”, Algebra Discrete Math., 9:2 (2010), 115–126 | MR

[56] Umar, A., “Combinatorial results for semigroups of orientation-preserving partial transformations”, J. Integer Seq., 14 (2011), Article 11.7.5 | MR | Zbl