Isomorphisms and Automorphisms

681 Views Asked by At

An automorphism is a mapping of a graphs nodes onto it's own nodes. Whereas an isomorphism is the mapping of a graphs nodes onto another graphs nodes.

Doesn't this mean the are fundamentally the same thing, it's just a matter of what the nodes are labelled (for example in one graph the nodes may numbered sequentially, but in the other graph they are labelled alphabetically)?

So will the number of automorphisms be the same as the number of isomorphisms?

3

There are 3 best solutions below

1
On

Your understanding matches mine. The distinction is somewhat academic. I am not aware of any theorems that hinge on the distinction.

Does the identity count as an automorpism? If not, there is probably one more isomorphism than automorphism. Also, intuition breaks down when you are talking about infinite sets.

0
On

The two notions describe a similar situation, but we often obtain two graphs (groups, rings, modules, etc.) in two different ways and wonder whether the two objects are the same. We thus talk of isomorphisms. On the other hand, if we have one object, we may want to study self-symmetries of it. To do this we talk of automorphisms of the object.

And yes, the number of isomorphisms of $A$ is the same as the number of ismorphisms of $A$ to $B$ (assuming there is one). If $\phi$ is such an isomorphism, then $$\text{Aut}(A) \to \text{Iso}(A,B)$$ $$\psi \mapsto \phi \circ \psi$$ bijects these two sets.

1
On

If two graphs $X$ and $Y$ are isomorphic (that is, there exists an isomorphism between them) then it is true that the number of automorphisms of $X$ is equal to the number of isomorphisms from $X$ to $Y$.

Let's recall the definition of an isomorphism, as I don't know what notation you're used to. Let $X$ and $Y$ be graphs with respective vertex sets $V(X)$ and $V(Y)$. An isomorphism from $X$ to $Y$ is a bijection $f:V(X)\to V(Y)$ such that each pair of vertices $u,v\in V(X)$ are adjacent in $X$ if and only if $f(u),f(v)$ are adjacent in $Y$.

Let $\operatorname{Iso}(X,Y)$ denote the set of all isomorphisms from $X$ to $Y$. (This is the empty set if $X$ and $Y$ are not isomorphic, by definition.)

Let $\operatorname{Aut}(X)$ denote the set of automorphisms of $X$. That is, $\operatorname{Aut}(X) = \operatorname{Iso}(X,X)$.

Suppose $X$ and $Y$ are isomorphic. Then by definition there exists some $f\in \operatorname{Iso}(X,Y)$. We can then use this element $f$ to construct a bijection $$\Phi:\operatorname{Aut}(X)\to\operatorname{Iso}(X,Y)$$ by definining $\Phi(\alpha) = f\circ\alpha$ for each automorphism $\alpha$ of $X$. (As an exercise, verify that $\Phi(\alpha)$ is indeed an isomorphism.)

So if $X$ and $Y$ are isomorphic, then indeed the number of automorphisms of $X$ (or of $Y$, for that matter) is the same as the number of isomorphisms from $X$ to $Y$. However, note that the bijection we constructed above depended on the choice of isomorphism $f$. There is no canonical bijection $\operatorname{Aut}(X)\to\operatorname{Iso}(X,Y)$, unless of course each of these sets has just one element.