In my report on CAMconf, I didn’t mention Laci Babai’s talk, whose title was the same as that of this post. This was a talk that needed some thinking about. I want to describe the situation briefly, and then pose a problem which I am sure is not too difficult, and might be a good way into this field for anyone who wants to try it.
Laci started with a paradox: symmetry and regularity tend to work in different directions. It might seem at first sight that the most regular configurations have the largest amount of symmetry, but you quickly come to realise that it is not so. There are various symptoms of this paradox:
- Strongly regular graphs (the most “regular” of graphs in abundant supply) almost all have trivial automorphism group; the same is true for other very regular structures such as Steiner triple systems, Latin squares, etc.
- Primitive permutation groups, apart from the symmetric and alternating groups, are very small, and doubly transitive groups even smaller.
- Among regular structures such as Steiner systems, all (without exception) have small automorphism groups.
The first two of these are old results in which Laci and I both had a hand; the last is much more recent work of Laci and others which he talked about at the meeting.
The problem I want to pose is related to a consequence of both the smallness of primitive permutation groups, and our better understanding of them since the Classification of Finite Simple Groups, In the 1980s, Peter Neumann, Jan Saxl and I showed that for any primitive group, apart from the symmetric and alternating groups and finitely many others, there is a subset of the domain whose setwise stabiliser is trivial. (Incidentally, Laci and I showed that this set could be chosen to have size just a little larger than the square root of n, the number of points, but never managed to publish this.) Ákos Seress, whose recent death is a great loss to many of us, found all the exceptions: there are 43 of them, the largest having degree 32.
The other ingredient in the problem is Seidel switching of graphs. Given a graph X, and a subset A of the vertex set, the operation of switching X with respect to A consists of replacing all edges from A to its complement by non-edges, and all non-edges by edges, while leaving edges within A or outside A unchanged. Switching defines an equivalence relation on the set of all graphs with given n-element vertex set, each equivalence class containing 2n−1 graphs (since switching with respect to a set and its complement are the same thing, and switching with respect to two sets is the same as switching with respect to their symmetric difference). The equivalence classes are called switching classes.
Now we can talk about the automorphism group of a switching class, the group of permutations which map some (or every) graph in the class to a graph in the class. It contains as a subgroup the automorphism group of every graph in the class, but may be larger than any of them; for example, there are non-trivial switching classes which have doubly transitive automorphism group (this cannot happen for a non-trivial graph, of course).
Problem Prove that, if S is a switching class (not that of the complete or null graph) which has a primitive automorphism group, then with finitely many exceptions it is true that there is a graph in S which has trivial automorphism group. Find the finitely many exceptions.
One case of this problem already follows from what I said earlier. If there is a graph in S whose automorphism group coincides with that of S, then choose a subset whose stabiliser in this group is trivial, and switch the graph with respect to this subset.
So the case requiring work is that when no graph admits all the automorphisms of the switching class.
There is more to say about this case. Mallows and Sloane, in the course of enumerating switching classes (and showing that they are equinumerous with even graphs), proved that every single automorphism group of a switching class fixes some graph in the class. However, as noted, this may fail for the full automorphism group; this failure is detected by the non-vanishing of a certain cohomology class associated with the action of the group on the permutation module over GF(2) modulo constants.
Peter Cameron's Blog 
To what extent is this due to the fact that we almost always “define away” the objects that combine high symmetry and regularity? For example, we could happily call the complete graph strongly regular and then it would have a nice large automorphism group, and ditto we could keep the alternating and symmetric groups, and complete designs. So perhaps there is some effect that we only find things “interesting” if they combine regularity with not-too-much symmetry.
The interesting thing is that there are many fewer things that have to be defined away. There are no huge (exponentially large) primitive or multiply transitive groups. That is what makes this philosophy work. So in some sense it is a consequence of CFSG.
The first part of my problem, asking for a proof that there are only finitely many exceptions to the statement that a non-trivial switching class with primitive automorphism group contains a graph with trivial automorphism group, is now solved. There are only two exceptions with an odd number of vertices: the switching classes of the 5-cycle and the line graph of K3,3. Finding all exceptions with an even number of vertices is more challenging but should be doable. If anyone is interested in having a go, let me know and I will send you what I know.
One more fact which I tried to resist mentioning but in the end I have succumbed. I said in the post that the automorphism group of a switching class contains as a subgroup the automorphism group of every graph in the class. Now, given a finite group G, there is a switching class S of graphs with the properties