Problem1A in “A course in combinatorics”

Problem 1A: Find all the automorphisms of Petersen Graph.

Solution: We can label the vertices of the graph by 2-subsets in { S=\left\{ 1,2,3,4,5\right\} }, such that any two vertices are adjacent iff the intersection of their labels is empty. Then any permutation of {S} will induce an automorphism of the graph since the adjacency is preserved. Hence there are {5!=120} such automorphisms. The interesting part is how to show that they are actually all the automorphisms of Petersen Graph. In my opinion, the question to determining all the automorphisms for a particular object is not easy in general. However, for Petersen Graph, it is possible, and there are three steps to show this. Suppose the vertices of the graph are {\left\{ v_{1},v_{2},\ldots ,v_{10}\right\} .} First, show that given any two vertices {v_{i},v_{j}}, there exists an automorphism {\sigma _{ij}} mapping {v_{i}} to {v_{j}}. Denote by {A_{1k}} the set of all the automorphisms that map {v_{1}} to {v_{k}.} Show that {\sigma _{1k}A_{11}=A_{1k\text{ }}} for any {k,} so that {|A_{11}|=|A_{1k}|.} So the number of all the automorphisms are {10|A_{11}|.} Second, show that given any permutation of the three neighbors of {v_{1},} there exists an automorphism in {A_{11}} permuting the neighbors in that way. There are {3!=6 } such permutations Denote the corresponding automorphisms by {\sigma _{1},\sigma _{2},\ldots ,\sigma _{6}.} Consider the subgroup of automorphisms that fix {v_{1}} and its three neighbors, denoted by {A_{1.}} It is not hard to show that {|A_{1}|=2.} Show that {A_{11}=\cup _{i=1}^{6}\sigma _{i}A_{1}.} Hence {|A_{11}|=12,} and therefore the number of all the automorphisms is {120.}

Notes: Let {S=\left\{ 1,2,\ldots ,n\right\} ,} and {k} is an integer such that {1<k\leq n/2.} Consider the following graph. Let the vertices be all the {k}-subsets of {S,} and two vertices are adjacent iff they are disjoint. It is called an Kneser Graph {KG_{n,k}.} It is obvious that any permutation of {S} leads to an automorphism of the graph. Are these automorphisms form the whole automorphism group of the Kneser graph? Yes, it is. Many thanks to Tan Ming Ming who found the following paper answering my question! (Ming ming is a phd student supervised under Professor Bernhard Schmidt. ) See http://www.math.uky.edu/~braun/Braun_AutomorphismGroupStableKneserGraph.pdf

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: