Manuel Kauers Hagenberg, May 6, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 8

Exercise 1 Let X be a G-set and G_{Y} be the set stabilizer of Y ⊆ X. Prove G_{Y} ≤ G.

G_{Y} is clearly a semigroup. By 1_{G}(x) = x (x ∈ X ⊇ Y) we have 1_{G} ∈ G_{Y}, so G_{Y} is a monoid. Finally, if g ∈ G_{Y}, then all y ∈ Y satisfy gy = y, so y = g^{−1}y for all y ∈ Y, so g^{−1} ∈ G_{Y}. Therefore, G_{Y} is a group.

Exercise 2 Let G be a finite group and H ≤ G. Show that |G/H| = |G|/|H|.

G/H is a partition, [1_{G}] = H, and every equivalence class has the same number of elements. For the last claim, observe that x ↦ gx is a bijection between H and gH.

Exercise 3 What is the symmetry group H of the corners of a square? What is the symmetry group H′ of the edges of a square?

Consider the following square:

[figure: 1; 2; 3; 4; A; B; C; D]

We find the following symmetry groups by inspection:

H = {id, (1 2)(3 4), (1 4) (2 3), (1 3)(2 4), (1 2 3 4), (1 4 3 2)}
H′ = {id, (A C), (B D), (A D)(B C), (A B C D), (A C)(B D), (A D C B)}.

Observe that H and H′ cannot be isomorphic, because they do not have the same number of elements.