Orbits of primitive $k$-homogenous groups on $(n-k)$-partitions with applications to semigroups
HTML articles powered by AMS MathViewer
- by João Araújo, Wolfram Bentz and Peter J. Cameron PDF
- Trans. Amer. Math. Soc. 371 (2019), 105-136 Request permission
Abstract:
The purpose of this paper is to advance our knowledge of two of the most classic and popular topics in transformation semigroups: automorphisms and the size of minimal generating sets. In order to do this, we examine the $k$-homogeneous permutation groups (those which act transitively on the subsets of size $k$ of their domain $X$) where $|X|=n$ and $k<n/2$. In the process we obtain, for $k$-homogeneous groups, results on the minimum numbers of generators, the numbers of orbits on $k$-partitions, and their normalizers in the symmetric group. As a sample result, we show that every finite $2$-homogeneous group is $2$-generated.
Underlying our investigations on automorphisms of transformation semigroups is the following conjecture:
For the special case that $S$ contains all constant maps, this conjecture was proved correct more than $40$ years ago. In this paper, we prove that the conjecture also holds for the case of semigroups containing a map of rank $3$ or less. The effort in establishing this result suggests that further improvements might be a great challenge. This problem and several additional ones on permutation groups, transformation semigroups, and computational algebra are proposed at the end of the paper.If a transformation semigroup $S$ contains singular maps and its group of units is a primitive group $G$ of permutations, then its automorphisms are all induced (under conjugation) by the elements in the normalizer of $G$ in the symmetric group.
References
- Jorge André, João Araújo, and Peter J. Cameron, The classification of partition homogeneous groups with applications to semigroup theory, J. Algebra 452 (2016), 288–310. MR 3461068, DOI 10.1016/j.jalgebra.2015.12.025
- João Araújo, On idempotent generated semigroups, Semigroup Forum 65 (2002), no. 1, 138–140. MR 1903561, DOI 10.1007/s002330010089
- João Araújo, Generators for the semigroup of endomorphisms of an independence algebra, Algebra Colloq. 9 (2002), no. 4, 375–382. MR 1933846, DOI 10.1017/S0013091500000729
- João Araújo, Wolfram Bentz, and Peter J. Cameron, Groups synchronizing a transformation of non-uniform kernel, Theoret. Comput. Sci. 498 (2013), 1–9. MR 3083510, DOI 10.1016/j.tcs.2013.06.016
- João Araújo, Wolfram Bentz, Peter J. Cameron, Gordon Royle, and Artur Schaefer, Primitive groups, graph endomorphisms and synchronization, Proc. Lond. Math. Soc. (3) 113 (2016), no. 6, 829–867. MR 3626847, DOI 10.1112/plms/pdw040
- João Araújo, Wolfram Bentz, James D. Mitchell, and Csaba Schneider, The rank of the semigroup of transformations stabilising a partition of a finite set, Math. Proc. Cambridge Philos. Soc. 159 (2015), no. 2, 339–353. MR 3395375, DOI 10.1017/S0305004115000389
- J. Araújo, W. Bentz, E. Dobson, J. Konieczny, and J. Morris, Automorphism groups of circulant digraphs with applications to semigroup theory. To appear in Combinatorica.
- J. Araújo, P. V. Bünau, J. D. Mitchell, and M. Neunhöffer, Computing automorphisms of semigroups, J. Symbolic Comput. 45 (2010), no. 3, 373–392. MR 2578344, DOI 10.1016/j.jsc.2009.10.001
- João Araújo and Peter J. Cameron, Primitive groups synchronize non-uniform maps of extreme ranks, J. Combin. Theory Ser. B 106 (2014), 98–114. MR 3194197, DOI 10.1016/j.jctb.2014.01.006
- João Araújo and Peter J. Cameron, Two generalizations of homogeneity in groups with applications to regular semigroups, Trans. Amer. Math. Soc. 368 (2016), no. 2, 1159–1188. MR 3430360, DOI 10.1090/tran/6368
- João Araújo, Peter J. Cameron, James D. Mitchell, and Max Neunhöffer, The classification of normalizing groups, J. Algebra 373 (2013), 481–490. MR 2995039, DOI 10.1016/j.jalgebra.2012.08.033
- João Araújo, Peter J. Cameron, and Benjamin Steinberg, Between primitive and 2-transitive: synchronization and its friends, EMS Surv. Math. Sci. 4 (2017), no. 2, 101–184. MR 3725240, DOI 10.4171/EMSS/4-2-1
- João Araújo, Edward Dobson, and Janusz Konieczny, Automorphisms of endomorphism semigroups of reflexive digraphs, Math. Nachr. 283 (2010), no. 7, 939–964. MR 2677280, DOI 10.1002/mana.200710033
- João Araújo, Vítor H. Fernandes, Manuel M. Jesus, Victor Maltcev, and James D. Mitchell, Automorphisms of partial endomorphism semigroups, Publ. Math. Debrecen 79 (2011), no. 1-2, 23–39. MR 2850032, DOI 10.5486/PMD.2011.4703
- João Araújo and Michael Kinyon, Inverse semigroups with idempotent-fixing automorphisms, Semigroup Forum 89 (2014), no. 2, 469–474. MR 3258495, DOI 10.1007/s00233-014-9585-0
- João Araújo and Janusz Konieczny, Automorphism groups of centralizers of idempotents, J. Algebra 269 (2003), no. 1, 227–239. MR 2015308, DOI 10.1016/S0021-8693(03)00499-X
- João Araújo and Janusz Konieczny, Automorphisms of endomorphism monoids of relatively free bands, Proc. Edinb. Math. Soc. (2) 50 (2007), no. 1, 1–21. MR 2294000, DOI 10.1017/S0013091505000672
- João Araújo and Janusz Konieczny, A method of finding automorphism groups of endomorphism monoids of relational systems, Discrete Math. 307 (2007), no. 13, 1609–1620. MR 2316670, DOI 10.1016/j.disc.2006.09.029
- João Araújo and Janusz Konieczny, Automorphisms of endomorphism monoids of 1-simple free algebras, Comm. Algebra 37 (2009), no. 1, 83–94. MR 2482811, DOI 10.1080/00927870802241204
- João Araújo and Janusz Konieczny, General theorems on automorphisms of semigroups and their applications, J. Aust. Math. Soc. 87 (2009), no. 1, 1–17. MR 2538636, DOI 10.1017/S1446788709000019
- J. Araújo and J. D. Mitchell, Relative ranks in the monoid of endomorphisms of an independence algebra, Monatsh. Math. 151 (2007), no. 1, 1–10. MR 2317387, DOI 10.1007/s00605-006-0433-5
- J. Araújo and J. D. Mitchell, An elementary proof that every singular matrix is a product of idempotent matrices, Amer. Math. Monthly 112 (2005), no. 7, 641–645. MR 2158897, DOI 10.2307/30037549
- J. Araújo, J. D. Mitchell, and Csaba Schneider, Groups that together with any transformation generate regular semigroups for idempotent generated semigroups, J. Algebra 343 (2011), 93–106. MR 2824546, DOI 10.1016/j.jalgebra.2011.07.002
- J. Araújo, J. D. Mitchell, and N. Silva, On generating countable sets of endomorphisms, Algebra Universalis 50 (2003), no. 1, 61–67. MR 2026827, DOI 10.1007/s00012-003-1809-1
- Fredrick Arnold and Benjamin Steinberg, Synchronizing groups and automata, Theoret. Comput. Sci. 359 (2006), no. 1-3, 101–110. MR 2251603, DOI 10.1016/j.tcs.2006.02.003
- V. S. Atabekyan, The automorphisms of endomorphism semigroups of free Burnside groups, Internat. J. Algebra Comput. 25 (2015), no. 4, 669–674. MR 3349110, DOI 10.1142/S0218196715500149
- George Barnes and Inessa Levi, Ranks of semigroups generated by order-preserving transformations with a fixed partition type, Comm. Algebra 31 (2003), no. 4, 1753–1763. MR 1972890, DOI 10.1081/AGB-120018506
- George Barnes and Inessa Levi, On idempotent ranks of semigroups of partial transformations, Semigroup Forum 70 (2005), no. 1, 81–96. MR 2107195, DOI 10.1007/s00233-004-0142-0
- R. A. Beaumont and R. P. Peterson, Set-transitive permutation groups, Canadian J. Math. 7 (1955), 35–42. MR 67889, DOI 10.4153/CJM-1955-005-x
- A. Belov-Kanel, A. Berzins, and R. Lipyanski, Automorphisms of the endomorphism semigroup of a free associative algebra, Internat. J. Algebra Comput. 17 (2007), no. 5-6, 923–939. MR 2355675, DOI 10.1142/S0218196707003901
- A. Belov-Kanel and R. Lipyanski, Automorphisms of the endomorphism semigroup of a polynomial algebra, J. Algebra 333 (2011), 40–54. MR 2785936, DOI 10.1016/j.jalgebra.2011.01.020
- A. Berzins, The group of automorphisms of the semigroup of endomorphisms of free commutative and free associative algebras, Internat. J. Algebra Comput. 17 (2007), no. 5-6, 941–949. MR 2355676, DOI 10.1142/S0218196707003949
- Peter J. Cameron, Permutation groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999. MR 1721031, DOI 10.1017/CBO9780511623677
- P. J. Cameron and W. M. Kantor, $2$-transitive and antiflag transitive collineation groups of finite projective spaces, J. Algebra 60 (1979), no. 2, 384–422. MR 549937, DOI 10.1016/0021-8693(79)90090-5
- Peter J. Cameron, Ron Solomon, and Alexandre Turull, Chains of subgroups in symmetric groups, J. Algebra 127 (1989), no. 2, 340–352. MR 1028457, DOI 10.1016/0021-8693(89)90256-1
- J. Cichoń, J. D. Mitchell, and M. Morayne, Generating continuous mappings with Lipschitz mappings, Trans. Amer. Math. Soc. 359 (2007), no. 5, 2059–2074. MR 2276612, DOI 10.1090/S0002-9947-06-04026-8
- John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR 1409812, DOI 10.1007/978-1-4612-0731-3
- J. A. Erdos, On products of idempotent matrices, Glasgow Math. J. 8 (1967), 118–122. MR 220751, DOI 10.1017/S0017089500000173
- Edward Formanek, A question of B. Plotkin about the semigroup of endomorphisms of a free group, Proc. Amer. Math. Soc. 130 (2002), no. 4, 935–937. MR 1873764, DOI 10.1090/S0002-9939-01-06155-X
- G. U. Garba, On the nilpotent ranks of certain semigroups of transformations, Glasgow Math. J. 36 (1994), no. 1, 1–9. MR 1260812, DOI 10.1017/S0017089500030482
- L. M. Gluskĭn, Semi-groups of isotone transformations, Uspehi Mat. Nauk 16 (1961), no. 5, 157–162 (Russian). MR 0131486
- Gracinda M. S. Gomes and John M. Howie, On the ranks of certain semigroups of order-preserving transformations, Semigroup Forum 45 (1992), no. 3, 272–282. MR 1179851, DOI 10.1007/BF03025769
- Olexandr Ganyushkin and Volodymyr Mazorchuk, Classical finite transformation semigroups, Algebra and Applications, vol. 9, Springer-Verlag London, Ltd., London, 2009. An introduction. MR 2460611, DOI 10.1007/978-1-84800-281-4
- The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.6.2, 2013, http://www.gap-system.org
- Robert M. Guralnick, Attila Maróti, and László Pyber, Normalizers of primitive permutation groups, Adv. Math. 310 (2017), 1017–1063. MR 3620702, DOI 10.1016/j.aim.2017.02.012
- P. M. Higgins, J. M. Howie, J. D. Mitchell, and N. Ruškuc, Countable versus uncountable ranks in infinite semigroups of transformations and relations, Proc. Edinb. Math. Soc. (2) 46 (2003), no. 3, 531–544. MR 2013951, DOI 10.1017/S0013091502000974
- Peter M. Higgins, John M. Howie, and Nikola Ruškuc, Generators and factorisations of transformation semigroups, Proc. Roy. Soc. Edinburgh Sect. A 128 (1998), no. 6, 1355–1369. MR 1663980, DOI 10.1017/S0308210500027360
- P. M. Higgins, J. D. Mitchell, M. Morayne, and N. Ruškuc, Rank properties of endomorphisms of infinite partially ordered sets, Bull. London Math. Soc. 38 (2006), no. 2, 177–191. MR 2214470, DOI 10.1112/S0024609305018138
- J. M. Howie, The subsemigroup generated by the idempotents of a full transformation semigroup, J. London Math. Soc. 41 (1966), 707–716. MR 219649, DOI 10.1112/jlms/s1-41.1.707
- John M. Howie, Fundamentals of semigroup theory, London Mathematical Society Monographs. New Series, vol. 12, The Clarendon Press, Oxford University Press, New York, 1995. Oxford Science Publications. MR 1455373
- John M. Howie and Robert B. McFadden, Idempotent rank in finite full transformation semigroups, Proc. Roy. Soc. Edinburgh Sect. A 114 (1990), no. 3-4, 161–167. MR 1055541, DOI 10.1017/S0308210500024355
- William M. Kantor, $4$-homogeneous groups, Math. Z. 103 (1968), 67–68. MR 220812, DOI 10.1007/BF01111290
- William M. Kantor, $k$-homogeneous groups, Math. Z. 124 (1972), 261–265. MR 306296, DOI 10.1007/BF01113919
- William M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972), 315–318. MR 377681, DOI 10.1007/BF01113923
- William M. Kantor, Line-transitive collineation groups of finite projective spaces, Israel J. Math. 14 (1973), 229–235. MR 326565, DOI 10.1007/BF02764881
- Janusz Konieczny, Automorphism groups of endomorphism monoids of free $G$-sets, Asian-Eur. J. Math. 7 (2014), no. 1, 1450015, 15. MR 3189584, DOI 10.1142/S1793557114500156
- R. Lipyanski, Automorphisms of the endomorphism semigroups of free linear algebras of homogeneous varieties, Linear Algebra Appl. 429 (2008), no. 1, 156–180. MR 2419147, DOI 10.1016/j.laa.2008.02.020
- Inessa Levi, Automorphisms of normal transformation semigroups, Proc. Edinburgh Math. Soc. (2) 28 (1985), no. 2, 185–205. MR 806750, DOI 10.1017/S001309150002263X
- Inessa Levi, Automorphisms of normal partial transformation semigroups, Glasgow Math. J. 29 (1987), no. 2, 149–157. MR 901661, DOI 10.1017/S0017089500006790
- Inessa Levi, On the inner automorphisms of finite transformation semigroups, Proc. Edinburgh Math. Soc. (2) 39 (1996), no. 1, 27–30. MR 1375662, DOI 10.1017/S0013091500022732
- I. Levi, On groups associated with transformation semigroups, Semigroup Forum 59 (1999), no. 3, 342–353. MR 1847649, DOI 10.1007/s002339900054
- Inessa Levi, Congruences on normal transformation semigroups, Math. Japon. 52 (2000), no. 2, 247–261. MR 1793274
- Inessa Levi, Nilpotent ranks of semigroups of partial transformations, Semigroup Forum 72 (2006), no. 3, 459–476. MR 2228540, DOI 10.1007/s00233-005-0538-5
- I. Levi, D. B. McAlister, and R. B. McFadden, Groups associated with finite transformation semigroups, Semigroup Forum 61 (2000), no. 3, 453–467. MR 1832320, DOI 10.1007/PL00006041
- I. Levi and R. B. McFadden, $S_n$-normal semigroups, Proc. Edinburgh Math. Soc. (2) 37 (1994), no. 3, 471–476. MR 1297316, DOI 10.1017/S0013091500018927
- Inessa Levi and Steve Seif, Combinatorial techniques for determining rank and idempotent rank of certain finite semigroups, Proc. Edinb. Math. Soc. (2) 45 (2002), no. 3, 617–630. MR 1933743, DOI 10.1017/S0013091501000530
- A. E. Liber, On symmetric generalized groups, Mat. Sbornik N.S. 33(75) (1953), 531–544 (Russian). MR 0059268
- Martin W. Liebeck, The affine permutation groups of rank three, Proc. London Math. Soc. (3) 54 (1987), no. 3, 477–516. MR 879395, DOI 10.1112/plms/s3-54.3.477
- Donald Livingstone and Ascher Wagner, Transitivity of finite permutation groups on unordered sets, Math. Z. 90 (1965), 393–403. MR 186725, DOI 10.1007/BF01112361
- Andrea Lucchini and Federico Menegazzo, Generators for finite groups with a unique minimal normal subgroup, Rend. Sem. Mat. Univ. Padova 98 (1997), 173–191. MR 1492976
- A. Lucchini, F. Menegazzo, and M. Morigi, Asymptotic results for transitive permutation groups, Bull. London Math. Soc. 32 (2000), no. 2, 191–195. MR 1734189, DOI 10.1112/S0024609399006591
- A. Lucchini, F. Menegazzo, and M. Morigi, Asymptotic results for primitive permutation groups and irreducible linear groups, J. Algebra 223 (2000), no. 1, 154–170. MR 1738257, DOI 10.1006/jabr.1999.8081
- Tomasz Łuczak and László Pyber, On random generation of the symmetric group, Combin. Probab. Comput. 2 (1993), no. 4, 505–512. MR 1264722, DOI 10.1017/S0963548300000869
- K. D. Magill Jr., Semigroups of continuous functions, Amer. Math. Monthly 71 (1964), 984–988. MR 192464, DOI 10.2307/2311913
- Kenneth D. Magill Jr., Semigroup structures for families of functions. I. Some homomorphism theorems, J. Austral. Math. Soc. 7 (1967), 81–94. MR 0207875
- A. I. Mal′cev, Symmetric groupoids, Mat. Sbornik N.S. 31(73) (1952), 136–151 (Russian). MR 0050576
- G. Mashevitzky and B. I. Plotkin, On automorphisms of the endomorphism semigroup of a free universal algebra, Internat. J. Algebra Comput. 17 (2007), no. 5-6, 1085–1106. MR 2355687, DOI 10.1142/S0218196707003974
- G. Mashevitzky, B. Plotkin, and E. Plotkin, Automorphisms of the category of free Lie algebras, J. Algebra 282 (2004), no. 2, 490–512. MR 2101073, DOI 10.1016/j.jalgebra.2003.09.038
- G. Mashevitzky and Boris M. Schein, Automorphisms of the endomorphism semigroup of a free monoid or a free semigroup, Proc. Amer. Math. Soc. 131 (2003), no. 6, 1655–1660. MR 1953569, DOI 10.1090/S0002-9939-03-06923-5
- Donald B. McAlister, Semigroups generated by a group and an idempotent, Comm. Algebra 26 (1998), no. 2, 515–547. MR 1604099, DOI 10.1080/00927879808826145
- Annabelle McIver and Peter M. Neumann, Enumerating finite groups, Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 152, 473–488. MR 916229, DOI 10.1093/qmath/38.4.473
- Peter M. Neumann, Primitive permutation groups and their section-regular partitions, Michigan Math. J. 58 (2009), no. 1, 309–322. MR 2526090, DOI 10.1307/mmj/1242071695
- John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, N.J., 1944. MR 0011937
- B. I. Plotkin. Seven Lectures on the Universal Algebraic Geometry. Preprint, Institute of Mathematics, Hebrew University (2000).
- B. Plotkin and G. Zhitomirski, Automorphisms of categories of free algebras of some varieties, J. Algebra 306 (2006), no. 2, 344–367. MR 2271339, DOI 10.1016/j.jalgebra.2006.07.028
- Boris Plotkin and Grigori Zhitomirski, On automorphisms of categories of universal algebras, Internat. J. Algebra Comput. 17 (2007), no. 5-6, 1115–1132. MR 2355689, DOI 10.1142/S0218196707004098
- Maria Isabel Marques Ribeiro, Rank properties in finite inverse semigroups, Proc. Edinburgh Math. Soc. (2) 43 (2000), no. 3, 559–568. MR 1878658, DOI 10.1017/S0013091500021192
- I. K. Rystsov, Quasioptimal bound for the length of reset words for regular automata, Acta Cybernet. 12 (1995), no. 2, 145–152. MR 1370976
- J. Schreier, Über Abbildungen einer abstrakten Menge Auf ihre Teilmengen, Fund. Math. 28 (1936), 261–264.
- R. P. Sullivan, Automorphisms of transformation semigroups. part 1, J. Austral. Math. Soc. 20 (1975), no. part 1, 77–84. MR 0372095
- È. G. Šutov, Homomorphisms of the semigroup of all partial transformations, Izv. Vysš. Učebn. Zaved. Matematika 1961 (1961), no. 3 (22), 177–184 (Russian). MR 0150223
- J. S. V. Symons, Normal transformation semigroups, J. Austral. Math. Soc. Ser. A 22 (1976), no. 4, 385–390. MR 437668, DOI 10.1017/s1446788700016232
- Haobo Yang and Xiuliang Yang, Automorphisms of partition order-decreasing transformation monoids, Semigroup Forum 85 (2012), no. 3, 513–524. MR 3001597, DOI 10.1007/s00233-012-9430-2
- Helmut Wielandt, Finite permutation groups, Academic Press, New York-London, 1964. Translated from the German by R. Bercov. MR 0183775
Additional Information
- João Araújo
- Affiliation: Universidade Aberta and CEMAT-CIÊNCIAS, Departamento de Matemática, Faculdade de Ciências, Universidade de Lisboa, 1749-016, Lisboa, Portugal
- MR Author ID: 664908
- Email: jaraujo@ptmat.fc.ul.pt
- Wolfram Bentz
- Affiliation: School of Mathematics & Physical Sciences, University of Hull, Kingston upon Hull, HU6 7RX, United Kingdom
- MR Author ID: 641226
- Email: w.bentz@hull.ac.uk
- Peter J. Cameron
- Affiliation: School of Mathematics and Statistics, University of St Andrews, St Andrews, Fife KY16 9SS, United Kingdom
- MR Author ID: 44560
- ORCID: 0000-0003-3130-9505
- Email: pjc20@st-andrews.ac.uk
- Received by editor(s): December 28, 2015
- Received by editor(s) in revised form: January 17, 2017, and January 29, 2017
- Published electronically: May 3, 2018
- Additional Notes: The first author is the corresponding author.
This work was developed within FCT project CEMAT-CIÊNCIAS (UID/Multi/04621/2013). - © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 371 (2019), 105-136
- MSC (2010): Primary 20B30, 20B35, 20B15, 20B40, 20M20, 20M17
- DOI: https://doi.org/10.1090/tran/7274
- MathSciNet review: 3885139