Thursday, August 1, 2013

Mutating completely foldable triangulations

If we have a completely foldable (CF) triangulation in hand, we might be able to mutate it into another CF triangulation by making local "moves" that preserve its tricolorability.

It is known that a sequence of Pachner moves (a.k.a., bistellar flips) connect any two triangulations of the same surface.

The three Pachner moves are:

flip22 = rotate the edge shared by two triangles (this move is self-inverse.)
flip13 = trisection one triangle into three triangles by adding one vertex and three edges to its interior.
flip31 = weld together the three triangles around a trivalent vertex by removing the vertex and its three incident edges (this is the inverse of flip13.)

None of the Pachner moves preserve the tricolorability of a triangulation by themselves. Rotate creates four non-Eulerian vertices when applied to a triangulation that is already tricolorable. Trisection does the same. Weld cannot even be applied to a tricolorable triangulation since it needs a trivalent vertex. 

The tricolorability-preserving mutation we are looking for, if it exists, must be expressible as a composition of Pachner moves.

There are nine possible 2-move compositions of Pachner moves, and these may have variations depending on which edge or triangle we choose operate on in the second move.

We can immediately eliminate the 2-move compositions that begin with weld since there are no trivalent vertices to be found in a triangulation that is tricolorable. For like reasons, we can eliminate the 2-move compositions that end with trisection since this would leave us with a trivalent vertex in the triangulation making it non-tricolorable.

The three remaining possibilities are:

rr: rotate-then-rotate: an identity when the same edge is operated on in the second move; the first rotation creates four non-Eulerian vertices and there is simply no way to repair them all with a subsequent rotation of any other edge.

rw: rotate-then-weld: this fails in the general case because there is no guarantee that the edge rotation of the first move will produce a trivalent vertex to weld in the second move. The special cases when an edge rotation produces a trivalent vertex are: I, when at least one of the vertices the edge rotates away from has valence 4, and II, when at least one of the vertices the edge rotates toward has valence 2.

tr: trisection-then-rotate: this works any time the rotation acts on one of the three edges created in the first move. Rotating some other edge in the second move would leave a trivalent vertex from the first move, making the triangulation non-tricolorable.

tw: trisection then weld: this is an identity since the only trivalent vertex available to weld is the one created in he first move.

So the only 2-move composition of Pachner moves that preserves tricolorability is tr, more explicitly, "trisection a triangle, then rotate one of the new edges." The action of tr is to increase the count of vertices by 1, faces by 2, and edges by 3.

In visual terms, tr parallellizes an edge and then separates the two parallel edges with a bisected edge.

With hindsight we can construct an inverse for tr from special case II of rw as follows. If any vertex in a triangulation has valence 2, it must lie between two parallel edges (else its incident faces could not both be triangles.) Finding such a 2-valent vertex, we can rotate either of its opposing parallel edges, making said vertex 3-valent, and then remove the vertex with weld. Note that this rw acts as the inverse of tr regardless of which of the two opposing parallels gets rotated and ultimately removed.

That gives us tr, which can grow a tricolorable triangulation, and rw, which can shrink one, leaving us still in the hunt for a mutation that can interconvert tricolorable triangulations of the same size.

What tr means physically is that we slit open one edge of the triangulation (creating the two parallel edges) and repair the wound by gluing on a triangular envelope that has been likewise slit open one on edge. The net result is that we have joined a triangular "ear" to the surface. The 2-valent vertex is the point of the ear. Inversely, rw finds such an ear and removes it.

Clearly, slit-and-join is a general technique we can use to compose any two completely foldable triangulations (CFT's) along a doubled common edge. If we imagine this surgery occurring when both CFT's are completely folded, the final move is simply to fold on the coincident common edges so that we once again have a single triangle.

No comments: