## The existential transversal property: A generalization of homogeneity and its impact on semigroups

HTML articles powered by AMS MathViewer

- by João Araújo, Wolfram Bentz and Peter J. Cameron PDF
- Trans. Amer. Math. Soc.
**374**(2021), 1155-1195 Request permission

## Abstract:

Let $G$ be a permutation group of degree $n$, and $k$ a positive integer with $k\le n$. We say that $G$ has the *$k$-existential transversal property*, or *$k$-et*, if there exists a $k$-subset $A$ (of the domain $\Omega$) whose orbit under $G$ contains transversals for all $k$-partitions $\mathcal {P}$ of $\Omega$. This property is a substantial weakening of the $k$-universal transversal property, or $k$-ut, investigated by the first and third author, which required this condition to hold for all $k$-subsets $A$ of the domain $\Omega$.

Our first task in this paper is to investigate the $k$-et property and to decide which groups satisfy it. For example, it is known that for $k< 6$ there are several families of $k$-transitive groups, but for $k\ge 6$ the only ones are alternating or symmetric groups; here we show that in the $k$-et context the threshold is $8$, that is, for $8\le k\le n/2$, the only transitive groups with $k$-et are the symmetric and alternating groups; this is best possible since the Mathieu group $M_{24}$ (degree 24) has $7$-et. We determine all groups with $k$-et for $4\le k\le n/2$, up to some unresolved cases for $k=4,5$, and describe the property for $k=2,3$ in permutation group language. These considerations essentially answer Problem 5 proposed in the paper on $k$-ut referred to above; we also slightly improve the classification of groups possessing the $k$-ut property.

In that earlier paper, the results were applied to semigroups, in particular, to the question of when the semigroup $\langle G,t\rangle$ is regular, where $t$ is a map of rank $k$ (with $k<n/2$); this turned out to be equivalent to the $k$-ut property. The question investigated here is when there is a $k$-subset $A$ of the domain such that $\langle G, t\rangle$ is regular for all maps $t$ with image $A$. This turns out to be much more delicate; the $k$-et property (with $A$ as witnessing set) is a necessary condition, and the combination of $k$-et and $(k-1)$-ut is sufficient, but the truth lies somewhere between.

Given the knowledge that a group under consideration has the necessary condition of $k$-et, the regularity question for $k\le n/2$ 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.

## 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, 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, and Peter J. Cameron,
*Orbits of primitive $k$-homogenous groups on $(n-k)$-partitions with applications to semigroups*, Trans. Amer. Math. Soc.**371**(2019), no. 1, 105–136. MR**3885139**, DOI 10.1090/tran/7274 - 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, 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**, DOI 10.1007/s00493-016-3403-0 - 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 - 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 - 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 - 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, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 91–108. MR**0416986** - Csilla Bujtás and Zsolt Tuza,
*Smallest set-transversals of $k$-partitions*, Graphs Combin.**25**(2009), no. 6, 807–816. MR**2600478**, DOI 10.1007/s00373-010-0890-4 - 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**, DOI 10.1112/plms/pdn024 - Peter J. Cameron,
*Dixon’s theorem and random synchronization*, Discrete Math.**313**(2013), no. 11, 1233–1236. MR**3034755**, DOI 10.1016/j.disc.2012.06.002 - 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.9.1,*http://www.gap-system.org/ - Chris Godsil and Gordon F. Royle,
*Cores of geometric graphs*, Ann. Comb.**15**(2011), no. 2, 267–276. MR**2813515**, DOI 10.1007/s00026-011-0094-5 - 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 - 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 - 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 - Charles H. C. Little, Douglas D. Grant, and D. A. Holton,
*On defect-$d$ matchings in graphs*, Discrete Math.**13**(1975), no. 1, 41–54. MR**416981**, DOI 10.1016/0012-365X(75)90085-0 - 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 - 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 - Stanisław P. Radziszowski,
*Small Ramsey numbers*, Electron. J. Combin.**1**(1994), Dynamic Survey 1, 30. MR**1670625** - Pablo Spiga and Gabriel Verret,
*Vertex-primitive digraphs having vertices with almost equal neighbourhoods*, European J. Combin.**61**(2017), 235–241. MR**3588719**, DOI 10.1016/j.ejc.2016.11.002 - 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 - Donald E. Taylor,
*The geometry of the classical groups*, Sigma Series in Pure Mathematics, vol. 9, Heldermann Verlag, Berlin, 1992. MR**1189139** - Mark E. Watkins,
*Connectivity of transitive graphs*, J. Combinatorial Theory**8**(1970), 23–29. MR**266804**

## 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
- MR Author ID: 664908
- 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
- MR Author ID: 641226
- 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
- MR Author ID: 44560
- ORCID: 0000-0003-3130-9505
- Email: pjc20@st-andrews.ac.uk
- 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. - © Copyright 2020 American Mathematical Society
- 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
- MathSciNet review: 4196390