Synchronizing coherent configurations

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 C1, … Cr such that

  • the diagonal Δ = {(x,x):x∈Ω} is the union of some of the classes Ci;
  • the transpose {(y,x):(x,y)∈Ci>} of any class is another class (possibly the same);
  • the adjacency matrices of the classes (rows and columns indexed by Ω, (x,y) entry 1 if (x,y)∈Ci) 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.

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 Ci 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.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, history and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s