## Vertex-primitive graphs of valency 5

Gabriel Verret

The University of Western Australia

Symmetries and Covers of Discrete Objects, Queenstown February 18th 2016

## Primitive groups

G is a permutation groupon a finite set Ω.

G is transitiveif, for every two elements of Ω, there is an element ofG mapping one to the other.

G is primitiveif it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

## Primitive groups

G is a permutation groupon a finite set Ω.

G istransitive if, for every two elements of Ω, there is an element ofG mapping one to the other.

G is primitiveif it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

## Primitive groups

G is a permutation groupon a finite set Ω.

G istransitive if, for every two elements of Ω, there is an element ofG mapping one to the other.

G isprimitive if it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

## Primitive groups

G is a permutation groupon a finite set Ω.

G istransitive if, for every two elements of Ω, there is an element ofG mapping one to the other.

G isprimitive if it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

## Primitive groups

G is a permutation groupon a finite set Ω.

G istransitive if, for every two elements of Ω, there is an element ofG mapping one to the other.

G isprimitive if it is transitive and preserves no non-trivial partition of Ω.

A graph isvertex-primitiveif its automorphism group is primitive on vertices.

(Anautomorphismof a graph is an adjacency-preserving permutation of the vertex-set.)

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless).

They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K_{2}.
Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2).

They are vertex-transitive and thus regular.

Valency 1 =⇒ K_{2}.
Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K_{2}.
Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K_{2}.

Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

## Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless). They arenot bipartite(except forK2). They are vertex-transitive and thus regular.

Valency 1 =⇒ K_{2}.
Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

## Vertex-primitive graphs

Valency 1 =⇒ K_{2}.
Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

## Vertex-primitive graphs

Valency 1 =⇒ K_{2}.
Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

## Vertex-primitive graphs

Valency 1 =⇒ K_{2}.
Valency 2 =⇒ Cp.

Valency 3 =⇒ K4, Petersen, Coxeter, Wong, an infinite family on PSL(2,p) (Li, Lu, Maruˇsiˇc 2004).

Valency 4 =⇒ 5 graphs, and 5 infinite families (Li, Lu, Maruˇsiˇc 2004).

Valency 5 =⇒ 7 graphs and 5 infinite families (Fawcett, Giudici, Li, Praeger, Royle, V. 2016?).

## Vertex-primitive graphs of valency 5

Aut(Γ) Aut(Γ)_{v} |V(Γ)|

Z^{4}_{2}oSym(5) Sym(5) 16
PΓL(2,9) AGL(1,5)×Z2 36

PGL(2,11) D_{10} 66

Sym(9) Sym(4)×Sym(5) 126 Suz(8) AGL(1,5) 1 456 J3o2 AΓL(2,4) 17 442

Th Sym(5) 756 216 199 065 600

Aut(Γ) Aut(Γ)v |V(Γ)| Conditions
PSL(2,p) Alt(5) ^{p}_{120}^{3}^{−p} p ≡ ±1,±9 (mod 40)
PΣL(2,p^{2}) Sym(5) ^{p}^{6}_{120}^{−p}^{2} p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) ^{p}^{9}^{(p}^{6}^{−1)(p}_{240}^{4}^{−1)(p}^{2}^{−1)} p ≡ ±1 (mod 8)
PGSp(6,p) Sym(5) ^{p}^{9}^{(p}^{6}^{−1)(p}_{120}^{4}^{−1)(p}^{2}^{−1)} p≡ ±3 (mod 8), p ≥11
(Note K6 hiding sneakily...)

## Vertex-primitive graphs of valency 5

Aut(Γ) Aut(Γ)_{v} |V(Γ)|

Z^{4}_{2}oSym(5) Sym(5) 16
PΓL(2,9) AGL(1,5)×Z2 36

PGL(2,11) D_{10} 66

Sym(9) Sym(4)×Sym(5) 126 Suz(8) AGL(1,5) 1 456 J3o2 AΓL(2,4) 17 442

Th Sym(5) 756 216 199 065 600
Aut(Γ) Aut(Γ)v |V(Γ)| Conditions
PSL(2,p) Alt(5) ^{p}_{120}^{3}^{−p} p ≡ ±1,±9 (mod 40)
PΣL(2,p^{2}) Sym(5) ^{p}^{6}_{120}^{−p}^{2} p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) ^{p}^{9}^{(p}^{6}^{−1)(p}_{240}^{4}^{−1)(p}^{2}^{−1)} p ≡ ±1 (mod 8)
PGSp(6,p) Sym(5) ^{p}^{9}^{(p}^{6}^{−1)(p}_{120}^{4}^{−1)(p}^{2}^{−1)} p≡ ±3 (mod 8), p ≥11

(Note K6 hiding sneakily...)

## Vertex-primitive graphs of valency 5

Aut(Γ) Aut(Γ)_{v} |V(Γ)|

Z^{4}_{2}oSym(5) Sym(5) 16
PΓL(2,9) AGL(1,5)×Z2 36

PGL(2,11) D_{10} 66

Sym(9) Sym(4)×Sym(5) 126 Suz(8) AGL(1,5) 1 456 J3o2 AΓL(2,4) 17 442

Th Sym(5) 756 216 199 065 600
Aut(Γ) Aut(Γ)v |V(Γ)| Conditions
PSL(2,p) Alt(5) ^{p}_{120}^{3}^{−p} p ≡ ±1,±9 (mod 40)
PΣL(2,p^{2}) Sym(5) ^{p}^{6}_{120}^{−p}^{2} p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) ^{p}^{9}^{(p}^{6}^{−1)(p}_{240}^{4}^{−1)(p}^{2}^{−1)} p ≡ ±1 (mod 8)
PGSp(6,p) Sym(5) ^{p}^{9}^{(p}^{6}^{−1)(p}_{120}^{4}^{−1)(p}^{2}^{−1)} p≡ ±3 (mod 8), p ≥11
(Note K6 hiding sneakily...)

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

To find all vertex-primitive graphs of small valency, we first find all primitive groups withsmall suborbits...

...and then do a littlemore work.

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

To find all vertex-primitive graphs of small valency, we first find all primitive groups withsmall suborbits...

...and then do a littlemore work.

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

To find all vertex-primitive graphs of small valency, we first find all primitive groups withsmall suborbits...

...and then do a littlemore work.

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

...and then do a littlemore work.

## Idea of proof: suborbits

An orbit of the point-stabiliserGω is called asuborbit of G.

In an arc-transitive graph, theneighbourhoodof a vertex is a suborbit of the automorphism group.

In a vertex-transitive graph, the neighbourhood is aunion of suborbits.

...and then do a littlemore work.

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).
2 =⇒G ∼=D_{p}.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)). 5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=D_{p}.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)). 5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=D_{p}.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)). 5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=D_{p}.

3 =⇒G ∼=...(Wong 1966).

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=D_{p}.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)).

5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

## Small suborbits

IfG is primitive and has a suborbit of length...

1 =⇒G ∼=Zp (non-trivial suborbit).

2 =⇒G ∼=D_{p}.

3 =⇒G ∼=...(Wong 1966).

4 =⇒G ∼=...(Sims 1967, Quirin 1971, Wang 1992 (CFSG)).

5 =⇒G ∼=...(Fawcett, Giudici, Li, Praeger, Royle, V. 2016 (CFSG!)).

## Idea of proof

Let ∆ be asuborbit of length 5 forG_{ω}.

Wang (1995,1996) dealt with the case when G_{ω}^{∆} is soluble, or
whenG_{ω}^{∆} is insoluble and unfaithful. (With a few omissions.)
It remains to deal with the case whenG_{ω} is isomorphic to Alt(5)
orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

## Idea of proof

Let ∆ be asuborbit of length 5 forG_{ω}.

Wang (1995,1996) dealt with the case whenG_{ω}^{∆} is soluble, or
whenG_{ω}^{∆} is insoluble and unfaithful.

(With a few omissions.)
It remains to deal with the case whenG_{ω} is isomorphic to Alt(5)
orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

## Idea of proof

Let ∆ be asuborbit of length 5 forG_{ω}.

Wang (1995,1996) dealt with the case whenG_{ω}^{∆} is soluble, or
whenG_{ω}^{∆} is insoluble and unfaithful. (With a few omissions.)

It remains to deal with the case whenG_{ω} is isomorphic to Alt(5)
orSym(5).

In other words, we are looking for all groups with a core-free maximal subgroup isomorphic toAlt(5) orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

## Idea of proof

Let ∆ be asuborbit of length 5 forG_{ω}.

Wang (1995,1996) dealt with the case whenG_{ω}^{∆} is soluble, or
whenG_{ω}^{∆} is insoluble and unfaithful. (With a few omissions.)
It remains to deal with the case whenG_{ω} is isomorphic to Alt(5)
orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

## Idea of proof

Let ∆ be asuborbit of length 5 forG_{ω}.

Wang (1995,1996) dealt with the case whenG_{ω}^{∆} is soluble, or
whenG_{ω}^{∆} is insoluble and unfaithful. (With a few omissions.)
It remains to deal with the case whenG_{ω} is isomorphic to Alt(5)
orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

## Idea of proof

Let ∆ be asuborbit of length 5 forG_{ω}.

Wang (1995,1996) dealt with the case whenG_{ω}^{∆} is soluble, or
whenG_{ω}^{∆} is insoluble and unfaithful. (With a few omissions.)
It remains to deal with the case whenG_{ω} is isomorphic to Alt(5)
orSym(5).

There are a fewaffineexamples but we quickly reduce to the almost simplecase.

## Almost simple groups with a maximal Sym(5)

G m Conditions

Alt(7) 1
M_{11} 1
M_{12}o Z2 1
J2o Z2 1

Th 2

PSL(2,5^{2}) 1

PΣL(2,p^{2}) 2 p≡ ±3 (mod 10)
PSL(2,2^{2r})o Z2 1 r odd prime

PGL(2,5^{r}) 1 r odd prime
PSL(3,4)ohσi 1 σ a graph-field aut.

PSL(3,5) 1

PSp(6,p) 2 p≡ ±1 (mod 8) PGSp(6,3) 1

PGSp(6,p) 2 p ≡ ±3 (mod 8), p≥11
m:=|N_{G}(Sym(4)) :Sym(4)|

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups

2. Classical groups

3. Lie groups of exceptional type

4. Sporadic groups (Thompson sporadic group: degree

≈7×10^{14}, order≈9×10^{16})

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups 2. Classical groups

3. Lie groups of exceptional type

4. Sporadic groups (Thompson sporadic group: degree

≈7×10^{14}, order≈9×10^{16})

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups 2. Classical groups

3. Lie groups of exceptional type

4. Sporadic groups (Thompson sporadic group: degree

≈7×10^{14}, order≈9×10^{16})

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups 2. Classical groups

3. Lie groups of exceptional type 4. Sporadic groups

(Thompson sporadic group: degree

≈7×10^{14}, order≈9×10^{16})

## Almost simple groups with a maximal Alt(5) or Sym(5)

1. Alternating groups 2. Classical groups

3. Lie groups of exceptional type

4. Sporadic groups (Thompson sporadic group: degree

≈7×10^{14}, order≈9×10^{16})

## Consequence: half-arc-transitive graphs

A graph ishalf-arc-transitiveif its automorphism group is transitive on edges and vertices but not on arcs.

No vertex-primitive half-arc-transitive graph of valency at most 10. There are examples of valency 14.

This leaves valency 12...

## Consequence: half-arc-transitive graphs

A graph ishalf-arc-transitiveif its automorphism group is transitive on edges and vertices but not on arcs.

No vertex-primitive half-arc-transitive graph of valency at most 10.

There are examples of valency 14. This leaves valency 12...

## Consequence: half-arc-transitive graphs

A graph ishalf-arc-transitiveif its automorphism group is transitive on edges and vertices but not on arcs.

No vertex-primitive half-arc-transitive graph of valency at most 10.

There are examples of valency 14.

This leaves valency 12...

## Consequence: half-arc-transitive graphs

No vertex-primitive half-arc-transitive graph of valency at most 10.

There are examples of valency 14.

This leaves valency 12...

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

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

work.

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

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

work.

## Motivation: vertices with almost the same neighbourhood

Easy exercise: a vertex-primitive graph with two vertices having the same neighbourhood must beedgeless.

Theorem (Spiga, V. 2016?)

A vertex-primitive graph with two vertices having neighbourhood differing by oneis either complete or has prime order.

To do the next case (neighbourhooddiffering by two) using our approach, one would need to know the vertex-primitive graphs of valency at most 6.

This looks quite difficult at the moment:

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

work.

## Motivation: vertices with almost the same neighbourhood

Theorem (Spiga, V. 2016?)

This looks quite difficult at the moment:

work.

## Motivation: vertices with almost the same neighbourhood

Theorem (Spiga, V. 2016?)

This looks quite difficult at the moment:

1. Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type).

2. Once we have the graphs, we still have to do a little extra work.

## Motivation: vertices with almost the same neighbourhood

Theorem (Spiga, V. 2016?)

This looks quite difficult at the moment:

1. Finding the vertex-primitive graphs of valency 6 does not seem easy (especially for the exceptional groups of Lie type).

2. Once we have the graphs, we still have to do a little extra work.