{'fraction_non_alphanumeric': 0.047480971366437114, 'fraction_numerical': 0.015363210139251014, 'mean_word_length': 3.4060375025757264, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Expansion properties for finite subdivision rules I

Among Thurston maps (orientation-preserving, postcritically finite branched coverings of the 2-sphere to itself), those that arise as subdivision maps of a finite subdivision rule form a special family. For such maps, we investigate relationships between various notions of expansion---combinatorial, dynamical, algebraic, and coarse-geometric.


Introduction
This is the first in a series of papers devoted to expansion properties of Thurston maps and of finite subdivision rules (fsr's).
It is a robust principle in discrete-time dynamical systems that expanding maps are determined, up to topological conjugacy, by a finite amount of combinatorial data. For example, the topological conjugacy class of a smooth expanding map g : S 1 → S 1 is determined by its degree. Also, in many settings, homotopy or other similar classes of maps which contain smooth expanding maps can be identified combinatorially, and shown to contain smooth (indeed, algebraic) models. For example, a continuous map f : S 1 → S 1 is homotopic to an expanding map g if and only if | deg(f )| > 1; in this case one may take g as x → deg(f )x mod 1. Similar results hold for torus maps f : T 2 → T 2 and indeed much more general results hold, cf. [24,Theorem 3]. The expanding maps g are necessarily covering maps.
In one real dimension, multimodal interval maps f : I → I, studied in detail by Milnor and Thurston [19], provide a natural class of noninvertible maps with local branching. Their kneading theory provides a rich set of combinatorial invariants. In this setting also, one may formulate a notion of combinatorial classes of maps, and one may characterize those classes containing expanding maps as well. The presence of local branch (turning) points means that the notion of expanding needs to be properly formulated. Up to topological conjugacy, the subclass of such maps g with eventually periodic turning points-called postcritically finite maps-is countable. A general result then implies that each postcritically finite expanding map g is topologically conjugate to an algebraic model-a piecewise linear map where the absolute value of the slope is constant.
In two real dimensions, Thurston [13], [26] generalized the kneading theory to orientation-preserving postcritically finite branched coverings f : (S 2 , P ) → (S 2 , P ); here, P is the set of forward orbits of branch points, and is required to be finite. These maps f are now often called Thurston maps for brevity. The central result-sometimes referred to as the Fundamental Theorem of Complex Dynamics-is (i) a combinatorial characterization of rational functions g among Thurston maps, and (ii) a rigidity result, which asserts that the holomorphic conjugacy class of a rational Thurston map g is (with a well-understood class of exceptions) uniquely determined by its combinatorics. The second of these results says that in addition to the topological dynamics, the conformal structure on (S 2 , P ) left invariant by g is encoded in the combinatorics of g. At around the same time, Cannon [4] was considering the problem of the hyperbolization of certain three-manifolds. His approach was to formulate what is now called Cannon's conjecture: a Gromov hyperbolic group G with ∂G homeomorphic to S 2 acts geometrically on hyperbolic three-space. Bonk and Kleiner [2] reinterpreted this in the following way: the natural quasiconformal structure on ∂G determined by the family of so-called visual metrics is, conjecturally, equivalent to that of the Euclidean metric.
The presence of a natural combinatorial structure on ∂G generated much interest in the problem of characterizing its quasisymmetry class through asymptotic combinatorial means. These structures were highly reminiscent of cellular Markov partitions occuring in dynamics, and these began to be studied in their own right [5,6,7,8,9]. Now called finite subdivision rules, these often take the form of a Thurston map whose inverse branches refine some tiling of S 2 ; see §2. Such Thurston maps are, a priori, special among general Thurston maps. Along the way, various notions of topological expansion and of combinatorial expansion were formulated for Thurston maps, and relationships among these notions were established [3,5,11,16]. In independent remarkable developments, it was shown that an expanding rational Thurston map and, more generally, an expanding Thurston map, has the property that some iterate is the subdivision map of an fsr [9,3].
It became recognized that bounded valence finite subdivision rules-those for which there is an upper bound on the valence of 0-cells independent of the number of levels of subdivision-behave more regularly than their unbounded valence counterparts. In this context, an fsr has unbounded valence if and only if the Thurston map defining its subdivision rule has a periodic branch point. For example, the unbounded valence barycentric subdivision rule admits two natural subdivision maps. One is a rational map for which there exists a fixed critical point and for which the diameters of the tiles at level n do not tend to zero as n → ∞. The other is a piecewise affine map, for which the diameters of the tiles do tend to zero. This distinction led these authors to the realization that the formulation of a reasonable notion of combinatorial expansion for Thurston maps with periodic branch points is subtle.
In this first work, we suppose f : S 2 → S 2 is a Thurston map which is the subdivision map of an fsr, and we investigate properties of f , focusing on themes related to notions of expansion. We discuss combinatorial, grouptheoretic, dynamical, and coarse geometric properties.
Here is an outline and a summary of our main results. A heads-up to the reader: in smooth dynamics, it is common to focus on forward iterates and expansion. But in our setting, it is often more convenient to consider backward iterates and contraction. So below, one should read 'expanding' as 'forward iterates are expanding' and 'contracting' as 'backward iterates are contracting'. For example, the map x → 2x modulo 1 is both expanding and contracting.
Throughout, we assume f is the subdivision map of a finite subdivision rule R .
§2 introduces basic terminology related to Thurston maps and fsr's. §3 formulates several distinct notions of combinatorial expansion for fsr's, and systematically studies the subtleties mentioned above. These notions are local and are defined in terms of tile types. We discuss their relationships, and give examples and counterexamples. While many of these notions coincide in the case of bounded valence, in general, this is not the case. We define a particular form of combinatorial expansion, here denoted Property (CombExp), and single it out as the one which is best suited for our purpose of characterizing various equivalent notions.
§4 quickly recalls the construction of group-theoretic invariants associated to f , focusing on the associated virtual endomorphism φ f of the orbifold fundamental group. §5 introduces the notion of a combinatorially contracting (CombContr) fsr. Unlike the local notions introduced in §3, combinatorially contracting is a global notion. Our first main result, Proposition 5.1, gives sufficient local combinatorial conditions for an fsr to be combinatorially contracting. Corollary 5.2 then implies that property (CombExp) implies (CombContr). Examples in §3 show that the converse fails, however.
§6 presents results related to algebraic notions: • Theorem 6.2: Let f : S 2 → S 2 be a Thurston map which is Thurston equivalent to the subdivision map of a finite subdivision rule. Then there exist (1) nonnegative integers a and b; (2) a choice of orbifold fundamental group virtual endomorphism φ : G p G p associated to f ; (3) a finite generating set for the orbifold fundamental group G p with associated length function · such that φ n (g) ≤ a g + bn for every nonnegative integer n and g ∈ dom(φ n ). If the subdivision map takes some tile of level 1 to the tile of level 0 which contains it, then we may take b = 0. If there is only one tile of level 0, then we may take a = 1.
• Theorem 6.5: R is contracting if and only if φ f is contracting. Theorem 3.4 shows that if R has bounded valence, then property (Comb-Exp) is equivalent to property (M0Comb), mesh approaching 0 combinatorially. Corollary 5.2 shows that property (CombExp) implies that R is contracting. Combining these results with Theorem 6.5 implies that if R has bounded valence and the mesh of R approaches 0 combinatorially, then φ f is contracting. This is the main result of [11].
• Theorem 6.7: If f is combinatorially equivalent to a map g that, outside a neighborhood of periodic branch points, is expanding with respect to some length metric, then R is contracting. In § §7 and 8, we turn our attention to coarse (large-scale) geometric notions. Associated to f are two natural infinite 1-complexes. The fat path subdivision graph joins a tile to its parent by a vertical edge and to its edge-adjacent neighbors by a horizontal edge. The selfsimilarity complex is built from the iterated monodromy of f under the action of the orbifold fundamental group. Theorem 7.4: If R is contracting, then its fat path subdivision graph is Gromov hyperbolic.
For the proof, we use some general results of Rushton [23]. These lead to a condition on R which is necessary and sufficient for the fat path subdivision graph to be Gromov hyperbolic. This necessary and sufficient condition is very similar to but strictly weaker than the condition that R is contracting.
Theorem 8.1: The fat path subdivision complex and (any) selfsimilarity complex are quasi-isometric. §9 begins with a discussion of dynamical plane obstructions for an fsr to be contracting. The most natural candidate is a so-called Levy obstruction. It is easy to see that the existence of Levy obstructions implies that φ f is not contracting, and hence that R is not contracting. However, we do not know if Levy obstructions are the only obstructions. We conclude with some related open questions.
1.1. Acknowledgement. We express heartfelt gratitude to Jim Cannon, who helped us in many ways. Without him this paper would not exist. K. Pilgrim was supported by Simons grant 245269.

Basic definitions
A continuous map f : S 2 → S 2 is a branched covering if f is orientation preserving and for each x ∈ S 2 there are local charts about x and f (x) (this is the set of points at which f is not locally injective) and the postcritical set is P f = ∪ n>0 f n (Ω f ). The mapping f is called postcritically finite (or critically finite) or a Thurston map if P f is finite. Two Thurston maps f and g are combinatorially equivalent or Thurston equivalent if there are orientation-preserving homeomorphisms h 0 , h 1 : (S 2 , P f ) → (S 2 , P g ) such that h 0 • f = g • h 1 and h 0 and h 1 are isotopic rel P f .
A preimage of a connected set U under f is a connected component of f −1 (U ). Let U 0 be a finite open cover of S 2 by connected sets. Inductively define finite open covers U n of S 2 by setting U n+1 to be the cover whose elements are preimages of elements of U n . Following Haïssinsky-Pilgrim [15], a Thurston map f is said to satisfy Axiom [Expansion] with respect to U 0 if for every open cover Y of S 2 , there exists N ∈ N such that for all n ≥ N , every element of U n is contained in an element of Y. We say that f satisfies Axiom [Expansion] if it satisfies Axiom [Expansion] with respect to some such cover U 0 . Equipping S 2 with e.g. the spherical metric, letting ǫ > 0 be arbitrary, and taking Y to be a cover by ǫ balls shows that Axiom [Expansion] is equivalent to the assertion that there exists a finite cover by connected open sets whose iterated preimages under f n have diameters tending to zero uniformly as n → ∞.
A finite subdivision rule R consists of a finite 2-dimensional CW complex S R which is the union of its closed 2-cells, a subdivision R(S R ) of S R , and a continuous cellular map f : R(S R ) → S R whose restriction to each open cell is a homeomorphism. Furthermore, for each closed 2-cellt of S R there are i) a cell structure t on the 2-disk D 2 (t is called the tile type oft) such that the 1-skeleton of t is ∂D 2 and t has at least three vertices and ii) a continuous surjection ψ t : t →t (called the characteristic map oft) whose restriction to each open cell is a homeomorphism. If R is a finite subdivision rule, a 2-dimensional CW complex X is an R-complex if it is the union of its closed 2-cells, and there is a continuous cellular map g : X → S R whose restriction to each open cell is a homeomorphism. In this case, for each positive integer n there is a subdivision R n (X) of X with associated map f n • g.
When the underlying space of S R is homeomorphic to the 2-sphere S 2 and f is orientation preserving (for concreteness, we consider only this case), f is a Thurston map. Since S R is an R-complex, we get a recursive sequence {R n (S R )} of subdivsions of S R . For each positive integer n, f is a cellular map from the n th to the (n − 1) st subdivision. Thus, we may speak of tiles (which are closed 2-cells), edges, and vertices at level n. The subdivision rule R has bounded valence if there is a uniform upper bound on the valence of vertices of {R n (S R )}. It is important to note that formally a finite subdivision rule is not a combinatorial object, since the map f , which is part of the data, is assumed given. In other words: as a dynamical system on the 2-sphere, the topological conjugacy class of f is well defined.
Two finite subdivision rules R, R ′ with subdivision maps f , f ′ are weakly isomorphic if there is a cellular isomorphism h : S R → S R ′ such that h is cellularly isotopic to a cellular isomorphism g : In the case of finite subdivision rules on the sphere, R weakly isomorphic to R ′ implies that f and f ′ are combinatorially equivalent as Thurston maps. The finite subdivision rules R, R ′ are isomorphic provided there is a cellular isomorphism h : That is, f and f ′ are topologically conjugate as dynamical systems via a cellular isomorphism.

Expansion properties for finite subdivision rules
We are interested here in various definitions of combinatorial expansion for finite subdivision rules. We begin with some definitions of separation and expansion properties. Let R be a finite subdivision rule.
(Esub) R is edge subdividing if whenever e is an edge in S R , there is a positive integer n such that e is properly subdivided in R n (S R ). (Esep) R is edge separating if whenever t is a tile type of R and e and e ′ are disjoint edges of t, there is a positive integer n such that no tile of R n (t) contains subedges of e and of e ′ . (VEsep) R is vertex-edge separating if whenever t is a tile type, u is a vertex of t, and e is an edge of t not containing u, there exists a positive integer n such that no tile of R n (t) contains both u and an edge contained in e. (Vsep) R is vertex separating if whenever t is a tile type and u and v are distinct vertices of t, there exists a positive integer n such that no tile of R n (t) contains both u and v.
(Sexp) R is subcomplex expanding if whenever X is an R-complex and M > 0, then there exists a natural number N such that if Y and Z are disjoint subcomplexes (not necessarily unions of tiles) of X then the edge-path distance in R n (X) between Y and Z is greater than M if n ≥ N . (M0) R has mesh approaching 0 if given an open cover U of S R there exists a positive integer n such that every tile of R n (S R ) is contained in an element of U . We are interested in the relationships between these definitions.
• The first four-(Esub), (Esep), (VEsep) and (Vsep)-of these nine properties might be called "primary" because Theorem 3.5 below will show that the last five can be defined in terms of these. Esub follows from the other three primary properties.
We next give several examples. In each example, the subdivision complex is a 2-sphere and the subdivision map is a Thurston map. Each example is accompanied by a figure giving the subdivisions of the tile types. For each example, the edge labelings and their cyclic order determine the tile types of all of the tiles, so the tile types are not specified.
Example 3.1. This finite subdivision rule shows that (Vsep) does not follow from the other three primary properties. Let f (z) = 1 − 1/z 2 . The postcritical set is {0, 1, ∞}. We equip the Riemann sphere with a cell structure for which the 1-skeleton is the real axis together with ∞ and the set of 0-cells is the postcritical set. The associated finite subdivision rule R 1 has two tile types, and the subdivision complex S R 1 is a triangular pillowcase. The subdivisions of the tile types are given in Figure 1. Since both tile types are triangles, a tile cannot have disjoint edges and so (Esep) is satisfied vacuously. Since the edges of each tile type are properly subdivided in the third subdivision, R 0 also satisfies (Esub) and hence (M0comb). The vertex 1, which is contained in edges a and b, is separated from the edge opposite it in the first subdivision. So vertex ∞ is separated from the edge opposite it in the second subdivision. Vertex 0 is separated from the edge opposite it in the third subdivision. So R 1 satisfies (VEsep). However, (Vsep) is not satisfied because the subdivision of each tile type contains a tile of the same type with vertices 0, 1 and ∞. Note from Figure 2 that the immediate basins of postcritical points have closures that meet. Example 3.2. This finite subdivision rule R 2 shows that (VEsep) does not follow from the other three primary properties. The subdivision complex is a triangular pillowcase. The subdivisions of the two tile types are given in Figure 3, and Figure 4 (which was drawn using CirclePack [25]) shows the first four subdivisions of the quadrilateral Q obtained by gluing the two triangles along the edge labelled c. R 2 satisfies (Esep) vacuously since the tile types are triangles. For each tile type t, each edge of t is properly subdivided in R 2 (t) and so R 2 satisfies (Esub) and (M0comb).
This finite subdivision rule satisfies (Esub), (Esep), and (Vsep); it does not satisfy (VEsep) or (Sexp). The subdivision map is realized by the rational map Example 3.3. This finite subdivision rule R 3 shows that (Esep) does not follow from the other three primary properties. The subdivision rule has bounded valence and has subdivision complex a rectangular pillowcase. The subdivisions of the two tile types are given in Figure 5, and Figure 6 (which was drawn using CirclePack [25]) shows the first three subdivisions of one of the tile types. It is clear from the subdivisions of the tile types that it satisfies (Esub), (Vsep), and (VEsep). Since for any n and tile type t the complex R n 3 (t) has a tile which contains subedges of the edges of t labelled b and d, R 3 does not satisfy (Esep) or (Sexp). It is not realizable by a rational map; a horizontal curve gives a Thurston obstruction. Proof. (1) is clear. The reverse implication in (2) follows from (1). The forward implication in (2) is similar to [7,Lemma 2.7]. We begin by assuming that X is a tile type of R and that Y and Z both consist of either one vertex or one edge. By repeatedly applying what it means for R to be combinatorially expanding and using the fact that there are only finitely many choices for X, Y , and Z, we find that there exists a positive integer N 0 for which the following three statements hold. If Y and Z are distinct vertices, then no tile of R N 0 (X) contains both Y and Z. If Y is a vertex not in the edge Z, then no tile of R N 0 (X) contains Y and an edge in Z. If Y and Z are disjoint edges, then no tile of R N 0 (X) contains an edge in Y and an edge in Z. Moreover, the same statements hold for the same integer N 0 if X is any tile in any R-complex and if Y and Z both consist of either one vertex or one edge of X.  Now let Y and Z be any disjoint subcomplexes of any R-complex X. We next prove by contradiction that no tile of R 3N 0 (X) meets both Y and Z. To prove this, suppose that t 3 is a tile of R 3N 0 (X) which meets both Y and Z. Let y ∈ Y ∩ t 3 and z ∈ Z ∩ t 3 . Let t i be the tile of R iN 0 (X) which contains t i+1 for i = 2, then i = 1, and then i = 0. Because y and z are both contained in t 3 and the subcomplexes Y and Z are disjoint, neither Y nor Z contains t 3 . Hence neither Y nor Z contains t i for i ∈ {0, 1, 2, 3}. So  So either y or z is a vertex of t 1 . The same reasoning now shows that both y and z are vertices of t 2 . We finally obtain a contradiction to the vertex separating property provided by the choice of N 0 . Thus no tile of R 3N 0 (X) meets both Y and Z.
The previous paragraph implies that the star of Y in R 3N 0 (X) is disjoint from Z. Inductively, the mth star of Y in R 3mN 0 (X) is disjoint from Z for every positive integer m. So if m ≥ M , then the edge-path distance in R 3mN 0 (X) between Y and Z is greater than M . Thus we may let N be any integer greater than 3M N 0 . This proves (2).
For (3), note that by the first statement of the theorem, (CombExp) ⇒ (M0comb) for any finite subdivision rule. The equivalence of (M0comb) and (M0weak) for a bounded valence finite subdivision rule is [ [5] when the authors were primarily interested in finite subdivision rules with bounded valence. For finite subdivision rules without bounded valence, the property (CombExp) is a better fit for the notion "mesh approaching zero combinatorially". By the second part of Theorem 3.4, we could have defined combinatorially expanding as being subcomplex expanding. We used the definition we gave instead because it is easier to verify.
In [11,Theorem 6.1] we prove that, to verify the conditions (Esub) and (Esep) of (M0comb) for a finite subdivision rule R, it suffices to let n be the integer kl 2 , where k is the number of tiles in S R and l is the maximum number of edges of a tile type of R. The statement and proof easily adapt to give the following. Proof. The proof follows the argument in the proof of [11, Theorem 6.1]. If the conditions (Esep), (VEsep), and (Vsep) are satisfied for n = kl 2 , then R is combinatorially expanding. Now suppose that R is combinatorially expanding. Let G e (respectively G v ) be the directed graph whose vertices are triples (t, a 1 , a 2 ) such that t is a tile type and a 1 and a 2 are disjoint edges (respectively vertices) of t. Let G ve be the directed graph whose vertices are triples (t, v, e) such that t is a tile type, v is a vertex of t, and e is an edge of t which is disjoint from v. For each of the graphs, there is a directed edge from (t, a 1 , a 2 ) to (t ′ , a ′ 1 , a ′ 2 ) if the subdivision R(t) contains a tile with type t ′ such that the 0-cell (or 1-cell) corresponding to a ′ i is equal to (or contained in) a i for i = 1, 2. Each of the three graphs has at most kl 2 vertices. The subdivision rule R does not satisfy condition (Esep) (respectively (Vsep), respectively (VEsep)) if and only if the graph G e (respectively G v , respectvely G ve ) has a directed cycle. For each case, if there is a directed cycle there is a directed cycle of length at most kl 2 , the number of vertices in the graph.

The virtual endomorphism
This section mainly fixes definitions and notation related to the orbifold fundamental group virtual endomorphism. Let f : S 2 → S 2 be a Thurston map.
The weight function ν. For y ∈ S 2 let ν(y) = lcm{deg x (f n ) : f n (x) = y, n ∈ N}. The set of elements x in S 2 such that ν(x) > 1 is exactly the postcritical set P f of f , a finite set.
The orbifold fundamental group G p . We choose a basepoint p ∈ S 2 \ P f .
Let N p be the normal subgroup of the fundamental group π 1 (S 2 \ P f , p) generated by all elements of the form g µ(x) , where g is represented by a simple loop around x ∈ P f based at p. The orbifold fundamental group associated to f is G p = π 1 (S 2 \ P f , p)/N p . Changing the basepoint p leads to an isomorphic group just as for the ordinary fundamental group.
The orbifold universal covering map π. Let π : D → S 2 be the orbifold universal covering map for f . The restriction of π to the points of D which map to S 2 \P f is the ordinary covering map associated to the subgroup N p of f are branch points of π. The orbifold fundamental group virtual endomorphism φ. We define a group homomorphism φ from a subgroup of G p to G p . Choose q ∈ S 2 such that f (q) = p. Let β be a path from p to q in S 2 \P f . The domain dom(φ) of φ consists of all elements g ∈ G p represented by loops γ based at p such that γ lifts via f to a loop f −1 (γ)[q] based at q. Then φ(g) is the homotopy class of βf −1 (γ)[q]β −1 . Concatenations of paths are read from left to right. This definition depends on the choice of p, q and β, but it is unique up to preand post-composition by inner automorphisms. This defines the orbifold fundamental group virtual endomorphism φ : G p G p associated to f . Properties of φ. Suppose that f has degree d. Let q 1 = q, . . . , q d be all the points in S 2 which f maps to p. Let γ be a loop based at p. Then the lift f −1 (γ)[q] of γ to a path based at q ends at one of the points q 1 , . . . , q d . If γ = f (α), where α is a path from q to q i for some i ∈ {1, . . . , d}, then f −1 (γ)[q] = α ends at q i . This discussion essentially implies that φ is surjective and that [G p : dom(φ)] = d. Extending this argument shows that φ is level transitive in the language of Nekrashevych's book [20].
The contraction ratio ρ φ . Let g denote the length of g ∈ G p relative to some finite generating set of G p . The contraction ratio of φ is by definition Of course, in the inner limit we only consider g ∈ dom(φ n ). Lemma 2.11.10 of [20] shows that this limit exists and is independent of the choice of generating set. Because φ is level transitive, Proposition 2.11.11 of [20] implies that φ is contracting if and only if ρ φ < 1.
Iterates of φ. Let n be a positive integer. We may view φ n in the following way. We have p and β 1 = β. We inductively define β i to be the lift of β i−1 via f such that the initial endpoint of β i equals the terminal endpoint of β i−1 for i ∈ {2, . . . , n}. Let r be the terminal endpoint of β n . Then a loop γ at p represents an element g of dom(φ n ) if and only if the lift of γ to r via f n is closed. Furthermore, φ n (g) is gotten by traversing β 1 , . . . , β n , then f −n (γ)[r] and then β −1 n , . . . , β −1 1 . G p ∼ = Aut(π). Since N p is a normal subgroup of π 1 (S 2 \P f , p), the covering map π is normal (regular), and its automorphism group Aut(π) of deck transformations is isomorphic to G p . We next explicitly identify such an isomorphism. Let p ∈ D be a lift of the basepoint p ∈ S 2 \ P f . Let γ be a loop in S 2 \ P f based at p. Let γ be the lift of γ based at p. There exists a unique element σ ∈ Aut(π) such that σ( p) is the terminal endpoint of γ. The map γ → σ induces a group isomorphism from G p to Aut(π). We use this group isomorphism to conjugate φ to a virtual endomorphism of Aut(π). Abusing notation, we also denote the virtual endomorphism of Aut(π) by φ.
Torsion in G p . The group G p is an F -group in the terminology of Lyndon and Schupp's book [18]. Proposition 6.2 of [18] implies that every torsion element of G p is conjugate to an element with a representative loop which is either peripheral or inessential. So every torsion element of Aut(π) fixes a branch point of π.
The lift F of f −1 . The multifunction f −1 lifts to a genuine function F : D → D via π. Recall that q is a point in S 2 such that f (q) = p and that β is a path in S 2 \ P f from p to q. Let β be the lift of β to D based at p, and let q be the terminal endpoint of β. We may, and do, choose F so that F ( p) = q.
We conclude this section with the following theorem which relates φ and F .
Proof. Let σ be in the domain of φ. We recall the definition of φ(σ). Let γ be a loop in S 2 \ P f based at p which represents the element g ∈ G p which maps to σ under the isomorphism from G p to Aut(π). Let γ be the lift of γ based at p. See Figure 7. Then the terminal endpoint of γ is σ( p). We have a path β in S 2 \ P f based at p and ending at q. We have the lift β of β based at p and ending at q = F ( p). We have that φ(g) is the homotopy class and they agree at one point, p. Thus they are equal. This proves Theorem 4.1.

Contracting finite subdivision rules
In this section we assume that f : S 2 → S 2 is a Thurston map which is the subdivision map of a finite subdivision rule R. We fix more definitions and notation leading to the notion of contracting finite subdivision rule.
The finite subdivision rule R. The 2-sphere S 2 has the structure of a CW complex R 0 (S 2 ). Every postcritical point of f is a vertex of R 0 (S 2 ), and f maps the 1-skeleton of R 0 (S 2 ) into itself. This leads to an infinite sequence R 0 (S 2 ), R 1 (S 2 ), R 2 (S 2 ), . . . of cell structures, each one refining the previous one, such that f maps every open cell of R n (S 2 ) homeomorphically onto an open cell of R n−1 (S 2 ) for every positive integer n. We refer to the cells of R n (S 2 ) as cells of level n.
The cell structure R −1 (S 2 ). We choose a tree in the 1-skeleton of R 0 (S 2 ) which contains P f . For neatness, we require that every leaf of this tree is in P f . The vertices and edges of this tree together with the 2-cell which they determine provide S 2 with another cell structure, which we denote by R −1 (S 2 ). When dealing with R −1 (S 2 ), we abuse terminology by referring to S 2 as a tile t (with edge identifications). By the interior of t, we mean the points of S 2 which are not in the 1-skeleton of R −1 (S 2 ). This is an open topological disk.
Lifting the cell structures to D * . We would like to use π to lift our cell structures on S 2 to cell structures on the orbifold universal covering space D. This is not always possible because in general π does not surject onto S 2 . It surjects onto S 2 \ P ∞ f . Consequently, D is generally in a certain sense missing some vertices. So we enlarge D by adjoining a set C (cusps) to it in such a way that π extends naturally to C, mapping C to P ∞ f . We continue to use π to denote this extension.
(This determines the topology of D * .) The elements of Aut(π) extend to D * and preserve these cell structures.
The generating set S. Let t be the tile of R −1 (S 2 ). In this paragraph we require that p is not in the 1-skeleton of R −1 (S 2 ), that is, p is in the interior of t. Let p ∈ D be a lift of p. Let t be the lift of t containing p. The neatness assumption in the definition of R −1 (S 2 ) implies that every edge of t is on the boundary of t. These edges can be partitioned into pairs {e, e ′ } of distinct edges such that σ(e) = e ′ for some σ ∈ Aut(π). The set S of all such elements σ, one for every such pair of edges, forms a generating set for Aut(π). Using the obvious bijection between the Aut(π)-orbits of p and t, we obtain a corresponding subset S of G p , which is a generating set for G p . We use the notation · to denote lengths of elements of both G p and Aut(π) with respect to these generating sets.
The fat path pseudometrics. Let n ∈ {−1, 0, 1, . . .}. Let γ be a curve in D. (We emphasize that γ contains no cusps.) We define the length ℓ n (γ) of γ relative to R n (D * ) to be 1 less than the number of tiles of R n (D * ) which meet γ. The fat path pseudometric d n on D relative to R n (D * ) is defined so that d n (x, y) is the minimum such length of a curve in D joining the points x, y ∈ D. (A fat path in R n (D * ) is the union of all tiles of R n (D * ) which meet a given curve in D.) These pseudometrics are not metrics because every two points in the interior of one tile of R n (D * ) are at d n -distance 0 from each other. In addition, the equation d n (x, x) = 0 fails if x is in the 1-skeleton of R n (D * ). By a d 0 -geodesic in S 2 \P f , we mean a curve in S 2 \P f whose lifts to D are d 0 -geodesics. Let g ∈ G p , and let σ ∈ Aut(π) be the corresponding element given by our bijection. If p is not in the 1-skeleton of R −1 (S 2 ), then d −1 ( p, σ( p)) = σ = g .
Decompositions of curves. Let n be a nonnegative integer. Let γ be a curve in S 2 \ P f beginning at the point x and ending at the point y. We wish to speak of the level n decomposition of γ. For this we always, at least implicitly, assume that γ meets the 1-skeleton of R n (S 2 ) in finitely many, say m, points, and these points are not vertices of R n (S 2 ). So γ decomposes as the concatenation of curves γ 0 , . . . , γ m , where γ 0 begins at x and γ m ends at y. If x lies in a level n edge, then γ 0 is constant. Likewise if y lies in a level n edge, then γ m is constant. We call γ 0 , . . . , γ m the level n segments of γ. Every segment γ 0 , . . . , γ m is contained in a level n tile. This concatenation γ 0 · · · γ m is the level n decomposition of γ. The segments γ 0 and γ m are the outer segments, and γ 1 , . . . , γ m−1 are the inner segments. We say that γ is taut (for level n) if it intersects the 1-skeleton of R n (S 2 ) transversely and if the following condition is satisfied. For every inner segment α of γ there exists a tile type s to which α pulls back. We require that the endpoints of this pullback of α lie in different edges of s. We define level n decomposition and tautness of curves in D analogously.
These notions are preserved by π : D → S 2 . If γ is a taut d 0 -geodesic arc in S 2 \ P f with a level 0 decomposition having m + 1 segments, then m is the d 0 -length of every lift of γ to D. We are especially interested in the case in which the level 0 and level n decompositions of γ are equal for some positive integer n. This is illustrated in Figure 8, where level 0 edges are drawn with solid line segments and level n = 1 edges not contained in these are drawn with dashed line segments. The curve γ in Figure 8 is taut.
Contracting finite subdivision rules. We say that the finite subdivision rule R is contracting if there exist positive integers M and n such that the following condition is satisfied. If γ is a taut d 0 -geodesic in S 2 \ P f with level 0 and level n decompositions which are equal, then the number of level 0 segments in γ is at most M .

Remarks:
(1) It is immediately clear from the definition that R is contracting if and only if the following more combinatorial-flavored condition holds. Note first that a taut curve corresponds to an edge-path without backtracking. Next, an edge-path in the dual graph to the tiling of D at level n determines in a canonical fashion a corresponding edge-path at level n − 1. Their lengths are the same if and only if no two consecutive level n tiles are contained in the same parent tile. Finally, here is the equivalent condition: there exist positive integers M, n such that for each level n geodesic edge-path of length M in the dual tiling in D, the corresponding edge-path at level 0 has length strictly less than M .  The rest of this section is devoted to discussing contracting finite subdivision rules. Our interest in contracting finite subdivision rules lies in the fact that Theorem 6.5 below shows that R is contracting if and only if φ is contracting. To gain a feeling for contracting finite subdivision rules, we next prove that if R is edge and vertex separating, then R is contracting.
Proposition 5.1. Let R be a finite subdivision rule which is edge separating and vertex separating. Then R is contracting.
Proof. Because R is edge separating, there exists a positive integer k such that for every tile type t of R and disjoint edges e 1 and e 2 of t, no tile of R k (t) contains subedges of e 1 and e 2 . Because R is vertex separating, there exists a positive integer m such that the open R m (S 2 )-stars of the vertices of R 0 (S 2 ) are disjoint. Let n be an integer such that n ≥ k + m and if x is a vertex of R 0 (S 2 ) with ν(x) = ∞, then the valence of x in R n (S 2 ) is greater than the valence of x in R 0 (S 2 ). Let M be a positive integer which is greater than the valence of every vertex of R 0 (S 2 ) and every vertex of Now let γ be a taut d 0 -geodesic in S 2 \ P f with level 0 and level n decompositions which are equal. We will show that γ has at most M level 0 segments.
In this paragraph, we show that γ is contained in the R m (S 2 )-open star of some level 0 vertex. Let α be an inner level n segment of γ. The endpoints of α lie in interiors of level n edges. Because n > m, the endpoints of α also lie in level m edges e 1 and e 2 . Because n ≥ k + m, the choice of k implies that e 1 and e 2 are consecutive edges of some level m tile and hence are not disjoint. Because e 1 and e 2 are contained in level 0 edges, e 1 ∩ e 2 is contained in a level 0 edge. Because γ is taut, it follows that e 1 ∩ e 2 contains a level 0 vertex x. Hence α is contained in the open R m (S 2 )-star of x. Since such open stars are disjoint, it follows that γ is contained in the open R m (S 2 )-star of x. Moreover, because γ is taut, it winds around x in the sense that its inner segments join consecutive level 0 edges which contain x without backtracking.
If ν(x) < ∞, then because γ is a d 0 -geodesic, a lift of γ to D cannot wind completely around the corresponding lift of x. Hence if ν(x) < ∞, then γ has at most M segments. If ν(x) = ∞, then γ cannot wind completely around x because its level n decomposition equals its level 0 decomposition but the valence of x in R n (S 2 ) is greater than the valence of x in R 0 (S 2 ). So again, γ has at most M segments.
Corollary 5.2. Every combinatorially expanding finite subdivision rule is contracting.
We will see in Theorem 6.7 that if R is a finite subdivision rule whose subdivision map is a Thurston map which is Thurston equivalent to a rational map, then R is contracting. So the finite subdivision rules of Examples 3.1 and 3.2 are both contracting because their subdivision maps are Thurston equivalent to rational maps. Neither of these finite subdivision rules is combinatorially expanding. The property of being combinatorially expanding is much stronger than the property of being contracting.

The contraction theorems
We prove two theorems in this section. The first one gives a strong form of the assertion that the contraction ratio of the orbifold fundamental group virtual endomorphism φ is at most 1 for every Thurston map which is the subdivision map of a finite subdivision rule R. The second theorem shows that φ is contracting if and only if R is contracting.
We maintain the notation and terminology from Sections 4 and 5. The following lemma prepares for the theorems. Statement 1 gives a fundamental inequality. It states that the map F is distance nonincreasing with respect to the pseudometric d 0 . The other statements provide information about the case in which equality is attained. Lemma 6.1. Let x, y ∈ D, and let n be a positive integer. Then we have the following.
(1) d 0 (F n (x), F n (y)) ≤ d 0 (x, y) (2) If d 0 (F n (x), F n (y)) = d 0 (x, y), then there exist points x ′ = x and y ′ = y in the open stars of x and y in R 0 (D * ), respectively, such that d 0 (F n (x ′ ), F n (y ′ )) = d 0 (x ′ , y ′ ). (3) If x and y are not vertices of R 0 (D * ) and d 0 (F n (x), F n (y)) = d 0 (x, y), then there exists a taut d 0 -geodesic in D joining F n (x) and F n (y) whose level 0 and level n decompositions are equal. (4) If x and y are not vertices of R 0 (D * ) and they are the endpoints of a lift via F n of a taut d 0 -geodesic joining F n (x) and F n (y) whose level 0 and level n decompositions are equal, then d 0 (F n (x), F n (y)) = d 0 (x, y).
Proof. The function F : D * → D * which lifts f −1 is a cellular map from R 0 (D * ) to R 1 (D * ). Similarly, F n is a cellular map from R 0 (D * ) to R n (D * ). Let γ be a d 0 geodesic arc joining x and y. Let t 0 , . . . , t m be the tiles of R 0 (D * ) which meet γ. So m = d 0 (x, y). We assume that γ contains no vertex of R 0 (D * ) other than possibly x and y, that γ meets each of t 0 , . . . , t m in an arc and that it intersects the 1-skeleton of R 0 (D * ) transversely. So γ is taut. We maintain these assumptions for the entire proof of Lemma 6.1.
Then F n (t 0 ), . . . , F n (t m ) are the tiles of R n (D * ) which meet F n (γ). Each of F n (t 0 ), . . . , F n (t m ) is contained in a unique tile of R 0 (D * ). This proves statement 1.
To prove statement 2, suppose that d 0 (F n (x), F n (y)) = d 0 (x, y). Let d = d 0 (x, y). Then d tiles of R 0 (D * ) meet γ. So at most d tiles of R n (D * ) meet F n (γ). So at most d tiles of R 0 (D * ) meet F n (γ). Now we use the assumption that d 0 (F n (x), F n (y)) = d 0 (x, y). This assumption implies that these inequalities are equalities. So the map from the set of tiles of R 0 (D * ) which contain γ to the set of tiles of R 0 (D * ) which contain R 0 (F n (γ)) is a bijection. Hence if x ′ and y ′ are any points of γ, then d 0 (F n (x ′ ), F n (y ′ )) = d 0 (x ′ , y ′ ). This proves statement 2.
In the situation of statement 3, the curve F n (γ) is a taut d 0 -geodesic joining F n (x) and F n (y) whose level 0 and level n decompositions are equal. This proves statement 3.
In the situation of statement 4, we have that d 0 (F n (x), F n (y)) = d n (F n (x), F n (y)) because F n (x) and F n (y) are joined by a taut d 0 -geodesic whose level 0 and level n decompositions are equal. Because x and y are joined by a lift of such a d 0 -geodesic, d 0 (x, y) ≤ d n (F n (x), F n (y)) = d 0 (F n (x), F n (y)). This inequality combined with statement 1 yields statement 4.
The next result shows that the virtual endomorphism on the orbifold fundamental group associated to a subdivision map of an fsr cannot expand word lengths very much. (2) a choice of orbifold fundamental group virtual endomorphism φ : G p G p associated to f ; (3) a finite generating set for the orbifold fundamental group G p with associated length function · such that φ n (g) ≤ a g + bn for every nonnegative integer n and g ∈ dom(φ n ). If the subdivision map takes some tile of level 1 to the tile of level 0 which contains it, then we may take b = 0. If there is only one tile of level 0, then we may take a = 1.
In a sequel to this work [14], we will use Theorem 6.2 to show that Thurston maps with certain properties are not combinatorially equivalent to subdivision maps of subdivision rules. For example, if f has a piece of its canonical decomposition on which the associated restriction is a pseudo-Anosov homeomorphism [22], then f cannot be equivalent to the subdivision map of an fsr.
Proof. The theorem is insensitive to Thurston equivalence, so we assume that f is the subdivision map of a finite subdivision rule R.
We return to the situation of Section 4 and the beginning of Section 5. We choose the basepoint p to be any point in the interior of a level 0 tile. The point q is a point of S 2 such that f (q) = p, and t is the tile of R −1 (S 2 ). Both p and q are in the interior of t. We choose a path β from p to q also in the interior of t. These choices of p, q and β determine φ. Now let γ be a loop at p representing g ∈ dom(φ). See Figure 7. Then φ(g) is the homotopy class of βf −1 (γ)[q]β −1 . Let γ be the lift of γ to D based at the lift p of p, and let σ ∈ Aut(π) be the element corresponding to g. Then the endpoints of γ are p and σ( p). Let β be the lift to D of β based at p, and let t be the lift of t which contains p. Then φ(g) equals the d −1 -distance between the endpoints of the following path. Traverse the path β in t, follow this by F ( γ) and follow this by the lift of β −1 based at F (σ( p)) in some open tile of R −1 (D * ).
We postpone consideration of this d −1 -distance to consider the corre- where b is twice the d 0 -length of β. Statement 1 of Lemma 6.1 with n = 1 implies that this d 0 -distance is at most d 0 ( p, σ( p)) + b. So we begin with p and a point at distance d 0 ( p, σ( p)) from it and we end with p and a point at distance at most d 0 ( p, σ( p)) + b from it. Now we iterate. Replacing φ by φ n for some nonnegative integer n, we end with p and a point at distance at most d 0 ( p, σ( p)) + bn from it. If a is the number of tiles in R 0 (S 2 ), then d 0 ( p, σ( p)) ≤ ad −1 ( p, σ( p)) = a g . Thus if g ∈ dom(φ n ) for some nonnegative integer n, then φ n (g) ≤ a g + bn.
This proves the first assertion of the theorem. Suppose that f maps some tile of R 1 (S 2 ) to the tile of R 0 (S 2 ) which contains it. Then we may choose p, q and β to be in this tile of R 0 (S 2 ). In this case b = 0. The rest of the theorem is now clear. Corollary 6.3. Let f : S 2 → S 2 be a Thurston map which is Thurston equivalent to the subdivision map of a finite subdivision rule. Then the contraction ratio of the associated orbifold fundamental group virtual endomorphism is at most 1.
In general, the term bn in Theorem 6.2 tends to ∞ as n → ∞. This is undesireable behavior. However, if f maps some tile of level 1 to the tile of level 0 which contains it, then we may take b = 0. The next result shows that this can be achieved by passing to an iterate of f . Proof. We construct a directed graph Γ. The vertices of Γ are the tiles of level 0. There exists a directed edge from tile t 1 to tile t 2 if and only if t 1 contains a tile s of level 1 such that f (s) = t 2 . The graph Γ has finitely many vertices and at least one directed edge emanating from every vertex. Hence it has a cycle, say of length n. If t is a tile in this cycle, then t contains a tile s of level n such that f n (s) = t. This proves Proposition 6.4.
Here is our second contraction theorem. Theorem 6.5. Let f : S 2 → S 2 be a Thurston map which is Thurston equivalent to the subdivision map of a finite subdivision rule R. Let ρ φ be the contraction ratio of the associated orbifold fundamental group virtual endomorphism φ. Then (1) ρ φ = 1 if R is not contracting; (2) ρ φ < 1 if R is contracting. Thus φ is contracting if and only if R is contracting.
Proof. The last sentence follows from statements 1 and 2 together with Proposition 2.11.11 from Nekrashevych's book [20], using the fact that φ is level transitive.
Like Theorem 6.2, this theorem is insensitive to Thurston equivalence, so we assume that f is the subdivision map of a finite subdivision rule R. We return to the setting of Section 4 and the beginning of Section 5.
Suppose that R is not contracting. Let n be a positive integer. Then for every positive integer M there exists a taut d 0 -geodesic γ in S 2 \ P f whose level 0 and level n decompositions are equal and γ has more than M segments.
In this paragraph we show that we may assume that γ is a closed curve. Let γ be a lift of γ to D. Let α be an inner segment of γ. So α joins two edges e 1 and e 2 of the tile t of R n (D * ) which contains α. We consider a homotopy of γ which changes only α and the segments of γ immediately preceding and following α. This homotopy moves α through a family of arcs in t which join e 1 and e 2 . This homotopy moves the segments immediately preceding and following α only near e 1 and e 2 . Projecting to S 2 , such a homotopy takes γ to another curve in S 2 \ P f whose level 0 and level n decompositions are equal with the same number of segments as γ. So up to such homotopies, γ is determined by the sequence of edges of R n (S 2 ) which it crosses. Since there are only finitely many such ordered pairs of edges and M is arbitrary, it follows that we may assume that γ is a closed curve. Since R n (S 2 ) contains only finitely many tiles, there is a tile t of R n (S 2 ) for which there are infinitely many values of M for which the corresponding curve γ meets t. Similarly, since f n (t) is a level 0 tile, there are infinitely many values of n such that f n (t) is a fixed level 0 tile s. Let p be a point in the interior of s. Now let n be one of the infinitely many positive integers such that p ∈ f n (t). Choose q ∈ t such that f n (q) = p. Because p is in the interior of s, it follows that q is in the interior of t. Since there are infinitely many choices for M , there exist infinitely many elements g ∈ G q with representative taut d 0 -geodesic loops whose level n and level 0 decompositions are equal. Now choose g ∈ G q with a representative taut d 0 -geodesic loop γ whose level n and level 0 decompositions are equal. Let η = f n (γ), a loop based at p. In other words, η is a loop in S 2 \ P f based at p and γ lifts η via f n . See Figure 9. Let γ be a lift of γ to D via π, and let η be a lift of γ to D via F n . Then η is a lift of η to D via π. Let q and q ′ be the initial and terminal endpoints of γ. Let p and p ′ be the initial and terminal endpoints of η.
Let h ∈ G p be the element represented by η. We recall the discussion of the iterates of φ in Section 4. We begin with a path β from p to a point in f −1 (p). To compute φ n , we take n − 1 lifts of β, obtaining a point in f −n (p). If that point is q, then h ∈ dom(φ n ). In general, that point is not q. Nonetheless, there exists a virtual endomorphism φ n : G p G p with h ∈ dom(φ n ) such that φ n equals φ n precomposed and postcomposed with conjugations. These conjugations and φ n depend only on n, not on h. So the estimates which we obtain for φ n will provide the needed estimates for φ n .
We seek a lower bound for h . Let a be the number of tiles in R 0 (S 2 ). Then where the equations use the fact that p and q are not in the 1-skeleton of R −1 (S 2 ) and the second inequality comes from statement 1 of Lemma 6.1. From this we conclude that h → ∞ as g → ∞.
The previous paragraph provides a lower bound for h . Now we obtain an upper bound as follows.
≤ ad −1 ( q, q ′ ) every level − 1 tile contains a level 0-tiles = a g definitions of · and d −1 Moreover, φ n (h) differs from g by at most an additive constant K (for a fixed n) which arises from the implicit path from p to q. Since there are infinitely many choices for g, the lengths g are unbounded. Hence the previous paragraph implies that the lengths h are unbounded. So when we consider all elements h ∈ dom(φ n ), we find that This is true for infinitely many positive integers n. So taking the limit supremum of nth roots, we find that ρ φ ≥ 1. This proves statement 1.
To prove statement 2, we assume that R is contracting. Statement 1 of Lemma 6.1 implies that F is distance nonincreasing. The following lemma shows that if R is contracting, then some iterate of F is uniformly strictly distance decreasing in the large. Lemma 6.6. If R is contracting, then there exist positive integers n and N and a real number c with 0 < c < 1 such that d 0 (F n (x), F n (y)) ≤ cd 0 (x, y) for every x, y ∈ D with d 0 (x, y) ≥ N .
Proof. Here is the only place in the proof of statement 2 that we use the fact that R is contracting. Because R is contracting, there exist positive integers M and n such that if γ is a taut d 0 -geodesic in S 2 \ P f whose level 0 and level n decompositions are equal, then γ has at most M segments. Let K be the largest valence of a vertex of R 0 (D * ) in D. Let N = M + 2K. This determines the integers n and N in the statement of the lemma.
Now let x, y ∈ D, and suppose that d 0 (F n (x), F n (y)) ≥ d 0 (x, y). We will prove that d 0 (x, y) < N .
We first reduce to the case in which neither x nor y is a vertex of R 0 (D * ). Statement 1 of Lemma 6.1 implies that d 0 (F n (x), F n (y)) = d 0 (x, y). Now statement 2 of Lemma 6.1 implies that there exist points x ′ and y ′ , which are not vertices of R 0 (D * ), in the open stars of x and y in R 0 (D * ) such that d 0 (F n (x ′ ), F n (y ′ )) = d 0 (x ′ , y ′ ). So to prove that d 0 (x, y) < N , it suffices to prove that d 0 (x ′ , y ′ ) < M .
But statement 3 of Lemma 6.1 implies that there exists a taut d 0 -geodesic joining F n (x ′ ) and F n (y ′ ) whose level 0 and level n decompositions are equal.
The assumption that R is contracting easily implies that this geodesic has at most M segments. Hence d 0 (x ′ , y ′ ) < M .
We have proved that if d 0 (x, y) = N , then d 0 (F n (x), F n (y)) < N . In general, we choose a d 0 -geodesic joining x and y. We decompose it into as many initial segments of length N as possible. We obtain this inequality for each such segment. Statement 1 of Lemma 6.1 applies to the remainder, and so if d 0 (x, y) ≥ N , then This proves Lemma 6.6 with c = 1 − 1 2N .
With Lemma 6.6 in hand, we proceed as follows. The definition of the contraction ratio ρ φ involves the limit supremum of fractions of the form φ m (g) / g for positive integers m. Write m = kn + l with n as in Lemma 6.6 and nonnegative integers k and l with 0 ≤ l < n. Then Using the definitions, Figure 7, statement 1 of Lemma 6.1 and the fact that there are only finitely many possibilities for l, one sees that the last of these three fractions is bounded for g ∈ dom(φ m ). It follows that to prove that ρ φ < 1, we may replace f by f n . So we have, as in Lemma 6.6, that We choose a basepoint p in the interior of some tile of R 0 (S 2 ). Let p be a lift of p to D. Instead of working with the virtual endomorphism of G p , we work with the equivalent virtual endomorphism of Aut(π).
Let m be a positive integer. Finally, set K = 2d 0 (F m ( p), p) and choose σ ∈ Aut(π) such that φ m (σ) ≥ N + K. Then we have the following, keeping in mind that when Lemma 6.6 is applied, the choice of σ implies that the right side of the inequality is at least N + K.
contains a level 0 tiles = ac m σ + K definitions of · and d −1 Taking the limit supremum of m-th roots, we conclude that ρ φ < 1. This proves Theorem 6.5.
Theorem 6.7. Let R be a finite subdivision rule whose subdivision map f is a Thurston map which is Thurston equivalent to a map g with the following property. As for f , let P ∞ g denote the set of orbifold points for g with orbifold weight infinity. There is a neighborhood U of P ∞ g and a complete length metric on K := S 2 − U such that g −1 (K) ⊂ K and inverse branches of g uniformly decrease lengths of curves. Then R is contracting.
In particular, if f is equivalent to a rational map, then R is contracting.
Proof. Theorem 6.4.4 of Nekrashevych's book [20] implies that the orbifold fundamental group virtual endomorphism of f is contracting. Thus R is contracting by Theorem 6.5.

The fat path subdivision graph
In this section we assume that f : S 2 → S 2 is a Thurston map which is the subdivision map of a finite subdivision rule R. We will define the fat path subdivision graph of R. We will give a condition on R which is equivalent to the condition that this graph is Gromov hyperbolic. We will also describe the Gromov boundary of this graph when it is hyperbolic.
As in Section 5, we have cell complexes R −1 (S 2 ), R 0 (S 2 ), R 1 (S 2 ), . . .. The fat path subdivision graph of R is defined as follows. It is a graph Γ with a vertex v(t) for every tile t of R n (S 2 ) for integers n ≥ −1. We say that the vertex v(t) represents the tile t. Let t be a tile of R n (S 2 ) for some integer n ≥ −1. Then v(t) is joined by an edge of Γ to v(s) for every subtile s of t in R n+1 (S 2 ). These edges are said to be vertical. The vertex v(t) is also joined by an edge of Γ to v(s) for every tile s = t of R n (S 2 ) which has an edge in common with t. These edges are said to be horizontal. The skinny path subdivision graph of R is defined in the same way except that if s = t are tiles of R n (S 2 ), then v(s) and v(t) are joined by an edge if and only if s ∩ t = ∅. Thus the only difference between these graphs is that in general the fat path subdivision graph has fewer horizontal edges than the skinny path subdivision graph. These graphs are given metrics in the straightforward way so that every edge has length 1.
For every integer n ≥ −1, let Γ n be the subgraph of Γ spanned by all vertices of the form v(t), where t is a tile of R n (S 2 ). Let δ n be the path metric on Γ n . Because Γ n might not be connected, δ n might take the value ∞. Following Rushton [23], we define a transition function f m,n : Γ n → Γ m for all integers m, n ≥ −1 such that m ≤ n. Let t be a tile of R n (S 2 ). Then f (v(t)) = v(s), where s is the tile of R m (S 2 ) which contains t. We extend f m,n to the edges of Γ n in the straightforward way, so that f m,n is a cellular map.
These graphs are called history graphs on page 100 of [10], where they were briefly introduced. We feel that the terminology finite subdivision graph is a bit more descriptive and it distinguishes our graphs from those studied by Rushton in [23]. Rushton's graphs depend not only on R but also a choice of R-subdivision complex X and ideal cells (more about these later). For us X is the 2-sphere S 2 . Our skinny path subdivision graph is essentially Rushton's history graph for X = S 2 and no ideal cells.
We wish to apply two of Rushton's results, Theorems 5 and 6 of [23]. The former gives necessary and sufficient conditions for hyperbolicity of a graph. The latter shows that the boundary is homeomorphic to a certain quotient. However, Rushton's results do not apply directly to the fat path subdivision graph Γ because Rushton in effect works with skinny path subdivision graphs. These subdivision graphs are quasi-isometric if R has bounded valence, but they are not quasi-isometric if R does not have bounded valence. To obviate this difficulty, we introduce a new finite subdivision rule R which is gotten from R by introducing "ideal tiles" at vertices of R 0 (S 2 ) whose valences are unbounded under subdivision. We will see that Rushton's skinny path subdivision graph for R with these ideal tiles is quasi-isometric to Γ, so Rushton's results applied to R describe Γ.
In this paragraph we define the finite subdivision rule R. For this, let v be a vertex of R 0 (S 2 ) whose valences are unbounded under subdivision. We call such vertices ideal vertices of R 0 (S 2 ). The space S 2 \{v} is homeomorphic to Figure 10. On the left are R 0 (S 2 ) and R 1 (S 2 ) near v and on the right are R 0 (S 2 ) and R 1 (S 2 ) near v, a vertex of R 0 (S 2 ) whose valences are unbounded under subdivision S 2 \D, where D is a small closed topological disk containing v in its interior. Using such a homeomorphism, the cell structure of R 0 (S 2 ) together with the boundary ∂D of D determine a cell structure on the closure of S 2 \ D. The induced cell structure on ∂D together with v determine a cell structure on D by joining every vertex of ∂D to v with an edge. We do this for every ideal vertex v of R 0 (S 2 ), in effect replacing v by a closed disk subdivided into n sectors, where n is the valence of v in R 0 (S 2 ). One verifies that this determines a new finite subdivision rule R. See Figure 10. We view R n (S 2 ) as a subcomplex of R n (S 2 ) for every nonnegative integer n. Let f : S 2 → S 2 be the subdivision map of R.
Now we describe Rushton's history graph Γ( R, S 2 ). It has a base vertex corresponding to the vertex of Γ −1 . It also has one vertex for every closed cell c of R n (S 2 ) such that f n (c) does not contain an ideal vertex of R 0 (S 2 ). A horizontal edge joins vertices representing distinct cells of R n (S 2 ) if and only if one cell is contained in the other. Containment also determines vertical edges just as for Γ. Thus there is a canonical map from the set of vertices of Γ to the set of vertices of Γ( R, S 2 ). It is easy to see that this map extends to edges, yielding a quasi-isometry.
To emphasize the similarity between the condition in Theorem 7.1 and the condition of being contracting, we restate the condition in Theorem 7.1 as follows. In our usual situation, we say that a curve γ in S 2 \ P f is a δ mgeodesic for some nonnegative integer m if the tiles of R m (S 2 ) which meet γ are exactly the tiles represented by the vertices of a δ m -geodesic in Γ m . The condition of Theorem 7.1 can be restated as follows. There exist positive integers M and n with the following property. If γ is a taut δ m -geodesic for some nonnegative integer m with level m and level m + n decompositions which are equal, then the number of level m segments in γ is at most M . We say that R is graph hyperbolic if it satisfies this condition. The only difference between R being contracting and R being graph hyperbolic is that the former definition deals with d 0 -geodesics and the latter definition deals with δ m -geodesics.
We next make a definition to prepare for the next theorem. Let R be a finite subdivision rule whose subdivision map is a Thurston map. Let X be the topological space gotten by deleting from S 2 the open star of every vertex of R n (S 2 ) whose valences are unbounded under subdivision for every nonnegative integer n. Now define a relation ∼ on X as follows. Let x, y ∈ X. Let s n and t n be tiles of R n (S 2 ) which contain x and y, respectively, for every nonnegative integer n. Let v n (x) and v n (y) be the vertices of Γ n representing s n and t n , respectively. Then x ∼ y if and only if the distances δ n (v n (x), v n (y)) are bounded as n varies over the nonnegative integers. The relation ∼ is an equivalence relation.
Theorem 7.2. Let R be a graph hyperbolic finite subdivision rule whose subdivision map is a Thurston map. Then the boundary of Γ is homeomorphic to the space X defined immediately above modulo the relation ∼.
The following lemma gives a slightly different interpretation of the equivalence relation ∼. Lemma 7.3. The equivalence relation ∼ is generated by the relation ≈ defined as follows. Let x, y ∈ X. Then x ≈ y if and only if for every nonnegative integer n there exists a tile of R n (S 2 ) which contains both x and y.
Proof. This is an exercise in point set topology.
Let R be a graph hyperbolic finite subdivision rule whose subdivision map is a Thurston map. Theorem 7.2 and Lemma 7.3 imply that the boundary of the fat path subdivision graph of R can be constructed in two steps. In the first step, we delete from S 2 an open topological disk about every vertex of R n (S 2 ) whose valences are unbounded under subdivision for every nonnegative integer n. In the second step, we identify two points of this space if (but not only if) some tile of R n (S 2 ) contains both of them for every nonnegative integer n. The first step is trivial if and only if R has bounded valence. The second step is trivial if and only if the mesh of R approaches 0.
Using Theorem 7.1, we next prove that if R is contracting, then R is graph hyperbolic.
Theorem 7.4. Let R be a finite subdivision rule whose subdivision map f is a Thurston map. If R is contracting, then it is graph hyperbolic and hence its fat path subdivision graph is Gromov hyperbolic.
Proof. Theorem 7.1 implies that it suffices to prove that R is graph hyperbolic. Let Γ be the fat path subdivision graph of R.
Because R is contracting, there exist positive integers M and n such that the following condition is satisfied. If γ is a taut d 0 -geodesic in S 2 \ P f with level 0 and level n decompositions which are equal, then the number of level 0 segments in γ is at most M . Now we begin to verify the condition of Theorem 7.1 for these values of M and n. Let u and v be vertices of Γ m for some nonnegative integer m such that δ m (u, v) ≥ M . Set N = δ m (u, v). Let u ′ and v ′ be vertices of Γ m+n such that f m,m+n (u ′ ) = u and f m,m+n (v ′ ) = v. The vertices u and v represent tiles s and t of level m, and u ′ and v ′ represent tiles s ′ and t ′ of level m + n with s ′ ⊆ s and t ′ ⊆ t. Let p and q be points in the interiors of s ′ and t ′ , respectively. Because δ m (u, v) = N , there exists a taut arc α in S 2 \ P f joining p and q with a level m decomposition containing N + 1 segments.
Let α be a curve in D which lifts α via π • F m : D → S 2 . Let p and q be the endpoints of α. Because N + 1 tiles of R m (S 2 ) cover α, it follows that N + 1 tiles of R 0 (D * ) cover α. So d 0 ( p, q) ≤ N . This inequality cannot be strict because otherwise there exists a curve in R 0 (D * ) joining p and q covered by at most N tiles of R 0 (D * ). This curve maps by π •F m to a curve in R m (S 2 ) joining p and q. It would follow that δ m (u, v) < N , which is not true. Hence d 0 ( p, q) = N and α is a taut d 0 -geodesic.
Let γ = π( α). Then γ is a taut d 0 -geodesic in S 2 \P f whose level 0 decomposition has N + 1 segments. Because N ≥ M , the contraction condition which R satisfies implies that the level n decomposition of γ does not equal the level 0 decomposition of γ. In other words, the level n decomposition of γ has more than N + 1 segments. In turn, the level m + n decomposition of α has more than N + 1 segments. This implies that p and q cannot be joined by a curve whose level m + n decomposition has at most N + 1 segments.
See the discussion after Theorem 9.1 for examples which show that it is possible for a finite subdivision rule to be graph hyperbolic without being contracting. Figure 11. A finite subdivision rule which is not graph hyperbolic Example 7.5. In practice, finite subdivision rules which one encounters whose subdivision maps are Thurston maps are almost all graph hyperbolic.
Here is an example of a Thurston map f which is the subdivision map of a finite subdivision rule R which is not graph hyperbolic. The 1-skeleton of R 0 (S 2 ) is a simple closed curve decomposed into four edges a, b, c, d. So R 0 (S 2 ) has two tiles, t 1 and t 2 . The subdivisions of t 1 and t 2 , which are reflections of each other, are shown in Figure 11.
In this paragraph we define a sequence α 1 , α 2 , α 3 , . . . of arcs in t 1 . Two edges which f maps to edge a in the subdivision of t 1 are drawn with thick line segments. Let α 1 be the arc which is the union of these two thick edges in t 1 . We inductively see that for every positive integer n there exists an arc α n joining the top and bottom of t 1 consisting of 2 n edges of R n (t 1 ). Each of these 2 n edges maps to edge a under f n . Each of these arcs is to the right of the previous one. The open star S n of α n in R n (t 1 ) is combinatorially a rectangle tiled by 2 n rows and 2 columns of squares.
The fat path distance between the endpoints of α n in S n is 2 n + 1. However, a fat path geodesic joining the endpoints of α n in R n (t 1 ) might leave S n , and the fat path distance in R n (t 1 ) between these points might be less than 2 n + 1. So let m be a nonnegative integer, and consider R m (S n ). Using the fact that the tiles in both R(t 1 ) and R(t 2 ) can be organized into three columns, we see that the tiles of R m (S n ) can be organized into 2·3 m columns. A fat path in R n+m (t 1 ) starting at an endpoint of α n must traverse at least 3 m tiles to leave R m (S n ). It follows that if m is large enough, then the fat path distance between the endpoints of α n in R n+m (t 1 ) is exactly 2 n + 1. The same holds for R n+m (t 2 ). So the fat path distance between these points in R n+m (S 2 ) is independent of m and greater than 2 n if m is large enough.
Thus R is not graph hyperbolic, since the fat path subdivision graph will contain arbitrarily large embedded geodesic square grids.

Remarks:
(1) Example 7.5 may be generalized by thinking of it as a local obstruction. If the fsr R of this example is a sub-fsr of another fsr R ′ , then the same argument shows that the subdivision complex for R ′ will not be hyperbolic either. (2) The vertical curve joining sides b, d of Example 7.5 forms a Thurston obstruction whose corresponding eigenvalue is 1 + 1/2 + 1/2 = 2.
Obstructions to hyperbolicity are not detectable just by looking at such eigenvalues. The map (x, y) → (2x, y) descends to an affine map which is the subdivision map of a subdivision rule R ′ whose tiles are images of the usual integral unit squares under the natural projection. This map also has a Thurston obstruction with eigenvalue 2. However, R ′ is contracting and the fat path subdivision complex is hyperbolic.

The selfsimilarity complex
This section is devoted to relating the fat path subdivision graph Γ of R with a selfsimilarity complex Σ of f . We recall the definition of Σ.
As in Section 4, we choose a basepoint p ∈ S 2 \ P f . Let A, which we view as an alphabet, be a finite set with the same cardinality as f −1 (p). For every nonnegative integer n, let A n be the set of words of length n in A, We next define a bijection Λ : A * → ∪ n (f −n (p) × {n}) so that Λ(A n ) = f −n (p) × {n} for every nonnegative integer n. The action of Λ on A 0 is forced. Define Λ on A = A 1 to be any bijection to f −1 (p) × {1}. For each x ∈ A, let λ x be an arc in S 2 \ P f from p to the first component of Λ(x). Now let n be a positive integer for which Λ is defined on A n . Let x ∈ A and w ∈ A n . Then Λ(xw) = (q, n + 1) ∈ f −(n+1) (p) × {n + 1}, where q is the terminal endpoint of the f n -lift of λ x whose initial endpoint is Λ(w). This defines Λ.
Let G p be the orbifold fundamental group of f as in Section 4. Let g ∈ G p , and let w ∈ A n for some nonnegative integer n. We define g.w as follows. We choose a loop γ in S 2 \ P f at p representing g. Then g.w is the element of A n such that the first component of Λ(g.w) is the terminal endpoint of the f n -lift of γ whose initial endpoint is the first component of Λ(w). Let S be a generating set for G p . Now we define the selfsimilarity complex Σ. It is a graph whose vertex set is A * . Given w ∈ A * , a horizontal edge joins w and s.w for every s ∈ S. If we have x ∈ A in addition to w ∈ A * , then a vertical edge joins w and xw. We define a metric on Σ in the straightforward way so that every edge has length 1. This defines Σ. Different choices of p, S and arcs λ x obtain Figure 12. The basepoint p in the tile t of R −1 (S 2 ), the tilings of S 2 which pullback t under f and f 2 and a portion of the selfsimilarity complex Σ quasi-isometric graphs. Let Σ n denote the subgraph of Σ spanned by A n for every nonnegative integer n.
We discuss Figure 12 in this paragraph. We prefer to work with special choices for p and S. Let t be the tile of R −1 (S 2 ) as in Section 5. Let p be a point in the interior of t, and let S be the generating set of G p determined by t as in Section 5. Figure 12 gives a schematic diagram of a portion of the resulting selfsimilarity complex Σ. The tile t is represented by a parallelogram at the bottom, disregarding identification of edges. The arcs λ x are not drawn. In Figure 12, the map f has degree 4 and t lifts to four parallelograms. The tilings of S 2 obtained by pulling back t under f and f 2 need not be subdivisions of t. These tilings are drawn with gray line segments, and the edges of Σ are drawn with black line segments. A prominent property of Σ illustrated by Figure 12 is that edges of Σ n correspond exactly to pairs of lifts of t via f n which have an edge in common. So Σ n is the graph dual to the 1-skeleton of f −n (t) for every integer n.
Here is our result which relates selfsimilarity complexes and subdivision graphs.
Theorem 8.1. Let R be a finite subdivision rule whose subdivision map f is a Thurston map. Then every selfsimilarity complex of f is quasi-isometric to the fat path subdivision graph of R.
Proof. We define a selfsimilarity complex Σ of f as above with the following choices. Let t be the tile of R −1 (S 2 ). Let p be a point of S 2 not in the 1-skeleton of R 0 (S 2 ). Hence p is in the interior of t. Let S be the generating set of G p determined by t. Because p is not in the 1-skeleton of R 0 (S 2 ), neither are the elements of f −1 (p). So we may choose arcs λ x to lie in the interior of t. To prove the theorem, it suffices to prove that the fat path subdivision graph Γ of R is quasi-isometric to Σ. In turn, it suffices to prove that the set V * (Γ) of vertices of ∞ n=0 Γ n is quasi-isometric to the set V (Σ) of vertices of Σ.
The vertex set V (Σ) of Σ comes with a bijection from it to ∞ n=0 (f −n (p)× {n}). Every element of f −n (p) is contained in a unique lift of t via f n for every nonnegative integer n. Thus for every element v ∈ V (Σ), we have a tile τ (v), which is a lift of t via f n for some nonnegative integer n. Similarly, for every v ∈ V * (Γ), there exists a tile τ (v) in some subdivision of R 0 (S 2 ).
Let d Γ and d Σ be the metrics on Γ and Σ, respectively. Let K be the number of tiles in R 0 (S 2 ), and let L be the number of tiles in R 1 (S 2 ).
We define a map ϕ : V * (Γ) → V (Σ) as follows. Let v ∈ V * (Γ). Let s = τ (v), a tile of R n (S 2 ) for some nonnegative integer n. The interior of the tile f n (s) of R 0 (S 2 ) is contained in the interior of t. Hence s is contained in some lift t of t via f n . There exists a unique vertex w ∈ Σ n such that τ (w) = t. We set ϕ(v) = w. This defines ϕ.
Now we begin to verify that ϕ is a quasi-isometry. Let v 1 , v 2 ∈ V * (Γ) be the endpoints of a horizontal edge of Γ. Then s 1 = τ (v 1 ) and s 2 = τ (v 2 ) are tiles of R n (S 2 ) for some nonnegative integer n. There exist lifts t 1 and t 2 of t via f n such that s 1 ⊆ t 1 and s 1 ⊆ t 2 . Because v 1 and v 2 are the endpoints of a horizontal edge, s 1 ∩ s 2 contains an edge of R n (S 2 ). So t 1 ∩ t 2 contains an edge of f −n (t). Thus the vertices ϕ(v 1 ) and ϕ(v 2 ) of Σ, where τ (ϕ(v 1 )) = t 1 and τ (ϕ(v 2 )) = t 2 , are either equal or they are the endpoints of an edge. This proves that if v 1 and v 2 are the endpoints of a horizontal edge of Γ, then d Σ (ϕ(v 1 ), ϕ(v 2 )) ≤ 1.
Next suppose that v 1 , v 2 ∈ V * (Γ) are the endpoints of a vertical edge of Γ. Then after interchanging v 1 and v 2 if necessary, we have that s 1 = τ (v 1 ) is a tile of R n−1 (S 2 ) and s 2 = τ (v 2 ) is a tile of R n (S 2 ) for some positive integer n. Moreover, s 2 ⊆ s 1 . Also, t 1 = τ (ϕ(v 1 )) is the lift of t via f n−1 such that s 1 ⊆ t 1 and t 2 = τ (ϕ(v 2 )) is the lift of t via f n such that s 2 ⊆ t 2 . Set Figure 13. Now choose any arc λ x in the definition of Σ, and let λ x be the lift of λ x to t 1 via f n−1 . Let s 3 be a tile of R n (S 2 ) which contains the terminal endpoint of λ x . Let t 3 be the lift of t via f n such that s 3 ⊆ t 3 . Because t contains L tiles of R 1 (S 2 ), the tile t 1 contains L tiles of R n (S 2 ). Each of these tiles is contained in a unique lift of t via f n . Hence t 1 is covered by at most L lifts of t via f n . Since s 2 ⊆ s 1 ⊆ t 1 , s 2 ⊆ t 2 , s 3 ⊆ t 1 and s 3 ⊆ t 3 , the vertices w 3 and w 2 of Σ n such that τ (w 3 ) = t 3 and τ (w 2 ) = t 2 are connected by a horizontal edge path which contains at most L vertices. The vertices w 1 and w 3 , where τ (w 1 ) = t 1 , are the endpoints of a vertical edge of Σ. So We have proved that if v 1 , v 2 ∈ V * (Γ) are the endpoints of an edge, then . This is one half of what is needed to prove that ϕ is a quasi-isometry.
To begin the other half of the proof, let v 1 ∈ V (Σ). We consider the set ϕ −1 (v 1 ). The tile t 1 = τ (v 1 ) is a lift of t via f n for some nonnegative integer n. By definition, ϕ −1 (v 1 ) consists of all vertices v of Γ n such that τ (v) is a tile of R n (S 2 ) which is contained in t 1 . In particular, ϕ is surjective. Moreover, the d Γ -distance between such vertices of Γ n is at most K.
Now let v 1 , v 2 ∈ V * (Γ) such that ϕ(v 1 ) and ϕ(v 2 ) are the endpoints of a horizontal edge of Σ. Let n be the nonnegative integer and let t 1 and t 2 be the lifts of t via f n such that t 1 = τ (ϕ(v 1 )) and t 2 = τ (ϕ(v 2 )). Then s 1 = τ (v 1 ) and s 2 = τ (v 2 ) are tiles of R n (S 2 ) such that s 1 ⊆ t 1 and s 2 ⊆ t 2 . Because ϕ(v 1 ) and ϕ(v 2 ) are the endpoints of a horizontal edge, t 1 ∩ t 2 contains an edge of f −n (t). It easily follows that d Γ (v 1 , v 2 ) ≤ 2K ≤ K + L.
Finally, let v 1 , v 2 ∈ V * (Γ) such that ϕ(v 1 ) and ϕ(v 2 ) are the endpoints of a vertical edge of Σ. Then after interchanging v 1 and v 2 if necessary, we have that s 1 = τ (v 1 ) is a tile of R n−1 (S 2 ) and s 2 = τ (v 2 ) is a tile of R n (S 2 ) for some positive integer n. Let t 1 = τ (ϕ(v 1 )) and t 2 = τ (ϕ(v 2 )). Then s 1 ⊆ t 1 and s 2 ⊆ t 2 . See Figure 14. Because ϕ(v 1 ) and ϕ(v 2 ) are the endpoints of a vertical edge of Σ, there exists an arc λ x whose lift λ x to t 1 via f n−1 has an endpoint in t 2 . Let s 3 be a tile of R n (S 2 ) which contains this endpoint of λ x , and let v 3 be the vertex of Γ n such that τ (v 3 ) = s 3 . Let s 4 be a tile of R n (S 2 ) contained in s 1 , and let v 4 be the vertex of Γ n such that τ (v 4 ) = s 4 . Then v 1 and v 4 are the vertices of a vertical edge of Γ, and so d Γ (v 1 , v 4 ) = 1. Since s 4 ⊆ t 1 and s 3 ⊆ t 1 , as in the argument which involves Figure 13, we have that d Γ (v 4 , v 3 ) < L. Since s 3 ⊆ t 2 and s 2 ⊆ t 2 , we have that d Γ (v 3 , v 2 ) < K. So the triangle inequality implies that Combining the last three paragraphs with the triangle inequality shows that if u, v ∈ V * (Γ), then d Γ (u, v) ≤ (K + L)d Σ (ϕ(u), ϕ(v)) + K. This completes the proof of Theorem 8.1.
Theorem 8.2. Suppose that f is a rational map which is the subdivision map of a finite subdivision rule R. Then R is graph hyperbolic, and the Proof. Theorem 6.7 implies that R is contracting. So Theorem 7.4 implies that R is graph hyperbolic. Theorem 8.1 implies that the fat path subdivision graph of R is quasi-isometric to the selfsimilarity complex Σ of f . Finally, Theorem 6.4.4 of Nekrashevych's book [20] implies that the boundary of Σ is homeomorphic to the Julia set of f . Example 8.3. In this example we construct a Thurston map which is not rational such that its orbifold fundamental group virtual endomorphism is contracting and the boundary of its selfsimilarity complex is a Sierpinski carpet. We begin with a general discussion.
Let R be a combinatorially expanding finite subdivision rule whose subdivision map f is a Thurston map. Statement 3 of Theorem 3.4 shows that R is weakly isomorphic to a finite subdivision rule whose mesh approaches 0. Replacing R by a weakly isomorphic finite subdivision rule does not change the isometry type of it fat path subdivision graph Γ or the homeomorphism type of ∂Γ. So we assume that the mesh of R approaches 0. Corollary 5.2 implies that R is contracting. This and Theorem 7.4 imply that Γ is Gromov hyperbolic. The discussion after Lemma 7.3 describes ∂Γ. So ∂Γ is a subspace of S 2 gotten by deleting an open topological disk about every vertex of R n (S 2 ) whose valences are unbounded under subdivision for every nonnegative integer n. Finally, Theorem 8.1 shows that the selfsimilarity complex Σ of f is quasi-isometric to Γ. So the above describes ∂Σ.
We are interested in the case in which R does not have bounded valence. The assumption of unbounded valence and the fact that the mesh of R approaches 0 imply that ∂Γ and, hence ∂Σ, is the complement in S 2 of the union of infinitely many disjoint open topological disks. Because the mesh of R approaches 0, the diameters of these open disks tend to 0. By a theorem of Whyburn [27], any two such spaces are ambiently homeomorphic by an orientation-preserving homeomorphism of S 2 . This means that ∂Σ is a Sierpinski carpet.
Now we construct such a finite subdivision rule R and Thurston map f . Figure 15 describes R. The 1-skeleton of R 0 (S 2 ) is a simple closed curve subdivided into four edges a, b, c, d. Hence R 0 (S 2 ) has two quadrilateral tiles, t 1 and t 2 . One verifies that Figure 15 does indeed describe a finite subdivision rule. It is easy to see that R is combinatorially expanding. So Corollary 5.2 and Theorem 6.5 imply that the orbifold fundamental group virtual endomorphism of f is contracting. The four vertices of R 0 (S 2 ) form the postcritical set of f , and they all map to the vertex in the lower left corner of t 1 . Moreover, this vertex is a critical point of f . So its valences are unbounded under subdivision. It follows that the orbifold of f is hyperbolic. A simple closed curve in S 2 \ P f which is vertical relative to the drawing of t 1 and t 2 in Figure 15 is a Thurston obstruction. So f is not rational.
In conclusion, f is a Thurston map which is not equivalent to a rational map, its orbifold fundamental group virtual endomorphism is contracting and the boundary of its selfsimilarity complex is a Sierpinski carpet.

Levy obstructions
A Levy cycle for a Thurston map f is a multicurve {γ 1 , . . . , γ k } such that for each i ∈ {1, . . . , k} γ i is homotopic rel P f to a component of f −1 (γ i+1 ) (where the subscripts are modulo k) which maps to γ i+1 with degree one. In [17], Levy proves that if a Thurston map has degree two and has a Thurston obstruction, then it has a Levy cycle. In [1], Bielefeld, Fisher, and Hubbard prove that if a topological polynomial has a Thurston obstruction, then the Thurston obstruction contains a Levy cycle. If a Thurston map f has a Levy cycle, then its fundamental group virtual endomorphism φ is not contracting.
One can generalize the definition of a Levy cycle as follows and still get an obstruction to the contraction of φ. A Levy obstruction for a Thurston map f is an essential, nonperipheral, simple closed curve γ in S 2 \ P f for which there exists a positive integer n such that there is a degree 1 lift of γ via f n to a simple closed curve which is homotopic to γ rel P f . Note that every element of a Levy cycle is a Levy obstruction.
The following theorem motivates our interest in Levy obstructions.
Theorem 9.1. Let f : S 2 → S 2 be a Thurston map with orbifold fundamental group virtual endomorphism φ. If f admits a Levy obstruction, then φ is not contracting.
Proof. Suppose that f admits a Levy obstruction. Then there exists a simple closed curve γ in S 2 \ P f such that γ is neither inessential nor peripheral and there exists a positive integer n such that there is a degree 1 lift of γ via f n to a simple closed curve δ which is homotopic to γ rel P f . To prove that φ is not contracting, it suffices to prove that the orbifold fundamental group virtual endomorphism of f n is not contracting. This is what we do.
In effect, we replace f by f n , so that f (δ) = γ. We choose p ∈ γ, q ∈ δ with f (q) = p and a path β from p to q, the data used to define φ. Let X be the universal covering space of S 2 \ P f . We lift to X. Let p be a lift of p. Let γ and β be lifts of γ and β to paths based at p. Then β ends at a point q which lifts q. Let δ be a lift of δ based at q.
A homotopy H : [0, 1] × [0, 1] → S 2 \ P f from δ to γ also lifts to a homotopy H from δ to γ. The homotopy H takes δ to γ through a family of closed curves. If α is a lift of such a closed curve α, then there exists a deck transformation which takes the initial endpoint of α to its terminal endpoint. Because the universal covering map is a local homeomorphism, these deck transformations are equal for sufficiently close curves. This and a compactness argument imply that there exists a deck transformation σ such that σ( p) is the terminal endpoint of γ and σ( q) is the terminal endpoint of δ. So σ • β is a lift of β from the terminal endpoint of γ to the terminal endpoint of δ. So β δ(σ • β) −1 γ −1 lifts βδβ −1 γ −1 and shows that βδβ −1 γ −1 is homotopic to the constant path at p in S 2 \ P f .
Hence if g ∈ G p is the element represented by γ, then g ∈ dom(φ) and φ(g) = g. So g ∈ dom(φ n ) and φ n (g) = g for every positive integer n. Since γ is neither inessential nor peripheral, g has infinite order in G p . So the lengths of the powers of g become arbitrarily large relative to any finite generating set of G p . Since they are all fixed by all powers of φ n , it follows that φ is not contracting.
Consider the finite subdivision rule R 3 of Example 3.3. It was observed there that a horizontal curve gives a Thurston obstruction. This Thurston obstruction is even a Levy obstruction. So Theorems 6.5 and 9.1 imply that R 3 is not contracting. On the other hand, it is not hard to verify that R 3 is graph hyperbolic. In particular, if a curve in S 2 \ P f is a taut δ m -geodesic for some nonnegative integer m with more than 4 segments, then it cannot have equal level m and level m + 1 decompositions. Figure 16. A finite subdivision rule which is graph hyperbolic but not contracting.
A simpler example is shown in Figure 16. In this case a vertical curve gives a Levy obstruction. Now suppose that R is a finite subdivision rule whose subdivision map is a Thurston map. In practice it is easy to check whether R is contracting or graph hyperbolic if only because the finite subdivision rules one encounters in practice are so simple. However, the existence and effectiveness of general algorithms is as yet unclear.
For general Thurston maps f , systematic enumeration of curves will detect a Levy obstruction, if one exists. Also, systematic enumeration of candidate nuclei for associated wreath recursions will detect if φ f is contracting [20]. But as of this writing, we do not know if absence of Levy obstructions (and still assuming the map is not one of the exceptional Lattès examples) is sufficient to prove φ f is contracting. In the present context of subdivision maps of finite subdivision rules, we may ask similar questions.
(1) Is there an effective algorithm which begins with a finite subdivision rule R associated to a Thurston map and determines whether or not it is contracting? (2) Is there an effective algorithm which begins with a finite subdivision rule R associated to a Thurston map and determines whether or not it is graph hyperbolic? (3) Is there a Levy obstruction if R is not contracting? (4) Is there a Levy obstruction if R is not graph hyperbolic?