22
$\begingroup$

I am trying to find out the automorphism group of the Petersen graph. My book carries the hint: "Show that the $\tbinom{5}{2}$ pairs from {1, . . . , 5} can be used to label the vertices in such a way that a simple rule determines when there is an edge. To find the full automorphism group, consider the subgroup that fixes a vertex and its three neighbors."

Accordingly the rule is that there is an edge if 2-sets are disjoint. What I am not getting is to how to use the second sentence of the hint to find the automorphism group. Its not at all clear what the order of such a subgroup will be and how such a subgroup will be the requisite automorphism group.

Also I am not really proficient with group action, so if that is involved I would appreciate a detailed explanation.

  • 0
    Hey, I am learning from the same book. What did you think? I have not done any group theory or abstract algebra, but so far, it seems like it would be helpful.2014-09-01
  • 0
    @user170141: I found another proof and have written it here if you are interested: http://notesonmathematics.wordpress.com/2013/10/09/graph-automorphisms/2014-09-02

2 Answers 2

19

Since each vertex is labeled with a subset with two elements of $\{1,2,3,4,5\}$, then any permutation of $\{1,2,3,4,5\}$ is going to induce a permutation of the vertices. Moreover, if $\{a,b\}\cap\{c,d\}=\emptyset$, and $\sigma$ is a permutation of $\{1,2,3,4,5\}$, then $\{\sigma(a),\sigma(b)\}\cap\{\sigma(c),\sigma(d)\} = \emptyset$. That is: this permutation of the vertices sends adjacent vertices to adjacent vertices (and non-adjacent vertices to non-adjacent vertices).

Also, two permutations induce the same permutation of the vertices if and only if they are identical permutations (you should prove this). That means that every element of $S_5$ induces a distinct automorphism of the graph.

Are these all the automorphisms, or are there more? If $\tau$ is any automorphism, then by composing with an appropriate permutation of $\{1,2,3,4,5\}$ you may assume that the map fixes $\{1,2\}$; that means that the vertices adjacent to $\{1,2\}$, $\{3,4\}$, $\{3,5\}$, and $\{4,5\}$, must map to each other. Composing with an appropriate permutation (that fixes $1$ and $2$) you may assume that the permutation also fixes $\{3,4\}$; and composing again by a suitable permutation, you can make it fix also $\{3,5\}$ $\{4,5\}$ (again, you need to prove this). So then you are left with an automorphism that fixes $\{1,2\}$ and its three neighbors. If you can show that this is also given by a permutation of $\{1,2,3,4,5\}$, then you will have shown that every automorphism "comes" from an element of $S_5$ (since composing with suitable automorphism that do give you the identity).

  • 0
    I am having trouble understanding what you mean by the last sentence. Do you mean to say that the automorphism that fixes {1,2} and its three neighbors is the identity automorphism? If so, why? Also, if you mean that the automorphism we are left with is non-identity then I dont see any way to determine it uniquely from a permutation of $S_5$. (Eg both (1) and (12) work upto fixing 12 and its neighbors, that doesnt mean the automorphism we are left with is induced by them though.)2011-05-18
  • 0
    @Shahab: I did not (mean to) say that an identity that fixes $\{1,2\}$ and its three neighbors must be the identity. What I tried to say was that if you take an automorphism $\phi$, and you can find an automorphism $\psi$ that "comes from" a permutation of $\{1,2,3,4,5\}$ and is such that $\psi\circ\phi$ is the identity, then that means that $\phi=\psi^{-1}$, so $\phi$ also "comes from" a permutation. We do this by first composing with a suitable automorphism from $S_5$ so that $\sigma_1\phi$ fixes $\{1,2\}$; then (cont...)2011-05-18
  • 0
    @Shahab: (cont) compose with some other suitable automorphism so that $\sigma_2\sigma_1\phi$ fixes $\{1,2\}$ and $\{3,4\}$; then another one so that $\sigma_3\sigma_2\sigma_1\phi$ fixes $\{1,2\}$ and its three neighbors. And keep doing that until you get a composition that fixes everything. Sorry if that wasn't clear.2011-05-18
  • 0
    @Arturo Magidin: Yes, I had guessed by now thats what you had meant. But now I have a further doubt. It seems to me that we have initially a monomorphism from $S_5$ to Aut(Petersen graph) and we are using that in the last stages. That the map is an injection is clear from your post but why will it be a homomorphism?2011-05-18
  • 1
    @Shahab: We actually started by giving a homomorphism from $S_5$ to the permutation group of the vertices; that this is a homomorphism is, I hope, clear. Then we saw that in fact the permutation of the vertices that we obtain is an automorphism of the Petersen graph (note that the automorphism group of the Petersen graph is a *subgroup* of the group of permutations of the vertices). So the image of $S_5$ inside the group of permutations of the vertices is contained in the automorphism group of the Petersen graph; so we have a homomorphism from $S_5$ to the automorphism group.2011-05-18
  • 0
    Thanks for all the help. Actually, what wasn't clear was precisely that the map from $S_5$ to the permutation group of the vertices was a homomorphism but after giving proper notation etc I managed to prove it too. The rest I have already worked out :)2011-05-18
  • 0
    @Shahab: Oh, I see. Well, glad it's cleared up now. Essentially, we have a natural homomorphism from $S_X$ to $S_{P(X)}$ (the permutations of $X$ to the permutations of the subsets of $X$), and the resulting permutations permute sets of the same size among themselves.2011-05-18
  • 0
    Hi Magidin. I think we are nearly done when we find $\sigma_i,\, i=1,2,3$ s.t. $\sigma_3\sigma_2\sigma_1\phi$ fixes $\{1,2\}$ and its three neighbor, right? Since $\sigma_3\sigma_2\sigma_1\phi$ fixes $\{3,4\},\{4,5\},\{3,5\}$, and hence fix $\{3\},\{4\},\{5\}.$ If $\sigma_3\sigma_2\sigma_1\phi$ fixes $\{1\}$ and $\{2\}$, then it is identity (Since Aut(Petersen)$\le S_{10}$, and $S_{10}$ is faithful). For otherwise, just compose a $(1,2)$. Am I right?2018-04-25
2

Prof. Ravi Vakil has given lecture notes on Complex Algebraic Surfaces, and you can find the proof of your result in the second page.

  • 0
    I think he is looking for the proof sketched on page one.2011-05-18