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.

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