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 *D*_{10}, PSL(2,5), 3^{2}:*D*_{8}, PΣL(2,9), PSL(2,13), and 2^{4}:*S*_{6}. 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
*A*_{5}, 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 *A*_{5} 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 *S*_{5} are isomorphism classes, of which there are just four with 3 edges, namely *K*_{3}, *K*_{2}∪*P*_{3}, *K*_{1,3} and *P*_{4}, 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 *P*_{4}, so these form a two-graph containing *S*_{5} in its automorphism group. The full automorphism group is larger; it is the group PΣL(2,9) (aka *S*_{6}) and appears on our list.

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

You can see from the table that taking one of the *A*_{5}-orbits on *P*_{4}s, together with the orbit on *K*_{1,3}s, form a two-graph. So here are the mysterious two switching classes with automorphism group *A*_{5}. We see that their symmetric difference is the much more symmetric two-graph consisting of all the *P*_{4}s.

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