Lethbridge Number Theory and Combinatorics Seminar: Joy Morris

A Digraphical Regular Representation (DRR) for a group G is a directed graph whose full automorphism group is the regular representation of G. In 1981, Babai showed that with five small exceptions, there is at least one DRR for every finite group.

A Cayley digraph on a group G is a group that contains the regular representation of G in its automorphism group. So when a Cayley digraph is a DRR, its automorphism group is as small as possible given that constraint.

The question of whether or not requiring a certain level of symmetry (in this case, a Cayley digraph) makes having additional symmetry more likely is a natural one, particularly in light of results by Erdős and others proving that almost every graph is asymmetric.

In some 1981 and 1982 papers, Babai and Godsil conjectured that as r→∞, over all groups G of size r, the proportion of Cayley digraphs that are DRRs tends to 1. They proved this to be true for the restricted family of nilpotent groups of odd order.

I will talk about recent joint work with Pablo Spiga in which we prove this conjecture.