Computer Science

Colloquium Details

A new approach to finding covers of arc-transitive graphs

Abstract

Quite a lot of attention has been paid recently to the construction of edge- or arc-transitive covers of symmetric graphs. In most cases, the approach has involved voltage graph techniques, which are excellent for finding normal covers in which the group of covering transformations is either cyclic or elementary abelian, or more generally, homocyclic, but not so easy to use when the covering group has other forms, even when it is abelian (but not homocyclic). In this talk, I will describe a different approach that can be used more widely. This approach takes a universal group for the action of the automorphism group of the base graph, and then uses Reidemeister-Schreier theory to obtain a presentation for a 'universal covering group', and some representation theory and other methods for determining suitable quotients. In joint work with my PhD student Jicheng Ma, we have used this approach to find all arc-transitive abelian normal covers of $K_4$, $K_{3,3}$, the cube $Q_3$, the Petersen graph and the Heawood graph. As we anticipated, this approach produces some of the best known graphs for the degree-diameter problem.

This is an invited talk at the Workshop on Algebraic, Topological and Complexity Aspects of Graph Covers (http://kam.mff.cuni.cz/conferences/ATCAGC_2012/) organized in the department on January 26-28.