Pure Mathematics Colloquium - How large are extremal Abelian Cayley graphs?

Speaker: Rob Lewis (The Open University)

Abstract:  We will discuss the degree-diameter problem for Abelian Cayley graphs, to find graphs with the largest possible number of vertices for a given maximum degree and diameter, denoted extremal graphs. No prior knowledge of graphs is assumed. Connections are described between Abelian Cayley graphs and lattice coverings of integer space by Lee spheres. This is extended to lattice coverings of real space by dual hypercubes. Published upper bounds for the density of such coverings that are sub-exponential in the dimension are challenged. This argument supports a conjecture about the order of extremal Abelian Cayley graphs of any dimension.