This is just an arbitrary testimony of an often repeated slogan:

"The group of automorphisms of a given structure is often a powerful tool for studying this structure." D. Lascar, On the Category of Models of a Complete Theory

I wonder why this should be so when thinking of the fact that (for example) almost all graphs have a trivial automorphism group. And only very few - if any - graphs have an automorphism group that allows literally to tell the graph from it.

How then is this slogan to be understood? For which kinds of structures does it make sense, resp. in which sense?

Side question: Is it true, that when the automorphism group of a graph is isomorphic to the full symmetric group $S_n$, then the graph has to be the complete graph $K_n$ or its complement?


Lascar says often, not always. The philosophy -- which you correctly link back to Klein's Erlangen Program; I think you would do well to study that and read what Klein has to say about it -- certainly works better for structures which have large, rich automorphism groups. Klein's original motivation was the observation that many of features of a geometry are determined by its group of isometries, which is usually a Lie group of positive dimension. Geometries with nonisomorphic isometry groups are profoundly different. Geometries with isomorphic isometry groups often have some deep commonalities.

I think it is too broad a question to ask for anything like a comprehensive description of the structures for which the automorphism group plays a key role. Here are two important examples:

The classification of fiber bundles on a (sufficiently nice) topological space depends only on the automorphism group of the fiber, not on the homeomorphism type of the fiber. This leads to a description/construction of fiber bundles on a space in terms of $1$-cocycles with coefficients in the automorphism group. Also the notion of "reduction of the structure group" is a key one in the study of fiber bundles. E.g. a paracompact differentiable manifold is orientable if the structure group of the tangent bundle can be reduced to $\operatorname{GL}_n(\mathbb{R})^+$. It admits a Riemannian metric iff the structure group can be reduced to $O_n(\mathbb{R})$. In fact the latter is always the case, and that can be understood (among other ways) by understanding the way that $O_n(\mathbb{R})$ sits inside $\operatorname{GL}_n(\mathbb{R})$.

A closely related principle is the principle of Galois descent: if $V_{/K}$ is an algebraic structure defined over a field (examples: a $K$-algebra, a variety, a group variety), then the set of twisted forms of $V_{/K}$ -- namely those objects $W_{/K}$ which become isomorphic to $V$ over the algebraic closure of $K$ -- are again parameterized by $1$-cocycles with coefficients in the automorphism group of $V$. In particular, when two objects which have isomorphic automorphism groups, there is a bijection between the twisted forms. Here the case of a trivial automorphism group is not a trivial case: when the automorphism group is trivial, there are no twisted forms other than $V$.

One could go on forever in the above manner, so I'll limit myself now to graph theory.

For every finite graph $G$, there is a nonisomorphic finite graph $G'$ such that $\operatorname{Aut}(G) \cong \operatorname{Aut}(G')$.

This follows easily from the fact that you mentioned: for all sufficiently large $n$, there is a connected graph $R_n$ on $n$ vertices with trivial automorphism group (and indeed the proportion of such graphs among all connected graphs approaches $1$ as $n$ approaches infinity). Then given a graph $G$ with $n$ vertices, $G \coprod R_{n+1}$ must have the same automorphism group as $G$.

Let $G$ be a nonempty simple graph on $n$ vertices with automorphism group $S_n$. Then $G = K_n$ is the complete graph on $n$ vertices.

We may assume $n \geq 2$, and then $S_n$ acts doubly transitively on $\{1,\ldots,n\}$, in other words, given any two pairs of distinct vertices, there is a graph automorphism taking one to another. Since the graph is nonempty, there are two vertices $v_1$ and $v_2$ connected by an edge. It follows that every pair of vertices is connected by an edge.

By the way, the fact that most finite graphs have trivial automorphism group only means that one cannot use the automorphism group as a tool to classify finite graphs (which is a rather hopeless problem anyway). It certainly does not mean that the automorphism group of a graph is not a highly interesting and useful invariant. In practice, the individual graphs of most interest tend to be those with a large, interesting automorphism group (and recall that by a theorem of Frucht, every group occurs up to isomorphism as an automorphism group of some graph). For instance Cayley graphs of groups are extremely important, and there the automorphism group acts simply transitively. Conversely, a celebrated theorem of G. Sabidussi says that any graph which admits a simply transitive subgroup $G$ of automorphisms must be a Cayley graph on the group $G$. So the automorphism group of a graph can tell us important information about the graph, especially when regarded as a permutation group on the set of vertices rather than as an abstract group.

  • $\begingroup$ I don't know why I should not say "thanks" (as suggested by the MSE-system). But I feel urged to thank you for this comprehensive answer - and that you took my question serious. One thing is for sure: "often" does not mean "always". But it also does not mean "almost always not" (like for graphs, where almost all graphs have the same automorphism group). $\endgroup$ – Hans-Peter Stricker Jul 26 '13 at 0:45
  • $\begingroup$ Hans: "often", upon restriction to an infinite subset, can certainly become "almost never" or even "never". This can even happen with "almost always": e.g. a real number is almost always transcendental, but a rational number is never transcendental. But the quantification is silly: like most "principles", this one is useful in some situations and not in others, and there is not a prearranged formal demarcation of one versus the other. $\endgroup$ – Pete L. Clark Jul 26 '13 at 0:51
  • $\begingroup$ More pertinently, notice that in my answer I gave two instances in which the automorphism group (as a permutation group on the vertices) does tell you important information about the graph, in one case coming close to classifying it. If you look up "automorphisms of graphs" you will find that hundreds of paper have been written on them, so it is certainly a fruitful and deep topic. They don't tell you everything...so what? $\endgroup$ – Pete L. Clark Jul 26 '13 at 0:53
  • $\begingroup$ No question about that! a) I never dared to doubt that it's a fruitful and deep topic. (Just wanted to learn, how, why, and in which contexts.) b) I am quite happy to learn, how automorphisms don't tell everything, but... $\endgroup$ – Hans-Peter Stricker Jul 26 '13 at 0:57
  • $\begingroup$ One last question: How can "often" become "never"? $\endgroup$ – Hans-Peter Stricker Jul 26 '13 at 0:59

I wonder why this should be so when thinking of the fact that (for example) almost all graphs have a trivial automorphism group.

The distribution of graphs that one can encounter is biased in favor of nonrandom, structured, low entropy objects.

  • $\begingroup$ I explicitly appreciate this answer. $\endgroup$ – Hans-Peter Stricker Jul 26 '13 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.