Skip to content

There are 677402 vertex-transitive graphs on 32 vertices

February 27, 2012

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 {G} acting on a set {\Omega} is an orbit of {G} in its action on {\Omega \times \Omega}. An orbital is self-paired if it contains the ordered pair {(i,j)} whenever it contains the ordered pair {(j,i)}. Otherwise, each orbital has a partner which contains all the switched-round pairs.

If {\Gamma} is a (possibly directed) graph with a group {G} acting transitively on it, then the edge set of {\Gamma} is necessarily the union of the orbitals of {G}. If {\Gamma} is undirected, then any non-self-paired orbital can only appear in the edge set if its partner does too. Furthermore if {\Gamma} has no loops, then the diagonal orbital (containing all the pairs {(x,x)}) 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 {G} 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 {i}-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 {k} orbs, then {2^k} vertex-transitive graphs can be constructed by taking every possible subset of the {k} orbs to be the edge set. The {2^k} graphs will contain many isomorphic graphs and so the list must be filtered to throw out isomorphs. The worst case for this is when {G} is the elementary abelian group of order 32, in which case {k=31}, 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.

 

About these ads
No comments yet

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

Follow

Get every new post delivered to your Inbox.

Join 40 other followers

%d bloggers like this: