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−1y.
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−1y.
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−1y.
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−1y.
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−1y.
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−1y.
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−1y.
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−1y.
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−1y.
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 D8 (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 D8 (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 D8 (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
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.)
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 D8. Its full automorphism group isD8, and the action ofD8 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 D8. Its full automorphism group isD8, and the action ofD8 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 D8. Its full automorphism group isD8, and the action ofD8 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 D12. Its full automorphism group isD12, 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 D12. Its full automorphism group isD12, 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 D12. Its full automorphism group isD12, 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
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
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,x2 =y, and x−1ax =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,x2 =y, and x−1ax =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,x2 =y, and x−1ax =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,x2 =y, and x−1ax =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,
x2 =y, and x−1ax =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,x2 =y,
and x−1ax =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,x2 =y, and x−1ax =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,x2 =y, and x−1ax =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,x2 =y, and x−1ax =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,x2 =y, and x−1ax =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,x2 =y, and x−1ax =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 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.
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 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.
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 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.
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 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 x2= 1 and x−1ax =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−1x2 =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 x2= 1 and x−1ax =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−1x2 =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 x2= 1 and x−1ax =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−1x2 =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 x2= 1 and x−1ax =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−1x2 =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 x2= 1 and x−1ax =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−1x2 =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 x2= 1 and x−1ax =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−1x2 =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 g26= 1, g2∈Z∩Z(G), and zg =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 ishg2i.
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 g2 6= 1, g2∈Z∩Z(G), and zg =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 ishg2i.
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)
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)
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)
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.
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
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
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)
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.
Remarks
loops are irrelevant so we can take the number of Cayley digraphs on a group of orderr to be 2r (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)
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.
Remarks
loops are irrelevant
so we can take the number of Cayley digraphs on a group of orderr to be 2r (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)
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.
Remarks
loops are irrelevant so we can take the number of Cayley digraphs on a group of orderr to be 2r (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)
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.
Remarks
loops are irrelevant so we can take the number of Cayley digraphs on a group of orderr to be 2r (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)
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.
Remarks
loops are irrelevant so we can take the number of Cayley digraphs on a group of orderr to be 2r (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)
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.
Remarks
loops are irrelevant so we can take the number of Cayley digraphs on a group of orderr to be 2r (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.
