Results 1 to 4 of 4

Math Help - Graph Automorphisms

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    3

    Graph Automorphisms

    EDIT: I think I got it now. (see 4th post)

    Hello. I recently had an Algebra exam that had a few questions about graph automorphisms. I'm not too familiar with graphs (a little bit familiar with permutations, groups, and morphisms though) so I was hoping someone could help me out with these questions and/or maybe lead me to any online resources about the subject since my textbook doesn't say much about it.

    1) Let T be the graph on 4 vertices with edges {1,2} and {3,4} (union of two disjoint edges). Make a list of all elements in the automorphism group of T

    This one seems easiest, so if someone could explain how to go about this maybe I would understand the concept a bit better and try figuring out the other two.

    2) Let T_n be the union of n disjoint edges (on 2n vertices) and G_n = Aut(T_n). Determine the order |G_n|

    I think the answer to this one was n!*2^n but I'm not sure how to get at that.

    3) (Follow up to 2) Let G=G_3 in the preceding problem. Describe all the elements of order 3 in G_3. How many are there?

    Again on this one I know the answer is 8 elements of order 3, but have no idea how to find that. The elements are listed as permutations and I know the elements of order three are products of disjoint 3 cycles, but I don't know how to find them.

    I'd greatly appreciate any help, since I'm not really familiar with graphs at all.
    Last edited by moocow; March 29th 2010 at 01:59 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by moocow View Post
    Hello. I recently had an Algebra exam that had a few questions about graph automorphisms. I'm not too familiar with graphs (a little bit familiar with permutations, groups, and morphisms though) so I was hoping someone could help me out with these questions and/or maybe lead me to any online resources about the subject since my textbook doesn't say much about it.

    1) Let T be the graph on 4 vertices with edges {1,2} and {3,4} (union of two disjoint edges). Make a list of all elements in the automorphism group of T

    This one seems easiest, so if someone could explain how to go about this maybe I would understand the concept a bit better and try figuring out the other two.

    2) Let T_n be the union of n disjoint edges (on 2n vertices) and G_n = Aut(T_n). Determine the order |G_n|

    I think the answer to this one was n!*2^n but I'm not sure how to get at that.

    3) (Follow up to 2) Let G=G_3 in the preceding problem. Describe all the elements of order 3 in G_3. How many are there?

    Again on this one I know the answer is 8 elements of order 3, but have no idea how to find that. The elements are listed as permutations and I know the elements of order three are products of disjoint 3 cycles, but I don't know how to find them.

    I'd greatly appreciate any help, since I'm not really familiar with graphs at all.
    What is a graph automorphism?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    3
    Quote Originally Posted by Drexel28 View Post
    What is a graph automorphism?
    This is what I have from my notes:
    G = Aut(T) = {a ∈ S_v, a(m) ∈ E ∀ m ∈ E}

    Where a is a permutation, V is the set of vertices, and E is the set of edges.

    edit: As an example we considered a square (union of 4 edges), which I thought was a bit easier to understand since you could just look at the rotation and reflection symmetries. I just can't really visualize a similar way to list the elements for a graph with disjoint edges.
    Last edited by moocow; March 29th 2010 at 09:15 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2010
    Posts
    3
    Well, after staring at the problems for quite some time today I think I've got them figured out. Thanks for anybody who took the time to look at this.

    The key thing is that Aut(T) maps edges to edges, so any two particular vertices have to get mapped to the same edge (paired vertices can't be separated in the mapping, they both have to go to the same edge if they started on the same edge). I found it helped a lot to actually draw some of this stuff out on paper, but if anyone is interested here is what I came up with for solutions:

    1) The elements (permutations) are: (1 2), (1 2)(3 4), (1 3)(2 4), (1 3 2 4), (1 4)(2 3), (1 4 2 3), and (3 4).

    2) Let the set of edges E = { e_1, e_2, ... , e_n} and the set of vertices V = { 1, 2, 3, ..., 2n-1, 2n}, where e_1={1,2}, e_2 = {3,4}, etc. Then we have n choices on where to put e_1, n-1 choices on where to place e_2,...,2 choices for e_n-1, and 1 choice for e_n. Also, for each edge we have 2 choices on how to arrange the two vertices. Thus |Aut(T_n)|=n!*2^n.

    3) Let the graph consist of 3 edges: e_1={1,2}, e_2={3,4}, and e_3={5,6}. The elements (permutations) of of order 3 are products of disjoint 3 cycles. Therefore, since vertices have to "stick together", we can't map 1 to 2 because then we'd have to map 2 to 1 and we'd have a 2-cycle (1 2) in the permutation.

    Starting with 1, we can map it to any of 3, 4, 5, or 6. Say we map it to 3 - then we know 2 has to map to 4 since 1 & 2 have to stay on the same edge. We also can't map 3 back to 1 (then it would be a 2 cycle) or 2 (then it would be a 4 cycle: (1 3 2 4)). Thus we can map 3 to either 5 or 6. If we map 3 to 5 then for it to be a 3 cycle, 5 goes back to 1. So we have a 3 cycle (1 3 5) - then we map 2 to the same edge as 1, since 1 is mapped to 3 we map 2 to 4. 4 has to go to the same edge as 3 (which is mapped to 5) so we map 4 to 6. Finally, we check that 6 maps back to 2 to complete the 3 cycle, which indeed it does (since 5 was mapped to 1). Therefore we have an element (1 3 5)(2 4 6).

    Repeating the same line of reasoning got me in total 8 elements of order 3: (1 3 5)(2 4 6), (1 3 6)(2 4 5), (1 4 5)(2 3 6), (1 4 6)(2 3 5), (1 5 3)(2 6 4), (1 5 4)(2 6 3), (1 6 3)(2 5 4), (1 6 4)(2 5 3). Again, this is MUCH easier to see if you actually draw out the graph.

    If anybody has any questions about my reasoning, or sees anything wrong feel free to let me know. Otherwise I think I understand it now. Thanks again for anybody who looked at it. Cheers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Automorphisms
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 29th 2011, 04:17 PM
  2. Automorphisms of R/Q
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 23rd 2009, 06:10 PM
  3. Automorphisms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 11th 2009, 10:14 AM
  4. Automorphisms
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 22nd 2008, 05:05 PM
  5. Automorphisms of Q
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 10th 2008, 09:03 PM

Search Tags


/mathhelpforum @mathhelpforum