Butterflies

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.

Butterfly

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

Butterfly

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 …

Advertisements

About Peter Cameron

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

5 Responses to Butterflies

  1. Jon Awbrey says:

    A.K.A. Bowtie ⋈

  2. Gordon Royle says:

    Yes, this degree-45 example is indeed the lowest degree counterexample – there are not that many vertex-primitive graphs with equal chromatic- and clique-number up to that size, and they are not too hard to check individually.

    Probably not of much significance, but your graph has other non-uniform endomorphisms too – for example, one with fibres of size 5,5,5,5,5,10,10 whose image is three triangles arranged in a path. (Presumably this is just a refinement of the one you’ve exhibited, but I haven’t checked that.)

  3. Jon: Yes, but I never heard of a bowtie causing tornadoes in Texas (or even loud lamentations in Lisbon).
    Gordon: I have challenged James Mitchell to compute the endomorphism monoid of this graph. It might be interesting to see just what else is there.

  4. I guess it is now reasonable to ask which primitive groups synchronize all non uniform transformations as an intermediate between synchronizing groups and primitive groups.

  5. Gordon went on to find the first of an infinite family of primitive groups not synchronizing a non-uniform map of rank 6. The graph is two complete graphs of size 4 joined along an edge, that is, a larger butterfly with 1-dimensional body.

    So there are no examples of rank at most 4; we know just two of rank 5; and infinitely many of rank 6.

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