DOI 10.1007/s10801-008-0127-2
Homogeneous factorisations of complete graphs with edge-transitive factors
Cai Heng Li·Tian Khoon Lim·Cheryl E. Praeger
Received: 20 April 2007 / Accepted: 13 February 2008 / Published online: 26 February 2008
© Springer Science+Business Media, LLC 2008
Abstract A factorisation of a complete graph Kn is a partition of its edges with each part corresponding to a spanning subgraph (not necessarily connected), called a factor. A factorisation is called homogeneous if there are subgroupsM < G≤Sn
such thatM is vertex-transitive and fixes each factor setwise, andG permutes the factors transitively. We classify the homogeneous factorisations ofKnfor which there are such subgroupsG, M withM transitive on the edges of a factor as well as the vertices. We give infinitely many new examples.
Keywords Graph factorisation·Edge-transitive graph·Homogeneous factorisation
1 Introduction
LetKn:=(V , E)be a complete graph on n vertices, with vertex set V and edge setE:= {{x, y} |x =y andx, y∈V}. A factorisation ofKn is a partition E:=
{E1, . . . , Ek}ofEwith at least two parts such that eachEi is the edge set of a span- ning subgraphi=(V , Ei), called a factor (that is to say, the set of vertices incident
This paper forms part of an Australian Research Council Discovery Grant project, and was a major part of the PhD project of the second author.
C.H. Li·T.K. Lim·C.E. Praeger (
)School of Mathematics and Statistics, University of Western Australia, 35 Stirling Highway, Crawley, WA 6009, Australia
e-mail:praeger@maths.uwa.edu.au C.H. Li
e-mail:li@maths.uwa.edu.au Present address:
T.K. Lim
45 Choa Chu Kang Loop #07-14, 689679, Singapore, Singapore e-mail:limtk@phillip.com.sg
with some edge ofEi is the whole vertex setV). A factorisation(Kn,E)is said to be (G, M)-homogeneous ifM < G≤Sn,Mis transitive onV and fixes each factor set- wise, whileGleavesEinvariant and permutes the factors transitively. Since elements ofGinduce isomorphisms between the factors, all factors are isomorphic, and indeed
‘isomorphic factorisations’ of complete graphs have been well studied, see for exam- ple [3,4,13,14]. Homogeneous factorisations of complete graphs were introduced in [21] (and for graphs in general in [12]). Each vertex-transitive, self-complementary graphtogether with its complement forms a homogeneous factorisation in which the indexkis equal to 2 andE consists of the edge set ofand the edge set of its complement: we may takeM=Aut()andG= M, σwhereσis any permutation that interchangesand its complement. Thus all the papers [1,17,20,26,27,30, 34] give examples of homogeneous factorisations of complete graphs of index 2.
We give a classification of all (G, M)-homogeneous factorisations of Kn such that the groupM acts edge-transitively on some (and hence all) factors. We call such homogeneous factorisations edge-transitive, and similarly, if each factor isM- arc-transitive, then the factorisation is called an arc-transitive homogeneous factori- sation. In Section3 we show that, for each (G, M)-homogeneous, edge-transitive factorisation of Kn, the group G is a 2-homogeneous subgroup of Sn and hence is known, see Subsection2.4. Our classification involves a case-by-case consider- ation of the families of 2-homogeneous groups, and as the classification of finite 2-homogeneous groups relies on the finite simple group classification, so also does our classification.
Another link with previous work is to the partial classification by Thomas Sib- ley [29] of decompositions of complete graphs into isomorphic subgraphs (not nec- essarily spanning subgraphs) preserved by a group acting 2-transitively on the ver- tex set. His classification is complete in the cases where the automorphism group contains either a simple group or PL(2,8)acting 2-transitively on vertices, but is incomplete in the remaining case where the automorphism group is a subgroup of some affine group AGL(d, p). The results of this paper provide a classification of those decompositions considered by Sibley that admit 2-transitive affine groups and are homogeneous factorisations.
Our theorem below involves the following notation: the Ree factorisation ERee(28,3)defined in Definition 3.3, theM-edge-partition E(M)defined in Defi- nition3.2, the cyclotomic factorisations and twisted cycloctomic factorisations de- fined in Definitions4.1and4.16respectively, admissible pairs(G0, M0)defined via Condition4.12, the graphsG(q2, k)from Definition5.4, and the Hamming graph H (9,2)=(Z92, E)where{x, y} ∈Eif and only ifx, ydiffer in exactly one coordi- nate.
Theorem 1.1 Let(Kn,E)be a(G, M)-homogeneous, edge-transitive factorisation ofKn=(V , E)of indexkwith factorsi (1≤i≤k). ThenG, M may be chosen so thatGis 2-transitive onV, each factor isM-arc-transitive, and one of the following holds.
(1) (G, M, n, k)=(Ree(3),PSL(2,8),28,3), andE=ERee(28,3).
(2) G=T G0is an affine 2-transitive permutation group onV =V (a, q) (where n=qa),M=T M0,E=E(M), and precisely one of the following holds.
(a) a=1,E=Cyc(q, k), and eachi∼=GPaley(q,q−k1).
(b) a=1, and(G0, M0)is admissible.
(c) a=2, andq, k, M0, i are as in Tables2or3.
(d) a=4,q=3,M0=21+4,k=5 and eachi∼=H (9,2).
Remark 1.2 (a) For Part 2(b), we give in Condition4.12an explicit list of parameter conditions that determine whether a pair of subgroups of AL(1, q)is admissible.
While there are some examples in Part 2(b) for whichE(M)=Cyc(q, k), the infi- nite family of admissible pairs defined explicitly in Proposition4.18corresponds to infinitely many new factorisations, the twisted cyclotomic factorisations of Defini- tion4.16, because the factors of these factorisations, the twisted generalised Paley graphs, are not isomorphic to generalised Paley graphs (unless(q, k)=(9,2), see Proposition4.18). That is to say, the twisted cyclotomic factorisations are not equiv- alent to the cyclotomic factorisations of Part 2(a). (We say that two factorisations (Kn,E)and(Kn,E)are equivalent if there is a permutationg∈Snsuch thatEg∈E for eachE∈E.)
(b) In some of the examples in Theorem1.1the factors are not connected. This is true in particular for a sub-family of the cycloctomic factorisations, see Lemma4.3.
(c) More details about the examples in Part 2(c) are given in Remark5.7. More- over, Lemma5.6determines precisely which of these factorisations are equivalent to a factorisation in Part 2(a) or 2(b). Even though thei are sometimes generalised Paley graphs or twisted generalised Paley graphs, in most cases the factorisation is new.
(d) The exceptional almost simple example in Part 1 is associated with Ree(3), the only almost simple 2-transitive group whose socle is not 2-transitive.
(e) The exceptional example in Part 2(d) is associated with the exceptional affine 2-transitive groupGwithG0≤21+4.S5, andM0=21+4; it is explored in detail in [23] and [24].
After presenting some preliminary results in Section2, we give the proof of The- orem1.1in the following three sections.
2 Preliminaries
2.1 Graphs
All graphs considered in this paper are finite, undirected and without loops or mul- tiple edges. Thus a graph=(V , E)consists of a vertex setV and a setE of unordered pairs of vertices, called edges. If{α, β} ∈E, thenαandβ are said to be adjacent and the ordered pairs(α, β)and(β, α)are called arcs. The set of arcs ofis denotedA. An automorphism ofis a permutation ofV that leavesE invariant. The set of all automorphisms forms a subgroup Aut()of Sym(V )(the symmetric group onV ), and is called the automorphism group of, and for a sub- groupG≤Aut(),isG-vertex-transitive,G-edge-transitive orG-arc-transitive if Gacts transitively on the vertices, edges or arcs ofrespectively. An arc-transitive
graph is also edge-transitive but the converse is not true in general. Arc-transitivity is characterised in the following lemma (see [2]). Forv∈V ,(v)denotes the set of vertices adjacent tov.
Lemma 2.1 A connected graphisG-arc-transitive if and only ifGis transitive on V and for anyv∈V ,Gvis transitive on(v).
2.2 Cayley graphs
We will often encounter a special kind of vertex-transitive graph called a Cayley graph, defined as follows.
Definition 2.2 For a groupGand a nonempty subsetS ofGsuch that 1G∈/Sand S=S−1= {s−1|s∈S}, the Cayley graph =Cay(G, S) of G relative to S is defined as the graph with vertex setV =Gand edge setEsuch that
{x, y} ∈E⇐⇒yx−1∈S.
A Cayley graph Cay(G, S)is connected if and only ifS =G(see [7, p. 241]).
A permutation groupGonV is semiregular if the only element fixing a point in V is the identity element ofG. A groupGis regular onV if it is both semiregular and transitive, and such groups characterise Cayley graphs as follows.
Lemma 2.3 [2, Lemma 16.3]. A graphis isomorphic to a Cayley graph for some group if and only if some subgroup of Aut()is regular on vertices.
2.3 Permutation groups
A partition of a setV is a familyBof non-empty subsets ofV such that∪B∈BB=V andB∩B= ∅for distinctB, B∈B. LetGbe a group acting on a finite setV. A nonempty subsetB⊆V is called a block forGif for everyg∈G, eitherB∩Bg= ∅ or B=Bg. A block B is said to be trivial if|B| =1 or B=V. Otherwise, B is nontrivial. A partitionBof V is calledG-invariant ifBg ∈B for anyB∈Band g∈G. It is easy to see that the parts of a G-invariant partitionB are blocks for G, and that Gpermutes the elements ofB blockwise inducing a natural, possibly unfaithful, action onB. The groupGis primitive onV ifGis transitive and the only blocks forG are the trivial ones. IfGis transitive but not primitive onV, then G is said to be imprimitive. The lemma below shows that partitions invariant under a transitive permutation group often arise as sets of orbits of normal subgroups. For a groupGacting on a setV, and a pointv∈V, we denote theG-orbit containingvby vG= {vg|g∈G}.
Lemma 2.4 LetG≤Sym(V ), letMbe a normal subgroup ofGand letBbe the set ofM-orbits inV. Then(vM)g=(vg)M for eachvM∈Bandg∈G. MoreoverBis aG-invariant partition ofV, and ifGis transitive onV thenGacts transitively on B, and allM-orbits inV have the same length.
Proof LetvM∈Bandg∈G. Thenu∈(vM)gif and only ifu=vmg for somem∈ M. Nowvmg=(vg)g−1mg, andg−1mgruns through all the elements ofMasmruns throughM. Thus(vM)g=(vg)M∈B, and henceBis aG-invariant partition ofV. Now assume thatGis transitive onV. Then forvM, uM∈B, there existsg∈Gsuch thatvg=uand hence such that(vM)g=(vg)M=uM and|vM| = |(vM)g| = |uM|.
This establishes the remaining assertions.
GroupsG, H acting on setsV , U respectively, are said to be permutationally iso- morphic if there exist a group isomorphismθ:G−→H and a bijectionξ:V −→U such that(ξ(v))θ (g)=ξ(vg)for allg∈Gandv∈V.
2.4 Finite 2-homogeneous groups
LetG≤Sym(V )withV finite. ThenGis 2-homogeneous if it is transitive on the set of 2-element subsets ofV, andGis 2-transitive if it is transitive on the set of ordered pairs of distinct elements ofV. Such groups are known to be almost simple or affine, defined as follows.
The group G is almost simple if it has a unique minimal normal subgroup Soc(G) which is a nonabelian simple group. Equivalently, G is almost simple if T ≤G≤Aut(T )for some nonabelian simple groupT (since an almost simple group Gcan be embedded as a subgroup of Aut(Soc(G)) containing the group of inner automorphisms).
The groupGis affine if it has an elementary abelian regular normal subgroupT ∼= ZRp, for some primep. In this case we may identifyV with anR-dimensional vector space over a field of orderpsuch thatGbecomes a group of affine transformations, namelyG=TG0≤AGL(R, p)withT the group of translations (tx:v−→v+x, for allx, v∈V) and G0≤GL(R, p), the stabiliser of the zero-vector 0∈V. The finite 2-homogeneous but not 2-transitive groups were characterised by Kantor [18]
(or see [16, pp. 368–369]) as 1-dimensional affine groups, while the finite affine 2- transitive groups were classified by Hering and are listed in [19] and [22, Appendix], and the finite almost simple 2-transitive groups are described in [9, Section 7.7].
These classifications rely on the finite simple group classification, and we state the parts of the classification that we will use in this paper below.
Theorem 2.5 LetGbe a finite 2-homogeneous permutation group on a setV with
|V| =n. ThenGhas a unique minimal normal subgroupT and one of the following holds:
(1) T is nonabelian simple and eitherT is 2-transitive, orT =PSL(2,8),n=28 andG=PL(2,8)is 2-transitive.
(2) T =ZRp for some primepand integerR≥1, andG=T G0 is affine, with G0≤L(a, q)whereqa=pR. Moreover, eitherG0has 2-orbitsXand−Xin V\ {0}, orGis 2-transitive andG0is one of the following(note that the symbol
“◦” denotes a central product):
(a) a=1 andG0≤L(1, q),
(b) a≥2 andL(a, q)≥G0SL(a, q),
(c) a=2l≥4 andZq−1◦Sp(a, q)≥G0Sp(a, q),
(d) a=6,qeven andZq−1×Aut(G2(q))≥G0G2(q), (e) a=4,q=2 andG0∼=A6orA7,
(f) a=6,q=3 andG0=SL(2,13),
(g) a=2,q=p=5,7,11 or 23 andG0SL(2,3), ora=2,q=9,11,19,29 or 59 andG0SL(2,5),
(h) a=4,q=3 andG0has a normal extraspecial subgroup E of order 25, and G0/E is isomorphic to a subgroup ofS5.
Remark 2.6 In Theorem2.5(2),Gpreserves onV the structure of ana-dimensional vector space over the finite field Fq. Thus G0≤L(a, q)andV =Faq=V (a, q) whereqa=pRwitha≥1. Also in cases (a)-(h),G0is transitive on the set of nonzero vectors inV, denoted asV∗.
2.5 Orbitals
Now letG≤Sym(V )be transitive onV. ThenGacts faithfully on the set V ×V via the action(v1, v2)g=(v1g, v2g)wherev1, v2∈V andg∈G. The orbits ofGon V ×V are known as the orbitals ofGinV (or simply theG-orbitals). In particular {(v, v)|v∈V}is aG-orbital, called the trivial orbital, and all others are called non- trivial. Furthermore for eachG-orbitalO=(u, v)G, theG-orbitalO∗=(v, u)G is called the paired orbital ofO; ifO=O∗thenOis said to be self-paired.
Lemma 2.7 LetG≤Sym(V )with a transitive normal subgroupM. ThenGleaves invariant the set of nontrivialM-orbitals, and the set of self-paired, non-trivialM- orbitals.
Proof LetO=(u, v)M be a nontrivial M-orbital and g∈G. Since G acts faith- fully on V ×V, it follows from Lemma 2.4 that Og=((u, v)g)M =(ug, vg)M, which is also a nontrivialM-orbital. Moreover, ifO∗=Othen(Og)∗=(vg, ug)M=
((v, u)M)g=((u, v)M)g=Og.
For a transitive subgroupG≤Sym(V ), to each non-trivialG-orbitalO we as- sociate a graph(O)=(V , E(O))whereE(O)= {{x, y} |(x, y)∈O∪O∗}. Then (O)=(O∗),(O)has arc setO∪O∗, isG-edge-transitive for anyO, and isG- arc-transitive if and only ifO=O∗. Moreover the converse holds (see for example [28, Theorem 2.1 (b)] or [32, 7.53 on p. 59]).
Lemma 2.8 For a transitive subgroup G≤Sym(V ) and graph =(V , E) with E= ∅,
(1) isG-arc-transitive if and only ifE=E(O)for some non-trivial self-paired G-orbitalO, and
(2) is G-edge-transitive, but not G-arc-transitive, if and only if E=E(O)for some non-trivialG-orbitalOsuch thatO=O∗.
ForG,Oas above, and for a pointv∈V, the setO(v):= {u|(v, u)∈O}is aGv- orbit inV \ {v}, and each suchGv-orbit arises asO(v)for some non-trivialG-orbital
O(see [9, Section 3.2]). Moreover,O(v)∪O∗(v)is the set(v)of vertices adjacent tovin the graph=(O).
2.6 Affine Cayley graphs
Most of our effort is directed towards considering affine subgroups G≤Sym(V ) with regular minimal normal subgroupT =ZRp, and consequently (see Lemma2.3) the graphs(O)are Cayley graphs forT. We interpretV as a finite vector space over some extension fieldFqofFpandT as the translation groupT = {tx|x∈V}(written additively) ofV, wheretx:v−→v+x. ThusG=TG0withG0≤L(a, q), the stabiliser of the zero vector 0. IfG≤Aut()with=(V , E), then=Cay(T , S) for someG0-invariantS⊂T withS= −S. We bring together the orbital description of edge-transitive Cayley graphs and their definition as Cayley graphs.
Lemma 2.9 LetG=TG0be an affine transitive permutation group on the vector spaceV =V (a, q)whereT =ZRp,G0≤L(a, q)andqa=pR. Let=Cay(V , S) be a Cayley graph on V (withS= −S) and suppose thatG≤Aut(). Then the following hold.
(1) isG-arc-transitive if and only if S=O(0)for a non-trivial self-paired G- orbitalO.
(2) isG-edge-transitive but notG-arc-transitive if and only ifS=O(0)∪O∗(0), for a non-trivialG-orbitalOwithO=O∗. MoreoverO∗(0)= −O(0), and in this caseq is odd.
Proof The ‘connecting set’Sof the Cayley graph=Cay(V , S)is precisely the set of vertices adjacent to the zero-vector 0. Part 1 then follows from Lemma2.1and the remarks following. For part 2, recall from Lemma2.8(2) that=Cay(V , S)is G-edge-transitive but notG-arc-transitive if and only ifE=E(O)for some non- trivialG-orbitalO withO=O∗, that is to say, if and only ifS=O(0)∪O∗(0).
Let s∈O(0)and consider the action of the translation t−s ∈T. Now (0, s)t−s = (−s,0)∈Oand so(0,−s)∈O∗. ThusO∗(0)=(−s)G0= −(sG0)= −O(0). Since in this caseO(0)=O∗(0)it follows thatqis odd.
3 Reduction to the affine case
Throughout the rest of the paper we assume that(Kn,E)is a(G, M)-homogeneous edge-transitive factorisation. We writeKn=(V , E), andE= {E1, . . . , Ek}with cor- responding factorsi=(V , Ei), for 1≤i≤k.
Lemma 3.1 The groupGis 2-homogeneous onV.
Proof Let{x, y}and{u, v}be two-element subsets of V. SinceG is transitive on E, some element ofGmaps{x, y}to a pair{x, y}lying in the same part ofE as {u, v}, sayEi. Then sincei isM-edge-transitive, some element ofMmaps{x, y} to{u, v}. ThusGis 2-homogeneous.
If (Kn,E) is (G, M)-homogeneous arc-transitive then M has exactly k non- trivial orbitals, each self-paired, and they may be labeled so thatEi =E(Oi)and i=(Oi)fori=1, . . . , k. It is convenient to have a standard notation for the cor- responding edge-partition.
Definition 3.2 Suppose that a transitive subgroup M≤Sym(V )has k non-trivial orbitalsO1, . . . ,Ok and each is self-paired. The M-edge-partition is the partition E(M):= {E(Oi)|1≤i≤k}.
Before continuing with the general discussion we make some comments about almost simple 2-transitive groups G. The simple normal subgroup T of G is 2- transitive except when G=Ree(3)is the smallest Ree group acting on 28 points andT =G∼=PSL(2,8)(see [6] or [9, p. 245–253]). This exceptional group gives rise to a homogeneous arc-transitive factorisation of index 3.
Definition 3.3 LetG=Ree(3)acting 2-transitively on a setVof size 28 and letM= G∼=PSL(2,8). There are exactly three non-trivialM-orbitalsO1,O2,O3, each self- paired, and these are permuted transitively by G. Let i :=(Oi)=(V , E(Oi)) for i=1,2,3 (as defined before Lemma 2.8), and let ERee(28,3)=E(M). Then (K28,ERee(28,3))is a(G, M)-homogeneous arc-transitive factorisation.
We note that each of the factors(Oi)isM-arc-transitive of valency 9. Moreover, using MAGMA[8] it is simple to check that(Oi)has automorphism groupMand is not a Cayley graph. We prove below that this is the only homogeneous edge-transitive factorisation of a complete graph with the groupGalmost simple, and hence also the only example for which the factors are not Cayley graphs. We also prove the first assertion of Theorem1.1.
Proposition 3.4 Replacing(G, M)if necessary by slightly larger groups, we may as- sume thatGis 2-transitive onV,MG, and eachi isM-arc-transitive. Moreover, eitherG, M, n,Eare as in Definition3.3, or
(1) G=T G0 andM=T M0are affine withT =ZRp,M0G0≤L(a, q), φ∈M0 (where φ:v−→ −v, for all v∈V ), n=qa, and V =V (a, q), an a-dimensional vector space overFq;
(2) E=E(M)as defined in Definition3.2.
Proof Since M fixes each of the Ei setwise,M is contained in the kernel of the G-action onE. ReplacingMif necessary by this kernel we may assume from now on that MG. Sincek≥2, M is not transitive on the arcs of Kn, and so M is not 2-transitive. By Lemma3.1the groupGis 2-homogeneous onV, and hence by Theorem2.5, eitherGis affine orGis almost simple and 2-transitive. In either caseG has a unique minimal normal subgroupT, and so we must haveT ≤M. In particular T is not 2-transitive.
In the almost simple case, as discussed above, the simple normal subgroupT ofG is 2-transitive, except whenG=Ree(3)on 28 points andT =G∼=PSL(2,8). Thus in this caseG, M, nare as in Definition3.3. Also as the group PSL(2,8)has three
non-trivial orbitals, each self-paired, and permuted transitively byG, it follows from Lemma2.8thatk=3,Eis as in Definition3.3, and eachiisM-arc-transitive. Thus the result is proved in this case.
We assume from now on thatGis affine, soG=T G0 withT =ZRp,G0≤ L(a, q), where n=qa=pR, and V is identified with ana-dimensional vector space V (a, q)over Fq. Since T ≤MG, we have M=T M0 and M0 G0. As discussed in Subsection2.2, each i =Cay(T , Si)for some M0-invariant sub- setSi⊂T withSi= −Si. By assumptioni isM-edge-transitive and so, by Lem- nma2.9, there is a non-trivialM-orbitalOi such that Si =Oi(0)if i is M-arc- transitive, orSi =Oi(0)∪Oi∗(0)withOi =O∗i ifi is notM-arc-transitive. In the latter caseOi∗(0)= −Oi(0), and in either caseEi=E(Oi)andi=(Oi). Now the transformationφ∈GL(a, q)fixes 0 and interchangesOi(0)and−Oi(0)=Oi∗(0).
HenceφfixesE(Oi)for eachiand alsoφcentralisesG. Thus the groupG, φis 2-transitive onV and leavesEinvariant, and its subgroupM, φis normal and fixes each Ei setwise. Replacing G, M by these groups we may therefore assume that φ∈M0. This implies thatM0is transitive onSi for eachiand hence, by Lemma2.1, eachi isM-arc-transitive andGis 2-transitive. Also each of theOi (1≤i≤k) is self-paired and these are all of the non-trivialM-orbitals, soE=E(M).
In the light of Proposition3.4, we assume from now on thatG is an affine 2- transitive permutation group onV that contains the mapφ:v−→ −v(for v∈V).
Our broad strategy is to consider each of the possibilities forG, as given in Theo- rem2.5(2), examine each of its normal subgroupsMthat is not 2-homogeneous and containsφ, and determine the structure of theM-arc-transitive factors. Thus in the remainder of the paper we assume thatV =V (a, q)where|V| =qa=pR withp prime, andG, Msatisfy the following condition.
Condition 3.5 G=T G0, M=T M0withT =ZRp, M0G0≤L(a, q) andφ∈M0.
Also M has k non-trivial orbitals O1, . . . ,Ok, each self-paired, and such that Ei =E(Oi), andi =(Oi)=Cay(V , Si)withSi=Oi(0), fori=1, . . . , k. Note that we identify the vertex setV withT, and without loss of generality we will as- sume that 1∈S1. Thus(Kn,E)=(KpR,E(M)), whereE(M)= {E(O1), . . . E(Ok)}
as in Definition3.2, and this is a(G, M)-homogeneous factorisation if and only if Gacts transitively on {O1, . . . ,Ok}(with the action described in Lemma2.7), or equivalentlyG0acts transitively on{S1, . . . , Sk}.
4 The one-dimensional affine case
This is case (a) of Theorem2.5(2). The groupGis as in Condition3.5witha=1.
In this case we identifyV with the finite field Fq of orderq =pR. We introduce generators forL(1, q)as follows. Chooseω to be a primitive element ofFq and denote byωthe corresponding scalar multiplicationx−→xω(forx∈V). Also let αdenote the Frobenius automorphism ofFq, that is,α:x−→xp. Thenωgenerates the multiplicative group GL(1, q),L(1, pR)= ω, αand AL(1, q)=Tω, α.
Although it is necessary to distinguish elements of GL(1, q)from elements ofV, it is helpful to have similar notation for certain subsets ofV. Fori≥1 andi|(q−1), we shall useωito denote the subset{1, ωi, ω2i, . . . , ω((q−1)/ i)−i}of V. Also, for 1,−1∈Fq, we will use1 and−1 to denote the corresponding scalar multiplications in GL(1, q).
4.1 Generalised Paley graphs and cyclotomic factorisations
First we give a family of examples generalising the homogeneous factorisation con- sisting of the edge sets of a Paley graph and its complement.
Definition 4.1 (Generalised Paley graph and cyclotomic partition) Letk be a di- visor of q −1 such that k ≥2 and either q or q−k1 is even. Then the graph GPaley(q,q−k1)=Cay(V ,ωk)is called a generalised Paley graph onV. The corre- sponding cyclotomic partition ofKqis the partition Cyc(q, k)= {E1, . . . , Ek}where Ei= {{u, v} |v−u∈ωi−1ωk}for 1≤i≤k.
Note that the conditions on k imply that ωk = −ωk and so the graph GPaley(q,q−k1) is well defined as an undirected Cayley graph. If k = 2 then GPaley(q,q−21)is the Paley graph which is arc-transitive and self-complementary, with automorphism groupT ω2, α(see for example [27]). In Proposition4.2we prove that(Kq,Cyc(q, k))is a homogeneous factorisation, called a cyclotomic fac- torisation. These factorisations are closely related to cyclotomic association schemes, see for example [5, Section 2.10A].
Proposition 4.2 Letkbe a divisor ofq−1 such thatk≥2 and eitherq or q−k1 is even. LetG=T ωandM=T ωk.
(1) Then GPaley(q,q−k1)is an undirected,M-arc-transitive graph of valency q−k1. (2) The pair(Kq,Cyc(q, k))is a(G, M)-homogeneous arc-transitive factorisation
of indexk, and each factor is isomorphic to GPaley(q,q−k1).
Proof Part 1. The ‘connecting set’ωkis an orbit forM0= ωkof size q−k1, and hence is equal toO(0)for a non-trivialM-orbitalO. As discussed aboveO(0)=
−O(0)and so, by Lemma2.9, GPaley(q,q−k1)isM-arc-transitive of valency q−k1. Part 2. The group M is transitive on V and the sets Si :=ωi−1ωk, where 1≤i≤k, are theM0-orbits inV\ {0}. Sinceωk = − ωk, it follows that, for each i, Si = −Si and hence Si =Oi(0) for some self-paired non-trivialM-orbital Oi. Then by Lemmas2.8and2.9,Ei=E(Oi), and(Oi)=(V , Ei)isM-arc-transitive for eachi. Moreover Cyc(q, k)is a partition ofEKq, so(Kq,Cyc(q, k))is a factori- sation. Finally, sinceω∈G0mapsSi toSi+1for i=1, . . . , k−1, andSk toS1, it follows from Lemma2.4, and the fact thatMG, thatGpermutes the non-trivial M-orbitals transitively. Hence Cyc(q, k)isG-invariant,(Kq,Cyc(q, k))is(G, M)- homogeneous, andGinduces isomorphisms between thek factors(Oi)so all are M-arc-transitive and isomorphic to(O1)=GPaley(q,q−k1).
Finally in this subsection we characterise the examples arising from any affine 2-transitive groupG(not only the one-dimensional groups) in the case whereM0is contained in the scalar subgroup ofL(a, q).
Lemma 4.3 Let (Kqa,E) be an (G, M)-homogeneous arc transitive factorisation withG, M as in Condition3.5, and suppose thatφ∈M0≤Z(GL(a, q)). ThenE= Cyc(qa, k)and we may replaceGby a 2-transitive one-dimensional affine group so that Theorem1.1(2)(a) holds.
Proof NowM0≤Z(GL(a, q))≤GL(1, qa). Temporarily identifyV withFqa, let ω be a primitive element of Fqa, and use the notation introduced above. Then M0= ωk<ω =GL(1, qa), wherekdividesqa−1 and sinceφ∈M0, eitherqor
qa−1
k is even. Moreover theM0orbits inV \ {0}are the setsSi = −Si =ωi−1ωk, for i=1, . . . , k. Hence E is the cyclotomic partition Cyc(qa, k). IfH =T ω thenMH ≤AL(1, qa), and as in the proof of Proposition4.2,(Kqa,E)is an (H, M)-homogeneous arc-transitive factorisation. Replacing GbyH we have that
Theorem1.1(2)(a) holds.
4.2 Standard parameters for one-dimensional affine groups
Foulser [10] gives a standard generating set for each subgroup ofL(1, q)= ω, α that facilitates the checking of various important properties of the subgroups.
Lemma 4.4 [10, Lemma 4.1] LetH≤L(1, pR)= ω, α. Then there exist unique integersd,eandssuch thatH= ωd,ωeαs, and the following all hold:
(1) d >0 andd|(pR−1);
(2) s >0 ands|R;
(3) 0≤e < dande(pR−1)/(ps−1)≡0(mod d).
Definition 4.5 (Standard Form) IfH = ωd,ωeαs ≤L(1, pR)and the integers d, e ands satisfy conditions (1)-(3) of Lemma 4.4, then the representation H = ωd,ωeαsis said to be in standard form with standard parameters(d, e, s).
Remark 4.6 In subsequent results (for example, see Lemmas4.7-4.10), we will al- ways work with subgroups ofL(1, pR)given in standard form. To emphasise this we give an example: ifp=3 thenH = ω3, αis not expressed in standard form since condition (1) of Lemma 4.4 fails. The standard form for this subgroup is H= ω, α and by Lemma4.4, we know that this expression in standard form is unique.
First we give necessary and sufficient conditions on the standard parameters of a subgroup for it to be transitive onV∗:=V \ {0}. This criteria may be found in [11, Section 3]. We provide a proof as we need the details later for determining the possibilities forM0.
Lemma 4.7 (Transitivity) Suppose G0= ωd,ωeαs ≤L(1, pR) is in standard form. ThenG0 is transitive on V∗ if and only if either d=1 (soe=0), or both of the following hold:
1. e >0,ddividese((pds−1)/(ps−1)), and
2. if 1< d< d, thend does not dividee((pds−1)/(ps−1)).
Proof The set of orbits ofH := ωd inV∗ is:= {ωd, ωωd, . . . , ωd−1ωd}, andτ:=ωeαs induces a permutation of. Moreover,G0is transitive onV∗if and only ifτis transitive on. (To determine the image ofωiωdunderτ, we simply need to find the “coset” ofωdcontaining(ωi)τ.)
Ife=0 thenτ=αs, and since(ωd)αs =ωdps ∈ ωd, it follows thatτ acts triv- ially on. Thus in this caseG0is transitive onV∗if and only ifd=1. From now on suppose thate=0. Then we have:
τis transitive on⇐⇒(1)τdfixesωd, and
(2) if 1≤d< d, thenτd does not fixωd
⇐⇒(1)ωeps((pds−1)/(ps−1))∈ ωd, and
(2) if 1≤d< d, thenωeps((pds−1)/(ps−1))∈ / ωd
⇐⇒(1)d divideseps((pds−1)/(ps−1)), and (2) if 1≤d< d, thenddoes not divideeps
pds−1 ps−1
. Sinced|(pR−1)by Definition4.5, it follows that gcd(p, d)=1. So
τis transitive on⇐⇒(1)ddividese((pds−1)/(ps−1)), and (2) if 1≤d< d, thend does not dividee
pds−1 ps−1
.
We need to study normal subgroupsM0in standard form of a givenG0in standard form. Our next tasks are to give criteria for containment of one subgroup in another, and for normality.
Lemma 4.8 (Containment) SupposeM0= ωd1,ωe1αs1andG0= ωd,ωe, αare subgroups ofL(1, pR)expressed in standard form. ThenM0is a subgroup ofG0if and only if
(1) d|d1, (2) s|s1,
(3) andd|(e(p(pss1−−1)1)−e1).
Proof SupposeM0≤G0. Thenωd1 andωe1αs1 are elements ofG0. LetB= ω. ThenG0∩B= ωdcontainsM0∩B= ωd1, so|ωd1|divides|ωd|and hence
d|d1. Also, we haveM0/(M0∩B)∼=M0B/BG0B/B∼=G0/(G0∩B). Since M0/(M0∩B)= ωd1ωe1αs1 ∼=ZR/s1 andG0/(G0∩B)= ωdωeαs ∼=ZR/s, it follows thats|s1.
Given thatsdividess1(as shown above), we have(ωeαs)s1/s∈G0. Now by [11, Lemma 2.1], for eachi≥1,(ωeαs)i=ωJαsiwhereJ ≡e(psi−1)/(ps−1)(mod pR−1), and hence
(ωeαs)s1/s=ωJαs1, whereJ=e(ps1−1)/(ps−1). Writing
(ωeαs)s1/s=ωJαs1=ωJω−e1ωe1αs1,
and since(ωeαs)s1/s,ωe1αs1∈G0, we see thatωJ−e1 ∈G0and this is true if and only ifd|(J−e1).
Conversely, suppose the three conditions of the lemma are satisfied. Then since d|d1, there exists an integer j such that(ωd)j =ωd1. Thusωd1 ∈G0. Nows|s1
andd |(e(p(pss1−−1)1) −e1). As above, by [11, Lemma 2.1], we get (ωeαs)s1/s ∈G0. However, we know that
(ωeαs)s1/s=ωJαs1=ωJ−e1ωe1αs1∈G0,
whereJ−e1=(e(p(pss1−−1)1) −e1). Sinced|(J−e1), we haveωJ−e1∈G0, forcing
ωe1αs1 to be inG0.
Lemma 4.9 (Normality) SupposeM0= ωd1,ωe1αs1is in standard form and is a subgroup ofG0= ωd,ωeαs (so the conditions of Lemma 4.8hold). Then M0 is normal inG0if and only if
(1) d1|d(ps1−1)and
(2) d1|(e1(ps−1)+eps(pR−s1−1)).
Proof NowM0is normal inG0if and only if(ωd1)g∈M0and(ωe1αs1)g∈M0for allg∈G0. Since ωd1G0 wheneverM0= ωd1,ωe1αs1 is a subgroup ofG0, it follows that M0 is normal in G0 if and only if (ωe1αs1)g∈M0 for allg∈G0. Furthermore, sinceG0= ωd,ωeαs, we have thatM0is normal inG0if and only if (ωe1αs1)ωd ∈M0and(ωe1αs1)ωeαs ∈M0. Now
(ωe1αs1)ωd =ω−dωe1αs1ωd=ωe1−dαs1ωd=ωe1αs1ωd−dps1. Thus
(ωe1αs1)ωd ∈M0⇐⇒ωd−dps1 ∈M0
⇐⇒ωd−dps1 ∈M0∩ ω = ωd1
⇐⇒d1|d(ps1−1).
