Manuel Kauers Hagenberg, May 19, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 10

Exercise 1 Prove the following variant of the Cauchy-Frobenius Lemma: Let X be a finite G-set, R a commutative ring such that ℚ ⊆ R, and w: X → R be a constant on the G-orbits of X, i.e., w(gx) = w(g′x) for all x ∈ X, g, g′ ∈ G. Then for any set T being a complete set of representatives of G \\ M we have

∑_{t∈T} w(t) = \frac{1}{|G|} ∑_{g∈G} ∑_{x∈X_{g}} w(x).

By [A(x)] denote the indicator function that evaluates to 1 if A(x) is true and to 0 otherwise. The we can reason:

∑_{g∈G} ∑_{x∈X_{g}} w(x) = ∑_{g∈G} ∑_{x∈X}[x ∈ X_{g}]w(x) = ∑_{x∈X} ∑_{g∈G}[x ∈ X_{g}]w(x)

= ∑_{x∈X} w(x)|G_{x}| = ∑_{x∈X} w(x)\frac{|G|}{|G(x)|} = |G| ∑_{t∈T} ∑_{x∈G(t)} w(x)\frac{1}{|G(x)|}

= |G| ∑_{t∈T} w(t) \underbrace{∑_{x∈G(t)} \frac{1}{|G(t)|}}_{=1} .

Exercise 2 Let G be a group, H ≤ G. Show that

H × G → G, (h, g) ↦ hg := h ∘ g ∘ h^{−1}

defines a group action of H on G.

First, 1g = 1 ∘ g ∘ 1^{−1} = g for all g ∈ G. Secondly, for all h_{1}, h_{2} ∈ H and g ∈ G we have

h_{1}h_{2}g = h_{1}(h_{2} ∘ g ∘ h_{2}^{−1}) = h_{1} ∘ h_{2} ∘ g ∘ h_{2}^{−1} ∘ h_{1}^{−1} = (h_{1} ∘ h_{2}) ∘ g ∘ (h_{1} ∘ h_{2})^{−1}
= (h_{1} ∘ h_{2})g.

Exercise 3 Prove the following variant of the Cauchy-Frobenius Lemma: Let X be a G-set, H ≤ G and T_{G} be a complete set of of representatives of the conjugacy classes of G. Then

|H \\ X| = \frac{1}{|H|} ∑_{g∈T_{G}} |C^{G}(g) ∩ H| · |X_{g}|.

By |X_{g}| = |X_{h∘g∘h^{−1}}| we can collaps the sum to

∑_{g∈G} |X_{g}| = ∑_{g∈T_{G}} |C^{G}(g)| · |X_{g}|.

Considering only elements of H, this argument gives

∑_{h∈H} |X_{h}| = ∑_{g∈T_{G}} |C^{G}(g) ∩ H| · |X_{g}|.

The rest follows by applying the standard Cauchy-Frobenius Lemma to H and X.