Abstract
Let G be a permutation group of degree n, and k a positive integer with k ≤ n. We say that G has the k-existential property, or k-et, if there exists a k-subset A (of the domain Ω) whose orbit under G contains transversals for all k-partitions P of Ω. 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 Ω.
Our first task in this paper is to investigate the k-et property a≤nd 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 ≥ 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 ≤ k ≤ n/2, the only transitive groups with k-et are the symmetric and alternating groups; this is best possible since the Mathieu group M24 (degree 24) has 7-et. We determine all groups with k-et for 4 ≤ k ≤ 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 <G,t> 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 <G,t> 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 ≤ 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.
Our first task in this paper is to investigate the k-et property a≤nd 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 ≥ 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 ≤ k ≤ n/2, the only transitive groups with k-et are the symmetric and alternating groups; this is best possible since the Mathieu group M24 (degree 24) has 7-et. We determine all groups with k-et for 4 ≤ k ≤ 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 <G,t> 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 <G,t> 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 ≤ 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.
| Original language | English |
|---|---|
| Pages (from-to) | 1155–1195 |
| Journal | Transactions of the American Mathematical Society |
| Volume | 374 |
| Issue number | 2 |
| Early online date | 3 Dec 2020 |
| DOIs | |
| Publication status | Published - Feb 2021 |
Keywords
- Transformation semigroups
- Regular semigroups
- Permutation groups
- Primitive groups
- Homeogenous groups
