Wikipedia:Reference desk/Archives/Mathematics/2010 November 4

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 4

graph automorphism

How do I show that for a simple graph G, Aut (G) is isomorphic to Aut(${\bar {G}}$), where ${\bar {G}}$ is the complement of G. I want to exhibit a isomorphism between them. But I cant seem to figure out that if I pick a permutation of the vertex set which preserves adjacency in G, what will be the corresponding permutation of the vertices which preserves adjacency in ${\bar {G}}$. -Shahab (talk) 07:24, 4 November 2010 (UTC)

Isn't it just the identity isomorphism? 67.158.43.41 (talk) 08:10, 4 November 2010 (UTC)

Oops!! Thanks.-Shahab (talk) 08:49, 4 November 2010 (UTC)

I have two more questions now. Won't the automorphism group of the complete bipartite graph K_m,n be S_m x S_n. I reason this out by taking the complement of K_m,n which is a disjoint union of K_m and K_n and trying to find its automorphism group. The automorphism groups of K_m and K_n are clearly S_m and S_n (sice adjacency is always preserved, no matter the permutation) and so to count all permutations I conclude that the automorphism group of K_m,n is S_m x S_n. But the wikipedia article says that there are 2m!n! automorphisms if m = n. Why is that so?

Secondly, I also want to compute the automorphism group of the Petersen graph which is the same as that of L(K₅). The wikipedia article says that it is S₅, the reason is not clear to me.

Thanks-Shahab (talk) 09:42, 4 November 2010 (UTC)

(Edit: ignore this; see next comment.) For your second question, a proof outline would be: (1) the inner "star" gets sent to itself in any automorphism (this is the hard part); (2) determining where the inner star gets sent determines where the outside vertices get sent, completely determining the permutation; (3) there are 5! = 120 permutations of the inner star, where each generates an automorphism, and these permutations are easily seen to be isomorphic to S_5. 67.158.43.41 (talk) 09:52, 4 November 2010 (UTC)

Both parts of your argument are false. There are automorphisms which (for example) swap the inner star with the outer pentagon, and the inner star (being a five-cycle) only has ten automorphisms in any case. A better way is to consider S₅ acting on the vertices of K₅ in the obvious fashion, which induces an action on the line graph of K₅, which induces and action on the Petersen graph. Algebraist 10:02, 4 November 2010 (UTC)

Thank you for pointing that out. I should be more careful in the future. I saw 5 vertices and 5! and shoved the ideas together, assuming the steps in the proof would necessarily follow. 67.158.43.41 (talk) 10:44, 4 November 2010 (UTC)

If m=n, then there are automorphisms of K_m,m which swap the left side with the right side. Thus the automorphism group is a semidirect product of S_m x S_m by Z₂. Algebraist 10:02, 4 November 2010 (UTC)

Thanks for the reply. For the first question instead of thinking about semi direct product (the part about Z₂ confuses me) can I just say: given any 2m symbols we can obtain a required automorphism by permuting the first m in m! ways and the second m in m! more ways. Hence we have is m!m! permutations. Moreover for each such permutation f we may also another permutation by mapping 1,...m to f(m+1)...f(2m), and mapping m+1,...2m to f(1),...f(m). This swaps the two complete graph vertices and as this is possible for each of our previous permutations so the total is 2m!m!. The second question is not clear to me still unfortunately. I am not understanding how and what group action is induced. I'll prefer an intuitive counting argument, if thats possible. That the complement of the Peterson graph is L(K₅) is clear to me and we hence need only to show Aut(L(K₅))=S₅.-Shahab (talk) 10:52, 4 November 2010 (UTC)

Here's how you may visualize the 5! automorphisms of the Petersen graph (if you like this algebraic way of thinking). You say you know that the Petersen graph is isomorphic to the complement of the line graph of K₅. Consider how the line graph is defined: the vertices of the line graph L(G) are the edges {x,y} of graph G, and two edges are connected iff they aren't disjoint. Take a permutation σ of the vertices of K₅ (there are 5! of these). This acts naturally on the edges of K₅, namely {x,y}σ is defined as {xσ,yσ} (here we use that we have the complete graph so we know the latter is also an edge). Now you can regard this permutation of the edges of K₅ as a permutation of the vertices of the line graph L(K₅). Prove that this permutation is a graph automorphism of the line graph. Also prove that no two of these permutations are equal.

(Incidentally, you can also generalize this to finding the n! automorphisms of the Kneser graph KG(n,k), where KG(n,2) is isomorphic to the complement of L(K_n).)

This does not give an easy way to prove that these are the only automorphisms of the graph, so you'll have to find some specialized argument for that. – b_jonas 20:26, 4 November 2010 (UTC)

Two questions

ok I have two questions: speaking of the prime-counting function $\pi (x)$ there is an approximation $\pi (x)\approx {\frac {x}{\ln x}}$ and $\pi (x)\approx li(x)$. Which is more accurate? Also, how can it be proven that $\lim _{n\to \infty }(1+{\frac {1}{n}})^{nx}=\lim _{n\to \infty }(1+{\frac {x}{n}})^{n}$? Thanks. —Preceding unsigned comment added by 24.92.78.167 (talk) 21:56, 4 November 2010 (UTC)

1. The latter
2. assuming x>0, substitute n=m/x in the left hand side

Bo Jacoby (talk) 22:56, 4 November 2010 (UTC).