tested.ipynb

Kernel: My mdtraj

Cayley Graphs

A semigroup $S$ is a set with a closed and associative binary operation. One can generate a semigroup by taking elements in a generating set and repeatedly multiplying them. One can make a right cayley graph, which is a directed graph, by taking as vertex set the elements of S --- factored in terms of the generators --- and adjoining vertices $x,y \in V$ if there exists $a$ in the generating set such that $xa = y$. Similarly, one can make the left cayley graph, by adjoing vertices $x,y$ if there exists $a$ in the generating set such that $ax = y$.

import networkx as nx
from libsemigroups_cppyy import Transformation, Permutation, FroidurePin, BooleanMat
import numpy as np
import matplotlib

Define your semigroup creating a Froidure-Pin class, and placing generating elements in the function. The following produces a group.

#Define your Semigroup. This is the one from the notes.
S = FroidurePin(Permutation([1, 2, 3, 0]), Permutation([1, 0, 2, 3]))
S.size()

24

This is the right cayley graph of S.

np.random.seed(2)
def right_cayley(semigroup):
    edges = []
    for i in range(S.size()):
        for j in range(S.nr_generators()):
            edges.append((str(S.factorisation(S[i])),str(S.factorisation(S.right(i,j)))))
    G=nx.DiGraph()
    G.add_edges_from(edges)
    return(nx.draw(G, with_labels = True))
right_cayley(S)

This is the left cayley graph of S.

np.random.seed(2)
def left_cayley(semigroup):
    edges = []
    for i in range(S.size()):
        for j in range(S.nr_generators()):
            edges.append((str(S.factorisation(S[i])),str(S.factorisation(S.left(i,j)))))
    G=nx.DiGraph()
    G.add_edges_from(edges)
    return(nx.draw(G, with_labels = True))
left_cayley(S)

Cayley graphs of transformations

The following semigroups and cayley graph were made in the notes. We construct it here.

S = FroidurePin(Transformation([1,1,2]), Transformation([1,0,1]))

np.random.seed(2)
right_cayley(S)

np.random.seed(2)
left_cayley(S)

So left and right cayley graphs of semigroups can look very different!