### Regular Representations of Groups

Joy Morris

University of Lethbridge

February 10, 2020 SODO, Rotorua, NZ

### Overview

1 Group actions

2 History and definitions

3 Obstructions

4 Asymptotics Main tools

5 Related Work and Open Problems

## Group Actions

### Disclaimer

Throughout this talk, assume groups are finite. Some things may apply to infinite groups also, but this hasn’t been studied much to my knowledge.

### Groups and their actions

Often we introduce group theory to students with pictures like the following, and ask:

What are all the symmetries of this object?

### Groups and their actions

Often we introduce group theory to students with pictures like the following, and ask:

What are all the symmetries of this object?

### Groups and their actions

Often we introduce group theory to students with pictures like the following, and ask:

What are all the symmetries of this object?

### Groups and their actions

Often we introduce group theory to students with pictures like the following, and ask:

What are all the symmetries of this object?

This provides us with some intuitive understanding of the group.

### Regular action of a group

Sometimes that intuition is limited. For example, many people struggle to understand the interactions between rotations and reflections.

Given any group G, it admits a natural permutation action on the set of elements of G, by right- (or left-) multiplication.

{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G
is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

Notice that this action is regular: for any x,y ∈G, there is a unique
g ∈G such thatτ_{g}(x) =y: namely,g =x^{−1}y.

### Regular action of a group

Sometimes that intuition is limited. For example, many people struggle to understand the interactions between rotations and reflections.

Given any group G, it admits a natural permutation action on the set of elements of G,

by right- (or left-) multiplication.
{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G
is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

Notice that this action is regular: for any x,y ∈G, there is a unique
g ∈G such thatτ_{g}(x) =y: namely,g =x^{−1}y.

### Regular action of a group

Sometimes that intuition is limited. For example, many people struggle to understand the interactions between rotations and reflections.

Given any group G, it admits a natural permutation action on the set of elements of G, by right- (or left-) multiplication.

{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G
is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

Notice that this action is regular: for any x,y ∈G, there is a unique
g ∈G such thatτ_{g}(x) =y: namely,g =x^{−1}y.

### Regular action of a group

Given any group G, it admits a natural permutation action on the set of elements of G, by right- (or left-) multiplication.

{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G

is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

_{g}(x) =y: namely,g =x^{−1}y.

### Regular action of a group

{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G
is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

_{g}(x) =y: namely,g =x^{−1}y.

### Regular action of a group

{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G
is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

_{g}(x) =y: namely,g =x^{−1}y.

### Regular action of a group

{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G
is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

Notice that this action is regular:

for any x,y ∈G, there is a unique
g ∈G such thatτ_{g}(x) =y: namely,g =x^{−1}y.

### Regular action of a group

{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G
is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

Notice that this action is regular: for any x,y ∈G, there is a unique
g ∈G such thatτ_{g}(x) =y:

namely, g =x^{−1}y.

### Regular action of a group

{τ_{g} :g ∈G}, whereτ_{g}(h) =hg for everyh∈G
is called the right-regular action ofG.

[Cayley’s Theorem: G is isomorphic to a subgroup of Sym(|G|).]

_{g}(x) =y: namely,g =x^{−1}y.

### Regular action and intuition

The regular action can sometimes help our intuition more than other group representations.

### Regular action and intuition

The regular action can sometimes help our intuition more than other
group representations. For example, we can think of D_{8} (the dihedral
group of order 8) as the symmetries (automorphisms) of a square

### Regular action and intuition

The regular action can sometimes help our intuition more than other
group representations. For example, we can think of D_{8} (the dihedral
group of order 8) as the symmetries (automorphisms) of a square

### Regular action and intuition

The regular action can sometimes help our intuition more than other group
representations. For example, we can think of D_{8} (the dihedral group of
order 8) as the symmetries (automorphisms) of a square or of this object:

## History and Definitions

### History

Question [K¨onig, 1936]

Given an abstract group G, is there a graph whose automorphism group is isomorphic to G?

Answer [Frucht, 1938]

Yes; in fact, there are infinitely many such graphs for any group G. General constructions, though, did not have regular group actions – they required far more than|G|vertices.

Example: Z5

### History

Question [K¨onig, 1936]

Given an abstract group G, is there a graph whose automorphism group is isomorphic to G?

Answer [Frucht, 1938]

Yes; in fact, there are infinitely many such graphs for any group G.

General constructions, though, did not have regular group actions – they required far more than|G|vertices.

Example: Z5

### History

Question [K¨onig, 1936]

Given an abstract group G, is there a graph whose automorphism group is isomorphic to G?

Answer [Frucht, 1938]

Yes; in fact, there are infinitely many such graphs for any group G.

General constructions, though, did not have regular group actions – they required far more than|G|vertices.

Example: Z5

### Definitions

Definition

A graphis a collection of vertices, with edges joining some of them.

Definition

A digraphis a collection of vertices, with arcs (directed edges) joining some of them. If we have arcs in both directions between two vertices, we often represent this by an edge.

Definition

An oriented graphis a directed graph that does not have arcs in both directions between any two vertices.

Definition

For any of these objects, an object of that type whose full automorphism group is the regular representation of some group G , is called a [object type] regular representation of G . (GRR, DRR, ORR.)

### Definitions

Definition

A graphis a collection of vertices, with edges joining some of them.

Definition

A digraphis a collection of vertices, with arcs (directed edges) joining some of them.

If we have arcs in both directions between two vertices, we often represent this by an edge.

Definition

An oriented graphis a directed graph that does not have arcs in both directions between any two vertices.

Definition

For any of these objects, an object of that type whose full automorphism group is the regular representation of some group G , is called a [object type] regular representation of G . (GRR, DRR, ORR.)

### Definitions

Definition

A graphis a collection of vertices, with edges joining some of them.

Definition

A digraphis a collection of vertices, with arcs (directed edges) joining some of them. If we have arcs in both directions between two vertices, we often represent this by an edge.

Definition

An oriented graphis a directed graph that does not have arcs in both directions between any two vertices.

Definition

For any of these objects, an object of that type whose full automorphism group is the regular representation of some group G , is called a [object type] regular representation of G . (GRR, DRR, ORR.)

### Definitions

Definition

A graphis a collection of vertices, with edges joining some of them.

Definition

A digraphis a collection of vertices, with arcs (directed edges) joining some of them. If we have arcs in both directions between two vertices, we often represent this by an edge.

Definition

Definition

### Definitions

Definition

A graphis a collection of vertices, with edges joining some of them.

Definition

Definition

Definition

For any of these objects, an object of that type whose full automorphism group is the regular representation of some group G , is called a [object type] regular representation of G .

(GRR, DRR, ORR.)

### Definitions

Definition

A graphis a collection of vertices, with edges joining some of them.

Definition

Definition

Definition

### Examples

is not a DRR, GRR, or ORR for any group. Its full automorphism group is D8, but the action ofD8 is not regular on the vertices of this graph.

### Examples

is not a DRR, GRR, or ORR for any group. Its full automorphism group is D8, but the action ofD8 is not regular on the vertices of this graph.

### Examples

is a DRR, for D_{8}. Its full automorphism group isD_{8}, and the action ofD_{8}
is regular on the vertices of this digraph. It is not a graph, nor an oriented
graph, so it is not a GRR or an ORR.

### Examples

is a DRR, for D_{8}. Its full automorphism group isD_{8}, and the action ofD_{8}
is regular on the vertices of this digraph.

It is not a graph, nor an oriented graph, so it is not a GRR or an ORR.

### Examples

is a DRR, for D_{8}. Its full automorphism group isD_{8}, and the action ofD_{8}
is regular on the vertices of this digraph. It is not a graph, nor an oriented
graph, so it is not a GRR or an ORR.

### Examples

is a GRR, for D_{12}. Its full automorphism group isD_{12}, and the action of
D12 is regular on the vertices of this graph. It is also a digraph, so it is a
DRR, but it is not an oriented graph, so is not an ORR.

### Examples

is a GRR, for D_{12}. Its full automorphism group isD_{12}, and the action of
D12 is regular on the vertices of this graph.

It is also a digraph, so it is a DRR, but it is not an oriented graph, so is not an ORR.

### Examples

is a GRR, for D_{12}. Its full automorphism group isD_{12}, and the action of
D12 is regular on the vertices of this graph. It is also a digraph, so it is a
DRR, but it is not an oriented graph, so is not an ORR.

### Cayley graphs

Definition

The Cayley (di)graphΓ =Cay(G,S) is the (di)graph whose vertices are the elements of G , with an arc from g to sg if and only if s ∈S .

g

sg

Notice

Γ will be a graph if and only ifS =S^{−1};

right-multiplication by any element of G is necessarily an

automorphism of this (di)graph (there is an arc from ghto sgh).

### Cayley graphs

Definition

The Cayley (di)graphΓ =Cay(G,S) is the (di)graph whose vertices are the elements of G , with an arc from g to sg if and only if s ∈S .

g

sg

Notice

Γ will be a graph if and only ifS =S^{−1};

right-multiplication by any element of G is necessarily an

automorphism of this (di)graph (there is an arc from ghto sgh).

### Cayley graphs

Definition

The Cayley (di)graphΓ =Cay(G,S) is the (di)graph whose vertices are the elements of G , with an arc from g to sg if and only if s ∈S .

g

sg

Notice

Γ will be a graph if and only ifS =S^{−1};

right-multiplication by any element of G is necessarily an

automorphism of this (di)graph (there is an arc from ghto sgh).

### Cayley graphs and Regular Representations

Proposition (Sabidussi)

A (di)graph is Cayley on the group G if and only if its group of automorphisms contains the (right-)regular representation of G .

So, a DRR/GRR/ORR must be a Cayley digraph that happens to not have any extra automorphisms.

### Cayley graphs and Regular Representations

Proposition (Sabidussi)

A (di)graph is Cayley on the group G if and only if its group of automorphisms contains the (right-)regular representation of G .

So, a DRR/GRR/ORR must be a Cayley digraph that happens to not have any extra automorphisms.

## Obstructions

### Obstructions for GRRs

Observation

For any Cayley (di)graph Γ =Cay(G,S), ifα is an automorphism of the group G that fixes S setwise, then the map defined byα on the vertices of Γ is an automorphism of Γ.

Proof.

Suppose that there is an arc fromg tosg, sos ∈S. Sinceα is a group
automorphism, (sg)^{α} =s^{α}g^{α}. Sinceα fixes S,s^{α}∈S, so there is an arc
from g^{α} tos^{α}g^{α}= (sg)^{α}.

### Obstructions for GRRs

Observation

For any Cayley (di)graph Γ =Cay(G,S), ifα is an automorphism of the group G that fixes S setwise, then the map defined byα on the vertices of Γ is an automorphism of Γ.

Proof.

Suppose that there is an arc fromg tosg, sos ∈S.

Since α is a group
automorphism, (sg)^{α} =s^{α}g^{α}. Sinceα fixes S,s^{α}∈S, so there is an arc
from g^{α} tos^{α}g^{α}= (sg)^{α}.

### Obstructions for GRRs

Observation

For any Cayley (di)graph Γ =Cay(G,S), ifα is an automorphism of the group G that fixes S setwise, then the map defined byα on the vertices of Γ is an automorphism of Γ.

Proof.

Suppose that there is an arc fromg tosg, sos ∈S. Sinceα is a group
automorphism, (sg)^{α} =s^{α}g^{α}.

Sinceα fixes S,s^{α}∈S, so there is an arc
from g^{α} tos^{α}g^{α}= (sg)^{α}.

### Obstructions for GRRs

Observation

Proof.

Suppose that there is an arc fromg tosg, sos ∈S. Sinceα is a group
automorphism, (sg)^{α} =s^{α}g^{α}. Sinceα fixes S,s^{α}∈S, so there is an arc
from g^{α} tos^{α}g^{α}= (sg)^{α}.

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group
automorphism.

SinceS =S^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

The generalised dicyclic groupDic(A,y) whereAis an abelian group of
even order and y has order 2 in A, is hA,xi wherex ∈/A,x^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

In the generalised dicyclic group D =Dic(A,y), the map ιdefined by
a^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.
Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

Abelian groups containing a non-involution (i.e. of exponent greater than 2); and generalised dicyclic groups cannot have GRRs.

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

automorphism. SinceS =S^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR

unlessα is the identity map. Generalised Dicyclic Groups

The generalised dicyclic groupDic(A,y) whereAis an abelian group of
even order and y has order 2 in A, is hA,xi wherex ∈/A,x^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

In the generalised dicyclic group D =Dic(A,y), the map ιdefined by
a^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.
Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

Abelian groups containing a non-involution (i.e. of exponent greater than 2); and generalised dicyclic groups cannot have GRRs.

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

automorphism. SinceS =S^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

The generalised dicyclic groupDic(A,y) whereAis an abelian group of
even order and y has order 2 in A, is hA,xi wherex ∈/A,x^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

In the generalised dicyclic group D =Dic(A,y), the map ιdefined by
a^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.
Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

Abelian groups containing a non-involution (i.e. of exponent greater than 2); and generalised dicyclic groups cannot have GRRs.

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

automorphism. SinceS =S^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

The generalised dicyclic groupDic(A,y) whereAis an abelian group of even order and y has order 2 in A,

is hA,xi wherex ∈/A,x^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.
Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

automorphism. SinceS =S^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

The generalised dicyclic groupDic(A,y) whereAis an abelian group of even order and y has order 2 in A, is hA,xi wherex ∈/A,

x^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.
Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

The generalised dicyclic groupDic(A,y) whereAis an abelian group of
even order and y has order 2 in A, is hA,xi wherex ∈/A,x^{2} =y,

and
x^{−1}ax =a^{−1} for everya∈A.

^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.
Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.
Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

In the generalised dicyclic group D =Dic(A,y), the map ιdefined by
a^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.

Again S^{ι} =S, so a Cayley graph on D can never be a GRR.
Theorem (Nowitz 1968, Watkins 1971)

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

In the generalised dicyclic group D =Dic(A,y), the map ιdefined by
a^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.

Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

In the generalised dicyclic group D =Dic(A,y), the map ιdefined by
a^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.

Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

Abelian groups containing a non-involution (i.e. of exponent greater than 2);

and generalised dicyclic groups cannot have GRRs.

### Obstructions for GRRs

Abelian groups

A group G is abelian if and only if the map g^{α}=g^{−1} is a group

^{−1} for a graph, this map fixes S, so a Cayley
graph onG can never be a GRR unlessα is the identity map.

Generalised Dicyclic Groups

^{2} =y, and
x^{−1}ax =a^{−1} for everya∈A.

^{ι} =a for a∈A, andg^{ι} =g^{−1} for g ∈D−Ais a group automorphism.

Again S^{ι} =S, so a Cayley graph on D can never be a GRR.

Theorem (Nowitz 1968, Watkins 1971)

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G.

Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof.

If the graph has no edges and n>2 vertices, its automorphism group is Sym(n) which does not act regularly on the n vertices.

So we may assume that S 6=∅, buthSi 6=G. Lets ∈S.
Defineα byg^{α} =g ifg ∈ hSi, andg^{α} =gs otherwise. Since

right-multiplication bys fixes hSi, this is an automorphism of the graph. The automorphism group of the graph has more than one element fixing e, so is not regular.

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof.

If the graph has no edges and n>2 vertices, its automorphism group is Sym(n) which does not act regularly on the n vertices.

So we may assume that S 6=∅, buthSi 6=G. Lets ∈S.
Defineα byg^{α} =g ifg ∈ hSi, andg^{α} =gs otherwise. Since

right-multiplication bys fixes hSi, this is an automorphism of the graph. The automorphism group of the graph has more than one element fixing e, so is not regular.

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof.

If the graph has no edges and n>2 vertices, its automorphism group is Sym(n) which does not act regularly on the n vertices.

So we may assume that S 6=∅, buthSi 6=G. Lets ∈S.
Defineα byg^{α} =g ifg ∈ hSi, andg^{α} =gs otherwise. Since

right-multiplication bys fixes hSi, this is an automorphism of the graph. The automorphism group of the graph has more than one element fixing e, so is not regular.

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof.

So we may assume that S 6=∅, buthSi 6=G.

Lets ∈S.
Defineα byg^{α} =g ifg ∈ hSi, andg^{α} =gs otherwise. Since

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof.

So we may assume that S 6=∅, buthSi 6=G. Lets ∈S.

Defineα byg^{α} =g ifg ∈ hSi, andg^{α} =gs otherwise. Since

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof.

So we may assume that S 6=∅, buthSi 6=G. Lets ∈S.

Defineα byg^{α} =g if g ∈ hSi, andg^{α} =gs otherwise.

Since

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof.

So we may assume that S 6=∅, buthSi 6=G. Lets ∈S.

Defineα byg^{α} =g if g ∈ hSi, andg^{α} =gs otherwise. Since

right-multiplication bys fixes hSi, this is an automorphism of the graph.

The automorphism group of the graph has more than one element fixing e, so is not regular.

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof.

So we may assume that S 6=∅, buthSi 6=G. Lets ∈S.

Defineα byg^{α} =g if g ∈ hSi, andg^{α} =gs otherwise. Since

right-multiplication bys fixes hSi, this is an automorphism of the graph.

The automorphism group of the graph has more than one element fixing e, so is not regular.

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Proof by picture.

fix

e s multiply by s

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Obstruction

If|G|>2 and G cannot be generated without elements of order 2, it cannot have an ORR. (In fact, it has no connected oriented Cayley digraph.)

### Obstructions for ORRs

Observation

The Cayley (di)graph Cay(G,S) is connected if and only ifhSi=G. Observation

A disconnected Cayley (di)graph onG with more than 2 vertices is never a regular representation.

Obstruction

If|G|>2 and G cannot be generated without elements of order 2, it cannot have an ORR. (In fact, it has no connected oriented Cayley digraph.)

### Obstructions for ORRs

Obstruction

If|G|>2 and G cannot be generated without elements of order 2, it cannot have an ORR.

Definition

For an abelian group A, the generalised dihedral groupDih(A) is the group
hA,xi with x^{2}= 1 and x^{−1}ax =a^{−1} for every a∈A. (If A is cyclic this is
a dihedral group.)

Note...

... that in Dih(A), every element ax of Ax has

(ax)^{2} =axax =aa^{−1}x^{2} =e. Thus, generalised dihedral groups cannot be
generated without an element of order 2.

So generalised dihedral groups do not admit ORRs. [Babai, 1980]

### Obstructions for ORRs

Obstruction

If|G|>2 and G cannot be generated without elements of order 2, it cannot have an ORR.

Definition

For an abelian group A, the generalised dihedral groupDih(A) is the group
hA,xi with x^{2}= 1 and x^{−1}ax =a^{−1} for every a∈A.

(If A is cyclic this is a dihedral group.)

Note...

... that in Dih(A), every element ax of Ax has

(ax)^{2} =axax =aa^{−1}x^{2} =e. Thus, generalised dihedral groups cannot be
generated without an element of order 2.

So generalised dihedral groups do not admit ORRs. [Babai, 1980]

### Obstructions for ORRs

Obstruction

If|G|>2 and G cannot be generated without elements of order 2, it cannot have an ORR.

Definition

For an abelian group A, the generalised dihedral groupDih(A) is the group
hA,xi with x^{2}= 1 and x^{−1}ax =a^{−1} for every a∈A. (If A is cyclic this is
a dihedral group.)

Note...

... that in Dih(A), every element ax of Ax has

(ax)^{2} =axax =aa^{−1}x^{2} =e. Thus, generalised dihedral groups cannot be
generated without an element of order 2.

So generalised dihedral groups do not admit ORRs. [Babai, 1980]

### Obstructions for ORRs

Obstruction

If|G|>2 and G cannot be generated without elements of order 2, it cannot have an ORR.

Definition

For an abelian group A, the generalised dihedral groupDih(A) is the group
hA,xi with x^{2}= 1 and x^{−1}ax =a^{−1} for every a∈A. (If A is cyclic this is
a dihedral group.)

Note...

... that in Dih(A), every element ax of Ax has
(ax)^{2} =axax =aa^{−1}x^{2} =e.

Thus, generalised dihedral groups cannot be generated without an element of order 2.

So generalised dihedral groups do not admit ORRs. [Babai, 1980]

### Obstructions for ORRs

Obstruction

If|G|>2 and G cannot be generated without elements of order 2, it cannot have an ORR.

Definition

^{2}= 1 and x^{−1}ax =a^{−1} for every a∈A. (If A is cyclic this is
a dihedral group.)

Note...

... that in Dih(A), every element ax of Ax has

^{2} =axax =aa^{−1}x^{2} =e. Thus, generalised dihedral groups cannot be
generated without an element of order 2.

So generalised dihedral groups do not admit ORRs. [Babai, 1980]

### Obstructions for ORRs

Obstruction

If|G|>2 and G cannot be generated without elements of order 2, it cannot have an ORR.

Definition

^{2}= 1 and x^{−1}ax =a^{−1} for every a∈A. (If A is cyclic this is
a dihedral group.)

Note...

... that in Dih(A), every element ax of Ax has

^{2} =axax =aa^{−1}x^{2} =e. Thus, generalised dihedral groups cannot be
generated without an element of order 2.

So generalised dihedral groups do not admit ORRs. [Babai, 1980]

### Obstructions for DRRs

Observations

Every ORR is a special kind of DRR.

Every GRR is a special kind of DRR. So an obstruction for DRRs would have to be an obstruction for ORRs and for GRRs.

There are none.

### Obstructions for DRRs

Observations

Every ORR is a special kind of DRR. Every GRR is a special kind of DRR.

So an obstruction for DRRs would have to be an obstruction for ORRs and for GRRs.

There are none.

### Obstructions for DRRs

Observations

Every ORR is a special kind of DRR. Every GRR is a special kind of DRR.

So an obstruction for DRRs would have to be an obstruction for ORRs and for GRRs.

There are none.

### Obstructions for DRRs

Observations

Every ORR is a special kind of DRR. Every GRR is a special kind of DRR.

So an obstruction for DRRs would have to be an obstruction for ORRs and for GRRs.

There are none.

### Obstructions for bipartite GRRs

Obstruction

If the group G has a subgroup M of index 2 and there is a non-identity
automorphism ϕofG that maps every element g of G−M to eitherg or
g^{−1},

then G cannot admit a bipartite GRR with the cosets of M as the bipartition sets.

### Obstructions for bipartite GRRs

Obstruction

If the group G has a subgroup M of index 2 and there is a non-identity
automorphism ϕofG that maps every element g of G−M to eitherg or
g^{−1}, then G cannot admit a bipartite GRR with the cosets of M as the
bipartition sets.

### Obstructions for bipartite GRRs

Theorem (Du, Feng, Spiga 2020+)

The groups G and subgroups M that have such an automorphism satisfy one of:

M is abelian and G is not generalised dihedral over M;

M contains an abelian subgroup Z of index 2, and there is some
g ∈G −M such that g^{2}6= 1, g^{2}∈Z∩Z(G), and z^{g} =z^{−1} for
every z ∈Z ; or

Z(M) has index4 in M; there is some g ∈G−M such that: g has order 4;

g inverts every element of Z(M);

there is some m∈M−Z(M)such that gm does not have order2; and
the commutator subgroup of M ishg^{2}i.

### Obstructions for bipartite GRRs

Theorem (Du, Feng, Spiga 2020+)

The groups G and subgroups M that have such an automorphism satisfy one of:

M is abelian and G is not generalised dihedral over M;

M contains an abelian subgroup Z of index 2, and there is some
g ∈G −M such that g^{2} 6= 1, g^{2}∈Z∩Z(G), and z^{g} =z^{−1} for
every z ∈Z ; or

Z(M) has index4 in M; there is some g ∈G−M such that:

g has order 4;

g inverts every element of Z(M);

there is some m∈M−Z(M)such that gm does not have order2; and
the commutator subgroup of M ishg^{2}i.

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

With the exception of abelian groups that do not have exponent 2, and generalised dicyclic groups, and 13 other groups of order at most 32, every group has a GRR.

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR. Theorem (M., Spiga, 2018)

With the exception of generalised dihedral groups, and 11 other groups of order at most 64, every group has an ORR.

Conjecture (Du, Feng, Spiga, 2020+)

With 59 exceptions of order at most 64, the groups classified by the obvious obstruction are the only groups not admitting bipartite GRRs.

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

With the exception of abelian groups that do not have exponent 2, and generalised dicyclic groups,

and 13 other groups of order at most 32, every group has a GRR.

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR. Theorem (M., Spiga, 2018)

With the exception of generalised dihedral groups, and 11 other groups of order at most 64, every group has an ORR.

Conjecture (Du, Feng, Spiga, 2020+)

With 59 exceptions of order at most 64, the groups classified by the obvious obstruction are the only groups not admitting bipartite GRRs.

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

With the exception of abelian groups that do not have exponent 2, and generalised dicyclic groups, and 13 other groups of order at most 32,

every group has a GRR.

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR. Theorem (M., Spiga, 2018)

With the exception of generalised dihedral groups, and 11 other groups of order at most 64, every group has an ORR.

Conjecture (Du, Feng, Spiga, 2020+)

With 59 exceptions of order at most 64, the groups classified by the obvious obstruction are the only groups not admitting bipartite GRRs.

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

With the exception of abelian groups that do not have exponent 2, and generalised dicyclic groups, and 13 other groups of order at most 32, every group has a GRR.

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR. Theorem (M., Spiga, 2018)

Conjecture (Du, Feng, Spiga, 2020+)

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

With the exception of abelian groups that do not have exponent 2, and generalised dicyclic groups, and 13 other groups of order at most 32, every group has a GRR.

Theorem (Babai, 1980)

With 5 small exceptions of order at most16,

every group has a DRR.

Theorem (M., Spiga, 2018)

Conjecture (Du, Feng, Spiga, 2020+)

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR.

Theorem (M., Spiga, 2018)

Conjecture (Du, Feng, Spiga, 2020+)

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR.

Theorem (M., Spiga, 2018)

With the exception of generalised dihedral groups,

and 11 other groups of order at most 64, every group has an ORR.

Conjecture (Du, Feng, Spiga, 2020+)

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR.

Theorem (M., Spiga, 2018)

With the exception of generalised dihedral groups, and 11 other groups of order at most 64,

every group has an ORR.

Conjecture (Du, Feng, Spiga, 2020+)

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR.

Theorem (M., Spiga, 2018)

Conjecture (Du, Feng, Spiga, 2020+)

### There are no other significant obstructions

Theorem (Hetzel 1976, Godsil 1981)

Theorem (Babai, 1980)

With 5 small exceptions of order at most16, every group has a DRR.

Theorem (M., Spiga, 2018)

Conjecture (Du, Feng, Spiga, 2020+)

### Related Results

Theorem (Babai and Imrich, 1979)

Every group of odd order admits a tournament regular representation (and so an ORR), except C3×C3 which does not admit a DRR.

Theorem (Du, Feng, Spiga, 2020+ (arXiv))

Every group that has an abelian subgroup M of index 2 admits a bipartite DRR (with the cosets of M as the bipartition sets), or is one of 22 small exceptions of order at most 64.

Remark

The major techniques for finding DRRs involve looking at the subgraph induced on the neighbours of a vertex and trying to make it asymmetric; this does nothing for bipartite graphs.

Conjecture (Du, Feng, Spiga, 2020+)

“abelian” is not a necessary hypothesis.

### Related Results

Theorem (Babai and Imrich, 1979)

Every group of odd order admits a tournament regular representation (and so an ORR),

except C3×C3 which does not admit a DRR.

Theorem (Du, Feng, Spiga, 2020+ (arXiv))

Every group that has an abelian subgroup M of index 2 admits a bipartite DRR (with the cosets of M as the bipartition sets), or is one of 22 small exceptions of order at most 64.

Remark

The major techniques for finding DRRs involve looking at the subgraph induced on the neighbours of a vertex and trying to make it asymmetric; this does nothing for bipartite graphs.

Conjecture (Du, Feng, Spiga, 2020+)

“abelian” is not a necessary hypothesis.

### Related Results

Theorem (Babai and Imrich, 1979)

Every group of odd order admits a tournament regular representation (and so an ORR), except C3×C3 which does not admit a DRR.

Theorem (Du, Feng, Spiga, 2020+ (arXiv))

Every group that has an abelian subgroup M of index 2 admits a bipartite DRR (with the cosets of M as the bipartition sets), or is one of 22 small exceptions of order at most 64.

Remark

The major techniques for finding DRRs involve looking at the subgraph induced on the neighbours of a vertex and trying to make it asymmetric; this does nothing for bipartite graphs.

Conjecture (Du, Feng, Spiga, 2020+)

“abelian” is not a necessary hypothesis.

### Related Results

Theorem (Babai and Imrich, 1979)

Every group of odd order admits a tournament regular representation (and so an ORR), except C3×C3 which does not admit a DRR.

Theorem (Du, Feng, Spiga, 2020+ (arXiv))

Every group that has an abelian subgroup M of index 2

admits a bipartite DRR (with the cosets of M as the bipartition sets), or is one of 22 small exceptions of order at most 64.

Remark

Conjecture (Du, Feng, Spiga, 2020+)

“abelian” is not a necessary hypothesis.

### Related Results

Theorem (Babai and Imrich, 1979)

Theorem (Du, Feng, Spiga, 2020+ (arXiv))

Remark

Conjecture (Du, Feng, Spiga, 2020+)

“abelian” is not a necessary hypothesis.

### Related Results

Theorem (Babai and Imrich, 1979)

Theorem (Du, Feng, Spiga, 2020+ (arXiv))

Remark

The major techniques for finding DRRs involve looking at the subgraph induced on the neighbours of a vertex and trying to make it asymmetric;

this does nothing for bipartite graphs.

Conjecture (Du, Feng, Spiga, 2020+)

“abelian” is not a necessary hypothesis.

### Related Results

Theorem (Babai and Imrich, 1979)

Theorem (Du, Feng, Spiga, 2020+ (arXiv))

Remark

The major techniques for finding DRRs involve looking at the subgraph induced on the neighbours of a vertex and trying to make it asymmetric;

this does nothing for bipartite graphs.

Conjecture (Du, Feng, Spiga, 2020+)

“abelian” is not a necessary hypothesis.

### Theme/Lesson

With the exception of some “small noise”, regular representations exist as long as obvious structural obstructions are avoided.

## Asymptotics

Theorem (Erd¨os–R´enyi, 1963) Almost every (di)graph is asymmetric.

Idea

Symmetry is rare. “Extra” symmetry may also be rare. Question

If we force a (di)graph to have some symmetry (automorphisms), is it still true that almost every such (di)graph has no symmetry beyond what we force?

Theorem (Erd¨os–R´enyi, 1963) Almost every (di)graph is asymmetric.

Idea

Symmetry is rare. “Extra” symmetry may also be rare.

Question

If we force a (di)graph to have some symmetry (automorphisms), is it still true that almost every such (di)graph has no symmetry beyond what we force?

Theorem (Erd¨os–R´enyi, 1963) Almost every (di)graph is asymmetric.

Idea

Symmetry is rare. “Extra” symmetry may also be rare.

Question

If we force a (di)graph to have some symmetry (automorphisms), is it still true that almost every such (di)graph has no symmetry beyond what we force?

Theorem (Babai, 1980)

With 5 small exceptions, every group has a DRR.

Conjecture (Babai, Godsil 1981–2)

As r (the number of vertices) tends to infinity, the number of DRRs onr vertices tends to 1 as a proportion of the number of Cayley digraphs on r vertices.

Theorem (Babai, 1980)

With 5 small exceptions, every group has a DRR.

Conjecture (Babai, Godsil 1981–2)

As r (the number of vertices) tends to infinity, the number of DRRs onr vertices tends to 1 as a proportion of the number of Cayley digraphs on r vertices.

Theorem (Babai, 1980)

With 5 small exceptions, every group has a DRR.

Conjecture (Babai, Godsil 1981–2)

As r (the number of vertices) tends to infinity, the number of DRRs onr vertices tends to 1 as a proportion of the number of Cayley digraphs on r vertices.

Conjecture (Babai, Godsil 1981–2)

Remarks

loops are irrelevant so we can take the number of Cayley digraphs on
a group of orderr to be 2^{r} (choose the connection set);

Does every group of orderr have this property, or is it only true over all groups of order r, as r→ ∞;

We can look at labelled digraphs, or digraphs up to isomorphism; They made a similar conjecture about GRRs and Cayley graphs.

Conjecture (Babai, Godsil 1981–2)

Remarks

loops are irrelevant

so we can take the number of Cayley digraphs on
a group of orderr to be 2^{r} (choose the connection set);

Does every group of orderr have this property, or is it only true over all groups of order r, as r→ ∞;

We can look at labelled digraphs, or digraphs up to isomorphism; They made a similar conjecture about GRRs and Cayley graphs.

Conjecture (Babai, Godsil 1981–2)

Remarks

loops are irrelevant so we can take the number of Cayley digraphs on
a group of orderr to be 2^{r} (choose the connection set);

Does every group of orderr have this property, or is it only true over all groups of order r, as r→ ∞;

We can look at labelled digraphs, or digraphs up to isomorphism; They made a similar conjecture about GRRs and Cayley graphs.

Conjecture (Babai, Godsil 1981–2)

Remarks

loops are irrelevant so we can take the number of Cayley digraphs on
a group of orderr to be 2^{r} (choose the connection set);

Conjecture (Babai, Godsil 1981–2)

Remarks

^{r} (choose the connection set);

We can look at labelled digraphs, or digraphs up to isomorphism;

They made a similar conjecture about GRRs and Cayley graphs.

Conjecture (Babai, Godsil 1981–2)

Remarks

^{r} (choose the connection set);

We can look at labelled digraphs, or digraphs up to isomorphism;

They made a similar conjecture about GRRs and Cayley graphs.