With the recent flurry of activity in constructing vertex-transitive graphs, in particular Primoz, Pablo and Gabriel’s work on cubic vertex-transitive graphs, I was thinking about the current situation regarding catalogues of vertex-transitive graphs of unrestricted valency.

In prehistoric times, Brendan (McKay) and I worked on this problem; indeed part of my PhD thesis was extending Brendan’s catalogue of vertex-transitive graphs from 20 vertices to 24 vertices, and subsequently we pushed it a little further to 26 vertices. The difficulty of these computations depends primarily on the prime decomposition of the number of vertices – if there is a large prime involved, then it is easy, while if there are lots of small primes involved, it is hard. So our efforts ended at 31 vertices and we just put the lists of graphs online for anyone interested.

In the interim, group theorists have been busily extending the known catalogues of *transitive groups* of low degree. For my thesis, I computed the transitive groups of degree up to 12, reproducing and correcting the lists laboriously hand-produced by G.A. Miller in the early 1900s (See http://www-history.mcs.st-andrews.ac.uk/Biographies/Miller.html for an interesting bio-sketch of Miller, especially the part about how “one is tempted to say that he should have applied his undoubted skills to produce fewer yet more significant results”!) This work was rapidly extended over the next few years, until the lists of transitive groups were complete up to degree 31; again blocked by the fact that 32 is a high power of a small prime. It is straightforward (see below) to compute all the vertex-transitive graphs of a given order if you know all the transitive groups of that degree and so we could easily check that our lists of graphs were correct.

A couple of years ago, John Cannon and Derek Holt managed to breach this barrier and computed the 2801324 transitive groups of degree 32. This catalogue has now made its way into recent releases of Magma and so the vertex-transitive graphs on 32 vertices were just a few hours work away. Being on long-service leave for the next couple of months, and therefore able to legitimately, if temporarily, ignore tedious meetings and free of the all-consuming rush of the beginning of semester (here in the Southern Hemisphere, our academic year is just starting) I finally found that couple of hours over the weekend.

The results are as follows: there are 677402 vertex-transitive graphs of which 659232 are Cayley graphs, leaving 18170 non-Cayley graphs. The numbers broken down according to valency are in the following table: the numbers for valencies 16 to 31 are the same as those for valencies 15 to 0 respectively.

Valency | Cayley | Non-Cayley | Total |
---|---|---|---|

0 | 1 | 0 | 1 |

1 | 1 | 0 | 1 |

2 | 4 | 0 | 4 |

3 | 17 | 0 | 17 |

4 | 78 | 2 | 80 |

5 | 290 | 23 | 313 |

6 | 937 | 56 | 993 |

7 | 2457 | 146 | 2603 |

8 | 5621 | 253 | 5874 |

9 | 11248 | 468 | 11716 |

10 | 20102 | 650 | 20752 |

11 | 31931 | 965 | 32896 |

12 | 46104 | 1212 | 47316 |

13 | 60277 | 1572 | 61849 |

14 | 72025 | 1785 | 73810 |

15 | 78523 | 1953 | 80476 |

**Details of the computation **

For those interested, this is how the computation was performed. I’m sure this could be done entirely in Magma if desired, but I used various programs outside Magma that I already had lying around in conjunction with Magma itself.

Recall (or learn) that an *orbital* of a group acting on a set is an orbit of in its action on . An orbital is *self-paired* if it contains the ordered pair whenever it contains the ordered pair . Otherwise, each orbital has a partner which contains all the switched-round pairs.

If is a (possibly directed) graph with a group acting transitively on it, then the edge set of is necessarily the union of the *orbitals* of . If is undirected, then any non-self-paired orbital can only appear in the edge set if its partner does too. Furthermore if has no loops, then the diagonal orbital (containing all the pairs ) should be omitted.

However rather than compute orbitals and then work out which is paired with which, it is even easier just to get Magma to directly compute the orbits of on *unordered* pairs — I don’t know if these have a catchy name like orbital, but they should! I’ll just call them “orbs” for now.

So to process the -th transitive group of degree 32, the Magma code I used was:

g := TransitiveGroup(32,i); gset := GSet(g,Subsets({1..Degree(g)},2)); orbs := Orbits(g,gset);

If there are orbs, then vertex-transitive graphs can be constructed by taking every possible subset of the orbs to be the edge set. The graphs will contain many isomorphic graphs and so the list must be filtered to throw out isomorphs. The worst case for this is when is the elementary abelian group of order 32, in which case , but in most cases the number is much smaller. For this particular worst case, we actually know the answer anyway because the graphs correspond to binary matroids of rank 5, and there are only 1372 of those. There are lots of little tricks that can be used to reduce the number of isomorphs created in the first place, but for this problem, it would cost more of my time than the computer time saved, which seems a poor use of my time.

One obvious thing that *is* worth doing however is not running this process for every one of the 2801324 transitive groups, but separating out just those that are *minimal transitive*. Every transitive group will contain one or (probably) more minimal transitive subgroups and any graph constructed when the larger group is processed will also be constructed again when the smaller one is. I don’t know if Magma has a built-in command for minimal transitivity, but in any case it is easy to write one:

function isMinimalTransitive(g) m := MaximalSubgroups(g); for i in [1..#m] do if IsTransitive(m[i]`subgroup) then return false; end if; end for; return true; end function;

It turns out that there are only 12033 minimal transitive groups, and it just took a single computer working over the weekend to process all of these. Moreover the vast majority of this time was spent on the elementary abelian group, which I had left in as a sort of minor double-check on the process.

The Cayley graphs are then just those graphs produced when processing the 51 groups of order 32, and so taking the difference between this set of graphs and the entire set of graphs yields the non-Cayley graphs.

Is there a chance one could get the list of those graphs?