Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 
 

 

Two generalizations of homogeneity in groups with applications to regular semigroups


Authors: João Araújo and Peter J. Cameron
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
Published electronically: July 1, 2015
MathSciNet review: 3430360
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ X$ be a finite set such that $ \vert X\vert=n$ and let $ i\leq j \leq n$. A group $ G\leq \mathcal {S}_{n}$ is said to be $ (i,j)$-homogeneous if for every $ I,J\subseteq X$, such that $ \vert I\vert=i$ and $ \vert J\vert=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\leq \mathcal {S}_{n}$ is said to have the $ k$-universal transversal property if given any set $ I\subseteq X$ (with $ \vert I\vert=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\leq \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\leq k\leq \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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1142/S0218196711006923
  • [2] 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 (2006g:08008), https://doi.org/10.1142/9789812702616_0004
  • [3] 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 (2012g:20116), https://doi.org/10.1016/j.jalgebra.2011.07.002
  • [4] 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 (2001e:20061), https://doi.org/10.1080/00927870008827049
  • [5] 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 (2006i:20072)
  • [6] Fredrick Arnold and Benjamin Steinberg, Synchronizing groups and automata, Theoret. Comput. Sci. 359 (2006), no. 1-3, 101-110. MR 2251603 (2007i:68081), https://doi.org/10.1016/j.tcs.2006.02.003
  • [7] 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 (2008c:20002), https://doi.org/10.1016/j.jalgebra.2006.11.006
  • [8] Peter J. Cameron, Permutation groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999. MR 1721031 (2001c:20008)
  • [9] 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 (81c:20032), https://doi.org/10.1016/0021-8693(79)90090-5
  • [10] Peter J. Cameron and Priscila A. Kazanidis, Cores of symmetric graphs, J. Aust. Math. Soc. 85 (2008), no. 2, 145-154. MR 2470534 (2010a:05094), https://doi.org/10.1017/S1446788708000815
  • [11] Peter J. Cameron and Csaba Szabó, Independence algebras, J. London Math. Soc. (2) 61 (2000), no. 2, 321-334. MR 1760686 (2002b:08004), https://doi.org/10.1112/S0024610799008546
  • [12] John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR 1409812 (98m:20003)
  • [13] The GAP Group,
    GAP - Groups, Algorithms, and Programming, Version 4.4.12, 2008.
  • [14] V. Gould, Independence algebras, Algebra Universalis 33 (1995), no. 3, 294-318. MR 1322776 (96a:08007), https://doi.org/10.1007/BF01190702
  • [15] L. Grunenfelder, M. Omladic, H. Radjavi, and A. Sourour, Semigroups generated by similarity orbits, Semigroup Forum 62 (2001), no. 3, 460-472. MR 1831467 (2002g:20107), https://doi.org/10.1007/s002330010029
  • [16] Christoph Hering, Transitive linear groups and linear groups which contain irreducible subgroups of prime order, Geometriae Dedicata 2 (1974), 425-460. MR 0335659 (49 #439)
  • [17] 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 (86k:20046), https://doi.org/10.1016/0021-8693(85)90179-6
  • [18] D. G. Higman, Intersection matrices for finite permutation groups, J. Algebra 6 (1967), 22-42. MR 0209346 (35 #244)
  • [19] 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 (98e:20059)
  • [20] William M. Kantor, $ 4$-homogeneous groups, Math. Z. 103 (1968), 67-68. MR 0220812 (36 #3864)
  • [21] William M. Kantor, $ k$-homogeneous groups, Math. Z. 124 (1972), 261-265. MR 0306296 (46 #5422)
  • [22] William M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972), 315-318. MR 0377681 (51 #13850)
  • [23] William M. Kantor, Line-transitive collineation groups of finite projective spaces, Israel J. Math. 14 (1973), 229-235. MR 0326565 (48 #4908)
  • [24] 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 (2002k:20111), https://doi.org/10.1007/PL00006041
  • [25] I. Levi and R. B. McFadden, $ S_n$-normal semigroups, Proc. Edinburgh Math. Soc. (2) 37 (1994), no. 3, 471-476. MR 1297316 (95k:20103), https://doi.org/10.1017/S0013091500018927
  • [26] Inessa Levi, On the inner automorphisms of finite transformation semigroups, Proc. Edinburgh Math. Soc. (2) 39 (1996), no. 1, 27-30. MR 1375662 (96m:20106), https://doi.org/10.1017/S0013091500022732
  • [27] 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 (87i:20007), https://doi.org/10.1112/blms/18.2.165
  • [28] 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 (99e:20078), https://doi.org/10.1007/PL00004628
  • [29] 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 (2002k:20112), https://doi.org/10.1006/jsco.2000.0406
  • [30] Donald Livingstone and Ascher Wagner, Transitivity of finite permutation groups on unordered sets, Math. Z. 90 (1965), 393-403. MR 0186725 (32 #4183)
  • [31] Donald B. McAlister, Semigroups generated by a group and an idempotent, Comm. Algebra 26 (1998), no. 2, 515-547. MR 1604099 (99c:20090), https://doi.org/10.1080/00927879808826145
  • [32] 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
  • [33] Peter M. Neumann, Generosity and characters of multiply transitive permutation groups, Proc. London Math. Soc. (3) 31 (1975), no. 4, 457-481. MR 0382407 (52 #3291)
  • [34] Peter M. Neumann, Primitive permutation groups and their section-regular partitions, Michigan Math. J. 58 (2009), no. 1, 309-322. MR 2526090 (2010k:20005), https://doi.org/10.1307/mmj/1242071695
  • [35] 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 (2001a:22003)
  • [36] C. S. Pazzis, The semigroup generated by the similarity class of a singular matrix,
    to appear.
  • [37] Stanisław P. Radzizowski, Small Ramsey numbers. Dynamic Survey DS1, Electronic J. Combinatorics, 72pp.
  • [38] K. P. S. Bhaskara Rao, Products of idempotent matrices over integral domains, Linear Algebra Appl. 430 (2009), no. 10, 2690-2695. MR 2509850 (2010f:15032), https://doi.org/10.1016/j.laa.2008.11.018
  • [39] 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 0291330 (45 #424)
  • [40] L.H. Soicher,
    The GRAPE package for GAP, Version 4.3, 2006. +http://www.maths.qmul.ac.uk/$ \sim $leonard/grape/+.
  • [41] D. E. Taylor, Regular $ 2$-graphs, Proc. London Math. Soc. (3) 35 (1977), no. 2, 257-274. MR 0476587 (57 #16147)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20B30, 20B35, 20B15, 20B40, 20M20, 20M17

Retrieve articles in all journals with MSC (2010): 20B30, 20B35, 20B15, 20B40, 20M20, 20M17


Additional Information

João Araújo
Affiliation: Universidade Aberta and Centro de Álgebra, Universidade de Lisboa, Av. Gama Pinto, 2, 1649-003 Lisboa, Portugal
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
Email: pjc20@st-andrews.ac.uk

DOI: https://doi.org/10.1090/tran/6368
Keywords: Transformation semigroups, regular semigroups, permutation groups, primitive groups, homogeneous groups
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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society