The graphic beta move, with details

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 GRAPH to GRAPH though, as we shall see.

The graphic beta move takes its name from the beta reduction in lambda calculus.

Consider the set GRAPH with the equality of oriented,  locally planar graphs (with leaves not numbered), denoted by \equiv.

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.

beta_move_1

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:

beta_move_6

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.

beta_move_2

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:

beta_move_3

In particular we have a justification of considering loops and wires as members of GRAPH.

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:

beta_move_4

Here “A, B, C, D” denote four graphs in GRAPH. 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 GRAPH.

beta_move_5

These two applications of the graphic beta move may be represented alternatively like this:

beta_move_8

__________________________

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:

beta_move_9

The unzip operation acts only from left to right in the following figure. Remarkably, it acts on trivalent graphs (but not oriented).

beta_move_10

UNZIP is not a move in graphic lambda calculus.

__________________________

Return to Tutorial:Graphic lambda calculus

Advertisements

27 thoughts on “The graphic beta move, with details”

  1. Pingback: chorasimilarity

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s