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)



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
Published electronically: December 3, 2020
MathSciNet review: 4196390
Full-text PDF

Abstract | References | Similar Articles | Additional Information


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 [Enhancements On Off] (What's this?)


Similar Articles

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
MR Author ID: 664908

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

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

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