I am in Lisbon working with João Araújo and Wolfram Bentz on synchronization.

We say that a permutation group *G* on the set {1,…*n*} *synchronizes* a non-permutation *f* from this set to itself if the semigroup generated by *G* and *f* contains a constant map. Also, the *kernel classes* of a map *f* are the inverse images of the points in the image of *f*; and *f* is *uniform* if all the kernel classes have the same size, and *non-uniform* otherwise.

A group that synchronizes every non-permutation must be primitive. It is not true that a primitive group synchronizes every non-permutation; there are some very interesting exceptions, and deciding the question is very difficult. The current “big conjecture” on synchronization for primitive permutation groups is due to João, and says:

**Conjecture:** A primitive group synchronizes every non-uniform map.

I have spoken about this conjecture in several places. We had proved it for maps of rank at most 4 (where the rank is the cardinality of the image) or at least *n*−2, in a paper published this year in the Journal of Combinatorial Theory Series B (doi: 10.1016/j.jctb.2014.01.006). We are currently hard at work improving the upper bound, and hope to get it down to *n*−4 or even *n*−5.

This morning, we discovered that the conjecture is **false**.

Here is a brief description of the counterexample.

The graph in question is the line graph of the *Tutte–Coxeter graph*, also known as *Tutte’s 8-cage*. The Tutte–Coxeter graph is trivalent; its line graph has valency 4, and any edge lies in a unique triangle (the triangles corresponding to the vertices in the original graph), so the closed neighbourhood of a vertex is a *butterfly*, consisting of two triangles with a common vertex.

As in dynamics, it is the butterfly that causes chaos with a flap of its wings …

Our graph has automorphism group *G* = PΓL(2,9), and has chromatic number 3; this means that it has a homomorphism onto one of its triangles, this being a (uniform) map of rank 3 not synchronized by the primitive group *G*.

We used GAP and its share package GRAPE to determine all the independent sets of size 15 in the graph (up to the action of the group *G*, there are just two of these), and to examine the induced subgraph on the complement of each such set. In both cases, this induced subgraph turns out to be a disjoint union of cycles of even length; so each independent set of size 15 is a colour class in a 3-colouring. For one of these independent sets, it occurs that the induced subgraph on the complement has two components, of sizes 10 and 20. In this case, the original independent set *A* and the bipartite blocks *B* and *C* of the component of size 10 and *D* and *E* of the other component are all independent sets, with edges between *A* and the others, and between *B* and *C* and between *D* and *E*, and no further edges.

Thus the edges between these five sets can be mapped homomorphically to the butterfly, with *A* mapping to the central vertex. This gives us a non-uniform map of rank 5 (with kernel classes of sizes 15, 5, 5, 10, 10) which is an endomorphism of the graph, and hence not synchronized by the group *G*.

Indeed, this butterfly resembles Lorenz’s attractor in one respect. If you wander round the graph and follow your image under the homomorphism, it will move around one wing of the butterfly and then (apparently randomly) switch to the other wing, and so on. Actually, since the wings are of unequal sizes, you will spend most of your time on the larger wing.

Is this an isolated example, or the first butterfly of the summer? (It is not completely isolated; the line graph of the Biggs–Smith graph gives another example with degree 153, where the kernel type is (6,6,45,45,51).)

As with any good counterexample, it opens various new questions. Is it the smallest counterexample? What can we say about the gap between the ranks of the smallest map and the smallest non-uniform map not synchronized by a primitive group? (It can’t be 1; how large can it be?) Does a primitive group of degree *n* synchronize every map of rank greater than *n*/2? Can one determine all the primitive groups which fail to synchronize some map of rank 3? And so on …