user_guide:tutorials:aut_of_graphs

This tutorial is probably also available as a Jupyter notebook in the demo folder in the polymake source and on github.

Different versions of this tutorial: latest release, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, nightly master

# Automorphisms of Graphs

Let's look at the graph of a square. Since a square is a 2-cube, we can create the polytope and look at its graph:

> $c=cube(2); >$c->GRAPH->VISUAL;
unnamed
Transparency
Rotation
x-axis
y-axis
z-axis
Rotation speed
Display
Objects
Camera
SVG
New tab  To study the automorphisms of this graph, we create a GraphAdjacency<Dir> object refering to the C++ class named Graph (see the tutorial on graphs for more details):

> $g=new GraphAdjacency($c->GRAPH->ADJACENCY);

The picture of the graph shows that the node with label 0 is adjacent to the nodes 1 and 2, Node 1 is adjacent to 0 and 3, and so on. For the complete adjacency information you can print $c->GRAPH->ADJACENCY or just the GraphAdjacency object $g:

> print rows_labeled($g); 0:1 2 1:0 3 2:0 3 3:1 2 Now, we compute the generators of the automorphism group of this graph (see the tutorial on groups for more info): >$aut=automorphisms($g); In this case, the automorphism group has two generators: > print$aut;
0 2 1 3
1 0 3 2

Each generator is a permutation on the nodes. The first generator fixes the nodes 0 and 3, and exchanges the nodes 1 and 2, i.e., it describes the reflection along the diagonal through 0 and 3. The second generator is the reflection along the horizontal line.

In order to be able to work with the group, we create a new Group object, which lives in the application group:

> $action = new group::PermutationAction(GENERATORS =>$aut);
> $autgroup = new group::Group(PERMUTATION_ACTION =>$action);

Now we can ask for basic properties of the group, e.g., the number of elements:

> print $autgroup->ORDER; 8 Sometimes, it is useful to know which elements of the group fix a specific set of indices, that is, we are interested in the subgroup which is the stabilizer of the given set. In the first case, we just fix the index 0: >$s0=new Set<Int>(0);
> $stab0=group::stabilizer_of_set($action,$s0); We learn that the node 0 is only fixed by the permutation 0 2 1 3: > print$stab0->ORDER;
2
> print $stab0->PERMUTATION_ACTION->GENERATORS; 0 2 1 3 In the second case, we look at the subgroup which leaves the set {1,2} invariant: >$s12=new Set<Int>(1,2);
> $stab12=group::stabilizer_of_set($action,$s12); Now, we obtain a group of order 4: > print$stab12->ORDER;
4
> print $stab12->PERMUTATION_ACTION->GENERATORS; 3 1 2 0 0 2 1 3 Finally, we compute the orbits of the indices under the three different groups: > print$stab0->PERMUTATION_ACTION->ORBITS;
{0}
{1 2}
{3}
> print $stab12->PERMUTATION_ACTION->ORBITS; {0 3} {1 2} > print$autgroup->PERMUTATION_ACTION->ORBITS;
{0 1 2 3}
• user_guide/tutorials/aut_of_graphs.txt