Page 94 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 94
3.3 Finite simple groups
Proposition 3.3.1 Any transitive action of a group G on a set X is equivalent to the action
of G on H \G , where H = stabG (x ) for some x ∈ X . Furthermore, the actions of G on H \G
and K \G are equivalent if and only if H and K are conjugate.
PROOF. Fix x ∈ X and denote H = stabG (x ). Since the action is transitive, is straightfor-
ward to show there is an obvious bijection between X and the set of subsets O(x , y ) =
{g ∈ G | x g = y } of G . Note that O(x , y ) = H g for any g ∈ O(x , y ). It is now easy that the
map y → O(x , y ) is an equivalence between the action of G on X , and the action of G on
H \G . The second part is left as an exercise.
Suppose G acts transitively on a set X with |X | > 1. A G -congruence on X is an equiva-
lence relation ≡ on X that is compatible with the action, i.e., if x ≡ y , then x g ≡ y g for all
g ∈ G . An equivalence class of a G -congruence is called a block. There are two trivial G -
congruences on X , namely, the equality x ≡ y ⇔ x = y , and the universal relation x ≡ y
for all x , y ∈ X . The action is called imprimitive if there is a non-trivial G -congruence on
X , and primitive otherwise.
Examples of primitive actions can be obtained as follows. We say that an action of
G on X is doubly transitive if for any two ordered pairs (x1, x2) and (y1, y2) of distinct
elements of X there exists g ∈ G such that x1 g = y1 and x2 g = y2.
Proposition 3.3.2 A doubly transitive action is primitive.
We leave the proof as an exercise. The following result provides a useful characteri-
zation of blocks:
Proposition 3.3.3 Let G act transitively on X and let B be a non-empty subset of X . Then
B is a block if and only if, for all g ∈ G , either B g = B or B g ∩ B = .
PROOF. If B is a block then B g is also a block and the claim follows by the fact that differ-
ent equivalence classes are disjoint.
Conversely, let B be a non-empty subset of X such that, for all g ∈ G , either B g = B
or B g ∩ B = . Since the action is transitive, all different B g form a partition of X , which
is the set of equivalence classes of a congruence.
Proposition 3.3.4 Let H be a proper subgroup of G . Then the action of G on H \G is prim-
itive if and only if H is a maximal subgroup of G .
PROOF. Suppose that G acts primitively on H \G and assume that H < K < G . Let B be the
set of all cosets of H which are contained in K . By Proposition 3.3.3, B is a block which
neither a singleton nor the whole H \G , a contradiction.
Proposition 3.3.1 Any transitive action of a group G on a set X is equivalent to the action
of G on H \G , where H = stabG (x ) for some x ∈ X . Furthermore, the actions of G on H \G
and K \G are equivalent if and only if H and K are conjugate.
PROOF. Fix x ∈ X and denote H = stabG (x ). Since the action is transitive, is straightfor-
ward to show there is an obvious bijection between X and the set of subsets O(x , y ) =
{g ∈ G | x g = y } of G . Note that O(x , y ) = H g for any g ∈ O(x , y ). It is now easy that the
map y → O(x , y ) is an equivalence between the action of G on X , and the action of G on
H \G . The second part is left as an exercise.
Suppose G acts transitively on a set X with |X | > 1. A G -congruence on X is an equiva-
lence relation ≡ on X that is compatible with the action, i.e., if x ≡ y , then x g ≡ y g for all
g ∈ G . An equivalence class of a G -congruence is called a block. There are two trivial G -
congruences on X , namely, the equality x ≡ y ⇔ x = y , and the universal relation x ≡ y
for all x , y ∈ X . The action is called imprimitive if there is a non-trivial G -congruence on
X , and primitive otherwise.
Examples of primitive actions can be obtained as follows. We say that an action of
G on X is doubly transitive if for any two ordered pairs (x1, x2) and (y1, y2) of distinct
elements of X there exists g ∈ G such that x1 g = y1 and x2 g = y2.
Proposition 3.3.2 A doubly transitive action is primitive.
We leave the proof as an exercise. The following result provides a useful characteri-
zation of blocks:
Proposition 3.3.3 Let G act transitively on X and let B be a non-empty subset of X . Then
B is a block if and only if, for all g ∈ G , either B g = B or B g ∩ B = .
PROOF. If B is a block then B g is also a block and the claim follows by the fact that differ-
ent equivalence classes are disjoint.
Conversely, let B be a non-empty subset of X such that, for all g ∈ G , either B g = B
or B g ∩ B = . Since the action is transitive, all different B g form a partition of X , which
is the set of equivalence classes of a congruence.
Proposition 3.3.4 Let H be a proper subgroup of G . Then the action of G on H \G is prim-
itive if and only if H is a maximal subgroup of G .
PROOF. Suppose that G acts primitively on H \G and assume that H < K < G . Let B be the
set of all cosets of H which are contained in K . By Proposition 3.3.3, B is a block which
neither a singleton nor the whole H \G , a contradiction.
