# Automorphism Group of a Graph or Digraph The automorphism group functionality is an interface to version 2.6r7 of the `nauty` and `Traces` packages of B. McKay and A. Piperno. For a paper describing `nauty` see [[McKay, 1981](../../references.md#cite-bdm-nauty-paper)]. There also exists a user’s manual [[McKay and Piperno, n.d.](../../references.md#cite-nauty-traces-manual)] describing the essential features of `nauty` and `Traces`. ## The Automorphism Group Function ### `AutomorphismGroup(G : parameters): Grph -> GrpPerm, GSet, GSet, PowMap, Map, Grph` ```magma Al : MonStgElt Default: "nauty" Canonical : BoolElt Default: {false} Stabilizer : [ \{ GrphVert \} ] Default: Invariant : MonStgElt Default: Minlevel : RngIntElt Default: 0 Maxlevel : RngIntElt Default: Arg : RngIntElt Default: Print : RngIntElt Default: 0 IgnoreLabels: BoolElt Default: false ``` Compute the automorphism group of the graph $G$. This returns the group $A$, the vertex and edge $G$-sets (in that order), the power structure $\cal{A}$ of all automorphisms of $G$, and the transfer map from $A$ to $\cal{A}$. Note that $G$ may be directed or undirected. For small graphs (i.e. having less than 500 vertices) the canonically labelled graph is also returned. The automorphism group computation may be driven by several user parameters. There are five principal parameters: `Al`, `Canonical`, `Stabilizer`, `Invariant` and `Print`. Some of these parameters have associated parameters. The parameter `Al` controls whether the `nauty` or `Traces` algorithms are used to compute the automorphism group. Some parameters are only applicable with the `nauty` algorithm. If the parameter `Canonical` is set to `true`, then the canonically labelled graph will be returned. If the graph has fewer than 500 vertices then the default value for this parameter is `true`, while if the graph has 500 or more vertices, the default value is `false`. It is important to note that the canonically labelled graph is *dependent* upon all the parameters used to compute the automorphism group, including the algorithm parameter. If the parameter `Stabilizer` is assigned a partition $P$ of the vertex-set of $G$ as its value, then the subgroup of the automorphism group of $G$ that preserves the partition $P$ will be computed. The partition given as `Stabilizer` need not be a partition of the full vertex-set of $G$. Any vertices not covered by the sets in `Stabilizer` are assumed to belong to an extra partition cell. This parameter is only relevant when the `nauty` algorithm is used. It causes the algorithm to use the named invariant to assist the auto group computation. The invariant is specified by a string which is the name of a C function computing an invariant, as on pages 37–39 of the `nauty` and `Traces` manual [[McKay and Piperno, n.d.](../../references.md#cite-nauty-traces-manual)]. The default value for `Invariant` is `"Null"` when $G$ is an undirected graph, or `"adjacencies"` when $G$ is a digraph. For a more detailed discussion on invariants see Subsection [nauty Invariants](#graph-subsec-auto-grp-nauty-inv). There are three optional associated parameters to `Invariant`: An expression, depending upon the type of invariant. When $G$ is undirected these three parameters take the values 0, 1, and 0 respectively. When $G$ is a digraph they take the values 0, 2, and 0 respectively. When `Invariant` is one of “indsets”, “cliques”, “cellcliq”, or “cellind”, the default value for `Arg` is $3$. Again, see Subsection [nauty Invariants](#graph-subsec-auto-grp-nauty-inv) for more information. The integer valued parameter `Print` is used to control informative printing according to the following table: `Print := 0` : No output (default). `Print := 1` : Statistics are printed. `Print := 2` : Summary upon completion of each level (`nauty` only). `Print := 3` : Print the automorphisms as they are discovered. By default, the automorphism group computation respects vertex labels (colours). That is, elements of the group will only take a vertex to an identically labelled vertex. The Boolean value `IgnoreLabels` will treat all vertices as identically labelled for the purposes of this computation. ## nauty Invariants Invariants can be used to supplement the built-in partition refinement code in `nauty`, to assist in the processing of difficult graphs. Invariants are used with three parameters: `Minlevel`: the minimum depth in the search tree at which an invariant is to be applied (default 0) `Maxlevel`: the maximum depth in the search tree at which an invariant is to be applied (default 1 for undirected graphs and 2 for digraphs) `Arg`: an integer argument which has a different meaning (or no meaning) for each invariant The root of the tree, corresponding to the partition provided by the user, has level 1. Note that the invariants use an existing partition and attempt to refine it. Thus it can be that an invariant fails to refine the partition at the root of the search tree but succeeds further down the tree. In particular, all invariants necessarily fail at the root of the tree if the graph is vertex-transitive. The invariants are : `"default"` : **•** Default — No invariant is used. `"twopaths"` : **•** Each vertex is classified according to the vertices reachable from along a path of length $2$. This is a cheap invariant sometimes useful for regular graphs. `Arg` is not used. `"adjtriang"` : **•** This counts the number of common neighbours between pairs of adjacent (if `Arg` = $0$) or non–adjacent (if `Arg` = $1$) vertices. This is a fairly cheap invariant which can often work for strongly regular graphs. `"triples"` : **•** This considers in detail the neighbourhoods of each triple of vertices. It often works for strongly regular graphs that `"adjtriang"` fails on, but is more expensive. `Arg` is not used. `"quadruples"` : **•** Similar to triples but using quadruples of vertices. Much more expensive but can work on graphs with highly regular structure that `"triples"` fails on. `Arg` is not used. `"celltrips"` : **•** Like `"triples"`, but only triples inside one cell are used. One to try for the bipartite incidence graphs of structures like block designs (but won’t work for projective planes). `Arg` is not used. `"cellquads"` : **•** Like `"quadruples"`, but only quadruples inside one cell are used. Originally designed for some exceptional graphs derived from Hadamard matrices (where applying it at level $2$ is best). `Arg` is not used. `"cellquins"` : **•** Considers 5-tuples of vertices inside a cell. Very expensive. We don’t know of a good application. `Arg` is not used. `"cellfano"` : `"cellfano2"` : **•** These are intended for the bipartite graphs of projective planes and similar highly regular structures. `"cellfano2"` is cheaper, so try it first. `Arg` is not used. The method is similar to counting Fano subplanes. `"distances"` : **•** This uses the distance matrix of the graph. It is good at partitioning general regular graphs (but not strongly regular graphs). Moderately cheap. `Arg` is unused. `"indsets"` : **•** This uses the independent sets of size `Arg` (default $3$). Can be successful for strongly regular graphs (for `Arg` $\ge 4$) or regular bipartite graphs. `"cliques"` : **•** This uses the cliques of size `Arg` (default $3$). Can be successful for strongly regular graphs (for `Arg` $\ge 4$). `"cellind"` : **•** This uses the independent sets of size `Arg` (default $3$) that lie entirely within one cell of the partition. Try applying at level $2$ for difficult vertex-transitive graphs. `"cellcliq"` : **•** This uses the cliques of size `Arg` (default $3$) that lie entirely within one cell of the partition. Try applying at level $2$ for difficult vertex-transitive graphs. `"adjacencies"` : **•** This is a simple invariant that corrects for a deficiency in the built-in partition refinement procedure for directed graphs. It is the default in Magma for directed graphs. Apply at a few levels, say levels 1–5. `Arg` is unused. These invariants are further described on pages 37–39 of the `nauty` and `Traces` manual [[McKay and Piperno, n.d.](../../references.md#cite-nauty-traces-manual)]. Also, we provide a facility enabling users to test if a specific `Invariant` achieves a partition refinement for a graph $G$. ### `IsPartitionRefined(G: parameters): Grph -> BoolElt` ```magma Stabilizer : [ \{ Vert \} ] Default: Invariant : MonStgElt Default: Arg : RngIntElt Default: IgnoreLabels: BoolElt Default: false ``` Returns `true` if and only the invariant in `Invariant` could refine the graph $G$’s vertex-set partition. If no invariant is set in `Invariant` then the refinement procedure which is tested is taken to be the default one. Four parameters can be passed: The parameters have the same meaning as for [`AutomorphismGroup`](#function-graph-automorphismgroup). ## Graph Colouring and Automorphism Group For any calls to `nauty` or `Traces` via Magma functions the graph colouring of a graph $G$ (as set by [`AssignLabels`](../Multigraphs/multig-decorations.md#function-multigraph-assignlabels) or a similar function) is taken as an *intrinsic* property of $G$. Consequently, the default automorphism group computed by `nauty` or `Traces` is the group for the coloured graph $G$. In particular this implies that, when $G$ is coloured, this default automorphism group is *not* $G$’s full automorphism group. There are several Magma functions which make use of the automorphism group of a graph, and therefore rely on a call to `nauty`. We list them here: **1** `Diameter`, `DiameterPath`, `IsDistanceRegular`, `GirthCycle`, `Girth` **2** `IsDistanceTransitive`, `IsTransitive`, `IsPrimitive`, `IsSymmetric`, `IsIsomorphic`, `IsEdgeTransitive`, `EdgeGroup`, `OrbitsPartition`, `CanonicalGraph` The functions in Group $1$ make use of the automorphism group of the graph only as a means to improve efficiency. If some group has already been computed for the graph under consideration then this group will be used. Otherwise the graph’s default group is computed. The functions in Group $2$ all use the graph’s default group. If a group $A$ of the graph $G$ has already been computed but is not $G$’s default group (for example if a stabilizer of $G$ was given when computing $A$) then the graph’s default group will be computed. Consequently, as an example, if $G$ is coloured, `IsTransitive(G)` will (always) return `false`. For all these functions it is possible to drive the group computation by setting an appropriate `Invariant` parameter. This is particularly useful when it is known that some invariant will speed up the group computation. This is achieved by first computing the group using [`AutomorphismGroup`](#function-graph-automorphismgroup) while setting `Invariant`. This parameter is then remembered for any further (re)computation of the default automorphism group, unless reset by a subsequent call to `AutomorphismGroup`. For convenience, the function `IsIsomorphic` accepts a parameter suite very similar to that of the `AutomorphismGroup` function: It is particularly useful when stabilizers need to be set. ## Variants of Automorphism Group ### `CanonicalGraph(G): Grph -> Grph` Given a graph $G$, return the canonically labelled graph isomorphic to $G$. To see which automorphism group is computed see Subsection [Graph Colouring and Automorphism Group](#graph-subsec-auto-grp-colours). Users should be aware that the canonical graph is *dependent* upon the invariant used when computing the automorphism group. Thus, the computation of the automorphism group of $G$ using different invariants will produce *different* canonical labellings. ### `EdgeGroup(G): Grph -> GrpPerm, GSet` Returns the automorphism group of the graph $G$ in its action on the edges of $G$, and the $G$-set of edges of $G$. To see which automorphism group is computed see Subsection [Graph Colouring and Automorphism Group](#graph-subsec-auto-grp-colours). ### `IsIsomorphic(G, H : parameters): GrphDir, GrphDir -> BoolElt, Map` ### `IsIsomorphic(G, H : parameters): GrphUnd, GrphUnd -> BoolElt, Map` ```magma Stabilizer : [ \{ Vert \} ] Default: Stabilizer2 : [ \{ Vert \} ] Default: IgnoreLabels: BoolElt Default: false ``` This function returns `true` if the graphs $G$ and $H$ are isomorphic. If $G$ and $H$ are isomorphic, a second value is returned, namely a mapping between the vertices of $G$ and the vertices of $H$ giving the isomorphism. The parameters accepted by `IsIsomorphic` are almost the same as for [`AutomorphismGroup`](#function-graph-automorphismgroup). The exceptions are: This sets the stabilizer set for *both* graphs $G$ and $H$. If one wishes to set two distinct stabilizers then one would also use: This sets the stabilizer set for the second graph $H$ only. This indicates whether or not to ignore the graph labelling for *both* graphs $G$ and $H$. Graph isomorphism is understood as mapping colours to colours and stabilizers to stabilizers. Consequently comparing two graphs for isomorphism will always return `false` if one graph is coloured while the other one is not. Similarly two graphs can’t be isomorphic if each is coloured using a different set of colours. Moreover, it is a `nauty` requirement that in order to achieve mapping of stabilizers they must be compatible: that is, they *must* have same-sized cells in the same order. In general, to see which and how the graphs’ automorphism groups are computed see Subsection [Graph Colouring and Automorphism Group](#graph-subsec-auto-grp-colours). ### `Example: Automorphism Group (ex-bda3f8)` We provide a very simple example of the use of `AutomorphismGroup` which shows how the automorphism group and the corresponding canonical graph differ depending on the labelling of the graph and of the stabilizer given, if any. ```magma > G := Graph<5 | { {1,2}, {2,3}, {3,4}, {4,5}, {5,1} }>; > > AssignLabels(VertexSet(G), ["a", "b", "a", "b", "b"]); > A, _, _, _, _, C1 := AutomorphismGroup(G); > A; Permutation group A acting on a set of cardinality 5 Order = 2 (1, 3)(4, 5) > C1; Graph Vertex Neighbours 1 3 5 ; 2 4 5 ; 3 1 4 ; 4 2 3 ; 5 1 2 ; > B, _, _, _, _, C2 := AutomorphismGroup(G : IgnoreLabels := true); > B; Permutation group B acting on a set of cardinality 5 Order = 10 = 2 * 5 (2, 5)(3, 4) (1, 2)(3, 5) > C2; Graph Vertex Neighbours 1 2 3 ; 2 1 4 ; 3 1 5 ; 4 2 5 ; 5 3 4 ; > C, _, _, _, _, C3 := AutomorphismGroup(G : Stabilizer := > [ { VertexSet(G) | 1, 2 } ]); > C; Permutation group C acting on a set of cardinality 5 > #C; 1 > C3; Graph Vertex Neighbours 1 3 4 ; 2 3 5 ; 3 1 2 ; 4 1 5 ; 5 2 4 ; ``` We now check that the graph returned by `CanonicalGraph` is identical to $C_1$: ```magma > C4 := CanonicalGraph(G); > C4 eq C1; true ``` ### `Example: Graph Isomorphim (ex-4bd4fd)` These two examples should help clarify how `IsIsomorphic` behaves for graphs for which a colouring is defined. The first example shows that two graphs cannot be isomorphic if one is coloured while the other is not. This example also demonstrates the use of stabilizers. ```magma > G1 := CompleteGraph(5); > AssignLabels(VertexSet(G1), ["a", "a", "b", "b", "b"]); > G2 := CompleteGraph(5); > IsIsomorphic(G1, G2); false > IsIsomorphic(G1, G2 : IgnoreLabels := true); true > > V1 := Vertices(G1); > V2 := Vertices(G2); > S1 := { V1 | 1, 2, 3}; > S2 := { V2 | 3, 4, 5}; > > IsIsomorphic(G1, G2 : Stabilizer := [S1], > Stabilizer2 := [S2]); false > IsIsomorphic(G1, G2 : Stabilizer := [S1], > Stabilizer2 := [S2], IgnoreLabels := true); true > IsIsomorphic(G1, G2 : Stabilizer := [S1], > IgnoreLabels := true); true > > SS1 := [ { V1 | 1}, {V1 | 2, 3} ]; > SS2 := [ { V2 | 3, 4}, { V2 | 1} ]; > IsIsomorphic(G1, G2 : Stabilizer := SS1, Stabilizer2 := SS2, > IgnoreLabels := true); false > > SS1 := [ {V1 | 2, 3}, { V1 | 1} ]; > IsIsomorphic(G1, G2 : Stabilizer := SS1, Stabilizer2 := SS2, > IgnoreLabels := true); true ``` The second example shows that two graphs are isomorphic if and only if colours map to the *same* colours. ```magma > G1 := CompleteGraph(5); > AssignLabels(VertexSet(G1), ["b", "b", "b", "a", "a"]); > G2 := CompleteGraph(5); > AssignLabels(VertexSet(G2), ["a", "a", "b", "b", "b"]); > IsIsomorphic(G1, G2); true > > G1 := CompleteGraph(5); > AssignLabels(VertexSet(G1), ["a", "b", "b", "c", "c"]); > G2 := CompleteGraph(5); > AssignLabels(VertexSet(G2), ["a", "c", "b", "b", "c"]); > IsIsomorphic(G1, G2); true > > G1 := CompleteGraph(5); > G2 := CompleteGraph(5); > AssignLabels(VertexSet(G1), ["a", "a", "b", "b", "b"]); > AssignLabels(VertexSet(G2), ["b", "b", "a", "a", "a"]); > IsIsomorphic(G1, G2); false > IsIsomorphic(G1, G2 : IgnoreLabels := true); true > > G1 := CompleteGraph(5); > AssignLabels(VertexSet(G1), ["b", "b", "b", "a", "a"]); > G2 := CompleteGraph(5); > AssignLabels(VertexSet(G2), ["b", "b", "c", "c", "c"]); > IsIsomorphic(G1, G2); false > IsIsomorphic(G1, G2 : IgnoreLabels := true); true ``` ## Action of Automorphisms The automorphism group $A$ of a graph $G$ is given in its action on the standard support and it does not act directly on $G$. The action of $A$ on $G$ is obtained using the $G$-set mechanism. The two basic $G$-sets associated with the graph correspond to the action of $A$ on the set of vertices $V$ and the set of edges $V$ of $G$. These two $G$-sets are given as return values of the function `AutomorphismGroup` or may be constructed directly. Additional $G$-sets associated with a graph may be built using the $G$-set constructors. Given a $G$-set $Y$ for $A$, the action of $A$ on $Y$ may be studied using the permutation group functions that allow a $G$-set as an argument In this section, only a few of the available functions are described: see the section on $G$-sets for a complete list. ### `Image(a, Y, y): GrpPermElt, GSet, Elt -> Elt` Let $a$ be an element of the automorphism group $A$ for the graph $G$ and let $Y$ be a $G$-set for $A$. Given an element $y$ belonging either to $Y$ or to a $G$-set derived from $Y$, find the image of $y$ under $a$. ### `Orbit(A, Y, y): GrpPerm, GSet, Elt -> GSet` Let $A$ be a subgroup of the automorphism group for the graph $G$ and let $Y$ be a $G$-set for $A$. Given an element $y$ belonging either to $Y$ or to a $G$-set derived from $Y$, construct the orbit of $y$ under $A$. ### `Orbits(A, Y): GrpPerm, GSet -> [ GSet ]` Let $A$ be a subgroup of the automorphism group for the graph $G$ and let $Y$ be a $G$-set for $G$. This function constructs the orbits of the action of $A$ on $Y$. ### `Stabilizer(A, Y, y): GrpPerm, GSet, Elt -> GrpPerm` Let $A$ be a subgroup of the automorphism group for the graph $G$ and let $Y$ be a $G$-set for $A$. Given an element $y$ belonging either to $Y$ or to a $G$-set derived from $Y$, construct the stabilizer of $y$ in $A$. ### `Action(A, Y): GrpPerm, GSet -> Hom(Grp), GrpPerm, GrpPerm` Given a subgroup $A$ of the automorphism group of the graph $G$, and a $G$-set $Y$ for $A$, construct the homomorphism $\phi: A \rightarrow L$, where the permutation group $L$ gives the action of $A$ on the set $Y$. The function returns: **(a)** The natural homomorphism $\phi: A \rightarrow L$; **(b)** The induced group $L$; **(c)** The kernel of the action (a subgroup of $A$). ### `ActionImage(A, Y): GrpPerm, GSet -> GrpPerm` Given a subgroup $A$ of the automorphism group of the graph structure $G$, and a $G$-set $Y$ for $A$, construct the permutation group $L$ giving the action of $A$ on the set $Y$. ### `ActionKernel(A, Y): GrpPerm, GSet -> GrpPerm` Given a subgroup $A$ of the automorphism group of the graph $G$, and a $G$-set $Y$ for $A$, construct the kernel of the action of $A$ on the set $Y$. ### `Example: Automorphism Action (ex-ec7c11)` We construct the Clebsch graph (a strongly regular graph) and investigate the action of its automorphism group. ```magma > S := { 1 .. 5 }; > V := &join[ Subsets({1..5}, 2*k) : k in [0..#S div 2]]; > E := { {u,v} : u,v in V | #(u sdiff v) eq 4 }; > G, V, E := StandardGraph( Graph< V | E >); > G; Graph Vertex Neighbours 1 4 6 8 10 12 ; 2 5 6 9 12 14 ; 3 9 10 12 13 16 ; 4 1 7 9 14 16 ; 5 2 7 8 10 16 ; 6 1 2 13 15 16 ; 7 4 5 12 13 15 ; 8 1 5 9 11 13 ; 9 2 3 4 8 15 ; 10 1 3 5 14 15 ; 11 8 12 14 15 16 ; 12 1 2 3 7 11 ; 13 3 6 7 8 14 ; 14 2 4 10 11 13 ; 15 6 7 9 10 11 ; 16 3 4 5 6 11 ; > A, AV, AE := AutomorphismGroup(G); > A; Permutation group aut acting on a set of cardinality 16 Order = 1920 = 2^7 * 3 * 5 (2, 15)(5, 11)(7, 14)(10, 12) (3, 11)(8, 10)(9, 14)(13, 15) (2, 11)(5, 15)(6, 8)(9, 16) (2, 7)(4, 6)(9, 13)(14, 15) (1, 2, 13, 15)(3, 11, 4, 5)(7, 10, 12, 14)(8, 9) > CompositionFactors(A); G | Cyclic(2) * | Alternating(5) * | Cyclic(2) * | Cyclic(2) * | Cyclic(2) * | Cyclic(2) 1 > IsPrimitive(A); true ``` From the composition factors we guess that the group is $Sym(5)$ extended by the elementary abelian group of order $16$. Let us verify this and relate it to the graph. We begin by trying to get at the group of order $16$. We ask for the Fitting subgroup. ```magma > F := FittingSubgroup(A); > F; Permutation group F acting on a set of cardinality 16 Order = 16 = 2^4 (1, 13)(2, 11)(3, 4)(5, 15)(6, 8)(7, 10)(9, 16)(12, 14) (1, 10)(2, 9)(3, 12)(4, 14)(5, 8)(6, 15)(7, 13)(11, 16) (1, 11)(2, 13)(3, 5)(4, 15)(6, 14)(7, 9)(8, 12)(10, 16) (1, 12)(2, 6)(3, 10)(4, 7)(5, 16)(8, 11)(9, 15)(13, 14) ``` Since $A$ is primitive, this looks as if it is an elementary abelian regular normal subgroup: ```magma > EARNS(A) eq F; true ``` Thus, $A$ has a regular normal subgroup $N$ of order $16$ which acts transitively on the vertices. Therefore, the stabilizer of any point is a complement of $N$. ```magma > S1 := Stabilizer(A, AV, V!1); > #S1; 120 > IsTransitive(S1); false > Orbits(S1); [ GSet{@ 1 @}, GSet{@ 3, 7, 9, 11, 15 @}, GSet{@ 2, 5, 4, 14, 16, 6, 13, 12, 8, 10 @} ] > exists(orbit){x : x in Orbits(S1) | #x eq 5}; true > orbit; GSet{@ 3, 7, 9, 11, 15 @} > IsSymmetric(ActionImage(S1, orbit)); true ``` So the stabilizer of the vertex $1$ is ${\operatorname{Sym}}(5)$, acting faithfully on the $5$ neighbours of vertex $1$.