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 \v{C}ern\'y 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⟩
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 \v{C}ern\'y 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 \v{C}ern\'y conjecture, some challenges to finite geometers, some
thoughts about infinite analogues, and a long list of open problems.