MATH 6342 - Advanced Enumeration: Definitions of A Group
MATH 6342 - Advanced Enumeration: Definitions of A Group
MATH 6342 - Advanced Enumeration: Definitions of A Group
Definitions of a group
The definition of a group has had an historical path going from that has changed
a lot through the years. We will show some equivalent definitions of this:
If we want to list the possible symmetries of this object (X, S), (this is the
set of vertices and edges, together with in an structure of a graph) note the
following:
1
to be Sym3 × Sym2 , this means, each symmetry corresponds to a com-
bination of both, a permutation on the leftmost edges and a reflection
on an horizontal axis.
1. A permutation g on X is an automorphism if gS = S.
For example, if we permute the rightmost vertices of Figure 1 but not
the rest of them, this will not preserve the initial graph structure. Hence
that would not be an automorphism.
2. The automorphism group of (X, S) is the set Aut(X, S) of all automor-
phisms of (X, S).
3. A subset G of the symmetries of X is an automorphism group if G =
Aut(X, S) for some structure S on X. This was the first definition of a
group for us.
And our second definition is given by this three properties. We say that a
set G is a permutation group on X if G satisfies (P1), (P2) and (P3).
Is clear, due to the definition, that every automorphism group is a permuta-
tion group. The other direction is given by the following:
2
Theorem 1 (Exercise 14.8.1). Every permutation group is the automorphism
group of some object.
gg −1 = g −1 g = e,
3
Theorem 2 (Cayley’s Theorem). Every abstract group is isomorphic to a
permutation group.
ρg x = g ◦ x,
ρh e = h ◦ e = h ρg e = g ◦ e = g,
ρg ρh x = (g ◦ h) ◦ x = g ◦ (h ◦ x) = ρg◦h x,
Now is clear that our three definitions are equivalent, but moreover, Frucht showed
that every abstract group is the automorphism group of a graph, this will be
approached further.
From now and on, we abbreviate ‘abstract group’ to ‘group’ and g ◦ h to gh. A
group will be defined by the axioms (A1)-(A3), and note that Cayley’s theorem
imply that it makes sense to study groups as groups of permutations, but note
that the definition of ‘permutation group’ changes then, now we will take it as a
set of permutations which is equipped with the composition of these, and it makes
a group.
4
Now we will define the action of a group on a set X a map θ : G → Sym(X)
that satisfies the following:
1. θ(gh) = (θg)(θh),
2. θ(1) = (1),
3. θg −1 = (θg)−1 .
Here we use the same notation for a group operation and permutations, more-
over, θ is an homomorphism from G into Sym(X).
Is also interesting to note that a group can have many different actions, so we need
to find a way to tell when two actions are the same, or equivalent. For this, let’s
consider two actions θ and ϕ from G into sets X and Y respectively. We will say
that these actions are equivalent if there exists a bijection f : X → Y such that,
for any x ∈ X and g ∈ G:
a b
This maps show that both actions are equivalent, for example if a permutation
g ∈ G send a to b then it also carries {b, c} to {c, a}.
5
Examples of groups
Lets consider the following additional definitions:
• A subset H ⊂ G is a subgroup if H is closed under the operation of G.
A finite group (group with finite order) that can be generated by only one
element is called cyclic group and denoted Cn . The group Cn can be regarded in
many different ways, for example:
• The additive group of congruence classes modulo n.
• The multiplicative group of all nth roots of the unit in C, i.e. {e2kπi/n : k =
0, . . . , n − 1}.
1
n 2
3
···
10 4
9 5
8 6
7
Another example of groups, that is closely related to cyclic groups, are dihedral
groups, D2n of order 2n. We can think on the dihedral group for n > 2 to be
either:
6
• The automorphism group of the undirected graph of figure 2.
• The group of symmetries of a regular n-gon.
Is easy to note that Cn is contained as a subgroup of D2n (as the rotations of
the n-gon). The remaining elements are reflections of the n-gon through n axis of
symmetry.
There are several examples of other groups, but something interesting about
we can construct new group using smaller ones. We are going to describe 3 con-
structions.
Direct product: Let’s consider two groups G and H, we define the new group
G × H, for elements being pairs (g, h) such that g ∈ G and h ∈ H. and
operation defined as
(g1 , h1 )(g2 , h2 ) = (g1 g2 , h1 h2 ).
Taking all these in consideration, is easy to see that the group S3 × C2 is the
group of symmetries of the graph on Figure 1.
Wreath product The abstract definition of the wreath product between two
groups G, H, denoted as G ≀ H need more work, but we can also give a
description as a permutation group acting on X × Y , moreover, if Y =
{y1 , . . . , yn }, we can think on X × Y as n copies of X, denoted as Xi =
X × {yi }. And we will define two permutation groups:
7
u
• The top group T defined as the action on the second coordinate, i.e.
Note that the action on the second component shifts the Xi . And the wreath
product G ≀ H is the group generated by T and B i.e. consists in all the prod-
uct of elements t ∈ T and b ∈ B.
8
front–back pair X2 (containing v); and the left–right pair X3 (containing
w). Using reflections one can exchange the two vertices in the top–bottom,
front–back, or left–right pair, leaving the other four vertices fixed. Is very
clear that this reflection commute, so for the symmetries of Γ we know that
Moreover, the action of a permutation on the set of vertices given by this sub-
group of Sym(Γ) is exactly the natural action, as it fixes two pairs of vertices.
Now, we want permute the each one of 8 faces of the octahedron to the
face delimited by the vertices {u, v, w}, for this we can do it by rotating the
octahedron over the middle plan or turning it upside down, for a total of 6
possible permutations, and as those permutations doesn’t commute we know
that the group that acts on the faces by permutations is exactly S3 < Sym(Γ).
Now, the action of S3 on the vertices, is exactly shifting the sets of pairs of
vertices, moreover, this is the product action. This implies that S 2 is the
bottom group and S3 is the top group, i.e. S2 ≀ S3 < Sym(Γ).
9
Orbits and Transitivity
The main interests of groups from the algebraic perspective are the groups it-
self, but from the point of view of combinatorics, its more interesting to see the
structures X on which a group G acts on; for example what structures on X are
invariant by the action of G.
For this, consider the following relation. Let G acts on X, we can define a
relation ≡ on X given by:
For example let’s consider the action of D4 into a square, we know that D4
have 8 elements, denoted as {e, a, b, c, r, s, t, u}. If we take a point x in the square,
Figure 4 shows the action of all elements into x.
r
s
e·x=x r·x
a·x b·x
t a
c
a·x b u·x
u u·x t·x
Figure 4: Action of D4
10
actions, we have an action of G on each separate orbit that is, itself, transitive, as
for example thinking the action of D4 in x instead of the whole square. Moreover
if we want to describe all ways into a group can act in a set X it is sufficient to
describe transitive actions.
Now, if we want to describe the transitive actions, consider the following. Let
H be a subgroup, a left coset of H in G is the set gH = {gh : h ∈ H} for a fixed
g ∈ G. A classical, and useful, result is the following:
Theorem 4 (Lagrange’s Theorem). The H be a subgroup of G, if |H| = n and
|G| = m then n|m.
It is also important to remark the following:
Proposition 5 (Exercise 14.8.7). The number of left cosets and right cosets is the
same.
Proof. If ah ∈ aH, then (ah)−1 = h−1 a−1 ∈ Ha−1 . Now gH = g ′ H ⇐⇒ g −1 g ′ ∈
H. Since H is a subgroup, (g −1 g ′ )−1 = g ′−1 g ∈ H.
This implies that g ′−1 (g −1 )−1 ∈ H, which happens if and only if Hg −1 = Hg ′−1 .
Thus if ϕ(gH) = Hg −1 , we see that for any coset g ′ H = gH, that:
ϕ(g ′ H) = Hg ′−1 = Hg −1 = ϕ(gH), that is, ϕ is is independent of the repre-
sentative element. So ϕ is a well-defined function on left cosets. And clearly is a
bijection, so the result follows.
Now, we want to fact when two cosets are equivalent, for this, note that, if
g ′ ∈ gH, then g ′ = gh0 for some h0 ∈ H; then any element g ′ h ∈ g ′ H lies in gh
because g ′ h = g (h0 h) and h0 h ∈ H. Similarly, every element of g ′ H is in gH.
Then, if gH and g ′ H are not disjoint, g ′ H = gH.
Lagrange’s theorem tells us that the order of a subgroup divide the order of
the group, and that follows from noticing the number of cosets of H has the same
number of elements of H itself, i.e. the map h → g · h is a bijection from H to
gH. And moreover the number of cosets of H in G is |G|/|H| and this number we
write it as [G : H] and its called the index of H in G.
11
Proof. Let’s suppose that G acts transitively on X, and let x ∈ X, we can define
the set H = {g ∈ G : gx = x}, this is the subset of G that fixes x, and its known
as the stabilizer of x and is written as Gx . Note that Gx is a subgroup of G:
• The identity fixes x for any x ∈ X.
• If g ∈ Gx by definition gx = x hence g −1 gx = g −1 x and then x = g −1 x and
therefore g −1 ∈ Gx .
• If h, g ∈ Gx then (gh)x = g(hx) = gx = x and therefore gh ∈ Gx .
Now, there is a bijection between X and (G : H), defined as, let y ∈ X we can
define the subset S(y) = {g ∈ G : gx = y}, and as the action is transitive, we
know that this set is non-empty, and moreover, {S(y) : y ∈ Y } is a partition of X
and hence we can identify each partition with the partition in cosets given by H.
So this bijection define an equivalence in the actions of G over X, i.e. if gy = z
then g(S(y)) = g(S(z)), and this, by definition is a coset action.
Theorem 7. Two coset actions on (G : H) and (G : K) are equivalent if and only
if the subgroups H and K are conjugated.
Proof. Let’s suppose that H and K are conjugated, this is, there exists an ĝ ∈ G
such that K = gˆ−1 H ĝ, clearly, this implies the equivalence between the cosets
Kg → H ĝg.
For the the other direction let’s suppose that the two coset actions are equiva-
lent. Let’s suppose that the corresponding coset for K is H ĝ, then the stabilizers
of both are equal, the stabilizer of K is K itself, but the one for H ĝ is:
{g ∈ G : H ĝg = H ĝ} = g ∈ G : ĝgĝ −1 ∈ H = ĝ −1 H ĝ,
12
Schreier-Sims algorithm
A common problem is need to find the size of a group G, in this section we will
give an algorithm that can be used for this.
As an example, let’s set G = S3 = {e, (1, 2), (1, 3), (2, 3), (123), (132)} and H
is a subgroup C3 = {e, (123), (132)}. We know that S3 is generated by s1 = (12)
and s2 = (123). We want to find a set of generators for C3 .
Note that C3 only has two cosets, and the coset representatives are t1 = e and
t2 = (1, 2). So:
t1 s1 = (12), so t1 s1 = (12),
t1 s2 = (123), so t1 s2 = e,
t2 s1 = e, so t2 s1 = e,
t2 s2 = (23), so t2 s2 = (12).
13
And:
−1
t1 s1 t1 s1 =e
−1
t1 s2 t1 s2 = (123)
−1
t2 s1 t2 s1 =e
−1
t2 s2 t2 s2 = (123)
As having e in the generator set is irrelevant, C3 is generated by (123).
This is useful calculating group size of big groups like the Rubik’s cube group,
but can be very hard to do it on hand, anyway let’s do a small example to see how
it works.
e · 1 = 1,
x · 1 = 2,
x−1 · 1 = 3,
xy · 1 = 4.
xx−1 = e,
x−1 y = (2, 4, 3).
14
as we get a non-identity element, we stop and adjoint a new base point 2 and add
a z = (2, 4, 3) as a generator, and using S2 = {z} for basepoint 2, note that:
e · 2 = 2,
z · 2 = 4,
z −1 · 2 = 3.
Hence, the orbit of 2 under S2 is {2, 3, 4} and now we want to find the Schreier
generators to the stabilizer G2 , it is easy to verify that all products given by the
Schreier lemma gives the identity and hence we stop the algorithm. And so we
know that the order of the group G is the multiplication of the basic orbit lengths,
i.e. 4 × 3 = 12.
15
Primitivity and multiple transitivity
We have reduced the study of group actions to only the ones that are transitive,
but it can be reduced even more. In general, a relation on X ban be thought as a
set of ordered pairs, i.e. is a subset of X × X.
Proposition 11. The relation R is perserved by G if and only if it is the union
of orbits of G in X 2 .
Proof. As the relation is G-invariant, this by definition is that if (x, y) ∈ R iff
(gx, gy) ∈ R, for any g ∈ G, and this implies that the whole orbit of (x, y) is in R,
hence R is the union of orbits. The other direction is similar.
Consider the following:
• A relation is preserved by G, or G-invariant, if x ∼ y implies that gx ∼ gy
and conversely.
• G acts on the set X × X as:
g(x, y) = (gx, gy).
16
• G acts on the set Y and let G0 be the permutation group on Y induced by
G.
This tells us that G can be constructed out of smaller groups which are both
transitive, and if they are imprimitive, we can recursively continue until we end
up with a collection of primitive subgroups, known as primitive components of G,
which are not necessarily unique, as G may have different congruences.
1. G is (t − 1)-transitive,
2. G is primitive.
Proof. 1. Let’s consider two (t − 1)-tuples, (x1 , . . . , xt−1 ) and (y1 , . . . , yt−1 ), we
can extend them to t-tuples by adding elements that are not in the tuples xt
and yt respectively. As G is t-transitively, there is an g such that gxi = yi
for i = 1, . . . , n. And then we can use the same g for the (t − 1)-tuples.
It is known that Sn acting on {1, . . . , n} is n-transitive for any n and the alter-
nating group An acting on the same set is (n − 2)-transitive for n > 2. And this
implies that Sn is primitive for any n and An is primitive for any n > 2.
Another very interesting fact is that no other finite permutation group can be
more than 5-transitive, as a consequence of the classification of the finite simple
groups.
17
Example
Let’s consider the Petersen Graph:
(1, 2)
(1, 3) (2, 5)
(1, 4) (2, 4)
(2, 3) (1, 5)
It can be proved that the number of automorphisms of this graph is 120. Now,
we have labeled each vertex with a 2-tuple of the set {1, 2, 3, 4, 5}, so, there are
5
2
= 10 possible 2-subsets that are used. Note also that two vertices are adjacent
if and only if their labels are disjoint, hence any permutation of {1, 2, 3, 4, 5} in
the inducted action over these pairs is an automorphism. It follows that, as we
find a group of automorphism isomorphic to S5 on X × X with order 120, so the
full automorphism group is S5 .
Is easy to note that the automorphism group is vertex transitive, but is not 2-
transitive, since no automorphism map two adjacent vertices to two non-adjacent.
However, the orbits of S5 on X 2 are three:
18
Suppose that the relation contains the second orbit (that can be interpretated
as the ordered edges) and not the third one (that can be interpretated as the
ordered non-edges). Since we can find vertices x, y, z such that x ∼ y ∼ z, by
transitivity of the relation x ∼ z but then this imply that the relation include also
the third orbit. A similar argument works if we suppose that the relation include
the third but not the second orbit.
So, either, the relation is the identity, or the whole X 2 , and therefore, the group
is primitive.
19
Cayley Digraphs and Frutch’s Theorem
Let S be a subset of a group G, not containing the identity, we can define the
Cayley digraph of a group with respect to S.
2. Each s ∈ S forms a directed edge with initial vertex vg and terminal ver-
tex vg·s ; Giving each edge a correspondence with right multiplications of the
elements of S.
Note for example, that Figure 2 is exactly the Cayley digraph of Cn with re-
spect to the generating set S = {1}.
Cayley digraphs can change a lot depending on the set S, for example, let’s
consider the group S3 with S1 = {(12), (23)} and S2 = {(12), (123)}. The first one
is illustrated in Figure 6b, and the other in Figure 6a. In those graphs, to avoid
the use of cycles, we will use the double arrows to simplify the graph.
(12) (123)
(12)
e
e (13)
(132) (123)
(23) (132) (23) (13)
(a) S1 = {(12), (23)}. (b) S2 = {(12), (123)}.
20
Proof. 1. If S generates G then every element g ∈ G can be written as the
product of the elements of S, in the Cayley digraph this can be see as a path
from e to g, it follows that ΓG,S is connected, but not necessarily strongly
connected.
The converse is pretty similar, any path from e to g in the underlying graph
translates into a product of elements of S that equals g, it follows that S
generates G.
2. Let (x, sx) an edge, then (ρg x, ρg sx) = (gx, gsx) is also an edge, and the
result follows.
21
References
[1] Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University
Press, 1995.
[2] Jhon Meier, Groups, Graphs and Trees. An Introduction to Geometry of Infinite Groups,
London Mathematical Society, 2008.
22