Connecting $3$-manifold triangulations with monotonic sequences of elementary moves

The most well-known elementary moves are the Pachner moves (also often called bistellar flips). For $3$-dimensional triangulations, the four Pachner moves—illustrated in Figures 1 and 2—are:

• •

  the 2-3 move, which replaces two distinct tetrahedra attached along a triangular face with three distinct tetrahedra attached around an edge;

• •

  the 3-2 move, which is the inverse of the 2-3 move;

• •

  the 1-4 move, which subdivides a single tetrahedron into four distinct tetrahedra attached around a vertex; and

• •

  the 4-1 move, which is the inverse of the 1-4 move.

Pachner showed that any two triangulations of the same $3$-manifold are connected by a finite sequence of these moves [17].

Notice that the 2-3 and 3-2 moves do not change the number of vertices, and also that these moves can only be performed on a triangulation with at least two tetrahedra. In fact, if we restrict our attention to one-vertex triangulations with at least two tetrahedra, then only 2-3 and 3-2 moves are necessary to connect any two such triangulations of the same $3$-manifold; this was proven independently by Matveev [15, p. 29] and Piergallini [18]. Moreover, as we discuss in Section 2.2, the Matveev-Piergallini theorem extends to more general settings than just one-vertex triangulations of compact $3$-manifolds [2, 3, 1].

With this in mind, recall that we often rely on invariants to give a “no” answer to the homeomorphism problem. The Matveev-Piergallini theorem provides a natural way to prove that a particular object associated to a triangulation is actually an invariant: prove that this object is preserved by 2-3 moves. Indeed, a number of $3$-manifold invariants have been established using 2-3 moves and/or similar moves on triangulations; for example, see [11, 23].

On the other hand, one way to give a “yes” answer to the homeomorphism problem is to find a sequence of elementary moves that connects the two input triangulations. For well-structured $3$-manifolds such as Seifert fibre spaces or cusped hyperbolic manifolds, this is not the most efficient method, because we have access to specialised recognition algorithms [15, 16, 24]. However, for arbitrary $3$-manifolds, performing a computationally expensive search for a sequence of elementary moves is currently the best technique available.

Beyond Pachner moves, it is often useful to include other elementary moves in our toolbox. In particular, the following moves are quite widely-used:

• •

  the 0-2 move, which “fattens up” a pair of adjacent triangles into a pair of tetrahedra attached around an edge; and

• •

  the 2-0 move, which is the inverse of the 2-0 move.

These moves are illustrated in Figure 3. The 0-2 and 2-0 moves can be found under various names in other sources [1, 14, 15, 18, 19]. The 0-2 move always preserves the underlying $3$-manifold. The same is true for the 2-0 move provided some simple conditions are satsified; we discuss this in more detail at the end of Section 2.2.

As we saw above, elementary moves—in particular, connectivity results like the Matveev-Piergallini theorem—play an important role in both theoretical and practical applications in computational $3$-manifold topology. However, a drawback of the Matveev-Piergallini theorem is that it only says that some sequence of 2-3 and 3-2 moves exists, and says nothing about what this sequence actually looks like. From a theoretical perspective, knowing more about the structure of the sequence could simplify proofs; from a practical perspective, we could potentially exploit any extra structure to perform a targeted search for a sequence of elementary moves, instead of relying on a brute-force search.

In this paper, we study sequences of moves that are monotonic in the sense that they break up into two parts:

• •

  first, a (monotonic) ascent which consists only of moves that increase the number of tetrahedra (such as 2-3 or 0-2 moves); and

• •

  second, a (monotonic) descent which consists only of moves that decrease the number of tetrahedra (such as 3-2 or 2-0 moves).

A very natural question to ask is whether two one-vertex triangulations of the same $3$-manifold are always connected by a monotonic sequence of 2-3 and 3-2 moves (that is, a sequence consisting of an ascent via 2-3 moves followed by a descent via 3-2 moves); later on, we give a more general and more precise statement in Conjecture 8. In Section 4, we give some experimental evidence that Conjecture 8 may be true.

Our main result in this paper (Theorem 9) is that if we restrict our attention to one-vertex triangulations with at least two tetrahedra, then any two such triangulations of the same $3$-manifold are connected by a monotonic sequence of 2-3 and 2-0 moves; that is, the descent uses 2-0 moves, rather than 3-2 moves. Alternatively, we could follow the sequence backwards to obtain a monotonic sequence of 0-2 and 3-2 moves. (Actually, just as the Matveev-Piergallini theorem extends to more general settings, our main result also extends to these more general settings.) Most of Section 3 is devoted to proving Theorem 9; we also briefly discuss how our proof technique could potentially extend to a proof of Conjecture 8.

As mentioned earlier, we study the characteristics of monotonic sequences experimentally in Section 4. Specifically, we implemented algorithms to search for both unstructured and monotonic sequences that connect one-vertex triangulations of the same $3$-manifold; we tested these algorithms on 2984 distinct $3$-manifolds, which produced over 200 million intermediate triangulations. The results suggest that, despite its poorer theoretical bounds, a blind search for an unstructured sequence gives better practical performance due to requiring fewer additional tetrahedra in intermediate triangulations.

We finish this introduction by mentioning a couple of related results that have previously appeared in the literature:

• •

  There has been some previous attention given to monotonic sequences, though using different terminology. Specifically, in a 1999 paper [13], Makovetskii studied monotonic sequences involving 2-3, 0-2, 3-2 and 2-0 moves (where the moves could occur in any order, as long as all the 2-3 and 0-2 moves occur before all the 3-2 and 2-0 moves). Our proof of Theorem 9 was conducted independently, before we became aware of Makovetskii’s work. Makovetskii’s paper is rather terse and contains some omissions, but a high-level comparison indicates that there are some similarities between our proof strategy and that of Makovetskii. As we discuss in Section 3.1, our proof is heavily influenced by work of Matveev [15]; this common influence is the source of at least some of the similarity with Makovetskii’s work. In any case, we were able to contribute enough new insight to obtain a substantially stronger result.

• •

  A similar philosophy has previously been applied to Reidemeister moves for links in the $3$-sphere. Specifically, Coward showed [10] that any two diagrams of a link can be related by a sequence of Reidemeister moves sorted in the following order:

  1. (1)

     Reidemeister I moves that increase the number of crossings.

  2. (2)

     Reidemeister II moves that increase the number of crossings.

  3. (3)

     Reidemeister III moves (which preserve the number of crossings).

  4. (4)

     Reidemeister II moves that decrease the number of crossings.

Triangulations and special spines give two dual ways to represent a $3$-manifold. Here, we define these dual notions, and describe how to convert between them. Much of our discussion is based on that in [15] and [19], though we omit the details of some proofs.

A (generalised) triangulation $\mathcal{T}$ is a collection of $n$ tetrahedra, such that each of the $4n$ triangular faces is affinely identified with one of the other triangular faces; intuitively, the $n$ tetrahedra have been “glued together” along their faces to form a $3$-dimensional complex. Each pair of identified faces is referred to as a single face of the triangulation. Since the face identifications cause many tetrahedron edges to be identified and many tetrahedron vertices to be identified, we also define an edge of the triangulation to be an equivalence class of identified tetrahedron edges, and a vertex of the triangulation to be an equivalence class of identified tetrahedron vertices. Here we allow multiple edges of the same tetrahedron to be identified, and we allow multiple vertices of the same tetrahedron to be identified.

We call $\mathcal{T}$ a 3-manifold triangulation if its underlying topological space is a (compact) $3$-manifold. In the definition we gave above, we did not allow any faces of tetrahedra to be left unglued; thus, for the purposes of this paper, a $3$-manifold triangulation must represent a closed $3$-manifold (i.e., a compact $3$-manifold without boundary). Also, note that a generalised triangulation $\mathcal{T}$ need not be a $3$-manifold triangulation, because it may contain “singularities” at midpoints of edges and at vertices. Depending on the face identifications that make up $\mathcal{T}$, there are two possibilities for an edge $e$.

• •

  If $e$ is identified with itself in reverse, then every small neighbourhood of the midpoint of $e$ will be bounded by a projective plane. In this case, the midpoint of $e$ is a singularity, and $\mathcal{T}$ is not a $3$-manifold triangulation.

• •

  Otherwise, every interior point of $e$ will have a small neighbourhood bounded by a sphere, in which case the edge does not produce a singularity.

Throughout this paper, we will tacitly assume that no edge is identified with itself in reverse, so that singularities only occur at the vertices of a triangulation.

To see what can happen at a vertex $v$, imagine introducing a small triangle near each tetrahedron vertex that is incident with $v$. As illustrated in Figure 4, we can glue all these triangles together to form a closed surface called the link of $v$. If the link is a $2$-sphere, then $v$ is not a singularity, and we call $v$ an internal vertex; otherwise, we call $v$ an ideal vertex. A triangulation that satisfies the edge condition above is a $3$-manifold triangulation if and only if every vertex is internal.

The motivation for working with these generalised $3$-manifold triangulations is that they tend to be smaller, and hence better suited to computation, than simplicial complexes. In particular, every $3$-manifold admits a one-vertex triangulation: an $n$-tetrahedron triangulation in which all $4n$ tetrahedron vertices are identified to become a single vertex.

Generalised triangulations also give us the flexibility to work with ideal triangulations: triangulations that have one or more ideal vertices. Although the underlying topological space of an ideal triangulation $\mathcal{T}$ is not a $3$-manifold, we can recover a bounded $3$-manifold (i.e., a compact $3$-manifold with non-empty boundary) $\mathcal{M}$ by deleting a small open regular neighbourhood of the ideal vertices of $\mathcal{T}$; we say that $\mathcal{T}$ is an ideal triangulation of $\mathcal{M}$, and that $\mathcal{M}$ is obtained from $\mathcal{T}$ by truncating the ideal vertices. (Alternatively, it is also common to recover a non-compact $3$-manifold by deleting, rather than truncating, the ideal vertices; we do not use this idea in this paper.) The idea for such ideal triangulations originated with Thurston’s famous two-tetrahedron ideal triangulation of the figure-eight knot complement (see [21] or [22, Example 1.4.8]). Ideal triangulations are often useful for computation because they typically require fewer tetrahedra than non-ideal triangulations of the same bounded $3$-manifold (such non-ideal triangulations can be obtained by allowing some faces of some tetrahedra to be left unglued).

As mentioned earlier, we can also represent $3$-manifolds using the dual notion of a special spine, which is essentially a $2$-dimensional complex that captures all the topological information in a $3$-dimensional manifold. Before defining special spines precisely, it helps to get an intuitive feel for these objects by reviewing the procedure for turning a triangulation into its dual special spine.

We start by defining a $2$-dimensional configuration called a butterfly that dualises the combinatorics of a tetrahedron. Specifically, a butterfly consists of four arcs that meet at a central vertex, with a $2$-dimensional “wing” attached to each of the six possible pairs of arcs, as shown in Figure 5(a); the four arcs are dual to the four triangular faces of a tetrahedron, and the six wings are dual to the six edges of a tetrahedron. To turn a triangulation into its dual spine, replace each tetrahedron with its dual butterfly; as illustrated in Figure 5(b), the face-gluings of the triangulation induce a natural way to attach all the dual butterflies together to form the dual spine.

It is not difficult to see that the dual spines constructed in this way are always a type of $2$-dimensional complex called a special polyhedron, which we characterise via the following two definitions:

As we hinted earlier, a special spine of a $3$-manifold $\mathcal{M}$ is a special polyhedron that is embedded in $\mathcal{M}$ in such a way that it captures all the topological information in $\mathcal{M}$. The following is a precise characterisation of this idea:

Consider a compact $3$-manifold $\mathcal{M}$ with no $2$-sphere boundary components (recall Remark 1). If $\mathcal{M}$ is closed, let $\mathcal{T}$ be a corresponding $3$-manifold triangulation; otherwise, if $\mathcal{M}$ is bounded, let $\mathcal{T}$ be an ideal triangulation of $\mathcal{M}$. Following the construction described earlier, take $P$ to be the dual spine of $\mathcal{T}$. To see that $P$ is indeed a special spine for $\mathcal{M}$, observe that taking a small open regular neighbourhood of the internal vertices of $\mathcal{T}$ gives precisely the required choice $Z$ of open balls in $\mathcal{M}$. Going in the other direction, a special spine $P$ also determines a unique corresponding dual triangulation (see [15, pp. 10–13] for a proof of this); this justifies the use of the term “dual” to describe this relationship between triangulations and special spines.

As mentioned in Section 1.1, the 2-3 and 3-2 moves are local moves that modify a triangulation without changing its topology. Recall also that, modulo some mild necessary conditions, two homeomorphic triangulations are always connected by a sequence of 2-3 and 3-2 moves. This was first proven in the special case of one-vertex triangulations of closed $3$-manifolds:

This was extended to triangulations of closed $3$-manifolds with any number of vertices by Benedetti and Petronio [2, 3], and subsequently also extended to ideal triangulations of bounded $3$-manifolds by Amendola [1]. To state the most general version of Theorem 5, and also to state our main result in this paper later on, we use the following notation:

Theorems 5 and 7 were originally stated and proved in the dual setting of special spines; a proof of Theorem 7 can also be found in [19]. One advantage of working with special spines is that it is often easier to visualise long sequences of moves in this setting. With this in mind, we devote the remainder of this section to describing 2-3, 3-2, 0-2 and 2-0 moves on special spines.

Recall that in a triangulation, a 2-3 move takes a pair of tetrahedra that are joined along a triangular face, and replaces them with three tetrahedra attached around a common edge. In the dual special spine, the corresponding 2-3 move takes a pair of vertices that are connected by an edge, and replaces them with three vertices that form the vertices of a triangular face. Figure 7 illustrates the 2-3 and 3-2 moves in a way that emphasises the duality between the triangulation and special spine settings.

For our purposes, it will be helpful to use a different visualisation of 2-3 moves in the special spine setting. Specifically, let $P$ be a special spine for a $3$-manifold $\mathcal{M}$, and consider an edge $e$ that connects two distinct vertices in $P$. Imagine taking a sheet attached to one endpoint of $e$, and dragging this sheet along $e$ until it crosses the other endpoint, as shown in Figure 8(a); up to ambient isotopy of $P$ in $\mathcal{M}$, this operation is equivalent to performing a 2-3 move on the vertices that form the endpoints of $e$. When visualising 2-3 moves in this way, we will often simplify our drawings by omitting the sheet that gets dragged along $e$, as shown in Figure 8(b).

For 0-2 moves, recall that in a triangulation, such a move takes a pair of triangular faces that share a common edge, and “fattens up” these triangles into a pair of tetrahedra attached around a new edge. In the dual special spine, the corresponding 0-2 move takes a pair of edges that are both incident to a common face, and creates a pair of vertices that together form the vertices of a new bigon face. Figure 9 illustrates the 0-2 and 2-0 moves in a way that emphasises the duality between the triangulation and special spine settings.

As with 2-3 moves, we will find it helpful to use a different visualisation of 0-2 moves in the special spine setting. In detail, let $P$ be a special spine for a $3$-manifold $\mathcal{M}$, and consider a curve $\alpha$ embedded in a face $C$ of $P$ such that the endpoints of $\alpha$ lie on edges of $C$. Imagine taking a sheet attached to one endpoint of $\alpha$, and dragging this sheet along $\alpha$ until it crosses the other endpoint, as shown in Figure 10(a); up to ambient isotopy of $P$ in $\mathcal{M}$, this operation is equivalent to performing a 0-2 move on the pair of edges incident to the endpoints of $\alpha$. We will often simplify our drawings of such 0-2 moves by omitting the sheet that gets dragged along $\alpha$, as shown in Figure 10(b).

It is straightforward to check that performing a 0-2 move on a special spine always yields a new special spine of the same $3$-manifold. However, performing a 2-0 move on a special spine is not guaranteed to produce a special spine. To see why, let $P_{0}$ and $P_{2}$ denote the spines on the left and right, respectively, of Figure 10(a). Even if $P_{2}$ is special, it is possible for $P_{0}$ to be non-special in one of the following ways:

1. (a)

   Suppose the two faces $C^{\prime}$ and $C^{\prime\prime}$ coincide to form a single disc. In this case, the face $C$ must be either an annulus or a Möbius band, so $P_{0}$ cannot be special.

2. (b)

   Suppose the two faces $C^{\prime}$ and $C^{\prime\prime}$ form two distinct discs, but the two vertices shown in Figure 10(a) are the only vertices incident to either $C^{\prime}$ or $C^{\prime\prime}$. In this case, the face $C$ must be a single disc whose boundary contains no vertices, so again $P_{0}$ cannot be special.

We need to rule out these two degenerate cases to ensure that a 2-0 move preserves the property of being a special spine.

Translating this into the dual triangulation setting, we can perform a 2-0 move about an edge $e$ in a triangulation $\mathcal{T}$ (with the restriction that the result is a triangulation homeomorphic to $\mathcal{T}$) if and only if the following conditions are all satisfied:

• •

  The edge $e$ has degree two (i.e., as an equivalence class of tetrahedron edges, $e$ is formed from exactly two tetrahedron edges), and is incident to two distinct tetrahedra $\Delta^{\prime}$ and $\Delta^{\prime\prime}$. (In the dual special spine setting, this corresponds to the fact that a 2-0 move can only be performed on a bigon face that meets two distinct vertices.)

• •

  Let $\varepsilon^{\prime}$ denote the edge of $\Delta^{\prime}$ opposite $e$, and let $\varepsilon^{\prime\prime}$ denote the edge of $\Delta^{\prime\prime}$ opposite $e$. The edges $\varepsilon^{\prime}$ and $\varepsilon^{\prime\prime}$ must be distinct. (This is dual to ruling out case (a).)

• •

  Let $f^{\prime}$ and $g^{\prime}$ denote the two faces of $\Delta^{\prime}$ that share the common edge $\varepsilon^{\prime}$, and let $f^{\prime\prime}$ and $g^{\prime\prime}$ denote the two faces of $\Delta^{\prime\prime}$ that share the common edge $\varepsilon^{\prime\prime}$. We cannot simultaneously have $f^{\prime}$ identified to $g^{\prime}$ and $f^{\prime\prime}$ identified to $g^{\prime\prime}$. (This is dual to ruling out case (b).)

Our proof of Theorem 9, which we present in Section 3.2, uses a variation of a technique from Matveev’s proof of Theorem 5. The construction at the heart of this technique is Matveev’s arch-with-membrane; for brevity, we will simply refer to an arch-with-membrane as an arch.¹¹1 Matveev uses the word “arch” to describe a slightly different construction from the arch-with-membrane. For our purposes, there is no risk of confusion because we will only need to work with the arch-with-membrane. We have two goals in this section.

• •

  First, we introduce some terminology that will help us describe and work with arches.

• •

  Second, we use this terminology to paraphrase some key ideas from Matveev’s proof, since we will be reusing these ideas in Section 3.2.

To describe how we construct arches, we first define a sort of precursor to an arch. For this, let $\mathcal{M}$ be a $3$-manifold with no $2$-sphere boundary components, and consider any particular special spine $P$ for $\mathcal{M}$. A wall for $P$ is an embedding of the rectangle $[0,1]\times[0,1]$ into $\mathcal{M}$ such that:

• •

  the intersection of the rectangle with $P$ is given by the curve $[0,1]\times\{0\}$—we call this curve the base of the wall;

• •

  the base of the wall only ever meets the singular graph $S_{P}$ via transverse intersections of $(0,1)\times\{0\}$ with edges of $P$—we call each such point of intersection a buttress of the wall; and

• •

  there is at least one buttress.

The length $\ell$ of the wall is given by the number of buttresses minus one; we (arbitrarily) orient the base of the wall, and label the buttresses from $0$ to $\ell$ in the order that they appear along the base. Figure 11 shows an example of a wall of length $4$.

We first describe how to construct an arch of length $0$. Let $b_{0}$ denote the \nth0 buttress of a wall $W$, and focus on a small neighbourhood $N$ of $b_{0}$ inside $\mathcal{M}$. On the edge containing $b_{0}$, consider two points $p$ and $p^{\prime}$ that lie on either side of $b_{0}$; inside $N$, let $\alpha$ denote a curve from $p$ to $p^{\prime}$ that lies in the face that only meets $W$ at the buttress $b_{0}$. We construct a length-$0$ arch by performing a 0-2 move along $\alpha$; this is more easily visualised by first performing an isotopy of the spine, as illustrated in Figure 12. We usually simplify our drawings of arches (of any length, not just of length $0$), as shown in Figure 13.

By creating a length-$0$ arch, we introduce two new faces into our spine:

• •

  a new monogon, which we call the artificial monogon; and

• •

  a new bigon (shaded grey in Figure 13), which we call the artificial membrane.

Very shortly, we will describe how to construct arches of arbitrary positive length $\ell$; for such arches, the artificial membrane will be an $(\ell+2)$-gon, rather than a bigon. To go along with this terminology, we will call an edge of our spine artificial if it is incident to either the artificial membrane or the artificial monogon; otherwise, we will call the edge natural.

To construct an arch of positive length $\ell$, start with a wall $W$ of length $\ell$. As above, use a 0-2 move to create an arch of length $0$. We extend this arch to length $\ell$ using the following two steps:

1. (1)

   Perform a sequence of $\ell$ 0-2 moves along the base of the wall $W$.

2. (2)

   Perform a sequence of $\ell$ 3-2 moves to turn the artificial membrane into an $(\ell+2)$-gon.

Figure 14 illustrates this extension procedure for the case $\ell=4$.

Creating an arch on a spine $P$ is useful because doing so has “minimal impact” on the structure of $P$. To pin down this intuition, let $W$ denote a wall of length $\ell$ for $P$, and let $Q$ denote the spine obtained by using $W$ to add an arch of length $\ell$ to $P$. For each vertex $v$ of $Q$, we classify this vertex into one of the following types:

• •

  Call $v$ an artificial vertex if it is incident to both the artificial membrane and the artificial monogon; there is exactly one such vertex.

• •

  Call $v$ a subdividing vertex if it is incident to the artificial membrane, but not incident to the artificial monogon; there are exactly $\ell+1$ such vertices.

• •

  Call $v$ a natural vertex if it is incident to neither the artificial membrane nor the artificial monogon.

Observe that there is a natural bijection between the vertices of $P$ and the natural vertices of $Q$; there is also a natural bijection between the buttresses of $W$ and the subdividing vertices of $Q$.

With this in mind, consider the singular graphs $S_{Q}$ and $S_{P}$. Observe that after deleting the artificial vertex and the artificial edges from $S_{Q}$, we obtain a new graph $G_{Q}$ that is a subdivision of $S_{P}$:

• •

  every vertex in $S_{P}$ corresponds to a natural vertex in $G_{Q}$; and

• •

  every edge in $S_{P}$ corresponds to a “chain” of edges in $G_{Q}$ that starts at a natural vertex, possibly passes through one or more subdividing vertices, and ends at a natural vertex.

Intuitively, if we “ignore” the artificial vertex and artificial edges, then the singular graphs $S_{Q}$ and $S_{P}$ can be considered “more-or-less equivalent”; thus, we can think of the spine $Q$ as being “just like $P$, but with an extra arch”.

We now outline how Matveev uses arches in his proof of Theorem 5 (see [15] for more details), since a similar idea will be useful for us in Section 3.2. Here, we rephrase Matveev’s idea in a way that is better suited to our purposes. Prior to proving Theorem 5, Matveev establishes the following (non-trivial) facts:

• •

  A 0-2 move on a special spine can be replaced by a sequence (not necessarily monotonic) of 2-3 and/or 3-2 moves. Going backwards, if a 2-0 move results in a special spine, then it can be replaced by a sequence of 2-3 and/or 3-2 moves.

• •

  If $P$ and $Q$ are special spines of the same $3$-manifold, each with at least two vertices, then $P$ is connected to $Q$ by a sequence $\varSigma$ of 2-3, 3-2, 0-2 and/or 2-0 moves.

From here, Matveev proceeds by turning the sequence $\varSigma$ into a new sequence that only uses 2-3 and 3-2 moves.

Although the 0-2 moves in $\varSigma$ can always be replaced by 2-3 and 3-2 moves, we might not be able to replace all of the 2-0 moves, because a 2-0 move could yield a spine that is not special. Matveev circumvents this issue by creating an arch every time a 2-0 move is supposed to be performed. To see how this works, consider a 2-0 move $\vartheta$ that turns a spine $P$ into another spine $Q$. Instead of performing the move $\vartheta$, we can perform the 2-3 move illustrated in Figure 15, which turns $P$ into a spine that is just like $Q$ except it has an extra arch of length $1$. Note that this 2-3 move is always possible, since we must initially have two distinct vertices to perform the 2-0 move $\vartheta$. (In [15], Matveev actually creates the arch using a 0-2 move followed by a 3-2 move. Our 2-3 move gives the same result, but is more useful for our purposes in Section 3.2.)

As we have already mentioned, Matveev’s idea is to replace every 2-0 move by creating an arch in the manner just described. The extra arches that arise in this way can be moved around quite freely using 2-3, 3-2 and 0-2 moves, so that they never prevent us from performing any of the 2-3, 3-2 and 0-2 moves in $\varSigma$; the specific details are unimportant here, but it is worth noting that we rely on a slight variation of this idea in Section 3.2. At the end, we can use Observation 10 to remove all the extra arches using 2-3 and 2-0 moves; it is not hard to see that every intermediate spine in this removal process must be special, which means that the 2-0 moves can be realised by 2-3 and 3-2 moves. In this way, Matveev turns $\varSigma$ into a sequence consisting only of 2-3 and 3-2 moves.

In this section, we prove Theorem 9 by giving a procedure for transforming a non-monotonic sequence into a monotonic one. At the end, we also briefly discuss what would be required to adapt this strategy to prove Conjecture 8.

To begin, we use the ideas discussed in Section 3.1 to prove Lemma 11 below. We then use this lemma to prove Theorem 9.

• Proof.

  Let $Q_{0}$ denote the spine obtained from $P$ by applying the 3-2 move $\gamma$, and for each $i\in\{1,\ldots,k\}$ let $Q_{i}$ denote the spine obtained from $Q_{i-1}$ by applying the 2-3 move $\delta_{i}$ (so, in particular, $Q_{k}=Q$). Our strategy is to show that there is a sequence $P_{0},\ldots,P_{k}$ of spines such that:

  • –

    for each $i\in\{0,\ldots,k\}$, $P_{i}$ looks just like $Q_{i}$ but with an extra arch;

  • –

    $P$ can be transformed into $P_{0}$ using two 2-3 moves; and

  • –

    for each $j\in\{1,\ldots,k\}$, $P_{j-1}$ can be transformed into $P_{j}$ using some finite sequence of 2-3 moves.

  Once we have such a sequence, we can complete the proof by using Observation 10 to remove the extra arch in $P_{k}$, and hence transform $P_{k}$ into $Q$ using a monotonic sequence of 2-3 and 2-0 moves.

  To construct the sequence $P_{0},\ldots,P_{k}$, we proceed by induction on $k$. When $k=0$, all we need to show is that we can use two 2-3 moves to turn $P$ into a new spine $P_{0}$ that looks like $Q_{0}$ with an extra arch. In other words, at the cost of introducing an arch, we need to “copy” the 3-2 move $\gamma$ using two 2-3 moves; we can do this in the manner illustrated in Figure 16.

  

Before we describe the inductive step, it is helpful to consider an explicit example with $k=1$. Specifically, consider the 3-2 move $\gamma$ and the 2-3 move $\delta_{1}$ shown in Figure 17. After “copying” $\gamma$ using two 2-3 moves, we would like to “copy” $\delta_{1}$. However, $\delta_{1}$ is initially obstructed by the extra arch that we created when we “copied” $\gamma$. To circumvent this, we simply use an additional 2-3 move to shift the arch out of the way, which then allows us to perform a 2-3 move identical to $\delta_{1}$. This captures the essence of our proof: once we have “copied” the initial 3-2 move $\gamma$, we can always “copy” the remaining 2-3 moves $\delta_{1},\ldots,\delta_{k}$, using additional 2-3 moves to shift the arch whenever necessary.

With this idea in mind, let $k\geqslant 1$ and suppose we have constructed a suitable sequence $P_{0},\ldots,P_{k-1}$. We need to construct a new spine $P_{k}$ such that:

• –

  $P_{k}$ looks just like $Q_{k}$ but with an extra arch; and

• –

  $P_{k-1}$ can be transformed into $P_{k}$ using 2-3 moves.

For this, we know that $Q_{k-1}$ can be turned into $Q_{k}$ using a single 2-3 move $\delta_{k}$, and we also know that $P_{k-1}$ looks like $Q_{k-1}$ with an extra arch. In the singular graph $S_{Q_{k-1}}$, consider the edge $e$ along which we perform $\delta_{k}$. Recall from Section 3.1 that $e$ corresponds to a chain of edges in $S_{P_{k-1}}$ such that:

• –

  the chain starts and ends at natural vertices; and

• –

  every intermediate vertex in the chain is a subdividing vertex.

Each subdividing vertex corresponds to a point at which the arch obstructs the 2-3 move $\delta_{k}$. Thus, following the idea described above, we first need to shift the arch out of the way using 2-3 moves; we only require one 2-3 move for each subdividing vertex. After removing all the subdividing vertices in this way, we can obtain the required spine $P_{k}$ using a 2-3 move identical to $\delta_{k}$.

By induction, this completes the construction of a sequence of 2-3 moves that transforms $P$ into a new spine $P_{k}$. As explained at the beginning of the proof, all that remains is to turn $P_{k}$ into $Q$ using a monotonic sequence of 2-3 and 2-0 moves. Since $P_{k}$ looks just like $Q$ but with an extra arch, we can achieve this by removing the arch according to Observation 10. ∎

See 9

• Proof.

  Throughout this proof, call a sequence $\varSigma$ of 2-3, 3-2 and 2-0 moves benign if it consists of two parts: an arbitrary sequence of 2-3 and 3-2 moves, followed by a (possibly empty) sequence of 2-0 moves. Thus, a monotonic sequence of 2-3 and 2-0 moves is just a benign sequence with no 3-2 moves. With this in mind, the idea of this proof is to turn a benign sequence into a monotonic sequence by repeatedly applying Lemma 11 to reduce the number of 3-2 moves.

  To do this, let $P$ be the special spine dual to $\mathcal{T}$, and let $Q$ be the special spine dual to $\mathcal{U}$. By Amendola’s result (Theorem 7), we know that $P$ is connected to $Q$ by a sequence of 2-3 and 3-2 moves. Denote this sequence by $\varSigma_{m}$, where $m$ is the number of 3-2 moves in this sequence; there is nothing to prove if $m=0$, so we may assume that $m\geqslant 1$ for the rest of this proof. Since $\varSigma_{m}$ is a benign sequence (with no 2-0 moves), we can use it as the starting point for our construction.

  To inductively reduce the number of 3-2 moves in our benign sequence, fix any particular $i\in\{1,\ldots,m\}$, and suppose we have constructed a benign sequence $\varSigma_{i}$ such that:

  • –

    $\varSigma_{i}$ transforms $P$ into $Q$; and

  • –

    $\varSigma_{i}$ includes exactly $i$ 3-2 moves.

  Let $\gamma$ denote the last 3-2 move in $\varSigma_{i}$. Because $\varSigma_{i}$ is benign, $\gamma$ must be followed immediately by 2-3 moves $\delta_{1},\ldots,\delta_{k}$, for some $k\geqslant 0$; these 2-3 moves must then be followed immediately by the sequence of 2-0 moves at the end of $\varSigma_{i}$. By Lemma 11, we can replace the sequence $\gamma,\delta_{1},\ldots,\delta_{k}$ with a monotonic sequence of 2-3 and 2-0 moves; this produces a benign sequence $\varSigma_{i-1}$ with $(i-1)$ 3-2 moves.

  At the end of this inductive construction, we therefore obtain a benign sequence $\varSigma_{0}$ with no 3-2 moves. As observed earlier, this means that $\varSigma_{0}$ is a monotonic sequence of 2-3 and 2-0 moves that transforms $P$ into $Q$; by duality, this proves the theorem for the triangulations $\mathcal{T}$ and $\mathcal{U}$. ∎

To conclude this section, we briefly discuss Conjecture 8. The only difference between this conjecture and Theorem 9 is that we seek a monotonic sequence of 2-3 and 3-2 moves, rather than a monotonic sequence of 2-3 and 2-0 moves. Given this similarity, it is natural to wonder whether a similar proof strategy could work to prove Conjecture 8.

Going back through the proof of Theorem 9, and in particular the proof of Lemma 11, we see that the only place where we use 2-0 moves is when we remove arches according to Observation 10. Thus, one possible way to prove Conjecture 8 would be to establish the following:

In contrast to Observation 10, which follows immediately from our construction of arches, Conjecture 12 appears to be rather difficult to prove.