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 X□Y 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 x∈X and y∈Y; edges join pairs (x₁,y₁) and (x₂,y₂) whenever x₁ = x₂ and y₁ and y₂ are joined in Y, or vice versa (X components joined, Y components equal). Thus, for example, if K_k is the complete graph on k vertices, then K_k□K_k is the k×k square lattice graph L₂(k), the line graph of the complete bipartite graph on k+k vertices.

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

Now

• if X has primitive automorphism group, so does X□X (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 K_k, and so X□X has a surjective homomorphism to K_k□K_k = L₂(k).

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

X□X → L₂(k) → X → X□X

is an endomorphism of X□X. (The last map sends X to the set of vertices of X□X 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 L₂(k). (That is, vertices of the square grid are joined if they lie in different rows and different columns; X is the categorical product K_k×K_k.) 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 L₂(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 k², 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 X□X. 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 k² except k+1 and k²−1 occurs; all the exceptions for lower values of k have been determined.

So we have primitive graphs with k⁴ vertices, and with endomorphisms of k²−k−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.