Browsing by Author "Cameron, Peter J."
Now showing 1 - 5 of 5
Results Per Page
Sort Options
- Between primitive and 2-transitive: synchronization and its friendsPublication . Araújo, João; Cameron, Peter J.; Steinberg, BenjaminAn automaton is said to be synchronizing if there is a word in the transitions which sends all states of the automaton to a single state. Research on this topic has been driven by the Černý conjecture, one of the oldest and most famous problems in automata theory, according to which a synchronizing n-state automaton has a reset word of length at most (n-1)2. The transitions of an automaton generate a transformation monoid on the set of states, and so an automaton can be regarded as a transformation monoid with a prescribed set of generators. In this setting, an automaton is synchronizing if the transitions generate a constant map. A permutation group G on a set Ω is said to synchronize a map f if the monoid ⟨G,f⟩ fi generated by G and f is synchronizing in the above sense; we say G is synchronizing if it synchronizes every non-permutation. The classes of synchronizing groups and friends form an hierarchy of natural and elegant classes of groups lying strictly between the classes of primitive and 2-homogeneous groups. These classes have been floating around for some years and it is now time to provide a unified reference on them. The study of all these classes has been prompted by the Černý conjecture, but it is of independent interest since it involves a rich mix of group theory, combinatorics, graph endomorphisms, semigroup theory, finite geometry, and representation theory, and has interesting computational aspects as well. So as to make the paper self-contained, we have provided background material on these topics. Our purpose here is to present results that show the connections between the various areas of mathematics mentioned above, we include a new result on the Černý conjecture, some challenges to finite geometers, some thoughts about infinite analogues, and a long list of open problems.
- 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.
- Primitive groups synchronize non-uniform maps of extreme ranksPublication . Araújo, João; Cameron, Peter J.Let Ω be a set of cardinality n, G a permutation group on Ω, and f : Ω → Ω a map which is not a permutation. We say that G synchronizes f if the semigroup hG, fi contains a constant map.The first author has conjectured that a primitive group synchronizes any map whose kernel is non-uniform. Rystsov proved one instance of this conjecture, namely, degree n primitive groups synchronize maps of rank n − 1 (thus, maps with kernel type (2, 1, . . . , 1)). We prove some extensions of Rystsov’s result,including this: a primitive group synchronizes every map whose kernel type is (k, 1, . . . , 1). Incidentally this result provides a new characterization of imprimitive groups. We also prove that the conjecture above holds for maps of extreme ranks, that is, ranks 3, 4 and n − 2. These proofs use a graph-theoretic technique due to the second author: a transformation semigroup fails to contain a constant map if and only if it is contained in the endomorphism semigroup of a non-null (simple undirected) graph. The paper finishes with a number of open problems, whose solutions will certainly require very delicate graph theoretical considerations.
- The classification of normalizing groupsPublication . Araújo, João; Cameron, Peter J.; Mitchell, James D.; Max, NeunhöfferLet X be a finite set such that |X|=n. Let Tn and Sn denote the transformation monoid and the symmetric group on n points, respectively. Given a∈Tn∖Sn, we say that a group G⩽Sn is a-normalizing if ,where a, G and g−1ag | g ∈ G denote the subsemigroups of Tn generated by the sets {a} ∪ G and {g−1ag | g ∈ G}, respectively. If G is a-normalizing for all a ∈ Tn \ Sn, then we say that G is normalizing.The goal of this paper is to classify the normalizing groups and hence answer a question of Levi, McAlister, and McFadden. The paper ends with a number of problems for experts in groups, semigroups and matrix theory.
- Two generalizations of homogeneity in groups with applications to regular semigroupsPublication . Araújo, João; Cameron, Peter J.Let X be a finite set such that |X| = n and let i 6 j 6 n. A group G 6 Sn is said to be (i, j)-homogeneous if for every I, J ⊆ X, such that |I| = i and |J| = j, there exists g ∈ G such that Ig ⊆ J. (Clearly (i, i)-homogeneity is i-homogeneity in the usual sense.) A group G 6 Sn is said to have the k-universal transversal property if given any set I ⊆ X (with |I| = k) and any partition P of X into k blocks, there exists g ∈ G such that Ig is a section for P. (That is, the orbit of each k-subset of X contains a section for each k-partition of X.) In this paper we classify the groups with the k-universal transversal property (with the exception of two classes of 2-homogeneous groups) and the (k−1, k)-homogeneous groups (for 2 < k 6 ⌊n+12 ⌋). As a corollary of the classification we prove that a (k − 1, k homogeneous group is also (k − 2, k − 1)-homogeneous, with two exceptions; and similarly, but with no exceptions, groups having the k-universal transversal property have the (k − 1)-universal transversal property. A corollary of all the previous results is a classification of the groups that together with any rank k transformation on X generate a regular semigroup (for 1 6 k 6 ⌊n+1 2 ⌋). The paper ends with a number of challenges for experts in number theory, group and/or semigroup theory, linear algebra and matrix theory.