Center for Computational and Stochastic Mathematics

Funder

Organizational Unit

Publications

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

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

Improving the conditioning of the method of fundamental solutions for the Helmholtz equation on domains in polar or elliptic coordinates

Publication . Antunes, Pedro R. S.; Calunga, Hernani; Serranho, Pedro

A new approach to overcome the ill-conditioning of the Method of Fundamental Solutions (MFS) combining Singular Value Decomposition (SVD) and an adequate change of basis was introduced in [1] as MFS-SVD. The original formulation considered polar coordinates and harmonic polynomials as basis functions and is restricted to the Laplace equation in 2D. In this work, we start by adapting the approach to the Helmholtz equation in 2D and later extending it to elliptic coordinates. As in the Laplace case, the approach in polar coordinates has very good numerical results both in terms of conditioning and accuracy for domains close to a disk but does not perform so well for other domains, such as an eccentric ellipse. We therefore consider the MFS-SVD approach in elliptic coordinates with Mathieu functions as basis functions for the latter. We illustrate the feasibility of the approach by numerical examples in both cases.

2024Journal article

Embargoed access