====== Automorphisms of Graphs ======

===== First Example: The graph of a square =====

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:

<code perl>
> $c=cube(2);
> $c->GRAPH->VISUAL;
</code>
{{:tutorial:square.png?200|}}

To study the automorphisms of this graph, we create a ''props::Graph'' object refering to the ''C++'' class named ''Graph'' (see the [[apps_graph|tutorial on graphs]] for more details):

<code perl>
> $g=new props::Graph($c->GRAPH->ADJACENCY);
</code>
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 props::Graph object ''$g'':

<code perl>
> print rows_labeled($g);
0:1 2
1:0 3
2:0 3
3:1 2
</code>
Now, we compute the generators of the automorphism group of this graph (see the [[apps_group|tutorial on groups]] for more info):

<code perl>
> $aut=automorphisms($g);
</code>
In this case, the automorphism group has two generators:

<code perl>
> print $aut;
0 2 1 3
1 0 3 2
</code>
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'':

<code perl>
> $action = new group::PermutationAction(GENERATORS => $aut);
> $autgroup = new group::Group(PERMUTATION_ACTION => $action);
</code>
Now we can ask for basic properties of the group, e.g., the number of elements:

<code perl>
> print $autgroup->ORDER;
8
</code>
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:

<code perl>
> $s0=new Set<Int>(0);
> $stab0=group::stabilizer_of_set($action,$s0);
</code>
We learn that the node 0 is only fixed by the permutation ''0 2 1 3'':

<code perl>
> print $stab0->ORDER;
2
> print $stab0->PERMUTATION_ACTION->GENERATORS;
0 2 1 3
</code>
In the second case, we look at the subgroup which leaves the set ''{1,2}'' invariant:

<code perl>
> $s12=new Set<Int>(1,2);
> $stab12=group::stabilizer_of_set($action,$s12);
</code>
Now, we obtain a group of order 4:

<code perl>
> print $stab12->ORDER;
4
> print $stab12->PERMUTATION_ACTION->GENERATORS;
3 1 2 0
0 2 1 3
</code>
Finally, we compute the orbits of the indices under the three different groups:

<code perl>
> 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}
</code>