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.7, 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
depthWrite
Rotation
x-axis
y-axis
z-axis
Rotation speed
Display
Objects
Camera
SVG
Download
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
  • Last modified: 2019/02/11 23:09
  • (external edit)