close

Вход

Забыли?

вход по аккаунту

?

292

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
2
Размер файла
130 Кб
Теги
292
1/--страниц
Пожаловаться на содержимое документа