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

Advertisements

About Peter Cameron

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

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