Discrete Mathematics Seminar - Extremal circulant graphs and where to find them

Dates

Wednesday, March 31, 2021 - 14:00 to 15:00

Speaker: Rob Lewis (Open University)

Title: Extremal circulant graphs and where to find them

Abstract:

The goal of this talk is to present an efficient method for finding families of extremal circulant graphs of any given degree and infinite classes of diameters. This is a sub-problem of the general degree-diameter problem, which is to find graphs with the largest possible number of vertices for a given maximum degree and diameter.

The method relies on an established relationship between finite Abelian groups with f generators and the free Abelian group Z^f on f generators, and how this relates to a corresponding Abelian Cayley graph with f generators. The existence of an Abelian Cayley graph with given parameters is associated with the existence of a lattice covering of Z^f by Lee spheres of corresponding radius. The lattice is defined by a corresponding matrix of lattice generating vectors. It has been discovered that all extremal and largest-known Abelian Cayley graph families share a property called quasimaximality and are associated with lattice generator matrices of a specific canonical form. It is conjectured that all extremal Abelian Cayley graph families are quasimaximal and are generated by such a canonical lattice generator matrix. The search for such graph families may therefore be restricted to this subset of matrices.

My aim is to ensure that this talk is accessible to mathematicians with no knowledge of graph theory.