# Bounds for the number of moves between pants decompositions, and between
triangulations

Marc Lackenby, Mehdi Yazdi

###### Abstract.

Given two pants decompositions of a compact orientable surface $S$, we give an
upper bound for their distance in the pants graph that depends logarithmically
on their intersection number and polynomially on the Euler characteristic of
$S$. As a consequence, we find an upper bound on the volume of the convex core
of a maximal cusp (which is a hyperbolic structures on $S\times\mathbb{R}$
where given pants decompositions of the conformal boundary are pinched to
annular cusps). As a further application, we give an upper bound for the
Weil–Petersson distance between two points in the Teichmüller space of $S$ in
terms of their corresponding short pants decompositions. Similarly, given two
one-vertex triangulations of $S$, we give an upper bound for the number of
flips and twist maps needed to convert one triangulation into the other. The
proofs rely on using pre-triangulations, train tracks, and an algorithm of
Agol, Hass, and Thurston.

##  1\. Introduction

###  1.1. Pants decompositions

Let $S$ be a compact orientable surface. An _essential_ curve on $S$ is a
homotopically non-trivial and non-boundary-parallel simple closed curve. The
_curve graph_ $\mathcal{C}(S)$ of $S$, defined by Harvey [Har81], is a
simplicial graph whose vertices are isotopy classes of essential simple closed
curves on $S$, and with two vertices joined by an edge if their simple closed
curves are disjoint up to isotopy. Hempel’s Lemma [Hem01] states that the
distance between two simple closed curves $\alpha$ and $\beta$ in the curve
graph of $S$ is at most a logarithmic function of their geometric intersection
number, namely $2\log_{2}i(\alpha,\beta)+2$.

A _pants decomposition_ of $S$ is a maximal collection of disjoint, pairwise
non-parallel, essential simple closed curves on $S$ up to isotopy. The _pants
graph_ $\mathcal{P}(S)$ of $S$, defined by Hatcher and Thurston [HT80], is a
simplicial graph whose vertices are pants decompositions of $S$, with two
vertices joined by an edge if their pants decompositions are related by one
_simple_ or _associativity_ move as in Figure 1. Hatcher and Thurston showed
that the pants graph is connected. The pants graph is intimately related to
hyperbolic geometry in dimensions two and three. For example, Brock [Bro03]
showed that the Teichmüller space of $S$ equipped with the Weil–Petersson
metric is quasi-isometric to the pants graph of $S$, with the quasi-isometry
map sending a marked hyperbolic metric to one of its _short_ pants
decompositions (i.e. each curve in the pants decomposition being shorter than
the _Bers constant_).

Figure 1. The edges of the pants graph correspond to simple moves (left) and
associativity moves (right). In each case, the red curve is replaced with the
blue curve, and the remaining curves are unchanged.

In light of Hempel’s Lemma, a natural question is whether there is an upper
bound for the distance between two arbitrary pants decompositions $P$ and
$P^{\prime}$ in the pants graph that depends logarithmically on the geometric
intersection number $i(P,P^{\prime})$ and polynomially on the Euler
characteristic $\chi(S)$ of $S$. A first attempt would be to try to adapt the
proof of Hempel’s Lemma to the context of pants decompositions. The proof that
we have in mind uses a surgery trick, due to Lickorish [Lic62], to construct a
curve $\gamma$ such that both $i(\gamma,\alpha)$ and $i(\gamma,\beta)$ are at
most one half of $i(\alpha,\beta)$, and then it proceeds inductively. The
reader familiar with the proof would soon realise that if one starts with
multicurves $\alpha$ and $\beta$ instead, the produced multicurve $\gamma$
might have more or less components. In particular, even if $\alpha$ and
$\beta$ are pants decompositions, there is no guarantee that $\gamma$ would be
a pants decomposition too. A second attempt would be to apply Hempel’s Lemma
successively and $|P|$ times, with $|P|$ the number of curves in the pants
decomposition $P$, to convert one curve of $P$ at a time to one curve of
$P^{\prime}$. The issue is that applying the proof of Hempel’s Lemma to the
first curve in $P$ makes the remaining curves more complicated rapidly, and
its successive application does not seem to produce a good bound for the
distance between $P$ and $P^{\prime}$ in the pants graph. Nevertheless, using
different techniques, we show that such a bound exists. Throughout the paper,
the implicit constants in the big $O$ notation are universal; in particular
they do not depend on the underlying surface.

######  Theorem 1.1.

Let $S$ be a compact connected orientable surface, and $P$ and $P^{\prime}$ be
pants decompositions of $S$. The distance between $P$ and $P^{\prime}$ in the
pants graph is

$O(|\chi(S)|^{2})\hskip 2.84526pt(1+\log(i(P,P^{\prime})))$

Moreover, there is an algorithm that constructs a (not necessarily geodesic)
path $P=P_{0},P_{1},\cdots,P_{n}=P^{\prime}$ of length
$n=O(|\chi(S)|^{2})\hskip 2.84526pt(1+\log(i(P,P^{\prime})))$ connecting $P$
and $P^{\prime}$ in the pants graph, in time that is a polynomial function of
$|\chi(S)|$ and $\log(i(P,P^{\prime}))$. Here, for the input, $P$ is given as
a union of pairs of pants with gluing instructions, and $P^{\prime}$ is given
in normal form with respect to $P$. For the output, each $P_{i}$ is given as a
union of pairs of pants with gluing instructions together with the pants move
from $P_{i-1}$ to $P_{i}$.

We now briefly explain what we mean by normal form for $P^{\prime}$ with
respect to $P$ and refer the reader to Section 2.2 and Figure 2 for precise
definitions. The _Dehn coordinates_ express the isotopy class of any
multicurve $\gamma$ in terms of

  1. (1)

the geometric _intersection numbers_ of $\gamma$ with each curve in a fixed
pants decomposition $P$, and

  2. (2)

the _twist numbers_ about the curves in $P$.

Here we are interested in the isotopy class of $\gamma=P^{\prime}$ up to the
action of the mapping class group of $S-P$, which is generated by Dehn twists
about the curves in $P$. Therefore, if the intersection number of $P^{\prime}$
with a curve $\alpha\subset P$ is $n$, then we only need to know the twist
number about $\alpha$ modulo $n$.

Our proof of Theorem 1.1 uses pre-triangulations (Definition 1.3), train
tracks, as well as an algorithm of Agol, Hass, and Thurston [AHT06] for
counting the number of orbits for the action of a pseudogroup generated by
_isometries_ between subintervals of a (discrete) _interval_
$[1,N]:=\\{1,\cdots,N\\}$. See the Background Section.

######  Convention 1.2.

To simplify the statements, throughout the paper we allow a 1-complex to have
components that are simple closed curves with no vertices on them. Any such
component would be considered as an edge of the 1-complex as well.

######  Definition 1.3 (Pre-triangulation).

A _pre-triangulation_ of a surface $S$ is an embedded finite $1$-complex in
$S$ such that every complementary region is either a disc, or an annulus, or a
pair of pants.

With Convention 1.2, both triangulations and pants decompositions are special
cases of pre-triangulations. The connection between pants decompositions and
pre-triangulations is as follows. We describe a natural procedure that given a
pre-triangulation $\mathcal{T}$ and an ordering $\mathrm{O}$ on the set of
edges of $\mathcal{T}$, constructs a pants decomposition
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ of $S$ (Construction 3.7).
Conversely, given a pants decomposition $P$ and a choice of a suitable
1-complex $\gamma$ in $S$, called a _nerve_ (Definition 3.2), a connected pre-
triangulation $\mathcal{T}=\mathrm{\textbf{T}}(P,\gamma)$ of $S$ can be
constructed (Construction 3.5). It is shown that for any pre-triangulation
$\mathcal{T}$ and orderings $\mathrm{O}$ and $\mathrm{O}^{\prime}$ on the
edges of $\mathcal{T}$, the distance between the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ and
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O}^{\prime})$ in the pants graph is
$O(|\mathcal{T}|^{2})$, where $|\mathcal{T}|$ is the number of edges of
$\mathcal{T}$ (Lemma 3.14). Using this, we show in Lemma 3.15 that for any two
pre-triangulations $\mathcal{T}$ and $\mathcal{T}^{\prime}$ and orderings
$\mathrm{O}$ and $\mathrm{O}^{\prime}$ on their edges, the distance between
the pants decompositions $\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ and
$\mathrm{\textbf{P}}(\mathcal{T}^{\prime},\mathrm{O}^{\prime})$ is
$O(|\mathcal{T}\cup\mathcal{T}^{\prime}|^{2})$, where
$|\mathcal{T}\cup\mathcal{T}^{\prime}|$ is the number of edges of the pre-
triangulation $\mathcal{T}\cup\mathcal{T}^{\prime}$ obtained by superimposing
$\mathcal{T}$ and $\mathcal{T}^{\prime}$. In particular, this implies
Corollary 3.16 stating that the distance between two pants decompositions $P$
and $P^{\prime}$ in the pants graph is $O(i(P,P^{\prime})^{2})$. As far as we
are aware, albeit much weaker than Theorem 1.1, even this quadratic upper
bound for distance in the pants graph is new.

###  1.2. One-vertex triangulations

The idea of the proof of Theorem 1.1 can be used to give an upper bound for
the number of _flip and twist moves_ between two triangulations of a surface.
The _flip graph_ of a closed orientable surface $S$ is a simplicial graph
whose vertices are one-vertex triangulations of $S$ up to isotopy, with two
vertices joined by an edge if they differ by a _flip_ of a diagonal in a
simplicial square. It is well-known that the flip graph is connected. The
mapping class group of $S$ acts by isometries on the flip graph, and the
action is properly discontinuous and cocompact. By the Švarc–Milnor Lemma, the
flip graph of $S$ is quasi-isometric to the mapping class group of $S$, where
the metric on the mapping class group is the word metric with respect to any
fixed finite generating set. Given two one-vertex triangulations $\mathcal{T}$
and $\mathcal{T}^{\prime}$ of $S$, one can convert $\mathcal{T}$ to
$\mathcal{T}^{\prime}$ using a sequence of at most
$i(\mathcal{T},\mathcal{T}^{\prime})$ flips; see e.g. [DP19, Lemma 2.1]. In
general, the linear dependency on $i(\mathcal{T},\mathcal{T}^{\prime})$ cannot
be improved, essentially because the flip graph is quasi-isometric to the
mapping class group. For example, if $\mathcal{T}$ is a fixed one-vertex
triangulation of $S$, $\alpha$ is a fixed essential simple closed curve in
$S$, and $\mathcal{T}^{\prime}:=(T_{\alpha})^{n}(\mathcal{T})$ where
$T_{\alpha}$ is the Dehn twist about $\alpha$, then

  1. -

$i(\mathcal{T}^{\prime},\mathcal{T})$ is linear in $n$; and

  2. -

$\mathcal{T}^{\prime}$ and $\mathcal{T}$ have distance at least a constant
multiple of $n$ in the flip graph. This is because by the work of Farb,
Lubotzky, and Minsky [FLM01], the word length of $(T_{\alpha})^{n}$ in the
mapping class group is linear in $n$.

However, we show in Theorem 1.4 that if we are allowed to use powers of Dehn
twists (_twist maps_ for short) in addition to flips, then one can convert
$\mathcal{T}$ to $\mathcal{T}^{\prime}$ much more economically. In this case,
the total number of flips and twist maps needed will be bounded above by a
polynomial function of $\log(i(\mathcal{T},\mathcal{T}^{\prime}))$ and
$|\chi(S)|$.

######  Theorem 1.4.

Let $S$ be a compact orientable surface. When $S$ is closed (respectively, has
non-empty boundary), let $\mathcal{T}$ and $\mathcal{T}^{\prime}$ be one-
vertex (respectively, ideal) triangulations of $S$. There is a sequence
$\mathcal{T}=\mathcal{T}_{0},\mathcal{T}_{1},\cdots,\mathcal{T}_{n}=\mathcal{T}^{\prime}$
of one-vertex (respectively, ideal) triangulations of $S$ such that:

  1. (1)

Each $\mathcal{T}_{i+1}$ is obtained from $\mathcal{T}_{i}$ by either a flip
or a power of a Dehn twist. When $\mathcal{T}_{i+1}$ is obtained from
$\mathcal{T}_{i}$ by Dehn twisting $k$ times about a curve $\alpha$, then
$\alpha$ is a normal curve intersecting each edge of $\mathcal{T}_{i}$ at most
three times, and the absolute value of $k$ is bounded above by
$i(\mathcal{T},\mathcal{T}^{\prime})$.

  2. (2)

$n=O(|\chi(S)|^{3}\log(i(\mathcal{T},\mathcal{T}^{\prime}))+|\chi(S)|^{3})$.

Moreover, there is an algorithm that constructs the sequence
$\mathcal{T}_{1},\cdots,\mathcal{T}_{n}$ in time that is a polynomial function
of $\log(i(\mathcal{T},\mathcal{T}^{\prime}))$ and $|\chi(S)|$. Here we assume
that $\mathcal{T}$ and $\mathcal{T}^{\prime}$ have the same vertex (when $S$
is closed), $\mathcal{T}$ is given as a union of (possibly ideal) triangles
with gluing instructions, and $\mathcal{T}^{\prime}$ is given in terms of its
normal coordinates with respect to $\mathcal{T}$. For the output, each
$\mathcal{T}_{i}$ is given as a union of (possibly ideal) triangles with
gluing instructions together with the flip or twist move from
$\mathcal{T}_{i}$ to $\mathcal{T}_{i+1}$.

See Definition 2.4 for the definition of the normal form for a triangulation
with respect to another triangulation. In Theorem 6.2, as a precursor to
Theorem 1.4, we prove an analogous statement (Theorem 6.2) for a similar set
of moves between two _polygonal decompositions_ (Definition 2.6) of a compact
orientable surface. In Theorem 6.7, we also prove a similar result for a set
of moves between two spines of a compact orientable surface.

###  1.3. Volumes of hyperbolic 3-manifolds

A _maximal cusp_ is a geometrically finite hyperbolic 3-manifold such that
each component of its conformal boundary is a thrice-punctured sphere
[CCHS03]. The _convex core_ of a non-compact hyperbolic manifold is the
smallest geodesically convex subset that contains every closed geodesic.
Theorem 1.1 together with the work of Agol [Ago03] implies the following.

######  Corollary 1.5.

Let $\Sigma$ be a closed orientable surface of genus $g$, and $P$ and
$P^{\prime}$ be pants decompositions of $\Sigma$ with no curve in common.
Assume that $M$ is a maximal cusp obtained from a quasi-Fuchsian 3-manifold
homeomorphic to $\Sigma\times\mathbb{R}$ by pinching the multicurves $P$ and
$P^{\prime}$ to annular cusps on the two conformal boundary components of $M$.
The volume of the convex core of $M$ is

$O(g^{2})\hskip 2.84526pt(1+\log(i(P,P^{\prime}))).$

In Proposition 8.1 we give examples demonstrating that the bound in Corollary
1.5 is sharp up to a multiplicative factor of $g$.

###  1.4. Weil–Petersson distance in the Teichmüller space

Denote by $\mathrm{Teich}(S)$ the Teichmüller space of a compact orientable
surface $S$ (in other words, the space of marked hyperbolic metrics possibly
with cusps but with no boundary). Denote its Weil–Petersson metric by
$d_{\mathrm{WP}}$. Using Theorem 1.1, the work of Wolpert [Wol08], Cavendish
and Parlier [CP12], and Parlier [Par23] we show the following.

######  Theorem 1.6.

Let $S$ be a compact orientable surface, and let $X,Y\in\mathrm{Teich}(S)$.
Let $P_{X}$ and $P_{Y}$ be pants decompositions for $X$ and $Y$ respectively,
in which each curve has length at most $2\pi|\chi(S)|$, which exist by a
theorem of Parlier. Then

$d_{\mathrm{WP}}(X,Y)\leq O(|\chi(S)|^{2})\hskip
2.84526pt(1+\log(i(P_{X},P_{Y}))).$

###  1.5. Idea of the proof of Theorem 1.1

Given pants decompositions $P$ and $P^{\prime}$, we first put $P^{\prime}$ in
normal form with respect to $P$. Then we squeeze parallel normal arcs together
to produce a train track $\tau$ such that $P^{\prime}$ is carried by $\tau$.
In other words, there is an integral weight $\mu$ on branches of $\tau$ such
that the carried 1-complex $\mathcal{CC}(\tau,\mu)$ is equal to $P^{\prime}$.

Given an integrally weighted train track $(\tau,\mu)$, and making some extra
choices $\mathcal{I}$, we can define an _orbit counting problem_
$\mathrm{OCP}(\tau,\mu,\mathcal{I})$ (Definition 4.4). The extra data
$\mathcal{I}$ is called an _initial interval identification_ and can be safely
ignored for now. Applying the Agol–Hass–Thurston algorithm, we can count the
number of orbits $\mathrm{OCP}(\tau,\mu,\mathcal{I})$. While the number of
orbits of $\mathrm{OCP}(\tau,\mu,\mathcal{I})$ is not any new information (it
is always equal to the number of curves in $P^{\prime}$, which is
$(3|\chi(S)|-|\partial S|)/2$), we are interested in the way that the AHT
algorithm calculates the number of orbits. In Proposition 4.12 and Lemma 4.16,
we show that the AHT algorithm does this count in $n$ steps with

$\displaystyle n-1\leq E(1+\log|\mu|),$

where $E=O(|\chi(S)|)$ is the number of branches of $\tau$ and
$|\mu|=i(P,P^{\prime})$ is the total weight of all branches of $\tau$.
Moreover, each step of the the AHT algorithm can be seen as a geometric change
on the underlying integrally weighted train track, namely as either a
_splitting_ or a _twirling_ (Definition 4.6 and Figure 10). The algorithm
proceeds until $(\tau,\mu)$ is completely unwound to $P^{\prime}$, so
intuitively the algorithm does the reverse process of squeezing parallel arcs
together, in a precise and efficient way. Hence, there is a sequence
$(\tau_{i},\mu_{i})$ of integrally weighted train tracks for $i=1,\cdots,n$
starting with $(\tau_{1},\mu_{1})=(\tau,\mu)$ and terminating at $P^{\prime}$
such that each $(\tau_{i+1},\mu_{i+1})$ is obtained from $(\tau_{i},\mu_{i})$
by splitting or twirling, and

(1) $\displaystyle n-1=O(|\chi(S)|)(1+\log i(P,P^{\prime})).$

The underlying 1-complex of each $\tau_{i}$ is a pre-triangulation. By Lemma
4.10, since $(\tau_{i+1},\mu_{i+1})$ is obtained from $(\tau_{i},\mu_{i})$ by
a simple geometric operation (splitting or twirling), the following holds:
there are orderings $\mathrm{O}_{i}$ on the edges of $\tau_{i}$ such that for
most $i$ the distance between the pants decompositions
$\mathrm{\textbf{P}}(\tau_{i},\mathrm{O}_{i})$ and
$\mathrm{\textbf{P}}(\tau_{i+1},\mathrm{O}_{i+1})$ is $O(|\chi(S)|)$.
Moreover, by Lemma 3.15 the distance between the pants decompositions $P$ and
$\mathrm{\textbf{P}}(\tau_{1},\mathrm{O}_{1})$ is $O(|\chi(S)|^{2})$, because
$i(\tau_{1},P)=O(|\chi(S)|)$. Note also that
$\mathrm{\textbf{P}}(\tau_{n},\mathrm{O}_{n})=P^{\prime}$. The triangle
inequality now implies that the distance between $P$ and $P^{\prime}$ is at
most $O(|\chi(S)^{2}|)+(n-1)O(|\chi(S)|)$, which combined with equation (1)
gives the desired upper bound.

###  1.6. Previous related work

Several authors had previously used either train tracks and the
Agol–Hass–Thurston algorithm, or the _tracing algorithm_ of Erickson and
Nayyeri [EN13], to simplify curves on surfaces efficiently.

  * •

Motivated by the AHT algorithm, Dunfield and D. Thurston [DT06] adapted
Brown’s algorithm in the context of splittings of train tracks to decide
efficiently whether a random tunnel number one 3-manifold fibers over the
circle.

  * •

Dynnikov and Wiest [DW07] introduced a specialised version of the AHT
algorithm for curves on a punctured disc, called the _transmission-relaxation
algorithm_ , to simplify a weighted train track associated with a braid in an
$n$-times punctured disc. Using this, they proved that certain algebraic and
geometric complexity measures for a braid are comparable up to multiplicative
constants only depending on $n$. They showed an improved running time for
their algorithm compared to the general version of the AHT algorithm. In the
proof of Proposition 4.12, we use their improved bound to analyse the time
complexity of the AHT algorithm applied to a weighted train track.

  * •

Erickson and Nayyeri [EN13] gave an algorithm to _trace_ a curve $\gamma$ with
respect to a triangulation $\mathcal{T}$ in time that is a polynomial function
of $\log(i(\mathcal{T},\gamma))$ and $|\chi(S)|$.

  * •

Bell [Bel21] showed how to simplify a triangulation $\mathcal{T}$ of a surface
$S$ with respect to a _curve_ $\gamma$ using flips and twist maps, in time
that is a polynomial function of $\log(i(\mathcal{T},\gamma))$ but a super-
exponential function of $|\chi(S)|$. He has communicated to us that the source
code of his software program _flipper_ does this simplification in time that
is a polynomial function of both $\log(i(\mathcal{T},\gamma))$ and
$|\chi(S)|$.

Another novel feature of our work is to show that the AHT algorithm can be
used to establish non-algorithmic results such as Corollary 1.5 and Theorem
1.6.

###  1.7. Plan of the paper

In Section 2, we discuss the background on the algorithm of Agol, Hass, and
Thurston. We also introduce various normal forms needed for the statements of
the theorems. These include

  1. -

normal form for a pants decomposition with respect to another pants
decomposition. This is a slight modification of Dehn coordinates, and is used
in Theorem 1.1.

  2. -

normal form for a triangulation with respect to another triangulation with
common vertices. This is a mild generalisation of the usual notion of normal
curve with respect to a triangulation, and is used in Theorem 1.4.

  3. -

normal form for a 1-complex with respect to a polygonal decomposition. This is
a more relaxed notion than the usual notion of a normal curve with respect to
a triangulation, since the 1-complex can be quite general. This is used as a
bookkeeping tool in Theorems 6.2 and 6.7.

In Section 3, we discuss pre-triangulations and their relation to pants
decompositions. Section 4 discusses based weighted train tracks and orbit
counting problems associated to them. The effect of the AHT algorithm applied
to such orbit counting problems is seen as a geometric move on the underlying
train track (Proposition 4.12). Section 5 contains the proof of Theorem 1.1.
We first prove Theorems 6.2 and 6.7 in Section 6, and then use the latter to
prove Theorem 1.4 in Section 7. Section 8 proves Corollary 1.5 using only the
statement of Theorem 1.1 as well as the work of Agol [Ago03]. Theorem 1.6 is
proved in Section 9. Some open problems are discussed in Section 10.

##  2\. Background

###  2.1. Agol–Hass–Thurston (AHT) algorithm

By an _interval_ $[M,N]$ with $M\leq N$ integers, we mean the set
$\\{M,M+1,\cdots,N\\}$. An _isometry_ or _pairing_ between two intervals is a
bijection of the from $x\rightarrow x+c$ or $x\rightarrow-x+c$ for a constant
integer $c$. Let $[1,N]$ be an interval and $g_{i}$, $1\leq i\leq k$, be a
collection of pairings between subintervals of $[1,N]$. Two pairings can be
composed if the range of the first lies in the domain or range of the second.
The pairings generates a pseudogroup under the operations of composition where
defined, inverses, and restriction to subintervals. The interval $[1,N]$ is
divided into equivalence classes by the action of the pairings, which are
called _orbits_. Agol, Hass, and Thurston gave an algorithm for counting the
number of such orbits, in time that is a polynomial function of $k$ and
$\log(N)$. This logarithmic dependence on $N$ will be crucial for the
arguments in this paper.

We now explain further terminology and the AHT algorithm briefly; the reader
should see [AHT06] for more details. A pairing $g\colon[a,b]\rightarrow[c,d]$
is _orientation-preserving_ if $g(a)=c$ and $g(b)=d$, and otherwise
_orientation-reversing_. If $a\leq c$ we refer to $[a,b]$ as the _domain_ and
$[c,d]$ as the _range_ of the pairing. If the pairing preserves orientation,
its _translation distance_ $t$ is defined as $t=c-a=d-b$. An interval is
called _static_ if it is in neither the domain nor the range of any pairing.
Given a collection of pairings acting on $[1,N]$, a pairing is _maximal_ if
its range contains both $N$ and the range of any other pairing containing $N$.
A pairing $g\colon[a,b]\rightarrow[c,d]$ is _periodic_ with period $t$ if it
is orientation-preserving with translation distance $t$ and $a<c=a+t\leq b+1$,
so there is no gap between the domain and range. The combined interval $[a,d]$
is then called a _periodic interval_ of period t.

The orbit-counting algorithm applies a series of the following modifications,
in a particular order, to a collection of pairings.

  * •

_Periodic merger_ : Given two periodic pairings $g_{1}$ and $g_{2}$ with
periodic intervals $R_{1}$ and $R_{2}$ and periods $t_{1}$ and $t_{2}$ such
that $\text{width}(R_{1}\cap R_{2})\geq t_{1}+t_{2}$, the periodic merger
replaces $g_{1}$ and $g_{2}$ with a single periodic pairing of period
$\mathrm{GCD}(t_{1},t_{2})$. Here $\mathrm{GCD}$ stands for the greatest
common divisor.

######  Remark 2.1.

Assume that a periodic merger is done. Then before the merging, there is a
point which lies in the domain and range of at least 3 pairings, i.e.

$\exists p\in[1,N]\text{ such that
}\sharp\\{i:p\in\mathrm{domain}(g_{i})\\}+\sharp\\{i:p\in\mathrm{range}(g_{i})\\}\geq
3.$

In our applications in this paper, every point will be in the domain and range
of at most two pairings, hence periodic mergers will not occur. For this
reason we will not elaborate on the properties of periodic merger further.

  * •

_Contraction_ : Contraction can be performed on a static interval $[r,s]$. We
eliminate this interval, replace $[1,N]$ by $[1,N-(s-r+1)]$, and change each
$g_{j}$ by replacing any point $x$ in a domain or range which lies entirely to
the right of $s$ by $x-(s-r+1)$. We will then decrease the number of orbits by
$s-r+1$, since the eliminated points are each unique representatives of an
orbit.

  * •

_Trimming_ : The trimming operation simplifies an orientation-reversing
pairing whose domain and range overlap.

######  Remark 2.2.

In our applications in this paper, the orientability of the underlying surface
implies that there will be no trimming.

  * •

_Truncation_ : Given an interval that lies in the domain and range of exactly
one pairing, we can remove it without changing the orbit structure. This
operation can be applied to remove points from the right of the interval
$[1,N]$. Assume that there is a pairing $g\colon[a,b]\rightarrow[c,N]$ and a
value $N^{\prime}$ with $c\leq N^{\prime}+1\leq N$, such that all points in
the interval $[N^{\prime}+1,N]$ are in the range of only $g$. Truncating $g$
shortens the interval $[1,N]$ to the interval $[1,N^{\prime}]$, and similarly
shortens the domain and range of $g$. If $g$ is orientation-reversing,
truncation is applied only when $g$ has disjoint domain and range (i.e. after
trimming).

  * •

_Transmission_ : In transmission, a pairing $g_{1}$ is used to shift the
domain and range of a second pairing $g_{2}$ to the left as much as possible.
Once the pairings are shifted leftwards, we can subsequently apply truncation.
Transmissions allow significant simplifications of the orbit counting problem
in one step.

If $g_{1}$ is orientation-reversing and has overlapping domain and range, then
as a first step in transmission we trim $g_{1}$. Now consider a pairing
$g_{1}$, and a second pairing $g_{2}$ whose range is contained in the range of
$g_{1}$. Consider two cases:

    1. a)

If $\text{domain}(g_{2})\nsubseteq\text{range}(g_{1})$: then define the map
$g^{\prime}_{2}=g_{1}^{-r}\circ g_{2}$ , where $r=1$ if $g_{1}$ is
orientation-reversing and otherwise $r\geq 1$ is the largest integer such that
$g_{1}^{-r+1}([c_{2},d_{2}])$ is contained in the range of $g_{1}$.

    2. b)

If $\text{domain}(g_{2})\subseteq\text{range}(g_{1})$: then define the map
$g^{\prime}_{2}=g_{1}^{r}\circ g_{2}\circ g_{1}^{s}\colon
g_{1}^{-s}([a_{2},b_{2}])\rightarrow g_{1}^{r}([c_{2},d_{2}])$, where $r$ is
as above, $s=1$ if $g$ is orientation reversing, and otherwise $s\geq 1$ is
the largest integer such that $g_{1}^{-s+1}([a_{2},b_{2}])$ is contained in
the range of $g_{1}$. The operation of replacing $g_{2}$ by $g_{1}^{-r}\circ
g_{2}\circ g_{1}^{s}$ is called a transmission of $g_{2}$ by $g_{1}$.

The AHT algorithm repeatedly applies the following steps (1)–(6) to the orbit
counting problem.

  1. (1)

Delete any pairings that are restrictions of the identity.

  2. (2)

Make any possible contractions and, if any exist, increment the orbit counter
by the sum of the number of points deleted by the contractions. If the number
of pairings remaining is zero, output the number of orbits and stop.

  3. (3)

Trim all orientation-reversing pairings whose domain and range overlap.

  4. (4)

Search for pairs of periodic pairings $g_{i}$ and $g_{j}$ with periods $t_{1}$
and $t_{2}$ and with overlapping periodic intervals $R_{1}$ and $R_{2}$ such
that $\text{width}(R_{1}\cap R_{2})\geq t_{1}+t_{2}$. If any such pair exists,
then perform a merger replacing $g_{i}$ and $g_{j}$ by a single periodic
pairing. Repeat until no mergers can be performed.

  5. (5)

Find a maximal $g_{i}$. For each $g_{j}\neq g_{i}$ whose range is contained in
$[c_{i},N^{\prime}]$, transmit $g_{j}$ by $g_{i}$.

  6. (6)

Find the smallest value of $c$ such that the interval $[c,N^{\prime}]$
intersects the range of exactly one pairing. Truncate the pairing whose range
contains the interval $[c,N^{\prime}]$.

A _cycle_ of the AHT algorithm consists of applying steps (1)–(6) above. In
Proposition 4.12, we will be interested in the effect of applying the AHT
algorithm to certain orbit counting problems associated with train tracks. In
particular, we would like to see the effect of one cycle as a geometric change
in the underlying train track. In order to see a meaningful geometric change,
we will shift the steps in one cycle of the AHT algorithm as follows.

######  Definition 2.3 (Shifted cycle of the AHT algorithm).

The first _shifted cycle_ of the AHT algorithm applies steps (1)–(4) of the
orbit counting algorithm. Afterward, every shifted cycle applies steps (5)–(6)
followed by steps (1)–(4). Clearly the AHT algorithm is the successive
application of shifted cycles as well.

###  2.2. Normal form for pants decompositions

We define the Dehn parametrisation of isotopy classes of multicurves on a
surface, following Penner and Harer [PH92, page 13]. We then modify Dehn
coordinates slightly to define a normal form for a pants decomposition with
respect to another pants decomposition. The motivation for this modification
is that in Theorem 1.1, the isotopy class of $P^{\prime}$ is needed only up to
the action of the mapping class group of $S-P$.

Let $P$ be a pants decomposition of $S$. Denote the components of $P$ by
$\alpha_{r}$ where $1\leq r\leq|P|=3g-3+b$, where $g$ is the genus of $S$ and
$b$ is the number of boundary components of $S$. For each pants curve
$\alpha_{i}$, choose a closed arc $w_{i}\subset\alpha_{i}$ called a _window_.
For each pair of pants $F$ in $P$, choose a collection of properly embedded
arcs $\ell_{i,j}$ ($1\leq i,j\leq 3$) in $F$ with endpoints contained in the
windows as in Figure 2. Let $(m_{r})$ be non-negative integers and $(t_{r})$
be integers for $1\leq r\leq|P|$ such that

  1. -

if $m_{r}=0$ then $t_{r}\geq 0$;

  2. -

for each embedded pair of pants $F$, the sum $m_{i_{1}}+m_{i_{2}}+m_{i_{3}}$
corresponding to the three boundary components of $F$ is even; and

  3. -

the number $m_{r}$ corresponding to a pants curve that bounds a torus minus a
disc or a twice punctured disc is even.

Figure 2. The windows $w_{i}$ and the arcs $\ell_{i,j}$.

Then we can construct a multicurve $\gamma$ as follows: take a number of
parallel copies of the arcs $\ell_{i,j}$ such that the intersection number
with $\alpha_{r}$ is exactly $m_{r}$. These parallel arcs can be naturally
pasted together to produce a multicurve, and this corresponds to the case of
$t_{r}=0$ and $m_{r}\neq 0$. If $m_{r},t_{r}\neq 0$, then we paste these
parallel arcs on the two sides of $\alpha_{r}$ by a
$(\frac{t_{t}}{m_{r}})$-fractional Dehn twist, where the twist is right-handed
if $t_{r}>0$. If $t_{r}\neq 0$ and $m_{r}=0$ then we add $t_{r}$ parallel
copies of $\alpha_{r}$ to the multicurve. The numbers $m_{r}$ are called the
_intersection numbers_ , and $t_{r}$ are called the _twisting numbers_. The
isotopy class of every multicurve, with all components essential, can be
uniquely represented in this way. This is called the _Dehn coordinates_ of the
multicurve.

In our applications, we only need the twisting numbers $t_{r}$ modulo the
integers $m_{r}$, since a full twist (that is a Dehn twist) about $\alpha_{r}$
lies in the mapping class group of $S-P$. We say that a pants decomposition
$P^{\prime}$ is given in normal form with respect to a pants decomposition $P$
if the coordinates $(m_{r},t_{r}\hskip 5.69054pt\mathrm{mod}\hskip
5.69054ptm_{r})$ of $P^{\prime}$ with respect to $P$ are given ($1\leq
r\leq|P|$).

###  2.3. Normal form for triangulations with common vertices

######  Definition 2.4 (Normal form for a triangulation).

Let $\mathcal{T}$ and $\mathcal{T}^{\prime}$ be triangulations of a compact
surface $S$ with the same set of vertices. We say that $\mathcal{T}^{\prime}$
is in _normal form with respect to $\mathcal{T}$_ if for each triangle
$\Delta$ of $\mathcal{T}$, the intersection $\gamma\cap\Delta$ consist of a
union of arcs of the following types

  1. -

an arc connecting different sides of $\Delta$; or

  2. -

an arc connecting a common vertex of $\Delta$ and $\mathcal{T}^{\prime}$ to
its opposite side; or

  3. -

a side of $\Delta$ whose endpoints are vertices of $\mathcal{T}^{\prime}$.

######  Proposition 2.5.

Let $\mathcal{T}$ and $\mathcal{T}^{\prime}$ be triangulations of a compact
surface $S$ with the same set of vertices. Assume that every edge of
$\mathcal{T}^{\prime}$ with the same endpoints is homotopically essential.
Then $\mathcal{T}^{\prime}$ can be isotoped relative to its vertices to be in
normal form with respect to $\mathcal{T}$.

###### Proof.

First, isotope $\mathcal{T}^{\prime}$ relative to its vertices to be in
general position with respect to $\mathcal{T}$. Isotope $\mathcal{T}^{\prime}$
relative to its vertices and remove any bigons with one side in $\mathcal{T}$
and one side in $\mathcal{T}^{\prime}$. This reduces the weight
$|\mathcal{T}^{\prime}\cap\mathcal{T}|$ until no bigons are left. At this
point, for any triangle $\Delta$ of $\mathcal{T}$, any component of
$\mathcal{T}^{\prime}\cap\Delta$ is a normal arc or a simple closed curve
lying entirely in $\Delta$. The latter possibility is ruled out by the
assumption that every edge of $\mathcal{T}^{\prime}$ with the same endpoints
is homotopically essential. ∎

###  2.4. Normal form for a 1-complex with respect to a polygonal
decomposition

######  Definition 2.6 (Polygonal decomposition).

A _polygonal decomposition_ $\mathcal{D}$ of a compact surface $S$ is an
embedded connected finite $1$-complex such that

  1. -

each complementary region adjacent to a boundary component of $S$ is
topologically either a disc or an annular neighbourhood of the boundary
component; and

  2. -

every other complementary region is a topological disc.

The next definition is a generalisation of the usual notion of normal form for
multicurves.

######  Definition 2.7 (Normal form for a 1-complex with respect to a
polygonal decomposition).

Let $\mathcal{T}$ be a polygonal decomposition of a compact surface $S$, and
$\gamma$ be a finite 1-complex embedded in $S$. We say that $\gamma$ is in
_normal form with respect to $\mathcal{T}$_ if

  1. (1)

$\mathcal{T}^{\prime}$ has no homotopically trivial simple closed curve
component that lies in a 2-cell of $\mathcal{T}$; and

  2. (2)

there are no bigons between $\mathcal{T}$ and $\gamma$ except possibly those
bigons that were already present in $\gamma$; i.e. there is no embedded disc
$D\subset S$ whose interior is disjoint from $\gamma\cup\mathcal{T}$ and with
$\partial D=\alpha\cup\beta$ where $\alpha$ and $\beta$ are arcs with
$\partial\alpha=\partial\beta$, and $\alpha$ lies in an edge of $\mathcal{T}$
but not in an edge of $\gamma$, and $\beta$ lies in an edge of $\gamma$.

######  Proposition 2.8.

Let $\mathcal{T}$ be a polygonal decomposition of a compact surface $S$, and
$\gamma$ be a finite 1-complex embedded in $S$. Then $\gamma$ can be isotoped
relative to its vertices to be in normal form with respect to $\mathcal{T}$.

###### Proof.

Denote the $i$-skeleton of $\mathcal{T}$ and $\gamma$ by respectively
$\mathcal{T}^{i}$ and $\gamma^{i}$ for $i=0,1$. First, isotope $\gamma$
relative to its vertices to be in general position with respect to
$\mathcal{T}$; i.e. such that $\gamma^{1}-\gamma^{0}$ is transverse to
$\mathcal{T}^{1}-\mathcal{T}^{0}$. All isotopes we consider will be relative
to the vertices of $\gamma$. By a bigon we mean a bigon between $\mathcal{T}$
and $\gamma$. Denote by $i(\gamma,\mathcal{T})$ the number of transverse
intersections of $\gamma^{1}-\gamma^{0}$ with
$\mathcal{T}^{1}-\mathcal{T}^{0}$. If $B$ is a bigon such that at least one
vertex of $B$ is not in $\gamma^{0}$, then we can isotope $\gamma$ relative to
its vertices and remove $B$ while reducing the intersection number
$i(\gamma,\mathcal{T})$. Repeat until every bigon has both vertices in
$\gamma^{0}$. For any remaining bigon $B$ with $\partial B=\alpha\cup\beta$,
if one side of $\partial B$, say $\alpha$, lies in an edge of $\mathcal{T}$
but not in an edge of $\gamma$, then isotope the other side $\beta$ of
$\partial B$ into $\alpha$, and increase the number of edges of $\gamma$ that
lie in an edge of $\mathcal{T}$. Repeating this process puts $\gamma$ in
normal form with respect to $\mathcal{T}$. ∎

Suppose $\mathcal{T}^{\prime}$ is in normal form with respect to
$\mathcal{T}$. Then $\mathcal{T}$ cuts $\mathcal{T}^{\prime}$ into connected
components, each of is either

  1. (1)

a graph with at least one vertex that is embedded in a 2-cell of
$\mathcal{T}$; or

  2. (2)

an arc properly embedded in a 2-cell of $\mathcal{T}$ whose endpoints lie on
distinct edges of the 2-cell.

Let $\Delta$ be a 2-cell of $\mathcal{T}$ and $a$ and $b$ be two distinct
sides of $\Delta$. Given two disjoint simple properly embedded arcs
$\gamma_{1},\gamma_{2}\subset\Delta$ as in (2) above and joining $a$ and $b$,
there is a rectangle with two opposite sides $\gamma_{1}$ and $\gamma_{2}$ and
the other two sides lying on $a$ and $b$. We say that $\gamma_{1}$ and
$\gamma_{2}$ are of the same _type_ if any other piece of
$\mathcal{T}^{\prime}$ in $R$ is a properly embedded arc joining $a$ and $b$
as well. We can specify $\mathcal{T}^{\prime}$ by specifying a weighted
1-complex $\mathcal{N}$ in each 2-cell of $\mathcal{T}$ where

  1. -

$\mathcal{N}$ contains all components as in (1) above, and

  2. -

for each arc type appearing in (2), $\mathcal{N}$ contains one copy of the arc
together with a positive integer weight that counts the number of arcs of that
type.

The data of the weighted 1-complex $\mathcal{N}$ over all 2-cells of
$\mathcal{T}$ is called the _normal coordinates_ of $\mathcal{T}^{\prime}$
with respect to $\mathcal{T}$. Note that if $\mathcal{T}^{\prime}$ is a
multicurve, then only components as in (2) above appear, and we recover the
usual notion of normal coordinates for a multicurve.

##  3\. From pants decompositions to pre-triangulations, and vice versa

###  3.1. From pants decompositions to pre-triangulations

######  Definition 3.1 (Bipartite adjacency graph of a pants decomposition).

Let $P$ be a pants decomposition of a compact connected orientable surface
$S$. Define the _bipartite adjacency graph_ $\Gamma=\Gamma(P)$ with vertices
$V=B\cup W$ partitioned into black $B$ and white $W$ colours as follows: black
vertices correspond to pairs of pants in $S\setminus P$, white vertices
correspond to simple closed curves in $P$, and each black vertex is connected
to the three (not necessarily distinct) white vertices corresponding to the
three boundary components of the pair of pants.

######  Definition 3.2 (A nerve for a pants decomposition).

Let $S$, $P$, and $\Gamma=\Gamma(P)$ be as above. Pick a base point $b\in
S\setminus P$, and let $b_{0}$ be the black vertex of $\Gamma$ corresponding
to the pair of pants containing $b$. Let $T$ be a maximal tree for $\Gamma$
containing $b_{0}$. Denote the white vertices of $\Gamma$ by $w_{i}$ where
$1\leq i\leq m$, and let $\alpha_{i}\in P$ be the simple closed curve
corresponding to $w_{i}$. For every vertex $w_{i}$, let $p_{i}$ be the unique
shortest path in $T$ from $b_{0}$ to $w_{i}$. Note that given any path $p$ in
$S$ that is transverse to $P$, we can _project_ $p$ to $\Gamma$. A _nerve of
$(P,b)$ compatible with $T$_ is a collection $\gamma=\cup\gamma_{i}$ of simple
arcs $\gamma_{i}\subset S$ such that

  1. (1)

$\gamma_{i}$ starts at $b$ and ends on $\alpha_{i}$;

  2. (2)

$\gamma_{i}$ is transverse to $P$ and its projection to $\Gamma$ is the path
$p_{i}$; and

  3. (3)

if the last white vertex of the path $p_{i}\cap p_{j}$ is $w_{\ell}$, then
$\gamma_{i}\cap\gamma_{j}=\gamma_{\ell}$. In the special case that $p_{i}\cap
p_{j}=\\{b_{0}\\}$, then $\gamma_{i}\cap\gamma_{j}=\\{b\\}$.

A _nerve of $(P,b)$_ is a nerve of $(P,b)$ compatible with some maximal tree
$T\subset\Gamma(P)$.

######  Lemma 3.3.

Given $S$, $P$, $T$, and $b$ as above, there is a nerve for $(P,b)$ compatible
with $T$.

###### Proof.

Let $d_{i}$ be the length (number of edges) of the path $p_{i}$. Define the
arcs $\gamma_{i}$ inductively based on the length $d_{i}$. Assume that
$\gamma_{i}$ is not defined yet, and $d_{i}$ is minimal with this property.
Let $w_{j}$ be the white vertex that is distance 2 from $w_{i}$ along $p_{i}$.
Let $b_{k}$ be the common neighbour of $w_{i}$ and $w_{j}$ in $p_{i}$, and
$w_{r}$ ($r\neq i,j$) be the third neighbour of $b_{k}$. Then $\gamma_{j}$ is
defined by hypothesis. Note that $\gamma_{j}\subset\gamma_{i}$ should hold.
Similarly if $p_{j}\subset p_{r}$, then $\gamma_{j}\subset\gamma_{r}$ should
hold. Now if $p_{j}\subset p_{r}$ then we define
$\gamma_{i}\setminus\gamma_{j}$ and $\gamma_{r}\setminus\gamma_{j}$
simultaneously such that $\gamma_{i}\cap\gamma_{r}=\gamma_{j}$, and otherwise
define $\gamma_{i}\setminus\gamma_{j}$. ∎

######  Remark 3.4.

Assume that a triangulation $\mathcal{H}$ of $S$ is given such that $P$ is
contained in the 1-skeleton of $\mathcal{H}$. Then we can construct a nerve
$\gamma$ for $(P,b)$ compatible with $T$ such that each arc $\gamma_{i}$
passes through each face of $\mathcal{H}$ at most once, and it is disjoint
from the vertices of the triangulation. To see this let $q_{i}$ be a shortest
path in the dual graph of $\mathcal{H}$ connecting $\gamma_{j}\cap\alpha_{j}$
to $\alpha_{i}$ in the above proof. Now if $p_{j}\nsubseteq p_{r}$, then
define $\gamma_{i}\setminus\gamma_{j}$ such that its projection to the dual
graph of $\mathcal{H}$ is equal to $q_{i}$. In particular,
$\gamma_{i}\setminus\gamma_{j}$ passes through each face of $\mathcal{H}$ at
most once. If $p_{j}\subset p_{r}$, define $q_{r}$ similar to $p_{i}$. Then
after possibly replacing $q_{r}$ by another path of the same length and the
same endpoints, $q_{i}$ and $q_{r}$ intersect each other in a connected
interval; this follows from the shortest length hypothesis. Hence we can
define $\gamma_{i}\setminus\gamma_{j}$ and $\gamma_{r}\setminus\gamma_{j}$
simultaneously such that their projections to the dual graph of $\mathcal{H}$
gives respectively $q_{i}$ and $q_{r}$, and they only intersect in a single
point.

A pants decomposition is a pre-triangulation as well. The next construction
shows how to produce a _connected_ pre-triangulation from a pants
decomposition equipped with a nerve.

######  Construction 3.5 (From a pants decomposition to a connected pre-
triangulation).

Let $S$ be a compact connected orientable surface, and $P$ be a pants
decomposition of $S$. Let $T$ be a maximal tree in the bipartite adjacency
graph $\Gamma=\Gamma(P)$, and $b\in S\setminus P$ be a base point. Pick a
nerve $\gamma$ for $(P,b)$ compatible with $T$. We construct a connected pre-
triangulation $\mathcal{T}=\mathrm{\textbf{T}}(P,\gamma)$ of $S$. Assume the
notations of Definitions 3.1 and 3.2. The only vertex of $\mathcal{T}$ is
$b_{0}$. Moreover, $\mathcal{T}$ has an edge $e_{i}$ for each curve
$\alpha_{i}$ in the pants decomposition, constructed inductively as follows

  1. (1)

First, for every white vertex $w_{i}$ adjacent to $b_{0}$, add an edge $e_{i}$
that runs from $b$ to $\alpha_{i}$ and remains close and almost parallel to
$\gamma_{i}$, then goes around $\alpha_{i}$, and finally comes back to $b$
close and almost parallel to $\gamma_{i}$.

  2. (2)

From now on at each step one or two edges are added. Pick a white vertex
$w_{i}$ for which $\gamma_{i}$ is not defined yet and such that the distance
between $w_{i}$ and $b_{0}$ in $T$ is minimal. Consider the shortest path
$p_{i}$ in $T$ joining $b_{0}$ to $w_{i}$, and let $w_{j}$ be the white vertex
along $p_{i}$ that is closest to $w_{i}$ ($j\neq i$). By hypothesis, the edge
$e_{j}$ is already defined. Let $b_{k}$ be the common neighbour of $w_{i}$ and
$w_{j}$ in $p_{i}$, and let $w_{r}$ ($r\neq i,j$) be the other neighbour of
$b_{k}$ in $\Gamma(P)$. If the edge joining $b_{k}$ to $w_{r}$ appears in
$p_{r}$, then add $e_{i}$ and $e_{r}$ as in Figure 3 Right; otherwise add
$e_{i}$ as in Figure 3 Left. Again $e_{i}$ runs from $b$ to $\alpha_{i}$
remaining almost parallel to $\gamma_{i}$, then goes around $\alpha_{i}$, and
finally comes back to $b$ almost parallel to $\gamma_{i}$

Intuitively, $e_{i}$ is obtained by pulling $\alpha_{i}$ to $b$ along the path
$\gamma_{i}$; the inductive process for constructing $e_{i}$ is to make sure
that the edges $e_{i}$ only intersect each other at the common vertex $b$.

$\alpha_{j}$ at 50 50 $\alpha_{j}$ at 280 50 $\alpha_{i}$ at 15 220
$\alpha_{i}$ at 250 220 $\alpha_{r}$ at 185 220 $\alpha_{r}$ at 420 220
$e_{i}$ at 80 100 $e_{i}$ at 305 100 $e_{r}$ at 360 100 $e_{j}$ at 120 10
$e_{j}$ at 350 10

Figure 3. From a pants decomposition to a connected pre-triangulation

######  Lemma 3.6.

$\mathrm{\textbf{T}}(P,\gamma)$ is a pre-triangulation of $S$.

###### Proof.

The nerve $\gamma$ is an embedded tree in $S$, and there is a collapsing map
$r\colon S\rightarrow S$ that collapses $\gamma$ to the base point $b$, and
the image of $P\cup\gamma$ under $r$ is the 1-complex
$\mathrm{\textbf{T}}(P,\gamma)$. Each complementary components of
$\mathrm{\textbf{T}}(P,\gamma)$ in $S$ is homeomorphic to a corresponding
complementary component of $P\cup\gamma$ in $S$. Since $P\cup\gamma$ is a pre-
triangulation, so is $\mathrm{\textbf{T}}(P,\gamma)$.

∎

###  3.2. From pre-triangulations to pants decompositions

######  Construction 3.7 (From a pre-triangulation to a pants decomposition).

Let $\mathcal{T}$ be a pre-triangulation of a compact connected orientable
surface $S$. Pick a forest $T$ in the $1$-skeleton $\mathcal{T}^{1}$ of
$\mathcal{T}$, and choose an ordering $\mathrm{O}$ on the edges of
$\mathcal{T}\setminus T$ as $e_{1},\cdots,e_{\ell}$. First define the
subsurfaces $N_{i}$ inductively: $N_{1}$ is a regular neighbourhood of $T\cup
e_{1}$ in $S$, and $N_{i+1}$ is a regular neighbourhood of $N_{i}\cup e_{i+1}$
for each $1\leq i<\ell$. Let $F_{i}$ be the subsurface obtained from $N_{i}$
by capping off any boundary component that bounds a disc in $S\setminus
N_{i}$. In particular, $F_{i}$ is isotopic to the subsurface that
$e_{1}\cup\cdots\cup e_{i}$ _fills_. Define the multicurve $P$ as the union of
$\partial F_{i}$ for $1\leq i\leq\ell$ after discarding any non-essential
(homotopically trivial or boundary parallel) or repeated simple closed curves.
By the next lemma, $P=\mathrm{\textbf{P}}(\mathcal{T},T,\mathrm{O})$ is a
pants decomposition. If $T=\emptyset$, we abbreviate
$\mathrm{\textbf{P}}(\mathcal{T},T,\mathrm{O})$ to
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$.

######  Lemma 3.8.

$P=\mathrm{\textbf{P}}(\mathcal{T},T,\mathrm{O})$ is a pants decomposition.

###### Proof.

We first show that every essential simple closed curve in $F_{i+1}-F_{i}$ is
isotopic to a component of $\partial F_{i+1}$ or $\partial F_{i}$. This is
clear if $e_{i+1}$ is a simple closed curve component, so assume that
$e_{i+1}$ is an edge. Up to isotopy, the subsurface $N_{i+1}$ is obtained from
$N_{i}$ by adding a small neighbourhood of the edge $e_{i+1}$ in $S$. Let
$C_{1}$ and $C_{2}$ be the complementary regions to $N_{i+1}$ in $S$ that are
adjacent to the edge $e_{i+1}$; it is possible that $C_{1}=C_{2}$. If at least
one of $C_{1}$ and $C_{2}$ is a disc, then $F_{i+1}$ is obtained from $F_{i}$
by thickening its boundary components to the outside or filling in an annular
complementary region. If none of $C_{1}$ and $C_{2}$ is a disc, then $F_{i+1}$
is obtained from $F_{i}$ via attaching a pair of pants along one or two
boundary components, and thickening the rest of the boundary components to the
outside. In any case, the conclusion holds.

Assume that $\alpha$ is an essential simple closed curve in $S\setminus P$. We
need to show that $\alpha$ is isotopic to a curve in $P$. Since $\mathcal{T}$
is a pre-triangulation, $F_{\ell}$ is the entire surface $S$ minus a (possibly
empty) union of disjoint essential annuli and pairs of pants. Setting
$F_{0}=\emptyset$ and $F_{\ell+1}=S$, the surface $S$ can be written as the
disjoint union of $F_{i+1}-F_{i}$ for $0\leq i\leq\ell$. Since $\alpha$ can be
isotoped to be disjoint from $P=\cup_{i=1}^{\ell}\partial F_{i}$, there is an
index $i$ such that $\alpha\subset F_{i+1}-F_{i}$. However, every essential
simple closed curve in $F_{i+1}-F_{i}$ is parallel to a component of $\partial
F_{i+1}$ or $\partial F_{i}$. This implies that $\alpha$ is isotopic to a
curve in $P=\cup\partial F_{i}$.

∎

######  Remark 3.9.

Let $\mathrm{O}=(e_{1},\cdots,e_{\ell})$ be an ordering on the edges of
$\mathcal{T}\setminus T$. Let $e^{\prime}_{1},\cdots,e^{\prime}_{m}$ be any
ordering on the edges of $T$. Define the ordering $\mathrm{O}^{\prime}$ on the
edges of $\mathcal{T}$ as
$\mathrm{O}^{\prime}=(e^{\prime}_{1},\cdots,e^{\prime}_{m},e_{1},\cdots,e_{\ell})$.
Then the pants decompositions $\mathrm{\textbf{P}}(\mathcal{T},T,\mathrm{O})$
and $\mathrm{\textbf{P}}(\mathcal{T},\emptyset,\mathrm{O})$ are equal.

######  Lemma 3.10 (Naturality).

Let $S$ be a compact connected orientable surface, and $P$ be a pants
decomposition of $S$. Let $b\in S\setminus P$ be a base point, and $\gamma$ be
a nerve for $(P,b)$. Let $\mathcal{T}$ be a pre-triangulation obtained by
possibly adding extra edges to the pre-triangulation
$\mathrm{\textbf{T}}(P,\gamma)$. There is an ordering $\mathrm{O}$ on the
edges of $\mathcal{T}$ such that
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})=P$.

###### Proof.

A pants decomposition of $S$ is a maximal collection of disjoint non-isotopic
essential simple closed curves on $S$. Therefore it is enough to show that for
a suitable choice of an ordering $\mathrm{O}$ we have
$P\subset\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$. Choose $\mathrm{O}$
such that the edges of $\mathrm{\textbf{T}}(P,\gamma)$ appear in the same
order that they were constructed in the inductive recipe of Construction 3.5;
if two (or three) edges were constructed simultaneously, the two (or three)
edges appear consecutively in the ordering $\mathrm{O}$. Finally, any edge of
$\mathcal{T}\setminus\mathrm{\textbf{T}}(P,\gamma)$ appears after the edges of
$\mathrm{\textbf{T}}(P,\gamma)$ in an arbitrary fashion. One can inductively
see that $P\subset\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$.

∎

###  3.3. Modifying a pre-triangulation and its effect on the associated pants
decomposition

In this subsection, we consider certain operations on pre-triangulations and
their effect on the associated pants decompositions.

######  Lemma 3.11 (Effect of subdividing a pre-triangulation on the
associated pants decomposition).

Let $\mathcal{T}$ be a pre-triangulation of a compact orientable surface $S$,
and $\mathrm{O}$ be an ordering on the edges of $\mathcal{T}$. Consider any of
the following two cases:

  1. a)

Let $\mathcal{T}^{\prime}$ be a pre-triangulation obtained by subdividing an
edge $e$ of $\mathcal{T}$. Define an ordering on the edges of
$\mathcal{T}^{\prime}$ as follows: if $e$ appears as the $i$th element in the
ordering $\mathrm{O}=(e_{1},e_{2},\cdots,e_{n})$ and
$e_{i}^{1},\cdots,e_{i}^{k}$ are the edges obtained by subdividing $e_{i}$,
define
$\mathrm{O}^{\prime}=(e_{1},\cdots,e_{i-1},e_{i}^{1},\cdots,e_{i}^{k},e_{i+1},\cdots,e_{n})$.

  2. b)

Let $R$ be a complementary region to $\mathcal{T}$, and $\mathcal{T}^{\prime}$
be the pre-triangulation obtained by adding a vertex $v$ in $R$ and connecting
some of the vertices of $R$ to $v$ by new edges. Define an ordering on the
edges of $\mathcal{T}^{\prime}$ where the edges of $\mathcal{T}$ appear first
and the newly added edges appear at the end in any order.

Then the associated pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ and
$\mathrm{\textbf{P}}(\mathcal{T}^{\prime},\mathrm{O}^{\prime})$ are equal.

###### Proof.

Part a) is clear. To see Part b), let
$O^{\prime}=(e_{1},\cdots,e_{\ell},e^{\prime}_{1},\cdots,e^{\prime}_{m})$
where $e^{\prime}_{j}$ are the newly added edges. Let $N_{i}$ and $F_{i}$ for
$1\leq i\leq\ell+m$ be the subsurfaces associated with
$(\mathcal{T}^{\prime},\mathrm{O}^{\prime})$ as in Construction 3.7. Part b)
follows from the following three facts:

  1. i)

$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ is obtained from
$\cup_{i=1}^{\ell}\partial F_{i}$ by discarding repeated curves. In particular
the inclusion
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})\subset\mathrm{\textbf{P}}(\mathcal{T}^{\prime},\mathrm{O}^{\prime})$
holds.

  2. ii)

$\partial R\subset\partial N_{\ell}$.

  3. iii)

Every essential simple closed curve in $R$ is parallel to a component of
$\partial R$. In particular, for $i>\ell$, the subsurface $\partial F_{i}$
contains no essential curve that was not already present in $\partial
F_{\ell}$.

∎

###  3.4. Changing the ordering and its effect on the associated pants
decomposition

######  Definition 3.12 (Consecutive transposition).

Let $\mathcal{T}$ be a pre-triangulation of a compact orientable surface, and
$\mathrm{O}$ and $\mathrm{O}^{\prime}$ be two orderings on the edges of
$\mathcal{T}$. We say that $\mathrm{O}^{\prime}$ is obtained from $\mathrm{O}$
by a _consecutive transposition_ if there are edges $e_{1}$ and $e_{2}$ of
$\mathcal{T}$ that are consecutive in the ordering $\mathrm{O}$ and such that
$\mathrm{O}^{\prime}$ is obtained from $\mathrm{O}$ by swapping the order of
$e_{1}$ and $e_{2}$.

######  Lemma 3.13.

Let $\mathcal{T}$ be a pre-triangulation of a compact orientable surface $S$.
Let $\mathrm{O}$ be an orderings on the edges of $\mathcal{T}$, and assume
that $\mathrm{O}^{\prime}$ is obtained from $\mathrm{O}$ by a consecutive
transposition. The distance between the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ and
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O}^{\prime})$ in the pants graph is
$O(1)$.

###### Proof.

Let $N_{1},\cdots,N_{n}$ (respectively $N^{\prime}_{1},\cdots,N^{\prime}_{n}$)
be the sequence of surfaces associated with $(\mathcal{T},\mathrm{O})$
(respectively $(\mathcal{T},\mathrm{O}^{\prime})$) as in Construction 3.7.
Define $F_{1},\cdots,F_{n}$ and $F^{\prime}_{1},\cdots,F^{\prime}_{n}$
similarly. Assume that $\mathrm{O}^{\prime}$ is obtained from $\mathrm{O}$ by
swapping the $j$th and $(j+1)$th element. Then

$\displaystyle F_{k}=F^{\prime}_{k}\hskip 8.53581pt\text{if}\hskip
8.53581pt|k-j|\geq 1.$

Hence the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O}^{\prime})$ and
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O}$ can differ only in curves that
are supported on the subsurface $F_{j+1}\setminus F_{j-1}$. After discarding
any disc or annulus components, $F_{j+1}\setminus F_{j-1}$ has Euler
characteristic at least $-2$. Hence, after discarding all disc and annulus
components, $F_{i+1}\setminus F_{i-1}$ is either a $4$-times punctured sphere,
a twice punctured torus, or a disjoint union of at most two pairs of pants.
The restrictions of $\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O}^{\prime})$ and
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ to the subsurface
$F_{j+1}\setminus F_{j-1}$, after discarding boundary-parallel curves, form
two pants decompositions $P$ and $P^{\prime}$ of $F_{j+1}\setminus F_{j-1}$.
We would like to give an upper bound for the distance between $P$ and
$P^{\prime}$ in the pants graph of $F_{j+1}\setminus F_{j-1}$. We claim that

$\displaystyle i(\partial N_{j},\partial N^{\prime}_{j})\leq 4.$

If at least one of $e_{j}$ and $e_{j+1}$ is a simple closed curve, or at least
one end of $e_{j}$ or $e_{j+1}$ is disjoint from $e_{1}\cup\cdots\cup
e_{j-1}$, then $\partial N_{j}$ and $\partial N^{\prime}_{j}$ can be isotoped
to be disjoint. So assume that $e_{j}$ and $e_{j+1}$ have both ends on
$e_{1}\cup\cdots\cup e_{j-1}$. Choose regular neighbourhoods $N$ and
$N^{\prime}$ of $e_{1}\cup\cdots\cup e_{j-1}$ in $S$ such that
$N\subset\text{int}N^{\prime}$ and $N^{\prime}\setminus N\cong\partial
N\times[0,1]$. Take a band $B_{j}\cong[0,1]\times[0,1]$ around $e_{j}$ and
connecting $\partial N$ to itself such that

  1. -

$B_{j}\cap\partial N=[0,1]\times\\{0,1\\}$; and

  2. -

$B_{j}\cap(\overline{N^{\prime}\setminus N})$ is identified with
$[0,1]\times([0,\frac{1}{4}]\cup[\frac{3}{4},1])$ in $B_{j}$ and with
$(B_{j}\cap\partial N)\times[0,1]$ in $N^{\prime}\setminus N$.

Choose a band $B_{j+1}$ around $e_{j+1}$, and disjoint from $B_{j}$, that
connects $\partial N^{\prime}$ to itself. Then $\partial N_{j}$ is isotopic to
$\partial(N\cup B_{j})$, and $\partial N_{j+1}$ is isotopic to
$\partial(N^{\prime}\cup B_{j+1})$. The only intersections of $\partial N_{j}$
and $\partial N_{j+1}$ come from the $4$ intersection points between $\partial
N^{\prime}$ and $\partial B_{j}$, proving the desired inequality. See Figure
4.

$B_{j}$ at 200 101 $B_{j+1}$ at 120 106

Figure 4. A schematic picture showing that the multicurves $\partial N_{j}$
and $\partial N_{j+1}$ (in red and blue respectively, and in different dashed
lines) intersect in at most $4$ points (solid dots). Here the horizontal
rectangle is $N^{\prime}\setminus N$, and the area below this rectangle is
$N$. There are other possibilities: the bands are allowed to have twists, and
the endpoints of the bands might not interlace or they might lie on different
components of $\partial N$.

Hence

$\displaystyle i(\partial F_{j},\partial F^{\prime}_{j})\leq i(\partial
N_{j},\partial N^{\prime}_{j})\leq 4.$

Therefore, the pants decompositions $P$ and $P^{\prime}$ have distance $O(1)$
in the pants graph of $F_{j+1}\setminus F_{j-1}$, proving the lemma. ∎

######  Corollary 3.14.

Let $\mathcal{T}$ be a pre-triangulation of a compact orientable surface $S$.
Let $\mathrm{O}$ and $\mathrm{O}^{\prime}$ be two orderings on the edges of
$\mathcal{T}$. The distance between the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ and
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O}^{\prime})$ in the pants graph is
$O(n^{2})$ where $n$ is the number of edges of $\mathcal{T}$.

###### Proof.

If $S_{n}$ is the symmetric group on $n$ elements, then every permutation
$\sigma\in S_{n}$ can be written as a product of at most

$\displaystyle 1+2+\cdots+(n-1)=O(n^{2})$

_consecutive transpositions_ of the form $\sigma_{j}=(j,j+1)$, where $1\leq
j\leq n-1$. Here $\sigma_{j}$ swaps the $j$-th and $(j+1)$-th elements. This
can be seen by induction on $n$: assume $\sigma(n)=i$ and note that
$\sigma_{n-1}\circ\cdots\circ\sigma_{i+1}\circ\sigma_{i}\circ\sigma$ fixes $n$
and hence can be considered as an element of $S_{n-1}$.

We can identify the symmetric group $S_{n}$ with the group of permutations of
the edges of $\mathcal{T}$ such that $\mathrm{O}$ corresponds to the identity.
Hence there are orderings $\mathrm{O}_{1},\cdots,\mathrm{O}_{k}$ on the edges
of $\mathcal{T}$ such that

  1. (1)

$\mathrm{O}=\mathrm{O}_{1}$, $\mathrm{O}^{\prime}=\mathrm{O}_{k}$;

  2. (2)

each $\mathrm{O}_{i+1}$ is obtained from $\mathrm{O}_{i}$ by a single
consecutive transposition; and

  3. (3)

$k=O(n^{2})$.

By Lemma 3.13, for each $1\leq i<k$ the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O}_{i+1})$ and
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O}_{i})$ have distance $O(1)$ in the
pants graph. The result now follows from the triangle inequality. ∎

###  3.5. Upper bound for distance between pants decompositions coming from
pre-triangulations

Given two pre-triangulations, and two orderings on their edges, the next lemma
gives an upper bound for the distance between their associated pants
decompositions.

######  Lemma 3.15.

Let $\mathcal{T}$ and $\mathcal{T}^{\prime}$ be pre-triangulations of a
compact orientable surface $S$. Assume that for any edge $e$ of $\mathcal{T}$
and any edge $e^{\prime}$ of $\mathcal{T}^{\prime}$, the intersection $e\cap
e^{\prime}$ is a disjoint union of subintervals of $e$ and also of
$e^{\prime}$. Here we allow a subinterval to be a single point as well. Let
$\mathrm{O}$ and $\mathrm{O}^{\prime}$ be orderings on the edges of
$\mathcal{T}$ and $\mathcal{T}^{\prime}$. Then the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ and
$\mathrm{\textbf{P}}(\mathcal{T}^{\prime},\mathrm{O}^{\prime})$ have distance
at most $O(n^{2}),$ where $n$ is the number of edges of the pre-triangulation
obtained by superimposing $\mathcal{T}$ and $\mathcal{T}^{\prime}$. In
particular, if $\mathcal{T}$ and $\mathcal{T}^{\prime}$ are transverse to each
other, and $|\mathcal{T}|$ and $|\mathcal{T}^{\prime}|$ are the number of
edges of $\mathcal{T}$ and $\mathcal{T}^{\prime}$, then $n\leq
2i(\mathcal{T},\mathcal{T}^{\prime})+|\mathcal{T}|+|\mathcal{T}^{\prime}|$.

###### Proof.

Let $\mathcal{U}$ be the pre-triangulation obtained by superimposing
$\mathcal{T}$ and $\mathcal{T}^{\prime}$. Construct an ordering
$\mathrm{O}_{2}$ on the edges of $\mathcal{U}$ as follows.

  1. (1)

First subdivide the edges of $\mathcal{T}$ by introducing the new vertices
that are in the intersection of $\mathcal{T}$ and $\mathcal{U}$. Let
$\mathcal{T}_{1}$ be the new pre-triangulation, and $\mathrm{O}_{1}$ a new
ordering on the edges of $\mathcal{T}_{1}$ constructed by repeated application
of Lemma 3.11 a).

  2. (2)

Secondly, starting with $(\mathcal{T}_{1},\mathrm{O}_{1})$, add the vertices
of $\mathcal{U}$ that are disjoint from $\mathcal{T}_{1}$ together with their
edges in $\mathcal{U}$ to obtain $\mathcal{U}$. Let $\mathrm{O}_{2}$ be an
ordering on the edges of $\mathcal{U}$ constructed by repeated application of
Lemma 3.11 b).

By Lemma 3.11, the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T},\mathrm{O})$ and
$\mathrm{\textbf{P}}(\mathcal{U},\mathrm{O}_{2})$ are equal. Similarly, there
is an ordering $\mathrm{O}^{\prime}_{2}$ on the edges of $\mathcal{U}$ such
that the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{T}^{\prime},\mathrm{O}^{\prime})$ and
$\mathrm{\textbf{P}}(\mathcal{U},\mathrm{O}^{\prime}_{2})$ are equal. Now by
Lemma 3.14 the distance between the pants decompositions
$\mathrm{\textbf{P}}(\mathcal{U},\mathrm{O}_{2})$ and
$\mathrm{\textbf{P}}(\mathcal{U},\mathrm{O}^{\prime}_{2})$ is $O(n^{2})$,
proving the first part of the lemma. For the second part we have

$\displaystyle 2n$ $\displaystyle=\text{sum of the degrees of vertices in
}\mathcal{U}\leq$ $\displaystyle
4i(\mathcal{T},\mathcal{T}^{\prime})+\text{sum of degrees in
}\mathcal{T}+\text{sum of degrees in }\mathcal{T}^{\prime}=$ $\displaystyle
4i(\mathcal{T},\mathcal{T}^{\prime})+2|\mathcal{T}|+2|\mathcal{T}^{\prime}|.$

∎

######  Corollary 3.16.

Let $P$ and $P^{\prime}$ be pants decompositions of a compact orientable
surface $S$. The distance between $P$ and $P^{\prime}$ in the pants graph is
$O(i(P,P^{\prime})^{2})$.

###### Proof.

Let $P_{\cap}$ be the union of simple closed curves that appear in both $P$
and $P^{\prime}$. Let $S_{1}$ be the surface obtained by cutting $S$ along
$P_{\cap}$, and let $P_{1}$ and $P^{\prime}_{1}$ be the corresponding pants
decompositions of $S_{1}$. Hence $P_{1}$ is the image of $P\setminus P_{\cap}$
in $S_{1}$, and $P^{\prime}_{1}$ is defined similarly. The pants
decompositions $P_{1}$ and $P^{\prime}_{1}$ are (disconnected) pre-
triangulations of $S_{1}$. Isotope $P^{\prime}_{1}$ to intersect $P_{1}$
minimally. Note that for any ordering $\mathrm{O}$ on $P_{1}$ we have
$\mathrm{\textbf{P}}(P_{1},\mathrm{O})=P_{1}$; and similarly
$\mathrm{\textbf{P}}(P^{\prime}_{1},\mathrm{O}^{\prime})=P^{\prime}_{1}$.
Hence the distance between the pants decompositions
$P_{1}=\mathrm{\textbf{P}}(P_{1},\mathrm{O})$ and
$P^{\prime}_{1}=\mathrm{\textbf{P}}(P^{\prime}_{1},\mathrm{O}^{\prime})$ is
$O(n^{2})$, where $n$ is the number of edges of the pre-triangulation
$P_{1}\cup P^{\prime}_{1}$ obtained by superimposing $P_{1}$ and
$P^{\prime}_{1}$. In particular, using the degree sum formula for the
4-regular graph $P_{1}\cup P^{\prime}_{1}$ we have

$n=\text{number of edges of }P_{1}\cup P^{\prime}_{1}=\frac{1}{2}\text{ degree
sum}=2i(P_{1},P^{\prime}_{1})=2i(P,P^{\prime}).$

∎

##  4\. Train tracks, and Agol–Hass–Thurston algorithm

Agol, Hass, and Thurston used their algorithm to count the number of connected
components of a simple closed multicurve $\gamma$ carried by a train track
$\tau$, in time that is bounded above by a polynomial function of $E\log(N)$,
where $E$ is the number of branches of $\tau$ and $N$ is the total weight of
$\gamma$ with respect to $\tau$. We are interested in the way that the
algorithm does this count; this will be via a sequence of _splitting_ and
_twirling_ (Definition 4.6, and Figure 10) the weighted train track until it
completely unwinds to the original curve $\gamma$. We will apply the AHT
algorithm to another similar setting and show in Proposition 4.12 that if one
starts with say a one-vertex triangulation $\mathcal{T}$ carried by a _based
train track_ $\tau$ (Definition 4.1), and set up an appropriate orbit counting
problem (Definition 4.4), then the AHT algorithm does the count via splitting
and twirling the based weighted train track until it completely unwinds it to
$\mathcal{T}$. Moreover the number of splitting and twirling is bounded above
by a polynomial function of $E\log(N)$, with $E$ equal to the number of
branches of the based train track and $N$ equal to the total weight of $\tau$.

###  4.1. Based integrally weighted train tracks, and orbit counting problems

Train tracks were introduced by Thurston to study simple closed multicurves on
a surface. Here we will work with 1-complexes, and a variant of a train track,
which we call a based train track, will be useful.

######  Definition 4.1 (Based integrally weighted train track).

A _based train track_ $(\tau,V)$ in a surface $S$ is an embedded finite
$1$-complex with a distinguished subset $V$ of its vertices called _base
vertices_ such that

  1. -

the embedding is $C^{1}$ in the interior of each edge of $\tau$;

  2. -

at every vertex $w\notin V$ there is a well-defined tangent line, and there
are edges entering $w$ from both directions. See Figure 5, top-left.

An edge of $\tau$ is called a _branch_. Fix a point $p_{e}$ in the interior of
each branch $e$. Each component of $e\setminus p_{e}$ is called a _half-
branch_. Therefore the half-branches at a vertex $w\notin V$ can be
partitioned into two non-empty subsets, which we can locally think of as
incoming vs outgoing; the choice of which subset is incoming and which is
outgoing is arbitrary. An _integral weight_ $\mu$ on $\tau$ is an assignment
of _positive integers_ to branches of $\tau$ such that at each vertex $w\notin
V$ the _switch condition_ is satisfied; i.e. sum of the weights of incoming
half-branches is equal to that of outgoing half-branches. We denote this
common number by $\mu_{w}$. A _based integrally weighted train track_
$(\tau,V,\mu)$ is a based train track $(\tau,V)$ together with an integral
weight $\mu$ on its branches. When $V$ is empty, we obtain the usual notions
of a _train track_ $\tau$ and an _integrally weighted train track_
$(\tau,\mu)$.

$2$ at 50 270 $2$ at 40 200 $2$ at 10 240 $3$ at 200 270 $3$ at 200 185 $3$ at
60 30 $2$ at 60 95 $2$ at 165 95 $1$ at 165 30

Figure 5. Left: on top, a non-base vertex of the based integrally weighted
train track $(\tau,V,\mu)$ is shown; a base vertex is depicted in the bottom.
The local picture for the associated $1$-complex $\mathcal{CC}(\tau,V,\mu)$ is
shown on the right.

######  Remark 4.2.

Note that unlike some texts, we do not require the complementary regions to a
train track to have negative (or non-positive) _index_ (a variant of the Euler
characteristic).

The following is analogous to the multicurve carried by an integrally weighted
train track.

######  Definition 4.3 (The $1$-complex carried by a based integrally weighted
train track).

Given a based integrally weighted train track $(\tau,V,\mu)$ on a surface $S$,
define the $1$-complex $\mathcal{CC}(\tau,V,\mu)$ embedded in $S$ as follows:
given a branch $e$ of $\tau$, not adjacent to any vertex in $V$, replace $e$
by $\mu_{e}$ parallel segments where $\mu_{e}$ is the weight of $e$. Given a
branch $e$ that is adjacent to a vertex $v\in V$, replace $e$ with $\mu_{e}$
parallel segments and identify one ends of these segments with $v$. At each
vertex $w\notin V$ of $\tau$, glue the endpoints of the incoming segments
adjacent to $w$ to those of the outgoing segments in an order-preserving way.
See Figure 5. We call $\mathcal{CC}(\tau,V,\mu)$ the _$1$ -complex carried by
$(\tau,V,\mu)$_.

Given a based integrally weighted train track $(\tau,V,\mu)$ on a surface $S$,
define a _branched neighbourhood $N(\tau,V,\mu)$_ of $(\tau,V,\mu)$ in $S$ as
follows: For each branch $e$, take a rectangle $R_{e}\cong e\times[0,\mu_{e}]$
around $e$ equipped with the horizontal foliation whose leaves consist of
$e\times\text{point}$. At each vertex $w\notin V$ glue the rectangles $R_{e}$
adjacent to $w$ along their vertical boundary $\partial e\times[0,\mu_{e}]$
according to their adjacency and the length of their vertical boundary; this
is possible by the switch condition. See Figure 6. For any base vertex $v\in
V$, let $\deg(v)$ be the number of half-branches adjacent to $v$. Take a
$2\deg(v)$-gon $P_{v}$ around $v$ and identify half of its edges with the
vertical boundaries of the adjacent rectangles in an alternating fashion; see
Figure 7. The _free sides_ of $P_{v}$ are those that are not identified with
the vertical boundary components of adjacent rectangles.

Note that $N(\tau,V,\mu)\setminus(\cup_{v\in V}P_{v})$ comes equipped with a
_horizontal foliation_ obtained by gluing together the horizontal foliations
of all rectangles $R_{e}$. Each rectangle $R_{e}$ has an $I$-bundle structure
given by fibres $\text{point}\times[0,\mu_{e}]$. For each point in the
interior of $e$, the _tie interval_ above the point is the $I$-fibre above
that. Given a vertex $w\notin V$, the _tie interval above $w$_ in
$N(\tau,\mu)$ is the union of the $I$-fibres over $w$ coming from the half-
branches adjacent to $w$; see Figure 6. The _tie interval_ above a base vertex
$v\in V$ is the disjoint union of $I$-fibres over $v$ coming from the half-
branches adjacent to $v$. A point $c$ on the tie interval above $w\notin V$ is
called a _cusp_ if a neighbourhood of $c$ in the leaf of the horizontal
foliation through it is not homeomorphic to $\mathbb{R}$; see Figure 6. Note
that $(\tau,V,\mu)$ is determined uniquely, up to isotopy, by the branched
neighbourhood $N(\tau,V,\mu)$.

$6$ at 30 155 $3$ at 30 115 $3$ at 30 77 $3$ at 295 155 $6$ at 295 85 $3$ at
295 25

$c_{1}$ at 510 100 $c_{2}$ at 550 70 $c_{3}$ at 510 32

Figure 6. A non-base vertex $w$ of a based integrally weighted train track
$(\tau,V,\mu)$ on the left, and the local picture for the branched
neighbourhood $N(\tau,V,\mu)$ on the right. The tie interval above $w$ is
shown by dashed lines, and the cusp points $c_{i}$ are depicted as dots on it.

$v$ at 50 80 $P_{v}$ at 295 80 $3$ at 30 30 $3$ at 30 130 $2$ at 110 95

Figure 7. A base vertex of a based integrally weighted train track
$(\tau,V,\mu)$ on the left, and the local picture for the branched
neighbourhood $N(\tau,V,\mu)$ on the right

A splitting of $(\tau,V,\mu)$ is defined just like a splitting of a weighted
train track except we require the support of the splitting to be disjoint from
$V$. Namely let $N(\tau,V,\mu)$ be a branched neighbourhood of $(\tau,V,\mu)$.
Consider a vertex $w\notin V$, and the tie interval $t$ above $w$. Let $p$ be
a cusp point of $t$, and $l$ be the leaf of the horizontal foliation on
$N(\tau,V,\mu)\setminus(\cup_{v\in V}P_{v})$ passing through $p$ and oriented
starting at $p$. Denote by $e$ the first branch of $\tau$ travelled by $l$,
and give $e$ the orientation from $l$. If $l\neq p$, let $q\neq p$ be the
first point of intersection of $l$ with the union of the tie intervals above
the vertices of $\tau$, and denote the segment of $l$ between $p$ and $q$ by
$l_{0}=[p,q)$ where $l_{0}$ contains $p$ but not $q$. If $l=p$, set $l_{0}=p$.
Then the _splitting of $N(\tau,V,\mu)$ along the cusp point $p$ (or the leaf
segment $l_{0}$)_ is defined as the closed complement
$N(\tau,V,\mu)\setminus\setminus l_{0}$ with one exception: if $q$ lies on a
tie interval above a base vertex $v\in V$ then we split $N(\tau,V,\mu)$ along
$l_{0}$ and then modify the polygon $P_{v}$ by adding a free side around $q$;
see Figure 9. Sometimes we refer to this operation as a splitting of
$N(\tau,V,\mu)$ along the branch $e$, if we do not need to stress the choice
of the cusp point $p$. We say that $(\tau^{\prime},V,\mu^{\prime})$ is
obtained by _splitting_ $(\tau,V,\mu)$ if $N(\tau^{\prime},V,\mu^{\prime})$ is
obtained by splitting $N(\tau,V,\mu)$; note that the set of base vertices $V$
is not changed during the splitting.

Just as in splittings of (unweighted) train tracks, it makes sense to talk
about a splitting of an (unweighted) based train track $(\tau,V)$ along a
branch $e$. Let $e$ be an oriented edge with the initial vertex $w\notin V$
and the terminal vertex $w^{\prime}$. A splitting of $(\tau,V)$ is a
combinatorial local move as in Figure 8.

Figure 8. Splitting an unweighted train track along an edge or a vertex. The
picture on the left is replaced with the one on the right, after splitting
along the middle vertex or edge.

$P_{v}$ at 75 55 $P^{\prime}_{v}$ at 75 10

Figure 9. Splitting of a branched neighbourhood. The shaded regions are the
rectangles over various edges. The dashed line is the leaf segment $l=[p,q)$,
where $q$ lies on $P_{v}$ here.

######  Definition 4.4 (Orbit counting problem associated with a based
integrally weighted train track).

Let $(\tau,V,\mu)$ be a based integrally weighted train track. For each vertex
$w\notin V$, define $\mu_{w}$ as sum of the weights of the incoming (or
outgoing) edges at $w$, and pick an interval $t_{w}\subset\mathbb{N}$ of
length $\mu_{w}$. Visually we think of $t_{w}$ as the intersection of the tie
interval above $w$ with the carried 1-complex $\mathcal{CC}(\tau,V,\mu)$.
Similarly, let $e_{1},\cdots,e_{r}$ be the half-branches adjacent to base
vertices, and for each $e_{j}$ consider an interval $t_{j}\subset\mathbb{N}$
of length $\mu_{e_{j}}$. Again we think of $t_{j}$ as the intersection of a
component of the tie interval above a base vertex $v$ with the 1-complex
$\mathcal{CC}(\tau,V,\mu)$. By abuse of notation, we call the intervals
$t_{w}$ and $t_{j}$ the tie intervals. Pick intervals $I_{j}\subset\mathbb{N}$
where the index $j$ varies in $\mathcal{J}:=\\{1,\cdots,r\\}\cup\\{w|w\notin
V\text{ is a vertex}\\}$ such that

  1. (1)

the interval $I_{j}$ has the same length as $t_{j}$ for $j\in\mathcal{J}$;

  2. (2)

the intervals $I_{j}$ for $j\in\mathcal{J}$ are pairwise disjoint and their
union is $[1,N]$ for some positive integer $N$; and

  3. (3)

the union of $I_{j}$ where $j\in\\{1,\cdots,r\\}$ is $[1,M]$ for some positive
integer $M$.

Pick isometric identifications $i_{j}\colon t_{j}\rightarrow I_{j}$; there are
two such choices for each index $j$. The data
$\mathcal{I}:=(t_{j},I_{j},i_{j})_{j\in\mathcal{J}}$ is called an _initial
interval identification_. Define an orbit counting problem
$\mathrm{OCP}(\tau,V,\mu,\mathcal{I})$ as follows. Let $e$ be an edge of
$\tau$ connecting vertices $w$ and $w^{\prime}$, and assume that
$I_{w^{\prime}}$ lies to the right of $I_{w}$ as subsets of $\mathbb{N}$.
Define an isometric pairing $g_{e}$ by following the segments of the
$1$-complex $\mathcal{CC}(\tau,V,\mu)$ along the rectangle $R_{e}$ where
$\text{domain}(g_{e})\subset I_{w}$ and $\text{range}(g_{e})\subset
I_{w^{\prime}}$. Then the isometric pairings $\\{g_{e}|e\text{ is a
branch}\\}$ form the orbit counting problem
$\mathrm{OCP}(\tau,V,\mu,\mathcal{I})$ with total interval $[1,N]$.

######  Remark 4.5.

By construction, every point in $[1,N]$ appears in the domain and range of at
most two pairings of $\mathrm{OCP}(\tau,V,\mu,\mathcal{I})$.

The following geometric operation on a based integrally weighted train track
appears naturally when applying the AHT algorithm to the orbit counting
problem $\mathrm{OCP}(\tau,V,\mu,\mathcal{I})$.

######  Definition 4.6 (Twirling).

Let $(\tau,V,\mu)$ be a based integrally weighted train track on an orientable
surface $S$, and let $N=N(\tau,V,\mu)$ be a branched neighbourhood of it. Let
$w\notin V$ be a vertex, and $e$ be a branch connecting $w$ to itself. Denote
the tie interval above $w$ by $t$, and identify $t$ with $[0,\mu_{w}]$ with
$0$ the _top_ point of $t$. Let $e\times[0,\mu_{e}]\cong R_{e}\subset N$ be
the rectangle around $e$. Write $\partial e=\partial_{-}e\cup\partial_{+}e$,
and orient $e$ from $\partial_{-}e$ to $\partial_{+}e$. Call
$\partial_{-}e\times[0,\mu_{e}]$ the negative vertical boundary of $R_{e}$,
similarly define the positive vertical boundary. Let the positive side of $t$
be the side of $\partial_{+}e$; similarly for the negative side. Assume that
$R_{e}$ starts and ends on different sides of $t$, and that the images of the
negative and positive vertical boundary components of $R_{e}$ in $N$ intersect
each other. Assume that $e$ is the top branch coming into $w$ on the negative
side of $t$. See Figure 10.

Let $p_{1},\cdots,p_{k}$ be the cusp points on $t$ that lie above
$\partial_{+}e\times(0,\mu_{e})$. Let $l_{i}$ be the leaf of the horizontal
foliation through $p_{i}$, and $s_{i}$ be connected component of $l_{i}\cap
R_{e}$ that contains $p_{i}$. Split $N$ along all $s_{i}$. More precisely, set
$p_{i}^{0}=p_{i}$, and if $l_{i}\neq\\{p_{i}^{0}\\}$ then define $p_{i}^{1}$
to be the first intersection point of $l_{i}$ with the positive vertical
boundary of $R_{e}$; and $p_{i}^{1}$ is not defined otherwise. Then by the
orientability of $S$, the relative order of $p_{i}^{1}$ on $t$ is the same as
that of $p_{i}$; i.e. $p_{i}^{1}$ is on top of $p_{j}^{1}$ if $i<j$ as long as
both are defined. Now if all $p_{i}^{1}$ are defined and lie in the negative
vertical boundary of $R_{e}$, we can repeat the same process starting with
$p_{i}^{1}$ to obtain points $p_{i}^{2}$ and so on. Hence there is an $m$ such
that at least one of the points $p_{1}^{m},\cdots,p_{k}^{m}$ is either not
defined or does not lie in the negative vertical boundary of $R_{e}$; say only
$p_{1}^{m},\cdots,p_{n}^{m}$ are defined and lie in the negative vertical
boundary of $R_{e}$ for some $0\leq n<k$. Then we split one further time along
$p_{1}^{m},\cdots,p_{n}^{m}$. The resulting based integrally weighted train
track is called a _twirling of $(\tau,V,\mu)$ along the oriented branch $e$_.

######  Remark 4.7.

If $(\tau^{\prime},V,\mu^{\prime})$ is obtained from $(\tau,V,\mu)$ via a
splitting, then the number of branches of $\tau^{\prime}$ is no more than that
of $\tau$. Since every twirling is a concatenation of a number of splits, the
same holds if $(\tau^{\prime},V,\mu^{\prime})$ is obtained from $(\tau,V,\mu)$
via a twirling.

$w$ at 410 90 $e$ at 385 110

$A$ at 30 145 $A$ at 290 20

a at 455 50 b at 460 70 c at 450 105

Figure 10. A twirling. A neighbourhood of the branch $e$ and the underlying
train track is shown on the right. Here $k=2$, $m=2$, and $n=1$. In the left
side, the two $A$ should be identified with each other to construct the
rectangle $R_{e}$. The solid points from top to bottom are $p_{1}^{0}$,
$p_{2}^{0}$, $p_{1}^{1}$, $p_{2}^{1}$, $p_{1}^{2}$, $p_{2}^{2}$ and
$p_{1}^{3}$. The numbers a, b, and c are the weights of $e$ and the two edges
coming into it from right.

######  Lemma 4.8 (Effect of twirling on the underlying train track).

Let $(\tau,V,\mu)$ be a based integrally weighted train track on an orientable
surface $S$. Assume that $(\tau^{\prime},V,\mu^{\prime})$ is obtained from
$(\tau,V,\mu)$ by twirling along the branch $e$. Let $\alpha$ be the simple
closed curve that is the closure of $e$, and $m$ be as in Definition 4.6.
Denote the Dehn twist along $\alpha$ by $T_{\alpha}$. Then $\tau^{\prime}$ is
obtained from $\tau$ via twisting by $(T_{\alpha})^{m-1}$ followed by
splitting the (unweighted) based train track $(T_{\alpha})^{m-1}(\tau,V)$ a
number of times along $e$.

###### Proof.

Define the points $p_{i}^{r}$ as in Definition 4.6. Let $l_{i}^{r}$ be the
segment of $l_{i}$ between $p_{i}^{r}$ and $p_{i}^{r+1}$, if both $p_{i}^{r}$
and $p_{i}^{r+1}$ are defined. Then repeatedly splitting along
$\cup_{i=1}^{k}l_{i}^{r}$ for $r=0,1,\cdots,m-2$ replaces $\tau$ with
$(T_{\alpha})^{m-1}(\tau)$. Then splitting along $\cup_{i=1}^{k}p_{i}^{m-1}$
followed by splitting further along $\cup_{i=1}^{n}p_{i}^{m}$ is a sequence of
splits along the oriented branch $e$. See Figure 10. ∎

######  Lemma 4.9.

Let $(\tau,V,\mu)$ be a based integrally weighted train track on a compact
orientable surface $S$. Assume that the carried 1-complex
$\mathcal{CC}(\tau,V,\mu)$ is a polygonal decomposition (respectively pre-
triangulation) of $S$. Then the underlying 1-complex of $\tau$ is also a
polygonal decomposition (respectively a pre-triangulation).

###### Proof.

The Euler characteristics of the complementary components of a train track
will not increase as a result of splitting, but they might decrease if some
complementary components merge together. Now each complementary component of
$\mathcal{CC}(\tau,V,\mu)$ has Euler characteristic at least $1$ (respectively
$-1$). It follows that the complementary components of $\tau^{\prime}$ have
Euler characteristic at least $1$ (respectively $-1$) as well. It remains to
show that no complementary component of $\tau$ is topologically a torus minus
a disc. Observe that if $\tau^{\prime}$ is obtained by splitting $\tau$, and
$\alpha$ is an essential (i.e. homotopically non-trivial and non-boundary-
parallel) curve in a complementary component $R$ of $\tau$, then some
complementary component of $\tau^{\prime}$ also contains an essential curve.
It follows that no complementary component $R$ of $\tau$ is a torus minus a
disc; otherwise $R$ contains an essential curve which implies that some
complementary component of $\mathcal{CC}(\tau,V,\mu)$ also contains an
essential curve, a contradiction.

∎

######  Lemma 4.10.

Let $(\tau,V,\mu)$ be a based integrally weighted train track with $E$ edges
on a compact orientable surface $S$. Assume that
$(\tau^{\prime},V,\mu^{\prime})$ is obtained from $(\tau,V,\mu)$ by either a
split or a twirl. Assume that the underlying 1-complex of $\tau$ is a pre-
triangulation. Set $k=\chi(\tau^{\prime})-\chi(\tau)\geq 0$, where
$\chi(\tau)$ is the Euler characteristic of $\tau$ as a 1-complex. For every
ordering $\mathrm{O}$ on the edges of $\tau$, there is an ordering
$\mathrm{O}^{\prime}$ on the edges of $\tau^{\prime}$ such that the pants
decompositions $\mathrm{\textbf{P}}(\tau,\mathrm{O})$ and
$\mathrm{\textbf{P}}(\tau^{\prime},\mathrm{O}^{\prime})$ have distance
$O((k+1)E)$ in the pants graph.

Moreover, given the train track $\tau$, the ordering $\mathrm{O}$, and the
split or twirl move from $\tau$ to $\tau^{\prime}$, there is an algorithm that
constructs such an ordering $\mathrm{O}^{\prime}$ together with a sequence of
$O((k+1)E)$ consecutive transpositions taking $\mathrm{O}$ to
$\mathrm{O}^{\prime}$. The algorithm runs in time that is a polynomial
function of $E$. Here the train track is given as follows: the complementary
components of $\tau$ are cusped polygons, annuli, or pairs of pants; these are
given together with their side identifications. Furthermore, the twirl or
split move is given by specifying an oriented edge.

###### Proof.

We first show how to reduce to the case where $\tau^{\prime}$ is obtained from
$\tau$ by splitting a number of times along the same oriented edge. Assume
that $(\tau^{\prime},V,\mu^{\prime})$ is obtained from $(\tau,V,\mu)$ by a
twirl along a branch $e$, and let $\alpha$ be the simple closed curve that is
the closure of $e$. By Lemma 4.8, $\tau^{\prime}$ is obtained from $\tau$ by
some power $(T_{\alpha})^{\ell}$ of the Dehn twist along $\alpha$ followed by
splitting $(T_{\alpha})^{\ell}(\tau,V)$ a number of times along $e$. Given the
ordering $\mathrm{O}$ on $\tau$, we can apply at most $E$ consecutive
transpositions to obtain $\mathrm{O}_{1}$ such that $e$ appears as the first
edge in $\mathrm{O}_{1}$. The distance between the pants decompositions
$\mathrm{\textbf{P}}(\tau,\mathrm{O})$ and
$\mathrm{\textbf{P}}(\tau,\mathrm{O}_{1})$ is $O(E)$ by Lemma 3.13. Since
$(T_{\alpha})^{\ell}$ is a mapping class, it induces an ordering
$((T_{\alpha})^{\ell})_{*}(\mathrm{O}_{1})$ on $(T_{\alpha})^{\ell}(\tau)$. We
claim that the pants decompositions $\mathrm{\textbf{P}}(\tau,\mathrm{O}_{1})$
and
$\mathrm{\textbf{P}}((T_{\alpha})^{\ell}(\tau),((T_{\alpha})^{\ell})_{*}(\mathrm{O}_{1}))$
are the same. To see this, note that $e$ appears as the first edge in
$\mathrm{O}_{1}$, and so Construction 3.7 produces $\alpha$ as the first curve
in $\mathrm{\textbf{P}}(\tau,\mathrm{O}_{1})$. Hence

$\mathrm{\textbf{P}}((T_{\alpha})^{\ell}(\tau),((T_{\alpha})^{\ell})_{*}(\mathrm{O}_{1}))=(T_{\alpha})^{\ell}(\mathrm{\textbf{P}}(\tau,\mathrm{O}_{1}))=\mathrm{\textbf{P}}(\tau,\mathrm{O}_{1}).$

The last equality holds because Dehn twisting a pants decomposition along one
of its curves does not change the pants decomposition. This shows that at the
cost of distance $O(E)$ in the pants graph, we may replace $(\tau,\mathrm{O})$
with $((T_{\alpha})^{\ell}(\tau),((T_{\alpha})^{\ell})_{*}(\mathrm{O}_{1}))$,
completing the reduction.

Now assume that $\tau^{\prime}$ is obtained from $\tau$ by splitting a number
of times along the same oriented edge $e$. Again at the cost of distance $E$
in the pants graph, we may assume that $e$ appears as the first edge in
$\mathrm{O}$. Assume that $k\leq 1$; the general case follows from this. Since
$\tau$ splits to $\tau^{\prime}$, the train track $\tau^{\prime}$ is carried
by $\tau$. This means that there is a neighbourhood $N(\tau)$ of $\tau$
foliated by interval fibers, a projection map $\pi\colon
N(\tau)\rightarrow\tau$ collapsing each fiber to a point, and a map
$f\colon\tau^{\prime}\rightarrow N(\tau)$ transverse to the fibers. In
particular, the composition $\pi\circ f$ gives a map $\pi\circ
f\colon\tau^{\prime}\rightarrow\tau$, which we abbreviate to
$\pi\colon\tau^{\prime}\rightarrow\tau$. Consider the following cases:

Case 1): If $k=0$ and $e$ has distinct endpoints. Here $T:=\pi^{-1}(e)$ is a
tree. Contract $e$ in $\tau$ to a point to obtain a pre-triangulation
$\tau_{1}$. Let $\mathrm{O}_{1}$ be the ordering on $\tau_{1}$ induced from
the ordering $\mathrm{O}$ on $\tau$ (by removing $e$). By Construction 3.7,
since $e$ appears as the first edge in $\mathrm{O}$ and the endpoints of $e$
are distinct, we have

$\mathrm{\textbf{P}}(\tau,\mathrm{O})=\mathrm{\textbf{P}}(\tau_{1},\mathrm{O}_{1}).$

For each point in $\pi^{-1}(\partial e)$, add it as a vertex (possibly of
degree two) in $\tau^{\prime}$. Define an ordering $\mathrm{O}^{\prime}$ on
$\tau^{\prime}$, where the restriction of $\mathrm{O}^{\prime}$ to
$\tau^{\prime}-T$ agrees with the restriction of $\mathrm{O}$ to $\tau-e$ and
such that the edges of $\tau^{\prime}$ lying in $T$ appear first (in any
order) in $\mathrm{O}^{\prime}$. Contract the tree $T$ in $\tau^{\prime}$ to
obtain $\tau^{\prime}_{1}$, let $\mathrm{O}^{\prime}_{1}$ be the ordering on
$\tau^{\prime}_{1}$ obtained from the ordering $\mathrm{O}^{\prime}$ on
$\tau^{\prime}$ by deleting the edges that lie in $T$. We have

$\mathrm{\textbf{P}}(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{1})=\mathrm{\textbf{P}}(\tau^{\prime},\mathrm{O}^{\prime}).$

Note that $(\tau_{1},\mathrm{O}_{1})$ is equal to
$(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{1})$ up to isotopy. Hence

$\mathrm{\textbf{P}}(\tau,\mathrm{O})=\mathrm{\textbf{P}}(\tau_{1},\mathrm{O}_{1})=\mathrm{\textbf{P}}(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{1})=\mathrm{\textbf{P}}(\tau^{\prime},\mathrm{O}^{\prime}).$

Case 2): If $k=1$ and $e$ has distinct endpoints. Here $\pi^{-1}(e)$ has two
connected components, each of which is a tree. Contract $e$ in $\tau$ to
obtain $(\tau_{1},\mathrm{O}_{1})$. For each point in $\pi^{-1}(\partial e)$
that is not a vertex of $\tau^{\prime}$, add it as a vertex of degree two to
obtain $\hat{\tau^{\prime}}$. Attach an extra edge $e^{\prime}$ (joining the
two components of $T$) to $\hat{\tau^{\prime}}$ to obtain a 1-complex
$\tau^{\prime}_{1}$ such that if we contract $e^{\prime}\cup\pi^{-1}(e)$ in
$\tau^{\prime}_{1}$ the result is isotopic to $\tau_{1}$. See Figure 11.

Figure 11. The train track $\tau^{\prime}$ on the right is obtained by
splitting $\tau$ (left). The added edge $e^{\prime}$ is shown with a dotted
segment. The edge $e$ and the preimage $\pi^{-1}(e)$ are shown in solid blue
segments.

Let $\mathrm{O}^{\prime}_{1}$ be the ordering on $\tau^{\prime}_{1}$ such that
the edges in $e^{\prime}\cup\pi^{-1}(e)$ appear first, and otherwise it agrees
with $\mathrm{O}_{1}$. We have

$\mathrm{\textbf{P}}(\tau,\mathrm{O})=\mathrm{\textbf{P}}(\tau_{1},\mathrm{O}_{1})=\mathrm{\textbf{P}}(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{1}).$

Let $\mathrm{O}^{\prime}_{2}$ be the ordering on $\tau^{\prime}_{1}$ such that
$e^{\prime}$ appears last, and otherwise the ordering agrees with
$\mathrm{O}^{\prime}_{1}$. Then $\mathrm{O}^{\prime}_{2}$ can be obtained from
$\mathrm{O}^{\prime}_{1}$ by $O(E)$ consecutive transpositions. Therefore, the
distance between
$\mathrm{\textbf{P}}(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{2})$ and
$\mathrm{\textbf{P}}(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{1})$ is $O(E)$.
Let $\hat{\mathrm{O}^{\prime}}$ be the ordering on $\hat{\tau^{\prime}}$
obtained by removing $e^{\prime}$ (the last edge) from $\tau^{\prime}_{1}$. We
claim that
$\mathrm{\textbf{P}}(\hat{\tau^{\prime}},\hat{\mathrm{O}^{\prime}})$ is equal
to $\mathrm{\textbf{P}}(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{2})$. This is
because, $e^{\prime}$ appears last in $\mathrm{O}^{\prime}_{2}$, and given
that $\tau^{\prime}$ and hence $\hat{\tau^{\prime}}$ is a pre-triangulation,
adding $e$ to $\hat{\tau^{\prime}}$ (to obtain $\tau^{\prime}_{1}$) does not
create any new curve in Construction 3.7. Hence the distance between
$\mathrm{\textbf{P}}(\tau,\mathrm{O})=\mathrm{\textbf{P}}(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{1})$
and
$\mathrm{\textbf{P}}(\hat{\tau^{\prime}},\hat{\mathrm{O}^{\prime}})=\mathrm{\textbf{P}}(\tau^{\prime}_{1},\mathrm{O}^{\prime}_{2})$
is $O(E)$. On the other hand, the ordering $\hat{\mathrm{O}^{\prime}}$ on
$\hat{\tau^{\prime}}$ induces an ordering $\mathrm{O}^{\prime}$ on
$\tau^{\prime}$, simply by deleting the vertices $\pi^{-1}(e)$ and we have
$\mathrm{\textbf{P}}(\hat{\tau^{\prime}},\hat{\mathrm{O}^{\prime}})=\mathrm{\textbf{P}}(\tau^{\prime},\mathrm{O}^{\prime})$.

Case 3: If $k\leq 1$ and the endpoints of $e$ coincide. In this case we can
add a vertex of degree $2$ in the middle of $e$ to obtain edges $e_{1}$ and
$e_{2}$ such that $e_{1}\cup e_{2}=e$, each $e_{i}$ has distinct endpoints,
and the splittings along $e$ can be obtained by splittings along $e_{1}$
followed by splittings along $e_{2}$. This reduces the problem to the previous
two cases.

It is straightforward to see that the above construction of
$\mathrm{O}^{\prime}$ can be done algorithmically in time that is a polynomial
function of $E$, $|\chi(S)|$, and $k$. Since $\tau$ is a pre-triangulation,
$E$ is at least linear in $|\chi(S)|$. Similarly, $k$ is at most $E$.
Therefore the algorithm runs in polynomial time in $E$.

∎

###  4.2. Simplifying a based integrally weighted train track using the AHT
algorithm

The following is a restatement of a definition due to Dynnikov and Wiest
[DW07, Definition 2.8 and Remark 2.2]. It will allow us, as in the case of
Dynnikov and Wiest, to obtain an improved estimate for the running time of the
AHT algorithm applied to the orbit counting problem associated with an
integrally weighted train track.

######  Definition 4.11 (AHT-complexity).

Let $S$ be a compact orientable surface, and $(\tau,V,\mu)$ be a based
integrally weighted train track on $S$. Let
$\mathcal{P}=\mathrm{OCP}(\tau,V,\mu,\mathcal{I})$ be the orbit counting
problem for some initial interval identification $\mathcal{I}$. Denote the
pairings of $\mathcal{P}$ by $g_{e}$ where $e$ ranges over the branches of
$\tau$. Denote by $z_{1},\cdots,z_{r}$ the length of the intervals
$\text{domain}(g_{e})$; i.e. $z_{i}$ are the measures associated to the
branches of $\tau$. Let $N$ be the maximum natural number appearing in the
intervals $\text{domain}(g_{e})\cup\text{range}(g_{e})$. Denote by $\tilde{z}$
the length of the narrower interval attached to $N$; i.e. if $N$ is an
endpoint of a tie interval $t_{w}$ then $\tilde{z}$ is the smaller measure for
the two branches that come into $t_{w}$ on the side of $N$. Define the _AHT-
complexity_ as

$c_{\text{AHT}}(\mathcal{P}):=r+\sum_{i=1}^{r}\log(z_{i})-\frac{1}{2}\log(\tilde{z}).$

The next proposition studies the effect of running one shifted cycle of the
AHT algorithm on a based integrally weighted track track $(\tau,V,\mu)$, or
more precisely on the associated orbit counting problem
$\mathrm{OCP}(\tau,V,\mu,\mathcal{I})$. Roughly speaking, it states that
running one shifted cycle of the AHT algorithm on
$\mathrm{OCP}(\tau,V,\mu,\mathcal{I})$ gives
$\mathrm{OCP}(\tau^{\prime},V^{\prime},\mu^{\prime},\mathcal{I}^{\prime})$ for
a new based integrally weighted train track
$(\tau^{\prime},V^{\prime},\mu^{\prime})$ that is obtained from $(\tau,V,\mu)$
via splitting or twirling. In what follows, we write $(\tau,V,\mu)$ as a
disjoint union of the _active part_ $(\tau_{a},V_{a},\mu_{a})$ and the
_stationary part_ $(\tau_{s},V_{s},\mu_{s})$. The stationary part is
completely unwound, so that $\tau_{s}$ has no vertices beside its base
vertices $V_{s}$. We apply the AHT algorithm to the active part, and as a
result the active and stationary parts are updated. While this notation is
cumbersome, it will be useful to keep track of the stationary part. See Remark
4.13 in the proof of the proposition.

######  Proposition 4.12 (Applying the AHT algorithm to a weighted train
track).

Let $S$ be a compact orientable surface, and $(\tau,V,\mu)$ be a based
integrally weighted track track on $S$ having $E$ branches. Assume that
$(\tau,V,\mu)$ is a disjoint union of $(\tau_{a},V_{a},\mu_{a})$ and
$(\tau_{s},V_{s},\mu_{s})$, where $\tau_{a}$ (the active part of $\tau$) has
at least one vertex besides its base vertices $V_{a}$, and $\tau_{s}$ (the
stationary part of $\tau$) has no vertices besides $V_{s}$. Let
$\mathcal{I}_{a}$ be an initial interval identification for
$(\tau_{a},V_{a},\mu_{a})$. There is a based integrally weighted train track
$(\tau^{\prime},V^{\prime},\mu^{\prime})$ on $S$, which is a disjoint union of
active $(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a})$ and stationary
$(\tau^{\prime}_{s},V^{\prime}_{s},\mu^{\prime}_{s})$ parts, and an initial
interval identification $\mathcal{I}^{\prime}_{a}$ on the active part of
$\tau^{\prime}$ with the following properties:

  1. (1)

Applying one shifted cycle of the AHT algorithm to
$\mathrm{OCP}(\tau_{a},V_{a},\mu_{a},\mathcal{I}_{a})$ gives
$\mathrm{OCP}(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a},\mathcal{I}^{\prime}_{a})$.

  2. (2)

$(\tau^{\prime},V^{\prime},\mu^{\prime})$ is obtained from $(\tau,V,\mu)$ by
either

     * •

at most $E$ splits along the same oriented branch of $\tau$; or

     * •

a twirling.

  3. (3)

The AHT-complexity of
$\mathrm{OCP}(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a},\mathcal{I}^{\prime}_{a})$
is at most that of $\mathrm{OCP}(\tau_{a},V_{a},\mu_{a},\mathcal{I}_{a})$
minus one.

Moreover, there is an algorithm that constructs
$(\tau^{\prime},V^{\prime},\mu^{\prime})$ together with its partition into
active and stationary parts and the splits or twirl move from $(\tau,V,\mu)$
to $(\tau^{\prime},V^{\prime},\mu^{\prime})$, in time that is a polynomial
function of $E$ and $\log|\mu|$.

###### Proof.

We first prove items (1)–(2). Recall the various steps in the orbit counting
algorithm:

  1. (1)

Delete any pairings that are restrictions of the identity.

  2. (2)

Make any possible contractions.

  3. (3)

Trim all orientation-reversing pairings whose domain and range overlap.

  4. (4)

Perform periodic mergers.

  5. (5)

Find a maximal $g_{i}$. For each $g_{j}\neq g_{i}$ whose range is contained in
$[c_{i},N^{\prime}]$, transmit $g_{j}$ by $g_{i}$.

  6. (6)

Find the smallest value of $c$ such that the interval $[c,N^{\prime}]$
intersects the range of exactly one pairing. Truncate the pairing whose range
contains the interval $[c,N^{\prime}]$.

######  Remark 4.13.

Before starting the proof, we note that the reason for updating the stationary
part of the weighted train track is that step (1) above may delete a pairing.
This results in loss of data regarding some part of $\tau$. To remedy this,
whenever step (1) deletes a paring, we preserve the data by adding the
corresponding part of the train track to the stationary part. For example, if
the carried 1-complex of $(\tau,\mu)$ is a pants decomposition $P$, then by
successively applying the AHT algorithm all components of $P$ will eventually
be removed, and so we keep a record of them by defining
$\tau^{\prime}_{\mathrm{s}}$.

Consider the first shifted cycle of the AHT algorithm applied to
$\mathrm{OCP}(\tau_{a},V_{a},\mu_{a},\mathcal{I}_{a})$. This consists of
applying steps (1)–(4). First consider the combined effect of steps (1)–(2).
In step (2), there could be no contractions unless we had deleted some pairing
in step (1) that was the restriction of the identity. This happens only when
$\tau$ has a component that is a simple closed curve. If this happens, then we
add the resulting weighted simple closed curve to $(\tau_{s},V_{s},\mu_{s})$.
Note that steps (3)–(4) are not applicable: there is no trimming since $S$ is
orientable, and periodic mergers are not possible since every point in
$[1,N^{\prime}]$ appears in the domain and range of at most $2$ pairings.
Hence the result holds for the first shifted cycle of the AHT algorithm.

Now consider a shifted cycle of the AHT algorithm consisting of steps (5)–(6)
followed by steps (1)–(4). As argued before, steps (3)–(4) are not applicable.

First we show that step (5) includes a transmission. The union of the tie
intervals above the base vertices $V_{a}$ is $[1,M]$ for some integer $M$ by
the definition of the initial interval identification; see Definition 4.4.
Furthermore $M\neq N^{\prime}$ by the assumption that $\tau_{a}$ has at least
one vertex besides the base vertices $V_{a}$. Hence, there is a vertex
$w^{\prime}\notin V_{a}$ such that the tie interval $t^{\prime}$ above
$w^{\prime}$ includes $N^{\prime}$. Let the top of $t^{\prime}$ be the side
containing $N^{\prime}$. Then at least one of the two half-branches entering
$t^{\prime}\subset N(\tau_{a},V_{a},\mu_{a})$ on the top side corresponds to a
maximal pairing, allowing a transmission.

Let $g_{i}$ be a maximal pairing, and $g_{j_{1}},\cdots,g_{j_{k}}$ be the
pairings whose range is contained in $[c_{i},N^{\prime}]$. After re-indexing,
we may assume that $\\{j_{1},\cdots,j_{k}\\}=\\{1,\cdots,k\\}$. Let
$g_{i}=g_{e}$ for a branch $e$ with initial vertex $w$ and terminal vertex
$w^{\prime}\notin V_{a}$. Let $e_{-}$ and $e_{+}$ be the half-branches of $e$
adjacent to $w$ and $w^{\prime}$. Let $p_{1},\cdots,p_{\ell}$ be the cusp
points on $\text{range}(g_{e})\subset t^{\prime}$. See e.g. Figure 10 left,
where there are two such cusp points. Note that $\ell\geq k$ with equality if
and only if for each $1\leq j\leq k$ we have
$\text{domain}(g_{j})\nsubseteq\text{range}(g_{e})$.

For $1\leq j\leq\ell$, denote by $l_{j}$ the leaf of the horizontal foliation
on $N(\tau_{a},V_{a},\mu_{a})$ containing $p_{j}$. Consider the following
possibilities:

Case a: If the domain and range of $g_{e}$ are disjoint.

Denote by $R_{e}$ the rectangle corresponding to $e$ in the branched
neighbourhood $N(\tau_{a},V_{a},\mu_{a})$. Let $s_{j}$ be the connected
component of $l_{j}|R_{e}$ containing $p_{j}$. Let
$N(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a})$ be obtained by
splitting $N(\tau_{a},V_{a},\mu_{a})$ along $\cup_{j=1}^{\ell}s_{j}$. Then
applying one shifted cycle of the AHT algorithm to
$\mathrm{OCP}(\tau_{a},V_{a},\mu_{a},\mathcal{I}_{a})$ will result in
$\mathrm{OCP}(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a},\mathcal{I}^{\prime}_{a})$
for some $\mathcal{I}^{\prime}_{a}$. More precisely, for each $1\leq j\leq k$,
step (5) replaces $g_{j}$ with $g^{\prime}_{j}:=g_{e}^{-1}\circ g_{j}\circ
g_{e}^{s}$, where $s\in\\{0,1\\}$ is equal to $1$ if and only if
$\text{domain}(g_{j})\subset\text{range}(g_{e})$. Let
$c:=\min_{j=1}^{\ell}p_{j}\in[c_{0},N^{\prime}]=t$. Hence, after step (5) the
points in the interval $[c,N^{\prime}]$ lie in the range of only $g_{e}$, and
$c$ is minimal with this property. Subsequently, step (6) will truncate the
pairing $g_{e}$. After step (6) there are no pairings that are restrictions of
the identity, and so step (1) will have no effect. Finally step (2) will
contract the static interval $[c,N^{\prime}]$.

In this case $(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a})$ is obtained
from $(\tau_{a},V_{a},\mu_{a})$ via $\ell$ splits along the same branch $e$.
Note that $\ell$ is at most twice the number of branches of $\tau$.

######  Remark 4.14.

Note that item (2) in the definition of an initial interval identification is
used here. This was to ensure that $N^{\prime}$ lies on a tie interval above a
vertex $w\notin V_{a}$; otherwise step (2) could have deleted a branch of the
train track adjacent to a base vertex.

Case b: If the domain and range of $g_{e}$ have non-empty intersection.

In this case $w=w^{\prime}$. Let $s_{j}$ be the connected component of
$l_{j}|R_{e}$ containing $p_{j}$. If $l_{j}\neq\\{p_{j}\\}$, then $s_{j}$
starts at $p_{j}$, runs horizontally across $R_{e}$ until it reaches the other
vertical boundary of $R_{e}$, then it possibly enters $R_{e}$ again, and
continues this for a finite number of times until it hits a tie interval in a
point not included in $\text{range}(g_{e})$. Let
$N(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a})$ be obtained by
splitting $N(\tau_{a},V_{a},\mu_{a})$ along $\cup_{j=1}^{\ell}s_{j}$. Then
applying Steps (5)–(6) of the AHT algorithm to
$\mathrm{OCP}(\tau_{a},V_{a},\mu_{a},\mathcal{I}_{a})$ will result in
$\mathrm{OCP}(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a},\mathcal{I}^{\prime}_{a})$
for some $\mathcal{I}^{\prime}_{a}$. Next if we apply Steps (1)–(2), the
entire collection of pairings corresponding to some components of $\tau$ might
be deleted; any such component is necessarily a simple closed curve, because
of item (2) in the definition of an initial interval identification. We add
any such components to the stationary part.

Let $\alpha$ be the simple closed curve that is the image of $e$ in $\tau$.
Then $(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a})$ is obtained from
$(\tau_{a},V_{a},\mu_{a})$ via twirling along $\alpha$, and then possibly
transferring some simple closed curve components to the stationary part. See
Definition 4.6 and Figure 10. This finishes the proof of items (1)–(2).

Now we prove item (3) following the proof of [DW07, Lemma 2.9, part a]. Let
$N$ be the maximum natural number appearing in the orbit counting problem
$\mathrm{OCP}(\tau_{a},V_{a},\mu_{a},\mathcal{I}_{a})$; hence $N$ corresponds
to an endpoint of a tie interval above a vertex $w\notin V_{a}$. There are
exactly two pairings whose domain or range include $N$; let $z\geq\tilde{z}$
be the length of the intervals associated with these pairings; in particular
$z$ is the length of $\text{range}(g_{e})$. Define
$z^{\prime}\geq\tilde{z}^{\prime}$ similarly for
$\mathrm{OCP}(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a},\mathcal{I}^{\prime}_{a})$.
Let $z_{i}$ be the measure of branches of $\tau$. Define $z^{\prime}_{j}$
similarly. Recall that in both Case a and Case b,
$N(\tau^{\prime}_{a},V^{\prime}_{a},\mu^{\prime}_{a})$ is obtained by
splitting $N(\tau_{a},V_{a},\mu_{a})$ along $\cup_{j=1}^{\ell}s_{j}$, and then
possibly transferring some components to the stationary part. Assume that
$p_{\ell}$ is the lowest point between all $p_{j}$ on the tie interval
containing it; i.e. $p_{\ell}$ is the furthest from the end point $N$. There
are two cases to consider:

  1. i)

If $p_{\ell}$ is the minimum of $\text{range}(g_{e})$, then the number of
pairings will be reduced by one as a result of splitting. Hence

$\displaystyle c_{\text{AHT}}^{\text{old}}-c_{\text{AHT}}^{\text{new}}$
$\displaystyle=\big{(}r+\sum_{i=1}^{r}\log(z_{i})-\frac{1}{2}\log(\tilde{z})\big{)}-\big{(}r-1+\sum_{i=1}^{r-1}\log(z^{\prime}_{i})-\frac{1}{2}\log(\tilde{z}^{\prime})\big{)}$
$\displaystyle=1+\log(z)-\frac{1}{2}\log(\tilde{z})+\frac{1}{2}\log(\tilde{z}^{\prime})\geq
1.$

  2. ii)

If $p_{\ell}$ is not the minimum of $\text{range}(g_{e})$, then the number of
pairings will not increase after splitting, and it decreases only if some
simple closed curve component of $\tau$ is transferred to the stationary part.
Moreover, $\tilde{z}^{\prime}$ will be equal to the length of
$\text{range}(g_{e})$ minus a whole positive multiple of the length of
$[p_{\ell},N]$, where $[p_{\ell},N]$ is the closed segment between $p_{\ell}$
and $N$ along the tie interval $I_{w}$. Hence
$z\geq\tilde{z}+\tilde{z}^{\prime}$. We have

$\displaystyle c_{\text{AHT}}^{\text{old}}-c_{\text{AHT}}^{\text{new}}$
$\displaystyle\geq\big{(}r+\sum_{i=1}^{r}\log(z_{i})-\frac{1}{2}\log(\tilde{z})\big{)}-\big{(}r+\sum_{i=1}^{r}\log(z^{\prime}_{i})-\frac{1}{2}\log(\tilde{z}^{\prime})\big{)}$
$\displaystyle=\big{(}r+\log(z)+\sum_{z_{i}\neq
z}\log(z_{i})-\frac{1}{2}\log(\tilde{z})\big{)}-\big{(}r+\sum_{z^{\prime}_{i}\neq\tilde{z}^{\prime}}\log(z^{\prime}_{i})+\frac{1}{2}\log(\tilde{z}^{\prime})\big{)}$
$\displaystyle\geq\log(z)-\frac{1}{2}\log(\tilde{z})-\frac{1}{2}\log(\tilde{z}^{\prime})=\frac{1}{2}\log(\frac{z^{2}}{\tilde{z}\tilde{z}^{\prime}})\geq
1,$

where we used the inequality $(a+b)^{2}\geq 4ab$.

This completes the proof of (3). Since the AHT-complexity is reduced by at
least 1 at each step, the above algorithm terminates in time that is a
polynomial function of $E$ and $\log|\mu|$.

∎

######  Remark 4.15.

The operations of splitting and twirling do not change the 1-complex carried
by a based integrally weighted train track. Hence, if
$(\tau^{\prime},V^{\prime},\mu^{\prime})$ is obtained from $(\tau,V,\mu)$ via
applying a shifted cycle of the AHT algorithm as in Proposition 4.12, then the
carried 1-complexes $\mathcal{CC}(\tau^{\prime},V^{\prime},\mu^{\prime})$ and
$\mathcal{CC}(\tau,V,\mu)$ are equal. Therefore, if $\tau^{\prime}$ has no
vertices besides the base vertices $V$ and no complementary component to
$\mathcal{CC}(\tau,V,\mu)$ is a bigon, then
$\tau^{\prime}=\mathcal{CC}(\tau,V,\mu)$.

The reduction of AHT-complexity in part (3) of Proposition 4.12 allows us to
control the number of shifted cycles needed to completely simplify a based
integrally weighted train track.

######  Lemma 4.16 (Bound on the number of train tracks).

Let $(\tau,V,\mu)$ be as in Proposition 4.12. Assume that no complementary
component to the carried 1-complex $\mathcal{CC}(\tau,V,\mu)$ is a bigon.
Apply shifted cycles of the AHT algorithm repeatedly to obtain a sequence of
based integrally weighted train tracks $(\tau_{i},V,\mu_{i})$ for
$i=1,\cdots,n$ with $(\tau_{1},V,\mu_{1})=(\tau,V,\mu)$ and
$\tau_{n}=\mathcal{CC}(\tau,V,\mu)$. Let $|\mu|$ be the sum of the weights of
all branches of $\tau$, and $E$ be the number of branches of $\tau$. Then the
number $n$ of the train tracks is at most

$1+E+E\log|\mu|.$

###### Proof.

The number $n-1$ is bounded above by the number of shifted cycles of the AHT
algorithm applied to the orbit counting problem
$\mathrm{OCP}(\tau,V,\mu,\mathcal{I})$. Let $c_{i}$ be the AHT-complexity of
$\mathrm{OCP(\tau_{i},V,\mu_{i},\mathcal{I}_{i})}$; see Definition 4.11. By
part 3) of Proposition 4.12 we have $0\leq c_{i+1}\leq c_{i}-1$ for each $i$,
hence the number of shifted cycles is at most the value of $c_{1}$. We have

$c_{1}=r+\sum_{i=1}^{r}\log(z_{i})-\frac{1}{2}\log(\tilde{z})\leq
E+E\log|\mu|.$

∎

##  5\. Upper bound for distance in the pants graph

######  Theorem 1.1.

Let $S$ be a compact connected orientable surface, and $P$ and $P^{\prime}$ be
pants decompositions of $S$. The distance between $P$ and $P^{\prime}$ in the
pants graph is

$O(|\chi(S)|^{2})\hskip 2.84526pt(1+\log(i(P,P^{\prime}))).$

Moreover, there is an algorithm that constructs a (not necessarily geodesic)
path $P=P_{0},P_{1},\cdots,P_{n}=P^{\prime}$ of length
$n=O(|\chi(S)|^{2})\hskip 2.84526pt(1+\log(i(P,P^{\prime})))$ connecting $P$
and $P^{\prime}$ in the pants graph, in time that is a polynomial function of
$|\chi(S)|$ and $\log(i(P,P^{\prime}))$. Here, for the input, $P$ is given as
a union of pairs of pants with gluing instructions, and $P^{\prime}$ is given
in normal form with respect to $P$. For the output, each $P_{i}$ is given as a
union of pairs of pants with gluing instructions together with the pants move
from $P_{i-1}$ to $P_{i}$.

###### Proof.

Step 1: Assume that $P^{\prime}$ is in normal form with respect to $P$. By
squeezing parallel (in $S-P$) arcs of $P^{\prime}$ together, we obtain an
integrally weighted train track $(\tau,\mu)$ with vertices lying on $P$ and
with the carried $1$-complex $\mathcal{CC}(\tau,\mu)$ isotopic to
$P^{\prime}$. Each component of $S-P$ contains at most $3$ branches of $\tau$,
and so the number of branches of $\tau$ is at most $3|\chi(S)|$. Moreover, the
total weight $|\mu|$ of all branches of $\tau$ is equal to $i(P,P^{\prime}).$

Step 2: Pick any initial interval identification $\mathcal{I}$ for
$(\tau,\mu)$, and repeatedly apply shifted cycles of the AHT algorithm to the
orbit counting problem $\mathrm{OCP}(\tau,\mu,\mathcal{I})$. Proposition 4.12
describes the geometric effect of each shifted cycle of the AHT algorithm on
an integrally weighted train track. We apply shifted cycles of the AHT
algorithm until we obtain $P^{\prime}=\mathcal{CC}(\tau,\mu)$. This is
possible since the AHT-complexity is reduced by at least 1 after applying each
shifted cycle; see Proposition 4.12, item (3). Hence, there is a sequence of
integrally weighted train tracks
$(\tau_{1},\mu_{1}),\cdots,(\tau_{n},\mu_{n})$ with the following properties.

  1. (1)

$(\tau_{1},\mu_{1})=(\tau,\mu)$, and $\tau_{n}=P^{\prime}$.

  2. (2)

The underlying 1-complex of each $\tau_{i}$ is a pre-triangulation (Lemma
4.9). Set $k_{i}=\chi(\tau_{i+1})-\chi(\tau_{i})\geq 0$. By Proposition 4.10,
there are orderings $\mathrm{O}_{i}$ on the edges of $\tau_{i}$ such that for
each $i$ the pants decompositions
$\mathrm{\textbf{P}}(\tau_{i},\mathrm{O}_{i})$ and
$\mathrm{\textbf{P}}(\tau_{i+1},\mathrm{O}_{i+1})$ have distance
$O((k_{i}+1)|\chi(S)|)$ in the pants graph. Note that

$\sum_{i=1}^{n-1}k_{i}=\chi(\tau_{n})-\chi(\tau_{1})=O(|\chi(S)|),$

and so if $d(\cdot,\cdot)$ denotes the distance in the pants graph, then

$\sum_{i=1}^{n-1}d(\mathrm{\textbf{P}}(\tau_{i},\mathrm{O}_{i}),\mathrm{\textbf{P}}(\tau_{i+1},\mathrm{O}_{i+1}))=(n-1)O(|\chi(S)|)+O(|\chi(S)|^{2}).$

  3. (3)

By Lemma 4.16, the number $n$ of the train tracks is

$1+O(|\chi(S)|)\log(i(P,P^{\prime})).$

Step 3: Recall that $\tau_{n}$ has no vertices and so
$\mathrm{\textbf{P}}(\tau_{n},\mathrm{O}_{n})=\mathcal{CC}(\tau_{n},\mu_{n})=P^{\prime}$.
Applying the triangle inequality we have the following

$\displaystyle d(P,P^{\prime})\leq
d(P,\mathrm{\textbf{P}}(\tau_{1},\mathrm{O}_{1}))+\sum_{i=1}^{n-1}d(\mathrm{\textbf{P}}(\tau_{i},\mathrm{O}_{i}),\mathrm{\textbf{P}}(\tau_{i+1},\mathrm{O}_{i+1}))$
$\displaystyle\leq
d(P,\mathrm{\textbf{P}}(\tau_{1},\mathrm{O}_{1}))+(n-1)O(|\chi(S)|)+O(|\chi(S)|^{2}).$

Note that by Lemma 3.15, the pants decompositions
$\mathrm{\textbf{P}}(\tau_{1},\mathrm{O}_{1})$ and $P$ have distance
$O(|\chi(S)|^{2})$, since $i(P,\tau_{1})=O(|\chi(S)|)$. This gives the desired
upper bound for $d(P,P^{\prime})$.

We now discuss the algorithmic and computational part of the statement. By
Proposition 4.12, the sequence $(\tau_{i},\mu_{i})$ for $1\leq i\leq n$ can be
constructed in time that is a polynomial function of $|\chi(S)|$ and
$\log(i(P,P^{\prime}))$. By Proposition 4.10, given $\mathrm{O}_{i}$ one can
construct $\mathrm{O}_{i+1}$ together with a sequence of at most
$O((k_{i}+1)|\chi(S)|)$ consecutive transpositions taking $\mathrm{O}_{i}$ to
$\mathrm{O}_{i+1}$, in time that is a polynomial function of $|\chi(S)|$. For
each pair $(\tau_{i},\mathrm{O}_{i})$, the pants decomposition
$\mathrm{\textbf{P}}(\tau_{i},\mathrm{O}_{i})$ can be constructed in time that
is polynomial in $|\chi(S)|$. Moreover, given two pairs
$(\tau_{i},\mathrm{O}_{i})$ and $(\tau_{i+1},\mathrm{O}_{i+1})$, one can
construct a sequence of pants moves of length $O((k_{i}+1)|\chi(S)|)$ taking
$\mathrm{\textbf{P}}(\tau_{i},\mathrm{O}_{i})$ to
$\mathrm{\textbf{P}}(\tau_{i+1},\mathrm{O}_{i+1})$, in time that is polynomial
in $|\chi(S)|$. This completes the proof of the algorithmic part of the
statement.

∎

##  6\. Polygonal decompositions

In this section, we prove Theorem 6.2, which will be used to relate two
polygonal decompositions of a surface.

######  Definition 6.1.

Let $S$ be a compact surface, and let $\mathcal{T}$ be a polygonal
decomposition that is disjoint from $\partial S$. Let $e$ be an arc embedded
in the interior of $S$ with both endpoints being vertices of $\mathcal{T}$.
Then the polygonal decomposition $\mathcal{T}\cup e$ is obtained from
$\mathcal{T}$ by _adding the diagonal_ $e$. We say that $\mathcal{T}$ is
obtained from $\mathcal{T}\cup e$ by _deleting the diagonal $e$_.

######  Theorem 6.2.

Let $S$ be a compact orientable surface, and $\mathcal{T}$ and
$\mathcal{T}^{\prime}$ be polygonal decompositions of $S$ disjoint from
$\partial S$ with at most $E$ edges. There is a sequence
$\mathcal{T}=\mathcal{T}_{0},\mathcal{T}_{1},\cdots,\mathcal{T}_{n}=\mathcal{T}^{\prime}$
of polygonal decompositions of $S$ such that:

  1. (1)

Each $\mathcal{T}_{i+1}$ is obtained from $\mathcal{T}_{i}$ by contracting or
expanding an embedded edge, or adding or deleting a diagonal, or a power of a
Dehn twist. When $\mathcal{T}_{i+1}$ is obtained from $\mathcal{T}_{i}$ by
Dehn twisting $k$ times about a curve $\alpha$, then $\alpha$ is the closure
of an edge (necessarily with the same endpoints) of $\mathcal{T}_{i}$, and the
absolute value of $k$ is bounded above by
$i(\mathcal{T},\mathcal{T}^{\prime})$.

  2. (2)

Each $\mathcal{T}_{i}$ is disjoint from $\partial S$.

  3. (3)

The number of vertices of each $\mathcal{T}_{i}$ is $O(E)$.

  4. (4)

The number $n$ of steps in this sequence is
$O(E^{2}\log(i(\mathcal{T},\mathcal{T}^{\prime}))+E^{2})$.

Moreover, there is an algorithm that constructs the sequence
$\mathcal{T}_{1},\cdots,\mathcal{T}_{n}$ in time that is a polynomial function
of $\log(i(\mathcal{T},\mathcal{T}^{\prime}))$ and $E$. For the input,
$\mathcal{T}$ is given as a union of polygonal discs and annuli with gluing
instructions, and $\mathcal{T}^{\prime}$ is given by its normal coordinates
with respect to $\mathcal{T}$. For the output, each $\mathcal{T}_{i}$ is given
as a union of polygonal discs and annuli with gluing instructions together
with the move from $\mathcal{T}_{i}$ to $\mathcal{T}_{i+1}$.

######  Remark 6.3.

Note that contracting or expanding edges and Dehn twists are not enough to go
between two arbitrary polygonal decompositions of $S$, since they preserve the
number of complementary regions. Similarly, adding or deleting diagonals and
Dehn twists preserve the number of vertices.

######  Lemma 6.4.

Let $\mathcal{T}$ and $\mathcal{T}^{\prime}$ be polygonal decompositions of a
compact surface $S$ that are disjoint from $\partial S$. Let
$|\mathcal{T}\cup\mathcal{T}^{\prime}|$ be the number of edges of the
polygonal decomposition $\mathcal{T}\cup\mathcal{T}^{\prime}$ obtained by
superimposing $\mathcal{T}$ and $\mathcal{T}^{\prime}$. Then $\mathcal{T}$ can
be transformed into $\mathcal{T}^{\prime}$ using
$O(|\mathcal{T}\cup\mathcal{T}^{\prime}|)$ contracting or expanding embedded
edges, and $O(|\mathcal{T}\cup\mathcal{T}^{\prime}|)$ adding or deleting
diagonals.

Moreover, there is an algorithm that produces such sequence of moves in time
that is polynomial in $|\mathcal{T}\cup\mathcal{T}^{\prime}|$. Here
$\mathcal{T}$ is given as a union of polygonal discs and annuli with gluing
instructions, and $\mathcal{T}^{\prime}$ is given in normal form with respect
to $\mathcal{T}$. The output gives a sequence of polygonal decompositions
(described as a union of polygonal discs and annuli with gluing instructions)
interpolating between $\mathcal{T}$ and $\mathcal{T}^{\prime}$ together with
the moves between consecutive polygonal decompositions.

###### Proof.

It is enough to show that $\mathcal{T}\cup\mathcal{T}^{\prime}$ can be
transformed into each of $\mathcal{T}$ and $\mathcal{T}^{\prime}$ using
$O(|\mathcal{T}\cup\mathcal{T}^{\prime}|)$ such moves. For any complementary
region $R$ of $\mathcal{T}$, remove all edges of
$\mathcal{T}\cup\mathcal{T}^{\prime}$ that lie in the interior of $R$ by
contracting embedded edges and deleting diagonals. Then remove any remaining
extra vertices of $\mathcal{T}\cup\mathcal{T}^{\prime}$ that lie on
$\mathcal{T}$ by contracting embedded edges. It is easy to see that this can
be done in polynomial time as a function of
$|\mathcal{T}\cup\mathcal{T}^{\prime}|$. ∎

###### Proof of Theorem 6.2.

Let $V$ be the set of vertices of $\mathcal{T}^{\prime}$. First we construct a
based integrally weighted train track $(\tau,V,\mu)$ such that the carried
1-complex $\mathcal{CC}(\tau,V,\mu)$ is equal to $\mathcal{T}^{\prime}$. To do
this, for each edge of $\mathcal{T}$ squeeze together all points of
intersection with $\mathcal{T}^{\prime}$ to a single switch of $\tau$, and
then for each set of parallel normal arcs of $\mathcal{T}^{\prime}$ squeeze
them together to a single edge of $\tau$; this gives the based integrally
weighted train track $(\tau,V,\mu)$. Apply shifted cycles of the AHT algorithm
to unwind $(\tau,V,\mu)$ to $\mathcal{T}^{\prime}$. By Proposition 4.12 we
obtain a sequence of based integrally weighted train tracks
$(\tau_{i},V,\mu_{i})$ for $1\leq i\leq n$ such that

  1. (1)

$(\tau_{1},V,\mu_{1})=(\tau,V,\mu)$, and
$(\tau_{n},V,\mu_{n})=(\mathcal{T}^{\prime},V,\textbf{1})$ where 1 denotes the
weight assigning $1$ to every branch.

  2. (2)

Each $(\tau_{i+1},V,\mu_{i+1})$ is obtained from $(\tau_{i},V,\mu_{i})$ by
either splits along the same oriented branch, or by a twirling.

  3. (3)

The number $n$ is $O(E\log(i(\mathcal{T},\mathcal{T}^{\prime}))+E)$. This
follows from Lemma 4.16 and the following two observations:

    1. -

$|\mu|$ is at most $i(\mathcal{T},\mathcal{T}^{\prime})+|E|$.

    2. -

The number of edges of $\mathcal{T}$ is at most $E$, and so the number of
branches of the based train track $(\tau,V)$ is $O(E)$ as well.

Lemma 4.16 then implies that $n$ is at most
$O(E)+O(E)\log(i(\mathcal{T},\mathcal{T}^{\prime})+|E|)$. When
$i(\mathcal{T},\mathcal{T}^{\prime})\geq|E|$, then
$i(\mathcal{T},\mathcal{T}^{\prime})+|E|\leq
2i(\mathcal{T},\mathcal{T}^{\prime})$, and so the upper bound on $n$ becomes
$O(E\log(i(\mathcal{T},\mathcal{T}^{\prime}))+E)$, as required. On the other
hand, when $i(\mathcal{T},\mathcal{T}^{\prime})<|E|$, Lemma 6.4 implies that
we can find a sequence of polygonal decompositions with length $O(E)$, which
is at most the required bound.

  4. (4)

The sequence $(\tau_{i},V,\mu_{i})$ for $1\leq i\leq n$ can be constructed in
time that is a polynomial function of
$\log(i(\mathcal{T},\mathcal{T}^{\prime}))$ and $E$.

By Lemma 6.4, there is a sequence of $O(E)$ addition or deletion of diagonals
that takes $\tau_{1}$ to $\mathcal{T}$ and this sequence can be constructed in
time that is polynomial in $E$. This is because $i(\mathcal{T},\tau_{1})$ is
$O(E)$ and so superimposing $\tau_{1}$ and $\mathcal{T}$ will produce a
1-complex with $O(E)$ edges.

Additionally, each $\tau_{i+1}$ is obtained from $\tau_{i}$ by $O(E)$
contractions or expansions of embedded edges, $O(E)$ addition or deletion of
diagonals, and at most one twist map. This again follows from Lemma 6.4 since
if $\tau_{i+1}$ is obtained from $\tau_{i}$ by splits along the same oriented
branch, then after a suitable isotopy the 1-complex $\tau_{i}\cup\tau_{i+1}$
obtained by superimposing them has $O(E)$ edges. In this case, by Lemma 6.4
such a sequence of moves from $\tau_{i}$ to $\tau_{i+1}$ can be constructed in
time that is polynomial in $E$. When $\tau_{i+1}$ is obtained from $\tau_{i}$
by a twist map, then the curve that we twist about and the power of the Dehn
twist are already given to us by Proposition 4.12.

Combining the sequence of moves

$\mathcal{T}\rightarrow\tau_{1}\rightarrow\tau_{2}\rightarrow\cdots\rightarrow\tau_{n}=\mathcal{T}^{\prime}$

gives the desired sequence of polygonal decompositions from $\mathcal{T}$ to
$\mathcal{T}^{\prime}$ of length

$n=O(E^{2}\log(i(\mathcal{T},\mathcal{T}^{\prime}))+E^{2}).$

∎

We now consider an alternative version of Theorem 6.2 for the following
important type of polygonal decomposition.

######  Definition 6.5.

A _spine_ for a closed surface $S$ is an embedded 1-complex $\Gamma\subset S$
such that the surface $S\setminus\setminus\Gamma$ obtained by cutting $S$
along $\Gamma$ is a disc. A _spine_ for a compact surface $S$ with non-empty
boundary is a 1-complex $\Gamma$ embedded in the interior of $S$ such that the
surface $S\setminus\setminus\Gamma$ is a regular neighbourhood of $\partial
S$.

The following is one natural way of modifying spines.

######  Definition 6.6 (Edge swap [LP19]).

Let $\Gamma$ be a spine for a compact surface $S$. Let $e^{\prime}$ be an arc
properly embedded in $S\setminus\setminus\Gamma$ with endpoints on $\Gamma$.
Let $e$ be an edge of the graph $\Gamma\cup e^{\prime}$ that has distinct
components of $S\setminus\setminus(\Gamma\cup e^{\prime})$ on either side of
it, at least one of which is a disc. Then the result of removing $e$ from
$\Gamma$ and adding $e^{\prime}$ is a new spine $\Gamma^{\prime}$ for $S$. We
say that $\Gamma$ and $\Gamma^{\prime}$ are related by an _edge swap_. See
Figure 12.

$e^{\prime}$ at 58 50 $e$ at 3 38 $e$ at 108 50

Figure 12. An edge swap on a spine $\Gamma$ of $S$. Here the polygon
represents $S\setminus\setminus\Gamma$.

######  Theorem 6.7.

Let $S$ be a compact orientable surface, and let $\Gamma$ and
$\Gamma^{\prime}$ be spines of $S$. There is a sequence
$\Gamma=\Gamma_{0},\Gamma_{1},\cdots,\Gamma_{n}=\Gamma^{\prime}$ of spines for
$S$ such that:

  1. (1)

Each $\Gamma_{i+1}$ is obtained from $\Gamma_{i}$ by an edge swap, an
expansion or contraction of an embedded edge, or a power of a Dehn twist. When
$\Gamma_{i+1}$ is obtained from $\Gamma_{i}$ by Dehn twisting $k$ times about
a curve $\alpha$, then $\alpha\cap\Gamma_{i}$ is a vertex of $\Gamma_{i}$, and
the absolute value of $k$ is bounded above by $i(\Gamma,\Gamma^{\prime})$.

  2. (2)

The number $n$ of steps in this sequence is
$O(\chi(S)^{2}\log(i(\Gamma,\Gamma^{\prime}))+\chi(S)^{2})$.

Moreover, there is an algorithm that constructs the sequence
$\Gamma_{0},\cdots,\Gamma_{n}$ in time that is a polynomial function of
$\log(i(\Gamma,\Gamma^{\prime}))$ and $\chi(S)$. For the input, $\Gamma$ is
given as a polygon or a collection of annuli with gluing instructions, and
$\Gamma^{\prime}$ is given by its normal coordinates with respect to $\Gamma$.
For the output, each $\Gamma_{i}$ is given as a polygon or annuli with gluing
instructions together with the move from $\Gamma_{i}$ to $\Gamma_{i+1}$.

###### Proof.

By Theorem 6.2, there is a sequence of polygonal decompositions

$\Gamma=\mathcal{P}_{0},\mathcal{P}_{1},\cdots,\mathcal{P}_{m}=\Gamma^{\prime}$

such that:

  1. (1)

Each $\mathcal{P}_{i+1}$ is obtained from $\mathcal{P}_{i}$ by contracting or
expanding an embedded edge, adding or deleting a diagonal, or a power of a
Dehn twist. When $\mathcal{P}_{i+1}$ is obtained from $\mathcal{P}_{i}$ by
Dehn twisting $k$ times about a curve $\alpha$, then $\alpha$ is the closure
of an edge of $\mathcal{P}_{i}$, and the absolute value of $k$ is bounded
above by $i(\Gamma,\Gamma^{\prime})$.

  2. (2)

Each $\mathcal{P}_{i}$ is disjoint from $\partial S$.

  3. (3)

The number of vertices of each $\mathcal{P}_{i}$ is $O(|\chi(S)|)$.

  4. (4)

$m=O(\chi(S)^{2}\log(i(\Gamma,\Gamma^{\prime}))+\chi(S)^{2}).$

  5. (5)

There is an algorithm that constructs the sequence
$\mathcal{P}_{1},\cdots,\mathcal{P}_{m}$ together with the moves from
$\mathcal{P}_{i}$ to $\mathcal{P}_{i+1}$, in time that is a polynomial
function of $\log(i(\Gamma,\Gamma^{\prime}))$ and $\chi(S)$.

For each polygonal decomposition $\mathcal{P}_{i}$, we will pick a collection
of edges $X_{i}$ in $\mathcal{P}_{i}$ so that $\mathcal{P}_{i}\setminus X_{i}$
is a spine $\Gamma_{i}$. Initially we will assume that $S$ is closed.

We will construct $X_{i}$ recursively. Initially, $X_{0}=\emptyset$. To define
$X_{i+1}$ from $X_{i}$, we consider various cases:

  1. (i)

If $\mathcal{P}_{i}\rightarrow\mathcal{P}_{i+1}$ is the insertion of a
diagonal $e$, we define $X_{i+1}$ to be $X_{i}\cup\\{e\\}$. So
$\Gamma_{i+1}=\Gamma_{i}$.

  2. (ii)

Suppose that $\mathcal{P}_{i}\rightarrow\mathcal{P}_{i+1}$ is the removal of a
diagonal $e$. If $e$ is in $X_{i}$, then set $X_{i+1}$ to be
$X_{i}\setminus\\{e\\}$. Then $\Gamma_{i}=\mathcal{P}_{i}\setminus
X_{i}=\mathcal{P}_{i+1}\setminus X_{i+1}=\Gamma_{i+1}$. So we consider when
$e$ does not lie $X_{i}$. Since we are assuming that $S$ is closed,
$S\setminus\Gamma_{i}$ is a single disc, and so there is an arc in this disc
region joining the two sides of $e$. However, in $S\setminus\mathcal{P}_{i}$,
the two sides of $e$ lie in distinct disc regions. So there is an arc $\alpha$
in $X_{i}$, consisting of a union of edges, that separates the two sides of
$e$. Let $X_{i+1}$ equal $X_{i}$ minus the edges in $\alpha$. Then
$\Gamma_{i+1}$ is obtained from $\Gamma_{i}$ by removing $e$ and adding this
arc $\alpha$. In other words, $\Gamma_{i+1}$ is obtained from $\Gamma_{i}$ by
performing an edge swap.

  3. (iii)

If $\mathcal{P}_{i}\rightarrow\mathcal{P}_{i+1}$ is the expansion of an edge
$e$, we set $X_{i+1}$ to be $X_{i}$, unless this creates a 1-valent vertex of
$\Gamma_{i+1}$, in which case we set $X_{i+1}=X_{i}\cup\\{e\\}$. So,
$\Gamma_{i+1}$ is obtained from $\Gamma_{i}$ by expanding the edge $e$, or is
a copy of $\Gamma_{i}$.

  4. (iv)

Suppose that $\mathcal{P}_{i}\rightarrow\mathcal{P}_{i+1}$ is the contraction
of an embedded edge $e$. If $e$ is not in $X_{i}$, then we set $X_{i+1}=X_{i}$
and we note $\Gamma_{i+1}$ is obtained from $\Gamma_{i}$ by contracting $e$.
So suppose that $e$ is in $X_{i}$. If we were to add $e$ to $\Gamma_{i}$, the
complementary disc $S\setminus\Gamma_{i}$ would be divided into two discs, $A$