arXiv:1605.09173v1 [] 30 May 2016

HIGHEST RANK OF A POLYTOPE FOR An
PETER J. CAMERON, MARIA ELISA FERNANDES, DIMITRI LEEMANS,
AND MARK MIXER

Abstract. We prove that the highest rank of a string C-group constructed
from an alternating group An is 0 if n = 3, 4, 6, 7, 8; 3 if n = 5; 4 if n = 9; 5 if
n = 10; 6 if n = 11; and ⌊ n−1
⌋ if n ≥ 12. This solves a conjecture made by
2
the last three authors in 2012.

1. Introduction
Given a group G and a set of involutions S := {ρ0 , . . . , ρr−1 } which generate G,
such that
∀i, j with |i − j| > 1, ρi and ρj commute (the string property),
we call the pair (G, S) a string group generated by involutions (or sggi for short).
We denote by ΓI the group generated by {ρi : i ∈ I} for I ⊆ {0, . . . , r − 1}.
The pair (G, S) satisfies the intersection property if for every I, J ⊆ {0, . . . , r − 1},
ΓI ∩ ΓJ = ΓI∩J . A sggi Γ := (G, S) that satisfies the intersection property is called
a string C-group of rank |S|. If Γ := (G, S) is a string C-group, we sometimes
will abuse language and talk about the group Γ and denote the rank of G as the
largest size of a set S of involutions such that Γ := (G, S) is a string C-group. For
i ∈ {0, . . . , r − 1}, we denote by Γi the group generated by all the elements of S
except ρi .
It is known that string C-groups are automorphism groups of abstract regular
polytopes and that, given an abstract regular polytope and a base flag of the polytope, one can construct a string C-group whose group G is the automorphism group
of the polytope [26, Section 2E]. Hence the study of string C-groups has interests
not only in group theory, but also in geometry.
Classifications of string C-groups from almost simple groups started with experimental work of Leemans and Vauthier [25] (see also [18, 19, 21, 10] for more
experimental results) and quickly led to the determination of the rank of a string
C-group of Suzuki type [20]. A series of results then followed for the almost simple
groups with socle PSL(2, q) [22, 23, 9], groups PSL(3, q) and PGL(3, q) [4], groups
PSL(4, q) [3], small Ree groups [24] and finally, symmetric groups [11, 12] and alternating groups [13, 14]. In particular, only the last two families gave rise to string
C-groups of arbitrary large rank. It was proved in [7] that the maximal rank of a
string C-group for transitive subgroups of Sn that are neither An nor Sn is n2 + 1.
A symmetric group Sn is known to have rank n − 1 [11] and an alternating group
An with n ≥ 12 is known to have rank at least ⌊ n−1
2 ⌋ when n ≥ 12 [14]. It is
conjectured in [14] that this is the highest possible rank for a string C-group of
alternating type. In this paper, we prove this conjecture. Our main result is as
follows.
1

2

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Theorem 1.1. The rank of An is 0 if n = 3, 4, 6, 7, 8; 3 if n = 5; 4 if n = 9; 5 if
n = 10; 6 if n = 11 and ⌊ n−1
2 ⌋ if n ≥ 12.
The cases where n ≤ 11 had already been dealt with the use of Magma [13].
In this paper, we show that if Γ := (An , S) is a string C-group and n ≥ 12, then
|S| ≤ ⌊ n−1
2 ⌋. In some parts of this proof we use induction over n. The proof is
divided into three parts. In Sections 2 and 3, we deal with the case where some
subgroup Γi is primitive or transitive imprimitive, respectively, and our main tool
here is permutation group theory. In the remainder of the paper we have to deal
with the case where all Γi ’s are intransitive. Our main tool for this case is the use
of fracture graphs; but these are also used elsewhere, so we give a brief introduction
here.
Let Γ = hρ0 , . . . , ρr−1 i be an sggi acting as a permutation group on a set
{1, . . . , n}. We define the permutation representation graph G as the r-edge-labeled
multigraph with n vertices and with a single i-edge {a, b} whenever aρi = b with
a 6= b. Suppose we have a sggi Γ which is a transitive subgroup of the symmetric
group Sn , such that every subgroup Γi is intransitive. Then, for each i, the permutation ρi has a cycle whose points lie in different Γi -orbits. Choosing one such cycle
for each i, and regarding them as the edges of a graph on the vertex set {1, . . . , n},
we obtain a fracture graph for Γ. The fracture graph is of course not unique, and
indeed much of our proof involves showing how to replace a fracture graph by a
more convenient one.
If Γ is contained in the group of even permutations (as in our main theorem),
then each permutation ρi has at least two cycles. If it happens that for each i we
can find two pairs of points in different Γi -orbits, then taking an i-edge between
each of these pairs of points we obtain a 2-fracture graph. Section 4 handles the
case where a 2-fracture graph exists. Section 5 the case where it does not, and we
then use fracture graphs instead.
2. Γi is primitive for some i
Now we embark on the proof of the main theorem. In this section we prove the
theorem in the case where some Γi is primitive.
Given a string C-group Φ := (G, T ) with T := {ρ0 , . . . , ρd−1 }, the diagram of Φ
is a graph with d vertices and an edge between vertices i and j whenever ρi ρj is
not an involution. Moreover, the edge {i, j} is then labelled with the order of ρi ρj .
Observe that, by the string property, the diagram of Φ is a union of paths. We say
that a set S ⊆ T is connected provided the labels of the generators of S form an
interval.
Let us first state a Theorem due to Maróti that will be useful in the proof of the
next proposition and also later on.
Theorem 2.1 (Maróti [16]). Let G be a primitive group of degree n which is not
Sn or An . Then one of the following possibilities occurs:
l
(a) For some integers m, k, l, we have n = m
k , and G is a subgroup of Sm ≀ Sl ,
where Sm is acting on k-subsets of {1, . . . , m};
(b) G is M11 , M12 , M23 or M24 in its natural 4-transitive action;
⌊log 2 n⌋−1
Y
(n − 2i ).
(c) |G| ≤ n ·
i=0

HIGHEST RANK OF A POLYTOPE FOR An

3

Proposition 2.2. Let n ≥ 12. If Φ := (G, T ) is a string C-group of rank d with
G < An and G primitive, then d ≤ (n − 3)/2.
Indeed, in this case d is asymptotically much smaller than n/2.
Proof. We use the methods of [7].
Suppose first that the diagram of Φ is not connected. Then the primitive group
G is the direct product of two proper subgroups, each of which is necessarily simple
and acts regularly; so |G| = n2 , and n ≥ 60. But clearly |G| ≥ 2d ; so d ≤ 2 log2 n <
(n − 3)/2 for n ≥ 60.
So we may suppose that the diagram of Φ is connected. Now we combine Conder’s lower bound 22d−1 for the order of a string C-group of rank d [8] with wellknown upper bounds for the order of primitive groups, such as Maróti’s (see Theorem 2.1). We deal with the three cases of Maróti’s Theorem. Case (b) is handled
by computer. In case (a), since we are only interested in an upper bound for |G|,
we can assume that G is maximal in An , so that either G is Sm acting
 on k-sets, or
G = Sm ≀Sl with l > 1. In the first subcase, d ≤ m−1, while n = m
k ≥ m(m−1)/2,
for
n
≥
12.
In
the
second
subcase,
we
can
use
the
main result of [7]
hence d ≤ n−3
2

m l
ml
to conclude that, d ≤ 2 + 1 while n = k and n ≥ 12; again this gives d ≤ n−3
2 .
In these cases, G is embeddable in a smaller symmetric group, of degree m in the
first case, or ml in the second. Finally, in case (c), we have
22d−1 ≤ |G| ≤ n1+log2 n ,
If we assume d ≥

n−2
2 ,

we get
2n−3 ≤ 22d−1 ≤ |G| ≤ n1+log2 n ,

thus
n ≤ (log2 n)(log2 n + 1) + 3
which gives a contradiction for n ≥ 34.
For n ≤ 33, we give in Table 1 the list of primitive groups of degree n such that
n
their order is ≥ 22⌊ 2 ⌋−3 , following numbering of Sims’s list [5]. When Magma
is mentioned in the references column, it means we computed all string C-groups
representations of the corresponding group using Magma and the bound is sharp.
So d ≤ (n − 3)/2 in all cases.

We remark that Maróti’s bound uses the Classification of Finite Simple Groups.
The use of such heavy machinery could in principle be avoided by using the slightly
weaker bounds proved by ‘elementary’ means by Babai and Pyber [1, 17]; however,
this would require examining of many more ‘small’ cases, some of which are too
large for practical computation.
The previous proposition gives the following corollary that finishes a case for our
main theorem, when some Γi is primitive.
Corollary 2.3. Let n ≥ 12 and let Γ := (An , S) be a string C-group of rank r. If
Γi is primitive for some i then r ≤ n−1
2 .
Proof. If Γi is primitive for some i, then Γi < An and satisfies the hypotheses of

Proposition 2.2. Hence the rank r − 1 of Γi is bounded by n−3
2 .

4

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Degree Number
G
Max rank
12
1
P SL(2, 11)
4
2
P GL(2, 11)
3
3
M11
0
4
M12
4
13
7
P SL(3, 3)
0
14
2
P GL(2, 13)
3
15
3
A7
0
4
P SL(4, 2)
0
16
18
2 4 : S6
5
19
24 : A7
0
20
24 : P SL(4, 2)
0
17
8
P ΓL(2, 16)
0
22
2
M22 : 2
4
23
5
M23
0
24
3
M24
5
Table 1. Primitive groups G of degree ≤ 33 with

Reference
[25, 22]
[25, 23]
[25]
[25]
[25, 4]
[25, 23]
[25]
Magma
Magma
Magma
Magma
[25]
[25]
[19]
[19]
n
|G| ≥ 22⌊ 2 ⌋−3 .

3. Γi is transitive imprimitive for some i
In this section, we prove the main theorem in the case where Γi is transitive but
imprimitive for some i.
Let Γ ∼
= An with n ≥ 12 and Γi be transitive imprimitive for some i ∈ {0, . . . , r −
1}. Let k and m be such that Γi is embedded into Sk ≀ Sm . We assume that the
blocks of imprimitivity are maximal (so Γi acts primitively on the set of blocks),
but do not require that k is as big as possible.
Consider the following sets of generators of Γi :
• L an independent generating set for the block action;
• C the set of generators that commute with all elements of L;
• R the remaining generators.
Let us first recall some important results found in [7]. We have that |L| ≤ m−1 and
|C| ≤ k − 1. The group hLi is primitive on the set of blocks, and L has at most two
connected components. When L has two components, r − 1 ≤ 2 log2 m + (k − 1) + 4
and m ≥ 60, thus in that case we have r ≤ n2 − 1. So, in what follows, we assume
that L is connected and generates a primitive group on the set of blocks.
Proposition 3.1. If m 6= 2 then {ρi } ∪ L must be connected and |R| ≤ 1.
Proof. As Γ is primitive, ρi must break the imprimitivity of Γi , thus it must swap
at least one pair of points in different blocks. On the other hand hLi is primitive,
thus ρi cannot commute with every element of L. Hence {ρi }∪L must be connected
and |R| ≤ 1.

3.1. The case k, m > 2.
Proposition 3.2. If k > 2 and m > 2, then r ≤ ⌊(n − 1)/2⌋.
Proof. As observed at the beginning of the section, |L| ≤ m − 1, |C| ≤ k − 1. By
Proposition 3.1, |R| ≤ 1, hence r − 1 ≤ (m − 1) + (k − 1) + 1. When n = 12 the

HIGHEST RANK OF A POLYTOPE FOR An

5

bound that we get for the rank is 7, but using Magma [2] we found out that there
are no polytopes of ranks 6 or 7 for A12 . So we may assume that n > 12.
If r > ⌊(n − 1)/2⌋, then
km − 1
n−1
=
≤ r ≤ k + m,
2
2
so (k − 2)(m − 2) ≤ 5. The solutions with km > 12 are (k, m) = (3, 5), (3, 6), (3, 7),
(4, 4), (5, 3), (6, 3), (7, 3).
Now we consider these cases. If (k, m) = (3, 7) or (7, 3), then r ≤ 10 = (21−1)/2,
as required. If (k, m) = (3, 5), (3, 6), (4, 4), (5, 3) or (6, 3), then we have r ≤
⌊(n − 1)/2⌋ unless |L| = m − 1, |C| = k − 1, and |R| = 1. So hCi ∼
= Sk , and since
hCi commutes with a group acting primitively on the blocks, it acts in the same
way on each block.
We also see that hLi acts as Sm on the set of blocks, and since it commutes with
Sk fixing the blocks, we have hL, Ci ∼
= Sk × Sm . Transpositions in Sk (resp. Sm )
act as products of m (resp. k) transpositions on the point set. So if either m or k
is odd, then Γ contains an odd permutation, a contradiction.
Now suppose that (k, m) = (4, 4) and r = 8. We know that ρi commutes with
a subgroup S3 × S4 with orbits of sizes 4 and 12. We know from the previous
paragraph that S4 × S4 is acting on the product of two sets of size 4. So when we
descend to S3 × S4 , the orbit of size 4 has S4 acting in the usual action (and its
centraliser is trivial), while the orbit of size 12 is the product of sets of sizes 3 and 4.
A permutation which commutes with it must fix the two systems of imprimitivity, so
its projection onto each factor commutes with the corresponding symmetric group,
and so is trivial.

3.2. The case k = 2. The estimate above gives r ≤ m + 2 = n2 + 2. We have to
knock three off this bound. The group induced on the blocks is primitive. It follows
that the centraliser of hLi in the symmetric group is generated by the involution
z which interchanges the points of each block. Now if m is odd, then z is an odd
permutation, and so C = ∅. If m is even, then |C| ≤ 1, and if z ∈ hLi then the
intersection property forces C = ∅.
We separate the argument into three cases, according as the group H induced
on blocks is Sm , Am , or neither of these. The cases H = Sm and H = Am use
similar arguments, but differ in detail, so we have kept them separate.
Case H = Sm . We assume that m ≥ 7 for this proof.
Note first that |R ∪ C| ≤ 1. Indeed, if both R and C are nonempty, m is even,
and z is contained in hL ∪ Ri ∩ hCi, a contradiction. [This is because the kernel of
the action of Γi on blocks is an Sm -submodule of (C2 )m ; the only such submodules
are the trivial ones, the module M1 generated by z, and the module M2 consisting
of elements interchanging an even number of blocks; if m is even then M1 ≤ M2 ,
and there cannot exist two independent submodules.]
So r ≤ |L| + 2, and if either |L| ≤ m − 3 or R ∪ C = ∅ and |L| ≤ m − 2 then we
have the required result. Up to duality, there are the three possibilities, either
(A) ρi = ρ0 , L = {ρ1 , . . . , ρr−2 }, R = {ρr−1 } and C = ∅,
(B) ρi = ρr−2 , L = {ρ0 , . . . , ρr−3 }, C = {ρr−1 } and R = ∅, or
(C) ρi = ρ0 , L = {ρ0 , . . . , ρr−1 }, and R = C = ∅.

6

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Let G = hLi. Now G induces the symmetric group Sm on the set of blocks, and L
is an independent set of generators for G as a string group (not necessarily a string
C-group!). We have |L| ≤ m − 1.
Assume that |L| = m − 1 and m ≥ 7. The elements of L induce the Coxeter
generators on the set of blocks: for a certain numbering of the blocks, ρj swaps
blocks j and j + 1, for j ∈ {1, . . . , m − 1}. (This is an easy deduction from the
result of [6].) In (A) and (C), ρi commutes with ρ2 , . . . , ρm−1 , and these elements
generate a group acting as Sm−1 on blocks, fixing the first block. Since m ≥ 7, we
see that ρi must fix all the blocks numbered from 2 to m, and clearly also block 1;
so it preserves the block system. In (B) ρi commutes with ρ0 , . . . , ρm−3 , which also
acts as Sm−1 on blocks, and the same applies. So Γ preserves the block system, and
is imprimitive, a contradiction to the assumption that Γ is the alternating group.
So we can assume that |L| = m − 2 and R ∪ C 6= ∅.
Let K be the kernel of the action of Γi on the blocks, and let K1 = K ∩ G. Then
K and K1 are Sm -submodules of the permutation module F m , where F is the field
with two elements. The only submodules have dimensions 0, 1 (spanned by the
all-1 vector), m − 1 (the vectors of even weight), and m. Now since Γi consists of
even permutations, we cannot have K = F m .
We show that K = K1 is impossible. If K = K1 , then G = Γi , and so R ∪ C = ∅,
contrary to our assumption.
Next we show that K1 = 1 is impossible. In this case, L generates Sm as string
C-group. By the main result of [11, 12], there is a unique possibility, up to duality.
In (A) the group generated by ρ2 , . . . , ρr−2 is Sm−1 , and ρ0 commutes with this
group, so ρ0 preserves the block system, a contradiction. In (B) the group generated
by ρ0 , . . . , ρr−4 is Sm−1 , and ρi commutes with this group. We then get the same
contradiction as before.
So we are left with the case K = [(C2 )m ]+ and K1 = hzi. In this case G is an
extension of C2 by Sm and C = ∅ (as in case (A)).
The involutions z and ρ0 both commute with Γ0,1 , since z is in the centre of
Γ0 . So the dihedral group D they generate also commutes with Γ0,1 . Moreover,
ρ0 and z do not commute with each other; if they did, then Γ = hΓ0 , ρ0 i would be
contained in the centralizer of z, contradicting the fact that Γ is the alternating
group. So D has order 2d with d ≥ 3. We now separate in two cases.
In the case where Γ0,1 is transitive, the group D is semiregular; thus Γ0,1 has
m/d blocks of imprimitivity each of size 2d, and is contained in D ≀ Sm/d . Now
since d ≥ 3, we can replace the action of Γ0,1 by one where each orbit of D has size
d, rather than 2d; this action is still faithful (since D acts faithfully on d points if
d ≥ 3). So Γ0,1 is isomorphic to a transitive imprimitive group of degree m. By
the main result of [7], we have r − 2 ≤ m
2 + 1 (whence m ≤ 6, which is not so).
So suppose that Γ0,1 is intransitive on blocks; then also Γ0,1,r−1 is intransitive.
Let H1 be the group it induces on the blocks. Now the images of ρ2 , . . . , ρr−2 form
a set of r − 3 generators for H1 as an sggi (not necessarily a string C-group). If
r ≥ m, then we conclude that
• H1 has at most three orbits;
• if it has three orbits, then it acts on each as the symmetric group;
• if it has two orbits, then it acts on one of them as the symmetric group.
Suppose there are three orbits. Then H1 commutes with the group induced by D
(which has at least one orbit of size d ≥ 3), the three orbits must be isomorphic

HIGHEST RANK OF A POLYTOPE FOR An

7

and a D-orbit meets each in one point. But then H1 ≤ Sm/3 and the number of
independent generators for H1 is at most m/3 − 1. So we have m/3 − 1 ≥ m − 3,
which is impossible.
Suppose that H1 has two orbits O1 and O2 with the action of H1 on O1 being
that of the symmetric group S|O1 | . We have a dihedral group D commuting with
the symmetric group such that each D-orbit meets O1 in one point, as these intersections form a system of imprimitivity for D on O1 . Suppose that the action
on the other orbit is not faithful. Then there is a non-trivial subgroup fixing all
points in this orbit (and hence fixing all D-orbits) but non-trivially on O1 , and
so moving the intersections of D-orbits with O1 (since these have size 1, only the
trivial group fixes them all). As to the size, each D-orbit has one point in O1 and
d − 1 in O2 , so |O2 | is (d − 1)/2 times the degree, that is, (d − 1)m/d. Thus H1
has at most (d − 1)m/d − 1 independent generators. If our inequality holds, then
(d − 1)m/d − 1 ≥ m − 3, from which we get m ≤ 2d. But then the dihedral group
has at most two orbits, and Γ0,1 ≤ D ≀ C2 . A group of order 2m2 has largest independent set of size at most 2 log2 m + 1. This number cannot be m − 2 or greater
for m > 8; the remaining cases are resolved by a computer check.
Case H = Am . As before, let L be an independent set of generators for the action
of Γi on blocks, and let G = hLi. If G is intransitive, then its orbits form a
transversal for the blocks, and so G ∼
= Am . By the induction hypothesis, if m ≥ 12,
m+3
then |L| ≤ ⌊ m−1
⌋,
and
so
r
≤
⌊
2
2 ⌋ ≤ m − 1, since m ≥ 7. For m < 12, if
the bound fails, we have either m = 10 and |L| = 5, or m = 11 and |L| = 6; the
required bound is satisfied in either case.
So we may assume that G is transitive.
Let K be the kernel of the action of Γi on blocks, and K ′ = K ∩ G. Since
Γi /K and G/K ′ are both isomorphic to Am , we see that K 6= K ′ . Moreover,
Am cannot act transitively on 2m points, and so K ′ 6= 1. Since K and K ′ are
submodules of the Am -module (C2 )m , and neither is the whole of (C2 )m (which
contains odd permutations), we must have |K| = 2m−1 , |K ′ | = 2. The generator
of K ′ is the involution z which interchanges the points in each block. Since this
is an even permutation, m must be even. Moreover C = ∅. Thus up to duality
we may assume that i = 0. If R = ∅ then r ≤ m − 1, hence we now assume that
R = {ρr−1 }.
Now z is in the centre of Γ0 , and so commutes with Γ0,1 . The involution ρ0 also
commutes with Γ0,1 , and by the intersection property ρ0 6= z. Let D = hz, ρ0 i, a
dihedral group of order 2d, say. Now ρ0 and z do not commute: for, if they did,
then hρ0 , Γ0 i would be contained in the centraliser of z, whereas in fact this group
is A2m . In particular, d ≥ 3.
Suppose first that Γ0,1 is transitive. Then D, which commutes with a transitive
group, is semiregular; and Γ0,1 , which commutes with D, is isomorphic to a subgroup of D ≀ Sm/d . Since D acts faithfully on d points (as d ≥ 3), Γ0,1 is isomorphic
to a transitive imprimitive group on m points. By the main theorem of [7], we get
r−2≤ m
2 + 1, so m ≤ 6.
Now suppose that Γ0,1 is intransitive.
We know that hρ1 , . . . , ρr−2 i ∼
= C2 × Am , and {ρ1 , . . . , ρr−2 } are string C-group
generators. We claim that their images, ρ̄1 , . . . , ρ̄r−2 , in Γ0,r−1 /hzi ∼
= Am are
independent.

8

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Suppose not. Note that they generate Am as an sggi. If they fail to be independent, one of them can be expressed in terms of the others. Suppose that it is
ρ̄h . We cannot have 1 < h < r − 2, since then these elements would generate a
commuting product of two subgroups. We cannot have h = 1, since we are assuming that Γ0,1 is intransitive. And finally, we cannot have h = r − 2. For if
so, then CA2m (Am ) = hzi; but ρr−1 centralises hρ1 , . . . , ρr−3 i = Am , so ρr−1 = z,
contradicting the intersection property, since z ∈ hρ1 , . . . , ρr−2 i.
Now the images mod z of ρ2 , . . . , ρr−2 are independent, and generate an intransitive subgroup of Am . So r − 3 ≤ m − 3. If equality holds, then this group has
just two orbits; it acts on each orbit as the symmetric group. But this contradicts
the fact that these elements belong to Γ0,1 , which centralises the dihedral group
D = hρ0 , zi having at least one orbit of size greater than 2 on the set of blocks.
Case H 6= Sm , Am . In this case we prove the following result on independent sets.
Proposition 3.3. Let G be a primitive group of degree n ≥ 8, not isomorphic to
An or Sn . Then the maximum size of an independent generating set of G is at
most n − 4.
Proof. Let M (G) be the maximum size of an independent generating set of G.
We consider separately the three possibilities given by Theorem 2.1.
l
l
In case (a) when l ≥ 2 we have n − 4 = (m
k ) − 4 ≥ m − 4 ≥ ml − 2 ≥ M (G).
When l = 1 we have k ≥ 2, m ≤ n/2 and the group is a subgroup of Sm or Am , so
M (G) ≤ m − 1, much smaller than n − 4.
In case (b) we have to consider the groups M11 , M12 , M23 or M24 . The maximal
length of a chain of subgroups of M11 , M23 or M24 is 7, 11 and 14 resp. (see [27]).
If G is isomorphic to M12 then M (G) ≤ 9 by [27]. Suppose that M (G) = 9. Then
one of the following subgroups H of M12 , namely M11 or P ΓL(2, 9), has to have
M (H) = 8. As M (M11 ) ≤ 7 (see [27]), we must have M (P ΓL(2, 9)) = 8. A quick
look at the subgroup lattice of M12 shows that this is impossible as two subgroups
of order 1440 never intersect in a subgroup of orderh720. Hence M (M12 ) ≤
i 8.
Q⌊log2 n−1⌋
i
(n − 2 ) that is
In case (c) the chain length is bounded by log2 n. i=0
at most n − 4 for n ≥ 26. We also know that if |G| = pe11 . . . pekk then the chain
length (and hence M (G)) is bounded by e1 + . . .+ ek . Combining these two bounds,
and using Magma, we conclude the result holds for n > 9 and for n = 8 we are
left with P ΓL1 (8), P SL2 (7), P GL2 (7) and ASL3 (2). But for those, looking at the
subgroup lattice we get M (G) ≤ 4.


3.3. The case m = 2. Suppose that m = 2, so that Γi ≤ Sk ≀ S2 . An involution
interchanging the blocks is fixed-point-free so k is even and n = 0 mod 4.
We separate the argument into two cases, according as there is or is not a value
of j 6= i such that Γi,j is transitive. First, suppose that such a j exists.
Proposition 3.4. If Γi,j is transitive for some j 6= i and Γi is transitive imprimitive embedded into Sn/2 ≀ S2 , then r ≤ n−1
2 .
Proof. Suppose r > n−1
and Γi,j is transitive for j 6= i. Then the two groups Γi
2
and Γj are transitive, so each has two blocks of size n/2. The stabilisers of the
blocks for the two subgroups each have index 2, so their intersection is a normal
subgroup of index 4 in Γi,j . The two block systems cannot be the same, since then
they would be preserved by hΓi , Γj i = Γ. These intersections are blocks for Γi,j , of
size n/4 = l, say, and the action on the blocks (which is not primitive in this case)

HIGHEST RANK OF A POLYTOPE FOR An

9

is isomorphic to the Klein group C2 × C2 generated, modulo the normal subgroup,
by a set L of size 2.
Now we play the usual game: let C be the set of generators commuting with L
(so C acts in the same way on each block, and has rank at most l − 1), and R the
remaining generators of Γi,j , so |R| ≤ 4.
Thus, r − 2 = |R| + |C| + |L| ≤ l + 5. As r > n−1
2 , l + 7 ≥ 2l, so l ≤ 7, and
n ≤ 28. Since n is a multiple of 4, we only need to consider the cases n = 16, 20,
24 and 28.
To deal with the exceptions, we first subdivide into two cases, according as the
permutations of L commute. Let L = {ρs , ρr }.
Suppose first that ρs and ρr do not commute. Then they are adjacent in the
diagram; so we can improve our estimate to |R| ≤ 2. Also, there is a vertex v such
that, if we follow a path with labels r, s, r, s, we arrive at a different point w in
the same block. Then the stabilizer of v in hCi also fixes w. So hCi is not the
symmetric group, and we have |C| ≤ l − 2. Then we have r − 2 ≤ l + 2, so n ≤ 16.
Now suppose that ρs and ρr commute. If |R| = 4, or if |R| = 3 and the diagram
of C is connected, then at least one element of R, say ρh , also commutes with
C. If hCi acts primitively on a block, then the centralizer of hCi is generated by
ρr and ρs , and so ρh ∈ hρr , ρs i, a contradiction. So we conclude that either C is
disconnected (giving |C| ≤ l − 2), or hCi is imprimitive (giving |C| ≤ l/2 + 1) or
|R| ≤ 2. Putting these into our estimates shows that n ≤ 24.
If n = 24, in the worst case scenario, we have |R| = 4, |C| = 4 and |L| = 2
possibly giving r = 12. If there are two permutations ρa and ρb such that Γi,j,a,b is
transitive, then it may be assumed that Γa and Γb are both embedded into Sn/2 ≀S2 .
This forces n to be divisible by 16, a contradiction. If |R| ≥ 2 then hCi is intransitive
within the blocks, otherwise another two generators can be removed from Γi,j and
the group remains transitive. Let hCi be intransitive within the blocks. If |C| = 4
then one element of R fuses the orbits of hCi inside a block, hence |R| ≤ 2, by the
same reason. Thus the case |C| = |R| = 4 leads to a contradiction.
We eliminate the case n = 20 as follows. For n = 20, we must have either
|C| = |R| = 3, or |C| = 4, |R| = 2. In the first case, the diagram of C is
disconnected, so we must have C ∼
= S3 × S2 , with orbit lengths 3 and 2. Take
an element of R which commutes with one component of the diagram of C, and
modify it using ρi and ρj so that it fixes all the blocks; this element commutes with
S2 × S3 , but this group contains its centraliser in S5 , a contradiction. In the second
case, hCi = S5 . Then hC, ρj i ∼
= S5 × S2 fixes the blocks of imprimitivity for Γi .
But this group is maximal in the stabiliser of this block system. There can be at
most one more generator in Γi , giving |R| ≤ 1, a contradiction.
For n = 16, we used the computer to show the nonexistence of such a group. 
In what follows we consider that Γi,j is intransitive for every j 6= i. We prove
that r ≤ n−1
2 using a certain fracture graph and we use the following results that
are immediate consequences of the definition of a fracture graph of a given sggi G
with permutation representation graph G. By an alternating square, in G, we mean
a square having opposed edges with the same label.
• ([15], Proposition 3.2 ) if two edges of G, e and e′ , have the same label and e
is an edge of a fracture graph, then at least one vertex of e′ is in a different
component of that fracture graph;

10

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

• ([15], Proposition 3.6) when two edges of an alternating square of G, belong
to a fracture graph of G, the vertex of the square not in these edges is in
another component of that fracture graph.
When representing G, dashed edges are used to represent edges that are in G but
not in the chosen fracture graph.
Proposition 3.5. If Γi,j is intransitive for every j 6= i and Γi is transitive imprimitive embedded into Sn/2 ≀ S2 , then r ≤ n−1
2 .
Proof. Let L = {ρl }. Suppose that R = ∅. In this case Γi ≤ 2 × Sn/2 and therefore
we could see ΓI as an imprimitive group with blocks of size two which we dealt
with before. Hence r ≤ n−1
2 .
We may now assume that R is nonempty.
First observe that if ρj ∈ R then ρj connects at least two pairs of hρl i-orbits.
Indeed as ρj is an even permutation and ρj does not commute with ρl , there must
be an even number (different from zero) of pairs of hρl i-orbits joined by a single
ρj -edge.
Suppose ρl−1 ∈ R. Consider the graph L whose vertices are the hρl i-orbits and
with a j-edge for each element of C ∪R connecting hρl i-orbits in different Γi,j -orbits.
Note that L is a fracture graph for the group action on the hρl i-orbits of Γi . Since
Γi,j is intransitive for every j 6= i, we have that L has no cycles. Then ρl−1 must
connect at least two pairs of hρl i-orbits, as observed before. Let us denote two
of them by (L1 , L′1 ), and (L2 , L′2 ). We have that |{L1 , L′1 , L2 , L′2 }| ≥ 3. Suppose
that {L1 , L′1 } is the (l − 1)-edge of L. Then either L2 or L′2 is another connected
component of L, different from the component of L1 . Let L1 and L2 be in different
connected components of L. Therefore |C ∪ R| ≤ n/2 − 2. Suppose we have the
equality. Then L has exactly two connected components, and either |C| = n/2 − 3
and |R| = 1, or |C| = n/2 − 4 and R = 2.
Let |C| = n/2 − 3 and R = {ρl−1 }. We claim that the incident edges of L have
consecutive labels. Suppose the contrary. Let g and h be non-consecutive labels of
incident edges of L. Consider first g, h 6= l − 1. Then there exists an alternating
square, with labels g and h, whose vertices are hρl i-orbits. Three vertices of the
square belong to one connected component of L and the fourth belongs to another
component of L. Let us denote this fourth vertex by L.
h

✤
g

✤g
❴ ❴L
h

Hence it may be assumed that L and L2 are in the same connected component of
L.
h
L′2 /o /o o/ /o /o /o
✤
✤
✤g
g
l−1 ✤
✤
❴ ❴L
L2 /o /o /o o/ /o /o
h

There are paths in L from the two ends of the g-edge to L2 and L′2 . But then
these two vertices are in the same Γg -orbit, a contradiction. Now suppose there
is an h-edge with h 6= l − 2 incident to an (l − 1)-edge. These two edges are on
an alternating square. Let h be minimal with this property. As k > 4, there is a

HIGHEST RANK OF A POLYTOPE FOR An

11

vertex incident to that square. Now the label of the edge connecting that vertex
to the square must be h + 1. Hence there is also an alternating square adjacent to
the first one, with labels h + 1 and l − 1. These two squares give three different
connected components of L, a contradiction. Thus two incident edges in L must
be consecutive. This gives a unique possibility for the permutation representation
graph of Γi .



l





l



l+1

l+1
l



l+2
l



l+3
l



l+4
l


l+2


l+3


l+4









Now there are two possibilities for i, namely either i = 0 or i = r−1. But as ρi must
break the block system, the only possibility is i = r − 1 and ρi a single transposition
connecting the two bottom vertices of the picture below, a contradiction.
Let |C| = n/2 − 4 and R = {ρl−1 , ρl+1 }. As observed at the beginning of the
proof of this proposition, ρl+1 connects at least two pairs of hρl i-orbits. If it does
not connect L2 to L′2 , then L has three connected components, a contradiction.
Hence assume both ρl−1 and ρl+1 connect L2 to L′2 . As k ≥ 3 there exists another
hρl i-orbit L that is adjacent to either L2 or L′2 . Let ρh ∈ R ∪ C be a permutation
connecting L and L2 . If ρh ∈ C then, as it commutes with at least one of ρl−1 and
ρl+1 , there is an alternating square in the permutation representation graph of Γ
with labels h and one of l − 1 and l + 1. This implies that ρh also connects two pairs
of hρl i-orbits different from (L2 , L′2 ). Hence |C ∪ R| ≤ n/2 − 3, a contradiction.
Thus ρh ∈ R. We may assume that h = l − 1. If a (l + 1)-edge is incident to a
(l − 1)-edge then there exists an alternating square and we get a contradiction as
before. Hence there exists a double edge with labels l + 1 and l − 1 and no other
incidence between edges with these labels. Also if incident edges have labels in C,
then the labels must be consecutive. Moreover Γi has the following permutation

12

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

representation graph.


l



l−1 l+1



l


l−1



l





l





l





l



l+1

l+2

l+2

l+3

l+3



Now there are two possibilities for i, namely either i = 0 or i = r − 1. In each case
either ρi is an odd permutation or ρi fixes the blocks, a contradiction.

4. All Γi ’s intransitive: 2-fracture graphs exist
In this section and the next, we handle the case where all subgroups Γi are
intransitive. As explained in the introduction, we use the techniques of fracture
graphs. In this section we deal with the case where 2-fracture graphs exist. In fact,
for later use, our results are more general: we do not assume that Γ ∼
= An until the
end of the section.
Let G be a permutation representation graph on n vertices for Γ, which is connected (meaning that this permutation representation of Γ is transitive). From now
on, we assume that Γ is indeed the permutation group defined by G.
Suppose that Γ has no transitive maximal parabolic subgroup Γi . We make the
further assumption that each ρi interchanges at least two pairs of points which lie
in different Γi -orbits for all i. Then G has a subgraph with n vertices and 2r edges
corresponding to two pairs of vertices in different Γi -orbits. We call this graph a
2-fracture graph.
For ease of notation, we denote by qi,j an alternating square with labels i and j,
and call a cycle with more than four vertices a big cycle.
We give some basic results that follow immediately from the definition of a 2fracture graph.
Proposition 4.1. If e = {v, w} is an i-edge of a 2-fracture graph Q of Γ, then any
path from v to w in G which does not contain e must contain another i-edge.
Proposition 4.2. A cycle in a 2-fracture graph has either zero or two i-edges. In
particular, a 2-fracture graph has no multiple edges.
Proposition 4.3. If one i-edge is in the intersection of a pair of cycles of a 2fracture graph, then both i-edges are in the intersection of those cycles. In particular, an edge of a square of a 2-fracture graph cannot be common to any other
cycle.
Proof. If only one i-edge is common to two cycles of a 2-fracture graph, then there
is a cycle with only one i-edge, which is not possible by Proposition 4.2.


HIGHEST RANK OF A POLYTOPE FOR An

13

Proposition 4.4. A big cycle of a 2-fracture graph has adjacent edges with nonconsecutive labels.
Proof. Let i be the smallest edge label in a big cycle. By Proposition 4.2 there are
two i-edges in that cycle. These i-edges must be adjacent to at least three further
edges. The only edges in the cycle with labels consecutive with i have label (i + 1)
(by minimality of i), and there are at most two of these; so the cycle has adjacent
edges with nonconsecutive labels.

In the following two propositions we show two useful ways of getting a 2-fracture
graph from another. In the first one an i-edge of a 2-fracture graph that is in a
cycle is replaced by another i-edge in the same cycle. In the second proposition,
one i-edge of a cycle is in a 2-fracture graph and the other i-edge in that cycle is
replaced by the i-edge not in the cycle in the 2-fracture graph.
Proposition 4.5. If there is a cycle C in G containing exactly two i-edges e1 , e2 ,
such that e1 is in a 2-fracture graph Q and e2 is not, then there is another 2-fracture
graph Q′ obtained by removing e1 and adding e2 .
Proof. The graph Q′ is a 2-fracture graph, because the edge e2 is between vertices
in different Γi -orbits.

Proposition 4.6. If there is a cycle C in G containing exactly two i-edges e1 , e2 ,
such that e1 is in a 2-fracture graph Q and e2 is not, then there is another 2-fracture
graph Q′ obtained by removing the i-edge of Q which is not e1 and adding e2 .
Proof. The proof is the same as that of the previous Proposition.



Both of the above Propositions will be of particular use when the cycle C is an
alternating square.
Proposition 4.7. Let qi,j be an alternating square with a vertex v l-adjacent to a
vertex w in a 2-fracture graph Q. If l is not consecutive with i, then the square can
be moved to include the edge {v, w}. That is, there is another 2-fracture graph Q′
obtained from Q by changing exactly two edges, as pictured below. Furthermore Q′
does not have more alternating squares than Q.
j



'&%$
!"#
w
✤
✤i
i
✤
❴ ❴ ❴

i



l

'&%$
!"#
v

j

−→

l

✤
✤i
✤


j

'&%$
!"#
v

l

'&%$
!"#
w

i
j



i



l

Proof. Let l be not consecutive with i. There is an alternating square in G, sharing
an i-edge with qi,j . We apply Proposition 4.5 to the other i-edge of qi,j , and
Proposition 4.6 for the l-edges.

Proposition 4.8. If a 2-fracture graph Q contains the subgraph on the left of the
following figure, then there is a 2-fracture graph Q′ containing the subgraph on the
right, such that Q and Q′ differ only in four edges.

i+1



i−1



i+1
i−1



❃

l

i



−→
❃
l

i

❃

❃




i−1

❃
❃❃
❃❃i
i+1
i+1
❃❃
❃
❴ ❴ ❴❴ ❴ ❴

i−1



l

i

l

14

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Proof. This is a consequence of applying Proposition 4.5 twice.



Proposition 4.9. If Γ has a 2-fracture graph, then it has one with no big cycle.
Proof. Consider a 2-fracture graph Q with q big cycles. Suppose that C is a big
cycle of Q. By Proposition 4.4 there is at least one pair of adjacent edges with
nonconsecutive labels i and j. Hence these edges belong to an alternating square
qi,j of G. The other two edges of this square are not edges of Q. Indeed the
remaining i and j edges of Q must belong to C by Proposition 4.2. Consider the
2-fracture graph Q′ that is obtained from Q by applying Proposition 4.5 twice,
replacing the i-edge and the j-edge of C which are not in qi,j by those that are not
in C but are in qi,j . By Proposition 4.3 the edges of the square cannot belong to
another cycle, thus Q′ has q − 1 big cycles. Continuing this process we obtain a
2-fracture graph without big cycles.

Proposition 4.10. If G has a 2-fracture graph, then it has a 2-fracture graph
such that each connected component has at most one cycle, and any cycle is an
alternating square.
Proof. By Proposition 4.9, G contains a 2-fracture graph Q0 having no big cycle.
If Q0 has a cycle, then it is an alternating square by Proposition 4.2. Suppose that
a connected component of Q0 has p alternating squares with p > 1. We will prove
that there exists a 2-fracture graph with p − 1 squares and without any big cycle.
The proof is a double induction. Suppose that qi,j and ql,k are squares of Q0
that have distance s which is the smallest distance between two squares in Q0 .
We produce another 2-fracture graph with either one fewer square, or the minimal
distance s reduced by 1.
Either the squares qi,j and ql,k share a vertex, or there is a path in Q0 connecting
them.
Suppose that they share a vertex. Then there exists another alternating square
in G. We may assume that it is qi,k , which shares an edge with both qi,j and ql,k .


j



j

i

❴ ❴k ❴✤
✤i
i
✤
 k 
l

l



k



By Proposition 4.5, we can replace one of the i-edges of Q0 with the i-edge of qi,k
not in Q0 to obtain a 2-fracture graph Q1 . Note that this new i-edge of Q1 does
not belong to any cycle by Proposition 4.3. Thus Q1 has p − 1 squares.
Now assume that the shortest path between qi,j and qk,l has s ≥ 1 edges. If the
first or the last edge of this path has a label not consecutive with the square that
it meets, then we can use Proposition 4.7, to create a new 2-fracture graph which
does not have more squares, and with a smaller minimal distance between squares.


j

i



j

❴ ❴x ❴✤
✤i
i
✤


x



k

l




l

k



−→

✤❴ ❴j ❴
✤i
i
✤


j

x


i

x





k

l




l

k



HIGHEST RANK OF A POLYTOPE FOR An

15

Otherwise, we can use Proposition 4.8 in order to create a new 2-fracture graph
with the first or the last edge of a new path having a label not consecutive with
the square that it meets, and then use Proposition 4.7 as before.
Continuing this process, we get a 2-fracture graph where the minimal distance
between squares is zero, and then applying the argument above, we get a 2-fracture
graph with fewer squares, and without big cycles. This construction terminates
with a 2-fracture graph with no big cycles and with at most one square in each
connected component.

Proposition 4.11. Suppose that Γ has a disconnected 2-fracture graph Q with no
big cycles such that every connected component has exactly one square. Then Γ has
a 2-fracture graph Q′ with the same characteristics as Q and such that the minimal
distance between two squares in G is either one, two or three accordantly to one of
the following three cases.
(1) 

i



l

❴ ❴x ❴

l


j

j



i

k



(3)
i+1



(2)

i+1

k

i−1







i−1

i−1



i+1
i−1





i

j+1



i

❴ ❴x ❴

j

l

k



i+1





❴ ❴x ❴
j−1


k

l





j+1



j−1



Proof. As Q contains all vertices of G, any component of Q is at distance one
from another component of Q. Consider two components in Q at distance one.
Repeatedly using Propositions 4.7 and 4.8, we can obtain a 2-fracture graph that
contains one of the above subgraphs.

4.1. Disconnected 2-fracture graphs. We now separate the argument into two
cases, dealing first with the case of a disconnected 2-fracture graph.
Proposition 4.12. If G has no connected 2-fracture graph, then it has a 2-fracture
graph that has at least one component which is a tree, all the others having only
one cycle (which is an alternating square).
Proof. Suppose that Q is a disconnected 2-fracture graph of Γ. By Proposition 4.10
there exists a 2-fracture graph Q of Γ having at most one cycle, that is an alternating
square, in each connected component. We proceed by induction on the number of
connected components of Q.
Suppose that Q has p connected components, each with an alternating square.
By Proposition 4.11, we can choose Q so that it has a subgraph as shown in one
of the three cases of Proposition 4.11. In what follows we deal with each of these
cases separately.
Let us consider that G has the subgraph (1) of Proposition 4.11. Observe here
that x is not consecutive with at least one of the labels of the squares. In addition
since the squares of Q are in different connected components of Q, the x-edge in
not in Q. Suppose x and l are nonconsecutive. Then we have an alternating square
as in the following picture on the left. Using Proposition 4.5 we obtain Q′ on the
right.

16

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER



i



i



l

❴

l



j

j

❃❴

❃
l

❃

−→



i



i

j

k

k

❴x




j

x

❃


❴ ❴l ❴


k

k

❃❴ ❴x ❴
❃❃
❃❃
❃
l ❃❃


l


x

If the other x-edge is not in Q, then we created a connected component which is a
tree. On the other hand, if the other x-edge is in Q, then the new 2-fracture graph
has p − 1 connected components.
Let us consider the second case of Proposition 4.11. First suppose that x is not
consecutive either with l or k. Without loss of generality we assume that it is not
consecutive with l; then we use Proposition 4.5 as shown in the following diagram.

i+1

i−1







❃❴ ❴x ❴
❃
❃
l
❃


i+1



i−1

l

−→



l


i+1

k

k
i





i−1

❴ ❴l ❴



i+1

k



i−1

k

❃❴ ❴x ❴
❃❃
❃❃
❃
l ❃❃


i

x



l
x

The argument for why this exchange does not create any new cycles is the same
as the previous case. Similar to above, if neither of the x-edges is in Q, then we
created a connected component which is a tree. On the other hand, if one of the
x-edges is in Q, then the new 2-fracture graph has p − 1 connected components.
Next, consider that x is consecutive with both l and k, then we have the following
diagram.


i−1





i+1

i+1

✸

✸i−1
✸
x ✸

l

❃i

x

❴ ❴x ❴
❃

❃
♣

✸ ♣
♣ i−1

i

l

−→

❴i−1
❴ ❴
i+1

k

k

❃




✸



i+1

✸i−1
✸
x ✸

l
k

k

❃

❃i

x

❴ ❴x ❴
❃

❃

♣
♣
✸ ♣♣♣
♣
 i−1



l



i

Note that x is not consecutive with i, and not consecutive with either i − 1 or
i + 1. Without loss we assume it is not consecutive with i − 1. Suppose that both
x-edges of the square qx,i−1 are in Q. Then using Proposition 4.5, we create a
square qx,i−1 in Q′ . Now if both i-edges are in Q we have reduced the number of
connected components; otherwise, we go back to case (1). Similarly, if an x-edge of
qx,i−1 is not in Q, then we either created a 2-fracture graph with p − 1 components
or with a component that is a tree.
Finally, we consider the diagram below for case (3). Here, x is not consecutive
with either i or j. We may assume it is not consecutive with i. Furthermore, x is
not consecutive either with i − 1 or i + 1. Let us assume it is not consecutive with
i − 1. A similar argument shows that the new graph either has p − 1 components
or a component that is a tree.

HIGHEST RANK OF A POLYTOPE FOR An



i−1

i+1

✸





i−1
✸
x

✸

✸

❃

❃i

x

❴ ❴x ❴
❃

❃

✸ qq
q
 i−1

j



❴i−1
❴ ❴

−→

j+1

j+1

i+1

j−1



j−1

17

✸

i

i−1
✸
x

✸

✸

❃

❃i

x

❴ ❴x ❴
❃

❃

✸ qqqq
q
 i−1

j

j−1



j+1

j+1

i+1

i+1






j−1



i

After any of the exchanges seen above, we have a 2-fracture graph with no big
cycle, and either p − 1 connected components or a component which is a tree.
Therefore, by induction, there exists a 2-fracture graph that is either connected or
disconnected with at least one component being a tree.

4.2. Connected 2-fracture graphs. In this subsection we will assume that Γ has
a connected 2-fracture graph.
Proposition 4.13. Let qi,j be an alternating square of a connected 2-fracture graph
Q of Γ. Let qi,l be an alternating square in G sharing an i-edge with qi,j . Then
neither or both the l-edges of qi,l are in Q.
Proof. Suppose that exactly one l-edge of qi,l is in Q. Let u be the vertex of qi,l
which is adjacent to qi,j in G by the l edge of qi,l which is not in Q.


j

i



j



l

✤
✤
i
✤i
❴ ❴ ❴ '&%$
!"#
u
l

Any possibility to connect u to qi,j gives a contradiction to Proposition 4.1.



Proposition 4.14. Let qi,j be an alternating square of a connected 2-fracture graph
Q. All edges of G meeting the vertices of qi,j belong to Q and have labels consecutive
either with i or j.
Proof. Let w be a vertex of qi,j k-adjacent (in G) to a vertex v. Suppose that {v, w}
is not in Q.
'&%$
!"#
v✤
✤
k ✤
 j '&%$
!"# l ✤
w
✤
i
i
✤i

❴ ❴ ❴ '&%$
!"#
u
j

l

There exists a path in Q from v to w. Let l be the label of the edge of this path
meeting qi,j . Suppose that there is a square qi,l or qj,l sharing an edge with qi,j .
Suppose first that qi,l contains w. Let u be the vertex of ql,i diagonally opposed to
w. One of the l-edges of ql,i is not in Q, because both are in the path from w to v.
By Proposition 4.13, we have a contradiction. Similar arguments rule out the case
where qi,l shares the other i-edge with qi,j . Thus |i − j| = 2 and l is consecutive
with both i and j. But then k is not consecutive either with i or with j. Suppose
without loss of generality it is not consecutive with j, thus we have a square qj,k

18

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

sharing an edge with qi,j . Let {v ′ , w′ } be the other k-edge of qi,k , with v ′ not in
qi,j .
j
/.-,
()*+
!"#
v✤
v✤ ′ ❴ ❴ ❴ '&%$
✤
✤
k
k ✤
✤
j
0123
7654
'&%$
!"#
′
w
w
i

l



i



j



By Proposition 4.13, {v ′ , w′ } is not in Q. Thus there is a path in Q, connecting w′
to v ′ , and this path does not have any l-edges. Let l′ be the label of the edge of this
path meeting w′ . As l′ is not consecutive with both i and j we have a contradiction
as before. Thus {v, w} is in Q.
Furthermore, as all edges of G adjacent to qi,j are in Q, k must be consecutive
to either i or j. Otherwise, we would have at least four edges with the same label
in Q.

Proposition 4.15. If qi,j is an alternating square of a connected 2-fracture graph
Q with n ≥ 9 vertices, then each vertex of qi,j has degree at most three in Q.
Proof. Suppose that qi,j has a vertex adjacent, in Q, to two other edges, and let k
and l be the labels of those edges. By Proposition 4.14 k and l must be consecutive
with one of the labels of qi,j . We may assume that i < j and l < k. Then there are
three possibilities either i < l < k < j, l < i < j < k or i < l < j < k corresponding
to the following graphs.
❴ ❴i ❴
k

k



i

j



l

j



i



l

✤
✤j
✤


❴ ❴i ❴ '&%$
!"# ❴ ❴l ❴ '&%$
!"#
w
v✤
✤k
k
k
✤
 i  l ✤
✤j
j
j
✤



i

l

❴ ❴i ❴❴ ❴l ❴✤
✤k
k
k
✤
i
l



j

j



i



Consider the second case. As Q is connected, there is a path in Q between v and
w. Then by Proposition 4.5, we can create a cycle in a 2-fracture graph having only
one edge with some label, contradicting Proposition 4.2.
The third case becomes the same as the first case by using Proposition 4.5 on
the i-edges.
Now we consider the first case. If the labels are not all consecutive, then another
pair of labels give an alternating square and we get the same contradiction as in
the second case. Suppose the labels are consecutive, then we use the fact that
there is another vertex of Q connected to one of the vertices of one of the graphs
above. Again using Propositions 4.5 and 4.14, independent of how this other vertex
is connected, we can obtain the same contradiction as in the second case.

Proposition 4.16. Let n ≥ 9. If Γ has a 2-fracture graph with a square, then it
has a 2-fracture graph having a square qi,j such that |i − j| = 2.
Proof. Choose Q, i, and j so that the alternating square qi,j has the property that
|i − j| is minimal.

HIGHEST RANK OF A POLYTOPE FOR An

19

First suppose that |i − j| ≥ 3. By Proposition 4.14 there is a vertex of the square
qi,j which is k1 -adjacent to another vertex with k1 ∈ {i−1, i+1, j−1, j+1}. Without
loss of generality, we can assume k1 = i ± 1, and thus there is an alternating square
qk1 ,j sharing an edge with qi,j . By Proposition 4.5, there is another connected 2fracture graph Q′ with qk1 ,j as its alternating square. Since we assumed that |i − j|
is minimal we know that |k1 − j| > |i − j|. Consider the vertices vi , i ∈ {0, . . . , 6}
as in the following figure.
()*+
/.-,
v1

i

k1

/.-,
()*+
v3

j

j

()*+
/.-,
v2

/.-,
()*+
v4

i

k1

/.-,
()*+
v✤5
✤j
✤
/.-,
()*+
v6

By Proposition 4.15 the degree of the vertices v3 and v4 is three. Suppose that v1
has degree three, then the label k of the edge incident to v1 , not in qi,j , would satisfy
|k − j| < |i − j|. As above, using Proposition 4.5, we would obtain a contradiction.
Thus the degree of v1 is two, and similarly the degree of v2 is two.
As n ≥ 9 the degree of either v5 or v6 is three. Assume without loss of generality
that v5 is k2 -adjacent to a vertex v7 . We have that k2 must be consecutive with
k1 ; furthermore, there is an alternating square qk2 ,j with vertices v5 , v6 , v7 , v8 , and
thus |k2 − j| > |k1 − j| > |i − j|. Continuing this process we get a sequence of
labels k3 , . . . , ks with |ks − j| > . . . > |k1 − j| > |i − j|. Thus Q does not have
edges with labels between i and j. We can then conclude that Γ is not connected,
a contradiction. Hence |i − j| ≤ 2.
Suppose that |i − j| = 1, say j = i + 1. Then by Proposition 4.14 there is a
vertex either i−1 or i+2 adjacent to this square. This situation guarantees another
alternating square either qi−1,i+1 or qi+2,i . By Proposition 4.5, there is another
connected 2-fracture graph having a square qi,j with j = i + 2, as wanted.

Proposition 4.17. Let n ≥ 9. If qi−1,i+1 is an alternating square of a connected
2-fracture graph Q, then both i-edges are incident to the square as shown in the
following figure.


i+1

i



i−1

'&%$
!"#
v

i−1



i+1



i

'&%$
!"#
w

Moreover the degree, in Q, of vertices v and w is one.
Proof. Suppose that there is no i-edge incident to a vertex of the square qi+1,i−1 .
Then, by Proposition 4.14, an edge incident to qi+1,i−1 has labels i + 2 or i − 2. By
duality we may assume there is an edge incident to the square having label i + 2.
Then there is a square sharing an edge with qi+1,i−1 , as shown in the following
figure.
/.-,
()*+
v3

i+1

i+2

i−1

i−1

/.-,
()*+
v4

/.-,
()*+
v1

i+1

/.-,
()*+
v2

i+2

'&%$
!"#
v✤
✤ i−1
✤
'&%$
!"#
w

By Proposition 4.15 there is no i-edge incident to the vertices of the figure above.
Furthermore, the vertices v1 and v2 have degree three and the vertices v3 and v4

20

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

have degree two. Thus one of the vertices on the right must have degree three.
Suppose v has degree three. Then it is (i + 3)-incident to another vertex, and we
get a square qi+3,i−1 as pictured below.


i+1



i−1



i+2

i−1
i+1



i+2

✤ i+3
✤ i−1
✤

i+3

✤
✤ i−1
✤


Again, by Proposition 4.15, there is no i-edges incident to the vertices of this
figure. Continuing this process we get a graph that doesn’t have i-edges, hence Γ
is disconnected, a contradiction.
Hence there is a vertex of the square i-adjacent to another vertex v. Consider
v1 , v2 , v3 and v4 as in the following figure.
/.-,
()*+
v3

i+1

/.-,
()*+
v1

i−1

/.-,
()*+
v4

i

'&%$
!"#
v

i−1

/.-,
()*+
v2

i+1

If the degree of v, in Q, is greater than one, then there exist an edge with label
j not consecutive with i and incident to v. Then there is an alternating square qi,j
containing v and v1 . Hence v1 has degree at least four in G, which is not possible
by Proposition 4.15. Thus the degree of v is one in Q.
Suppose that v4 is i-adjacent, in Q, to a vertex w. Then the degree of w,
analogously to v, is one. Thus either v2 or v3 is k-adjacent to another vertex. As
k is not consecutive either with i + 1 or i − 1 there is a square qk,i±1 containing v1
or v4 . Thus v1 or v4 is of degree four and we get a contradiction.
Now suppose that neither v2 nor v3 is i-adjacent to any vertex. Either v2 , v3 , or
v4 has degree three. Using duality we may assume that either v3 or v4 has degree
three. Suppose at first that v3 has degree three. By the same arguments as above
v3 is (i + 2)-adjacent to another vertex v5 . Then there exists an alternating square
qi+2,i−1 containing v3 , v4 , v5 , and v6 as seen in the following figure. Thus, both v3
and v4 have degree three.
()*+
/.-,
v✤5
✤
i−1 ✤
()*+
/.-,
v6

i+2

/.-,
()*+
v3

i+1

i−1
i+2

/.-,
()*+
v4

/.-,
()*+
v1

i

'&%$
!"#
v

i−1
i+1

/.-,
()*+
v2

On the other hand, if we assume that v4 has degree three, then using duality,
we may assume it is incident to an edge of label i + 2. Thus there is an alternating
square qi−1,i+2 containing v3 ; thus both situations give the same result.
Now if the other i-edge of Q is incident to either v5 or v6 , this creates an alternating square qi,i+2 containing either v3 or v4 , which is not possible because they
have degree three. Continuing this process we never get a way to connect the other
i-edge, giving a contradiction.
Hence either v2 or v3 is i-adjacent, in Q, to some vertex w. Moreover the same
argument used to prove that v has degree one holds for w.


HIGHEST RANK OF A POLYTOPE FOR An

21

Proposition 4.18. Let n ≥ 9. If G has a connected 2-fracture graph, then either
the 2-fracture graph is a tree or Γ is embedded in C2 ≀ Sn/2 .
Proof. Suppose G has a connected 2-fracture graph that is not a tree and let Q be
a 2-fracture graph with a square qi+1,i−1 accordantly with Proposition 4.16.
By Proposition 4.17 there are two i-edges incident to the square. Let v1 , v2 , v3
and v4 be the vertices of qi+1,i−1 , as in the following figure.
/.-,
()*+
v3

i+1

i

/.-,
()*+
v1

i−1

'&%$
!"#
v

i−1

/.-,
()*+
v4

i+1

/.-,
()*+
v2

'&%$
!"#
w

i

The degree of v and w are both one. Hence, by Proposition 4.17, either v3 or
v4 has degree three. Suppose without loss of generality that v3 has degree three.
Now the label of the edge incident to v3 , not in the square qi−1,i+1 , must have label
i + 2. This creates an alternating square qi−1,i+2 in G. In particular the degree of
v4 is also three.
/.-,
()*+
v✤5
✤
i−1 ✤
/.-,
()*+
v6

i+2

/.-,
()*+
v3

i+1

/.-,
()*+
v4

'&%$
!"#
v

i−1

i−1
i+2

i

/.-,
()*+
v1

i+1

/.-,
()*+
v2

i

'&%$
!"#
w

As n ≥ 9 either v5 or v6 has degree three. Assume that v5 is incident to another
vertex v7 . Then the label of the edge {v5 , v7 } must be (i + 3) and the degree of v5
must be three. Then there exists an alternating square qi−1,i+3 in G, and therefore
the degree of v6 must be three. If n = 10 we are done. Otherwise we continue this
process. The result is the graph below where i = 1.
✤
✤
0 ✤


r−1

✤
✤
0 ✤
r−1


✤
✤
0 ✤


5

5

✤
✤
0 ✤


4

4

✤
✤
0 ✤


3



2



0



3

1



0
2



1



Now the permutation graph of Γ is the graph above or has another 0-edge connecting
the vertices on the right. Indeed these are all the edges of G for otherwise there is a
cycle containing an edge of Q and no other edge with the same label, a contradiction.
In any case we get Γ embedded into C2 ≀ S n2 (since all the permutations ρi preserve
the partition whose parts are the 0-edges and the pair of vertices on the right). 
Corollary 4.19. With the assumptions of Proposition 4.18, if the 2-fracture graph
is not a tree, there are two possibilities for Γ, namely
(a) The permutation representation graph is the following and Γ ∼
= C2 × Sn/2 .

0



r−1



0
r−1





5

0





4

0
5



3

0



4





2

0
3





1

0
2




0

1



(b) The permutation representation graph is the following and Γ depends on
parity of n. If n/2 is even, then Γ ∼
= C2 ≀ Sn/2 and if n/2 is odd then

22

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER
n/2−1

Γ∼
= C2

: Sn/2 which is a subgroup of index 2 in C2 ≀ Sn/2 .

0



r−1



0
r−1





5

0





4

0
5



3

0



4





2

0
3





1



0
2



1



Finally in this section, we prove the main theorem in the case where all Γi are
intransitive and 2-fracture graphs exist. So our assumptions now are:
• Γ∼
= An ;
• all Γi ’s are intransitive, and each ρi interchanges at least two pairs of points
in different Γi -orbits.
The conclusions we reached from the second assumption are given in Propositions
4.12 and 4.18: either
• there is a 2-fracture graph of which one component is a tree and the others
are unicyclic; or
• the permutations are as given in Corollary 4.19.
In the first case, such a graph has n − 1 edges. So 2r ≤ n − 1, as required. In the
second, the group Γ is not An .
5. All Γi ’s intransitive: no 2-fracture graphs
In this section we continue to handle the case where all subgroups Γi are intransitive. In particular, we deal with the case where Γ does not have any possible
2-fracture graph. Although some of our results are more general, throughout this
section we will make the assumption that Γ is isomorphic to An .
Suppose that all maximal parabolic subgroups of Γ are intransitive but there
exists i ∈ {0, . . . , r − 1} such that ρi permutes only one pair {a, b} of vertices in
different Γi -orbits. Consequently, the only generators that can act non-trivially on
a and b are ρi−1 and ρi+1 .
We will say that the orbit of a is the first Γi -orbit and the orbit of b is the second
Γi -orbit. Let n1 and n2 be the sizes of the first and the second Γi -orbit, respectively;
and let A and B be the correspondent groups, determined by the action of Γi on
each orbit. Both A and B are string groups generating by involutions (or sggi’s).
Indeed let ρj = αj βj with αj and βj being the permutations in each Γi -orbit. Then
A := hαi | i ∈ {0, . . . , r − 1}i and B := hβi | i ∈ {0, . . . , r − 1}i.
Proposition 5.1. If A is primitive, then the set JA := {i | i ∈ {0, . . . , r − 1} and
αi 6= 1A } is an interval. The same result holds for B.
Proof. Suppose that JA is not an interval. Then A = H × K for H = hαj | j ∈ J1 i
and K = hαj | j ∈ J2 i for some disjoint index sets J1 and J2 such that JA = J1 ∪J2 .
As both H and K are transitive on the n1 points, the cardinality of J1 and J2 is at
least two. Moreover each generator αj commutes with all generators of a transitive
group on n1 points, either H or K, which implies that it has full support on the
first Γi -orbit. Therefore, it has a nontrivial action on a. However, we have seen
that the only generators that can act nontrivially on a are ρi−1 and ρi+1 . This
gives a contradiction, so JA is an interval. The proof also works for B.

Thanks to Proposition 5.1 we consider (up to duality) separately the following
cases : Case (1) A and B are both imprimitive; Case (2): JA and JB are intervals

HIGHEST RANK OF A POLYTOPE FOR An

23

and i ∈
/ {0, r − 1}; Case (3): we deal with the remaining cases, particularly we
assume that JB = ∅ or an interval.
5.1. Case (1): A and B are both imprimitive. Let A be embedded into Sk1 ≀
Sm1 and B be embedded into Sk2 ≀ Sm2 with n1 = m1 k1 and n2 = m2 k2 . Consider
a minimal subset M of the set of generators of Γi generating the group induced on
the two block systems. Let R be the set containing the remaining generators of Γi .
Consider the permutation representation graph X for the block action, that is,
a graph having m1 + m2 vertices, corresponding to the blocks, and with a j-edge
between two blocks whenever ρj swaps them. As Γi has exactly two orbits, the
graph X has two connected components. Also, consider the subgraph X̄ of X with
the same vertices and with a j-edge for each element of M , between blocks in
different Γj -orbits. This is a fracture subgraph of X , particularly X¯ has no cycles.
Hence |M | ≤ m1 + m2 − 2.
Similarly, consider the graph Y with k vertices corresponding to the hM i-orbits,
with a j-edge between a pair of hM i-orbits L and L′ whenever there is x ∈ L such
that xρj ∈ L′ with ρj ∈ R. Let Ȳ be a fracture subgraph of Y having only one jedge for each element ρj ∈ R between hM i-orbits in different Γj -orbits. As before,
Ȳ has no cycles and has at least two components. Hence |R| ≤ k − 2. Note that
k ≤ k1 + k2 , hence |R| ≤ k1 + k2 − 2.
Proposition 5.2. If |M | = m1 + m2 − 2 then X has two connected components
and consecutive labels. Up to a duality, X is the following graph.
i−m1 +1

i−2

i−1

a

b

i+1

i+m2 −1

i+2

Proof. Since |M | = m1 + m2 − 2 and X̄ has two components, X̄ = X . As ρi only
swaps the points a and b in different Γi -orbits, a j-edge of X incident to the blocks
containing a and b, must be consecutive with i.
The graph X does not have any alternating squares, and thus only edges with
consecutive labels are incident. Up to duality, we have determined X .

Proposition 5.3. If |M | = m1 + m2 − 3 then, up to duality, either m1 = 2 or
m1 ≥ 4, accordantly to one of the following graphs.
i−1

(1)
(2)

i+m1 −3

i+m1 −2

a

i−1

b

i+m1 −3

i−m2 −1

i−2

i+1

a

b

i−1

i−m2 −1

Proof. As X̄ has m1 + m2 − 3 edges, it has 3 connected components. Since X has
two components, there exists a j-edge ej of X such that X¯ ∪ ej has two components
and no cycles. Hence, as in Proposition 5.2 incident edges of X̄ ∪ ej must have
consecutive labels.
First suppose that the j-edges of X̄ ∪ ej are different Γi -orbits. We claim that
j = i ± 1. Assume the contrary. Then there is a path in the first Γi -orbit connecting
the block containing a to the block moved by ρj ; the same happens in the second
Γi -orbit: there is a path connecting the block containing b to the block moved by
ρj .
j

i−1

a

b

i+1

j

24

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Assume that j > i + 1. Then both of these paths have to contain the label i + 1, a
contradiction. Thus j = i±1. Up to duality we may consider j = i−1 corresponding
to the first possibility for X .
Now consider the j-edges of X¯ ∪ ej in the same Γi -orbit; assume it is the first
orbit. There is a path in X̄ ∪ ej joining the four blocks swapped by ρj which has
consecutive labels and no repeating labels other than j. Thus this path is a single
edge with label j ± 1. Assume that this edge has label j + 1. At least one of the four
vertices of X̄ ∪ ej that are incident to the j-edges has degree one. Otherwise, there
would be another repeated label. This gives the second possibility for the graph X
where j = i − m1 − 3 with m1 ≥ 4.

Proposition 5.4. If an element of R has a nontrivial action between more than
one pair of hM i-orbits, then |R| ≤ k − 3.
Proof. In this case Ȳ has at least three connected components, and still has no
cycles. Thus |R| ≤ k − 3.

In what follows let La be the hM i-orbit containing a and Lb the hM i-orbit
containing b.
Proposition 5.5. If |M | = m1 + m2 − 3 then |R| ≤ k1 + k2 − 3.
Proof. As Ȳ is a forest and has at least two components, |R| ≤ k − 2. If k < k1 + k2
then |R| ≤ k1 + k2 − 3. Assume that k = k1 + k2 and that we have the equality
|R| = k1 + k2 − 2. Then Ȳ has exactly two components and there are at least two
hM i-orbits in each Γi -orbit. As |M | = m1 + m2 − 3 we have, up to duality, one of
the two possibilities for X given in Proposition 5.3.
First suppose that m1 + m2 > 4. There are, up to duality, the two possibilities
for X given in Proposition 5.3. In graph (1) there is only one possibility to connect
La to another hM i-orbit, that is using a pair of (i + 1)-edges. Then in both cases,
(1) and (2), there is only one possibility to connect Lb to another hM i-orbit, that
is, with a single edge with label l = i − m2 − 2 (between vertices of the last block
of the second Γi -orbit). Furthermore, ρl swaps exactly one pair of vertices of these
hM i-orbits. Then as Γ is even ρl must swap another pair of hM i-orbits, hence we
have a contradiction with Proposition 5.4.
Now let m1 + m2 = 4. In this case X is as in figure (1) of Proposition 5.3 and
M = {ρi−1 }. To connect La to another hM i-orbit, or Lb to another hM i-orbit,
there are only two possibilities for the labels, either l = i − 2 or l = i + 1. By
Proposition 5.4 we may assume that either La or Lb is (i − 2)-adjacent to another
hM i-orbit. Then we use the fact that Γ is even and Proposition 5.4 to get a
contradiction.

Proposition 5.6. If |M | = m1 + m2 − 2 then |R| ≤ k1 + k2 − 4.
Proof. Up to duality we may consider X as in Proposition 5.2. First the elements
of R must fix all the blocks. Otherwise there is ρj ∈ M such that Γj is transitive, a
contradiction. Let C be the set of generators in R that commute with all elements
of M . We have that |R \ C| ≤ 2.
There is at most one hM i-orbit adjacent to La in Ȳ, and the label of the edge
which might connect them is ρf := ρi−m1 . Similarly, there is at most one hM iorbit adjacent to Lb in Ȳ, and the label of the edge which might connect them is
ρl := ρi+m2 . We denote the hM i-orbits adjacent to La and Lb , L′a and L′b resp. if

HIGHEST RANK OF A POLYTOPE FOR An

25

they exist. Furthermore, both ρf and ρl , if they exist, swap a single pair of points
in these hM i-orbits.


f −1





i−1



i−1

'&%$
!"#
a

i

'&%$
!"#
b

i+1



i+1





l−1



l−1

f




l

f −1









Since Γ is even, ρf and ρl must both have nontrivial action on a point in another
hM i-orbit. We now consider separately the cases: |R \ C| = 0, |R \ C| = 1 and
|R \ C| = 2.
If R \ C = ∅, then La and Lb are the unique hM i-orbits, R = ∅ and k = 2. Thus
|R| = 0 ≤ k1 + k2 − 4.
Suppose that R \ C = {ρf }. In this case Lb coincide with the second Γi -orbit.
As Y has at least two f -edges, by Proposition 5.4, |R| ≤ k − 3. In addition,
k ≤ k1 + k2 − 1, thus |R| ≤ k − 3 ≤ k1 + k2 − 4.
Now let R \ C = {ρf , ρl }. We may assume Ȳ with an f -edge between La and L′a ,
and with an l-edge between Lb and L′b . Since Γ is even, both ρf and ρl act nontrivially on a point in a hM i-orbit other than La , Lb , L′a and L′b . By Proposition 5.4,
Ȳ has at least three components. Furthermore, to have three components there
must exist a pair of hM i-orbits {L, L′ } such that both ρl and ρf swap a point in L
with a point in L′ . Indeed, ρl acts trivially on the points not in L, L′ , Lb or L′b and
ρf acts trivially on the points not in L, L′ , La or L′a . Let us assume that L and L′
are both in the first Γi -orbit. Then ρl swaps L and L′ entirely.
First suppose L = L′a . Then, both ρf and ρl , act nontrivially on a point in
′
La . Thus there is an alternating square, with labels f and l, containing this point.
Hence ρl acts nontrivially on a point in La , which we have shown is impossible.
Consequently L 6= L′a , as well as L′ 6= L′a .
Since Γi has only two orbits, there is a generator ρj ∈ R that sends a point in
either L or L′ to a point not in these two hM i-orbits; without loss of generality we
may assume that ρj sends a point in L′ to a point in a hM i-orbit which we denote
L′′ . Then the unique possibility is j = l + 1. However, then ρj commutes with all
the elements of M which act between blocks in the first Γi -orbit. Thus ρj swaps L′
and L′′ . This guarantees an alternating square with labels j and f , with ρf acting
nontrivially on L′′ . This implies that L′′ = L′a . Moreover this forces ρj to have a
nontrivial action on La , a contradiction.

Proposition 5.7. If A and B are both imprimitive then r ≤

n−1
2 .

Proof. By Propositions 5.5 and 5.2, we have r = |R|+|M |+1 ≤ k1 +k2 +m1 +m2 −5.
As k1 + m1 + k2 + m2 − 5 ≤ k1 m1 +k22 m2 −1 , we conclude that r ≤ n−1

2 .
5.2. Case 2: JA and JB are intervals and i ∈
/ {0, r − 1}. We first recall two
propositions on sggi that can be found in [14] that we use to deal with this case.
Proposition 5.8. [14, Proposition 3.3] Let Φ = hα0 , . . . , αd−1 i be a transitive
permutation group acting on the set of points {1, . . . , n} with n ≥ 5, and let Φ∗ =
hα0 , . . . , αd−1 , αd , αd+1 i, where
αr
αr+1

= (i, n + 1)(n + 2, n + 3) for some i ∈ {1, . . . , n}
= (n + 1, n + 2)(n + 3, n + 4).

26

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Then Φ∗ is isomorphic to Sn+4 if it contains an odd permutation, and to An+4
otherwise .
The term sesqui-extension was first introduced in [13]. Let us recall its meaning.
Let Φ = hα0 , . . . , αd−1 i be a sggi, and let τ be an involution in a supergroup of
Φ such that τ 6∈ Φ and τ commutes with all of Φ. For fixed k, we define the
group Φ∗ = hαi τ ηi | i ∈ {0, . . . , d − 1}i where ηi = 1 if i = k and 0 otherwise, the
sesqui-extension of Φ with respect to αk and τ .
Proposition 5.9. [14, Proposition 5.4] If Φ = hαi | i = 0, . . . , d − 1i and Φ∗ =
hαi τ ηi | i ∈ {0, . . . , d − 1}i is a sesqui-extension of Φ with respect to αk , then:
(a) Φ∗ ∼
= Φ × hτ i ∼
= Φ or Φ∗ ∼
= Φ × 2.
(b) whenever τ ∈
/ Φ∗ , Φ is a string C-group if and only if Φ∗ is a string C-group.
In this case we may assume that A = Γ<i and B = Γ>i . As A or B can have
small degree ≤ 11, in what follows we list all primitive even string C-groups of small
degree, with intransitive maximal parabolic subgroups, having rank r ≥ n−1
2 .
Proposition 5.10. Let Φ be string C-group with a connected Coxeter diagram
isomorphic to an even primitive group of degree n ≤ 11. If Φj is intransitive for
every j ∈ {0, . . . , r − 1} then either r ≤ n−2
or Φ has one of the permutation
2
representation graphs given in Table 2.
Proof. We used Magma to get this result.



Proposition 5.11. Let j ∈ {0, . . . , r − 1}. Suppose that Γ<j is transitive on m
points and fixes the remaining m − n points. If Γ<j is a primitive group of degree
then it must have permutation representation graph (1), (2)
m < 12 and j ≥ m−1
2
or (3) of Table 2.
The dual version of this proposition is also true.
Proof. By Proposition 5.10, Γ<j has one of the 16 permutation representation
graphs given in Table 2. Let X := {1, . . . , n} \ Fix(Γ<j ) with |X| = m. Then
there exists a generator ρk of Γ, with k ≥ j, such that cρk = d with c ∈ X and
d 6∈ X. As Γ<j is primitive, k must be consecutive with j − 1. Moreover, c has
degree two with the edges incident to c having labels j − 1 and j. In graphs (8),
(9), (13) and (15) there is no such vertex c. Let us consider the remaining graphs.
Now let (4) be the permutation representation graph of Γ<j . Then Γ<j = Γ<4 ∼
=
A9 and Γ>1 ∼
=
= An−4 by Proposition 5.8 (note that n − 4 ≥ 5), thus Γ>1 ∩ Γ<4 ∼
A5 . However, hρ2 , ρ3 i is a dihedral group. Consequently Γ does not satisfy the
intersection condition, a contradiction.
Only in cases (11) and (16) there are two possibilities for the vertex c, but as
in case (4), case (16) is self-dual. Using similar arguments, summarised below, we
conclude that Γ<j cannot be any of the graphs of Table 2 except graphs (1), (2)
and (3). Let (11)* denote the dual of (11) with its labels interchanged by k ↔ 4−k.
(5), (6), (7):

Γ>1 ∼
= An−4 (by Proposition 5.9);
= 2 × An−4 or Γ>1 ∼
6 hρ2 , ρ3 i.
Γ<4 ∼
=
= A5 ∼
= A9 ; Γ>1 ∩ Γ<4 ∼

(10), (11), (11)*, (12): Γ>2 ∼
= An−5 ; Γ<5
(14), (16):
Γ>3 ∼
= An−6 ; Γ<6

∼
= A10 ; Γ>2 ∩ Γ<5
∼
= A11 ; Γ>3 ∩ Γ<6

∼
= A5
∼
= A5

∼
6 hρ3 , ρ4 i.
=
∼
6 hρ4 , ρ5 i.
=

HIGHEST RANK OF A POLYTOPE FOR An

(1)

D10

(2)

L2 (5)



(3)

L2 (5)



(4)

A9

(5)



0



3



A9

1



0



1



0



1



0
2
0



1



0



1



2





1



2
0



1



2





0



1



2



3



2

2



3



2



1



0





A9

3




(7)

(8)

3



A9



A9

1

2

1



3







2

0



A9

2

1



0



0



1

1





2

0

1



0

0
2




2



(10)

A10

(11)

A10



(12)

A10

4
0



3



1



4





4



3



3



A10

0
2





3

3



2



1



A11



(15)

A11



(16)

A11



0
2
0
2
0



1

1

3

0





1

0  1  2  3  4  3 
2
3  4  3  2  1  0 
2

2

1



0



1



2



3



2



(14)

2



0



(13)











3 2 3 2

3








0





2
1
0
2  1  0 



3

3

3



(9)

0





2 1

2



(6)

27



1



0



1



2



3



4





1



0



1



2



3



4





1



0
2



1



2



3



4



3
5
5
3
5

0
4




2 1

0
4




2 3
4





4



5





4



5





4



3
5



Table 2. Even transitive string C-groups of degree m with connected Coxeter diagram having intransitive maximal parabolic sub.
groups and rank ≥ m−1
2


Proposition 5.12. Let Φ = hα0 , . . . , αd−1 i be a transitive sggi embedded into Sa ≀Sb
with X being the set of generators of Φ generating the block action independently.
If Φj is intransitive for all j ∈ {0, . . . , d − 1}, then

28

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

(a) d ≤ |X| + a − 1;
(b) d ≤ ab−2
for a, b 6= 2 and ab 6= 9;
2
(c) if (a, d) = (2, b) or (b, d) = (2, a) or (a, b) = (3, 3) then Φ either contains
an odd permutation or has disconnected diagram.
Proof. Consider a partition P of {1, . . . , ab} determined by the orbits of hXi. Now
let X be a graph with |P | vertices corresponding the partitions of P and with exactly
one j-edge for each generator of Φ that is not in X, connecting two partitions in
different Φj -orbits. This graph has no cycles and |P | ≤ a, thus d − |X| ≤ a − 1.
Hence, d ≤ |X| + a − 1. Moreover as X generate the bock action independenty
|X| ≤ b − 1. Hence d ≤≤ a + b − 2 ab−2
for a, b 6= 2 and ab 6= 9.
2
Now suppose that (a, d) = (2, b) or (b, d) = (2, a) and Φ is even, up to duality, Φ
has the following permutation representation graph, and


1

0





2

0
1





3

0
2


0



3





d−1

0

0





d−1



Thus Φ has a disconnected diagram.



Using induction over n and Proposition 5.12 we get the following result.
Proposition 5.13. Suppose that Φ is string C-group generated by involutions of
rank d, with connected diagram, having all maximal parabolic subgroups intransitive.
If Φ is a transitive even group of degree m with 12 ≤ m < n then, d ≤ m−1
2 .
Moreover if d = m−1
then
Φ
is
the
alternating
group
A
.
m
2
Proof. If Φ is primitive and not the alternating group then, by Proposition 2.2,
d ≤ m−2
2 . If Φ is imprimitive, then it is embedded into a group Sa ≀ Sb with ab = m
and with the block action being generated by at most b − 1 elements. As the
maximal parabolic subgroups of Φ are intransitive we may use Proposition 5.12 to
get
m−2
.
d≤
2
for a, b 6= 2. If either a = 2 or b = 2 then, as Φ is even and has a connected diagram,
m
∼
d< m
2 with m even, hence d ≤ 2 . Finally if Φ = Am with 12 ≤ m < n, we then
get the result by induction on n.

Proposition 5.14. Suppose that Γ<3 is not one of the string C-groups (2) or (3)
Table 2. If A is the string C-group (1) of Table 2, then r ≤ n−1
2 . The same result
holds for B.
then, by Proposition 5.11,
Proof. Consider first n − 5 < 12. If r − 3 ≥ (n−5)−1
2
B (= Γ>2 ) is one of the small examples (1), (2) or (3) of Table 2, thus n < 12, a
contradiction. Hence r − 3 < (n−5)−1
. Let n − 5 ≥ 12.
2
Suppose first that ρ2 has a trivial action on the first Γi - orbit. In this case Γ>1
is an even transitive group on n − 4 points. By Proposition 5.9 Γ1 ∼
= hρ0 i × Γ>1 .
n−1
and
hence
r
≤
Now, by Proposition 5.13, we get that r − 2 ≤ (n−4)−1
2
2 .
Now suppose that ρ2 has a nontrivial action on the first block. As Γ<3 cannot
be one of the string C-groups (2) or (3) of Table 2, it is a sesqui extension of it

HIGHEST RANK OF A POLYTOPE FOR An

29

(with respecto to ρ2 ). If B is not the alternating group, then by Proposition 5.13,
we get that r − 3 ≤ (n−5)−2
. We need only to consider the case B = Γ>2 ∼
= An2 .
2
Let Φ be either the string C-group (2) or (3) of Table 2 and τ be the action of ρ2 in
the second Γ2 -orbit. As either τ = (ρ1 ρ2 )3 or τ = (α1 α2 )5 (according to each case
(1) or (2)), Γ<3 is isomorphic to hτ i × Φ. But then, as Γ>2 ∼
= An2 , τ ∈ Γ>2 ∩ Γ<3 ,
.

a contradiction. Hence r ≤ n−1
2
Proposition 5.15. Suppose neither Γ<3 nor Γ>r−4 is one of the string C-groups
(2) or (3) of Table 2, or their duals. If A and B are not both the alternating groups,
then r ≤ n−1
2 .
Proof. By Proposition 5.14 it may be assumed that neither A nor B is the string
C-group (1) of Table 2.
If A and B are not alternating groups then by Propositions 5.13 and 5.10, i ≤
n1 −2
and r − 1 − i ≤ n22−2 . If A is the alternating group, then either n ≤ 12
2
and i ≤ n12−2 (by Proposition 5.10) or, n1 ≥ 12 and then, by Proposition 5.13
(induction) we conclude that i ≤ n12−1 . Analogously if B is the alternating group
then r − 1 − i ≤ n22−1 . In any case if A and B are not both the alternating groups,
r ≤ 1 + n1 +n2 2 −3 = n−1

2 .
Proposition 5.16. Suppose neither Γ<3 nor Γ>r−4 is one of the string C-groups
(2) or (3) of Table 2, or their duals. If A and B are both alternating groups then
r ≤ n−1
2 .
Proof. In this case Γ<i+1 is a sesqui extension of a sggi Φ with respect to ρi , where
Φ is a group of degree n1 +1. By Proposition 5.9 Γ<i+1 is isomorphic either to 2×Φ
or Φ. Suppose that Γ<i+1 ∼
= 2 × Φ. In that case there is an even permutation τ on
the second Γi -orbit that belongs to Γ<i+1 . As Γ>i ∼
= An2 , τ ∈ Γ>i and therefore
τ ∈ Γ<i+1 ∩Γ>i , a contradiction. Hence Γ<i+1 ∼
= Φ and Φ is itself a string C-group.
Using the same argument Γ>i−1 is also isomorphic to a transitive group Ψ of degree
n2 + 1. Moreover either Φ or Ψ is a even group. Suppose Φ is even. Then, as A
is not one of the string C-groups (1), (2) or (3), either n1 < 12 and i ≤ n12−2 , or
n1 + 1 ≥ 12. In latest case, by Proposition 5.13 i + 1 ≤ (n1 +1)−1
. In addition,
2
n2 −1
n−1

r − 1 − i ≤ 2 , hence r ≤ 2 .
Proposition 5.17. Suppose neither Γ<3 nor Γ>r−4 is one of the string C-groups
(2) or (3) of Table 2, or their duals. Let i ∈
/ {0, r − 1}. If A ∼
= Γ<i and B = Γ>i
n−1
then r ≤ 2 .
Proof. This is a consequence of Propositions 5.15 and 5.16.



To complete this case we still need to deal with Γ<3 , Γ>r−4 , or both, being one
of the string C-groups (2) or (3) of Table 2. This is included in Case 3, at the end.
5.3. Case 3: The remaining cases. Assume in this case that JB is either empty
or an interval. As before let G be the permutation representation graph of Γ.
Proposition 5.18. If e is an f -edge of G not in an alternating square, then any
path (not containing another f -edge) from e to an edge with label l, with l < f
(resp. l > f ), contains all labels between l and f . Moreover, there exists a path
from e to an l-edge, that is fixed by Γ>l (resp. Γ<l ).

30

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Proof. Consider a path starting in e and containing an l-edge. Let f < l. Suppose
that none of the edges of the path has label k, for some f < k < l. Then in this
path there is an edge with label < k meeting an edge with label u > k. Suppose
that this is the first time in the path that this happens. Then there is an alternating
square, containing e and a u-edge, a contradiction, as shown in the following figure.



u



...
 /o /o /o o/ /o /o /o /o 

u



f

u
u



l

 /o /o /o /o /o /o /o 




Proposition 5.19. Let i = 0. If ρr−1 acts non-trivially on both Γi -orbits, then
r ≤ n−1
2 .
Proof. By Proposition 5.18 there are two paths, one in the first and the other in the
second Γi -orbit, each containing all labels from 1 to r − 1. Thus 2(r − 1)+ 1 ≤ n− 1.
Hence r ≤ n2 . Suppose we have the equality. In that case the paths have consecutive
labels, as in the following figure and n is precisely the number of vertices of the two
paths.


r−1



r−2





1



0

1





r−2





r−1



But then there is no place for extra i-edges unless r = 3 (which gives the bound
trivially as n ≥ 12).

Proposition 5.20. Let i = 0. Let h 6= r − 1 be the maximal label such that ρh
acts non-trivially on both Γi -orbits. There exists a set of vertices X, contained in
and Γ>h fixes {1, . . . , n} \ X.
the Γi -orbit fixed by ρr−1 , such that h ≤ n−|X|−1
2
n−|X|−1
Moreover if h =
then Γ<h has the following permutation representation
2
graph, where the black dots represent the vertices of {1, . . . , n} \ X.
•

h

•

h−1

•

•

1

•

0

•

1

•

h−1

•

•

h



Proof. By Proposition 5.18 there exist a path P1 from the h-edge in the first Γi -orbit
to the vertex a, and a path P2 from the h-edge in the second Γi -orbit to the vertex
b, each of them containing all labels from 1 to h − 1, and fixed by Γ>h . In that case,
the two paths give us 2h+1 ≤ |Fix(Γ>h )| = n−|X| with X := {1, . . . , n}\Fix(Γ>h )
as required. When equality holds, the permutation representation graph is the one
given in this proposition.

Proposition 5.21. Let X := {1, . . . , n} \ Fix(Γ>j ). If Γ>j is transitive on X and
there exists a permutation ρl with l < j acting non trivially on X, then r − 1 − j ≤
|X|
|X|
2 − 1. Moreover if r − 1 − j = 2 − 1 then, Γ>j has one of the following
permutation representation graphs for some k ∈ {j + 1, . . . , r − 1}.


j+1

l


l



j+1



k

l





k+1

l



k


l



k+1

k+2
k



k+2


l


k



l

r−1
k



r−1


l

k



HIGHEST RANK OF A POLYTOPE FOR An


l

j+1
k




l


k



j+1

l

k−2
k




l

k−2

k−1
k





k

l

k−1





l



k

31

r−1

l




l



r−1



Proof. If ρl acts non trivially on X then Γ>j must be imprimitive with blocks of size
two, with ρl swapping all pairs of vertices inside the blocks. Let M an independent
generating set for the block action of Γ>j and suppose that the group generated
by M is intransitive on X. Then there must be two orbits on X under the action
of hM i and some k > j such that ρk swaps points of distinct orbits. But then, as
ρl ∈ Γk , Γk is transitive on X. Moreover, ρk only moves points in X which is the
union of two Γk -orbits. These two orbits are already fused by ρl ∈ Γk . Therefore,
Γk has to be transitive on {1, . . . , n}, a contradiction. So the action of hM i must be
transitive on X. If |M | = |X|
2 − 1 there are only the given possibilities for Γ>j . 
In what follows we suppose that i > 0 and that all generators acting on the
second Γi -orbit have labels > i. As JA is not an interval, Γ<i can either transitive
or intransitive on the first Γi -orbit. We consider these cases separately.
Proposition 5.22. Let r > n−1
2 . Let h > i be the maximal label of a permutation
acting non-trivially on both Γi -orbits. If Γ<i is transitive on the first Γi -orbit then
h = i + 1, h < r − 1 and there exists a set of vertices X, contained in the second
Γi -orbit, such that h ≤ n−|X|−1
and Γ>h fixes {1, . . . , n} \ X.
2
then
Γ<h (with h = i+1) has the following permutation
Moreover if h = n−|X|−1
2
representation graph for some k ∈ {2, . . . , i − 1} where the black dots represent the
vertices of {1, . . . , n} \ X.
•
i+1 k

•

0

•

i+1 k
0

•

1

•

i+1 k
1

•

•
i+1

i−1

•

i+1

•

i−1

i

•

i+1



•

Proof. In this case, Γ<i is transitive on the first Γi -orbit O1 , which has size n1 .
Moreover there exists h > i such that ρh acts non-trivially on O1 . This action is
fixed-point-free and hence ρh moves a and n1 is even. But since the i-edge {a, b}
is not in a square by hypothesis, h = i + 1 and Γ>h acts trivially on O1 . Moreover
by the dual of Proposition 5.21 we have that i ≤ n21 − 1. Thus h = i + 1 ≤ n21 .
As JB is an interval, ρi+1 is the unique permutation acting nontrivially on b. If
h 6= r − 1, Γ>h fixes O1 and a vertex in the second Γi -orbit, so at least n1 + 1
. The equality cannot occur
vertices altogether. Then h ≤ |Fix(Γ2>h )|−1 ≤ n−|X|−1
2
as it would imply that n − |X| = n1 + 1 is even, a contradiction. So h ≤ n−|X|−1
2
as wanted. Moreover, when the equality holds, by the dual of Proposition 5.21, the
only possibility is the permutation representation graph given in the statement of
this proposition.
Now suppose that h = r − 1. Then r − 1 ≤ n21 . As n ≥ n1 + 2, r ≤ n2 . As
n
by hypothesis r > n−1
2 , we have the equality r = 2 . Then Γ has the permutation
representation graph given in the statement of this proposition with h = i+1 = r−1,
with some additional i-edges. As all Γj ’s must be intransitive, the extra i-edges
must be vertical edges. Hence one of ρi and ρi+1 has to be an odd permutation, a
contradiction.


32

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Proposition 5.23. Let r > n−1
2 . Let h > i be the maximal label of a permutation
acting non-trivially on both Γi -orbits. If Γ<i is intransitive in the first Γi -orbit,
then h < r − 1 and there exists a set of vertices X, contained in the second Γi -orbit,
such that h ≤ n−|X|−1
and Γ>h fixes {1, . . . , n} \ X.
2
n−|X|−1
Moreover if h =
then h = i+1 and Γ<h+1 has the following permutation
2
representation graph, where the black dots represent the vertices of X.
•
i+1

0

•

1

•

0

•

i+1

i+1

•

•
i+1

•

1

i−1

•

i

•

i+1

•

i−1

i+1



•

Proof. In this case JA is not an interval thus, by Proposition 5.1, A is imprimitive
embedded into Sk ≀ Sm and Γ<i is fixing all the blocks (with k, m ≥ 2). By Proposition 5.18 there exist a path P1 from the h-edge in the first Γi -orbit to the vertex a,
and a path P2 from the h-edge in the second Γi -orbit to the vertex b, each of them
containing all labels from i + 1 to h − 1, and fixed by Γ>h . In addition there is a
path P3 in the block β containing the vertex a, and edges with all labels from 0 to
i − 1. Moreover, there is also a path P4 in the block βρi+1 also containing edges
with all labels from 0 to i − 1.
Let us first assume that there is an edge with label l > i inside one of the two
blocks β or βρi+1 . Then the generator ρl is fixed-point-free on the block containing
that edge. Suppose that block is β. Then l = i + 1, a contradiction. Suppose then
that the edge is in βρi+1 . Then l = i + 2 = h and there are only two blocks in
the block system. Moreover, ρl acts inside βρi+1 and provides an embedding of
Γ<i into S2 ≀ Sk/2 . Thus, since Γj is intransitive for every j, a similar argument
to the one used in the proof of Proposition 5.21 shows that i ≤ k/2 − 1. Hence
h − 2 ≤ k/2 − 1. Now if h = r − 1, as n ≥ 2k + 2 (the extra 2 coming from the
n−2
(as n must be at least
h-edge in the second Γi -orbit), we get r − 1 ≤ n+2
4 < 2
7 in this case) giving a contradiction with the hypotheses of the proposition. Thus
h < r − 1 and Γ>h fixes a set P of size 2k + 2. Therefore, h ≤ |P |+2
≤ |P 2|−1 for
4
every |P | ≥ 4 which is obviously the case here as k ≥ 2.
Let us now assume that all edges with label l > i are not contained in β nor in
βρi+1 . Then the paths P1 , P2 , P3 and P4 have no edge in common, as shown in
the following figure.


h

/o /o o/ P/o 1 /o /o /o

i+1

i−1

i

i−1

O
P4

'&%$
!"#
a

i+1

O

O


O

P2
'&%$
!"#
b /o /o o/ /o /o /o /o

h

'&%$
!"#
c

O

O P3


Suppose that h 6= r − 1 and that ρh+1 acts trivially on the first Γi -orbit. Let
P be the set of vertices of P1 ∪ P2 ∪ P3 ∪ P4 excluding the vertex c on the right
hand side of the diagram above, and X = {1, . . . , n} \ P . The set P is fixed by
Γ>h and 2h + 1 ≤ |P | = n − |X|. Moreover when 2h + 1 = |P | the permutation
representation of Γ<h is the one given in this proposition with h = i + 1.
Now if h = r−1, we have 2(r−1)+1 ≤ n−1. Hence r ≤ n2 , and by hypotheses we
must have the equality. Therefore Γ has precisely the permutation representation
graph given in the statement of this proposition with some additional i-edges. As

HIGHEST RANK OF A POLYTOPE FOR An

33

all Γj ’s must be intransitive, the extra i-edges must be vertical. Hence one of ρi
and ρi+1 has to be an odd permutation, a contradiction.
It remains to prove that Γ>h fixes the first Γi -orbit. Suppose the contrary. Then
ρr−1 acts nontrivially on the first Γi -orbit. In this case consider the path P1 as
before, with the label of its first edge being r − 1 instead of h, and consider P3 and
P4 has before. Now let P2 be a copy of P1 whose last vertex is aρi−1 , as in the
following figure.



r−1

/o /o o/ P/o 1 /o /o /o

i+1

i−1

i−1
r−1

/o /o /o /o /o /o /o
P2

P4

i

'&%$
!"#
a

O

i+1

O

O

'&%$
!"#
b /o /o /o /o /o /o /o

h



O

O P3


O


In this case 2(r − 1) + 1 ≤ (n − 1) − 1, a contradiction.



Proposition 5.24. Let r > n−1
2 . Let i 6= 0 and JB be an interval with labels > i.
If h > i is the maximal label of a permutation acting non-trivially on both Γi -orbits,
then h < r − 1 and there exists a set of vertices X, contained in the second Γi -orbit,
and Γ>h acts trivially on {1, . . . , n} \ X.
such that h ≤ n−|X|−1
2
Proof. This is consequence of Propositions 5.22 and 5.23.
Proposition 5.25. Let n ≥ 8. If i 6= 0 and JB = ∅ then r ≤


n−1
2 .

Proof. Similarly to the proof of Proposition 5.23, A is embedded into a wreath
product Sk ≀ Sm with n = km + 1 and Γ<i fixing the blocks. If there is a label l > i
such that ρl acts nontrivially inside a block then m = 2, r − 1 = l = i + 2 and Γ<i
is embedded into S2 ≀ Sk/2 , giving the inequality i = r − 3 ≤ k/2 − 1 ≤ n−1
4 − 1.
.
Hence for n ≥ 8, r ≤ n−1
2
Suppose then that every generator with label > i acts trivially on the blocks
it fixes. Thus there are four paths P1 , P2 , P3 and P4 , as in the following graph,
containing all but one label twice and one cycle that is an alternating square.



r−1

/o /o o/ P/o 1 /o /o /o

i+1

/o /o /o /o /o /o /o
P2

P4

i

i−1

i−1
r−1

'&%$
!"#
a

O

i+1

O
O



O

'&%$
!"#
b

O

O P3


Hence 2(r−1)+1 ≤ n. If equality holds, the paths contain exactly one edge for each
label, but then as all Γj ’s are intransitive, ρi acts trivially on {1, . . . , n} \ {a, b},
and thus is a transposition, a contradiction. Therefore r ≤ n2 . If n is odd then
r ≤ n−1
2 . If n is even then n1 is odd, and neither k = 2 nor m = 2. Hence there at
least two more vertices not in the paths, and then 2(r − 1) + 1 ≤ n − 2. Therefore
r ≤ n−1

2 .
Proposition 5.26. Let n ≥ 12. Suppose that h > i is the maximal label of a
permutation acting non-trivially on both Γi -orbits. If h 6= r−1 and Γ>h is transitive
on X := {1, . . . , n} \ Fix(Γ>h ) then, either r ≤ n−1
2 , or one of the groups Γ<3 or
Γ>r−4 is one the string C-groups (2) and (3) given in Table 2 or their duals.

34

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

Proof. Suppose that Γ>h is neither the dual of the string C-group (2) nor the
string C-group (3) given in Table 2. Then, by Propositions 5.11, 5.13 and 5.14,
|X|−1
if Γ>h is the alternating group A|X| .
r − 1 − h ≤ |X|−1
2 . Moreover r − 1 − h =
2
n−|X|−1
n−|X|−1
. Suppose that Γ>h ∼
.
By Proposition 5.24, h ≤
= A|X| and h =
2
2
If ρi has a nontrivial action on X then, by Proposition 5.21, Γ>h must be imprimitive with blocks of size two, a contradiction. Thus we may assume that ρi fixes X
pointwise and swaps a pair of vertices in {1, . . . , n} \ X.
If i = 0 then Γ<h has the permutation representation graph given in Proposition 5.20. The string condition implies that h = 2 and Γ<3 must be the string
C-group (2) given in Table 2, a contradiction.
When i 6= 0, either r ≤ n−1
or Γ<h has either the permutation representation
2
graph given in Proposition 5.22 or the one given in Proposition 5.23. As all Γj ’s
must be intransitive, the extra i-edges must be vertical edges. Hence one of ρi and
ρi+1 has to be an odd permutation, a contradiction.
Hence either h < n−|X|−1
or r − 1 − h < |X|−1
2
2 , which implies in both cases that
n−1
r≤ 2 .

In the previous proposition we considered the case where ρh acts nontrivially in
both Γi -orbits and Γ>h is transitive on the points it does not fix. Let us now deal
with the case where Γ>h is intransitive.
In what follows we use the results of the previous section on 2-fracture graphs.
Observe that in the proofs of Propositions 4.10 and 4.12 none of the following three
conditions on Γ were needed: intersection condition, connectedness of the diagram
and the group being even. Indeed all we need is a string group G generated by a
set {δj | j ∈ {0, . . . , d − 1}} of involutions where δj swaps two pairs of vertices in
different Gj -orbits for each j ∈ {0, . . . , d − 1}.
Proposition 5.27. Let t ∈ {0, . . . , r − 2} and U := {1, . . . , n} \ Fix(Γ>t ). If t is
such that
,
• t ≤ n−|U|−1
2
• Γ>t has a 2-fracture graph,
• Γ>t acts intransitively on U ,
then r ≤ n−1
2 .
Proof. Assume first that t = r − 2. In this case, |U | ≥ 4 for ρr−2 to be an even
permutation. Hence r ≤ n−1
2 . Let t < r − 2 be the maximal label satisfying the
conditions of this proposition.
Suppose that Γ>t has c nontrivial orbits U1 , . . . , Uc . For each set Us with s ∈
{1, . . . , c} denote by Is the set of labels l (> t) of edges in Us . Consider the graph
C whose vertices are the orbits U1 , . . . , Uc , and two orbits Us and Uq are joined by
an l-edge if there exist a point in Us and a point in Uq that are swapped by ρl .
Consider a (simple) fracture graph F of Φ := Γ>t , that is, a graph with |U |
vertices and r − 1 − t edges. Such a graph exists by the second hypothesis of
the proposition. Each l-edge of F connects vertices in different Φl -orbits. Let
s ∈ {1, . . . , c} and Fs be the set of labels of edges of F within Us . Clearly Fs ⊆ Is .
Choose F such that it satisfies the following property:
P1 if l ∈ Fs is the label of the unique l-edge in one component swapping vertices
in different Γl -orbits, then no other component has more than one pair of
vertices in different Γl -orbits.

HIGHEST RANK OF A POLYTOPE FOR An

35

Let Gs be the group action of Γ>t in Us . We have that Gs is generated by a
set of involutions (not necessarily independent) with labels in Is . The subset of
involutions with labels in Fs is independent since Fs is the subset of labels of edges
of F . We denote by (Gs )j the group generated by all involutions of the generating
set of Gs except the one with label j.
If Gs does not admit a 2-fracture graph with set of labels Fs , then there exists
an edge e with label l ∈ Fs with ρl swapping only one pair of vertices of Us , in
different Γl -orbits. Let m be the minimal label and x be the maximal label of an
edge inside Us . By Proposition 5.18 there exists a path P1 containing all labels
from l − 1 to m and another path P2 containing all labels from l + 1 x in Us . Let
P = P1 ∪ {e} ∪ P2 . Now we deal separately with the cases m > t + 1 and m = t + 1
and we conclude, in both cases, that x ≤ n−|X|−2
where X := {1, . . . , n}\Fix(Γ>x ).
2
m > t + 1: If m > t + 1 then a component Uq adjacent to Us also contains all
labels from m to x. Let Uz be a component containing an edge with label m − 1.
We can reach it from Us with a shortest path in C. The last component before Uz
in this path, say Uw , contains a copy P ′ of P. Thus there is a t-edge from Uw to
Uz .


m

t

'&%$
!"#
v

m−1



 m+1  /o /o /o /o /o /o /o 
t

t
m



m+1

x

 /o /o /o /o /o /o /o 



Uw

t

t
x



Uz

As m is the minimal label in Uw , m−1 ∈
/ Uw , thus m−1 = t+1. Let P be the set of
|−1
.
vertices of P ∪P ′ . We have 2(x−(t+1)) ≤ |P |−2, hence x ≤ t+ |P2 | ≤ n−|U|+|P
2
As Γ>t has a 2-fracture graph by hypothesis, there is at least one more edge with lan−1
bel t+1, so |U | > |P |+1 and x ≤ n−3
2 . If x = r−1 then r ≤ 2 . Let x 6= r−1. The
vertex v is fixed by Γ>x as well as all vertices of P . Let X := {1, . . . , n} \ Fix(Γ>x ).
.
Then we have x ≤ n−|X|−2
2
m = t + 1: Suppose that m = t + 1. Furthermore assume that any component
containing a unique l-edge between vertices in different Γl -orbits, has minimal label
t + 1. Let x be the maximal label in Us and let P be as before. We now use the fact
that Γ>t has a 2-fracture graph, and thus there exists another component Uq having
one l-edge e′ between vertices in different components. Moreover by Property (P1)
this l-edge cannot be in an alternating square inside Uq . By assumption the minimal
label in Uq is also t + 1. Let y be the maximal label in Uq . Assume that y ≥ x.
Then, there exists a path P1′ containing all labels from l−1 to t+1 and another path
P2′ containing all labels from l + 1 to x, both in Uq . Consider P ′ = P1′ ∪ {e′ } ∪ P2′ .
There is at most one vertex of P ′ that is not fixed by Γ>x . Let Q be the set of
vertices of P ∪ P ′ .


t+1

 /o /o /o /o /o /o /o 

x





t+1

 /o /o /o /o /o /o /o 

x

'&%$
!"#
c /o /o /o /o /o /o /o /o 

Us
y



Uq

In this case Γ>x fixes the set Q \ {c}. Hence 2(x − t) ≤ |Q| − 2 and we get
x≤

n − |X| − 2
2

36

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

where X := {1, . . . , n} \ Fix(Γ>x ).
In both cases, thanks to the maximality of t we conclude that either x = r − 1
or Γ>x is transitive on X. If x = r − 1, r ≤ n−2
2 . Suppose Γ>x is transitive on
X. In this case X is a subset of Us for some s ∈ {1, . . . , c}. If Γ>x is fix-point-free
on Us , then ρt centralizes Γ>x , thus, by Proposition 5.21, r − 1 − x ≤ |X|
2 − 1.
n−|X|−2
n−1
Hence r ≤ 2 . If Γ>x has fixed points in Us , then x 6=
and, as by
2
.
This
concludes
the
case
where Gs
Proposition 5.13 r − 1 − x ≤ X2 , we get r ≤ n−1
2
has no 2-fracture graph.
Therefore we may assume that Gs admits a 2-fracture graph with set of labels
Fs and therefore Fs ≤ |U2s | . We can use the results of Section 4.
Suppose that Γ>t+1 is transitive on Us . Take the closest orbit Uq to Us in C such
that Γ>t+1 is intransitive on Uq and let P be a shortest path from Us to Uq . We
can use ρt modify F along this path, to concentrate all edges of the fracture graph
in Uq . We obtain another fracture graph also satisfying P1. Hence, we may assume
that Fx is empty for every orbit Ux of P except Uq . Therefore |Fx | = 0 ≤ |Ux2|−2 .
Thus in every component with Fs 6= ∅ there exists an edge with label t + 1 between
vertices in different Γt+1 -orbits. Consequently there is at most one component
having a connected 2-fracture graph, and r − 1 − t ≤ |U|−(c−1)
where c is the
2
number of Γ>t -orbits of size at least 2. Whenever c > 2 or if |Fx | = 0 for some x,
n
we get r ≤ n−1
2 . Let us now assume c = 2. In this case, if r = 2 , the 2-fracture
graph on Us is connected and has an alternating square (by Proposition 4.10), and
the 2-fracture graph on Uq is disconnected, and has two components, one having
an alternating square and the other being a tree. These two components in Uq
must moreover be connected by a t-edge. These components satisfy the following
|U |−1
equalities: |Fs | = |U2s | , |Fq | = q2 , Is = Fs and Iq = Fq ∪ {t + 1}. Let Gs be the
group action in Us and let Gq be the group action in Uq .
Recall that t < r −2. If (Gq )t+2 is transitive on Uq then ρt+1 centralizes Gq , thus
the two components of the 2-fracture graph of Gq have the same shape, so they
must both be trees, a contradiction. Thus (Gq )t+2 is intransitive on Uq . Moreover
t + 2 ∈ Fq as Iq = Fq ∪ {t + 1}. Therefore t + 2 ∈
/ Fs = Is , hence ρt+1 centralizes
Gs . But then there exists an edge with label l 6= t + 1 in Us incident to the t-edge
that connects Us to Uq , thus l ∈ Is ∩ Iq , a contradiction.

Proposition 5.28. Let n ≥ 12. Suppose that i is the maximal label such that
• Γi has two orbits with a single i-edge joining them;
• there exists h > i such that ρh acts non-trivially on both Γi -orbits.
If r >

n−1
2 ,

then one of the following occurs.

(a) Γ>r−4 is the dual of the string C-group (2), or the string C-group (3) given
in Table 2;
(b) Γr−1 has exactly two orbits, one being trivial.
Proof. Let h be maximal. Let us choose the vertices a and b, and consequently
the groups A and B, such that JB is an interval with all labels in JB being > i.
If JA is also an interval, then, as h ∈ JA ∩ JB , i = 0; we assume without loss of
generality that r − 1 ∈ JA \ JB (Recall that the case h = r − 1 has been dealt with
in Proposition 5.19).

HIGHEST RANK OF A POLYTOPE FOR An

37

Denote by O1 and O2 the orbits of A and B respectively. By Proposition 5.20
when i = 0, and Proposition 5.24 when i 6= 0, we have that h < r − 1 and
h ≤ n−|X|−1
with X := {1, . . . , n} \ Fix(Γ>h ) ⊆ O2 . If Γ>h is transitive, by
2
Proposition 5.26, one of the groups Γ<3 or Γ>r−4 is one of the string C-groups (2)
or (3) given in Table 2 or their duals. Thus we may assume that Γ>h is intransitive.
Now if Γ>h has a 2-fracture graph, by Proposition 5.27, r ≤ n−1
2 , a contradiction.
Hence Γ>h does not admit a 2-fracture graph. Then there exists j > h such that
ρj only swaps one pair of vertices in different Γj -orbits. Choose j minimal with
this property. Then Γ{h+1,...j−1} has a 2-fracture graph. Let C and D be the
group actions of Γj in each Γj -orbit with C acting on the orbit L1 containing the
i-edge {a, b}. Let L2 denote the other Γj -orbit. If one of the groups is trivial then
either we get case (b) of the statement of this proposition or r ≤ n−1
2 by the dual
of Proposition 5.25, a contradiction. Thus assume both C and D are nontrivial
sggi’s. Indeed let ρj = γj δj with γj and δj being the permutations in each Γj orbit. Then C = hγi | i ∈ {0, . . . , r − 1}i and D := hδi | i ∈ {0, . . . , r − 1}i. Let
JC := {i ∈ {0, . . . , r − 1} | γi 6= 1C } and JD := {i ∈ {0, . . . , r − 1} | δi 6= 1D }. By
Propositions 5.1 and 5.7 either JC or JD is an interval. If C = Γ<j and D = Γ>j
or Γ>r−4 is, up to duality, one of the string
then by Proposition 5.17, r ≤ n−1
2
C-groups (2) or (3) given in Table 2. This gives case (a) of the statement.
It remains to consider the case where there exists a permutation ρg acting nontrivially on both Γj -orbits. Choose g minimal. Thanks to the maximality of i,
g < j. As g ∈ JD we have that g > i. We now consider four cases:
(1) If j = r − 1 and g = 0, then by the dual of Proposition 5.19, we get a
contradiction.
(2) If j = r−1 and g 6= 0, then both JC and JD are intervals and g is the minimal
label of a permutation acting nontrivially on L2 . Then we can use the dual of
Proposition 5.20 to conclude that r−g ≤ n−|Y2 |−1 with Y := {1, . . . , n}\Fix(Γ<g ) ⊆
L1 . If g ≤ h then, by Proposition 5.18, there is a path in X containing all labels
from h to r − 2 twice. Let V be the set of vertices of this path, then r − h ≤ |V2 | .
|−1
Hence r ≤ n−|X|−|V
, giving a contradiction. Hence g > h and X ∩ Y 6= ∅.
2
(3) Let j 6= r − 1 and JD be an interval. In this case both ρ0 and ρr−1 act
nontrivially on the first Γj -orbit. Hence we can use the dual argument to the
one used in the last paragraph of the proof of Proposition 5.23, to conclude that
r ≤ n−1
2 , a contradiction.
(4) Let j 6= r − 1 and JC be an interval. By the dual of Proposition 5.24, g < 0
and r − g ≤ n−|Y2 |−1 with Y := {1, . . . , n} \ Fix(Γ<g ) ⊆ L1 . By the same reasoning
as in (2), h > g.
Only cases (2) and (4) are possible and both give the inequality r − g ≤ n−|Y2 |−1
with Y := {1, . . . , n} \ Fix(Γ<g ) ⊆ L1 and h > g.
By choice of j, there is no other label l between h and g having only one pair of
vertices in different Γl -orbits. Then Γ{h+1,...,g−1} has a 2-fracture graph. Moreover
Γ>h ∩ Γ<g is intransitive on X ∩ Y for if it were transitive, then Γ>h would be
transitive on X, contradicting the assumptions of the proposition. Hence the 2fracture graph for Γ{h+1,...,g−1} is disconnected and g − h − 1 ≤ |X∩Y2 |−1 . We have
h ≤ n−|X|−1
, g − h ≤ |X∩Y2 |−1 + 1, r − g ≤ n−|Y2 |−1 and n = |X| + |Y | − |X ∩ Y |,
2
n−1

thus r ≤ 2 , a contradiction.

38

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

We now consider that A is trivial or has the permutation representation graph
(2) or (3) of Table 2.
Proposition 5.29. Let i = 0. If A is trivial and Γ>1 is transitive on {1, . . . , n} \
{a, b}, then r ≤ n−1
2 .
Proof. As ρ0 acts nontrivially on {1, . . . , n} \ {a, b} and centralizes Γ>1 , by Proposition 5.21, r − 2 ≤ n−2
2 − 1 and therefore r ≤ n/2. Suppose that we have the
equality. Then Γ>1 is as given in Proposition 5.21, and either ρ0 or ρ1 is odd, a

contradiction. Hence r ≤ n−1
2 .
Proposition 5.30. Let A have the permutation representation Fx = ∅ or (3) of
Table 2 (this implies that n ≥ 7). If Γ>4 is transitive on n−7 vertices then r ≤ n−1
2 .
Proof. In this case i = 3 and ρi has full support on the n − 7 vertices that are not
fixed by Γ>4 . So n− 7 is even. By Proposition 5.21, r − 5 ≤ n−7
2 − 1. Moreover if we
have the equality then either ρ3 or ρ4 is odd, a contradiction. Hence r − 5 < n−7
2 −1
n−1
and r ≤ 2 .

Proposition 5.31. Suppose that A is trivial or has permutation representation
graph (2) or (3) of Table 2 and B is the alternating group. If Γ>i+1 is intransitive
on the second Γi -orbit and Γ>i has a 2-fracture graph, then r ≤ n−1
2 . Moreover if
then
one
of
the
following
possibilities
must
occur.
r > n−3
2
with X = {1, . . . , n} \
(a) there exists x ∈ {0, . . . , r − 1} such that x ≤ n−|X|−1
2
Fix(Γ>x ).
(b) Γ has the following permutation representation graph.





0

1



2



0



1

3

0 1



2





0 1

0 1



3

r−1





0 1
r−1



Proof. Consider the graph C as in the proof of Proposition 5.27, with t = i + 1. Let
U , Us , Gs , Fs and Is be as in Proposition 5.27.
Suppose there is a component Us that does not have a 2-fracture graph. Let
m and x be the minimal and the maximal label of that component respectively.
We proved in Proposition 5.27 that m ∈ {t + 1, t + 2} and accordantly to these
possibilities for m the permutation representation graph of Γ contains one of the
following graphs.
 t+2  t+3  /o /o /o /o /o /o /o  x 
m=t+2:

m = t + 1:



t

t+1
t+1
t+1



t

t

t+2



t+3

 /o /o /o /o /o /o /o 

t

t

 /o /o /o /o /o /o /o 
x
x

x





 /o /o /o /o /o /o /o 
'&%$
!"#

c
Let P be the set of vertices of the first graph and Q be the set of vertices of the
second graph. If x 6= r − 1, in the first case Γ>x fixes P , and in the second case
Γ>x fixes Q \ {c}. If i = 0 and t = 1 we have that x ≤ |P 2|+1 or x ≤ |Q|
2 . If i = 3
(and t = 4), x ≤ |P 2|+7 or x ≤ |Q|+6
.
2
Suppose that x = r−1 and r ≥ n−2
2 . Consider first that A is trivial and m = t+2.
|P |+1
In this case n ≥ |P |+2 and 2 ≥ n−4
2 , thus |P | ∈ {n−5, n−4, n−3, n−2}. Then
it is possible to determined the permutation representation graph of Γ according

HIGHEST RANK OF A POLYTOPE FOR An

39

#

|P |

Possibilities for Γ when A is trivial

1

n−2


 1


2

0



1



2

3


 1

2


 1

3

n−4



0



1



0
2



1



 r−1 
 1  1
r−1

3

3


 1

 r−1 
 1  1
r−1

Table 3. Possibilities depending on |P | for Γ when A is trivial

to the value of |P |. If |P | = n − 2 then Γ is the graph (1) of Table 3 which is not
an even group. It is also not possible to get an even group when |P | = n − 3, as
there must exist a Γ>1 -orbit with a 2-edge. For |P | = n − 4 it is possible to create
such a component and we get the graph (2) of Table 3. But as Γ>1 does not have a
2-fracture graph we get a contradiction. If |P | = n − 5, it is not possible to create
a third Γ>1 -orbit, thus Γ>1 has exactly two components, one containing P and the
other having an even number of vertices swapped pairwise by ρ0 , a contradiction.
Now let A be trivial and m = t + 1. In this case |Q| ∈ {n − 4, n − 3, n − 2}. In
Table 4 we list all possibilities for the permutation representation graph of Γ for
each value of |Q|. If the permutation representation graph of Γ is one of the graphs
(3), (5a), (5b) or (5c), then Γ is odd, a contradiction. Thus the only possibility is
the permutation representation graph (4), giving the graph of the statement of this
proposition.
Now let A be the permutation representation graph (2) of Table 2 and m = t+ 2.
If r ≥ n−2
2 and x = r−1 then |P | ∈ {n−11, n−10, n−9, n−8, n−7}. In Table 5 we
list all possibilities for Γ according to |P |. For |P | = n − 7 we get the permutation
representation graph (1) and Γ is odd, a contradiction. Then |P | < n − 8, as there
must exist a Γ>4 -orbit containing a 5-edge and a 3-edge. Thus for |P | = n−9 we get
the permutation representation graph (2), but Γ>4 doesn’t have a 2-fracture graph,
a contradiction. Now suppose |P | ≤ n − 10. Either there are two Γ>4 -orbits, one
having a set of vertices P and another having ρ3 swapping all its vertices pairwise,
or there exist a third Γ>4 -orbit containing a 5-edge. For this to happen at least
two additional vertices are needed, thus |P | = n − 11. This gives the permutation
representation graph (3), which again corresponds to an odd group, a contradiction.
In Table 6, we list all possibilities for Γ when A has the permutation representation graph (2) of Table 2 and m = t + 1. As before r ≥ n−2
2 and x = r − 1, hence
|Q| ∈ {n − 10, n − 9, n − 8, n − 7}. In (4), (6a), (6b), (6c), (6d), (7b), (7c), (7d),
(7e) and (7f) Γ is odd. In the remaining case the intersection condition fails.
If A has the permutation representation graph (3) of Table 2 we get the same
contradictions as in Tables 5 and 6.
Now suppose that x 6= r−1. The group Γ>x fixes the first Γi -orbit and the vertex
b. Let X := {1, . . . , n}\Fix(Γ>x ). When i = 0 and t = 1 we have |X| ≤ n−(|P |+2)
and x ≤ |P 2|+1 , or |X| ≤ n − (|Q \ {c}| + 2) and x ≤ |Q|
2 , giving in any case
.
When
i
=
3
and
t
=
4,
we
have
|X|
≤
n
−
(|P
| + 7) and x ≤ |P 2|+7 ,
x ≤ n−|X|−1
2
n−|X|
or |X| ≤ n − (|Q \ {c}| + 7) and x ≤ |Q|+6
. Suppose we have the
2 . Hence x ≤
2
equality. Then Γ contains one of following two graphs, having all vertices fixed by

40

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

#

|Q|

Possibilities for Γ when A is trivial

3

n−2


4

0



0




1




1

n−3


5a




n−4

2

0

1

1

1


 0

2


 0

2


 0

2




3




3




3

0 1
2




r−1

0 1




0 1










r−1

0 1







r−1

0 1

0 1
3




0 1

r−1

3

0 1
2

0 1

3

0 1
2




r−1

0 1




0 1

r−1




0 1

r−1

or



5b

1

0




2

1


 0

2
0

n−4


5c



0


 0

2


0 1


3

1

2




2



0



1



2

0 1
3

3


0 1


1


 0

n−4



3

0 1




0 1

r−1

 r−2  r−1  r−2 
0 1
0 1
0 1
0 1




r−2

2

2


0 1


3




3

3

r−1


0 1


r−2

 r−1 
0 1
0 1


r−1

or





0



1



0
2

1


 0

2

0 1
2




0 1
3




r−1

0 1




0 1

r−1

Table 4. Possibilities depending on |Q| for Γ when A is trivial

#

|P |

1

n−7

Possibilities for Γ when A
has the permutation representation graph (2)


2

3

n−9



n − 11



2
0

2
0

2
0






1

1

1






0

0



0



1



1



1




2

2

2




3

3





3






4

4



3

3

4


5


5

4
3



 5


 4

5

4

4




6

6


 4

 r−1 
 4  4
r−1

5

 6 
 4  4

 r−1 
 4  4

5

 6 
 4  4

 r−1 
 4  4

6

6

r−1

r−1

Table 5. Possibilities depending on |P | for Γ when A has permutation representation graph (2)

Γ>x , except one of vertices c or d of graph (2).
(1)


2
0



1



0



1



2



3



4



5


4

6
6


4

 x 
4 4
x

HIGHEST RANK OF A POLYTOPE FOR An

#

|Q|

4

n−7

Possibilities for Γ when A
has the permutation representation graph (2)


5

2
0

2
0

6d

2
0



2
0

n−9



1

2
0

7b

n − 10



7e

0

2
0


2
0



2

3



4

3






1





0



1

2






4

2






1





0



1

5

3

4

4

4



0

1







1



0

2



1



3



2



5




6


 3

5


3 4


6


 3

5

5




6

4


 3

5

3 4
5

5

3



1

1







0



0



1



1



1





0

2



2




1

3
4

2



n − 10



2
0



1

2
0





0

1







1



0

2



1



3 4

0



1



0





0



1



0



3
6

1




1




4

n − 10
2



2

n − 10
2

3

2

2





3 4


 r−1 
3 4
3 4








3 4

r−1

r−1




3 4
6

r−1

r−1

3 4

3 4

r−1




6




3 4




3 4

r−1

3 4

4

 5  6 
 3 3  4 3  4

 r−2  r−1  r−2 
3 4 3 4 3 4 3 4








6

5




4




5

3
3

4

3



6




3 4

4




4




4




5




5

4

3

3
3



6




3 4



5

5

6


 3

4

4


 3

5




5

5

5





3 4
6

4


 3

5

5




4

4


3 4




6

3 4

n − 10


7f

1

n − 10


7d


2


7c

0



n−9


7a




 3

n−9


6c

1



n−9


6b



n−8


6a

41

5

6








 3

5

3 4
5

4

r−1


3 4


 r−1 
3 4
3 4



r−2









r−1




6

r−2

r−2




3 4

r−1







3 4

r−1

3 4
6




3 4

3 4

3 4
5

r−1

3 4

r−2

r−2

r−1

3 4
6

r−1

r−2

3 4

6

6




r−1

3 4

 r−2  r−1  r−2 
3 4 3 4 3 4 3 4








4


3 4


6




4




6

4

4

6


 3

5


 3

5

5

6

3 4
5

r−2

r−1


3 4


 r−1 
3 4
3 4



6

r−2

r−1







3 4

r−1

3 4




3 4

r−1

Table 6. Possibilities depending on |Q| for Γ when A has permutation representation graph (2)

or


(2)


2
0



1



0



1



2



3



4



5

5




6

6









x

x




3 4

r−1

 5  6 
 3 3  4 3  4
5




3 4

'&%$
!"#
c
()*+
/.-,
d

Then as x 6= r − 1 there is another vertex v, not fixed by Γ>x , incident to one of
the vertices of one of the two graphs above. If Γ contains the graph (1), v must be
attached to it by a 4-edge, which is not possible. This rules out graph (1). In the
second graph, the two components of the figure are not adjacent, since otherwise

42

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

c and d are both fixed by Γ>x . Suppose first that c is the vertex not fixed by
Γ>x . Then there is another component Ul adjacent to the Γ>4 -orbit containing the
vertex d, as in the following figure.



2
0



1



0



1



2



3



4



6

4

5











4

6

x

4



Ul

4

x

/.-,
()*+
d

But Γ>x is fix-point-free in Ul , a contradiction. This shows that x ≤ n−|X|−1
. If
2
d is the vertex not fixed by Γ>x , then the component adjacent to the component
having the vertex c must be fixed by Γ>x , giving a contradiction as before.
This finishes the case where some component does not have a 2-fracture graph.
We now consider that each group Gs has a 2-fracture graph for Fs . Particularly
each component Us with Fs 6= ∅ has at least four vertices. In addition let F be a
fracture graph satisfying the property (P1) and such that E := {Fs | Fs = ∅, s ∈
{1, . . . , c}} has maximal size. Denote by S and δs the following numbers.
c

δs = |Fs | −

X
|Us |
and S :=
δs .
2
s=1

As Gs has a 2-fracture graph for Fs , δs ≤ 0 for all s ∈ {1, . . . , c}. Let Up be the
component such that t+ 1 ∈ Fp . In Proposition 5.27 we proved that (Gs )t+1 cannot
be transitive in Us . Therefore a fracture graph for Gs with s 6= p is disconnected.
Hence δs ≤ −0.5 for s 6= p. If S ≤ −3, then r − 1 − t ≤ |U|
2 − 3. For (i, t) = (0, 1),
n−2
|U | ≤ n−2 hence r−2 ≤ 2 −3. For (i, t) = (3, 4), |U | ≤ n−7 hence r−5 ≤ n−7
2 −3.
.
In
what
follows
we
prove
that
either
S
≤
−3
or
we
have
(a)
In any case r ≤ n−3
2
of the statement of this proposition.
Note that if Fs 6= ∅, then as Gs has a 2-fracture graph for Fs , |Us | has at least
four vertices.
As ρi is an even permutation and fixes the first Γi -orbit except the vertex a,
it must act nontrivially as an odd permutation in U . In what follows we consider
separately the following cases: (1) ρi swaps an odd number of pairs of vertices (v, w)
with v ∈ Us and w ∈ Ux with s 6= x; (2) ρi acts as an odd permutation inside a
component Us with Fs 6= ∅ and s 6= p; (3) ρi acts as an odd permutation inside Up ;
(4) ρi acts as an odd permutation inside a component Us with Fs = ∅.
(1) If ρi swaps an odd number of pairs of vertices (v, w) with v ∈ Us and w ∈ Ux ,
then |Us | = |Ux | is odd. If |Ux | = |Us | = 3 then Fx = Fs = ∅, hence S ≤ −3.
Consider |Ux | = |Us | ≥ 5. As |E| is maximal, either Fx = ∅ or Fs = ∅. We may
assume that |Fx | = 0. Then |Fs | < 25 . Thus δx ≤ −2, 5 and δs ≤ −0, 5. Hence
S ≤ −3.
(2) Consider now that ρi acts as an odd permutation inside a Γ>t -orbit Us with
Fs 6= ∅ and s 6= p. In this case ρi centralizes Gs , therefore |Us | is even and |Us | ≥ 6.
Moreover there is a 2-fracture graph for Gs with labels in S := Fs ∪ {t + 1} being
disconnected and having no cycles. Hence |Fs | + 1 ≤ |Us2|−2 , thus δs ≤ −2. Suppose
δs = −2. In that case the permutation representation graph of Gs is as follows,
where x is the maximal label in Us and k ∈ {t + 1, . . . , x}.

HIGHEST RANK OF A POLYTOPE FOR An



t+1

i


i



t+1

k


i



k+1


i



k

i



k+2



k+1

i

k





k+2

x


k

i



43


i

k



k



x

Suppose that x 6= r − 1. Then Γ>x fixes Us , the vertex b and the first Γi -orbit.
Hence there exists x ∈ {0, . . . , r − 1} as in statement (a) of this proposition. Thus
we may consider that δs < −2. As in this case |Us | is even, δs is an integer thus
δs ≤ −3 and S ≤ −3.
If x = r − 1, we have r − 1 − t ≤ |U2s | − 1. For (i, t) = (0, 1), |Us | ≤ (n − 2) − 4
where 4 is the minimal size of Up . For (i, t) = (3, 4), |Us | ≤ (n − 7) − 4. In any case
we get r ≤ n−3
2 .
(3) If ρi acts as an odd permutation inside Up , then a 2-fracture graph of Gp is
|U |−2
disconnected without cycles. Hence |Fp | ≤ p2 , that is δp ≤ −1. Suppose we
|U |−2
have the equality |Fp | = p2 . Then the permutation representation graph of Gs
is as the permutation representation graph given in case (2). The only difference is
that in this case t + 1 ∈ Fp . In this case we get exactly the same result as before,
that is statement (a) of this proposition. Assume now that δp < −1. As in case
(2), |Up | is even, thus δp is an integer. Then we may assume that δp ≤ −2.
Suppose that t + 2 ∈
/ Fp . If t + 2 ∈
/ Ip or (Gp )t+2 is transitive in Up , then
ρt+1 also centralizes Gp . But then there exists l ∈ Ip ∩ Ix with Ix being the set
of labels of a component Ux adjacent to Up . Then a 2-fracture graph of Gx has
at least three components, hence δx ≤ −1. Thus δp + δs ≤ −3 and |S| ≤ −3. If
t + 2 ∈ Ip and (Gp )t+2 is intransitive in Up , then Gp has a disconnected 2-fracture
graph without cycles for Fs ∪ {ρt+2 }. Hence 2(|Fp | + 1) ≤ |Up | − 2. Moreover if we
have the equality then Gs is as the permutation representation graph given in case
(2). Hence 2(|Fp | + 1) < |Up | − 2 and δp ≤ −3.
We now consider that t+2 ∈ Fp . Suppose |S| = −2.5. Then c = 2 and the second
component Us is such that δs = −0.5. In particular, Fs 6= ∅, for otherwise δs ≤ −1.
First suppose that (Gs )t+2 is transitive in Us . Then ρt+1 centralizes Gs . Hence
2|Fs | ≤ |Us | − 2 and δs ≤ −1, a contradiction. Thus Gt+2 is intransitive in Us . As
t+2 ∈
/ Fs , a 2-fracture graph for Gs , with labels in Fs , has at least 3 components
with at most one cycle, hence 2|Fs | ≤ |Us | − 2, as before, a contradiction.
(4) Suppose that ρi acts as an odd permutation inside a component Us with
Fs = ∅. Either |Us | = 2 or |Us | ≥ 6. But in the second case clearly δs ≤ −3,
thus we consider Us = {u, v}. Let l be the number of components of size two,
whose vertices are swapped by ρi . We need to consider the case l odd. If l ≥ 3
then S ≤ −3, hence we assume l = 1. Moreover let ρi be a 2-transposition,
ρi = (a b)(u v). Then Is = {t + 1}.


t

'&%$
!"#
u

t+1
i=t−1

t

'&%$
!"#
v



If t+1 = r−1 then Γ has one of the following permutation representation graphs.
(i, t) = (0, 1) :


0



1



0
2



1



2



1



2



1





1



2



44

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

(i, t) = (3, 4) :


0



1



0
2

1



2





3



4



3
5



4



5



4

5





4



5





5



4



As by hypotheses Γ>i has a 2-fracture graph, for (i, t) = (0, 1), we have n ≥ 9, and
for (i, t) = (3, 4), we have n ≥ 15. In both cases r ≤ n−3
2 .
Assume t+1 6= r−1. In this case Γ>t+1 fixes the first Γi -orbit and {b, u, v, uρt, vρt }.
If |{b, u, v, uρt , vρt }| = 5, consider x = t + 1. Then x satisfies (a) of this proposition. Otherwise, |{b, u, v, uρt , vρt }| = 4. Then Γ contains one of the following
graphs.
For (i, t) = (0, 1):


0



1



0
2



1



2



0
2



1



2



3



4



3
5



2



4



5

For (i, t) = (3, 4):


0



1









5



In the first case, Γ>2 has at least five fixed points. Therefore x = 2 satisfies the
statement (a) of this proposition. Consider the second case. As B = Γ>3 ∼
= An−6 ,
Γ>2 ∼
= A10 × hτ i where τ is an even
= A10 or Γ<5 ∼
= An−5 . In addition Γ<5 ∼
involution. Thus Γ>2 ∩ Γ<5 is either A5 or A5 × hτ i. But hρ3 , ρ4 i ∼
= D5 × hτ i,
contradicting the intersection condition.

Proposition 5.32. Let n ≥ 12. If A is trivial or A has the permutation representation graph (2) or (3) of Table 2 and B is an alternating group, then r ≤ n−1
2 .
Proof. Assume for contradiction that r > n−1
2 . By the dual of Proposition 5.25 we
may consider, up to duality, that when A is trivial, i = 0. By Propositions 5.29,
5.30 and 5.31 we may assume that Γ>i+1 is intransitive on {1, . . . , n} \ Fix(Γ>i+1 ),
but Γ>i does not have a 2-fracture graph. In addition, by Propositions 5.17 and
5.28 we can consider that if Γj has exactly two orbits and a single j-edge connecting
them, then the group orbits are either C = Γr−1 ∼
= An−1 and D trivial, or C =
Γ<j ∼
= A5 , D having the permutation representation graph
= An−6 and D = Γ>j ∼
dual of (2) or the graph (3).
Consider the group C. Let rC be the rank of C and nC the degree of C. Thanks
to the intersection condition Γi+1,...,j−1 is the alternating group. In addition C>i+1
is intransitive on the second Ci -orbit (the orbit containing the vertex b), for otherwise Γ>i+1 is transitive on {1, . . . , n} \ Fix(Γ>i+1 ). Thus C satisfies the condition
of Proposition 5.31. Accordantly with that proposition there are three possibilities.
The first one is rC ≤ nC2−3 which implies r ≤ n−1
2 , a contradiction. The second
one gives the following permutation representation graph for C.



0



1



2

0

1





3

0 1
2





0 1
3



 rC −1 

0 1



0 1

rC −1



But then, it is not possible to attach the permutation representation graph of D by
a single j-edge, a contradiction. The last establishes that there exists x > i such
with X := {1, . . . , n} \ Fix(Γ>x ). On the other hand the dual
that x ≤ n−|X|−1
2
of Proposition 5.31 gives the same three possibilities for B and, as before, one of
them gives r ≤ n−1
2 , and the second gives a contradiction. Thus it may be assumed

HIGHEST RANK OF A POLYTOPE FOR An

45

that there exists y > i such that r − y ≤ n−|Y2 |−1 with X := {1, . . . , n} \ Fix(Γ<y ).
If Γ{x+1,...,y−1} is intransitive on X ∩ Y = {1, . . . , n} \ Fix(Γ{x+1,...,y−1} ) then it
has a disconnected 2-fracture graph. Hence y − 1 − x ≤ |X∩Y2 |−1 . Otherwise, as
Γ{x+1,...,y−1} has a 2-fracture graph it cannot be one of the graphs (2) or (3) of
Table 2. Thus by Propositions 5.11 and 5.13, we also have y − 1 − x ≤ |X∩Y2 |−1 .

As n = |X| + |Y | − |X ∩ Y |, we get r ≤ n−1
2 , a contradiction.
The cases we have covered, that some Γi is primitive, or transitive imprimitive,
or all Γi are intransitive and 2-fracture graphs do or do not exist, exhaust all
possibilities; so Theorem 1.1 is proved.
6. Acknowledgements
This research was supported by a Marsden grant (UOA1218) of the Royal Society of New Zealand, and by the Portuguese Foundation for Science and Technology (FCT-Fundação para a Ciência e a Tecnologia), through CIDMA - Center
for Research and Development in Mathematics and Applications, within project
UID/MAT/04106/2013.
References
1. L. Babai. On the order of uniprimitive permutation groups. Ann. Math. (2) 113:553–558, 1981.
2. W. Bosma, J. J. Cannon and C. Playoust. The Magma Algebra System. I. The User Language.
J. Symbolic Comput., 24(3-4):235–265, 1997. Computational Algebra and Number Theory
(London, 1993).
3. P. A. Brooksbank and D. Leemans. Polytopes of large rank for PSL(4, q). J. Algebra 452:390–
400, 2016.
4. P. A. Brooksbank and D. A. Vicinsky. Three-dimensional classical groups acting on polytopes.
Discrete Comput. Geom., 44(3):654–659, 2010.
5. F. Buekenhout and D. Leemans. On the list of finite primitive permutation groups of degree
≤ 50. J. Symbolic Comput. 22:215–225, 1996.
6. P. J. Cameron and P. Cara. Independent generating sets and geometries for symmetric groups.
J. Algebra 258(2):641–650, 2002.
7. P. J. Cameron, M. E. Fernandes, D. Leemans and M. Mixer. String C-groups as transitive
subgroups of Sn . J. Algebra 447:468–478, 2016.
8. M. Conder. The smallest regular polytopes of given rank. Adv. Math. 236:92–110, 2013.
9. T. Connor, J. De Saedeleer and D. Leemans. Almost simple groups with socle PSL(2, q) acting
on abstract regular polytopes. J. Algebra 423:550–558, 2015.
10. T. Connor, D. Leemans, and M. Mixer. Abstract regular polytopes for the O’Nan group. Int.
J. Alg. Comput. 24(1):59–68, 2014.
11. M. E. Fernandes and D. Leemans, Polytopes of high rank for the symmetric groups, Adv.
Math. 228:3207–3222, 2011.
12. M. E. Fernandes, D. Leemans and M. Mixer. Corrigendum to “Polytopes of high rank for the
symmetric groups”. Adv. Math., 238:506–508, 2013.
13. M. E. Fernandes, D. Leemans, and M. Mixer. Polytopes of high rank for the alternating groups.
J. Combin. Theory Ser. A, 119:42–56, 2012.
14. M. E. Fernandes, D. Leemans, and M. Mixer. All alternating groups An with n ≥ 12 have
⌋. SIAM J. Discrete Math., 26(2):482–498, 2012.
polytopes of rank ⌊ n−1
2
15. M. E. Fernandes, D. Leemans and M. Mixer. An extension of the classification of high rank
regular polytopes. Preprint, 2015. arXiv:1509.01032
16. A. Maróti, On the orders of primitive groups. J. Algebra 258:631–640, 2002.
17. L. Pyber. On the orders of doubly transitive permutation groups, elementary estimates. J.
Combin. Theory Ser. A 62:361–366, 1993.
18. M. I. Hartley. An atlas of small regular abstract polytopes. Period. Math. Hungar., 53(12):149–156, 2006.

46

P. J. CAMERON, M. E. FERNANDES, D. LEEMANS, AND M. MIXER

19. M. I. Hartley and A. Hulpke. Polytopes derived from sporadic simple groups. Contrib. Discrete
Math., 5(2):106–118, 2010.
20. D. Leemans. Almost simple groups of Suzuki type acting on polytopes. Proc. Amer. Math.
Soc., 134(12):3649–3651 (electronic), 2006.
21. D. Leemans and M. Mixer. Algorithms for classifying regular polytopes with a fixed automorphism group. Contr. Discrete Math., 7(2):105–118, 2012.
22. D. Leemans and E. Schulte. Groups of type L2 (q) acting on polytopes. Adv. Geom., 7(4):529–
539, 2007.
23. D. Leemans and E. Schulte. Polytopes with groups of type PGL2 (q). Ars Math. Contemp.,
2(2):163–171, 2009.
24. D. Leemans, E. Schulte and H. Van Maldeghem. Groups of Ree type in characteristic 3 acting
on polytopes Preprint, 2015. arXiv:1501.01125
25. D. Leemans and L. Vauthier. An atlas of abstract regular polytopes for small groups. Aequationes Math., 72(3):313–320, 2006.
26. P. McMullen and E. Schulte. Abstract regular polytopes, volume 92 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2002.
27. J. Whiston. Maximal independent generating sets of the symmetric group, J. Algebra
232(1):255–268, 2000.
Peter J. Cameron, School of Mathematics and Statistics, University of St Andrews,
North Haugh, St Andrews, Fife KY16 9SS, UK
E-mail address: pjc20@st-andrews.ac.uk
Maria Elisa Fernandes, Center for Research and Development in Mathematics and
Applications, Department of Mathematics, University of Aveiro, Portugal
E-mail address: maria.elisa@ua.pt
Dimitri Leemans, Department of Mathematics, University of Auckland, Private Bag
92019, Auckland 1142, New Zealand
E-mail address: d.leemans@auckland.ac.nz
Mark Mixer, Department of Applied Mathematics, Wentworth Institute of Technology, Boston, MA 02115, USA
E-mail address: mixerm@wit.edu

