Primitive switching classes

Last year I wrote here about switching classes of graphs for which the switching class has a primitive automorphism group. (I repeat the definitions briefly below.) I conjectured that, except for the trivial switching classes of the complete and null graphs and finitely many others, such a class must contain a graph with trivial automorphism group. This is an example of the point of view of Laci Babai: from the Classification of Finite Simple Groups we learn that conditions which seem to imply a great deal of symmetry (such as primitive automorphism group) actually severely restrict the amount of symmetry.

The operation of Seidel switching a graph with respect to a set S of vertices involves replacing edges between S and its complement with non-edges, and non-edges with edges, leaving edges and non-edges inside and outside S unchanged. This is an equivalence relation on the class of graphs on a given vertex set, whose classes are called switching classes. An automorphism of a switching class is a permutation which permutes among themselves the graphs in the class. An equivalent combinatorial concept is a two-graph, a collection of 3-element subsets of the vertex set with the property that any 4-element subset contains an even number of members of the collection. I talked about two-graphs at the Villanova conference, and you can find the slides here.

Soon after posting that, I was able to prove the conjecture. Now Pablo Spiga and I have worked out the finite list of exceptions. Up to complementation, there is just one such switching class on 5, 6, 9, 10, 14 and 16 vertices, and no others. The automorphism groups are D10, PSL(2,5), 32:D8, PΣL(2,9), PSL(2,13), and 24:S6. All these are well-known. For an odd number of vertices, these are the switching classes of the finite homogeneous graphs with primitive automorphism groups (I don’t think this is more than a small-number coincidence). On an even number of vertices, they all have doubly transitive automorphism groups, and are among the list of such things given by Don Taylor a long time ago.

The proof that the list is finite comes by confronting upper bounds for orders of primitive groups derived from CFSG with lower bounds from the assumption that every graph in the switching class possesses a non-trivial automorphism. By pushing these arguments as hard as possible, Pablo was able to show that there were no examples on more than 32 points, and I was able to search all the primitive groups with degree up to 32 and come up with the list.

I hope we will have a paper available quite soon.

One interesting thing emerged from the investigation, which is probably worth a further look. For reasons I won’t go into here, it suffices to consider the case where the number of vertices is even. (The odd case is covered by the results of Ákos Seress that I discussed in the earlier post.) The switching classes with primitive automorphism group on n vertices, with n even and n ≤ 32 fall into two types:

  • those with doubly transitive groups, which are in Taylor’s list; and
  • some with very small groups: two on 10 vertices with group A5, six on 28 vertices with group PGL(2,7), and six more on 28 vertices with group PSL(2,8).

I’d never seen anything like the second type before, so I looked at the first two examples, on 10 points.

The action of A5 is on the 2-element subsets of the domain {1,…,5}, which we can think of as edges of a graph. The orbits of the symmetric group S5 are isomorphism classes, of which there are just four with 3 edges, namely K3, K2P3, K1,3 and P4, where K means complete (or complete bipartite) graph and P means path, the subscript being the number of vertices. You can check that every 4-edge graph contains an even number of copies of P4, so these form a two-graph containing S5 in its automorphism group. The full automorphism group is larger; it is the group PΣL(2,9) (aka S6) and appears on our list.

However, the automorphism group of P4 consists of even permutations, so under the action of A5, the 60 copies of this graph fall into two orbits of 30. The table below shows the numbers of graphs in the various A5-orbits which are contained in each of the four-edge graphs on five vertices.

Graphs with 3 or 4 edges

You can see from the table that taking one of the A5-orbits on P4s, together with the orbit on K1,3s, form a two-graph. So here are the mysterious two switching classes with automorphism group A5. We see that their symmetric difference is the much more symmetric two-graph consisting of all the P4s.

Surely the examples on 28 points also have some nice structure! And what happens beyond?


About Peter Cameron

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

Leave a Reply

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

You are commenting using your 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