Loading...
8 results
Search Results
Now showing 1 - 8 of 8
- The existential transversal property: a generalization of homogeneity and its impact on semigroupsPublication . Araújo, João; Bentz, Wolfram; Cameron, PeterLet 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.
- Primitive permutation groups and strongly factorizable transformation semigroupsPublication . Araújo, João; Bentz, Wolfram; Cameron, PeterLet Ω 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.
- The commuting graph of the symmetric inverse semigroupPublication . Araújo, João; Bentz, Wolfram; Konieczny, JanuszThe commuting graph of a finite non-commutative semigroup S, denoted G(S), is a simple graph whose vertices are the non-central elements of S and two distinct vertices x, y are adjacent if xy = yx. Let I(X) be the symmetric inverse semigroup of partial injective transformations on a finite set X. The semigroup I(X) has the symmetric group Sym(X) of permutations on X as its group of units. In 1989, Burns and Goldsmith determined the clique number of the commuting graph of Sym(X). In 2008, Iranmanesh and Jafarzadeh found an upper bound of the diameter of G(Sym(X)), and in 2011, Dol˘zan and Oblak claimed that this upper bound is in fact the exact value.The goal of this paper is to begin the study of the commuting graph of the symmetric inverse semigroup I(X). We calculate the clique number of G(I(X)), the diameters of the commuting graphs of the proper ideals of I(X), and the diameter of G(I(X)) when |X| is even or a power of an odd prime. We show that when |X| is odd and divisible by at least two primes, then the diameter of G(I(X)) is either 4 or 5. In the process, we obtain several results about semigroups, such as a description of all commutative subsemigroups of I(X) of maximum order, and analogous results for commutative inverse and commutative nilpotent subsemigroups of I(X). The paper closes with a number of problems for experts in combinatorics and in group or semigroup theory.
- Independence algebras, basis algebras and the distributivity conditionPublication . Bentz, Wolfram; Gould, VictoriaStable basis algebras were introduced by Fountain and Gould and developed in a series of articles. They form a class of universal algebras, extending that of independence algebras, and reflecting the way in which free modules over well-behaved domains generalise vector spaces. If a stable basis algebra B satisfies the distributivity condition (a condition satisfied by all the previously known examples), it is a reduct of an independence algebra A. Our first aim is to give an example of an independence algebra not satisfying the distributivity condition. Gould showed that if a stable basis algebra B with the distributivity condition has finite rank, then so does the independence algebra A of which it is a reduct, and that in this case the endomorphism monoid End(B) of B is a left order in the endomorphism monoid End(A) of A. We complete the picture by determining when End(B) is a right, and hence a two-sided, order in End(A). In fact (for rank at least 2), this happens precisely when every element of End(A) can be written as α]β where α, β ∈ End(B), α] is the inverse of α in a subgroup of End(A) and α and β have the same kernel. This is equivalent to End(B) being a special kind of left order in End(A) known as straight.
- A transversal property for permutation groups motivated by partial transformationsPublication . Araújo, João; Araújo, João Pedro; Bentz, Wolfram; Cameron, Peter; Spiga, PabloIn 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.
- Matrix theory for independence algebrasPublication . Araújo, João; Bentz, Wolfram; Cameron, Peter; Kinyon, Michael; Konieczny, JanuszA universal algebra A with underlying set A is said to be a matroid algebra if (A, 〈·〉), where 〈·〉 denotes the operator subalgebra generated by, is a matroid. A matroid algebra is said to be an independence algebra if every mapping α : X → A defined on a minimal generating X of A can be extended to an endomorphism of A. These algebras are particularly well-behaved generalizations of vector spaces, and hence they naturally appear in several branches of mathematics, such as model theory, group theory, and semigroup theory. It is well known that matroid algebras have a well-defined notion of dimension. Let A be any independence algebra of finite dimension n, with at least two elements. Denote by End(A) the monoid of endomorphisms of A. In the 1970s, Glazek proposed the problem of extending the matrix theory for vector spaces to a class of universal algebras which included independence algebras. In this paper, we answer that problem by developing a theory of matrices for (almost all) finite-dimensional independence algebras. In the process of solving this, we explain the relation between the classification of inde- pendence algebras obtained by Urbanik in the 1960s, and the classification of finite indepen- dence algebras up to endomorphism-equivalence obtained by Cameron and Szab ́o in 2000. (This answers another question by experts on independence algebras.) We also extend the classification of Cameron and Szab ́o to all independence algebras. The paper closes with a number of questions for experts on matrix theory, groups, semi- groups, universal algebra, set theory or model theory.
- Groups synchronizing a transformation of non-uniform kernelPublication . Araújo, João; Bentz, Wolfram; Cameron, Peter J.Suppose that a deterministic finite automata A = (Q ,Σ) is such that all but one letters from the alphabet Σ act as permutations of the state set Q and the exceptional letter acts as a transformation with non-uniform kernel. Which properties of the permutation group G generated by the letters acting as permutations ensure that A becomes a synchronizing automaton under every possible choice of the exceptional letter (provided the exceptional letter acts as a transformation of non-uniform kernel)? Such permutation groups are called almost synchronizing. It is easy to see that an almost synchronizing group must be primitive; our conjecture is that every primitive group is almost synchronizing. Clearly every synchronizing group is almost synchronizing. In this paper we provide two different methods to find non-synchronizing, but almost synchronizing groups. The infinite families of examples provided by the two different methods have few overlaps. The paper closes with a number of open problems on group theory and combinatorics.
- The largest subsemilattices of the endomorphism monoid of an independence algebraPublication . Araújo, João; Bentz, Wolfram; Konieczny, JanuszAn algebra A is said to be an independence algebra if it is a matroid algebra and every map α:X→A, defined on a basis X of A, can be extended to an endomorphism of A. These algebras are particularly well-behaved generalizations of vector spaces, and hence they naturally appear in several branches of mathematics such as model theory, group theory, and semigroup theory. It is well known that matroid algebras have a well-defined notion of dimension. Let A be any independence algebra of finite dimension n , with at least two elements. Denote by End(A) the monoid of endomorphisms of A. We prove that a largest subsemilattice of End(A) has either 2n−1 elements (if the clone of A does not contain any constant operations) or 2n elements (if the clone of A contains constant operations). As corollaries, we obtain formulas for the size of the largest subsemilattices of: some variants of the monoid of linear operators of a finite-dimensional vector space, the monoid of full transformations on a finite set X, the monoid of partial transformations on X, the monoid of endomorphisms of a free G-set with a finite set of free generators, among others. The paper ends with a relatively large number of problems that might attract attention of experts in linear algebra, ring theory, extremal combinatorics, group theory, semigroup theory, universal algebraic geometry, and universal algebra.