Vertex-primitive graphs of valency 5

(1)

Vertex-primitive graphs of valency 5

Gabriel Verret

The University of Western Australia

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

(2)

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

(3)

Primitive groups

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

(4)

Primitive groups

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

(5)

Primitive groups

(6)

Primitive groups

(7)

Vertex-primitive graphs

Vertex-primitive graphs areconnected(or edgeless).

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

Valency 1 =⇒ K₂. 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?).

(8)

Vertex-primitive graphs

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

They are vertex-transitive and thus regular.

(9)

Vertex-primitive graphs

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

(10)

Vertex-primitive graphs

Valency 1 =⇒ K₂.

Valency 2 =⇒ Cp.

(11)

Vertex-primitive graphs

(12)

Vertex-primitive graphs

(13)

Vertex-primitive graphs

(14)

Vertex-primitive graphs

(15)

Vertex-primitive graphs of valency 5

Aut(Γ) Aut(Γ)_v |V(Γ)|

Z⁴₂oSym(5) Sym(5) 16 PΓL(2,9) AGL(1,5)×Z2 36

PGL(2,11) D₁₀ 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₁₂₀³^−p p ≡ ±1,±9 (mod 40) PΣL(2,p²) Sym(5) ^p⁶₁₂₀^−p² p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) ^p⁹^(p⁶^−1)(p₂₄₀⁴^−1)(p²⁻¹⁾ p ≡ ±1 (mod 8) PGSp(6,p) Sym(5) ^p⁹^(p⁶^−1)(p₁₂₀⁴^−1)(p²⁻¹⁾ p≡ ±3 (mod 8), p ≥11 (Note K6 hiding sneakily...)

(16)

Vertex-primitive graphs of valency 5

PGL(2,11) D₁₀ 66

Th Sym(5) 756 216 199 065 600 Aut(Γ) Aut(Γ)v |V(Γ)| Conditions PSL(2,p) Alt(5) ^p₁₂₀³^−p p ≡ ±1,±9 (mod 40) PΣL(2,p²) Sym(5) ^p⁶₁₂₀^−p² p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) ^p⁹^(p⁶^−1)(p₂₄₀⁴^−1)(p²⁻¹⁾ p ≡ ±1 (mod 8) PGSp(6,p) Sym(5) ^p⁹^(p⁶^−1)(p₁₂₀⁴^−1)(p²⁻¹⁾ p≡ ±3 (mod 8), p ≥11

(Note K6 hiding sneakily...)

(17)

Vertex-primitive graphs of valency 5

PGL(2,11) D₁₀ 66

Th Sym(5) 756 216 199 065 600 Aut(Γ) Aut(Γ)v |V(Γ)| Conditions PSL(2,p) Alt(5) ^p₁₂₀³^−p p ≡ ±1,±9 (mod 40) PΣL(2,p²) Sym(5) ^p⁶₁₂₀^−p² p ≡ ±3 (mod 10)

PSp(6,p) Sym(5) ^p⁹^(p⁶^−1)(p₂₄₀⁴^−1)(p²⁻¹⁾ p ≡ ±1 (mod 8) PGSp(6,p) Sym(5) ^p⁹^(p⁶^−1)(p₁₂₀⁴^−1)(p²⁻¹⁾ p≡ ±3 (mod 8), p ≥11 (Note K6 hiding sneakily...)

(18)

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.

(19)

Idea of proof: suborbits

(20)

Idea of proof: suborbits

(21)

Idea of proof: suborbits

(22)

Idea of proof: suborbits

(23)

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

(24)

Small suborbits

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

2 =⇒G ∼=D_p.

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

(25)

Small suborbits

2 =⇒G ∼=D_p.

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

(26)

Small suborbits

2 =⇒G ∼=D_p.

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

(27)

Small suborbits

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

(28)

Small suborbits

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

(29)

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.

(30)

Idea of proof

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

(31)

Idea of proof

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

(32)

Idea of proof

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

(33)

Idea of proof

(34)

Idea of proof

(35)

Almost simple groups with a maximal Sym(5)

G m Conditions

Alt(7) 1 M₁₁ 1 M₁₂o Z2 1 J2o Z2 1

Th 2

PSL(2,5²) 1

PΣL(2,p²) 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)|

(36)

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¹⁴, order≈9×10¹⁶)

(37)

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

1. Alternating groups 2. Classical groups

≈7×10¹⁴, order≈9×10¹⁶)

(38)

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

≈7×10¹⁴, order≈9×10¹⁶)

(39)

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

3. Lie groups of exceptional type 4. Sporadic groups

(Thompson sporadic group: degree

≈7×10¹⁴, order≈9×10¹⁶)

(40)

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

≈7×10¹⁴, order≈9×10¹⁶)

(41)

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

(42)

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

(43)

Consequence: half-arc-transitive graphs

There are examples of valency 14.

(44)

Consequence: half-arc-transitive graphs

There are examples of valency 14.

(45)

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.

(46)

Motivation: vertices with almost the same neighbourhood

work.

(47)

Motivation: vertices with almost the same neighbourhood

work.

(48)

Motivation: vertices with almost the same neighbourhood

work.

(49)

Motivation: vertices with almost the same neighbourhood

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.

(50)

Motivation: vertices with almost the same neighbourhood

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.