# Groups and their actions

N/A
N/A
Protected

Share "Groups and their actions"

Copied!
150
0
0

Full text

(1)

### Regular Representations of Groups

Joy Morris

University of Lethbridge

February 10, 2020 SODO, Rotorua, NZ

(2)
(3)

### Overview

1 Group actions

2 History and definitions

3 Obstructions

4 Asymptotics Main tools

5 Related Work and Open Problems

(4)

## Group Actions

(5)

### 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.

(6)

### 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?

(7)

### 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?

(8)

### 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?

(9)

### 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.

(10)

### 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.

(11)

### 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.

(12)

### 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.

(13)

### 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.

(14)

### 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.

(15)

### 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.

(16)

### 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.

(17)

### 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.

(18)

### 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.

(19)

### Regular action and intuition

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

(20)

### 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

(21)

### 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

(22)

### 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:

(23)

## History and Definitions

(24)

### History

Question [K¨onig, 1936]

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

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

(25)

### History

Question [K¨onig, 1936]

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

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

(26)

### History

Question [K¨onig, 1936]

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

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

(27)

### 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.)

(28)

### 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.)

(29)

### 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.)

(30)

### 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.)

(31)

### 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.)

(32)

### 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.)

(33)

### 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.

(34)

### 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.

(35)

### 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.

(36)

### 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.

(37)

### 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.

(38)

### 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.

(39)

### 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.

(40)

### 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.

(41)

### 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).

(42)

### 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).

(43)

### 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).

(44)

### 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.

(45)

### 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.

(46)

## Obstructions

(47)

### 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)α.

(48)

### 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)α.

(49)

### 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)α.

(50)

### 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)α.

(51)

### 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.

(52)

### 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.

(53)

### 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.

(54)

### 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.

(55)

### 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.

(56)

### 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.

(57)

### 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.

(58)

### 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.

(59)

### 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.

(60)

### 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.

(61)

### 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.

(62)

### 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.

(63)

### 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.

(64)

### 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.

(65)

### 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.

(66)

### 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.

(67)

### 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.

(68)

### 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.

(69)

### 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.

(70)

### 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

(71)

### 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.)

(72)

### 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.)

(73)

### 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]

(74)

### 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]

(75)

### 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]

(76)

### 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]

(77)

### 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]

(78)

### 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]

(79)

### 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.

(80)

### 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.

(81)

### 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.

(82)

### 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.

(83)

### 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.

(84)

### 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.

(85)

### 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 mMZ(M)such that gm does not have order2; and the commutator subgroup of M ishg2i.

(86)

### 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 mMZ(M)such that gm does not have order2; and the commutator subgroup of M ishg2i.

(87)

### 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.

(88)

### 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.

(89)

### 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.

(90)

### 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.

(91)

### 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.

(92)

### 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.

(93)

### 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.

(94)

### 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.

(95)

### 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.

(96)

### 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.

(97)

### 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.

(98)

### 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.

(99)

### 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.

(100)

### 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.

(101)

### 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.

(102)

### 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.

(103)

### 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.

(104)

### Theme/Lesson

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

(105)

## Asymptotics

(106)

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?

(107)

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?

(108)

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?

(109)

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.

(110)

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.

(111)

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.

(112)

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.

(113)

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.

(114)

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.

(115)

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.

(116)

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;

(117)

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;

References

Related documents

The Swedish school authorities have drawn attention to this work and designated the school ‘the best school in Sweden working for equal value 2008’. Student empowerment, child’s

In section 3 we show that the 37170 extreme rays containing in those 29 orbits are, in fact, the

For example, a combinatorial class could be the set of unary-ternary trees where the size of a tree is defined as its number of vertices.. In a more abstract setting consider

Theorem B For every natural number n there exists a computably categorical (noncommutative and nonassociative) ring R such that for some c ∈ R the expanded ring ( R , c) has exactly

61 Waitangi Tribunal Pakakohi and Tangahoe Settlement Claims Report: Wai 759 and 142 (Legislation Direct, Wellington, 2000); Waitangi Tribunal Ngati Maniapoto/Ngati Tama

Using an algebraic representation for graphs of bounded path- width or treewidth we provide simple methods for generating these families in increasing order of the number of

Sessional Com m ittee on the Environm ent 79.. A strong research and development effort, particularly into the integration of control methods, is essential to the

These recent Australian events have also thrown into relief the benefits of the stability of a state fund for financing scheme operations in New Zealand compared to the

cooperation  of  those  same  Councils.    The  prosecutions  under  the  Act  were  largely  governed  by  Mäori  political  dynamics.  If

6 Compensation for Personal Injury in New Zealand: Report of the Royal Commission of Inquiry (Government Printer, December 1967) [Woodhouse Report]... make itself a mutual

There is a finite number h n,d of tight frames of n distinct vectors for C d which are the orbit of a vector under a unitary action of the cyclic group Z n.. These cyclic

The limits set may not achieve a suitable level of protection of downstream environmental values for the Fitzroy River Basin and are not always reflective of all relevant

• Additional High Conservation Value Vegetation (AHCVV) means areas of vegetation which were found during ground-truthing which would otherwise meet the definition of Existing

Vessel biofouling is a major pathway for the introduction of non-indigenous marine organisms into New Zealand territorial waters, some of which may be harmful

Vertices whose random number are smaller than all of the numbers assigned to their adjacent vertices are included in the MIS. Vertices adjacent to the newly inserted vertices

(3) The Committee shall examine only those accounts of receipts and expenditure of the Northern Territory and reports of the Auditor-General for financial years commencing after

Ms LAWRIE (Leader of Government Business): Madam Speaker, I move – That, the Assembly refer the following matters to the Standing Orders Committee for inquiry and report to

Key Words: Lagrange interpolation, linear interpolation on a triangle, sharp error bounds, nite elements, Courant's nite element, multipoint Taylor formula, Kowalewski's

In the Australian context, in 2009 the NSW Valuer-General commissioned an analysis of the impact of wind farm development on rural land in NSW and Victoria (2009 NSW

The processing of the 2007 claim for compensation under MRCA 8 The processing of a subsequent claim in 2010 under MRCA 8 The raising of debts in 2015 in relation to the

5.15 At the time of Mr C’s requests for access to the NDIS, the NDIA did not have any policy or guideline dealing specifically with incarcerated individuals and access to the NDIS.

The owner of the lands has a water allocation of only 16,000kL and its proposed application to irrigate all five (5) proposed public open space areas, inclusive of one (1)

existence. In making such an estimate, the Government Printer was requested to take as understood that each author body would have its report printed by the