# Vertex-transitive graphs

N/A
N/A
Protected

Share "Vertex-transitive graphs"

Copied!
66
0
0

Full text

(1)

## A census of cubic vertex-transitive graphs

Gabriel Verret (Primorska), P. Potoˇcnik and P. Spiga

Queenstown, February 16th, 2012 (SODO)

(2)

## Vertex-transitive graphs

All graphs considered will be finite and simple (undirected, loopless, no multiple edges).

A graph Γ is calledvertex-transitive ifAut(Γ) acts transitively on V(Γ) (and G-vertex-transitiveifG ≤Aut(Γ) acts

transitively onV(Γ)).

WLOG, we may assume connectedness.

(3)

## Vertex-transitive graphs

All graphs considered will be finite and simple (undirected, loopless, no multiple edges).

A graph Γ is calledvertex-transitive ifAut(Γ) acts transitively on V(Γ) (and G-vertex-transitiveifG ≤Aut(Γ) acts

transitively onV(Γ)).

WLOG, we may assume connectedness.

(4)

## Vertex-transitive graphs

All graphs considered will be finite and simple (undirected, loopless, no multiple edges).

A graph Γ is calledvertex-transitive ifAut(Γ) acts transitively on V(Γ) (and G-vertex-transitiveifG ≤Aut(Γ) acts

transitively onV(Γ)).

WLOG, we may assume connectedness.

(5)

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!) Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

Using some new theoretical results and a few tricks, we construced all cubic vertex-transitive graphs of order at most1280.

(6)

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!)

Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

Using some new theoretical results and a few tricks, we construced all cubic vertex-transitive graphs of order at most1280.

(7)

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!) Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

Using some new theoretical results and a few tricks, we construced all cubic vertex-transitive graphs of order at most1280.

(8)

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!) Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

Using some new theoretical results and a few tricks, we construced all cubic vertex-transitive graphs of order at most1280.

(9)

## Cubic vertex-transitive graphs

Vertex-transitive graphs are regular. The first non-trivial case is that ofcubic graphs (3-regular).

Many questions considered first for cubic graphs : semiregular elements, Hamiltonicity, etc... (often still hard in this case!) Acensustests our understanding and is also useful to generated examples, conjectures, etc...

Using ad hoc methods, McKay and Royle (1996) obtained a list which is complete up to 94 vertices.

Using some new theoretical results and a few tricks, we construced all cubic vertex-transitive graphs of order at most1280.

(10)

## Three natural cases

Let Γ be a cubicG-vertex-transitive graph and letm bethe number of orbitsof GvΓ(v) (the permutation group induced by the action of a vertex-stabiliserGv in its action on the neighbourhood Γ(v)).

By vertex-transitivity,m is equal to the number of orbits ofG in its action on the arcs of Γ (anarc is an ordered pair of adjacent vertices).

Since Γ is cubic,m∈ {1,2,3}.

We deal with each of these separately.

(11)

## Three natural cases

Let Γ be a cubicG-vertex-transitive graph and letm bethe number of orbitsof GvΓ(v) (the permutation group induced by the action of a vertex-stabiliserGv in its action on the neighbourhood Γ(v)).

By vertex-transitivity,m is equal to the number of orbits ofG in its action on the arcs of Γ (anarc is an ordered pair of adjacent vertices).

Since Γ is cubic,m∈ {1,2,3}.

We deal with each of these separately.

(12)

## Three natural cases

Let Γ be a cubicG-vertex-transitive graph and letm bethe number of orbitsof GvΓ(v) (the permutation group induced by the action of a vertex-stabiliserGv in its action on the neighbourhood Γ(v)).

By vertex-transitivity,m is equal to the number of orbits ofG in its action on the arcs of Γ (anarc is an ordered pair of adjacent vertices).

Since Γ is cubic,m∈ {1,2,3}.

We deal with each of these separately.

(13)

## Three natural cases

Let Γ be a cubicG-vertex-transitive graph and letm bethe number of orbitsof GvΓ(v) (the permutation group induced by the action of a vertex-stabiliserGv in its action on the neighbourhood Γ(v)).

By vertex-transitivity,m is equal to the number of orbits ofG in its action on the arcs of Γ (anarc is an ordered pair of adjacent vertices).

Since Γ is cubic,m∈ {1,2,3}.

We deal with each of these separately.

(14)

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare known (the structure ofGv and G{uv}).

To find all the graphs up to a certain order, it suﬃces to :

Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

(15)

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare known (the structure ofGv and G{uv}).

To find all the graphs up to a certain order, it suﬃces to :

Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

(16)

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare known (the structure ofGv and G{uv}).

To find all the graphs up to a certain order, it suﬃces to :

Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

(17)

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare known (the structure ofGv and G{uv}).

To find all the graphs up to a certain order, it suﬃces to :

Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

(18)

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare known (the structure ofGv and G{uv}).

To find all the graphs up to a certain order, it suﬃces to :

Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

(19)

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare known (the structure ofGv and G{uv}).

To find all the graphs up to a certain order, it suﬃces to :

Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

(20)

## m = 1 (the arc-transitive case)

This is the easiest case because of the following result.

Theorem (Tutte)

IfΓis a cubic G -arc-transitive graph, then|Gv| ≤48.

|G|grows at most linearly with |V(Γ)|and the amalgamsare known (the structure ofGv and G{uv}).

To find all the graphs up to a certain order, it suﬃces to :

Construct the amalgams (finitely generated amalgamated products of finite groups). There are 7 of these.

Find all the normal subgroups up to a certain index (by using theLowIndexNormalSubgroupsalgorithm in Magma for example).

The census of cubic arc-transitive graphs is now complete up to 10000 vertices (Conder).

(21)

## m = 3 (Cayley graphs)

Ifm= 3, thenGv = 1 andG acts regularly on the vertex-set.

In particular,|G| ≤1280 and Γ∼=Cay(G,S) is a Cayley graph for G.

Naive method : consider all groupsG of order at most 1280 and, for eachG, all possible3-connection sets.

Computationally infeasible.

(22)

## m = 3 (Cayley graphs)

Ifm= 3, thenGv = 1 andG acts regularly on the vertex-set.

In particular,|G| ≤1280 and Γ∼=Cay(G,S) is a Cayley graph for G.

Naive method : consider all groupsG of order at most 1280 and, for eachG, all possible3-connection sets.

Computationally infeasible.

(23)

## m = 3 (Cayley graphs)

Ifm= 3, thenGv = 1 andG acts regularly on the vertex-set.

In particular,|G| ≤1280 and Γ∼=Cay(G,S) is a Cayley graph for G.

Naive method : consider all groupsG of order at most 1280 and, for eachG, all possible 3-connection sets.

Computationally infeasible.

(24)

## m = 3 (Cayley graphs)

Ifm= 3, thenGv = 1 andG acts regularly on the vertex-set.

In particular,|G| ≤1280 and Γ∼=Cay(G,S) is a Cayley graph for G.

Naive method : consider all groupsG of order at most 1280 and, for eachG, all possible 3-connection sets.

Computationally infeasible.

(25)

## A few tricks

Lemma

G/G is isomorphic to one ofZ32,Z2×Zr, or Zr.

Reduces drastically the number of groups we need to consider. Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then Cay(G,S)∼=Cay(G,Sφ).

Only need to consider connection setsup to conjugacy in Aut(G). These simple tricks are enough to make them= 3 case

computationally feasible, except whenG has order 512 or 1024 (too many groups).

(26)

## A few tricks

Lemma

G/G is isomorphic to one ofZ32,Z2×Zr, or Zr.

Reduces drastically the number of groups we need to consider.

Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then Cay(G,S)∼=Cay(G,Sφ).

Only need to consider connection setsup to conjugacy in Aut(G). These simple tricks are enough to make them= 3 case

computationally feasible, except whenG has order 512 or 1024 (too many groups).

(27)

## A few tricks

Lemma

G/G is isomorphic to one ofZ32,Z2×Zr, or Zr.

Reduces drastically the number of groups we need to consider.

Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then Cay(G,S)∼=Cay(G,Sφ).

Only need to consider connection setsup to conjugacy in Aut(G). These simple tricks are enough to make them= 3 case

computationally feasible, except whenG has order 512 or 1024 (too many groups).

(28)

## A few tricks

Lemma

G/G is isomorphic to one ofZ32,Z2×Zr, or Zr.

Reduces drastically the number of groups we need to consider.

Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then Cay(G,S)∼=Cay(G,Sφ).

Only need to consider connection setsup to conjugacy in Aut(G).

These simple tricks are enough to make them= 3 case computationally feasible, except whenG has order 512 or 1024 (too many groups).

(29)

## A few tricks

Lemma

G/G is isomorphic to one ofZ32,Z2×Zr, or Zr.

Reduces drastically the number of groups we need to consider.

Example : 1090235 non-isomorphic groups of order 768, but only 4810 satisfy this Lemma.

Lemma

Let G be a group and letφ∈Aut(G). Then Cay(G,S)∼=Cay(G,Sφ).

Only need to consider connection setsup to conjugacy in Aut(G).

These simple tricks are enough to make them= 3 case computationally feasible, except whenG has order 512 or 1024 (too many groups).

(30)

## 2-groups

Forn a power of 2, let Rn be the class of groups which have order n and admit a generating set consisting of3 involutionsor of 2 elements, one of which is an involution.

Lemma

Let G ∈R2i+1 and let C be a central subgroup of G of order 2. Then G/C ∈R2i.

Using this Lemma, we can constructRi by induction on i. (Repeated central extensions.)

Once we have constructedR512 and R1024, we apply to the groups in these classes the same procedure which we used for other orders.

(31)

## 2-groups

Forn a power of 2, let Rn be the class of groups which have order n and admit a generating set consisting of3 involutionsor of 2 elements, one of which is an involution.

Lemma

Let G ∈R2i+1 and let C be a central subgroup of G of order 2.

Then G/C ∈R2i.

Using this Lemma, we can constructRi by induction on i. (Repeated central extensions.)

Once we have constructedR512 and R1024, we apply to the groups in these classes the same procedure which we used for other orders.

(32)

## 2-groups

Forn a power of 2, let Rn be the class of groups which have order n and admit a generating set consisting of3 involutionsor of 2 elements, one of which is an involution.

Lemma

Let G ∈R2i+1 and let C be a central subgroup of G of order 2.

Then G/C ∈R2i.

Using this Lemma, we can constructRi by induction on i.

(Repeated central extensions.)

Once we have constructedR512 and R1024, we apply to the groups in these classes the same procedure which we used for other orders.

(33)

## 2-groups

Forn a power of 2, let Rn be the class of groups which have order n and admit a generating set consisting of3 involutionsor of 2 elements, one of which is an involution.

Lemma

Let G ∈R2i+1 and let C be a central subgroup of G of order 2.

Then G/C ∈R2i.

Using this Lemma, we can constructRi by induction on i.

(Repeated central extensions.)

Once we have constructedR512 and R1024, we apply to the groups in these classes the same procedure which we used for other orders.

(34)

## m = 2

The most diﬃcult case. The main problem in this case is that a vertex-stabiliser can be arbitrarily large. (In fact, very large with respect to|V(Γ)|).

Note thatGv fixes a unique neighbour ofv. This induces a perfect matchingin Γ.

We define an auxiliary graph, which is 4-valent,G-arc-transitive and has half the order. We also get aG-arc-transitive cycle decomposition of this new graph.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions. By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

(35)

## m = 2

The most diﬃcult case. The main problem in this case is that a vertex-stabiliser can be arbitrarily large. (In fact, very large with respect to|V(Γ)|).

Note thatGv fixes a unique neighbour ofv. This induces aperfect matchingin Γ.

We define an auxiliary graph, which is 4-valent,G-arc-transitive and has half the order. We also get aG-arc-transitive cycle decomposition of this new graph.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions. By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

(36)

## m = 2

The most diﬃcult case. The main problem in this case is that a vertex-stabiliser can be arbitrarily large. (In fact, very large with respect to|V(Γ)|).

Note thatGv fixes a unique neighbour ofv. This induces aperfect matchingin Γ.

We define an auxiliary graph, which is 4-valent,G-arc-transitive and has half the order. We also get aG-arc-transitive cycle decomposition of this new graph.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions. By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

(37)

## m = 2

The most diﬃcult case. The main problem in this case is that a vertex-stabiliser can be arbitrarily large. (In fact, very large with respect to|V(Γ)|).

Note thatGv fixes a unique neighbour ofv. This induces aperfect matchingin Γ.

We define an auxiliary graph, which is 4-valent,G-arc-transitive and has half the order. We also get aG-arc-transitive cycle decomposition of this new graph.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions.

By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

(38)

## m = 2

The most diﬃcult case. The main problem in this case is that a vertex-stabiliser can be arbitrarily large. (In fact, very large with respect to|V(Γ)|).

Note thatGv fixes a unique neighbour ofv. This induces aperfect matchingin Γ.

We define an auxiliary graph, which is 4-valent,G-arc-transitive and has half the order. We also get aG-arc-transitive cycle decomposition of this new graph.

This construction isreversible, hence it suﬃces to find all 4-valent arc-transitive graphs and their arc-transitive cycle decompositions.

By a paper of Miklavic, Potoˇcnik and Wilson, arc-transitive cycle decompositions of 4-valent graphs are well-understood, soit suﬃces to find all 4-valent arc-transitive graphs of order at most 640.

(39)

## 4-valent arc-transitive graphs

Because Γ admits an arc-transitive cycle-decomposition, we have GvΓ(v) ∼=Z4,Z22 or D4.

IfGvΓ(v) ∼=Z4 or Z22, then |Gv|= 4 and we can use the amalgam method.

(In the caseGvΓ(v) ∼=Z22, these correspond to maps and were provided by Conder.)

Otherwise,GvΓ(v) ∼=D4 (and|Gv|can be arbitrarily large). We characterised the graphs for which|Gv|is “very large” with respect to the the order of the graph.

(40)

## 4-valent arc-transitive graphs

Because Γ admits an arc-transitive cycle-decomposition, we have GvΓ(v) ∼=Z4,Z22 or D4.

IfGvΓ(v) ∼=Z4 or Z22, then |Gv|= 4 and we can use the amalgam method.

(In the caseGvΓ(v) ∼=Z22, these correspond to maps and were provided by Conder.)

Otherwise,GvΓ(v) ∼=D4 (and|Gv|can be arbitrarily large). We characterised the graphs for which|Gv|is “very large” with respect to the the order of the graph.

(41)

## 4-valent arc-transitive graphs

Because Γ admits an arc-transitive cycle-decomposition, we have GvΓ(v) ∼=Z4,Z22 or D4.

IfGvΓ(v) ∼=Z4 or Z22, then |Gv|= 4 and we can use the amalgam method.

(In the caseGvΓ(v) ∼=Z22, these correspond to maps and were provided by Conder.)

Otherwise,GvΓ(v) ∼=D4 (and|Gv|can be arbitrarily large). We characterised the graphs for which|Gv|is “very large” with respect to the the order of the graph.

(42)

## 4-valent arc-transitive graphs

Because Γ admits an arc-transitive cycle-decomposition, we have GvΓ(v) ∼=Z4,Z22 or D4.

IfGvΓ(v) ∼=Z4 or Z22, then |Gv|= 4 and we can use the amalgam method.

(In the caseGvΓ(v) ∼=Z22, these correspond to maps and were provided by Conder.)

Otherwise,GvΓ(v) ∼=D4 (and|Gv|can be arbitrarily large).

We characterised the graphs for which|Gv|is “very large” with respect to the the order of the graph.

(43)

## 4-valent arc-transitive graphs

Because Γ admits an arc-transitive cycle-decomposition, we have GvΓ(v) ∼=Z4,Z22 or D4.

IfGvΓ(v) ∼=Z4 or Z22, then |Gv|= 4 and we can use the amalgam method.

(In the caseGvΓ(v) ∼=Z22, these correspond to maps and were provided by Conder.)

Otherwise,GvΓ(v) ∼=D4 (and|Gv|can be arbitrarily large).

We characterised the graphs for which|Gv|is “very large” with respect to the the order of the graph.

(44)

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

Γ∼=C(r,s),

(Γ,G)is one of 18 exceptions,

|VΓ| ≥2|Gv|log2(|Gv|/2). Moreover, the graphs for which equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG. Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”. TheD4 amalgams were determined by Djokovi´c.

This allows us to use the amalgam method (construct the amalgams and find all normal subgroups up to a certain index).

(45)

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

Γ∼=C(r,s),

(Γ,G)is one of 18 exceptions,

|VΓ| ≥2|Gv|log2(|Gv|/2). Moreover, the graphs for which equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”. TheD4 amalgams were determined by Djokovi´c.

This allows us to use the amalgam method (construct the amalgams and find all normal subgroups up to a certain index).

(46)

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

Γ∼=C(r,s),

(Γ,G)is one of 18 exceptions,

|VΓ| ≥2|Gv|log2(|Gv|/2). Moreover, the graphs for which equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”.

TheD4 amalgams were determined by Djokovi´c.

This allows us to use the amalgam method (construct the amalgams and find all normal subgroups up to a certain index).

(47)

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

Γ∼=C(r,s),

(Γ,G)is one of 18 exceptions,

|VΓ| ≥2|Gv|log2(|Gv|/2). Moreover, the graphs for which equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”.

TheD4 amalgams were determined by Djokovi´c.

This allows us to use the amalgam method (construct the amalgams and find all normal subgroups up to a certain index).

(48)

## 4-valent arc-transitive graphs

Theorem (PSV)

Let(Γ,G) be locally-D4. Then one of the following holds:

Γ∼=C(r,s),

(Γ,G)is one of 18 exceptions,

|VΓ| ≥2|Gv|log2(|Gv|/2). Moreover, the graphs for which equality occurs are determined.

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

If|VΓ| ≤640, then |Gv| ≤32or Γ is “understood”.

TheD4 amalgams were determined by Djokovi´c.

This allows us to use the amalgam method (construct the amalgams and find all normal subgroups up to a certain index).

(49)

## Census complete!

To avoid memory issues when running

LowIndexNormalSubgroups, we sometimes need to do some theoretical analysis and “split” the amalgam into cases by adding certain relations.

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

Side note : by combining our data with the census of small 2-arc-transitive 4-valent graphs (Potoˇcnik), we get all 4-valent arc-transitive graphs of order at most 640.

(50)

## Census complete!

To avoid memory issues when running

LowIndexNormalSubgroups, we sometimes need to do some theoretical analysis and “split” the amalgam into cases by adding certain relations.

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

Side note : by combining our data with the census of small 2-arc-transitive 4-valent graphs (Potoˇcnik), we get all 4-valent arc-transitive graphs of order at most 640.

(51)

## Census complete!

To avoid memory issues when running

LowIndexNormalSubgroups, we sometimes need to do some theoretical analysis and “split” the amalgam into cases by adding certain relations.

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

Side note : by combining our data with the census of small 2-arc-transitive 4-valent graphs (Potoˇcnik), we get all 4-valent arc-transitive graphs of order at most 640.

(52)

## Census complete!

To avoid memory issues when running

LowIndexNormalSubgroups, we sometimes need to do some theoretical analysis and “split” the amalgam into cases by adding certain relations.

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

Side note : by combining our data with the census of small 2-arc-transitive 4-valent graphs (Potoˇcnik), we get all 4-valent arc-transitive graphs of order at most 640.

(53)

## Census complete!

To avoid memory issues when running

LowIndexNormalSubgroups, we sometimes need to do some theoretical analysis and “split” the amalgam into cases by adding certain relations.

We obtain all the locally-imprimitive 4-valent arc-transitive graphs of order at most 640.

We recover the cubic graphs and we are done!

There are 111360 non-isomorphic connected vertex-transitive cubic graphs.

Side note : by combining our data with the census of small 2-arc-transitive 4-valent graphs (Potoˇcnik), we get all 4-valent arc-transitive graphs of order at most 640.

(54)

## Number of graphs of order up to n

In gray is the graph of the functionn�→n2/15. In an upcoming paper, we prove that log(f(n))∈Θ((logn)2).

(55)

## Number of graphs of order up to n

In gray is the graph of the functionn�→n2/15. In an upcoming paper, we prove that log(f(n))∈Θ((logn)2).

(56)

## Graphs of order at most 1280 by type

m= 1 m= 2 m= 3 Total Cayley 386 11853 97687 109926

Non-Cayley 96 1338 0 1434

Total 482 13191 97687 111360

Most graphs are Cayley and most of those are GRRs. This seems to be part of a trend.

(57)

## Graphs of order at most 1280 by type

m= 1 m= 2 m= 3 Total Cayley 386 11853 97687 109926

Non-Cayley 96 1338 0 1434

Total 482 13191 97687 111360

Most graphs are Cayley and most of those are GRRs.

This seems to be part of a trend.

(58)

## Graphs of order at most 1280 by type

m= 1 m= 2 m= 3 Total Cayley 386 11853 97687 109926

Non-Cayley 96 1338 0 1434

Total 482 13191 97687 111360

Most graphs are Cayley and most of those are GRRs.

This seems to be part of a trend.

(59)

## Proportion of graphs of diﬀerent types

It is conjectured that almost all vertex-transitive graphs are Cayley (McKay and Praeger). It seems reasonable to conjecture that this is also true for any given valencyk ≥3.

(60)

## Proportion of graphs of diﬀerent types

It is conjectured that almost all vertex-transitive graphs are Cayley (McKay and Praeger). It seems reasonable to conjecture that this is also true for any given valencyk ≥3.

(61)

## Proportion of graphs of diﬀerent types

It is conjectured that almost all vertex-transitive graphs are Cayley (McKay and Praeger). It seems reasonable to conjecture that this is also true for any given valencyk ≥3.

(62)

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Asymptotic enumeration of k-valent vertex-transitive graphs (arc-transitive graphs, Cayley graphs, GRRs).

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs? Challenge

Census of4-valent vertex-transitive graphs of order up to 200? 300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

(63)

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Asymptotic enumeration of k-valent vertex-transitive graphs (arc-transitive graphs, Cayley graphs, GRRs).

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs? Challenge

Census of4-valent vertex-transitive graphs of order up to 200? 300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

(64)

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Asymptotic enumeration of k-valent vertex-transitive graphs (arc-transitive graphs, Cayley graphs, GRRs).

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs?

Challenge

Census of4-valent vertex-transitive graphs of order up to 200? 300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

(65)

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Asymptotic enumeration of k-valent vertex-transitive graphs (arc-transitive graphs, Cayley graphs, GRRs).

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs?

Challenge

Census of4-valent vertex-transitive graphs of order up to 200?

300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

(66)

## Open problems

We tested the graphs for various problems and conjectures (Hamiltonicity, degree/diameter, cages...)

Problem

Asymptotic enumeration of k-valent vertex-transitive graphs (arc-transitive graphs, Cayley graphs, GRRs).

Question

Are almost all k-valent vertex-transitive graphs Cayley? GRRs?

Challenge

Census of4-valent vertex-transitive graphs of order up to 200?

300?

Magmafiles containing the graphs can be found online at : http://www.matapp.unimib.it/˜spiga/

References

Related documents

Figures 4 and 5 are a series of graphs which show the extreme maximum and minimum, the mean daily maximum and minimum and mean monthly maxi- mum and minimum

We discuss related results along two strands: the problem of finding decompositions of large graphs with high minimum degree and the problem of decomposing bipartite graphs

add V random shortcuts to grid graphs and others A* uses ~ log E steps to find a path.

Worksheet 4: Sorting shapes and using tables Worksheet 12: Creating column graphs Assessment Activity Sheets 2, 3 &amp;

Worksheet 4: Sorting shapes and using tables Worksheet 12: Creating column graphs Assessment Activity Sheets 2, 3 &amp;

Worksheet 3: Understanding and drawing tally charts Worksheet 4: Understanding and drawing column graphs Assessment Activity Sheets 1 &amp;

the uniquely defined outer border cycle of M separates one (infinite) background component and a finite number of improper holes from M any inner border cycle of M separates a

 For studying Cayley graphs we want to decide existence of regular subgroups maybe in primitive groups – but a graph has a 2-transitive automorphism group only if it is empty

“Leaky” graphs are a more realistic model of graph-like nanostructures because they take quantum tunneling into account.. Summarizing

Using generalised metrics on transitive Courant algebroids we prove in Section 7 that the heterotic Einstein equations are preserved by T-duality.. A further consequence of (1.1)

By the construction described in Teorem 3 we can construct designs admitting a large transitive automorphism group. Codes of these designs are good candidates for permutation

There will be more vertex-transitive graphs, but essentially we may repeat the same line of arguments to compute the automorphisms. Instead of using full automorphims group we have

You should prove for yourself the vertex form of Menger’s Theorem for undirected graphs.. 8.2

Graphs in Life: Global Internet Connections.. Graphs in Life: Social

Kouider [Path partitions and cycle partitions of eulerian graphs of maximum degree 4, Studia Sci... Xu [Haj´ os conjecture and

By looking at the graphs on the previous page, when the toxin levels are high (ie: the squid is defecting) around the 4 area, the bacteria that are most common in that group are ones

Mar´ıa del R´ıo Francos (IMate, UNAM) Flag graphs and symmetry type graphs SCDO’16, Queenstown,

Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type).. Once we have the graphs, we still have to do a

Theorem ( Zhou &amp; Feng, J. Graph Theory, 2010 ) Let p &gt; q be odd primes and X a connected cubic vertex-transitive non-Cayley graph of order 2pq... Cubic VNC-graphs of order

Form appropriate 4 element generating sets and build corresponding Cayley graphs. Take only those graphs that are connected

The abelian normal quotient method: look for a nontrivial, abelian, minimal normal subgroup N and consider quotients until you reach a semisimple group.. Note that if N is

Frelih-Kutnar (2013): A cubic arc-transitive tetracirculant is one of 17 sporadic examples or in one of two infinite families.. Frelih-Kutnar (2013): A cubic

Rich theory of cartesian decompositions preserved by groups with a transitive minimal normal subgroup.