The existential transversal property: A generalization of homogeneity and its impact on semigroups
Authors:
João Araújo, Wolfram Bentz and Peter J. Cameron
Journal:
Trans. Amer. Math. Soc. 374 (2021), 1155-1195
MSC (2020):
Primary 20B30, 20B35, 20B15, 20M20, 20M17
DOI:
https://doi.org/10.1090/tran/8285
Published electronically:
December 3, 2020
Full-text PDF
Abstract | References | Similar Articles | Additional Information
Abstract: Let be a permutation group of degree
, and
a positive integer with
. We say that
has the
-existential transversal property, or
-et, if there exists a
-subset
(of the domain
) whose orbit under
contains transversals for all
-partitions
of
. This property is a substantial weakening of the
-universal transversal property, or
-ut, investigated by the first and third author, which required this condition to hold for all
-subsets
of the domain
.
Our first task in this paper is to investigate the -et property and to decide which groups satisfy it. For example, it is known that for
there are several families of
-transitive groups, but for
the only ones are alternating or symmetric groups; here we show that in the
-et context the threshold is
, that is, for
, the only transitive groups with
-et are the symmetric and alternating groups; this is best possible since the Mathieu group
(degree 24) has
-et. We determine all groups with
-et for
, up to some unresolved cases for
, and describe the property for
in permutation group language. These considerations essentially answer Problem 5 proposed in the paper on
-ut referred to above; we also slightly improve the classification of groups possessing the
-ut property.
In that earlier paper, the results were applied to semigroups, in particular, to the question of when the semigroup is regular, where
is a map of rank
(with
); this turned out to be equivalent to the
-ut property. The question investigated here is when there is a
-subset
of the domain such that
is regular for all maps
with image
. This turns out to be much more delicate; the
-et property (with
as witnessing set) is a necessary condition, and the combination of
-et and
-ut is sufficient, but the truth lies somewhere between.
Given the knowledge that a group under consideration has the necessary condition of -et, the regularity question for
is solved except for one sporadic group.
The paper ends with a number of problems on combinatorics, permutation groups and transformation semigroups, and their linear analogues.
- [1] 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, https://doi.org/10.1016/j.jalgebra.2015.12.025
- [2] 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, https://doi.org/10.1016/j.tcs.2013.06.016
- [3] João Araújo, Wolfram Bentz, and Peter J. Cameron, Orbits of primitive 𝑘-homogenous groups on (𝑛-𝑘)-partitions with applications to semigroups, Trans. Amer. Math. Soc. 371 (2019), no. 1, 105–136. MR 3885139, https://doi.org/10.1090/tran/7274
- [4] 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, https://doi.org/10.1112/plms/pdw040
- [5] João Araújo, Wolfram Bentz, Edward Dobson, Janusz Konieczny, and Joy Morris, Automorphism groups of circulant digraphs with applications to semigroup theory, Combinatorica 38 (2018), no. 1, 1–28. MR 3776345, https://doi.org/10.1007/s00493-016-3403-0
- [6] 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, https://doi.org/10.1016/j.jctb.2014.01.006
- [7] 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, https://doi.org/10.1090/S0002-9947-2015-06368-5
- [8] 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, https://doi.org/10.1016/j.jalgebra.2012.08.033
- [9] 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, https://doi.org/10.4171/EMSS/4-2-1
- [10] 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, https://doi.org/10.1016/j.jalgebra.2011.07.002
- [11] Fredrick Arnold and Benjamin Steinberg, Synchronizing groups and automata, Theoret. Comput. Sci. 359 (2006), no. 1-3, 101–110. MR 2251603, https://doi.org/10.1016/j.tcs.2006.02.003
- [12] Zs. Baranyai, On the factorization of the complete uniform hypergraph, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, North-Holland, Amsterdam, 1975, pp. 91–108. Colloq. Math. Soc. Ján\B{o}s Bolyai, Vol. 10. MR 0416986
- [13] Csilla Bujtás and Zsolt Tuza, Smallest set-transversals of 𝑘-partitions, Graphs Combin. 25 (2009), no. 6, 807–816. MR 2600478, https://doi.org/10.1007/s00373-010-0890-4
- [14] Timothy C. Burness, Martin W. Liebeck, and Aner Shalev, Base sizes for simple groups and a conjecture of Cameron, Proc. Lond. Math. Soc. (3) 98 (2009), no. 1, 116–162. MR 2472163, https://doi.org/10.1112/plms/pdn024
- [15] Peter J. Cameron, Dixon’s theorem and random synchronization, Discrete Math. 313 (2013), no. 11, 1233–1236. MR 3034755, https://doi.org/10.1016/j.disc.2012.06.002
- [16] John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR 1409812
- [17] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.9.1, http://www.gap-system.org/
- [18] Chris Godsil and Gordon F. Royle, Cores of geometric graphs, Ann. Comb. 15 (2011), no. 2, 267–276. MR 2813515, https://doi.org/10.1007/s00026-011-0094-5
- [19] William M. Kantor, 4-homogeneous groups, Math. Z. 103 (1968), 67–68. MR 220812, https://doi.org/10.1007/BF01111290
- [20] William M. Kantor, 𝑘-homogeneous groups, Math. Z. 124 (1972), 261–265. MR 306296, https://doi.org/10.1007/BF01113919
- [21] William M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972), 315–318. MR 377681, https://doi.org/10.1007/BF01113923
- [22] 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, https://doi.org/10.1007/PL00006041
- [23] Martin W. Liebeck, The affine permutation groups of rank three, Proc. London Math. Soc. (3) 54 (1987), no. 3, 477–516. MR 879395, https://doi.org/10.1112/plms/s3-54.3.477
- [24] Charles H. C. Little, Douglas D. Grant, and D. A. Holton, On defect-𝑑 matchings in graphs, Discrete Math. 13 (1975), no. 1, 41–54. MR 416981, https://doi.org/10.1016/0012-365X(75)90085-0
- [25] Donald Livingstone and Ascher Wagner, Transitivity of finite permutation groups on unordered sets, Math. Z. 90 (1965), 393–403. MR 186725, https://doi.org/10.1007/BF01112361
- [26] Peter M. Neumann, Primitive permutation groups and their section-regular partitions, Michigan Math. J. 58 (2009), no. 1, 309–322. MR 2526090, https://doi.org/10.1307/mmj/1242071695
- [27] Stanisław P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. 1 (1994), Dynamic Survey 1, 30. MR 1670625
- [28] Pablo Spiga and Gabriel Verret, Vertex-primitive digraphs having vertices with almost equal neighbourhoods, European J. Combin. 61 (2017), 235–241. MR 3588719, https://doi.org/10.1016/j.ejc.2016.11.002
- [29] D. E. Taylor, Regular 2-graphs, Proc. London Math. Soc. (3) 35 (1977), no. 2, 257–274. MR 476587, https://doi.org/10.1112/plms/s3-35.2.257
- [30] Donald E. Taylor, The geometry of the classical groups, Sigma Series in Pure Mathematics, vol. 9, Heldermann Verlag, Berlin, 1992. MR 1189139
- [31] Mark E. Watkins, Connectivity of transitive graphs, J. Combinatorial Theory 8 (1970), 23–29. MR 266804
Retrieve articles in Transactions of the American Mathematical Society with MSC (2020): 20B30, 20B35, 20B15, 20M20, 20M17
Retrieve articles in all journals with MSC (2020): 20B30, 20B35, 20B15, 20M20, 20M17
Additional Information
João Araújo
Affiliation:
Department of Mathematics and Centre for Mathematics and Applications (CMA), Faculdade de Ciências e Tecnologia (FCT) Universidade Nova de Lisboa (UNL), 2829-516 Caparica, Portugal; and CEMAT-Ciências, Faculdade de Ciências, Universidade de Lisboa 1749–016, Lisboa, Portugal
Email:
jj.araujo@fct.unl.pt, jjaraujo@fc.ul.pt
Wolfram Bentz
Affiliation:
Centre for Mathematics and Applications (CMA), Faculdade de Ciêcias e Tecnologia (FCT), Universidade Nova de Lisboa (UNL), 2829-516, Caparica, Portugal; and Universidade Aberta, R. Escola Politécnica, 147, 1269-001 Lisboa, Portugal; and Department of Physics and Mathematics, University of Hull, Kingston upon Hull, HU6 7RX, United Kingdom
Email:
Wolfram.Bentz@uab.pt
Peter J. Cameron
Affiliation:
School of Mathematics and Statistics, University of St Andrews, North Haugh, St Andrews, Fife KY16 9SS, United Kingdom
Email:
pjc20@st-andrews.ac.uk
DOI:
https://doi.org/10.1090/tran/8285
Keywords:
Transformation semigroups,
regular semigroups,
permutation groups,
primitive groups,
homogeneous groups.
Received by editor(s):
February 18, 2019
Received by editor(s) in revised form:
February 26, 2020, and May 26, 2020
Published electronically:
December 3, 2020
Additional Notes:
The corresponding author is W. Bentz
The first author was partially supported by the Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) through the projects UIDB/00297/2020 (Centro de Matemáica e Aplicações), PTDC/MAT-PUR/31174/2017, UIDB/04621/2020 and UIDP/04621/2020.
The second author was supported by travel grants from the University of Hull’s Faculty of Science and Engineering and the Center for Computational and Stochastic Mathematics.
Article copyright:
© Copyright 2020
American Mathematical Society