2 3 5 7 11 13 17 19 23 29 31 37 41

(1)

2 3 5 7 11 13 17 19 23 29 31 37 41

89 97 101 103 107 109 113 127 131 137 139 149 151 157

173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307

353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659

famnit lectures

■

famnitova predavanja

■ 2

PhD Summer School

in Discrete Mathematics

Marston Conder ■ Edward Dobson ■ Tatsuro Ito

(2)

(3)

PhD Summer School in Discrete Mathematics

(4)

Famnit Lecturs | Famnitova predavanja | 2

(5)

PhD Summer School

in Discrete Mathematics

Marston Conder

Edward Dobson

Tatsuro Ito

(6)

Famnit Lectures 2 | ISSN 2335-3708

PhD Summer School in Discrete Mathematics Dr Marston Conder, University of Auckland, New Zealand Dr Edward T. Dobson, Mississippi State University, USA,

and University of Primorska, Slovenia Dr Tatsuro Ito, Kanazawa University, Japan

Published by

University of Primorska Press, Titov trg 4, 6000 Koper Koper · 2013

Editor-in-Chief Dr Jonatan Vinkler Managing Editor Alen Ježovnik

@ 2013 University of Primorska Press www.hippocampus.si

Print run· 50 ·Not for sale

CIP – Kataložni zapis o publikaciji

Narodna in univerzitetna knjižnica, Ljubljana 519.17(0.034.2)

CONDER, Marston D. E.

Phd summer school in discrite mathematics [Elektronski vir] / Marston Conder, Edward Dobson, Tatsuro Ito. – El. knjiga. - Koper : University of Primorska Press, 2013. – (Famnit lectures = Famnitova predavanja, ISSN 2335-3708 ; 2)

Način dostopa (URL): http://www.hippocampus.si/ISBN/978-961-6832-62-5.pdf Način dostopa (URL): http://www.hippocampus.si/ISBN/978-961-6832-63-2.html ISBN 978-961-6832-62-5 (pdf)

ISBN 978-961-6832-63-2 (html)

1. Dobson, Edward, 1965– 2. Ito, Tatsuro 271775744

(7)

Preface

This is a collection of lecture notes of the PhD Summer School in Discrete Mathemat- ics, held from June 16 to June 21, 2013, by tradition at Rogla, Slovenia. The organization of this summer school came as a combined effort the Faculty of Mathematics, Natural Sciences and Information Technologies and the Andrej Marušiˇc Institute at the Univer- sity of Primorska, and the Centre for Discrete Mathematics at the Faculty of Education at the University of Ljubljana.

The Scientiﬁc Committee of the meeting consisted of Klavdija Kutnar, Aleksander Malniˇc, Dragan Marušiˇc, Štefko Miklaviˇc and Primož Šparl. The Organizing Committee of the meeting consisted of Ademir Hujdurovi´c, Boštjan Frelih and Boštjan Kuzman.

The aim of this Summer School was to bring together senior researchers, junior re- searches and PhD students working in Algebraic Graph Theory. The summer school has consisted of three minicourses given by

• Prof. Marston Conder, University of Auckland, New Zealand,

• Prof. Edward T. Dobson, Mississippi State University, USA & UP, Slovenia, and

• Prof. Tatsuro Ito, Kanazawa University, Japan.

i

(8)

(9)

List of Figures

2.1 The Petersen graph. . . 24

2.2 The Heawood graph labeled with the lines and hyperplanes of³₂ . . . 29

2.3 Γ1Γ2. . . 31

2.4 C8 . . . 31

2.5 C8K¯2 . . . 31

2.6 The Cayley graph Cay(10,{1, 3, 7, 9}). . . 35

v

(12)

(13)

Chapter 1 Graph Symmetries

Prof. Marston Conder

University of Auckland, New Zealand

SUMMARY

•Introduction to symmetries of graphs

•Vertex-transitive and arc-transitive graphs

•s-arc-transitivity (including theorems of Tutte and Weiss)

•Proof of Tutte’s theorem on symmetric cubic graphs

•Use of amalgams and covers to analyse and construct examples

•Some recent developments

1

(14)

(15)

M. D. E. Conder: Graph Symmetries 3

1.1 Introduction to Symmetries of Graphs

Generally, an object is said to havesymmetryif it can betransformed in way that leaves it looking the same as it did originally.

Automorphisms: Anautomorphism(orsymmetry) of a simple graphX= (V,E)is a permutation of the vertices ofXwhich preserves the relation of adjacency; that is, a bijection

π:V→V such that{v^π,w^π} ∈E if and only if{v,w} ∈E.

Under composition, the automorphisms form a group, called theautomorphism group (orsymmetry group) ofX, and this is denoted by Aut(X), or AutX.

Examples

(a) Complete graphs and null graphs: AutK_n∼=AutN_n∼=S_n for alln. (b) Simple cycles: AutC_n∼=D_n(dihedral group of order 2n) for alln≥3.

(c) Simple paths: AutP_n∼=S₂ for alln≥3.

(d) Complete bipartite graphs: AutKm,n∼=Sm×Sn whenm=n, while AutKn,n∼=Sn S₂∼= (S_n×S_n)S₂ (whenm=n).

(e) Star graphs – see above: AutK1,n∼=Sn for alln>1.

(f ) Wheel graphs (cycleC_n−1plusnth vertex joined to all): AutW_n∼=D_n−1 for alln≥5.

(g) Petersen graph: AutP∼=S₅.

Exercise 1: How many automorphisms has the underlying graph (1-skeleton) of each of the ﬁve Platonic solids: the regular tetrahedron, cube, octahedron, dodecahedron and icosahedron?

Exercise 2: Find a simple graph on 6 vertices that has exactly one automorphism.

Exercise 3: Find a simple graph that has exactly three automorphisms. What is thesmall- estsuch graph?

Exercise 4: For largen, do ‘most’ graphs of ordernhave a large automorphism group?

or just the identity automorphism?

One amazing fact about graphs and groups isFrucht’s theorem: in 1939, Robert(o) Frucht proved that given any ﬁnite groupG, there exist inﬁnitely many connected graphsXsuch that AutX is isomorphic toG. And then later, in 1949, he proved thatX may be chosen to be 3-valent. There are several variants and generalisations of this, such as regular rep- resentations for graphs and digraphs (GRRs and DRRs).

The simple graphs of ordern with the largest number of automorphisms are the null graphNnand the complete graphKn, each with automorphism groupSn(the symmetric group onn symbols). For non-null, incomplete graphs of bounded valency (vertex degree), the situation is more interesting.

In this course of lectures, we will devote quote a lot of attention to the case of regular graphs of valency 3, which are often calledcubic graphs.

Exercise 5: For eachn∈ {4, 6, 8, 10, 12, 14, 16}, which 3-valent connected graph onnvertices has the largest number of automorphisms?

For ﬁxed valency, some of the graphs with the largest number of automorphisms do not

(16)

4 1.1 Introduction to Symmetries of Graphs

look particularly nice, or do not have other good properties (e.g. strength/stability, or suitability for broadcast networks). The ‘best’ graphs possess special kinds of symmetry.

Transitivity: A graphX= (V,E)is said to be

• vertex-transitiveif AutXhas a single orbit on the vertex-setV;

• edge-transitiveif AutXhas a single orbit on the edge-setE;

• arc-transitive(orsymmetric) if AutX has a single orbit on the arc-set (that is, the setA={(v,w)| {v,w} ∈E}of all ordered pairs of adjacent vertices);

• distance-transitiveif AutXhas a single orbit on each of the sets{(v,w)|d(v,w) = k}fork=0, 1, 2, . . . ;

• semi-symmetricifXis edge-transitive but not vertex-transitive;

• half-arc-transitiveifXis vertex-transitive and edge-transitive but not arc-transitive.

Examples

(a) Complete graphs:K_nis vertex-transitive, edge-transitive, arc-transitive and distance- transitive.

(b) Simple cycles: Cn is vertex-transitive, edge-transitive, arc-transitive and distance- transitive.

(c) Complete bipartite graphs:K_m,nis edge-transitive, but is vertex-transitive (and arc- transitive and distance-transitive) only whenm=n.

(d) Wheel graphs:W_nis neither vertex-transitive nor edge-transitive (forn≥5).

(e) The Petersen graph is vertex-transitive, edge-transitive, arc-transitive and distance- transitive.

Note thatevery vertex-transitive graph is regular(in the sense of having all vertices of the same degree/valency), since for any two verticesvandw, there is an automorphism θtakingvtow, and thenθtakes the edges incident withvto the edges incident withw. On the other hand, not every edge-transitive graph is regular: counter-examples include allK_m,nform =n. But there exist graphs that are edge-transitive and regular but not vertex-transitive. One example is the smallest semi-symmetric cubic graph, called the Gray graph(discovered by Gray and re-discovered later by Bouwer), on 54 vertices. The smallest semi-symmetric regular graph is theFolkman graph, which is 4-valent on 20 vertices.

Also note that every arc-transitive connected graph without isolated vertices is both vertex- transitive and edge-transitive, but the converse does not hold. Counter-examples are half-arc-transitive. The smallest half-arc-transitive graph is theHolt graph, which is a 4-valent graph on 27 vertices. There are inﬁnitely many larger examples.

Exercise 6: LetX be ak-valent graph, wherek is odd (sayk =3). Show that ifX is both vertex-transitive and edge-transitive, then alsoX is arc-transitive. [Harder ques- tion: does the same thing always happen whenkis even?]

Exercise 7: Prove that every semi-symmetric graph is bipartite.

Exercise 8: Every distance-transitive graph is arc-transitive. Can you ﬁnd an arc-transitive

(17)

graph that is not distance-transitive?

s-arcs: Ans -arcin a graphX= (V,E)is a sequence(v0,v₁, . . . ,v_s)of vertices ofXin which any two consecutive vertices are adjacent and any three consecutive vertices are distinct, that is, {vi−1,v_i} ∈E for 1≤i≤s and v_i−1=v_i+1 for 1≤i<s. The graphX = (V,E)is calleds -arc-transitiveif AutXis transitive on the set of alls-arcs inX.

Examples

(a) Simple cycles:C_niss-arc-transitive for alls≥0, whenevern≥3.

(b) Complete graphs:K_nis 2-arc-transitive, but not 3-arc-transitive, for alln≥3.

(c) The complete bipartite graphKn,nis 3-arc- but not 4-arc-transitive, for alln≥2.

(d) The Petersen graph is 3-arc-transitive, but not 4-arc-transitive.

(e) The Heawood graph (the incidence graph of the projective plane of order 2) is 4-arc- transitive, but not 5-arc-transitive.

Exercise 9: For each of the ﬁve Platonic solids, what is the largest value ofssuch that the underlying graph (1-skeleton) iss-arc-transitive?

Exercise 10: LetX be ans-arc-transitived-valent connected simple graph. Find a lower bound on the order of the stabiliser in AutXof a vertexv∈V(X), in terms ofsandd. Sharp transitivity (‘regularity’): A graphX= (V,E)is said to be

• vertex-regularif the action of AutXon the vertex-setV is regular (that is, for every ordered pair(v,w)of vertices, there is auniqueautomorphism takingvtow);

• edge-regularif the action of AutXon the edge-setEis regular;

• arc-regularif the action of AutXon the arc-setAis regular;

• s -arc-regularif the action of AutXon the set ofs-arcs ofX is regular.

The same terminology applies to actions of a subgroup of AutXonX. For example,Cay- ley graphs(which will be encountered soon) are precisely the graphs that admit a vertex- regular group of automorphisms ... and possibly other automorphisms as well.

Important note: The term ‘distance regular’ means something quite different – a graph X is calleddistance regularif for allj andk, it has the property that for any two verticesvandw at distancej from each other, the number of vertices adjacent towand at distancekfromvis a constant (depending only onj andk, and not onvandw).

1.2 Vertex-transitive and Arc-transitive Graphs

LetX be a vertex-transitive graph, with automorphism groupG, and letH be the stabiliser of any vertexv, that is, the subgroupH =G_v ={g ∈G |v^g =v}. Let us also assume thatXis not null, and hence that every vertex ofXhas the same positive valency.

SinceG is transitive onV =V(X), we may label the vertices with the right cosets ofH inG such that each automorphism g ∈G takes the vertex labelledH to the vertex la- belledH g— that is, the action ofG onV(X)is given by right multiplication on the coset space(G:H) ={H g:g∈G}.

(18)

6 1.2 Vertex-transitive and Arc-transitive Graphs

Next,deﬁneD={g∈G|v^g is adjacent tov}={g∈G| {v,v^g} ∈E(X)}. Then:

Lemma 2.1:

(a)D is a union of double cosets Ha H of H in G (b)D is closed under taking inverses

(c)v^xis adjacent to v^yin X if and only if x y⁻¹∈D

(d)The valency of X is the number of right cosets H g contained in D (e)X is connected if and only if D generates G .

PROOF.

(a) Ifa ∈ D then for allh,h ∈ H we havev^{ha h} =v^{a h} = (v^a)^h, which is the image of a neighbour ofv under an automorphism ﬁxingv, and hence a neighbour ofv, so ha h ∈D. ThusHa H⊆Dwhenevera ∈D, and soDis the union of all such double cosets ofH.

(b) Ifa∈Dthen{vâ,v} ∈E(X), and hence{v,vâ⁻¹}={vâ,v}â⁻¹∈E(X), soa⁻¹∈D.

(c){v^y,v^x} ∈E(X) ⇔ {v,v^{x y}⁻¹}^y∈E(X) ⇔ {v,v^{x y}⁻¹} ∈E(X)⇔ x y⁻¹∈D.

(d) By vertex-transitivity, the valency ofXis the number of neighbours ofv. These neighbours are all of the formvâ fora ∈D, and ifvâ =vâ fora,a ∈D thenvââ⁻¹ =v so a a⁻¹∈G_V=H, or equivalently,a ∈Ha, and conversely, ifa =ha whereh∈H, then vâ =v^ha=vâ. Hence this valency equals the number of right cosets ofHcontained in D.

(e) Neighbours ofvare of the formvâ wherea∈D, and their neighbours are of the form vââ wherea,a ∈D. By induction, vertices at distance at mostkfromvare of the form vâ^kâ^k−1^...a²â¹whereai∈Dfor 1≤i≤k. It follows thatXis connected if and only if every vertex can be written in this form (for somek), or equivalently, if and only if every ele-

ment ofGcan be written as a product of elements ofD.

Lemma 2.2:X is arc-transitive if and only if the stabiliser H of a vertex v of X is transitive on the neighbours of v .

PROOF. IfXis arc-transitive, then for any two neighboursw andw ofv, there exists an automorphismg ∈G taking(v,w)to(v,w ). Any suchg lies inGv, and takesw tow , and it follows thatGvis transitive on the setX(v)of all neighbours ofv. Conversely, suppose thatH=G_vis transitive onX(v). Then for any arcs(v,w)and(v,w ), someg∈G takesvtov, and if the pre-image ofw undergisw, then also someh∈G_vtakeswto w. From these it follows that(v,w)^{h g}= (v,w)^g= (v,w ). ThusXis arc-transitive.

Lemma 2.3:X is arc-transitive if and only if D=Ha H for some a∈G\H , indeed if and only if D=Ha H for some a∈G such that a∈H but a²∈H .

PROOF. By Lemma 2.1, we know thatXis arc-transitive if and only ifH=G_vis transitive on the neighbours ofv, which occurs if and only if every neighbour ofv is of the form w^hfor somew∈X(v)and someh∈Gv=H. By takingv^a=w, we ﬁnd the equivalent condition thatD=Ha Hfor somea∈G\H.

For the second part, note thata⁻¹∈D=Ha H, soa⁻¹=ha h for someh,h ∈H. But thena ha= (h)⁻¹, so(a h)²= (h)⁻¹h∈H, and alsoH(a h)H=Ha hH=Ha H=D, so we

(19)

can replaceabya hand then assume thata²∈H(and stilla∈H).

Constructions: The observations in the preceding lemmas can be turned around to pro- duceconstructionsfor vertex-transitive and arc-transitive graphs, as follows.

LetG be any group,Hany subgroup ofG, andDany union of double cosets ofG such thatH∩D=, andDis closed under taking inverses.[Note: there is also a construction for vertex-transitive digraphs that does not assumeDis inverse-closed.]

Nowdeﬁnea graphX =X(G,H,D)by takingV =V(X)to be the right coset space(G : H) ={H g :g∈G}, andE=E(X)to be the set of all pairs of the form{Hx,Ha x}where a∈Dandx∈G. [This construction is due to Sabidussi (1964)]

The adjacency relation is symmetric, sinceHx=Ha(a⁻¹x), and so this is an undirected simple graph. Also right multiplication gives an action ofG onX, withg∈G taking a vertexHx to the vertexHx g, and an edge{Hx,Ha x}to the edge{Hx g,Ha x g}. This action is transitive on vertices, sincegtakesHtoH g for anyg∈G. The stabiliser of the vertexHis{g∈G|H g=H}, which is the subgroupHitself (sinceH g=Hif and only if g∈H). Valency and connectedness are as in Lemma 2.1.

Note, however, that the action ofG onX(G,H,D)need not be faithful: the kernelK of this action is thecoreofH(the intersection of all conjugatesg⁻¹H gofH) inG. Similarly, the groupG/Kinduced onX(G,H,D)need not be the full automorphism group AutX; it is often possible that the graph admits additional automorphisms.

Cayley graphs: Given a groupGand a setDof elements ofG, theCayley graphCay(G,D) is the graph with vertex-setG, and edge set{{x,a x}:x∈G,a ∈D}. Note that this is a special case of the above, withH={1}.

In particular, Cay(G,D)is vertex-transitive, and the groupGacts faithfully and regularly on the vertex-set, but is not necessarily the full automorphism group. For example, acir- culant(which is a Cayley graph for a cyclic group) can often have more than just simple rotations. Similarly, then-dimensional hypercubeQ_n is the Cayley graph Cay(₂ⁿ,B) whereB is the standard basis (of elementary vectors) for₂ⁿ, but AutQ_n ∼=2S_n ∼= ₂ⁿSn.

1.3 s -arc-transitivity (and Theorems of Tutte and Weiss)

As deﬁned earlier, ans -arcin a graphX is a sequence(v₀,v₁, . . . ,v_s)ofs+1 vertices of X in which any 2 consecutive vertices are adjacent and any 3 consecutive vertices are distinct. The graphXis calleds -arc-transitiveif AutXis transitive on thes-arcs inX. Lemma 3.1:Let X be a vertex-transitive graph of valency k>2, and let G=AutX . Then X is2-arc-transitive if and only if the stabiliser G_v of a vertex v is2-transitive on the k neighbours of v .

PROOF. IfX is 2-arc-transitive, then for any two ordered pairs(u₁,w₁)and(u₂,w₂)of neighbours ofv, some automorphismg∈G takes the 2-arc(u₁,v,w₁)to the 2-arc

(u2,v,w2),

(20)

8 1.3s-arc-transitivity (and Theorems of Tutte and Weiss)

in which caseg ﬁxesvandgtakes(u₁,w₁)to(u₂,w₂); henceG_v is 2-transitive on the neighbourhoodX(v). Conversely, supposeG_v is 2-transitive onX(v), and let(u,v,w) and(u ,v,w )be any two 2-arcs inX. Then by vertex-transitivity, some g ∈G takes v tov, and then ifg takesu touandw tow, say, then someh∈G_v takes(u,v) to(u,v), in which case(u,v,w)^{h g}⁻¹= (u,v,w)^g⁻¹ = (u ,v ,w ); henceX is 2-arc-

transitive.

Exercise 11: For a vertex-transitive graphX of valency 3, what are the possibilities for the permutation group induced onX(v)by the stabiliserGv inG=AutX of a vertexv?

Which of these correspond to arc-transitive actions?

Exercise 12: For an arc-transitive graphXof valency 4, what are the possibilities for the permutation group induced onX(v)by the stabiliserG_vinG=AutXof a vertexv?

Lemma 3.2:Let X be a vertex-transitive graph of valency k>2, and let G=AutX . Then X is(s+1)-arc-transitive if and only if X is s -arc-transitive and the stabiliser Gσof an s -arc σ= (v0,v1, . . . ,vs)is transitive on X(vs)\{vs−1}(the set of k−1neighbours of vsother than vs−1).

PROOF. IfXis(s+1)-arc-transitive, then for anys-arcσ= (v0,v₁, . . . ,v_s)and any vertices wandw inX(vs)\{vs−1}, some automorphismg∈Gtakes the(s+1)-arc(v0,v1, . . . ,vs,w) to the(s+1)-arc(v0,v1, . . . ,vs,w ), in which caseg ﬁxesσ, andgtakesw tow ; hence G_σis transitive onX(vs)\ {vs−1}. Conversely, supposeG_σis transitive onX(vs)\ {vs−1}, and let(v₀,v₁, . . . ,v_s,v_s+1)and(w₀,w₁, . . . ,w_s,w_s+1)be any two(s+1)-arcs inX. Then by s-arc-transitivity, someg∈G takes(v₀,v₁, . . . ,v_s)to(w₀,w₁, . . . ,w_s), and then ifgtakes w_s+1tow , say, then someh∈G_σtakesv_s+1tow , in which case

(v₀,v₁, . . . ,v_s,v_s+1)^{h g}⁻¹= (v₀,v₁, . . . ,v_s,w )^g⁻¹= (w₀,w₁, . . . ,w_s,w_s+1);

henceXis(s+1)-arc-transitive.

The simple cycleC_n(which has valency 2) iss-arc-transitive for alls≥0, as is the union of more than one copy ofC_n. This case is somewhat exceptional. Fork>2, there is an upper bound on values ofs for which there exists a ﬁnites-arc-transitive graph of valencyk, as shown by the theorems of Tutte and Weiss below.

The ﬁrst theorem, due to W.T. Tutte, is for valency 3, and will be proved in Section 4. On the other hand, the second theorem, due to Richard Weiss, is for arbitrary valencyk≥3, but its proof is much more difﬁcult, and is beyond the scope of this course.

Theorem 3.3[Tutte, 1959]:Let X be a ﬁnite connected arc-transitive graph of valency3.

Then X is s -arc-regular(and so|AutX|=3·2^s−1·|V(X)|)for some s≤5. Hence in particular, there are no ﬁnite6-arc-transitive cubic graphs.

The upper bound onsin Tutte’s theorem is sharp; in fact, it is attained by inﬁnitely many graphs, although these graphs are somewhat rare. The smallest example is given below.

Tutte’s 8-cage: This is the smallest 3-valent graph of girth 8, and has 30 vertices. It can be constructed in many different ways. One way is as follows:

In the symmetric groupS6, there are(⁶₂) =15 transpositions (2-cycles), and 5·3·1=15 triple transpositions (sometimes calledsynthemes). Deﬁne a graphTby taking these 30

(21)

permutations as the vertices, and joining each triple transposition(a,b)(c,d)(e,f)by an edge to each of its three transpositions(a,b),(c,d)and(d,e).

The resulting graphT isTutte’s 8-cage. It is 3-valent, bipartite and connected, and the groupS₆induces a group of automorphisms ofTby conjugation of the elements.

Exercise 13: Write down the form of a typical 5-arc(v0,v1, . . . ,v5)in Tutte’s cageT with initial vertexv0being a transposition(a,b). Use this to prove that (a) the groupS6is transitive on all such 5-arcs, and (b)Tis not 6-arc-transitive.

Exercise 14: Prove that the girth (the length of the smallest cycle) of Tutte’s 8-cage is 8.

Now the groupS₆is somewhat special among symmetric groups in that AutS₆is twice as large asS6. In fact,S6admits anouter automorphismthat interchanges the 15 transpositions with the 15 triple transpositions, and interchanges the 40 3-cycles with the 40 double 3-cycles(a,b,c)(d,e,f). Any such outer automorphism reverses a 5-arc in Tutte’s 8-cage, and it follows that Tutte’s 8-cage is 5-arc-transitive.

Note that Tutte’s theorem actually puts a bound on the order of the stabiliser of a vertex (in the automorphism group of a ﬁnite symmetric 3-valent graph). The same thing does not hold for 4-valent symmetric graphs, as shown by the following.

Necklace/wreath graphs: Take a simple cycleCn, wheren ≥3, with vertices labelled 0, 1, 2, . . . ,n−1 in cyclic order, and then replace every vertex j by a pair of verticesuj

andv_j, and join every suchu_j and every suchv_j by an edge to each of the four ver- ticesu_j₋₁,v_j₋₁,u_j₊₁andv_j+1, with addition and subtraction of subscripts taken mod- ulon. The resulting 4-valent graph (called a ‘necklace’ or ‘wreath’ graph) has 2n vertices, and is arc-transitive, with automorphism group isomorphic to the wreath product S₂D_n∼= (S₂)ⁿD_n. In particular, the stabiliser of any vertex has order 2ⁿ, which is un- bounded.

Exercise 15: What is the largest value ofsfor which the above graph (on 2n vertices) is s-arc-transitive?

It is also worth noting here that vertex-stabilisers are bounded for the automorphism groups of maps. Amapis an embedding of a connected graph or multigraph on a surface, dividing the surface into simply-connected regions, called thefacesof the map. By deﬁnition, an automorphism of a mapM preserves incidence between vertices, edges and faces ofM, and it follows that if a vertexv has degreek, then the stabiliser ofv in AutM is a subgroup of the dihedral groupD_k. The most highly symmetric maps are calledrotary, orregular.

Theorem 3.4[Weiss, 1981]:Let X be a ﬁnite connected s -arc-transitive graph of valency k≥3. Then s≤7, and if s=7then k=3^t+1for some t . Hence in particular, there are no ﬁnite8-arc-transitive graphs of valency k whenever k>2.

As with Tutte’s theorem, the upper bound onsin Weiss’s theorem is sharp. In fact, for ev- eryt>0, the incidence graph of a generalised hexagon over GF(3^t)is a 7-arc-transitive graph of valency 3^t+1.

The proof of Weiss’s theorem uses the fact that ifX iss-arc-transitive for somes ≥2, thenXis 2-arc-transitive (by Lemma 3.2), and so the stabiliser inG =AutX of a vertex

(22)

10 1.4 Proof of Tutte’s Theorem on Symmetric Cubic Graphs

vofX is 2-transitive on the neighbourhoodX(v)ofv(by Lemma 3.1). It then uses the classification of finite 2-transitive groups, obtained by Peter Cameron in 1981 using the classification of the finite simple groups (CFSG).

Finally in this section, we give something that is useful in proving Tutte’s theorem (and in other contexts as well):

Lemma 3.5(The ‘even distance’ lemma): For any connected arc-transitive graph X , let G⁺=〈G_v,G_w〉be the subgroup of G=AutX generated by the stabilisers G_vand G_wof any two adjacent vertices v and w . Then

(a)the orbit of v under G⁺contains all vertices at even distance from v, (b)G⁺contains the stabiliser of every vertex of X,

(c)G⁺has index1or2in G=AutX,and (d)|G:G⁺|=2if and only if X is bipartite.

PROOF. LetΩandbe the orbits ofvandwunderG⁺. Thencontainsw^G^v, so contains all neighbours ofv. Similarly,Ωcontains all neighbours ofw, so contains all vertices at distance 2 fromv. AlsoG⁺ contains their stabilisers; for example, ifh ∈G⁺takes v toz, thenG⁺ containsh⁻¹G_vh =G_z. Parts (a) and (b) now follow from these observations, by induction. By the same token, the orbit=w^G⁺contains all vertices at even distance fromw. Hence in particular, every vertex ofX lies inΩ∪. Also by the orbit-stabiliser theorem,|Gv||Ω|=|G⁺|=|Gw|||, and then since|Gv|=|Gw|, this implies

|Ω|=||, and it follows that|Ω|=||=|V(X)|or|V(X)|/2. In the latter case,Ωandare disjoint, which happens if and only ifX is bipartite (with partsΩand), and then also

|G|=|Gv||V(X)|=2|Gv||Ω|=2|G⁺|, soG⁺has index 2 inG. On the other hand, in the former case,Ω ==V(X)and|G|=|Gv||V(X)|=|Gv||Ω|=|G⁺|, and thenG⁺=G. This

proves parts (c) and (d).

1.4 Proof of Tutte’s Theorem on Symmetric Cubic Graphs

Theorem[Tutte, 1959]:Let X be a ﬁnite connected arc-transitive graph of valency3. Then X is s -arc-regular(and so|AutX|=3·2^s−1· |V(X)|)for some s≤5. Hence in particular, there are no ﬁnite6-arc-transitive cubic graphs.

We will prove this in several stages, using only elementary theory of groups and graphs.

First, we lets be the largest positive integert for which the graphX ist-arc-transitive, and letG=AutX.

Then we letσ= (v0,v1, . . . ,vs)be anys-arc inX, and consider the stabilisers inG of the 0-arc(v0), the 1-arc(v0,v1), the 2-arc(v0,v1,v2), and so on.

We use properties of these to show thatX iss-arc-regular, and then by considering the smallestk for which the stabiliser inG of thek-arc(v0,v₁, . . . ,v_k)is abelian, we prove thats≤5.

Lemma 4.1:X is s -arc-regular.

PROOF. We have assumedX iss-arc-transitive, so all we have to do is show that the sta-

(23)

biliser of ans-arc is trivial. So assume the contrary. Then everys-arcσis preserved by some non-trivial automorphismf, and by conjugating by a ‘shunt’ if necessary, we can chooseσ= (v0,v₁, . . . ,v_s)such thatf moves one of the neighbours ofv_s, sayw. Then sincef ﬁxesv_s and its neighbourv_s−1, it must interchangew with the third neighbour w ofv_s. It follows that the stabiliser of thes-arcσ= (v0,v₁, . . . ,v_s)is transitive on the set of two(s+1)-arcs extendingσ, namely(v0,v1, . . . ,vs,w)and(v0,v1, . . . ,vs,w ). HenceX

is(s+1)-arc-transitive, contradiction.

Stabilisers

Letσ= (v0,v1, . . . ,vs)be anys-arc ofX, and letG=AutX, and now deﬁne Hs = G⁽⁰⁾ = G_(v₀₎

H_s−1 = G⁽¹⁾ = G_(v₀,v1)

: : :

H_s−k = G^(k) = G_(v₀,v1,...,vk)

: : :

H0 = G^(s) = G_(v₀,v1,...,vs−1,vs)={1}.

Then working backwards, we ﬁnd that|H_j|=|G^(s−j⁾|=2^j for 0≤j<s, while also|H_s|=

|G⁽⁰⁾|=3·2^s−1and|G|=3·2^s−1· |V(X)|.

Particular automorphisms

As before, letwandw be the other two neighbours ofvs. Also lethandh be the two automorphisms that takeσ= (v0,v1, . . . ,v_s−1,vs)to(v1,v2, . . . ,vs,w)and(v1,v2, . . . ,vs,w ) respectively, and deﬁnex0=hh⁻¹andxj=h^jx0h^−jfor 1≤j≤s. Note thatx0=hh⁻¹ preserves(v₀,v₁, . . . ,v_s−1)and is non-trivial, sox₀must swapv_swith the third neighbour ofv_s−1; hencex₀has order 2. It follows that everyx_jhas order 2.

Moreover,x_j₋₁preserves(v0,v₁, . . . ,v_s−j)and swapsv_s−j₊₁with the third neighbour of v_s−j, for 1≤j <s. Hence in particular,x_j−1∈Hj\Hj−1. Then since|Hj|=2|Hj−1|, we ﬁnd thatHj is generated by{x0,x1, . . . ,x_j−1}for 1≤j <s. Similarly,x_s−1ﬁxesv0but movesv1, sox_s−1∈Hs\H_s−1. Then since|Hs:H_s−1|=3 (a prime),H_s−1is a maximal subgroup ofH_s, soH_sis generated by{x₀,x₁, . . . ,x_s−1}.

Next, consider the subgroupG^∗generated by{x0,x₁, . . . ,x_s}. This containsH_s =G_v₀ and〈x1, .. ,x_s−1,x_s〉=G_u whereu^h =v₀, and so by the ‘even distance’ lemma,G^∗is a subgroup of index 1 or 2 inG (the one we calledG⁺earlier). Hence in particular,

|G^∗|=3·2^s−1· |V(X)|or half of that. Finally, sincehmovesv0tov1(which is at distance 1 fromv0), we ﬁnd thatG=〈h,G^∗〉=〈h,x0,x1, . . . ,xs〉=〈h,x0〉.

We can summarise this in the following lemma.

Lemma 4.2:

(a)Hj=〈x0,x1, . . . ,x_j−1〉for1≤j≤s, (b)G⁺=〈x₀,x₁, . . . ,x_s〉,and

(c)G=〈h,x0,x₁, . . . ,x_s〉=〈h,x0〉.

Note thatH1=〈x0〉andH2=〈x0,x1〉are abelian, with orders 2 and 4 respectively.

(24)

12 1.4 Proof of Tutte’s Theorem on Symmetric Cubic Graphs

Deﬁneλto be the largest value ofjfor whichH_jis abelian.We will show that ²

3(s−1)≤ λ <¹₂(s+2)whenevers≥4, and hence thats≤5 ors=7, and then we will eliminate the possibility thats=7.

Lemma 4.3:If s≥4, then2≤λ <¹₂(s+2).

PROOF. Assume the contrary. We know thatλ≥2, so the assumption implies 2λ≥s+2, and henceλ−1≥s−λ+1. NowH_λ=〈x0,x₁, . . . ,x_λ−1〉is abelian, and therefore so is its conjugateh^s−λ+1H_λh^{−(s−λ+1)}=〈x_s−λ+1,x_s_−λ+2, . . . ,x_s〉. Then sinceλ−1≥s−λ+1, both of these containx_λ−1, and also together they generate〈x0,x₁, . . . ,x_s〉=G⁺. It follows thatx_λ−1commutes with every element ofG⁺. In particular,x_λ−1 commutes withh² (which lies inG⁺since|G:G⁺| ≤2). But that impliesx_λ−1=h²x_λ−1h⁻²=x_λ+1, and then

conjugating byh^λ−1givesx0=x2, contradiction.

Lemma 4.4: The centre of H_j =〈x0,x₁, . . . ,x_j−1〉is generated by{xj−λ, . . . ,x_λ−1}, forλ≤ j<2λ.

PROOF. Every elementxofH_j can be written uniquely in the formx=x_i₁x_i₂. . .x_i_r with 0≤i₁<i₂<···<i_r≤j−1. Now[x_i₁,x_i₁_+λ]=1 since otherwise[x₀,x_λ] =1 and thenx_λ commutes withx₀,x₁, . . . ,x_λ−1, soH_λ+1=〈x0,x₁, . . . ,x_λ〉is abelian, contradiction. Thus x_i₁_+λ∈Z(Hj)wheni₁+λ <j. Similarly[xir,x_i_r_−λ]=1 wheni_r−λ≥0. Hence ifx∈Z(Hj) thenx=x_i₁x_i₂. . .x_i_rwherei₁≥j−λandi_r< λ.

Conversely, if 0≤j−λ≤i < λ≤j thenxi commutes with all ofx0,x1, . . . ,x_λ−1, be- causeH_λ = 〈x0,x1, . . . ,x_λ−1〉is abelian, and with all ofx_λ, . . . ,xj−1, sinceh^λH_λh^−λ =

〈x_λ, . . . ,x_2λ−1〉is abelian (andλ≤j<2λ). Thus every such elementx_i₁x_i₂. . .x_i_ris central

inH_j.

Lemma 4.5:The derived subgroup of Hj+1=〈x0,x1, . . . ,xj〉is a subgroup of〈x1, . . . ,x_j−1〉, for1≤j≤s−2.

PROOF. Each of〈x₁, . . . ,x_j〉and〈x₀, . . . ,x_j₋₁〉has index 2 inH_j₊₁=〈x₀,x₁, . . . ,x_j〉, and is therefore normal inH_j₊₁. Their intersection〈x1, . . . ,x_j−1〉is a normal subgroup, of index 4, and (so) the quotient is abelian. Thus〈x1, . . . ,x_j₋₁〉contains all commutators of elements ofH_j₊₁, and hence contains the derived subgroup ofH_j+1. Next, consider the element[x₀,x_λ] =x₀⁻¹x⁻¹_λ x₀x_λ= (x₀x_λ)². By Lemma 4.5, this lies in

〈x1, . . . ,x_λ−1〉, so can be written in the formx_i₁. . .x_i_rwith 1≤i₁<···<i_r≤λ−1.

We will takeμ=i₁andν=i_r, and show thatμ+λ≥s−1 and 2λ−ν≥s−1, and hence that²₃(s−1)≤λ.

Lemma 4.6:If[x0,x_λ]is written as xi1. . .xir with0<i1<···<ir< λ, then (a)i₁+λ≥s−1,and(b) 2λ−i_r≥s−1.

PROOF. Takeμ=i₁andν=i_r, so that 0< μ≤ν < λ.

For (a), suppose thatμ+λ≤s−2. Then Lemma 4.5 implies that[x0,x_μ+λ]lies in

〈x₁, . . . ,x_μ+λ−1〉,

the centre of which is〈xμ, . . . ,x_λ〉. The latter containsx_λandx_μ. . .x_ν= [x0,x_λ], so both of these commute with[x0,x_μ+λ]. This gives

(25)

[x₀,x_λ]^x^μ+λ = [x₀^x^μ+λ,x_λ^x^μ+λ] = [x₀^x^μ+λ,x_λ]

= [x0[x0,x_μ+λ],x_λ] = [x0,x_μ+λ]⁻¹x₀⁻¹x_λ⁻¹x₀[x0,x_μ+λ]x_λ

= [x₀,x_μ+λ]⁻¹[x₀,x_λ]x⁻¹_λ [x₀,x_μ+λ]x_λ

= [x0,x_μ+λ]⁻¹[x0,x_λ][x0,x_μ+λ] = [x0,x_λ],

and thereforex_μ. . .x_ν= [x0,x_λ]commutes withx_μ+λ, contradiction.

Similarly, if 2λ−ν ≤s−2 then[x0,x_2λ−ν]∈ 〈x1, . . . ,x_2λ−ν−1〉, the centre of which is

〈xλ−ν, . . . ,x_λ〉, so[x0,x_2λ−ν]commutes withx_λ−νandx_μ+λ−ν. . .x_λ=h^λ−ν(xμ. . .x_ν)h^ν−λ= h^λ−ν[x0,x_λ]h^ν−λ= [xλ−ν,x_2λ−ν]. This gives

[x_λ−ν,x_2λ−ν]^x⁰ = [x_λ−ν^x⁰,x_2λ−ν^x⁰] = [x_λ−ν,x_2λ−ν^x⁰]

= [x_λ−ν,[x₀,x_2λ−ν]x_2λ−ν]

= x_λ−νx_2λ−ν[x0,x_2λ−ν]⁻¹x_λ−ν[x0,x_2λ−ν]x_2λ−ν

= x_λ−νx_2λ−νx_λ−νx_2λ−ν = [x_λ−ν,x_2λ−ν],

sox_μ+λ−ν. . .x_λ= [xλ−ν,x_2λ−ν]commutes withx_μ+λ, contradiction. This proves part (b).

Lemma 4.7:If s≥4, thenλ≥²₃(s−1).

PROOF. Lemma 4.6 gives s−1−λ ≤ μ ≤ ν ≤ 2λ−s+1, and then forgettingμandν

and rearranging gives 2s−2≤3λ.

Lemma 4.8:If s≥4, then s=4, 5or7.

PROOF. By Lemmas 3 and 6 we have²₃(s−1)≤λ <¹₂(s+2). Forgettingλand rearranging gives 4s−4<3s+6, sos<10, but on the other hand, fors∈ {6, 8, 9}there is no integer

solution forλ, sos=4, 5 or 7.

Lemma 4.9:s=7.

PROOF. Assume thats =7. Thenλ=4, and 2≤μ≤ν ≤2 soμ=ν =2, which gives [x0,x₄] =x₂. Next we consider[x0,x₅]. By Lemma 4.5, this lies in〈x1,x₂,x₃,x₄〉.

Suppose that(x0x5)²= [x0,x5]lies in〈x1,x2,x3〉. Thenx5x0x5lies in〈x0,x1,x2,x3〉=H4

and so fixes vertexv₃of our original 7-arcσ= (v₀,v₁, . . . ,v₇), and hencex₀fixesv₃^x⁵. Observe thatx₅fixesv₀andv₁but notv₂orv₃, and sov₂^x⁵is the third neighbour ofv₁, different fromv₀andv₂but then also fixed byx₀. It follows thatx₀preserves the 7-arc (v₃^x⁵,v₂^x⁵,v₁,v₂,v₃,v₄,v₅,v₆), contradiction.

Thus[x0,x5] =y x4for somey ∈ 〈x1,x2,x3〉. In particular,y commutes withx0andx4

(sinceλ=4), and alsoy²=1 since〈x1,x2,x3〉is abelian. But now it follows that x₂= [x₀,x₄] = (x₀x₄)²= (x₀y x₄)²= (x₀[x₀,x₅])²

= (x5x₀x₅)²=x₅x₀²x₅=1, a ﬁnal contradiction.

This completes the proof of Tutte’s theorem.

(26)

14 1.5 Amalgams and Covers

1.5 Amalgams and Covers

Recall (from Section 3) that ifX is an arc-transitive graph, with automorphism group G, andH is the stabiliser of a vertexv, thenX may be viewed as a double coset graph X(G,H,D)whereD=Ha Hfor somea∈G(movingvto a neighbour), witha²∈H.

Lemma 5.1:In the arc-transitive graph X(G,H,Ha H), the stabiliser in G of the arc(H,Ha) is the intersection H∩a⁻¹Ha , and the stabiliser of the edge{H,Ha}is the subgroup gener- ated by H∩a⁻¹Ha and a . In particular, the valency of X(G,H,Ha H)is equal to the index

|H:H∩a⁻¹Ha|.

PROOF. Letvbe the vertexH. Then sincea²∈H, the elementainterchangesvwith its neighbourw=v^a, and hence reverses the arc(v,w). Alsoa⁻¹Hais the stabiliser of the vertexv^a=w, soH∩a⁻¹Hais the stabiliser of the arc(v,w). The rest follows easily from

this (and transitivity ofHon the neighbours ofv).

Amalgams for symmetric graphs

For the next part of this section, we will abuse notation and useV,EandArespectively for the stabilisers of the vertexv, the edge{v,w}, and the arc(v,w), wherewis the neighbour ofvthat is interchanged withvby the arc-reversing automorphisma.

The triple(V,E,A)may be called anamalgam. Note thatV∩E=A. Note also that ifXis connected, thenG=〈Ha H〉=〈H,a〉=〈H,H∩a⁻¹Ha,a〉=〈V,E〉.

This amalgamspeciﬁes the kind of group action on X . For example, ifXis 3-valent and V∼=S₃∼=D₃andE∼=V₄(the Klein 4-group), withA=V∩E∼=C₂, then the action ofG on Xis 2-arc-regular, with the elementabeing an involution (reversing the arc(v,w)).

Conversely, from any such triple(V,E,A)we can form the amalgamated free product =V ∗AE (of the groupsV andE with their intersectionA=V∩E as amalgamated subgroup), which is a kind ofuniversalgroup for such actions.

Speciﬁcally,G is an arc-transitive group of automorphisms of the symmetric graphX, acting in the way that is speciﬁed, if and only ifGis a quotient ofvia some homomorphism which preserves the amalgam (that is, preserves the orders ofV,EandA). When that happens, the homomorphism takesV,EandA(faithfully) to the stabilisers of some vertexv, incident edge{v,w}and arc(v,w)respectively,

This gives a way of classifying such graphs, or ﬁnding all of the examples of small order.

Exercise 16: What is the amalgam for the action ofS₃S₂on the graphK_3,3? Is this the same as the amalgam for the Petersen graph?

In 1980, Djoković and Miller determined all possible amalgams for an arc-transitive action of a group on a 3-valent graph with finite vertex-stabiliser. There are precisely seven such amalgams, which they called 1, 2, 2, 3, 4, 4and 5. In each case, the given number is the value ofsfor which the group acts regularly ons-arcs, and indicates that the group contains arc-reversing elements that are involutions (of order 2), whileindicates that every arc-reversing element has order greater than 2. (Note that we requirea²∈H but not necessarilya²=1.) The first examples of finite 3-valent graphs with full auto-

2 3 5 7 11 13 17 19 23 29 31 37 41