The aim of this project is twofold: first, to study the non-commutative algebras that arise in the context of graph rewriting (both context-free and context-sensitive cases). It is illustrated that in certain cases, we always get a pre-Lie structure. Second, to study the axiom systems associated with these algebraic structures, that is, relations of the form
(x◦y)◦z-x◦(y◦z)(y◦x)◦z-y◦(x◦z)
are considered.

Pre-Lie structures of graph rewriting

Context-free case

Let
G
1
and
G
2
be two directed acyclic graphs (DAGs for short), both connected; furthermore, we may assume that they are disjoint graphs. Given any vertex
v
of
G
1
and the root
v
2
of
G
2
we can construct another graph denoted by
G
1
⊲
v
G
2
which is the result of gluing
G
2
into
G
1
by identifying (not replacing)
v
with
v
2
. For example, suppose
G
1
and
G
2
are the graphs given by
G
1
G
2
where, the vertex
v
has been chosen as
v5
and the root of
G
2
has been colored in red. Then, the graph
G
1
⊲
v
G
2
is given
Of course, the above product depends on the vertex
v
we chose. One way of defining a product between
G
1
and
G
2
which is independent of the vertex is the following:
G
1
⊲
G
2
:
∑
v∈V(
G
1
)
G
1
⊲
v
G
2
.
This gives us a bilinear product on the vector space generated by the set of DAGs and therefore we get an algebra. Moreover, in any algebra
(A,·)
, if we define the commutator
[a,b]:a·b-b·a
for
a,b∈A
, then the following equation holds:
[[
x
1
,
x
2
],
x
3
]+[[
x
2
,
x
3
],
x
1
]+[[
x
3
,
x
2
],
x
1
]
∑
σ∈
S
3
sgn(σ)(
x
σ(1)
,
x
σ(2)
,
x
σ(3)
)
,
where
(a,b,c):(a·b)·c-a·(b·c)
is called the associator map. Therefore, if for example the equation
(
x
1
,
x
2
,
x
3
)(
x
σ(1)
,
x
σ(2)
,
x
σ(3)
)
holds for all
x
1
,
x
2
,
x
3
∈A
and for a fixed permutation
σ∈
S
3
, then our algebra becomes a Lie algebra, that is, the Jacobi identity holds for any
x
1
,
x
2
,
x
3
∈A
:
[[
x
1
,
x
2
],
x
3
]+[[
x
2
,
x
3
],
x
1
]+[[
x
3
,
x
2
],
x
1
]0
.
In the algebra of graphs we just defined it turns out that if
σ(2,3)
then
(
x
1
,
x
2
,
x
3
)(
x
σ(1)
,
x
σ(2)
,
x
σ(3)
)(
x
1
,
x
3
,
x
2
)
for all
x
1
,
x
2
,
x
3
∈A
and hence we get a Lie algebra structure. Indeed, on one hand we have:
(
G
1
⊲
G
2
)⊲
G
3

∑
v,u∈V(
G
1
)
(
G
1
⊲
v
G
2
)
⊲
u
G
3
+
∑
v∈V(
G
1
),u∈V(
G
2
)
(
G
1
⊲
v
G
2
)
⊲
u
G
3
,
and also:
G
1
⊲(
G
2
⊲
G
3
)
∑
v∈V(
G
1
),u∈V(
G
2
)
G
1
⊲
v
(
G
2
⊲
u
G
3
)
.
The key observation now is that given any
v∈V(
G
1
)
and any
u∈V(
G
2
)
the following equation holds:
(
G
1
⊲
v
G
2
)
⊲
u
G
3

G
1
⊲
v
(
G
2
⊲
u
G
3
)
.
Let us visualize the above equation with the previous graphs and let us choose any vertex of
G
2
, say
u
19. Additionally, consider the graph
​
G
3
Then, it follows from the previous computation of
G
1
⊲
v
G
2
that
(
G
1
⊲
v
G
2
)
⊲
u
G
3
is given by
On the other hand,
G
2
⊲
u
G
3
is given by
⊲
19
=
According to the rule, the next step will identify the root
18
of the above graph with the vertex
5
of
G
1
and consequently after computing
G
1
⊲
v
(
G
2
⊲
u
G
3
)
we will indeed get the exact same graph as before. This means the associator
(
G
1
,
G
2
,
G
3
)
will be given by
Similarly, one has
whereas

Context-sensitive case

Thus,
Similarly (just switching the corresponding labels):

Axiom systems associated with pre-Lie structures

If the above graphs have at least one vertex in common it means the left-symmetric condition is satisfied (since the algebra is the same, the only difference is the initial state).
Nonetheless, this does not give us a path between the associators. In order to obtain a path we can proceed as follows.
Hence, a path between the initial state of the first multiway graph and the first element of the list IntersectionVertices is given by
Now we do the same thing for other initial state:
In this case, a path between the initial state of the first multiway graph and the first element of the list IntersectionVertices is given by
We now obtain a list of paths from one associator to other:
Hence, the first path of such list is given by
which gives us a proof of the left-symmetric condition. Graphically, the paths look as follows:

Concluding Remarks

Acknowledgments

I would like to thank my mentors Xerxes D. Arsiwalla and Hatem Elshatlawy for their valuable comments and the fruitful working sessions (which sometimes ended late into the night). I also thank Phileas Dazeley-Gaist and Alejandra Ortiz, who helped me out with programming stuff and graph theory, respectively. Last but not least, I would like to thank the entire WSS team for their diligence and goodwill from the beginning of the school.

References

1
.
M. Marcolli et al. (2015) “Graph Grammars, Insertion Lie Algebras, and Quantum Field Theory” . Math.Comput.Sci. https://doi.org/10.1007/s11786-015-0236-y
2
.
D. Burde (2006) “Left-symmetric algebras, or pre-Lie algebras in geometry and physics”. Central European Journal of Mathematics . https://doi.org/10.2478/s11533-006-0014-9
3
.
Diestel, R. (2017), Graph Theory 5th edition. Springer Berlin, Heidelberg.

Cite This Notebook

“Pre-lie structures of graph rewriting and associated axiom systems”
by Fernando Olivie Mendez Mendez​
​https://community.wolfram.com/groups/-/m/t/3210202