Untitled

Funder

Organizational Unit

Publications

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

Publication . Araújo, João; Bentz, Wolfram; Cameron, Peter

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 transversal property, or k-et, if there exists a k-subset A (of the domain Ω) whose orbit un- der 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 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 ≥ 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.

2021Journal article

Restricted access

Primitive permutation groups and strongly factorizable transformation semigroups

Publication . Araújo, João; Bentz, Wolfram; Cameron, Peter

Let Ω be a finite set and T (Ω) be the full transformation monoid on Ω. The rank of a transformation t ∈ T (Ω) is the natural number |Ωt|. Given A ⊆ T (Ω), denote by 〈A〉 the semigroup generated by A. Let k be a fixed natural number such that 2 ≤ k ≤ |Ω|. In the first part of this paper we (almost) classify the permutation groups G on Ω such that for all rank k transformations t ∈ T (Ω), every element in St := 〈G, t〉 can be written as a product eg, where e2 = e ∈ St and g ∈ G. In the second part we prove, among other results, that if S ≤ T (Ω) and G is the normalizer of S in the symmetric group on Ω, then the semigroup SG is regular if and only if S is regular. (Recall that a semigroup S is regular if for all s ∈ S there exists s′ ∈ S such that s = ss′s.) The paper ends with a list of problems.

2021-01-01Journal article

Open access

A transversal property for permutation groups motivated by partial transformations

Publication . Araújo, João; Araújo, João Pedro; Bentz, Wolfram; Cameron, Peter; Spiga, Pablo

In this paper we introduce the definition of the (k, l)-universal transversal property for permutation groups, which is a refinement of the definition of k-universal transversal property, which in turn is a refine- ment of the classical definition of k-homogeneity for permutation groups. In particular, a group possesses the (2, n)-universal transversal property if and only if it is primitive; it possesses the (2, 2)-universal transversal property if and only if it is 2-homogeneous. Up to a few undecided cases, we give a classification of groups satisfying the (k, l)-universal transversal property, for k ≥ 3. Then we apply this result for studying regular semigroups of partial transformations.

2021-05-01Journal article

Open access