Primitive groups, graph endomorphisms and synchronization

DOI10.1112/PLMS/PDW040MaRDI QIDQ2960608zbMATH OpenOpenAlexFDO

Authors João Araújo, Wolfram Bentz, Peter J. Cameron, Gordon Royle, Artur Schäfer

Publication date 17 February 2017

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.01629, http://hdl.handle.net/10023/9648

zbMATH Keywords

graphs with primitive automorphism groupssynchronizing group

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Primitive groups (20B15) Semigroups of transformations, relations, partitions, etc. (20M20)

Abstract: Let $Omega$ be a set of cardinality $n$, $G$ a permutation group on $Omega$, and $f:OmegaoOmega$ a map which is not a permutation. We say that $G$ emph{synchronizes} $f$ if the transformation semigroup $langleG,fangle$ contains a constant map, and that $G$ is a emph{synchronizing group} if $G$ synchronizes emph{every} non-permutation. A synchronizing group is necessarily primitive, but there are primitive groups that are not synchronizing. Every non-synchronizing primitive group fails to synchronize at least one uniform transformation (that is, transformation whose kernel has parts of equal size), and it has previously been conjectured that a primitive group synchronizes every non-uniform transformation. The first goal of this paper is to prove that this conjecture is false, by exhibiting primitive groups that fail to synchronize specific non-uniform transformations of ranks $5$ and $6$. In addition we produce graphs whose automorphism groups have approximately $sqrtn$ emph{non-synchronizing ranks}, thus refuting another conjecture on the number of non-synchronizing ranks of a primitive group. The second goal of this paper is to extend the spectrum of ranks for which it is known that primitive groups synchronize every non-uniform transformation of that rank. It has previously been shown that a primitive group of degree $n$ synchronizes every non-uniform transformation of rank $n-1$ and $n-2$, and here this is extended to $n-3$ and $n-4$. Determining the exact spectrum of ranks for which there exist non-uniform transformations not synchronized by some primitive group is just one of several natural, but possibly difficult, problems on automata, primitive groups, graphs and computational algebra arising from this work; these are outlined in the final section.

Recommendations

• Primitive groups synchronize non-uniform maps of extreme ranks
• Between primitive and 2-transitive: synchronization and its friends
• Primitive permutation groups and their section-regular partitions.
• Groups synchronizing a transformation of non-uniform kernel
• Imprimitive groups synchronizing a transformation of non-uniform kernel

Cites work

• Between primitive and 2-transitive: synchronization and its friends
• Completing the spectrum of \(r\)-orthogonal Latin squares
• Cores of geometric graphs
• CORES OF SYMMETRIC GRAPHS
• Dixon's theorem and random synchronization
• Finite group theory.
• Groups synchronizing a transformation of non-uniform kernel
• Groups that together with any transformation generate regular semigroups or idempotent generated semigroups.
• scientific article; zbMATH DE number 50655 (Why is no real title available?)
• scientific article; zbMATH DE number 827994 (Why is no real title available?)
• scientific article; zbMATH DE number 846959 (Why is no real title available?)
• Idempotent generated endomorphisms of an independence algebra.
• Independence Algebras
• Independence algebras
• Kantenprimitive Graphen vom Grad drei
• Minimal Degrees of Primitive Permutation Groups, with an Application to Monodromy Groups of Covers of Riemann Surfaces
• On Trivalent Graphs
• On two Combinatorial Problems Arising from Automata Theory
• Primitive groups synchronize non-uniform maps of extreme ranks
• Primitive permutation groups and their section-regular partitions.
• Products of idempotent endomorphisms of an independence algebra of finite rank
• Products of idempotent endomorphisms of an independence algebra of infinite rank
• Relative ranks in the monoid of endomorphisms of an independence algebra.
• Self-stabilizing systems in spite of distributed control
• SOME RESULTS ON ČERNÝ TYPE PROBLEMS FOR TRANSFORMATION SEMIGROUPS
• Synchronization
• Synchronizing generalized monotonic automata
• Synchronizing groups and automata
• The Affine Permutation Groups of Rank Three
• The Chords of the Non-Ruled Quadric In PG(3, 3)
• The Chords of the Non-Ruled Quadric In PG(3, 3)
• The classification of normalizing groups.
• The classification of partition homogeneous groups with applications to semigroup theory
• The Finite Primitive Permutation Groups of Rank Three
• The largest subsemilattices of the endomorphism monoid of an independence algebra.
• The origins of independence algebras
• The Rank 3 Permutation Representations of the Finite Classical Groups
• The Černý conjecture for aperiodic automata
• Three Remarkable Graphs
• Two generalizations of homogeneity in groups with applications to regular semigroups
• v*-ALGEBRAS, INDEPENDENCE ALGEBRAS AND LOGIC
• Vertex-primitive digraphs having vertices with almost equal neighbourhoods

Cited in

(22)

• Primitive permutation groups and their section-regular partitions.
• On two problems of almost synchronizing groups
• Congruences on direct products of transformation and matrix monoids
• Imprimitive groups synchronizing a transformation of non-uniform kernel
• Primitive permutation groups and strongly factorizable transformation semigroups
• The Hall-Paige conjecture, and synchronization for affine and diagonal groups
• Imprimitive permutations in primitive groups
• A transversal property for permutation groups motivated by partial transformations
• The structure of a type of affine primitive non-synchronizing groups
• Permutation groups and transformation semigroups: results and problems.
• Dixon's theorem and random synchronization
• Groups synchronizing a transformation of non-uniform kernel
• Primitive groups synchronize non-uniform maps of extreme ranks
• Orbits of primitive k-homogeneous groups on (n-k)-partitions with applications to semigroups
• The existential transversal property: a generalization of homogeneity and its impact on semigroups
• The classification of partition homogeneous groups with applications to semigroup theory
• Synchronising primitive groups of diagonal type exist
• New characterizations of primitive permutation groups with applications to synchronizing automata
• Adding a transformation to imprimitive transitive groups
• The hereditariness problem for the Černý conjecture
• Conjugacy in abstract semigroups, transformation and diagram monoids and conjugacy growth
• Vertex-primitive digraphs having vertices with almost equal neighbourhoods

Describes a project that uses

Uses Software

• MINION

This page was built for publication: Primitive groups, graph endomorphisms and synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2960608)