In previous posts I have discussed coherent configurations and synchronization. Yesterday I realised that these two topics can be combined …

#### Synchronization

A (finite-state, deterministic) automaton consists of a finite set of *states* and a finite set of *transitions*, each transition a mapping on the set of states. We are allowed to compose transitions, so can assume that the set of transitions is closed under composition, that is, a *transformation monoid*. (The identity map is the composition of the empty string of transitions and so is always present.) So we can use the languages of automata and transformation monoids interchangeably.

A transformation monoid is *synchronizing* if it contains a mapping of rank 1, that is, one which maps the whole set to a single point.

It is possible to show that there is only one obstruction to synchronization:

**Theorem 1** A transformation monoid *M* is non-synchronizing if and only if there exists a simple graph *X* which is non-trivial (that is, not a complete or null graph) whose clique number and chromatic number are equal, such that *M* is contained in the monoid of endomorphisms of *X*.

Recently, with various collaborators, I have been interested in the question: for which permutation groups *G* is it true that, for any non-permutation *a*, the monoid generated by *G* and *a* is synchronizing? By abuse of language, we call a permutation group *G* *synchronizing* if this is the case.

By Theorem 1, a permutation group *G* is non-synchronizing if and only if there is a non-trivial *G*-invariant graph *X* with clique number equal to chromatic number. In particular, a synchronizing group is *primitive* (that is, preserves no non-trivial equivalence relation). [If there is a *G*-invariant equivalence relation, then the disjoint union of complete graphs on the equivalence classes has clique number and chromatic number equal.]

#### Coherent configurations

Coherent configurations were introduced independently by Boris Weisfeiler (who called them “cellular algebras”) and Donald Higman. They provide a combinatorial description of the orbits on ordered pairs of a permutation group.

Given a set Ω, a *coherent configuration* on Ω is a partition of the Cartesian square Ω×Ω into classes *C*_{1}, … *C _{r}* such that

- the diagonal Δ = {(
*x,x*):*x*∈Ω} is the union of some of the classes*C*;_{i} - the
*transpose*{(*y,x*):(*x,y*)∈*C*} of any class is another class (possibly the same);_{i>} - the
*adjacency matrices*of the classes (rows and columns indexed by Ω, (*x,y*) entry 1 if (*x,y*)∈*C*) span an algebra; in other words, the product of any two of these matrices is a linear combination of them. This condition has a combinatorial interpretation._{i}

Now, if *G* is a permutation group on Ω, then the orbits of *G* on Ω×Ω form a coherent configuration; but not every coherent configuration arises in this way from a group.

#### Combining

A coherent configuration is *imprimitive* if the union of some of the classes *C _{i}* is a non-trivial equivalence relation. It is not hard to show that a permutation group is primitive if and only if its coherent configuration is primitive.

Now, for any permutation group *G*, the edge set of any *G*-invariant graph is the union of some of the classes in the coherent configuration of *G* (to get a loopless undirected graph, we must exclude diagonal classes, and if we include a non-diagonal class we must also include its transpose).

This leads to

**Definition** A coherent configuration is *synchronizing* if there is no union of classes which is the edge set of a non-trivial graph with clique number equal to chromatic number.

Then we have

**Theorem 2** A permutation group is synchronizing if and only if its coherent configuration is synchronizing.

And finally

**Problem** What can be said about synchronizing coherent configurations?

#### Final note: Boris Weisfeiler

I reported here about the unexplained disappearance of Boris Weisfeiler in Chile in 1985.

His sister Olga has just emailed to say that after nearly thirty years there is a new development in the story. See the New York Times report here.