Vertex-transitive graphs

(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

(4)

Vertex-transitive graphs

(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

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

(7)

Cubic vertex-transitive graphs

(8)

Cubic vertex-transitive graphs

(9)

Cubic vertex-transitive graphs

(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

(12)

Three natural cases

(13)

Three natural cases

(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)

Theorem (Tutte)

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

(16)

m = 1 (the arc-transitive case)

Theorem (Tutte)

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

(17)

m = 1 (the arc-transitive case)

Theorem (Tutte)

(18)

m = 1 (the arc-transitive case)

Theorem (Tutte)

(19)

m = 1 (the arc-transitive case)

Theorem (Tutte)

(20)

m = 1 (the arc-transitive case)

Theorem (Tutte)

(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)

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

(23)

m = 3 (Cayley graphs)

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

(24)

m = 3 (Cayley graphs)

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

(25)

A few tricks

Lemma

G/G^� is isomorphic to one ofZ³2,Z²×Z^r, or Z^r.

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

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

(27)

A few tricks

Lemma

(28)

A few tricks

Lemma

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

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 ∈R₂ⁱ⁺¹ and let C be a central subgroup of G of order 2. Then G/C ∈R₂ⁱ.

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

Lemma

Let G ∈R₂ⁱ⁺¹ and let C be a central subgroup of G of order 2.

Then G/C ∈R₂ⁱ.

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

(32)

2-groups

Lemma

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

(Repeated central extensions.)

(33)

2-groups

Lemma

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

(Repeated central extensions.)

(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

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

(36)

m = 2

(37)

m = 2

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

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) ∼=Z⁴,Z²2 or D₄.

IfGv^Γ(v) ∼=Z⁴ or Z²2, then |Gv|= 4 and we can use the amalgam method.

(In the caseGv^Γ(v) ∼=Z²2, 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

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

(41)

4-valent arc-transitive graphs

(42)

4-valent arc-transitive graphs

Otherwise,Gv^Γ(v) ∼=D₄ (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

Otherwise,Gv^Γ(v) ∼=D₄ (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|log₂(|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”. TheD₄ 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)

� Γ∼=C(r,s),

The proof uses theabelian normal quotient methodand the CFSG.

Corollary

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

(46)

4-valent arc-transitive graphs

Theorem (PSV)

� Γ∼=C(r,s),

Corollary

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

TheD₄ amalgams were determined by Djokovi´c.

(47)

4-valent arc-transitive graphs

Theorem (PSV)

� Γ∼=C(r,s),

Corollary

(48)

4-valent arc-transitive graphs

Theorem (PSV)

� Γ∼=C(r,s),

Corollary

(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!

(51)

Census complete!

(52)

Census complete!

(53)

Census complete!

(54)

Number of graphs of order up to n

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

(55)

Number of graphs of order up to n

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

(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)