Two generalizations of homogeneity in groups with applications to regular semigroups
HTML articles powered by AMS MathViewer
- by João Araújo and Peter J. Cameron PDF
- Trans. Amer. Math. Soc. 368 (2016), 1159-1188 Request permission
Abstract:
Let $X$ be a finite set such that $|X|=n$ and let $i\leqslant j \leqslant n$. A group $G\leqslant \mathcal {S}_{n}$ is said to be $(i,j)$-homogeneous if for every $I,J\subseteq X$, such that $|I|=i$ and $|J|=j$, there exists $g\in G$ such that $Ig\subseteq J$. (Clearly $(i,i)$-homogeneity is $i$-homogeneity in the usual sense.)
A group $G\leqslant \mathcal {S}_{n}$ is said to have the $k$-universal transversal property if given any set $I\subseteq X$ (with $|I|=k$) and any partition $P$ of $X$ into $k$ blocks, there exists $g\in G$ such that $Ig$ is a section for $P$. (That is, the orbit of each $k$-subset of $X$ contains a section for each $k$-partition of $X$.)
In this paper we classify the groups with the $k$-universal transversal property (with the exception of two classes of $2$-homogeneous groups) and the $(k-1,k)$-homogeneous groups (for $2<k\leqslant \lfloor \frac {n+1}{2}\rfloor$). As a corollary of the classification we prove that a $(k-1,k)$-homogeneous group is also $(k-2,k-1)$-homogeneous, with two exceptions; and similarly, but with no exceptions, groups having the $k$-universal transversal property have the $(k-1)$-universal transversal property.
A corollary of all the previous results is a classification of the groups that together with any rank $k$ transformation on $X$ generate a regular semigroup (for $1\leqslant k\leqslant \lfloor \frac {n+1}{2}\rfloor$).
The paper ends with a number of challenges for experts in number theory, group and/or semigroup theory, linear algebra and matrix theory.
References
- João Araújo, Mário Edmundo, and Steven Givant, $v^\ast$-algebras, independence algebras and logic, Internat. J. Algebra Comput. 21 (2011), no. 7, 1237–1257. MR 2863435, DOI 10.1142/S0218196711006923
- João Araújo and John Fountain, The origins of independence algebras, Semigroups and languages, World Sci. Publ., River Edge, NJ, 2004, pp. 54–67. MR 2170753, DOI 10.1142/9789812702616_{0}004
- 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
- João Araújo and Fernando C. Silva, Semigroups of linear endomorphisms closed under conjugation, Comm. Algebra 28 (2000), no. 8, 3679–3689. MR 1767581, DOI 10.1080/00927870008827049
- João Araújo and Fernando C. Silva, Semigroups of matrices closed under conjugation by normal linear groups, JP J. Algebra Number Theory Appl. 5 (2005), no. 3, 535–545. MR 2189966
- 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
- Robert W. Baddeley, Cheryl E. Praeger, and Csaba Schneider, Quasiprimitive groups and blow-up decompositions, J. Algebra 311 (2007), no. 1, 337–351. MR 2309892, DOI 10.1016/j.jalgebra.2006.11.006
- 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 and Priscila A. Kazanidis, Cores of symmetric graphs, J. Aust. Math. Soc. 85 (2008), no. 2, 145–154. MR 2470534, DOI 10.1017/S1446788708000815
- Peter J. Cameron and Csaba Szabó, Independence algebras, J. London Math. Soc. (2) 61 (2000), no. 2, 321–334. MR 1760686, DOI 10.1112/S0024610799008546
- 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
- The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.4.12, 2008.
- V. Gould, Independence algebras, Algebra Universalis 33 (1995), no. 3, 294–318. MR 1322776, DOI 10.1007/BF01190702
- L. Grunenfelder, M. Omladic, H. Radjavi, and A. Sourour, Semigroups generated by similarity orbits, Semigroup Forum 62 (2001), no. 3, 460–472. MR 1831467, DOI 10.1007/s002330010029
- Christoph Hering, Transitive linear groups and linear groups which contain irreducible subgroups of prime order, Geometriae Dedicata 2 (1974), 425–460. MR 335659, DOI 10.1007/BF00147570
- Christoph Hering, Transitive linear groups and linear groups which contain irreducible subgroups of prime order. II, J. Algebra 93 (1985), no. 1, 151–164. MR 780488, DOI 10.1016/0021-8693(85)90179-6
- D. G. Higman, Intersection matrices for finite permutation groups, J. Algebra 6 (1967), 22–42. MR 209346, DOI 10.1016/0021-8693(67)90011-7
- 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
- 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
- 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, 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
- Martin W. Liebeck and Jan Saxl, The finite primitive permutation groups of rank three, Bull. London Math. Soc. 18 (1986), no. 2, 165–172. MR 818821, DOI 10.1112/blms/18.2.165
- S. A. Linton, G. Pfeiffer, E. F. Robertson, and N. Ruškuc, Groups and actions in transformation semigroups, Math. Z. 228 (1998), no. 3, 435–450. MR 1637855, DOI 10.1007/PL00004628
- S. A. Linton, G. Pfeiffer, E. F. Robertson, and N. Ruškuc, Computing transformation semigroups, J. Symbolic Comput. 33 (2002), no. 2, 145–162. MR 1879378, DOI 10.1006/jsco.2000.0406
- 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
- 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
- Brendan D. McKay and Stanisław P. Radziszowski, The first classical Ramsey number for hypergraphs is computed, Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1991) ACM, New York, 1991, pp. 304–308. MR 1095846
- Peter M. Neumann, Generosity and characters of multiply transitive permutation groups, Proc. London Math. Soc. (3) 31 (1975), no. 4, 457–481. MR 382407, DOI 10.1112/plms/s3-31.4.457
- 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
- Alan L. T. Paterson, Groupoids, inverse semigroups, and their operator algebras, Progress in Mathematics, vol. 170, Birkhäuser Boston, Inc., Boston, MA, 1999. MR 1724106, DOI 10.1007/978-1-4612-1774-9
- C. S. Pazzis, The semigroup generated by the similarity class of a singular matrix, to appear.
- Stanisław P. Radzizowski, Small Ramsey numbers. Dynamic Survey DS1, Electronic J. Combinatorics, 72pp.
- K. P. S. Bhaskara Rao, Products of idempotent matrices over integral domains, Linear Algebra Appl. 430 (2009), no. 10, 2690–2695. MR 2509850, DOI 10.1016/j.laa.2008.11.018
- B. M. Šaĭn, A symmetric semigroup of transformations is covered by its inverse subsemigroups, Acta Math. Acad. Sci. Hungar. 22 (1971/72), 163–171 (Russian). MR 291330, DOI 10.1007/BF01896004
- L.H. Soicher, The GRAPE package for GAP, Version 4.3, 2006. +http://www.maths.qmul.ac.uk/$\sim$leonard/grape/+.
- D. E. Taylor, Regular $2$-graphs, Proc. London Math. Soc. (3) 35 (1977), no. 2, 257–274. MR 476587, DOI 10.1112/plms/s3-35.2.257
Additional Information
- João Araújo
- Affiliation: Universidade Aberta and Centro de Álgebra, Universidade de Lisboa, Av. Gama Pinto, 2, 1649-003 Lisboa, Portugal
- MR Author ID: 664908
- Email: jaraujo@ptmat.fc.ul.pt, jjrsga@gmail.com
- Peter J. Cameron
- Affiliation: Department of Mathematics, School of Mathematical Sciences at Queen Mary, University of London, London E1 4NS, United Kingdom
- MR Author ID: 44560
- ORCID: 0000-0003-3130-9505
- Email: pjc20@st-andrews.ac.uk
- Received by editor(s): April 10, 2012
- Received by editor(s) in revised form: December 11, 2012, and December 18, 2013
- Published electronically: July 1, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 1159-1188
- MSC (2010): Primary 20B30, 20B35, 20B15, 20B40, 20M20, 20M17
- DOI: https://doi.org/10.1090/tran/6368
- MathSciNet review: 3430360