Symmetric Group

• The Symmetric Group of order is the group whose set is the set of all permutations of elements and whose binary operation is the composition of permutations. It is denoted as .

• A Permutation Group is a group whose set consists of permutations and whose binary operation involves composing two permutations. It is a Subgroup of .

• (Fraleigh 8.16) Cayley’s Theorem: Every group is isomorphic to a permutation group.

  • Intuition: Every element of the group induces a group action on the group which permutes the group elements. A mapping from group elements to permutations of the group elements gives us an isomorphism to a permutation group.

  • We can define two maps. Let be the permutation on the group defined as

    The map defined by is the left regular representation of .

    Similarly, let be the permutation on the group defined as .

    The map defined by is the right regular representation of .

  • We can think of the left and right regular representations as encoding group actions and defining a bijection from a group element to its corresponding group action.

  • The set of left regular representations and right regular representations are equal if and only if is Abelian.

• Let be a set. Then is transitive on if

  such that .

• (Fraleigh e9.29) Every subgroup for , either all permutations in are even or exactly half of them are even.

  • Intuition: Any odd permutation has a corresponding group action which maps the group to itself. In , the evens become odds and the odds become evens but the number of elements must stay the same because the group elements did not change.

Transposition Graph §

• A set of transpositions from can be viewed as the edge set of a graph on vertices, where the transposition corresponds to an edge between and .

• (Godsil 3.10.1) Let be a set of transpositions from . Then is a generating set for if and only if its graph is connected.

  • Proof: Let be the group generated by and the corresponding graph. If then . By induction, if there is a path from to in , then . Thus, if and are in the same components, then .

    Thus, the transpositions of vertices within a component for generate the symmetric group for that component. Also, no transposition maps vertices across components; the components of are the orbits of .

• (Godsil 3.10.2) Let be a set of transpositions from . Then the following are equivalent:

  • is a minimal generating set for [^matroids]

  • The graph of is a tree. Thus, each tree on vertices determines a Cayley graph of

  • The product of the elements of in any order is a cycle of length .

  • Proof: The equivalence of the first and second follows by (Wilson 9.1) and (Godsil 3.10.2).

    The equivalence of the second and third is shown as follows. First, suppose is a tree. The product of all elements of must be a permutation. By (Fraleigh 9.8 ) it can be decomposed as the union of disjoint cycles with each corresponding to an orbit. is a tree therefore it must be connected and have one component. By (Godsil 3.10.2) this happens if and only if only contains one orbit.

    Also if contained a cycle, then it is possible to find which contradicts the assumption that there is only one disjoint cycle. So is acyclic if and only if and only if there are no stabilizers (i.e., the orbit, and by extension the cycle, have length ).

  • We can state this using Matroid Theory. Consider the matroid on the underlying set . can be treated as a basis. Sets of transpositions with fewer than elements as independent sets.

  • has no triangles. Otherwise, this would imply that which is impossible since the product of transpositions is not a transposition.

  • (Godsil e3.5) is bipartite.

    • Proof: The bipartition is between even and odd permutations. The parity only changes by multiplying with a single transposition by (Fraleigh 9.15). Thus, each joins an even and an odd permutation.

• (Godsil 3.10.3) Let be a set of transpositions from and let . Suppose the graph of contains no triangles. If then and have exactly one common neighbor in and exactly two common neighbors otherwise

  • Proof: Let . The neighbors of have the form , . Thus is a common neighbor. Then and any solution to this yields a common neighbor.

    If and commute they have disjoint support. The only solutions are and which are the two common neighbors.

    Otherwise, they have overlapping support. In which case, since the graph has no triangles, there is only one factorization of .The only common neighbor is .

• (Godsil 3.10.4) Let be a minimal generating set of transpositions for . If the graph for is asymmetric, then

  • Proof: Since is a minimal generating set, by (Godsil 3.10.2), the underlying graph is a tree. It contains no cycles. By (Godsil 3.10.3), we can determine which pairs of transpositions in have overlapping support (that is, they are incident). Thus, we can construct the line graph using . Also, determines .

    Any induces a permutation of . The restriction of to is an automorphism of . Thus since is asymmetric. That is

    Now if fixes at least one vertex. We show that the automorphism group is regular by showing that .Argue by contradiction and suppose not. Since is connected, there is an edge incident to one fixed point and one non-fixed point . Thus fixes and moves the adjacent vertex which is impossible since .

    Since the automorphism group is regular (Godsil 3.7.1; Godsil 3.7.2) implies contains a subgroup. isomorphic to . Since the automorphism group is regular, the only such subgroup is the automorphism group itself.

Links §

• A First Course in Abstract Algebra 7th Edition by Fraleigh
• Algebraic Graph Theory by Godsil and Royle