Exercise 20, § 7

We preserve the notation of the preceding exercise. Let H be a subgroup of G.

(a) Let $R_H$ be the set of S-connected subsets T of G such that $hT \cap T = \varnothing$ if $h \in H, h \neq e$. Show that $R_H$ is inductive for the relation of inclusion.

(b) Let Y be a maximal element of $R_H$. Show that $G = \bigcup_{h \in H} hY$, in other words Y is a system of representatives of the right cosets modulo H. (If $G' = \bigcup hY$ is distinct from G, show that there exist $x \in G'$ and $y \in Y$ which are S-neighbours and deduce that $Y \cup \{x\}$ belongs to $R_H$.)

(c) Let $S_H$ be the set of elements $h \in H$ such that Y and $hY$ are neighbours. It is a symmetric subset of H. Show that an element $h \in H$ belongs to $S_H$ if and only if $h \neq e$ and there exist $y, y' \in Y, s \in S$ with $ys = hy'$. Show that $S_H$ generates H. (If $H'$ is the subgroup of H generated by $S_H$, prove that $\bigcup_{h \in H'} hY$ is a connected S-component of G.) Obtain this result by means of Exercise 14 of § 4.

(d) Let $X_H$ be a subset of $S_H$ such that $S_H$ is the disjoint union of $X_H$ and $X_H^{-1}$ (show that such a subset exists).

Show that $X_H$ is a basic family for H and in particular that H is a free group ("Nielsen-Schreier Theorem"). (Apply the criterion of Exercise 18(c) to H together with $S_H$, noting that two elements $h, h'$ of H are $S_H$-neighbours if and only if $hY$ and $h'Y$ are neighbouring subsets of G. Use Exercise 19(d) to prove that $S_H$ satisfies condition (ii) in Exercise 18(c).)

(e) Let $d = (G:H) = \mathrm{Card}(Y)$. Suppose $d$ is finite. Show that:

(Let T be a non-empty S-connected finite subset of G and T' (resp. T'') the set of ordered pairs of S-neighbouring elements whose first element (resp. both of whose elements) belongs (resp. belong) to T. $\mathrm{Card}(T') = 2\mathrm{Card}(X)\mathrm{Card}(T)$ and it should be shown by induction on $\mathrm{Card}(T)$ that

Apply the result to $T = Y$, noting that $S_H$ is equipotent to $T' - T''$.)