3.1 Adjacency matrices

Let G be a finite directed graph and $\operatorname{Vert}(G)\kern1.2pt{=}\kern1.2pt\{v_1, v_2,\ldots ,v_n\}\kern-0.5pt$ . The adjacency matrix A of G is defined by

$$ \begin{align*} A_{ij}=\textrm{the number of edges from } v_i\textrm{ to }v_j, \end{align*} $$

where the $A_{ij}$ is the entry of the ith row and jth column of A. The adjacency matrix depends on the choice of indices of $v_i$ , and matrices defined by different choices of indices differ by conjugations by permutation matrices. In particular, if the index satisfies $i<j$ only when there exists a path from $v_i$ to $v_j$ , then the adjacency matrix is an upper triangular block matrix.

(UTB-form) $$ \begin{align} A= \left( \begin{array}{ccccc} A_1 & * & \dots & * & *\\ 0 & A_2 & \dots & * & *\\ \vdots & \vdots & \ddots& \vdots & \vdots\\ 0& 0 & \dots & A_{k-1} & *\\ 0& 0 & \dots & 0 & A_k \end{array} \right), \end{align} $$

where $A_i$ is irreducible or a $0$ matrix. A non-negative $m \times m$ square matrix M is irreducible if for every $1 \le i,j \le m$ , there exists $k\ge 1$ such that $(M^k)_{ij}>0$ . An irreducible non-negative matrix M has a simple eigenvalue, called the Perron–Frobenius eigenvalue, which is a positive real number and equal to the spectral radius of M. The spectral radius of A is equal to the maximum of Perron–Frobenius eigenvalues of the irreducible $A_i$ . See [Reference Berman and PlemmonsBP94, Ch. 2].

3.1.1 Asymptotic growth of entries of $A^n$

Let B be a non-negative irreducible matrix and denote by v and $w^T$ the right and the left eigenvectors of B which are normalized by $w^T v=1$ . By the Perron–Frobenius theorem, for the Perron–Frobenius eigenvalue $\rho $ of B, we have

$$ \begin{align*} \lim_{n\to \infty} B^n/\rho^n=v w^T. \end{align*} $$

Hence, the $(i,j)$ entry of $B^n$ is asymptotic to $\rho ^n\cdot v_i \cdot w_j$ . This implies the following proposition. The proof is left to the reader.

Proposition 3.4. Let A be an $N\times N$ non-negative upper triangular block matrix such that $A_1,\ldots A_k$ are blocks on the diagonal like equation (UTB-form). Let $A_i$ be an $N_i \times N_i$ matrix so that $N=\sum _{i=1}^k N_i$ . For $i\in \{1,\ldots ,N\}$ , let $l_i \in [1,k]_{\mathbb {Z}}$ such that $A_{l_i}$ contains the $(i,i)$ -entry of A. Let $R_{n,i}$ (respectively $C_{n,i}$ ) be the ith row (respectively column) sum of $A^n$ , that is, the sum of the entries in the ith row (respectively column) of $A^n$ . Then

$$ \begin{align*} \begin{cases} \lim_{n\to \infty} \dfrac{1}{n} \cdot \log (R_{n,i})=\max_{l_i \le j \le k} \log \rho_j,\\[4pt] \lim_{n\to \infty} \dfrac{1}{n} \cdot \log (C_{n,i})=\max_{1 \le j \le l_i} \log \rho_j, \end{cases} \end{align*} $$

where $\rho _j$ is the spectral radius of $A_j$ .

3.2 The growth rate of the number of paths

3.2.1 Polynomial and exponential growth rate

Suppose we have a sequence $\{a_n~|~a_n \in \mathbb {R}_{> 0},~n\ge 1\}$ . We consider sequences which are uniformly bounded or diverge to infinity when n tends to infinity. We say that the sequence has exponential growth, or grows exponentially fast, if there exists $C>D>1$ such that for any sufficiently large $n>0$ , we have

$$ \begin{align*} D<{|}\!\log a_n|<C, \end{align*} $$

and the sequence has polynomial growth of degree d, or grows polynomially fast with degree d, for a non-negative integer d if there exists $C>D>0$ such that for any sufficiently large $n>0$ , we have

$$ \begin{align*} D\cdot n^d < a_n < C \cdot n^d. \end{align*} $$

Lemma 3.5. Suppose $\{a_n~|~n\ge 1,~a_n\ge 0 \}$ is a non-decreasing sequence. If there exist $k,l,m>0$ such that $a_{k\cdot n+l}\ge m \cdot n^d$ (respectively $a_{k\cdot n+l}\le m \cdot n^d$ ) for every $n>0$ , then there exists $C>0$ such that $a_n>C\cdot n^d$ (respectively $a_n<C\cdot n^d$ ) for any sufficiently large n.

Proof. Since the sequence $\{a_n\}$ is non-decreasing, we have $a_{(k+1)\cdot n}\ge m \cdot n^d$ for any $n>l/k$ . Then, for any sufficiently large $n>0$ , we have

$$ \begin{align*} a_n \ge a_{(k+1)\cdot\lfloor {n}/({k+1}) \rfloor}\ge m\cdot {\bigg\lfloor\frac{n}{k+1}\bigg\rfloor}^d>\frac{m}{(k+2)^d} \cdot n^d, \end{align*} $$

where $\lfloor x \rfloor $ means the largest integer less than or equal to x. The same argument also works for the inverse direction.

Let G be a directed graph. Two paths in G are different if their sequences of edges are different. Let $P(v,n)$ be the number of different paths of length exactly n starting from v. The following criterion on the growth rate of $P(v,n)$ is well known. See [Reference SidkiSid00, Reference UfnarovskiĭUfn82]. We restate the criterion with a slight improvement for the case of polynomial growth.

Theorem 3.6. Let G be a directed graph and $v \in \operatorname{Vert}(G)$ .

1. (1) If there exist two different cycles passing through v, then $P(v,n)$ has exponential growth.

2. (2) If there exists $w\in \operatorname{Vert}(G)$ such that there are two different cycles starting from w and a path from v to w, then $P(v,n)$ has exponential growth.

3. (3) If v does not satisfy item (1) or (2), then $P(v,n)$ has polynomial growth. Moreover, if the maximum number of (disjoint) cycles that a path from v can intersect is $d+1$ , then the degree of the polynomial growth of $P(v,n)$ is d. When the maximum number of cycles is zero, then $P(v,n)=0$ for every sufficiently large n and we define the degree of polynomial growth to be $-1$ .

Proof. The number of paths of length $\le n$ is counted in [Reference UfnarovskiĭUfn82] and we slightly modify it. If two cycles of lengths p and q pass through v, then there are at least $2^n$ paths of length $npq$ starting from v. Let M be the maximal number of outgoing edges from one vertex in G. Then the number of paths with length n is less than $M^n$ . This proves items (1) and (2) is immediate from item $(1)$ .

Assume that v does not satisfy item (1) or (2). Let $W=\langle v\rangle $ be the ideal generated by v. There exist totally ordered finite subsets $W_1,\ldots W_k$ such that $v \in W_i$ for each i and $W=\bigcup _{i=1}^k W_i$ . More precisely, we think of a directed graph H obtained by collapsing each cycle in G to a vertex. Since v does not satisfy item (1) or (2), the graph H does not have any cycle. Let $v'$ be the vertex of H corresponding to v. Then $v'$ is the only minimal element of $\operatorname{Vert}(H)$ . Let $w_1,w_2,\ldots ,w_m$ be the maximal elements of $\operatorname{Vert}(H)$ . Choose any $w\in \operatorname{Vert}(W)$ .

Then the subgraph $G_i$ generated by $W_i$ is isomorphic to the graph in Figure 4. Since every path from v is supported in some $G_i$ , it suffices to show item $(3)$ when G is the graph of the type shown in Figure 4.

Figure 4 A graph with polynomial growth rate of $P(v,n)$ . Any arrow indicates paths, any dotted arrow means it may not exist but if exists it indicates a path, and any circle indicates a cycle. In each cycle, the incoming vertex and the outgoing vertex could be the same.

Assume G is a graph of the type in Figure 4. Let it have $d+1$ cycles of lengths $p_1,p_2,\ldots , p_{d+1}$ . Let $p_M$ and $p_m$ be the maximum and minimum of $\{p_1,\ldots , p_d\}$ , and K and L be the number of vertices and edges of G, respectively. Let $X(n)$ be the set of d-tuples $(n_1,\ldots ,n_d)$ of non-negative integers satisfying $n_1 + \cdots +n_d \le n$ . The set $X(n)$ has $\binom {n+d}{d}$ elements.

Claim. For any $n\ge 1$ , $P(v,p_m\cdot n)/K \le \binom {n+d}{d} \le P(v,p_M \cdot n +L)$ .

Proof of claim

For any n, we define an injective map from $X(n)$ to the set of paths from v of length $p_M\cdot n+L$ as follows. For any $(n_1,\ldots ,n_d)\in X(n)$ , we have a path from v which goes around the ith cycle $n_i$ times for $i \le d$ . The path has length not greater than $p_M\cdot n + L$ . There is a unique extension of the path which: (1) does not further go around the first d cycles, that is, the additional rotations occur only in the last cycle and (2) has length exactly equal to $p_M\cdot n + L$ . We assign the extended path to the element $(n_1,\ldots ,n_d)\in X(n)$ . Hence, we have $\binom {n+d}{d} \le P(v,p_M\cdot n+L)$ .

Similarly, we define another map from the set of paths of length $p_m\cdot n$ to $X(n)$ by assigning the numbers of times that each path goes around the first d cycles. Suppose that two such paths $p_1$ and $p_2$ have the same image in $X(n)$ . Since $p_1$ and $p_2$ start from the same vertex v and have the same length, their terminal vertex are the same if and only if $p_1$ and $p_2$ are the same. It follows that the number of preimages of the map is less than K.

As $\binom {n+d}{d}$ is a degree d polynomial in n, it follows from Lemma 3.5 that the $P(v,n)$ has polynomial growth of degree d as a sequence in n.

The polynomial growth rate of $P(v,n)$ implies the recurrent extension is unique.

Proposition 3.7. (Extension of recurrent paths)

Let G be a directed graph and $v\in \operatorname{Vert}(G)$ . Let $\gamma $ be a path from v of length $m>0$ . If $\gamma $ is recurrent, then for any $n>m$ , $\gamma $ has at least one extension to a recurrent path of length n. Moreover, if $P(v,n)$ grows polynomially fast as n tends to $\infty $ , then the extension is unique.

Proof. Since $\gamma $ is recurrent, the initial and the terminal points of $\gamma $ belong to one cycle C of G. Then we can extend $\gamma $ by repeatedly traveling along C. If $P(v,n)$ grows polynomially fast, then C is the only cycle that passes through v. Hence, traveling along C is the only way to extend $\gamma $ .

3.3 Graph maps with zero topological entropy

Let G be a finite graph and $\operatorname{Vert}(G)$ be its vertex set. A continuous map $f:G \to G$ is Markov if $f(\operatorname{Vert}(G)) \subset \operatorname{Vert}(G)$ and f is a homeomorphism or constant on each component of $G \setminus f^{-1}(\operatorname{Vert}(G))$ . Then the edges form a Markov partition of f. Denote by $e_1,e_2,\ldots $ the edges of G. Note that every edge is mapped to a union of edges. The adjacency matrix $A_f$ of $f:G \to G$ is defined in such a way that $f(e_i)$ covers $e_j$ as many as the $(i,\,j)$ entry of $A_f$ . Under a suitable choice of indexing $e_i$ terms, we may assume that $A_f$ is an upper triangular block matrix. Let $A_1,\ldots A_k$ be the block matrices on the diagonal as in equation (UTB-form).

The spectral radius $\unicode{x3bb} $ of $A_f$ is either equal to zero if every $A_i$ is zero or equal to the maximum of Perron–Frobenius eigenvalues of the irreducible $A_i$ terms. The topological entropy $h_{\textrm {top}}(f)$ of f is equal to zero if $\unicode{x3bb} =0$ or equal to $\log (\unicode{x3bb} )$ if $\unicode{x3bb}>0$ . The relationship between the topological entropy and the Perron–Frobenius eigenvalue follows from [Reference Misiurewicz and SzlenkMS80].

There is a directed graph $\mathcal {D}_f$ such that $\operatorname{Vert}(\mathcal {D}_f) = \operatorname {\textrm {Edge}}(G)$ and the directed edges are defined as follows: for $e_i,e_j\in \operatorname {\textrm {Edge}}(G)$ , if $f(e_i)$ covers $e_j$ exactly k times, then we draw k directed edges of $\mathcal {D}_f$ from $e_i$ to $e_j$ . Then $A_f$ is equal to the adjacency matrix of $\mathcal {D}_f$ . We refer to $\mathcal {D}_f$ as the directed graph of the Markov map $f:G\to G$ .

The following lemma is elementary, but we prove it for the sake of self-containedness.

4.1 Notation

As we wrote in the previous paragraph, we use bold fonts for the domains of characteristic maps and normal fonts for the corresponding closed cells in the CW-complexes. For example, for a closed $2$ -cell t in a CW-complex X, we write $\phi _t:\textbf {t}\to t$ for the characteristic map. Thus, $\textbf {t}$ is always homeomorphic to the closed $2$ -disk, but t may not be.

4.2 Subdivision maps as post-critically finite branched coverings

Throughout this article, we assume $S_{\mathcal {R}}$ is homeomorphic to the $2$ -sphere $S^2$ . Considering $\mathcal {R}(S_{\mathcal {R}})$ and $S_{\mathcal {R}}$ as different complexes on the same underlying $2$ -sphere, we may think of the subdivision map $f:\mathcal {R}(S_{\mathcal {R}}) \rightarrow S_{\mathcal {R}}$ as a topological branched self-covering of $S^2$ . Since the set of critical points $\Omega _f$ is a subset of the set of vertices of $\mathcal {R}(S_{\mathcal {R}})$ , f is post-critically finite.

A set of marked points A of $\mathcal {R}$ is a subset of $\operatorname{Vert}(S_{\mathcal {R}})$ with $P_f \cup f(A) \subset A$ . With a choice of a set of marked points A, the subdivision map can be considered as a marked post-critically finite branched covering .

4.3 Branched coverings represented as subdivision maps

If f is a subdivision map, then the $1$ -skeleton $S_{\mathcal {R}}^{(1)}$ is a graph such that: (1) it contains $P_f$ ; (2) it is connected; and (3) it is forward invariant under f. Conversely, if there is a graph satisfying the three conditions, then it defines a finite subdivision rule. Below is a list of some forward invariant graphs that are known to exist.

• • Spiders of polynomials [Reference Hubbard, Schleicher, Branner, Keen, Douady, Blanchard, Hubbard, Schleicher and DevaneyHS94].

• • Hubbard trees that can be augmented to be invariant trees [Reference Shepelevtseva and TimorinST19].

• • Jordan curves [Reference Bonk and MeyerBM17] and trees [Reference HlushchankaHlu17] of expanding Thurston maps.

• • Tischler graphs of critically fixed rational maps [Reference HlushchankaHlu19, Reference Pilgrim and TanPT98].

• • Jordan curves [Reference Gao, Haïssinsky, Meyer and ZengGHMZ18] and trees [Reference HlushchankaHlu17] of Sierpiński Carpet rational maps.

• • Extended Newton graphs for post-critically finite Newton maps [Reference Lodge, Mikulich and SchleicherLMS21].

• • A sufficiently large iterate $f^n$ of any post-critically finite branched covering f without a Levy cycle is homotopic to a subdivision map [Reference Floyd, Parry and PilgrimFPP20]. Its 1-skeleton is invariant up to homotopy.

There are post-critically finite branched coverings whose any iterates cannot be represented as subdivision maps [Reference Floyd, Parry and PilgrimFPP20, §4].

4.4 Combinatorial properties of $\mathcal {R}$ and Levy and Thurston obstructions

A finite subdivision rule $\mathcal {R}$ is edge separating if for every tile type $\textbf {t}$ and pair of disjoint closed edges e and $e'$ of $\textbf {t}$ , there exists a positive integer n such that no subtile of $\textbf {t}$ in $\mathcal {R}^n(\textbf {t})$ contains both a subedge of e and a subedge of $e'$ . Similarly, $\mathcal {R}$ is vertex separating if for every tile type $\textbf {t}$ and pair of vertices v and w of $\textbf {t}$ , there exists a positive integer n such that no subtile of $\textbf {t}$ in $\mathcal {R}^n(\textbf {t})$ contains both v and w. These two separating conditions are a part of the sufficient condition for a subdivision map not having a Levy cycle or a Thurston obstruction.

• • If $\mathcal {R}$ is vertex separating and edge separating, then f does not have a Levy cycle [Reference Floyd, Parry and PilgrimFPP18b, Proposition 5.1]. There is a finite subdivision rule which is neither edge separating nor vertex separating but does not have a Levy cycle, see Example 4.2.

• • If $\mathcal {R}$ is vertex separating, edge separating, and conformal (we do not define this conformality in the article), then f does not have a Thurston obstruction [Reference Cannon, Floyd, Kenyon and ParryCFKP03]. There is an example [Reference Cannon, Floyd, Kenyon and ParryCFKP03, Example 4.6] of finite subdivision rule which is not conformal but does not have a Thurston obstruction, thus it is combinatorially equivalent to a rational map. See [Reference Cannon, Floyd, Kenyon and ParryCFKP03] for a definition of conformal finite subdivision rules.

Example 4.2. The finite subdivision rule R given in Figure 5 is [Reference Floyd, Parry and PilgrimFPP18b, Example 5.3]. Its CW-complex $\mathcal {S}_{\mathcal {R}}$ of the $2$ -sphere consists of two square tiles. The edges of white and shaded tiles are glued to form a pillowcase. Since the shaded tile does not subdivide, $\mathcal {R}$ is neither edge separating nor vertex separating. However, it easily follows from Theorem 6.21 that the subdivision map does not have a Levy cycle.

Figure 5 An example of expanding finite subdivision rule which is neither edge separating nor vertex separating.

4.5 Edges, bands, bones, and curves of subdivision complexes

For $n\ge 0$ , a level- n tile, edge, or band of $\mathcal {R}$ is a tile, edge, or band of $\mathcal {R}^n(S_{\mathcal {R}})$ . See Definition 2.1 for definitions of bands and their bones. There is a bijection between level- $0$ tiles (respectively edge) and tile types (respectively edge types); a level- $0$ tile t is the image of the tile type $\textbf {t}$ under the characteristic map $\phi _t:\textbf {t}\to t$ .

We will use superscripts to indicate the level of tiles, edges, etc. Since frequently considering level- $0$ objects, we sometimes omit the superscript $^0$ for simplicity.

For $n>m$ , a level-n tile $t^n$ is a subtile of a level-m tile $t^m$ if $t^{n} \subset t^{m}$ . Let $\textbf {t}$ be a tile type and t be the corresponding level- $0$ tile. A level-n tile $t^n$ is of type $\textbf {t}$ if $f^n(t^n)=t$ . Subedges and their types are similarly defined. A band type is a level- $0$ band. For a band type $(t;e_1,e_2)$ , a level-n band $(t^n;e_1^n,e_2^n)$ is of type $(t;e_1,e_2)$ if the $f^n$ -image of its bone is the bone of $(t;e_1,e_2)$ (or, equivalently, if $t^n$ is of type $\textbf {t}$ and $e_i^n$ is of type $\textbf {e}_i$ for $i=1,2$ . For $n>m$ , a level-n band $(t^n;e_1^n,e_2^n)$ is a subband of a level-m band $(t^m;e_1^m,e_2^m)$ if $t^n\subset t^m$ and $e_i^n \subset e_i^m$ for $i=1,2$ . If $\deg (f)=d$ , there are $d^n$ level-n tiles, edges, and bands of the same type.

4.6 Two directed graphs defined from finite subdivision rules

4.7 Parents and children

We define parents and children for various objects regarding finite subdivision rules. The following are some important properties of the parent–child relationship. For any $i>0$ , $\textbf {X}^i$ stands for a level-i object, which can be an edge, a band, or a curve consisting of the bones of bands.

• (Transitivity) For $n>m>l\ge 0$ , if $\textbf {X}^n$ is a child of $\textbf {X}^m$ and $\textbf {X}^m$ is a child of object $\textbf {X}^l$ , then $\textbf {X}^n$ is a child of $\textbf {X}^l$ . A similar statement holds for parents.

• (Unique existence of parents) For $n>m\ge 0$ , every level-n object $\textbf {X}^n$ has a unique level-m parent $\textbf {X}^m$ . If $\textbf {X}^n$ is recurrent, then so is $\textbf {X}^m$ .

• (Existence of recurrent children) For $n>m\ge 0$ , every level-m recurrent $\textbf {X}^m$ has at least one level-n child $\textbf {X}^n$ that is also recurrent. We note that it does not work for non-expanded curves consisting of more than one bone in general.

5.1 Contracting orbisphere bisets

Let A be a finite subset of the sphere $S^2$ . An orbisphere structure on $(S^2,A)$ is an order function $\textrm {ord}:A\to [2,\infty ]_{\mathbb {Z}}$ . We say that $\textrm {ord}$ is an orbisphere structure of a post-critically finite branched covering if it satisfies:

1. (1) $\textrm {ord}(a)\cdot \deg _f(a)~|~\textrm {ord}(f(a))$ for every $a\in S^2$ , where $\textrm {ord}(a)=1$ for $a\notin A$ ; and

2. (2) $\textrm {ord}(a)= \infty $ only if $a\in A$ is a Fatou point.

In item (1), $\infty $ is considered as a multiple of any integer or $\infty $ itself. It follows that $\textrm {ord}(a)=\infty $ for every a in a periodic cycle containing a critical point. The triple $(S^2,A,\textrm {ord})$ is called an orbisphere.

The orbisphere group $\pi _1(S^2,A,\textrm {ord})$ of an orbisphere $(S^2,A,\textrm {ord})$ is defined by

$$ \begin{align*} \pi_1(S^2,A,\textrm{ord})=\pi_1(S^2\setminus A) /\, \langle\{\gamma_a^{\textrm{ord}(a)}~|~a\in A~\textrm{and}~\textrm{ord}(a)\neq \infty \}\rangle, \end{align*} $$

where $\gamma _a$ is a peripheral loop of $a\in A$ and $\gamma _a^{\textrm {ord}(a)}=1$ if $\textrm {ord}(a)=\infty $ .

The Euler characteristic $\chi (S^2,A,\textrm {ord})$ of an orbisphere $(S^2,A,\textrm {ord})$ is defined by

(1) $$ \begin{align} \chi(S^2,A,\textrm{ord})=2+\sum_{a\in A}\bigg(\frac{1}{\textrm{ord}(a)}-1\bigg). \end{align} $$

The orbisphere $(S^2,A,\textrm {ord})$ is hyperbolic if $\chi (S^2,A,\textrm {ord})<0$ .

Let p be a base point of $\pi _1(S^2,A,\textrm {ord})$ . Define a set $B(f,A,\textrm {ord})$ by

$$ \begin{align*} \{ \gamma:[0,1]\to S^2 \setminus A ~|~ \gamma(0)=f(\gamma(1))=p \}/~\textrm{homotopy relative to}~(A,\textrm{ord}). \end{align*} $$

By the homotopy relative to $(A,\textrm {ord})$ , we mean a homotopy relative to A together with one more homotopy condition: for any $a\in A$ with $\textrm {ord}(a)<\infty $ , the $\textrm {ord}(a)$ th power of the peripheral loop of a is considered to be homotopically trivial.

There is a natural $\pi _1(S^2,A,\textrm {ord})$ -action on $B(f,A,\textrm {ord})$ from both left and right. More precisely, for $\gamma _1,\gamma _2\in \pi _1(S^2,A,\textrm {ord})$ and for $\delta \in B(f,A)$ , the product $\gamma _1 \cdot \delta \cdot \gamma _2$ is the concatenation of $\gamma _1$ , $\delta $ , and the lift of $\gamma _2$ through f starting at the endpoint of $\delta $ , in order. The left action is free, and the right action is transitive. The set $B(f,A)$ equipped with the left and right actions is called the orbisphere biset of $(S^2,A,\textrm {ord})$ . If an orbisphere structure $\textrm {ord}: A \to [2,\infty ]_{\mathbb {Z}}$ is given, we implicitly assume that $B(f,A,\textrm {ord})$ has the left and right $\pi _1(S^2,A,\textrm {ord})$ -actions. When an orbisphere $(S^2,A,\textrm {ord})$ is understood in the context, we simply write $B(f)$ for $B(f,A,\textrm {ord})$ .

A tensor square $B(f) \otimes B(f)$ can be defined in two different ways. Topologically, the tensor product $\delta _1 \otimes \delta _2$ for $\delta _1,\delta _2\in B(f)$ is defined as a concatenation of $\delta _1$ and the lift of $\delta _2$ starting at the endpoint of $\delta _1$ . Algebraically, it is a quotient of $B(f) \times B(f)$ by the relation $(\delta _1 \cdot \gamma ) \otimes \delta _2=\delta _1 \otimes (\gamma \cdot \delta _2)$ . The left and right actions naturally extend to $B(f) \otimes B(f)$ . Similarly, $B(f)^{\otimes n}$ has a left free and a right transitive $\pi _1(S^2,A,\textrm {ord})$ -action for any $n \ge 1$ .

A basis X for $B(f)$ is a collection of representatives of left orbits of the biset $B(f)$ . Its cardinality $|X|$ is the same as the degree of f. For any $n\ge 1$ , the tensor power $X^{\otimes n}$ of X is a basis for $B(f)^{\otimes n}$ . Topologically, a basis is a choice of curves from the base point p of $\pi _1(S^2,A,\textrm {ord})$ to the d preimages $f^{-1}(p)=\{p_1,p_2,\ldots ,p_d\}$ , where $d=\deg (f)$ . Let $\delta _i$ be a curve from p to $p_i$ for $i\in [1,d]_{\mathbb {Z}}$ . Then $\{\delta _1,\delta _2,\ldots ,\delta _d\}$ is a basis for $B(f)$ , and every basis of $B(f)$ is of this form. Fix $n\ge 1$ . Let $i_1,i_2,\ldots ,i_n\in [1,d]_{\mathbb {Z}}$ . We simply write

$$ \begin{align*} \delta_{i_1i_2\ldots i_n}:=\delta_{i_1} \otimes \delta_{i_2} \otimes \cdots \otimes \delta_{i_n}, \end{align*} $$

which gives a bijection $([1,d]_{\mathbb {Z}})^n\leftrightarrow X^{\otimes n}$ .

The contracting property does not depend on the choice of basis [Reference NekrashevychNek05, Corollary 2.11.7], but the nucleus does. See Remark 5.8 for the independence of the choice of orbisphere structures.

Every Böttcher expanding map also has the Fatou set and the Julia set, which have similar properties of the Fatou and Julia sets of rational maps, see [Reference Bartholdi and DudkoBD18].

A post-critically finite rational map f is Böttcher expanding since it has the Böttcher coordinates and enjoys the Schwarz lemma about the conformal metric. The next theorem, which follows from [Reference Bartholdi and DudkoBD18, Theorem A, Corollary 1.2], is an analogue of Thurston’s characterization and rigidity.

5.2 Semi-conjugacy to Böttcher expanding maps

The idea of semi-conjugacy was introduced by Rees [Reference ReesRee92] and Shishikura [Reference Shishikura and LeiShi00] to show that, for any mateable pair of post-critically finite polynomials, the topological mating is topologically conjugate to the corresponding rational map. Then the idea was further developed by Cui, Peng, and Tan [Reference Cui, Peng and TanCPT12] to a form that can be applied for not only matings but also general post-critically finite branched coverings and rational maps. We slightly further generalize the theorem of Cui–Peng–Tan by applying Bartholdi and Dudko’s recent work on Böttcher expanding maps [Reference Bartholdi and DudkoBD18].

The next theorem is a generalization of [Reference Cui, Peng and TanCPT12, Theorem 1.1, Corollary 1.2] replacing rational maps by Böttcher expanding maps.

Proof. Since the metric $\mu $ blows up near marked points of infinite order, we should take a compact subset away from the points of infinite order. Let $B^\infty =h(A^{\infty })$ , where $A^\infty $ is the subset of A consisting of elements having infinite order. There exists a small neighborhood U of $B^\infty $ such that for $M:=S^2\setminus U$ and $M'=f^{-1}(M)$ , we have $M'\subset M$ and $f:M'\to M$ is a branched covering which has a uniform expanding constant $\unicode{x3bb}>1$ in the following sense: for every curve $\gamma \subset M$ and any of its lifting $\gamma '$ through f, we have

$$ \begin{align*} \unicode{x3bb} \cdot l_\mu([\gamma'])< l_\mu([\gamma]). \end{align*} $$

Let $X=\{\delta _1,\delta _2,\ldots , \delta _d\}$ , where each $\delta _i$ joins the base point p of $\pi _1(S^2,A,\textrm {ord})$ to one of the d preimages $f^{-1}(p)$ . Define $D>0$ by

$$ \begin{align*} D=\max_{1 \le j \le d} l_\mu([h(\delta_j)]). \end{align*} $$

Let $w=\delta _{i_1i_2\ldots i_n}\in X^{\otimes n}$ , where $i_l\in \{1,2,\ldots ,d\}$ . Then w is the concatenation of $\delta _{i_1}$ , a lift of $\delta _{i_2}$ through f, a lift of $\delta _{i_3}$ through $f^2$ , and so one. Every curve $\delta _i$ and its any lifting can be contained in M up to homotopy. Hence, we have

$$ \begin{align*} l_\mu([h(w)]<D\cdot\bigg(1+\frac{1}{\unicode{x3bb}}+\frac{1}{\unicode{x3bb}^2}+\cdots \bigg)=D\cdot \frac{\unicode{x3bb}}{\unicode{x3bb}-1}.\\[-37pt] \end{align*} $$

5.3 Homotopically infinite non-expanded curves and Levy cycles

The next proposition is immediate from standard properties of the hyperbolic geometry.

Each of the following two propositions is each direction of the equivalence in Theorem 5.1. We split them because the ideas of the proofs are quite different.

Proof. Suppose that does not have a Levy cycle. Then for any basis X for the biset $B(f)$ , there is a nucleus $\mathcal {N}$ , which is a finite set. For every $k>0$ , we use the sequence of finite restrictions $\{\gamma ^n|_{[0,k]}\}_{n\ge 0}$ to obtain an element $h_k\in \mathcal {N}$ such that $\|h_k\|\to \infty $ . Here, $\| \cdot \|$ is a distance on $\pi _1(S^2,A,\textrm {ord})$ with respect to a generating set, which does not need to be specified. Then the nucleus $\mathcal {N}$ has infinitely many elements, which contradicts the assumption that the biset is contracting.

Recall that we use p for the base point of $\pi _1(S^2,A,\textrm {ord})$ , each element of a basis X for $B(f)$ is a curve from p to one of its f-preimages $f^{-1}(p)$ , and an element $w\in X^{\otimes n}$ is a concatenation of curves connecting an $f^i$ -preimage to an $f^{i+1}$ -preimage that are liftings of elements in X.

Step 1: Construction of $h_k$ . Fix $k>0$ . There is an infinite sequence $n_1<n_2<\cdots $ , which depends on k, so that $\gamma ^{n_i}([0,k])$ consists of the bones of the bands of the same types, that is, there exists level- $0$ bands $b_0,b_1,\ldots b_{k-1}$ (possibly repeated) such that for every $j\in [0,k-1]$ , $\gamma ^{n_i}([j,j+1])$ is the bone of a level- $n_i$ band of type $b_j$ , which is independent of $i>0$ .

For every level- $0$ edge e, we fix a point $m_e \in \textrm {int}(e)$ and call it the midpoint of e. We assume that a bone of a level- $0$ band is chosen in the homotopy class in such a way that their endpoints are the midpoints of level- $0$ edges. For every level- $0$ edge e, we also choose a path $\delta _e$ from p to $m_e$ . Then, for each level- $0$ band $b=(t;e_1,e_2)$ , we can assign an element

$$ \begin{align*} g_{b_i}:=\delta_{e_1} \cdot \mathrm{bone}(b_i) \cdot \overline{\delta}_{e_2} \in \pi_1(S^2,A,\textrm{ord}), \end{align*} $$

where the overline $\overline {\,\cdot \,}$ means the reverse of the orientation of a curve and $\mathrm{bone}(b_i)$ means the bone of a band $b_i$ .

For $g\in \pi _1(S,A,\textrm {ord})$ , we define $N(g)\subset \pi _1(S,A,\textrm {ord})$ by the collection of elements h with the following property: for infinitely many $n>0$ , there exist $v,w\in X^{\otimes n}$ such that $h \cdot v = w \cdot g$ . We remark that $N(g) \subset \mathcal {N}$ .

Claim. There exists $C>0$ , independent of k, such that $N(g_k:=g_{b_1}\cdots g_{b_k})$ contains at least one element $h_k$ with $d(h_k,g_k) < C$ .

Proof of Claim

Recall that for every $i>0$ and $j\in [0,k-1]_{\mathbb {Z}}$ , $\gamma ^{n_i}([j,j+1])$ is the bone of a level- $n_i$ band of type $b_j$ , which is independent of i. Let e and $e'$ be level- $0$ edges such that their midpoints $m_e$ and $m_{e'}$ are the endpoints of $\gamma ^0([0,k])$ .

Let $w_{n_i}\in X^{\otimes n_i}$ , which will be specified soon. Let $v_{n_i}\in X^{\otimes n_i}$ and $h_{k,n_i}\in \pi _1(S^2,A,\textrm {ord})$ be defined by

$$ \begin{align*} h_{k,n_i}\cdot v_{n_i}=w_{n_i}\cdot g_k. \end{align*} $$

Let $\tilde {g}_k$ be the lift of $g_k$ through $f^{n_i}$ starting from the terminal point of $w_{n_i}$ . Let $\tilde {\delta }_e$ and $\tilde {\delta }_{e'}$ be the parts of $\tilde {g}_k$ where $\delta _e$ and $\delta _{e'}$ are lifted. We specify $w_{n_i}$ as an element of $X^{\otimes n_i}$ satisfying the following: the curve $g_k$ with $\delta _e$ and $\delta _{e'}$ being truncated is $S_{\mathcal {R}}$ -combinatorially equivalent to $\tilde {g}_k$ with $\tilde {\delta }_e$ and $\tilde {\delta }_{e'}$ being truncated. See Figure 6.

Figure 6 The left figure is $g_k$ drawn in $S_{\mathcal {R}}$ , and the right figure is $h_{k,n_i}$ drawn in $\mathcal {R}^{n_i}(S_{\mathcal {R}})$ . The bold line segments are portions of $1$ -skeletons of $S_{\mathcal {R}}$ and $\mathcal {R}^{n_i}(S_{\mathcal {R}})$ .

Then $h_{k,n_i}$ and $g_k$ differ by the pre- and post-composition with loops $w_{n_i}\cdot \tilde {\delta }_e \cdot \overline {\delta }_e$ and $\overline {\delta }_{e'} \cdot \delta _{e'} \cdot \overline {v}_{n_i}$ . We have: (1) a uniform upper bound on the homotopic length of $v_{n_i}$ and $w_{n_i}$ (in the projection to the Böttcher expanding map) by Lemma 5.11; (2) a uniform upper bound on the intersection between $\delta _e$ and $S_{\mathcal {R}}^{(1)}$ ; and (3) the upper bound in item (2) is also an upper bound of the intersection between any level-n lift $\tilde {\delta }_e$ and $\mathcal {R}^n(S_{\mathcal {R}})^{(1)}$ . Therefore, we have $\|w_{n_i}\cdot \tilde {\delta }_e \cdot \overline {\delta }_e\|, \|\overline {\delta }_{e'} \cdot \delta _{e'} \cdot \overline {v}_{n_i}\|< C/2$ for some C so that $d(g_k,h_{k,n_i})<C$ . Since there are only finitely many elements of $\pi _1(S^2,A,\textrm {ord})$ within the distance C from $g_k$ , there exists $h_k$ such that $h_k=h_{k,n_i}$ for infinitely many i terms.

Step 2: Proof of $\|h_k\|\to \infty $ . Let $g_k$ and $h_k$ be as defined in Step 1. Since $d(h_k,g_k)<C$ , it suffices to show $\|g_k\|\to \infty $ as k tends to $\infty $ .

Let $e_0$ and $e_k$ be the level- $0$ edges whose midpoints are the endpoints of $\gamma ^0([0,k])$ so that $g_k=\delta _{e_0} \cdot \gamma ^0([0,k]) \cdot \overline {\delta }_{e_k}$ . Then $\|g_k\|\to \infty $ follows from the condition that $\gamma ^0$ is homotopically infinite.

6.0.1 Motivation for the use of train-tracks

Let us see Figure 7. Let t denote the hexagonal tile and $e_1,e_2,e_3$ denote three of its boundary edges. Suppose that $b_1=(t;e_1,e_2)$ and $b_2=(t;e_1,e_3)$ are level-0 recurrent bands so that each has two level-1 recurrent subbands of type $b_1$ and $b_2$ . Then each level-1 recurrent subband of type $b_1$ or $b_2$ has two level- $2$ recurrent subbands of type $b_1$ and $b_2$ . Assume that we draw the bones of these bands. At level-0, we have two curves each of which joins $e_1$ to $e_2$ or $e_3$ . As a ‘collection’ of these two curves, we might consider a tripod whose leaves are on $e_1,e_2,$ and $e_3$ . However, the tripod contains an unintended curve which joins $e_2$ to $e_3$ . To exclude such a curve, we use the idea of train-tracks, which makes the curve joining $e_2$ and $e_3$ illegal.

Figure 7 Train-track structures on non-expanding spines.

6.1 Train-track

Let G be a graph and $v\in G$ be a point, which could be a vertex or a point in the interior of an edge. A direction at v is a germ of continuous curves starting from v. The number of directions at v is equal to the number of connected components of $U\setminus \{v\}$ , where U is a sufficiently small neighborhood of v. Denote the set of directions at v by $D_v$ .