This is part of the Tutorial:Graphic lambda calculus.
Here it is explained the most important move in graphic lambda calculus: the graphic beta move.
A move is a transformation of a graph into another. It is not a function from to though, as we shall see.
The graphic beta move takes its name from the beta reduction in lambda calculus.
Consider the set with the equality of oriented, locally planar graphs (with leaves not numbered), denoted by .
A graphic beta move is a local move which consists in replacing a pattern (sub-graph) by another pattern. More precisely, we can apply the graphic beta move to any graph which contains a certain pattern (sub-graph) and we obtain a new graph, which is identical with the initial one, with the exception of the pattern, now replaced by the other pattern.
Here is the precise definition of the graphic beta move. See the explanations after the figure.
The labels “1, 2, 3, 4” are used only as guides for gluing correctly the new pattern, after removing the old one. Imagine that we have a graph which contains as a sub-graph the one from the left hand side (LHS) of the previous figure. Then, by a graphic beta move, we may replace the pair of nodes from the LHS figure with two arrows, as indicated by the labelling “1,2,3,4”. The rest of the graph is unchanged.
We may represent the graphic beta move like this:
Up to the particular embedding in the plane of the graph from the right hand side (RHS), the move is the same. The crossing of the “1,3” arrow with the “4,2” arrow is an artefact of the embedding, there is no node there. Crossings of arrows have no meaning, remember that we work with graphs which are locally planar, not globally planar.
The graphic beta move goes into both directions. Referring to the first two pictures, we may pick a pair of arrows and label them with “1,2,3,4”, such that, according to the orientation of the arrows, “1” points to “3” and “4” points to “2”, without any node or label between “1” and “3” and between “4” and “2” respectively. Then, by a graphic beta move, we may replace the portions of the two arrows which are between “1” and “3”, respectively between “4” and “2”, by the pattern from the LHS of the figure.
Here is an example.
The red drawings have no meaning in the formalism, I have put them only to make a more clear drawing of the move. Remark that we may read the move from left to right, as well as from right to left. The dashed closed curve serves to mark the pattern.
The graphic beta move may be applied to a single arrow, or to a loop, there is nothing which might stop this. For example, here are three applications of the graphic beta move:
In particular we have a justification of considering loops and wires as members of .
A point important to stress is that the graphic beta move is not dependent of the particular embedding into the plane of the graphs (which we use when we draw the graphs). This will be important further, when we discuss about the crossing macros, see the post “Graphic beta rule as braiding“.
Also, different labelling (of the same graphs) leads to different outcomes of the graphic beta move. This is explained in the next figure:
Here “A, B, C, D” denote four graphs in . Two possible graphic beta moves are depicted. Let’s read them from right to left.
At the right we have a graph with two arrows, connecting “A” with “B” and “D” with “C”. We may apply the graphic beta move to this graph in two ways, depending on the labelling of the arrows. If we mark the arrow from “A” to “B” with “1,3” and the arrow from “D” to “C” with “4,2” then we get the first graphic beta move. However, we may choose to mark the arrow from “A” to “B” with “4,2” and the arrow from “D” to “C” with “1,3”, applying then the graphic beta move. The outcome is different.
A particular case of the previous figure is yet another justification for having loops as elements in .
These two applications of the graphic beta move may be represented alternatively like this:
A move which resembles very much with the graphic beta move is the unzip operation from the knotted trivalent graphs formalism, see for example the paper The algebra of knotted trivalent graphs and Turaev’s shadow world by D.P. Thurston, section 3. (this was mentioned also in the post “Graphic beta rule as braiding“).
In order to see this, let’s draw again the graphic beta move, this time without labelling the arrows:
The unzip operation acts only from left to right in the following figure. Remarkably, it acts on trivalent graphs (but not oriented).
UNZIP is not a move in graphic lambda calculus.
Return to Tutorial:Graphic lambda calculus