Peter Cameron
(St. Andrews, & Queen Mary, London)
Synchronization

An attack on the celebrated Černý conjecture (now nearly 50 years old) in the theory of finite automata led Ben Steinberg and João Araujo to study the problem: for which permutation groups G is it true that, for any singular map f, the semigroup generated by G and f contains a constant function?

We say that G synchronizes f if this condition holds for a particular f, and that G is synchronizing if it synchronizes every singular map.

A synchronizing group must be primitive, but (contrary to first expectations) the converse is false; we do not very well understand the class of such synchronizing groups. The question is intimately connected with graph endomorphisms: a permutation group G fails to be synchronizing if and only if there is a
G-invariant graph Γ with clique number equal to chromatic number (and so having an endomorphism whose image is complete).

This insight has led to further progress on some related questions such as the following: is it true that a primitive group synchronizes every map whose kernel is not uniform, or that the number of ranks of maps not synchronized is at most about log n?