Partition Graphs for Finite Symmetric Groups Marston Conder,1 Margaret Morton,1 and Cheryl E. Praeger2 1 DEPARTMENT OF MATHEMATICS UNIVERSITY OF AUCKLAND PRIVATE BAG 92109 AUCKLAND, NEW ZEALAND 2 DEPARTMENT OF MATHEMATICS UNIVERSITY OF WESTERN AUSTRALIA PERTH WA 6907, AUSTRALIA E-mail: morton@math.auckland.ac.nz conder@math.auckland.ac.nz praeger@maths.uwa.edu.au Received February 26, 1996 Abstract: This paper outlines an investigation of a class of arc-transitive graphs admitting a f inite symmetric group Sn acting primitively on vertices, with vertex-stabilizer isomorphic to the wreath product Sm wr Sr (preserving a partition of {1, 2, . . . , n} into r parts of equal size m). Several properties of these graphs are considered, including their correspondence with r О r matrices with constant row- and column-sums equal to m, their girth, and the local action of the vertex-stabilizer. Also, it is shown that the only instance where Sn acts transitively on 2-arcs c 1997 John Wiley & Sons, Inc. J Graph Theory 25: 107?117, 1997 occurs in the case m = r = 2. Keywords: graphs, symmetric groups 1. INTRODUCTION In this paper we begin an investigation of a class of arc-transitive graphs admitting a finite symmetric group Sn acting primitively on vertices. We have n = mr with 1 < r < n, and, for c 1997 John Wiley & Sons, Inc. CCC 0364-9024/97/020107-11 108 JOURNAL OF GRAPH THEORY each graph ? in this class the vertex set V (?) may be identified with the collection of partitions of a set ?n = {1, 2, . . . , n} of size n having r parts of size m. This class of graphs arose in the problem of classifying distance-transitive graphs with automorphism group a finite alternating or symmetric group [3]. Very few such graphs are distance-transitive, and of course distancetransitivity was the only property of interest in [3]. Here we study several basic properties of these graphs, namely: their girth, the action of the stabilizer of a vertex x on the vertices adjacent to x, and the action of the automorphism group Sn on the set of 2-arcs (simple paths of length two). We call these graphs the partition graphs G(m, r). In Section 3 we give a formal definition of them. Ivanov [3] showed that they can be indexed by classes of certain r О r integer matrices. Many, but not all, of the partition graphs have girth three. In Section 4 we give various sufficient conditions for them to have girth three, and give an example of a small class in which the girth is greater than three. For most but not all partition graphs, only the identity element of Sn stabilizes a vertex and each of its neighbours. We classify (Theorem 5.2) all partition graphs for which this is not the case: they all have m = 2. This result is then used in Section 6 (Theorem 6.1) to show that the only partition graph on which Sn acts 2-arc transitively is a 3-cycle C3 , and for this graph m = r = 2, and S4 acts unfaithfully. 2. PRELIMINARIES A method for constructing a symmetric graph from a group G with subgroup H and element a ? G \ H satisfying a2 ? H is described in [4]. Define such a graph ? = ?(G, H, a) as follows: let V be the set of right cosets of H in G, and let E be the set of all pairs {Hg1 , Hg2 } of cosets with the property that g1 g2?1 ? HaH. Then ? is a regular graph, and G induces a group of automorphisms of ? by right multiplication. In particular, this action of G is transitive on vertices and on arcs (ordered edges) of ?, and the subgroup H is the stabilizer in G of the vertex H. In this paper we consider the case where G is the symmetric group Sn , for composite n, say n = mr with 1 < m, r < n, and H is the wreath product Sn wr Sr . The latter consists of all permutations in Sn which preserve a partition of n of type mr (that is a partition with r r (of r copies of Sm ), with parts of size m), and is an extension by Sr of the direct product Sm r order (m!) r!. For a transitive permutation group G on a set ?, there is a natural action of G on ? О ? given by (?, ?)g = (?g , ? g ) for ?, ? ? ? and g ? G, and a G-orbit in ? О ? is called an orbital of G. The set ?0 = {(?, ?)|? ? ?} is an orbital, called the trivial orbital, and all other orbitals are said to be nontrivial. For an orbital ? its paired orbital ?? is defined as ?? = {(?, ?)|(?, ?) ? ?}, and ? is said to be self-paired if ? = ?? . The orbital graph for a nontrivial self-paired orbital ? is the graph with vertex set ? and edge set {{?, ?}|(?, ?) ? ?}. 3. THE CLASS OF PARTITION GRAPHS In our consideration of some of the properties of the symmetric graphs with G = Sn and H = Sm wr Sr , we follow an approach due to Ivanov [3]. In our case he notes that if Sn acts naturally on ?n = {1, 2, . . . , n}, where n = mr, then for the resulting graph ? the vertices can be viewed as the set R of all partitions of ?n into r subsets each of size m, and the edges can be characterised by a matrix of order r whose row and column sums are all equal to m. PARTITION GRAPHS 109 Let x = {x1 |x2 | и и и |xr } and y = {y1 |y2 | и и и |yr } be any two partitions in R with |xi | = |yi | = m, for 1 ? i ? r. The orbital digraph ? which contains the arc (x, y) is determined by the matrix M = (aij )rОr where aij = |xi ? yj |, 1 ? i, j ? r. Note that the ith row of this matrix describes the number of elements which the ith part of x has in common with each of the parts of y. Conversely, a matrix M of order r with nonnegative integer entries corresponds in this way to an orbital digraph ?(M ) if and only if the column and row sums of M are all equal to m. For example, the matrix ? ? 3 0 1 ?0 2 2? 1 2 1 corresponds to the orbital digraph containing the arc (x, y) where x is the partition {1, 2, 3, 4|5, 6, 7, 8|9, 10, 11, 12} and y is the image of x under the permutation a = (4, 10) (7, 11, 8, 12). Moreover, as shown in [3], ?(M ) = ?(M 0 ) if and only if M 0 can be obtained from M by means of permutations of rows and columns. Clearly the relation defined by M ? M 0 whenever ?(M ) = ?(M 0 ) is an equivalence relation on this class of matrices, and M (or any matrix M 0 in the equivalence class [M ] of M ) will subsequently be referred to as a matrix associated with its corresponding digraph ?(M ). Definition. For m, r > 1, let M(m, r) be the set of all square matrices of order r, excluding those of the form mIr , with nonnegative integer entries and with constant row- and column-sums equal to m. Definition. Two matrices in M(m, r) are said to be equivalent if one is obtainable from the other by row and column permutations. Let [M(m, r)] denote the set of equivalence classes of matrices in M(m, r), so that the number of pairwise inequivalent matrices in M(m, r) is |[M(m, r)]|. Observe also that if M is a matrix associated with the digraph ?, then its transpose M T is a matrix associated with the paired orbital digraph ?? . In particular for M to define a graph (rather than a digraph) we require ? = ?? , that is, M T must be equivalent to M . In either case, occasionally we will use M(x,y) to denote the specific matrix representing the arc from vertex x = {x1 |x2 | и и и |xr } to vertex y = {y1 |y2 | и и и |yr }, namely the matrix with (i, j)th entry equal to |xi ? yj |. Note that M(x,y) depends on the ordering chosen for the parts of x and y, and for different orderings we will obtain the other matrices in [M(x,y) ]. Each graph corresponding to a matrix in M(m, r) has vertices v1 , . . . , vk , where k = |Smr |/|Sm wr Sr |. Let G(m, r) = {?(M )|M ? M(m, r)}. Note that this set consists of one graph for each equivalence class of matrices in M(m, r), since ?(M ) = ?(M 0 ) whenever M ? M 0 . Also if ?1 and ?2 are distinct graphs in G(m, r), then the intersection of their edge sets must be empty. In particular a graph ? in G(m, r) is a complete graph if and only if |[M(m, r)]| = 1, and we can easily determine the values of m and r for which this is the case: Lemma 3.1. The only values of m and r for which G(m, r) contains a complete graph are (m, r) = (2, 2) and (3, 2), and representative matrices in these cases are (11 11 ) and (21 12 ) respectively. 110 JOURNAL OF GRAPH THEORY Proof. Clearly |[M(2, 2)]| = |[M(3, 2)]| = 1. For r = 2 and m > 3 the matrices (m?1 1 2 and (m?2 2 m?2 ) are inequivalent in M(m, 2) so |[M(m, r)]| > 1. For r > 2 the matrices ? ? m?1 1 0 ? 1 m?1 0 ? 0 0 mIr?2 and 1 m?1 ) ? m?1 1 0 0 ? 0 m?1 1 0 ? ? ? ? 1 0 m?1 0 ? 0 0 0 mIr?3 ? are inequivalent in M(m, r), where the latter matrix is to be taken as a matrix of order 3 if r = 3, and so again |[M(m, r)]| > 1. Note that the cases (m, r) = (2, 2) and (m, r) = (3, 2) correspond to the complete graphs K3 and K10 (with automorphism groups S3 and S10 ) respectively. Next, write (M1 ; . . . ; Ms ) for a block matrix of the form ? ? 0 M1 ? ? .. ? ?, . 0 Ms where Mi is a matrix of order ri , and r1 + и и и + rs = r. In each class in [M(m, r)] there M0 exists at least one such block matrix in which each Mi is not decomposable as ( 0 i M0 00 ). Such i a matrix will be called a completely decomposed matrix representative of the class. The matrices M1 , M2 , . . . , Ms will be called the indecomposable blocks of this matrix. Without loss of generality we may assume r1 ? ri+1 for i = 1, . . . , s ? 1. Also if this is the matrix M(x,y) then there is a partition of ?n with s parts of sizes mri (for 1 ? i ? s), the parts 1 1 i i being Bmr1 = ?rj=1 xj = ?rj=1 yj and Bmri = ?rj=1 xr1 +иии+ri?1 +j = ?rj=1 yr1 +иии+ri?1 +j for 2 ? i ? s. Moreover, for each i, Mi is a matrix associated with a graph in G(m, ri ) for the symmetric group Smri acting naturally on Bmri . 4. GIRTH INVESTIGATION In this section we consider the problem of determining the girth of the graphs in G(m, r)?that is, the length of their shortest cycles. Many of the graphs in G(m, r) have girth three, and we are able to prove this for a large subset of these graphs. We denote the girth of a graph ? by girth(?). First we show that if we have a completely decomposed matrix representative of a graph ? in G(m, r), where the graphs associated with each indecomposable block all have girth three, then ? must have girth three. Note that all of the following results apply equally well to orbital digraphs, with respect to the existence of a directed cycle (x, y, z) of length three. Lemma 4.1. Let M = (M1 ; . . . ; Ms ) be a completely decomposed matrix representative of a graph ? in G(m, r). Suppose that for each i such that Mi has order greater than one, the graph ?(Mi ) has girth three. Then ? has girth three. PARTITION GRAPHS 111 Proof. For i = 1, . . . , s, let Mi have order ri , where 1 ? ri ? r, and a that r1 ? r2 ? и и и ? / I we have r1 ? 2. Now for each i with ri > 1, we can find vertices xi , yi rs . Since M = and zi in ?(Mi ) such that (xi , yi , zi ) is a 3-cycle, and if ri = 1 we have the degenerate smallest cycle (xi , yi , zi ) where xi = yi = zi . Then setting x = {x1 |x2 | и и и |xs }, y = {y1 |y2 | и и и |ys }, z = {z1 |z2 | и и и |zs }, we see (x, y, z) is a 3-cycle in ?, since each of the three arcs in this cycle corresponds to the matrix (M1 ; . . . ; Ms ) = M . In particular, ? = ?(M ) contains a 3-cycle and therefore has girth 3. Using a generalization of the proof in this Lemma it follows that if the graph ?(Mi ) has girth gi , then maxi gi ? girth(?) ? lcm(g1 , . . . , gs ), and that if each ?(Mi ) has a circuit of length g, then so does ?. This suggests that it will be instructive to consider the girth of graphs whose representative matrix consists of just one indecomposable block. In the particular case where M = (aij ) ? M(m, r) is an indecomposable matrix with 2 nonzero entries in each row and column, it turns out that girth(?)M )) = 3. Since the row and column sums are all equal to m, there are positive integers u and v such that u + v = m and the two nonzero entries in each row and column are u and v. Without loss of generality assume u ? v. Since M is indecomposable we may reorder the columns and rows so that ai,i = u and ai,i+1 = v (reading the subscripts modulo r), that is, M is a circulant matrix with u's on the main diagonal and, except for the last row where v is the first entry, there are v's in every position one entry to the right of the main diagonal. All other entries in M are 0. We denote such a circulant matrix of order r by Cr (1, u; 2, v). A permutation matrix of order n is a matrix of 0's and 1's with a single 1 in each row and column. The set of permutation matrices of order n forms a group under matrix multiplication which is isomorphic to Sn . In general, matrices M1 and M2 are equivalent by row and column permutations, if and only if there exist permutation matrices R and S such that M2 = RM1 S. In particular, any permutation matrix is equivalent by row and column permutations to the identity matrix of the same order. Let Ir be the identity matrix of order r and ? be a permutation on the columns of Ir : then P? denotes the permutation matrix formed from Ir by the action of ? on its columns. Lemma 4.2. Let ? be a graph in G(m, r) with associated matrix equivalent to the circulant matrix Cr (1, u; 2, v) where r > 2. Then the girth of ? is three. Proof. We treat the cases where r is odd and r is even separately. For r odd, let x, y and z be vertices in ? represented by the partitions x = {a1 , b1 |a2 , b2 | и и и |ar?3 , br?3 |ar?2 , br?2 |ar?1 , br?1 |ar , br }, y = {a1 , b2 |a2 , b3 |a3 , b4 |a4 , b5 | и и и |ar?3 , br?2 |ar?2 , br?1 |ar?1 , br |ar , b1 }, z = {a1 , b3 |a2 , b4 |a3 , b5 |a4 , b6 | и и и |ar?3 , br?1 |ar?2 , br |ar?1 , b1 |ar , b2 }, where ai , bi ? Bmr with |ai | = u and |bi | = v for 1 ? i ? r. Now M(x,y) = uIr + vP? where ? = (1, r, r ? 1, . . . , 3, 2), and also M(y,z) = uIr + vP? while M(z,x) = uIr + vP? where ? = (1, 3, 5, . . . , r, 2, 4, . . . , r ? 1). Since ? and ? are cycles of length r, they are mutually conjugate within Sr , and so the three matrices M(x,y) , M(y,z) and M(z,x) are all in the same equivalence class in M(m, r). Hence (x, y, z) is a cycle of length three in ?. The case for r even is similar. Let x, y be as in the case for r odd, and let z be the vertex in ? represented by the following partition, where a1 = p1 ? q1 with |p1 | = v and |q1 | = u ? v: z = {q1 , b1 , b2 |a2 , br |a3 , p1 |a4 , b3 |a5 , b4 | и и и |ar?2 , br?3 |ar?1 , br?2 |ar , br?1 }. 112 JOURNAL OF GRAPH THEORY Here M(x,y) = uIr + vP? where ? = (1, r, r ? 1, . . . , 3, 2), while M(y,z) = uIr + vP? where ? = (1, 3, 5, . . . , r ? 1, 2, 4, . . . , r), and M(z,x) = uIr + vP? where ? = (1, 2, r, r ? 1, . . . , 5, 4, 3). Since ?, ? and ? are cycles of length r, they are mutually conjugate within Sr , and thus (x, y, z) is a cycle of length three in ?. Corollary. If r ? 2 then every graph in G(2, r) has girth three. Proof. Apply Lemmas 4.1 and 4.2 when r > 2; the case r = 2 is trivial. Lemma 4.3. Let Jr be the matrix of order r with every entry equal to 1, suppose m = kr, and let ? be a graph in G(m, r) with associated matrix kJr . Then the girth of ? is three. Proof. Let x, y and z be the vertices given by x = {a11 , a12 , . . . , a1r |a21 , a22 , . . . , a2r | и и и |ar1 , ar2 , . . . , arr } y = {a11 , ar2 , ar?1,3 и и и |a21 , a12 , ar3 и и и | и и и |ar1 , ar?1,2 , ar?2,3 и и и} z = {a11 , a21 , . . . , ar1 |a12 , a22 , . . . , ar2 | и и и |a1r , a2r , . . . , arr } where aij ? Bmr with |aij | = k for 1 ? i, j ? r. Note that y is formed from x by moving each aij from part i to part i + j ? 1 mod r for all i, j, and consequently M(x,y) = M(y,x) = kJr . Similarly, as z is formed from x by moving aij from part i to part j for all i, j we have M(x,z) = M(z,x) = kJr . Finally, note that y is formed from z by moving each aij from part j to part j + 1 ? 1 mod r for all j, i, and hence M(z,y) = M(y,z) = kJr . Consequently (x, y, z) forms a 3-cycle in ?. Lemma 4.4. Let ?0 be a graph in G(m, r) with associated matrix M , and let ? be a graph in G(m + k, r) with associated matrix M + kJr , for some k > 0. Then if ?0 contains a (possibly degenerate) 3-cycle, then the girth of ? is three. Proof. Let (x0 , y 0 , z 0 ) be a 3-cycle in ?0 , possibly degenerate (in which case x0 = y 0 = z 0 ). Also let (x, y, z) be the 3-cycle constructed for the graph with matrix kJr in Lemma 4.3. Now define x0 + x to be the partition of (m + k)r whose ith part is the disjoint union of the ith parts of x0 and x, and define y 0 + y and z 0 + z similarly. Then (x0 + x, y 0 + y, z 0 + z) is a 3-cycle in ?. The concept of indecomposability gave us the possibility of making inductive arguments on the parameter r, and Lemma 4.4 allows some kind of reduction, this time in terms of m. Lemma 4.4 tells us that if ?(M ) is in G(m, r) where r > 2, and if k is the smallest entry of M , then girth(?(M ? kJr )) = 3 implies that girth (?(M )) = 3. Hence if we are trying to prove that ?(M ) has girth three, for some class of matrices M , then we may assume that at least one entry in the associated matrix M is zero (by subtracting the appropriate multiple of Jr if necessary). Furthermore we can now prove that all graphs in G(m, r) have girth three for the cases r = 2 and r = 3: Lemma 4.5. If ? = ?(M ) is a graph in G(m, 2), then the girth of ? is three. Proof. By replacing M by another member of [M ] if necessary, we may suppose that M = (ab ba ) where a ? b ? 0 and a + b = m. If a = b then M = aJ2 and so by Lemma 4.3 the girth of ? is three. Hence we may assume that a > b. Then M = (a ? b)I2 + bJ2 and since ?((a ? b)I2 ) contains a degenerate 3-cycle, it follows by Lemma 4.4 that ? contains a 3-cycle as required. Lemma 4.6. If ? is a graph in G(m, 3), then the girth of ? is three. PARTITION GRAPHS 113 Proof. Without loss of generality we may assume the associated matrix for ? is ? ? a b c+d M = ? b + d a + c 0 ?, c d a+b by Lemma 4.4. Also by interchanging rows 1 and 3, and/or interchanging columns 1 and 2 if necessary, we may suppose a = max{a, b, c, d}. Let x and y be vertices in ? represented by the partitions x = {a1 , b1 , c1 , d1 |a2 , b2 , c2 , d2 |a3 , b3 , c3 , d3 }, y = {a1 , b2 , c3 , d2 |a2 , b1 , c2 , d3 |a3 , b3 , c1 , d1 }, where ai , bi , ci , di ? B3m and |ai | = a, |bi | = b, |ci | = c, |di | = d, for 1 ? i ? 3. Let a2 = p2 ? q2 where |p2 | = b and |q2 | = a ? b, and a3 = r3 ? s3 where |r3 | = c and |s3 | = a ? c. Now let z be the vertex represented by the partition z = {a1 , p2 , r3 , d3 |b1 ? q2 , b2 , c2 , d1 |c1 ? s3 , b3 , c3 , d2 }. ? ? a b c+d Note that M(x,y) = M(y,z) = M(z,x) = ? b + d a + c 0 ? = M , hence (x, y, z) is a c d a+b 3-cycle in ?. Note. Investigation of the graphs in G(m, 4) indicates that many, but not all, have girth three. For example, the graph with associated matrix ? ? 2 6 1 0 ?6 3 0 0? ? ? (1) ?1 0 0 8? 0 0 8 1 has girth four. The verification of this is left as an exercise for the reader. 5. LOCAL ACTION Let G be the group Sn (where n = mr with m, r > 1), let H be the subgroup Sm wr Sr , and let a be an element of G such that a ? / H but a2 ? H. Form the graph ?(G, H, a) as described in Section 2. Recall that H is an imprimitive subgroup of Smr , with r blocks of size m, inducing a partition x of the set ?n = {1, 2, . . . , n} of type mr . Similarly each right coset Hg of H = Gx induces a partition of the same type (namely the partition obtained by applying g to x), and in this way the vertices of the graph ?(G, H, a) can be viewed as partitions of ?n into r subsets of size m. Also ?(G, H, a) is connected, since the fact that H is a maximal subgroup of G implies that G is generated by elements of HaH. In this section we study the action of H on the set ?(x) = {Hah|h ? H} of vertices adjacent to x in ?. We classify all graphs for which this action is unfaithful. In Section 6 we use this result to study the action of G on the 2-arcs of ?. Proposition 5.1. Let G be the symmetric group Smr (where 1 < m, r < n), and let H be Sm wr Sr . The minimal normal subgroups of H are precisely the following: 114 JOURNAL OF GRAPH THEORY (i) (ii) (iii) (iv) Arm , where Am is the alternating group of degree m, for m = 3 and m ? 5, V4r , where V4 is the Klein 4-group, for m = 4, Z(S2 wr Sr ), the trace subgroup, when m = 2, S2r ? A2r , the augmentation subgroup, when m = 2 and r is odd. r r Proof. First observe that Sm is a normal subgroup of H, and that Sm has trivial centralizer in H if m > 2, and is self-centralizing in the case m = 2. Now let N be a minimal normal subgroup r r of H. As N ? Sm is normal in H, and N is minimal normal in H, we find either N ? Sm =N r r r or N ? Sm is trivial. However if N intersects Sm trivially then N centralizes Sm , and we have a r contradiction. Thus N ? Sm . Next suppose {x1 |x2 | и и и |xr } is the partition of ?n of type mr preserved by H. Choose an element g ? N which acts non-trivially on a minimal number l of the parts xi . We may assume that g is nontrivial on x1 , . . . , xl , and fixes the remaining r ? l parts pointwise. Write g = g1 g2 и и и gl , where 1 = / gi ? Sym(xi ) for 1 ? i ? l. Suppose m = / 2. In this case, since Sym(x1 ) ? = Sm has trivial centre there exists h1 in Sym(x1 ) such that g1h1 = / g1 , and then 1 = / g1?1 g1h1 = g ?1 g h1 ? N , giving l = 1 by minimality. Moreover, g1?1 g1h1 is an even permutation, so the intersection N ? Alt(x1 ) is a non-trivial normal subgroup r r of Sm . If m = / 4, then Alt(x1 ) is a minimal normal subgroup of Sm , and hence Alt(x1 ) ? N . Conjugation within H shows also Alt(xi ) ? N , for 2 ? i ? r, and thus N = Arm . This is case (i). Now suppose m = 4. We showed above that l = 1, and N ? Alt(x1 ) = / {1}. Thus N ? Alt(x1 ) contains the unique minimal normal subgroup V4 (x1 ) of Alt(x1 ), and it follows that N = V4r . This is case (ii). Finally suppose m = 2, and let xi = {ai , bi } for 1 ? i ? r. If l = r, then g = (a1 , b1 )(a2 , b2 ) и и и (ar , br ), which generates the trace subgroup Z(S2 wr Sr ), of order 2. This is case (iii). On the other hand, if l < r, then we may choose i and j such that g induces (ai , bi ) on xi but the identity on xj , and then letting ? be the transposition (i, j) in Sr , we find g ? g = (ai , bi )(aj , bj ). Thus l ? 2. By 2-transitivity of Sr , the normal subgroup N contains all such double transpositions, and therefore N = S2r ? A2r , the augmentation subgroup of S2r . Note that this contains the trace subgroup when r is even, and so minimality of N requires that r is odd, as stated in case (iv). This completes the proof. Theorem 5.2. Let G be the symmetric group Smr (where 1 < m, r < n), let H = Sm wr Sr , and let a be any element of G\H such that a2 ? H. For any vertex x of the graph ? = ?(G, H, a), one of the following holds: (i) Gx acts faithfully on ?(x); (ii) m = 2, r ? 3, and the kernel of the action of Gx on ?(x) is Z(S2 wr Sr ) ? = Z2 ; (iii) m = r = 2, ? = C3 (a cycle of length three), and G acts unfaithfully on ? with kernel S22 ? = V4 . Moreover, in case (ii), if M is a completely decomposed representative matrix for ?, then each indecomposable block of M has size 1 or 2 (and conversely, for each of these graphs the kernel is Z2 ). Proof. Let K be the kernel of the action of Gx on ?(x). Also suppose the vertex x is represented by the partition {x1 |x2 и и и |xr } of ?n , where xi = {xi1 , xi2 , . . . , xim } for 1 ? i ? r. If K is trivial, we have case (i), so suppose K is non-trivial, and let N be a minimal normal subgroup of Gx contained in K. Then by Proposition 5.1 we know the possibilities for N . PARTITION GRAPHS 115 Suppose m > 2. Then N ? = Arm or V4r , and consequently N is transitive on each of the sets xi in the partition representing the vertex x. Moreover, N ? Sym(xi ) acts transitively on xi and / i. Let y = {y1 |y2 | и и и |yr } be any vertex in ?(x), so that fixes all the points of xj , for all j = / xj for all j, and there exist y is fixed by N . Then since x = / y, there exists i such that yi = / ? and yi ? xl = / ?. Now N ? Sym(xj ) is transitive on xj and distinct xj , xl such that yi ? xj = fixes xl pointwise. But also N is a subgroup of Gy , and so yi is a block of imprimivitivity for N . Thus N ? Sym(xj ) fixes yi setwise (since N ? Sym(xj ) fixes yi ? xl = / ?) and so xj ? yi (since N ? Sym(xj ) is transitive on xj , and yi ? xj = / ?), whence |yi | > |xj | = m which is a contradiction. Hence m = 2. A similar argument shows that in this case, the base group S2r acts nontrivially on ?(x), and it follows that N is either the trace or the augmentation subgroup of S2 wr Sr , and S2r is not contained in K. We now show that if r > 2, then the augmentation subgroup S2r ? A2r acts non-trivially on ?(x). Let y be any vertex of ? fixed by this subgroup, and suppose y corresponds to the partition {y1 | и и и |yr }. Without loss of generality, we may assume that y1 = {x11 , ?} is the set containing the point x11 . Consider g = (x11 , x12 )(x21 , x22 ), an element of the augmentation subgroup. By assumption g fixes y, so {x12 , ? g } is one of the yi . In particular g moves ?, and hence ? ? {x12 , x21 , x22 }. Similarly, the element (x11 , x12 )(x31 , x32 ) moves ?, and so ? ? {x12 , x31 , x32 }. Hence ? = x12 , and so y1 = {x11 , x12 } = x1 . Similarly we find that each set yi in the partition y is a part of x, showing y = x. Thus x is in fact the only vertex of ? fixed by the augmentation subgroup. Hence, if r > 2 then S2r ? A2r is not contained in K, and it follows from Proposition 5.1 that N is the trace subgroup Z(S2 wr Sr ). Also if m = r = 2, then by Proposition 5.1, N = Z(S2 wr Sr ). Hence in all cases N = Z(S2 wr Sr ). Now we determine K. Suppose that the kernel K contains some element g ? / N . Writing g = g1 g2 и и и gl ?, where gi ? Sym(Bi ) for 1 ? i ? l, and ? ? Sr , we may consider two separate possibilities, as follows: (a) If ? = 1, then since g ? / N , we must have gi = (xi1 , xi2 ) for some i while gj = 1 for some j = / i, and then the same argument used in the final part of the proof of Proposition 5.1 shows that K contains the augmentation subgroup if r > 2 and contains S22 if r = 2, contrary to / 1. what we found above. Thus if g = g1 g2 и и и gl ? ? K \ N then ? = (b) If ? = / 1, then ? moves i to j for some distinct i, j in {1, 2, . . . , r}, and taking h = (xj1 , xj2 ) we find K contains h?1 ghg ?1 = (xi1 , xi2 )(xj1 , xj2 ), again leading to a contradiction if r > 2. Hence either K = Z(S2 wr Sr ), which is case (ii), or otherwise m = r = 2. In the latter case, H = S2 wr S2 is dihedral of order 8 and of index 3 in G = S4 , so the graph ? is a triangle. The kernel of the action of G on ? is V4 giving (iii). Finally for case (ii), suppose ? = ?(M ) for some completely decomposed matrix M . Then K = hzi, where z = (x11 , x12 )(x21 , x22 ) и и и (xr1 , xr2 ). Now let y ? ?(x). We may assume that {x11 , x21 } is a part of y (since y = / x). Then {x11 , x21 }z = {x12 , x22 } is also a part of y z = y, and it follows that every indecomposable block of M has size 1 or 2. Conversely for each graph ? corresponding to such a matrix, clearly z lies in the kernel K of Gx on ?(x), further if K = / < z >, then K would contain S2r ? A2r which, as we showed above, is not the case. 6. TWO-ARC TRANSITIVITY Here we use Theorem 5.2 to answer the question: when does Smr act transitively on the set of 2-arcs of ?? A 2-arc of ? is a triple (v0 , v1 , v2 ) of vertices of ? such that v1 is adjacent to both 116 JOURNAL OF GRAPH THEORY v0 and v2 in ? and v0 = / v2 . A subgroup G in Aut(?) is said to be 2-arc-transitive on ? if G is transitive on the set of 2-arcs of ?. If G is 2-arc-transitive (and vertex-transitive) on ?, then it is easy to prove that Gx acts 2-transitively on ?(x). (Consider the set of 2-arcs with second vertex x.) We shall combine this fact with the information about Gx in Theorem 5.2 to show that Smr is 2-arc-transitive on ? if and only if m = r = 2. As preparation, recall that m and r are integers greater than 1. For such a pair (m, r), any prime p which divides mr ? 1 but not mi ? 1 for 1 ? i < r, is known as a Zsigmondy prime. By a theorem of Zsigmondy [2], such primes exist in all cases except when m = 2 and r = 6, or when m = 2k ? 1 (for some integer k) and r = 2. Note that if p is a Zsigmondy prime for the pair (m, r), then m has multiplicative order r modulo p, and so p ? 1 is divisible by r, giving p ? r + 1. This fact, and also Burnside's characterisation of 2-transitive groups (on p. 202 of [1]) will be used in our proof. Theorem 6.1. Let G be the symmetric group Smr (where 1 < m, r < n), let H = Sm wr Sr , and let a be any element of G \ H such that a2 ? H. Then G is 2-arc-transitive on ?(G, H, a) if and only if m = r = 2 and ? = C3 . Proof. Suppose ?(G, H, a) is 2-arc-transitive. Then the stabilizer of a vertex x acts 2transitively on the set ?(x) of neighbours of x. We now consider various possibilities in turn, as before: (a) If m = 3 or m ? 5, then by Theorem 5.2 we know Gr is faithful on ?(x), and is therefore itself a 2-transitive permutation group. Burnside's theorem, however, states that a 2-transitive group must be either almost simple or affine, and since Gx ? = Sm wr Sr we must have m = 3, |?(x)| = 3r , and Gx isomorphic to a subgroup of AGL(r, 3). Now S3 wr Sr = Z3r L, where as a subgroup of GL(r, 3), the group L may be taken as the group of all monomial matrices, and this group preserves the subset of Z3r consisting of vectors of weight one. Hence S3 wr Sr is not an affine 2-transitive group, and so m = 2 or 4. (b) If m = 4, then Gx has a unique minimal normal subgroup N ? = V4r , again by Proposition 5.1. Also by Theorem 5.2, Gx is faithful on ?(x), so Gx is itself a 2-transitive permutation group and therefore primitive on ?(x). In particular, N must be transitive and therefore regular on ?(x), so |?(x)| = |N | = 4r . Moreover, since Gx is 2-transitive on ?(x), its order must be divisible by 4r (4r ? 1). Now, there exists a Zsigmondy prime p for the pair (4, r), and necessarily p divides |Gx |, and p ? r + 1. On the other hand, |Gx | = |S4 wr Sr | = (4)!r r!, so no prime divisor of / 4, leaving the only possibility as m = 2. |Gx | exceeds r, a contradiction. Hence m = (c) If m = 2 and Gx if faithful on ?(x), then by the same argument as in the first part of the previous case, every non-trivial abelian normal subgroup of Gx is regular on ?(x). Applying this to the trace subgroup gives |?(x)| = 2, while applying it to the normal subgroup isomorphic to S2r gives |?(x)| = 2r , a contradiction. Hence Gx is not faithful on ?(x). (d) If m = 2 and r > 2, then the kernel of the action of Gx must be the trace subgroup T (of order 2). In this case Gx /T is faithful and 2-transitive on ?(x), and so S2 acts regularly on ?(x), with kernel T , whence |?(x)| = 2r?1 . It follows that the stabilizer Gxy of an arc (x, y) in ? is an extension of T by Sr . Note that T is the unique normal subgroup of Gxy of order 2, and since the kernel of the action of Gy on ?(y) must also be a normal subgroup of Gxy of order 2, it must then be equal to T . Since ? is connected it follows that T is a subgroup of Gu , for every vertex w in ?, whence T acts trivially on ?, a contradiction. This leaves only one possibility. (e) If m = 2 and r = 2, then ? is a triangle, and G is clearly 2-arc transitive on ?. This completes the proof. PARTITION GRAPHS 117 Note 1. Possibilities (c) to (e) may also be dealt with using the girth investigation in Section 4, however we have given the above group-theoretic arguments for consistency with the earlier cases. Note 2. If m = 2 then ? has girth three, by the Corollary to Lemmas 4.1 and 4.2. Accordingly, for ? to be 2-arc-transitive it must be complete; hence by Lemma 3.1 either m = r = 2, in which case ? = K3 and S4 acts 2-arc-transitively, or (m, r) = (3, 2), but in that case S6 has two orbits on 2-arcs. ACKNOWLEDGMENTS The first two authors are grateful to the N.Z. Marsden Fund and the Auckland University Research Committee for financial support. References [1] W. Burnside, Theory of groups of f inite order, Cambridge University Press London (1911). [2] W. Feit, On large Zsigmondy primes. Proc. Amer. Math. Soc. 102 (1988), 29?36. [3] A. A. Ivanov, Distance transitive representations of the symmetric groups. J. Combinatorial Theory Ser. B 41 (1986), 255?274. [4] R. C. Miller, The trivalent symmetric graphs of girth at most 6. J. Combinatorial Theory Ser. B 10 (1971), 163?182.

1/--страниц