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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [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

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

Peter J. Cameron
Affiliation: School of Mathematics and Statistics, University of St Andrews, North Haugh, St Andrews, Fife KY16 9SS, United Kingdom

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