## Easy to state, hard to solve?

I described here how Pablo Spiga and I showed that all but finitely many nontrivial switching classes of graphs with primitive automorphism group contain a graph with trivial automorphism group, and found the six exceptions. (The trivial switching classes are those containing the complete and null graphs.)

Being in Prague makes me think about graph homomorphisms, so I wondered:

Problem Is it true that all but finitely many nontrivial switching classes of graphs with primitive automorphism group contain a rigid graph (one with trivial endomorphism monoid)?

The difficulty seems to be that homomorphisms privilege edges over nonedges (edges must map to edges, but non-edges can be collapsed or mapped to edges or nonedges), whereas switching treats edges and nonedges on the same footing. I can’t see how to begin: what possible connection exists between the endomorphism monoids of graphs related by switching?

(And yet, switching classes are equivalent to double covers of complete graphs, which are certainly things with a homomorphism-like feel to them.)

On the subject of switching, I managed to show the analogue for tournaments of the result for graphs. There are no “trivial” tournaments (admitting the symmetric group), so the result is:

Theorem With two exceptions (on 4 and 8 vertices), a switching class of tournaments with primitive automorphism group contains a tournament with trivial automorphism group.

This is much easier than the result for graphs. While any permutation group preserves a switching class of graphs, the groups preserving switching classes of tournaments are much more restricted: the Sylow 2-subgroups are cyclic or dihedral and act semiregularly. The only primitive groups occurring are groups of odd order (and odd degree), and groups between PSL(2,q) and PΣL(2,q), where q is a prime power congruent to 3 (mod 4).