A paper on synchronization

A paper on synchronization, written with João Araújo, Wolfram Bentz, Gordon Royle and Artur Schaefer, has just appeared on the arXiv.

It is quite a substantial paper, and goes well beyond anything we have published (or that I have written about here before). So I cannot describe it all. Here is what I think is the most dramatic new idea.

By way of recap: a permutation group G, acting on a set X, is said to synchronize a map f if the monoid generated by G and f contains an element mapping everything to a single point. Then G is said to be a synchronizing group if it synchronizes every non-permutation, and an almost synchronizing group if it synchronizes every non-permutation which is uniform in the sense that the sizes of the inverse images of all points in its range are the same.

A more “classical” notion: G is primitive if it preserves no non-trivial equivalence relation on X, that is, there is no partition of X whose parts are permuted by G other than the partition into singletons and the partition with a single part.

There is a connection between these concepts. It is known that any synchronizing group is primitive (as, indeed, is any almost synchronizing group). A theorem of Rystsov shows that a permutation group of degree n is primitive if and only if it synchronizes every map of rank n−1 (that is, a map which collapses two points to the same place and is injective on the remaining points). Indeed, the largest part of our paper is to push down this bound: with long and delicate arguments, we show that a primitive group of degree n synchronizes any map of rank n−4 or greater.

It was conjectured for a while that, conversely, a primitive group is almost synchronizing. I described here how we refuted this conjecture last year. Our new examples go much further.

The most powerful tool for examining this problem is the use of graphs and graph endomorphisms. A transformation monoid M fails to be synchronizing if and only if there is a simple graph X (that is, undirected and without loops or multiple edges) whose endomorphism monoid contains M; moreover, we can assume that X has clique number equal to its chromatic number, and that every edge is contained in a maximal clique.

Now the new idea for constructing graphs with a rich supply of endomorphisms uses the notion of the Cartesian product XY of graphs X and Y. Its vertex set is the Cartesian product of the vertex sets of X and Y (that is, the set of ordered pairs (x,y), where xX and yY; edges join pairs (x1,y1) and (x2,y2) whenever x1 = x2 and y1 and y2 are joined in Y, or vice versa (X components joined, Y components equal). Thus, for example, if Kk is the complete graph on k vertices, then KkKk is the k×k square lattice graph L2(k), the line graph of the complete bipartite graph on k+k vertices.

The picture shows L2(4) with a proper vertex colouring (aka a Latin square of order 4). The rows and columns are cliques.

Latin square


  • if X has primitive automorphism group, so does XX (the wreath product of Aut(X) with the cyclic group of order 2, in the product action);
  • if X has clique number and chromatic number k, then it has a surjective homomorphism to Kk, and so XX has a surjective homomorphism to KkKk = L2(k).

So, if there is a homomorphism from L2(k) to X, then the composite

XX → L2(k) → X → XX

is an endomorphism of XX. (The last map sends X to the set of vertices of XX with fixed second coordinate.) The first and third homomorphisms are uniform, but the middle one gives us the chance to introduce non-uniformity.

This trick works rather well when the graph X is the complement of L2(k). (That is, vertices of the square grid are joined if they lie in different rows and different columns; X is the categorical product Kk×Kk.) This graph has clique number k (a diagonal of the square grid is a clique in the complement) and chromatic number k (give a colour to each row of the grid).

Our ingredient is a homomorphism from L2(k) to its complement. Such a map has the form (x,y) → (f(x,y),g(x,y)), and the homomorphism condition is equivalent to saying that each of f and g should be a Latin square (but with no relation between the two). Thus the image is given by the superposition of two Latin squares.

The rank of such a superposition is the number of different ordered pairs of entries which arise. Clearly it is between k and k2, the lower bound realised when the squares are identical and the upper bound when they are orthogonal. This rank is equal to the rank of the resulting endomorphism of XX. So we would like to know which ranks are possible for the superposition of two Latin squares.

Fortunately, this problem has already been solved by Colbourn, Zhu and Zhang, who have determined all the possible ranks. For k > 6, every value in the interval from k to k2 except k+1 and k2−1 occurs; all the exceptions for lower values of k have been determined.

So we have primitive graphs with k4 vertices, and with endomorphisms of k2k−1 different ranks, almost all of them non-uniform!

We have other examples too, but have not explored the new realms opened up by this idea. The conclusion is that things are much more complicated and interesting than anyone thought.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition 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