Automorphism group computation problem

Description

The automorphism group computation problem is a general problem of the form: given a combinatorial/geometric/algebraic structure, which is usually a finite set with some additional structure, can we describe easily the automorphism group of that finite set? An explicit description would be a permutation encoding of the automorphism group, viewed as living inside the symmetric group on the underlying set.

Though the exact approach to solving the automorphism group computation problem varies depending on the precise kind of structure, there are a number of general features common to all algorithms. Some of those features are discussed here.

Examples are computing the automorphism group of a graph, of an incidence structure, of a Latin square etc.

Related problems

Related to the automorphism group computation problem are the following problems:

• Isomorphism problem which asks whether two given combinatorial structures (of the same type) are isomorphic.
• Isomorphism class-representative function problem which seeks to find a representative function for the isomorphism class of every object.

Suppose $X$ is the combinatorial object, $n$ is the size of the underlying set, and $G$ is the automorphism group. $G$ is a subgroup of $Sym(n)$, and the cosets of $G$ in $Sym(n)$ correspond to different elements in the isomorphism class of $X$. Thus, the action of $Sym(n)$ on the coset space of $G$ in $Sym(n)$, is precisely the action on the isomorphism class of $X$.

We can view $Sym(n)$ as acting on the set of all objects of size $n$. For this, the orbits are isomorphism classes, and the question of whether two objects are isomorphic boils down to the question of whether they are in the same orbit under the $Sym(n)$ action. Also, the problem of finding an isomorphism class-representative function boils down to the question of finding a function that picks one element from each orbit, and describes a way of finding this representative starting from any element in the orbit.

General ideas behind algorithms

The following ideas are generally used in the algorithms to compute the automorphism group:

References

• Computing automorphism groups of combinatorial objects by Jeffrey S Leon