Between primitive and $2$-transitive: Synchronization and its friends

Abstract

An 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 $\Omega$ is said to synchronize a map $f$ if the monoid $⟨G,f⟩$ 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.

References in corpus (2)

• Fast Synchronization of Random Automata
• Primitive groups and synchronization

Cited by in corpus (14)

• The Hall--Paige conjecture, and synchronization for affine and diagonal groups
• Primitive groups and synchronization
• Preimage problems for deterministic finite automata
• Primitivity, Uniform Minimality and State Complexity of Boolean Operations
• The geometry of diagonal groups
• Reset thresholds of transformation monoids
• Spreading primitive groups of diagonal type do not exist
• Constrained Synchronization for Commutative Automata and Automata with Simple Idempotents
• On Completely Reachable Automata and Subset Reachability
• Simplicity of augmentation submodules for transformation monoids
• Automorphisms of shift spaces and the Higman--Thompson groups: the one-sided case
• On the interplay between Babai and Cerny's conjectures
• An automata theoretic proof that $\mathrm{Out}(T)\cong \mathbb{Z}/2\mathbb{Z}$ and some embedding results for $\mathrm{Out}(V)$
• The road problem and homomorphisms of directed graphs