M417 Homework 6 Spring 2004
Instructions: Solutions are due Fri., March 12.
1. A digraph (i.e., directed graph) is a set of vertices, some of which can be connected by an arrow (i.e., a directed edge). For example, we can associate to each group G its subgroup digraph, in which each subgroup H of G is represented by a vertex vH, and there is an arrow from a vertex vH to a vertex vH' exactly when H' properly contains H. A directed path (of length r) in a digraph is a sequence v0,..., vr of vertices such that for each 1 <= i <= r there is an arrow from vi-1 to vi.
Show that every directed path in the subgroup digraph of a cyclic group of order N has length at most log2N.

2. Let g and x be in Sn. Assume that x = (a1 ... ar) is an r-cycle. Show that gxg-1 = (g(a1) ... g(ar)).

3. Find the centralizer of (1234) in S4. [Hint: Apply (2).]

4. Let n and N be positive integers.
• (a) If f: Zn -> ZN is a homomorphism of groups and m = f(1), show that N divides mn, and that f(x) = mx mod N, for all x in Zn.
• (b) Conversely, if m is a positive integer such that N divides mn, show that f(x)= mx mod N defines a homomorphism f: Zn -> ZN.

5. Let f: G -> H be a homomorphism of groups. If G is finite, show that |f(G)||ker f|=|G|.