{'fraction_non_alphanumeric': 0.07183519678912233, 'fraction_numerical': 0.01980860329551815, 'mean_word_length': 3.1240851255489246, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 52, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The co-Hopfian property of surface braid groups

Let g and n be integers at least two, and let G be the pure braid group with n strands on a closed orientable surface of genus g. We describe any injective homomorphism from a finite index subgroup of G into G. As a consequence, we show that any finite index subgroup of G is co-Hopfian.

into itself. We also showed the natural isomorphism between Mod * (S) and the automorphism group of CP(S). The present paper is thus devoted to showing that any superinjective map from CP(S) into itself is surjective. The following theorem is a consequence of these results. Theorem 1.1. Let S be a connected, compact and orientable surface such that both the genus and the number of boundary components of S are at least two. Then any superinjective map from CP(S) into itself is induced by an element of Mod * (S).
As a by-product of the proof of this theorem, in Corollary 8.15, we also prove that any superinjective map from the subcomplex CP n (S) of CP(S), called the complex of HBCs and non-separating HBPs for S, into CP(S) is induced by an element of Mod * (S). Combining the above theorem with Theorem 7.13 (i) in [22] and applying argument in Section 3 of [17], we obtain the following: Corollary 1.2. Let S be the surface in Theorem 1.1. Then for any finite index subgroup Γ of P (S) and any injective homomorphism f : Γ → P (S), there exists a unique element γ ∈ Mod * (S) with f (x) = γxγ −1 for any x ∈ Γ. In particular, Γ is co-Hopfian.
Parallel results are proved for the subgroup P s (S) of P (S) and the subcomplex CP s (S) of CP(S), called the complex of HBCs and separating HBPs for S, that are precisely defined in Section 2.2. Let us summarize the results on them.  This corollary is obtained by combining the last theorem with Theorem 7.13 (ii) in [22]. If the genus of a surface S is equal to zero, then we have the equalities P (S) = P s (S) = PMod(S) and CP(S) = CP s (S) = C(S). If the genus of S is equal to one, then we have the equalities P (S) = I(S) and P s (S) = K(S), where I(S) is the Torelli group for S and K(S) is the Johnson kernel for S. Moreover, CP(S) and CP s (S) are equal to the Torelli complex for S and the complex of separating curves for S, respectively. We refer to [19] for a definition of these groups and complexes. It therefore follows from [3] and [20] that if S is a surface with the genus less than two and the Euler characteristic less than −2, then the same conclusions for S as in the above theorems hold. The co-Hopfian property of the braid groups on the disk, which are central extensions of the mapping class groups of holed spheres, is discussed in [2] and [4].
For a positive integer n and a manifold M , we define B n (M ) as the braid group of n strands on M , i.e., the fundamental group of the space of non-ordered distinct n points in M . We also define P B n (M ) as the pure braid group of n strands on M , i.e., the fundamental group of the space of ordered distinct n points in M . The group P B n (M ) is naturally identified with a subgroup of B n (M ) of index n!. If S is a surface of genus at least two with p boundary components, then the kernel of the homomorphism from Mod(S) onto Mod(S) associated with the inclusion of S intoS is identified with B p (S) (see Theorem 4.3 of [5]). Under this identification, P (S) is identified with P B p (S). As a consequence of Corollary 1.2, we obtain the following corollary, which answers to Question 4 in [2] affirmatively for closed orientable surfaces of genus at least two. Corollary 1.5. Let n be an integer at least two. Let M be a connected, closed and orientable surface of genus at least two. Then any finite index subgroup of B n (M ) is co-Hopfian.
The proof of this corollary is presented in Section 2.5. In the next section, we introduce notation and terminology employed throughout the paper and recall basic properties of superinjective maps defined on CP(S) etc. Afterward, we present an organization of the paper, outlining the proof of Theorems 1.1 and 1.3.

Preliminaries
2.1. Notation and terminology. Unless otherwise stated, we always assume that a surface is connected, compact and orientable. Let S = S g,p be a surface of genus g with p boundary components, and let ∂S denote the boundary of S. A simple closed curve in S is said to be essential in S if it is neither homotopic to a single point of S nor isotopic to a boundary component of S. Let V (S) denote the set of isotopy classes of essential simple closed curves in S. When there is no confusion, we mean by a curve in S either an essential simple closed curve in S or its isotopy class. An essential simple closed curve α in S is said to be non-separating in S if S \ α is connected, and otherwise α is said to be separating in S. These properties depend only on the isotopy class of α. For a separating curve α in S and two components ∂ 1 , ∂ 2 of ∂S, we say that α separates ∂ 1 and ∂ 2 if ∂ 1 and ∂ 2 are contained in distinct components of S \ α.
Let i : V (S) × V (S) → Z ≥0 denote the geometric intersection number, i.e., the minimal cardinality of the intersection of representatives for two elements of V (S). If a and b are essential simple closed curves in S with |a ∩ b| = i([a], [b]), where [a] and [b] denote the isotopy classes of a and b, respectively, then we say that a and b intersect minimally. Let Σ(S) denote the set of non-empty finite subsets σ of V (S) with i(α, β) = 0 for any two elements α, β ∈ σ. We extend i to the symmetric function on (V (S) ⊔ Σ(S)) 2 so that i(α, σ) = β∈σ i(α, β) and i(σ, τ ) = β∈σ,γ∈τ i(β, γ) for any α ∈ V (S) and σ, τ ∈ Σ(S). We say that two elements σ, τ of V (S) ⊔ Σ(S) are disjoint if i(σ, τ ) = 0, and otherwise we say that they intersect. We say that two elements α, β of V (S) fill S if there exists no element of V (S) disjoint from both α and β.
For each σ ∈ Σ(S), we denote by S σ the surface obtained by cutting S along all curves in σ. When σ consists of a single curve α, we denote it by S α for simplicity. We often identify a component of S σ with a complementary component of a tubular neighborhood of a one-dimensional submanifold representing σ in S if there is no confusion. If Q is a component of S σ , then V (Q) is naturally identified with a subset of V (S).
Suppose that the boundary ∂S of S is non-empty. We say that a simple arc l in S is essential in S if • ∂l consists of two distinct points of ∂S; • l meets ∂S only at its end points; and • l is not isotopic relative to ∂l to an arc in ∂S.
Unless otherwise stated, isotopy of essential simple arcs in S may move their end points, keeping them staying in ∂S. An essential simple arc l in S is said to be separating in S if S \ l is not connected. Otherwise l is said to be non-separating in S. These properties depend only on the isotopy class of l. Let ∂ 1 and ∂ 2 be distinct components of ∂S. We say that an essential simple arc l in S connects ∂ 1 and ∂ 2 if one of the end point of l lies in ∂ 1 and another in ∂ 2 .
2.2. Complexes and groups associated to surfaces. The following simplicial complex was introduced by Harvey [11].
Complex C(S). This is defined as the abstract simplicial complex such that the sets of vertices and simplices of C(S) are V (S) and Σ(S), respectively. The complex C(S) is called the complex of curves for S.
We denote byS the closed surface obtained from S by attaching disks to all boundary components of S. Let C * (S) be the simplicial cone over C(S) with its cone point * . Namely, C * (S) is the abstract simplicial complex such that the set of vertices is the disjoint union V (S) ⊔ { * }; and the set of simplices is We then have the simplicial map π : C(S) → C * (S) associated with the inclusion of S intoS. Note that π −1 ( * ) consists of all separating curves in S cutting off a holed sphere from S.
Hole-bounding curves (HBC). A curve α in S is called a hole-bounding curve (HBC) in S if α lies in π −1 ( * ). When the genus of S is positive and the holed sphere cut off by α contains exactly k components of ∂S, we call α a k-HBC in S. Note that we have 2 ≤ k ≤ p.
If α is a k-HBC in S and ∂ 1 , . . . , ∂ k are the components of ∂S contained in the holed sphere cut off by α, then we say that α encircles ∂ 1 , . . . , ∂ k .
Let α be a 2-HBC in S encircling two components ∂ 1 , ∂ 2 of ∂S. Up to isotopy, there exists a unique essential simple arc in S connecting ∂ 1 with ∂ 2 and disjoint from α. This arc is called the defining arc of α. Conversely, if we have g ≥ 1 and p ≥ 2 and if l is an essential simple arc in S connecting two distinct components ∂ 1 , ∂ 2 of ∂S, then the boundary component of a regular neighborhood of the union l ∪ ∂ 1 ∪ ∂ 2 is a 2-HBC in S. The 2-HBC is then called the curve in S defined by l.
Hole-bounding pairs (HBP). A pair {α, β} of curves in S is called a holebounding pair (HBP) in S if {α, β} is an edge of C(S) and we have π(α) = π(β) = * . We note that there exists a unique component of S {α,β} of genus zero if the genus of S is at least two. In this case, if that component contains exactly k components of ∂S, then we call the pair {α, β} a k-HBP in S. Note that we have 1 ≤ k ≤ p.
An HBP in S is said to be non-separating if both curves in it are non-separating in S, and it is said to be separating if both curves in it are separating in S. Note that each HBP in S is either separating or non-separating. Two disjoint HBPs a, b in S are said to be equivalent in S if π(a) = π(b). Two disjoint curves α, β in S are said to be HBP-equivalent in S if π(α) = π(β).
Complexes CP(S), CP n (S) and CP s (S). Let V c (S) be the set of all isotopy classes of HBCs in S, and let V p (S) be the set of all isotopy classes of HBPs in S.
We define CP(S) to be the abstract simplicial complex such that the set of vertices is the disjoint union V c (S)⊔V p (S); and a non-empty finite subset σ of V c (S)⊔V p (S) is a simplex of CP(S) if and only if any two elements of σ are disjoint.
We denote by V np (S) and V sp (S) the subsets of V p (S) consisting of all nonseparating HBPs and all separating HBPs, respectively. We define CP n (S) and CP s (S) as the full subcomplexes of CP(S) spanned by V c (S) ⊔ V np (S) and V c (S) ⊔ V sp (S), respectively.
Mapping class groups. The extended mapping class group Mod * (S) for S is the group of isotopy classes of homeomorphisms from S onto itself, where isotopy may move points in ∂S. The mapping class group Mod(S) for S is the group of isotopy classes of orientation-preserving homeomorphisms from S onto itself. The pure mapping class group PMod(S) for S is the group of isotopy classes of orientationpreserving homeomorphisms from S onto itself that fix each component of ∂S as a set. Both Mod(S) and PMod(S) are finite index subgroups of Mod * (S). For each α ∈ V (S), we denote by t α ∈ PMod(S) the (left) Dehn twist about α.
Surface braid groups. We have the surjective homomorphism ι : PMod(S) → Mod(S) associated with the inclusion of S intoS. We define P (S) to be ker ι. By the Birman exact sequence, P (S) is generated by all elements of the forms t α and t β t −1 γ with α ∈ V c (S) and {β, γ} ∈ V p (S) (see Section 4.1 in [5]). We define P s (S) as the group generated by all elements of the forms t α and t β t −1 γ with α ∈ V c (S) and {β, γ} ∈ V sp (S). The group P s (S) is of infinite index in P (S) because no non-zero power of t δ t −1 ǫ with {δ, ǫ} ∈ V np (S) belongs to P s (S) by Lemma 2.3 in [22].
2.3. Superinjective maps. We review basic properties of superinjective maps defined between simplicial complexes introduced in the previous subsection.
Definition 2.1. Let S be a surface, and let X and Y be any of the simplicial complexes, C(S), CP(S), CP n (S) and CP s (S). We denote by V (X) and V (Y ) the sets of vertices of X and Y , respectively. We mean by a superinjective map φ : X → Y a simplicial map φ : X → Y satisfying i(φ(a), φ(b)) = 0 for any two vertices a, b ∈ V (X) with i(a, b) = 0.
Note that a map φ : V (X) → V (Y ) defines a simplicial map from X into Y if and only if i(φ(a), φ(b)) = 0 for any two vertices a, b ∈ V (X) with i(a, b) = 0. It can be checked that any superinjective map from X into Y is injective, and that for any superinjective map φ : Lemma 2.2. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2, and let φ : CP n (S) → CP(S) and ψ : CP s (S) → CP(S) be superinjective maps. Then φ sends each nonseparating HBP to an HBP, and ψ sends each separating HBP to an HBP.
This lemma is a direct consequence of the following description of simplices of maximal dimension in CP(S). . Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then we have dim(CP(S)) = dim(CP s (S)) = dim(CP n (S)) = p + 1 2 − 1.
Moreover, for any simplex σ of CP(S) of maximal dimension, there exists a unique simplex s = {β 0 , β 1 , . . . , β p } of C(S) such that • any two curves in s are HBP-equivalent; and • σ consists of all HBPs of two curves in s.
Using this description of simplices of maximal dimension, we can also show that the maps φ and ψ in Lemma 2.2 preserve rooted simplices defined as follows.
Definition 2.4. Let S be a surface, and let σ be a simplex of CP(S) consisting of HBPs. We say that σ is rooted if there exists a curve α in S contained in any HBP of σ. In this case, if |σ| ≥ 2, then α is uniquely determined and called the root curve of σ.
Rooted simplices are first introduced in [19] for the Torelli complex of S in an analogous way. The proof of the following two lemmas are verbatim translations of those of the cited lemmas, where only superinjective maps from CP(S) into itself and ones from CP s (S) into itself are dealt with. Lemma 3.12]). Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then any superinjective map from CP n (S) into CP(S) preserves rooted simplices. Moreover, the same conclusion holds for any superinjective map from CP s (S) into CP(S). Lemma 3.13]). Let S = S g,p be a surface with g ≥ 2 and p ≥ 2, and let φ : CP n (S) → CP(S) be a superinjective map. Pick a simplex σ of CP n (S) of maximal dimension, and let {α 0 , α 1 , . . . , α p } denote the collection of curves in HBPs of σ. Then there exists a collection of curves in S, {β 0 , β 1 , . . . , β p }, satisfying the equality φ({α j , α k }) = {β j , β k } for any distinct j, k = 0, 1, . . . , p. Moreover, the same conclusion holds for any superinjective map from CP s (S) into CP(S) and any simplex of CP s (S) of maximal dimension.
2.4. Strategy. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Our purpose is to show surjectivity of any superinjective map from CP(S) into itself and any superinjective map from CP s (S) into itself. In Section 3, we discuss topological properties of vertices preserved by a superinjective map φ : CP n (S) → CP(S). Specifically, we show that for any integers j and k with 2 ≤ j ≤ p and 1 ≤ k ≤ p, the map φ preserves j-HBCs and non-separating k-HBPs, respectively. In particular, the inclusion φ(CP n (S)) ⊂ CP n (S) is proved. The proof of these facts in the cases p = 2 and p ≥ 3 are fairly different. In the former case, the pentagons in CP n (S) described in Figures 1 and 3 play a central role. The proof in the latter case is more straightforward.
In Section 4, we study a superinjective map ψ : CP s (S) → CP s (S) and show that ψ preserves j-HBCs and k-HBPs, respectively, for any j and k. The proof in the cases p = 2 and p ≥ 3 are different as in Section 3. In the former case, the hexagons in CP s (S) described in Figures 4 and 6 are considered.
In Section 5, we focus on the case p = 2 and discuss topological types of hexagons in CP n (S), provided that topological types of their vertices are given. As a result, for any superinjective map φ : CP n (S) → CP n (S) and any non-separating 2-HBP a in S, the map from the link of a into the link of φ(a), defined as the restriction of φ, induces an injective simplicial map between the Farey graphs associated with the holed spheres cut off by a and φ(a) from S. We then conclude that it is surjective and that φ sends the link of a onto the link of φ(a).
In Section 6, we still focus on the case p = 2 and obtain a similar result for any superinjective map ψ : CP s (S) → CP s (S) and any separating 2-HBP in S by studying topological types of hexagons in CP s (S).
In Section 7, we introduce two natural subcomplexes of the complex of arcs, denoted by D(X, ∂) and D(Y ), and show that any injective simplicial maps from those complexes into themselves are surjective. In the case p = 2, properties of hexagons proved in Sections 5 and 6 are also used to show that the restrictions of superinjective maps φ : CP n (S) → CP n (S) and ψ : CP s (S) → CP s (S) to the link of any 1-HBP induce injective simplicial maps between those complexes.
In Section 8, we prove surjectivity of any superinjective maps φ : CP n (S) → CP n (S) and ψ : CP s (S) → CP s (S) by induction on p. Surjectivity of any superinjective map from CP(S) into itself then follows.

2.5.
Proof of Corollary 1.5. Assuming Corollary 1.2, we prove Corollary 1.5. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. We denote by  : Mod(S) → Mod(S) the homomorphism associated with the inclusion of S intoS, which is an extension of ι. We define B(S) as the kernel of . Our aim is to prove that any finite index subgroup of B(S) is co-Hopfian.
Let Γ be a finite index subgroup of B(S). Let f : Γ → Γ be an injective homomorphism. We put Γ 0 = P (S) ∩ f −1 (P (S) ∩ Γ), which is a finite index subgroup of P (S). By Corollary 1.2, there exists γ ∈ Mod * (S) with f (x) = γxγ −1 for any x ∈ Γ 0 . For any y ∈ Γ and any HBC α in S, there exists a non-zero integer N such that t N α belongs to Γ 0 . We then have On the other hand, we have We thus have f (y)γα = γyα for any HBC α in S. Replacing α with any HBP b = {b 1 , b 2 } in S and replacing t α with t b1 t −1 b2 , we can show the equality f (y)γb = γyb along a verbatim argument. Since the action of Mod * (S) on CP(S) is faithful by Lemma 2.2 in [22], the equality f (y) = γyγ −1 holds.
We have the equality γ We mean by a pentagon in CP(S) a subgraph of CP(S) consisting of five vertices v 1 , . . . , v 5 with i(v k , v k+1 ) = 0 and i(v k , v k+2 ) = 0 for each k mod 5. In this case, let us say that the pentagon is defined by the 5-tuple (v 1 , . . . , v 5 ). A pentagon in CP n (S) is defined as a pentagon in CP(S) each of whose vertices belongs to CP n (S). Examples of pentagons in CP n (S g,2 ) are described in Figures 1 and 3.
The following two lemmas are observations on pentagons in CP(S g,2 ) consisting of HBPs.
Lemma 3.1. Let S = S g,2 be a surface with g ≥ 2. Then there exists no pentagon Π in CP(S) such that • any vertex of Π corresponds to an HBP; and • there exists a curve in S contained in any HBP of Π.
Proof. Assuming that there exists such a Π defined by a 5-tuple (a, b, c, d, e), we deduce a contradiction. Let α denote the curve shared by the five HBPs of Π. Label all boundary components of S α by ∂ 1 , ∂ 2 , ∂ 3 and ∂ 4 so that ∂ 1 and ∂ 2 correspond to α, and ∂ 3 and ∂ 4 are components of ∂S. We define a 1 as the curve in a distinct from α and define b 1 , c 1 , d 1 and e 1 similarly. We can deduce a contradiction if all vertices of Π are assumed to correspond to a 1-HBP, by considering the component of ∂S contained in the pair of pants cut off by a 1-HBP. We may thus assume that a is a 2-HBP and that a 1 encircles ∂ 1 , ∂ 3 and ∂ 4 as a curve in S α if α is non-separating, or in a component of S α if α is separating. It follows that b and e are 1-HBPs. Without loss of generality, we may assume that b 1 encircles ∂ 1 and ∂ 3 . If both c and d were 1-HBPs, then c 1 would encircle ∂ 2 and ∂ 4 , and d 1 would encircle ∂ 1 and ∂ 3 . It turns out that e 1 encircles ∂ 2 and ∂ 4 and cannot be disjoint from a 1 . This is a contradiction. If c were a 2-HBP, then c 1 would have to encircle ∂ 1 , ∂ 3 and ∂ 4 . It follows that each of d 1 and e 1 encircles either ∂ 1 and ∂ 3 or ∂ 1 and ∂ 4 and that d 1 and e 1 cannot be disjoint and distinct. This is also a contradiction. In an analogous way, one can deduce a contradiction if d is assumed to be a 2-HBP. Let α 1 , α 2 and β denote the root curves of the three edges in the second condition, respectively. Then the equality α 1 = α 2 holds, and α 1 and β are disjoint, but not HBP-equivalent.
As an application of the last two lemmas, we prove the following property on a superinjective map from CP n (S) into CP(S) in the case p = 2. Subsequently, we prove an analogous property in the case p ≥ 3. Proof. Using Figure 1, we can find a pentagon Π in CP n (S) defined by a 5-tuple (x, y 1 , z 1 , z 2 , y 2 ) such that • y 1 = a and z 1 = b; • any vertex of Π corresponds to an HBP; and • any of the edges {x, y 1 }, {x, y 2 } and {z 1 , z 2 } is rooted. Applying Lemma 3.2 to φ(Π), we obtain the lemma. Proof. We prove assertion (i). Replacing a and b by HBPs equivalent to themselves, we may assume that a is a 1-HBP and that there exists a simplex s = {β 1 , . . . , β p } of C(S) such that • any curve in s is disjoint from a; • any two curves in s are HBP-equivalent; and • b is an HBP of two curves in s. Let σ denote the simplex of CP n (S) consisting of all HBPs of two curves in s. For each j = 1, . . . , p, we define σ j to be the rooted subsimplex of σ that consists of p − 1 HBPs and whose root curve is equal to β j . Let γ j denote the root curve of φ(σ j ). It follows from Lemma 2.6 that the equality If φ(a) were equivalent to φ(b), then those two HBPs would be contained in a simplex of CP(S) of maximal dimension. Proposition 2.3 shows that for each j = 1, . . . , p, there exists an HBP b j in σ j such that φ(a) and φ(b j ) share a curve. If this curve were not equal to γ j , then the inclusion This contradicts the existence of an HBP c with i(c, a) = i(c, b ′ j ) = 0 and i(c, b j ) = 0. It thus turns out that for each j = 1, . . . , p, φ(a) and φ(b j ) share γ j . This is a contradiction because φ(a) consists of two curves and we have p ≥ 3.
A verbatim proof shows assertion (ii).
In the rest of this section, we discuss topological properties of vertices preserved by any superinjective map from CP n (S) into CP(S).
Lemma 3.5. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then any superinjective map from CP n (S) into CP(S) preserves non-separating HBPs.
Proof. The following argument appears in the proof of Lemma 3.14 in [22]. Pick a simplex σ of maximal dimension in CP n (S) which consists of HBPs of two curves in the collection s = {α 0 , α 1 , . . . , α p } of non-separating curves described in Figure  2. Let β 1 , β 2 and β 3 be the curves in S described in Figure 2. Note that β 2 is not HBP-equivalent to any curve of s and that S {αj ,β2} is connected for each j = 0, . . . , p. By Lemma 2.6, there exist curves γ j and δ k in S with for any distinct j 1 , j 2 = 0, . . . , p and any distinct k 1 , k 2 = 1, 2, 3. We put t = {γ 0 , . . . , γ p }. Since {δ 1 , δ 2 } intersects γ 0 and is disjoint from any curve in t \ {γ 0 } and since {δ 2 , δ 3 } intersects γ p and is disjoint from any curve in t \ {γ p }, we see that δ 2 is disjoint from any curve in t. By Lemmas 3.3 and 3.4, δ 2 is not HBP-equivalent to any curve of t. It follows that {δ 2 , δ 1 } is a 1-HBP in S and that there exists a (p − 1)-HBP of two curves in t \ {γ 0 } such that the other curves in it are contained in the holed sphere cut off by that (p − 1)-HBP from S. Similarly, 1-HBP in S, and there exists a (p − 1)-HBP of two curves in t \ {γ p } such that the other curves in it are contained in the holed sphere cut off by that (p − 1)-HBP from S. It thus follows that {γ 0 , γ p } is a p-HBP in S. We now assume that any curve of t is separating in S. If δ 2 lies in the component of S {γ0,γp} of positive genus that contains γ 0 as a boundary component, then the HBP {δ 2 , δ 3 } cannot intersect γ p , kept disjoint from any curve in t \ {γ p }. This is a contradiction. In a similar way, we can deduce a contradiction if we assume that δ 2 lies in the component of S {γ0,γp} of positive genus that contains γ p as a boundary component. We thus proved that any curve of t is non-separating in S. Lemma 3.6. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then for each integer k with 1 ≤ k ≤ p, any superinjective map from CP n (S) into CP(S) preserves nonseparating k-HBPs.
Proof. Pick a non-separating 1-HBP a. There exists a simplex s = {β 1 , . . . , β p } of C(S) such that • any curve in s is disjoint from a; • any two curves in s are HBP-equivalent; and • the surface obtained by cutting S along β 1 and a curve of a is connected. Let σ denote the simplex of CP n (S) consisting of all HBPs of two curves in s. It then follows that φ(a) is a 1-HBP since φ(a) and any HBP in φ(σ) is not equivalent by Lemmas 3.3 and 3.4 and since φ(σ) consists of all HBPs of two curves in a collection of p curves which are mutually HBP-equivalent.
We have shown that φ preserves non-separating 1-HBPs. Note that for each nonseparating k-HBP c, there exist curves γ 0 , . . . , γ k such that we have the equality c = {γ 0 , γ k } and for each j, {γ j , γ j+1 } is a 1-HBP. It follows that φ({γ j , γ j+1 }) is a 1-HBP. Using Lemma 2.6, we see that φ(c) is a k-HBP. Lemma 3.7. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then for each integer j with 2 ≤ j ≤ p, any superinjective map from CP n (S) into CP(S) preserves j-HBCs.
We first show this lemma when p = 2, using the following observation on root curves of edges of pentagons.  Then the root curves of the three edges in the second condition are equal.
Proof of Lemma 3.7 when p = 2. Pick a 2-HBC a in S and choose a pentagon Π containing a and described as in Figure 3. Let (a, b 1 , c 1 , c 2 , b 2 ) denote the 5-tuple defining Π. We note that b 1 and b 2 are 2-HBPs and that c 1 and c 2 are 1-HBPs. By Lemmas 3.6 and 3.8, the root curves of the three edges were not a 2-HBC, then φ(a) would be a 1-HBP and share a curve in S with each of φ(b 1 ) and φ(b 2 ). We define b 2 1 and b 2 2 as the curves of φ(b 1 ) and φ(b 2 ) distinct from β, respectively. Since we have i(b 2 1 , b 2 2 ) = 0, φ(a) has to contain β. This contradicts Lemma 3.1. It therefore turns out that φ(a) is a 2-HBC, and the lemma follows.
Before giving a proof of Lemma 3.7 when p ≥ 3, let us prove the following: Lemma 3.9. Let S = S g,p be a surface with g ≥ 2 and p ≥ 3, and let φ : CP n (S) → CP(S) be a superinjective map. For each non-separating curve α in S, there exists a unique non-separating curve β in S such that for any HBP a in S containing α, the HBP φ(a) contains β.
Proof. Pick a non-separating curve α in S. Choosing two disjoint and distinct HBPs a, b in S containing α, we define β to be the root curve of the rooted edge {φ(a), φ(b)}. The curve β depends only on α thanks to Lemma 2.5 and the fact that for any two rooted edges {a 1 , b 1 } and {a 2 , b 2 } of CP n (S) whose root curves are equal to α, there exists a sequence of rooted 2-simplices of CP n (S), σ 1 , . . . , σ m , such that a 1 , b 1 ∈ σ 1 ; a 2 , b 2 ∈ σ m ; and σ j ∩ σ j+1 is an edge of CP n (S) for each j = 1, . . . , m − 1. Existence of such a sequence follows from Lemmas 4.5 and 5.1 in [22]. Uniqueness of β follows from injectivity of φ.
Proof of Lemma 3.7 when p ≥ 3. Let α be a j-HBC in S. We prove that φ(α) is a j-HBC in S by induction on j.
We next assume j ≥ 3. Pick a (j − 1)-HBC β in S disjoint from α and contained in the holed sphere cut off by α from S. The hypothesis of the induction shows that φ(β) is also a (j − 1)-HBC. Let Q and R denote the components of S β and S φ(β) of positive genus, respectively. The map φ induces a superinjective map from CP n (Q) into CP(R). Since α is a 2-HBC in Q, φ(α) is a 2-HBC in R by Lemma 3.7 in the case p = 2. It thus turns out that φ(α) is a j-HBC in S.
The following lemma is an immediate consequence of Lemmas 3.5 and 3.7.
Lemma 3.10. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2, and let φ : CP n (S) → CP(S) be a superinjective map. Then the inclusion φ(CP n (S)) ⊂ CP n (S) holds.

Superinjective maps from CP s (S) into itself
We discuss topological properties of vertices preserved by any superinjective map from CP s (S) into itself. Throughout this section, we mean by an HBP a separating one, unless otherwise stated.
We mean by a hexagon in CP(S) a subgraph of CP(S) consisting of six vertices In this case, let us say that the hexagon is defined by the 6-tuple (v 1 , . . . , v 6 ). A hexagon in CP s (S) (resp. CP n (S)) is defined as a hexagon in CP(S) each of whose vertices belongs to CP s (S) (resp. CP n (S)). Examples of hexagons in CP(S) are described in Figures 4, 5 and 6. Then the following assertions hold: The HBP a is equivalent to neither b nor f . In particular, we have g ≥ 3.
(ii) Each of a, b, d and f is a 1-HBP, and each of c and e is a 2-HBP.
Note that the hexagon in Figure 4 satisfies the assumption in this proposition. Let us summarize elementary properties on separating HBPs, which will be used to prove the proposition. One can readily check the following two lemmas.  In case (c), we first assume that a and d are 2-HBPs. Let Q 1 denote the holed sphere cut off by a from S. The curves in b and f that do not belong to a intersect and thus fill Q 1 . They belong to c and e, respectively, by Lemma 4.2 (ii). The equality a = d thus has to hold. This is a contradiction. We next assume that c and e are 2-HBPs. By Lemma 4.3 (ii), c, d and e share a curve, denoted by α. Similarly, by Lemma 4.3 (i), b, a and f share a curve, denoted by β. We have α = β by Lemma 4.2 (ii). We define c 1 , d 1 and e 1 as the curves in c, d and e distinct from α, respectively. It follows from i(b, c) = i(d, c) = 0 that β and d 1 are curves in the holed sphere, denoted by Q 2 , cut off by c from S. Since b consists of β and a curve in c and since we have i(b, d) = 0, the curves β and d 1 intersect and fill Q 2 . This contradicts the existence of the curve e 1 satisfying i(e 1 , β) = i(e 1 , d) = 0 and i(e 1 , c 1 ) = 0.
In case (d), we may assume that a, c and e are 2-HBPs. By Lemma 4.3 (ii), the three HBPs in each of the triplets {c, d, e}, {e, f, a} and {a, b, c} share a curve in S, and we denote it by α, β and γ, respectively. Note that α, β and γ are mutually disjoint. If α, β and γ were mutually distinct, then we would have the equalities a = {β, γ}, c = {γ, α} and e = {α, β}, and these three HBPs would form a 2-simplex of CP s (S). This is a contradiction. If α = β = γ, then we would have a = c and obtain a contradiction. A similar argument implies the equality α = β = γ. We define a 1 , . . . , f 1 as the curves of a, . . . , f distinct from α, respectively.
Let R denote the component of S α containing ∂S, which contains all the curves a 1 , . . . , f 1 . We have the three 3-HBCs a 1 , c 1 and e 1 in R encircling the two components of ∂S and the boundary component of R, denoted by ∂ α , that corresponds to α. The other three 2-HBCs b 1 , d 1 and f 1 in R encircles one component of ∂S and ∂ α . Without loss of generality, we may assume that b 1 and d 1 encircles ∂ α and the same component of ∂S, denoted by ∂ 1 . Another component of ∂S is denoted by ∂ 2 . LetR denote the surface obtained from R by attaching a disk to ∂ 2 . We have the simplicial map ρ : C(R) → C * (R) associated with the inclusion of R intõ R, where C * (R) is the simplicial cone over C(R) with the cone point * . Note that ρ −1 ( * ) consists of all 2-HBCs in R encircling ∂ 2 and another boundary component of R. We then obtain the equality If f 1 encircles ∂ 1 and ∂ α , then we have ρ(f 1 ) = ρ(a 1 ). This contradicts Theorem 7.1 in [18] asserting that the inverse image of a curve inR under ρ is a simplicial tree. If f 1 encircles ∂ 2 and ∂ α , then the equality ρ(a 1 ) = ρ(e 1 ) implies the equality a 1 = e 1 because a 1 and e 1 are disjoint from f 1 . This is also a contradiction.
If g = 2, then any two disjoint and separating HBPs in S are equivalent. The existence of Π therefore implies g ≥ 3.
Proof of Proposition 4.1 (ii). Assertion (i) and Lemma 4.2 (i) imply that a, b and f are 1-HBPs. By Lemma 4.3 (iii), at least one of c, d and e is a 2-HBP. Assuming that exactly one of c, d and e is a 2-HBP, we deduce a contradiction. This completes the proof.
First, we assume that c is a 2-HBP. By Lemma 4.3 (i), d, e and f share a curve, denoted by α. The curve α separates the two components of ∂S. It follows that d 1 and f 1 , the curves of d and f distinct from α, respectively, are contained in the same component of S α and that the two curves of a are contained in another component of S α . The equality i(a, d) = 0 thus holds, and this is a contradiction. By symmetry, we can also deduce a contradiction if we assume that e is a 2-HBP.
We next assume that d is a 2-HBP. Let α, β, γ and δ denote the root curves of {b, c}, {c, d}, {d, e} and {e, f }, respectively. By Lemma 4.2 (ii), we have α = β and γ = δ, and the equalities c = {α, β} and e = {γ, δ} thus hold. Since d contains β and γ and since we have i(c, e) = 0, the two curves α and δ intersect and fill the holed sphere cut off by d from S. This contradicts the existence of the 1-HBP a disjoint from α and δ.
We now turn our attention to superinjective maps from CP s (S) into itself.
Lemma 4.4. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then for each integer k with 1 ≤ k ≤ p, any superinjective map from CP s (S) into itself preserves k-HBPs.
We first prove this lemma when p = 2.
Proof of Lemma 4.4 when p = 2. If g ≥ 3, then the lemma is obtained by using the hexagon in Figure 4 and Proposition 4.1. If g = 2, then pick a superinjective map ψ : CP s (S) → CP s (S) and the hexagon in CP s (S) described in Figure 6 In the rest of the proof of Lemma 4.4, we assume p ≥ 3 and prove it in the cases of g = 2 and g ≥ 3 separately.
Proof of Lemma 4.4 when g = 2 and p ≥ 3. Let ψ : CP s (S) → CP s (S) be a superinjective map. Note that any two disjoint and separating HBPs in S are equivalent thanks to the assumption g = 2. We claim that ψ preserves 2-HBCs.
Pick a 2-HBC α in S. There then exists a simplex s = {β 1 , . . . , β p } of C(S) disjoint from α and consisting of mutually HBP-equivalent and separating curves in S. Let σ denote the simplex of CP s (S) consisting of all HBPs of two curves in s. If ψ(α) were an HBP, then it would be equivalent to any HBP in ψ(σ), and we can deduce a contradiction along the proof of Lemma 3.4. It thus turns out that ψ(α) is an HBC. The existence of σ implies that ψ(α) is a 2-HBC. Our claim follows.
We prove that ψ preserves k-HBPs by induction on p.
We have shown that {δ 0 , δ 2 } is a 2-HBP and that for each j = 2, . . . , p − 1, {δ j , δ j+1 } is a 1-HBP. It follows that {δ 0 , δ 1 } and {δ 1 , δ 2 } are 1-HBPs and that ψ preserves k-HBPs for each k. It is shown that {γ 0 , γ 2 } is a 2-HBP by choosing a simplex of CP s (S) consisting of (p − 1)(p − 2)/2 HBPs which are mutually equivalent and any of which is disjoint from {β 0 , β 2 }, but not equivalent to it. Repeating this argument, we see that for each j = 1, . . . , p, {γ 0 , γ j } is a j-HBP. The proof of Lemma 4.5 when p ≥ 3 is a verbatim translation of that of Lemma 3.7 when p ≥ 3. In place of Lemma 3.9, we use the following lemma, which can be verified by using Lemmas 4.10 and 5.3 in [22].  In this section, we focus on the case p = 2 and study topological types of hexagons in CP n (S g,2 ). We then show that any superinjective map φ from CP n (S g,2 ) into itself sends the link of any 2-HBP a onto the link of φ(a). Results in this section will also be used in the subsequent sections. Throughout this section, we put S = S g,2 with g ≥ 2 and mean by an HBP a non-separating one, unless otherwise stated, since we mainly deal with CP n (S). The hexagon in Figure 5 satisfies the assumption in this proposition.
Proof of Proposition 5.1 (i). Let α, β, γ and δ denote the root curves of the edges {c 1 , b 1 }, {b 1 , c 3 }, {c 3 , b 2 } and {b 2 , c 2 }, respectively. First, assuming β = γ, we deduce a contradiction. We then have c 3 = {β, γ} and denote by Q the holed sphere cut off by c 3 from S. We define a curve c 1 2 so that c 2 = {δ, c 1 2 }. We assume that any two of these curves intersect minimally unless they are isotopic.
Suppose that the equality α = β holds. If the equality γ = δ were true, then we would have i(a, c 3 ) = 0 and a contradiction. We thus have γ = δ and b 2 = {γ, δ}. Note that δ is a curve in Q. Since c 1 2 intersects β and is disjoint from δ and γ, the intersection c 1 2 ∩ Q consists of mutually isotopic, essential simple arcs in Q each of which cuts off an annulus containing exactly one component of ∂S. It is then impossible to find a position of a because a is a 2-HBC disjoint from β = α and c 2 .
In case (a), we have b 1 = {α, β} and b 2 = {β, δ}. It then follows that α and δ fill the holed sphere cut off by c 3 from S. Since a is disjoint from α and δ, it is impossible that a is a 2-HBC. In case (b), we have either b 2 = {α, δ} or b 1 = {α, δ}. Each of the two equalities contradicts the condition that a is disjoint from α and δ, but intersects b 1 and b 2 . In case (c), we have the equality b 1 = b 2 = {α, β} and a contradiction. k } for each j = 1, 2 and each k = 1, 2, 3. We assume that any two of these curves intersect minimally.
Let Q denote the holed sphere cut off by c 3 from S. Note that b 1 1 and b 1 2 are curves in Q. For each j = 1, 2, using b 1 j , we see that the intersection c 1 j ∩ Q consists of mutually isotopic, essential simple arcs in Q each of which cuts off an annulus containing exactly one component of ∂S, denoted by ∂ j , and joins two points of c 1 3 . Let l j denote a component of c 1 j ∩ Q. It follows from b 1 1 = b 1 2 that l 1 and l 2 are not isotopic. If l 1 and l 2 could not be isotoped so that they are disjoint, then the union of a subarc of l 1 and a subarc of l 2 would be a simple closed curve in Q isotopic to ∂ 1 . This is a contradiction because a is a 2-HBC in S disjoint from c 1 and c 2 . It thus turns out that l 1 and l 2 are non-isotopic and can be isotoped so that they are disjoint. The equality i(b 1 , b 2 ) = i(b 1 1 , b 1 2 ) = 2 now follows. Replacing the 6-tuple (a, c 1 , b 1 , c 3 , b 2 , c 2 ) with the 6-tuple (b 1 , c 3 , b 2 , c 2 , a, c 1 ), we show i(b 2 , a) = 2. Let R denote the holed sphere cut off by c 1 2 from S α . Let ∂ denote the boundary component of S α that corresponds to α and is contained in R. The holed sphere cut off by b 1 2 from S α contains ∂ because b 1 2 is disjoint from c 1 2 . Repeating this argument, we see that the holed sphere cut off by each of c 1 3 , b 1 1 and c 1 1 from S α contains ∂. As in the last paragraph, it is shown that the intersection c 1 1 ∩ R consists of mutually isotopic, essential simple arcs in R each of which cuts off an annulus containing ∂ and joins two points of c 1 2 . The intersection c 1 3 ∩ R also consists of mutually isotopic, essential simple arcs in R. Let r 1 and r 3 be components of c 1 1 ∩ R and c 1 3 ∩ R, respectively. It follows from a = b 1 2 that r 1 and r 3 are not isotopic. If r 1 and r 3 could not be isotoped so that they are disjoint, then the union of a subarc of r 1 and a subarc of r 3 would be a simple closed curve in R isotopic to ∂. This is a contradiction because b 1 1 is a 2-HBC in S α which is disjoint from c 1 1 and c 1 3 and cuts off a pair of pants containing ∂ from S α . It follows that r 1 and r 3 are non-isotopic and can be isotoped so that they are disjoint. The equality i(b 2 , a) = i(b 1 2 , a) = 2 is obtained. Along a verbatim argument, we obtain the equality i(a, b 1 ) = 2.
As an application of the last proposition, surjectivity of a superinjective map on the link of a 2-HBP is verified. Before proving this lemma, we recall the simplicial graph associated to S 0,4 .
Graph F (X). For a surface X homeomorphic to S 0,4 , we define a simplicial graph F (X) so that the set of vertices of F (X) is V (X) and two elements α, β ∈ V (X) are connected by an edge of F (X) if and only if we have i(α, β) = 2.
This graph is known to be isomorphic to the Farey graph (see Section 3.2 in [24]). It is shown that any injective simplicial map from the Farey graph into itself is surjective. To prove Lemma 5.2, we also need the following: Proof. Since we have already shown that φ preserves 2-HBCs, 1-HBPs and 2-HBPs, respectively, the proof of Lemma 4.7 in [22] is now valid for the present setting.
Proof of Lemma 5.2. We define curves β 1 , β 2 , γ 1 and γ 2 so that the equalities hold. By Lemma 5.3, we may assume that for any j = 1, 2 and any rooted edge e of CP n (S) whose root curve is equal to β j , the root curve of φ(e) is equal to γ j . It follows from Lemmas 3.6 and 3.7 that φ induces a map from the union of the set of HBCs in Lk(b) and the set of HBPs in Lk(b) containing β 1 into the union of the set of HBCs in Lk(φ(b)) and the set of HBPs in Lk(φ(b)) containing γ 1 . Applying Proposition 5.1 (ii), we conclude that this map induces an injective simplicial map between the Farey graphs associated to the holed spheres cut off by b and by φ(b) from S. Since such a simplicial map is surjective, the set φ(Lk(b)) contains all HBCs in Lk(φ(b)) and all HBPs in Lk(φ(b)) containing γ 1 . In a similar way, we can show that φ(Lk(b)) contains all HBPs in Lk(φ(b)) containing γ 2 .
Let us denote by H n = H n (S) the set of all hexagons in CP n (S) satisfying the assumption in Proposition 5.1. The following lemma motivates us to relate the link of a 1-HBP b in CP n (S) with the complex of arcs for the component of S b of positive genus. The latter complex will be examined in Section 7. Proof. Suppose that there exists a hexagon Π in H n containing b 1 , c 1 and c 3 . We then have a 6-tuple (a, c 1 , b 1 , c 3 , b 2 , c 2 ) defining Π. For each j = 1, 2, let b 1 j denote the curve of b j distinct from α. Let l a , l 1 and l 2 denote the defining arcs of a, b 1 1 and b 1 2 as curves in S α . Since b 1 1 and b 1 2 are curves in the holed sphere cut off by c 3 from S, the arcs l 1 and l 2 meet the same boundary component of S α corresponding to α. Proposition 5.1 (ii) implies that l a , l 1 and l 2 can mutually be disjoint. The defining arcs of c 1 1 and c 1 3 as curves in X are l a ∩ X and l 2 ∩ X, respectively, and are thus disjoint.
Conversely, suppose that the defining arcs of c 1 1 and c 1 3 as curves in X, denoted by r 1 and r 3 , respectively, are disjoint. Label as ∂ 1 and ∂ 2 the components of ∂S so that ∂ 2 is contained in the pair of pants cut off by b 1 from S. Let ∂ 3 denote the boundary component of S α that corresponds to α and is contained in the holed sphere cut off by c 1 1 from S α . The component ∂ 3 is also contained in the holed sphere cut off by c 1 3 from S α . Each of r 1 and r 3 connects the two component of ∂X corresponding to ∂ 1 and b 1 1 , the curve of b 1 distinct from α. We now extend r 1 to an essential simple arc l a in S α which connects ∂ 1 and ∂ 2 . We next extend r 3 to an essential simple arc l 2 in S α which connects ∂ 1 and ∂ 3 and is disjoint from l a . Let a and b 1 2 denote the curves in S α defined by l a and l 2 , respectively. Since l a and l 2 are disjoint, there exists a curve c 1 2 disjoint from a and In this section, we study hexagons in CP s (S g,2 ) and obtain results similar to those in the previous section (see Figure 6 for such a hexagon). The proof is also similar, and its large part is thus omitted. Throughout this section, we put S = S g,2 with g ≥ 2 and mean by an HBP a separating one, unless otherwise stated, since we mainly deal with CP s (S). Let (a, c 1 , b 1 , c 3  Proof. Assertion (i) is proved in Lemma 4.12 of [22]. Let α denote the common curve in assertion (i). Let R denote the component of S α containing ∂S, whose genus is positive and less than g. For each j = 1, 2 and each k = 1, 2, 3, we define curves b 1 j and c 1 k so that b j = {α, b 1 j } and c k = {α, c 1 k }. Let Q denote the holed sphere cut off by c 1 3 from R. It follows that a and each c 1 k are curves in R and that each b 1 j is a curve in Q. Along an argument of the same kind as in the proof of Proposition 5.1 (ii), we obtain the equality in assertion (ii). Proof. Since we have already shown that ψ preserves 2-HBCs, 1-HBPs and 2-HBPs, respectively, the proof of Lemma 4.14 in [22] is now valid for the present setting. Complex A(S). Let S be a surface with non-empty boundary. We define V a (S) as the set of isotopy classes of essential simple arcs in S. Let A(S) denote the abstract simplicial complex whose n-simplices are defined as a subset σ of V a (S) such that we have |σ| = n + 1 and have mutually disjoint representatives of elements of σ. We often identify an element of V a (S) with its representative if there is no confusion.
Complexes D(X, ∂) and D(Y ). Let X = S g,3 be a surface with g ≥ 1 and fix a boundary component ∂ of X. We define D(X, ∂) as the full subcomplex of A(X) spanned by all vertices that correspond to arcs in X connecting a component of ∂X \ ∂ with another component of ∂X \ ∂.
Let Y = S g,2 be a surface with g ≥ 1. We define D(Y ) as the full subcomplex of A(Y ) spanned by all vertices that correspond to arcs in Y connecting a component of ∂Y with another component of ∂Y .
The aim of this section is to show the following: Proposition 7.1. In the above notation, any injective simplicial map from D(X, ∂) into itself is surjective. Moreover, any injective simplicial map from D(Y ) into itself is also surjective.
The first subsection is preliminary to the proof of this proposition. We introduce variants of the complex of arcs and show that most of them are connected. These variants are special ones of the complex introduced and denoted by BZ(∆, ∆ 0 ) in [9]. The proof of Proposition 7.1 is presented in the second subsection. 7.1. Connectivity of complexes of arcs. Throughout this subsection, we fix a surface Q = S g,p+1 with g ≥ 0 and p ≥ 1, and fix a boundary component ∂ 0 of Q. Let R be the surface obtained from Q by attaching a disk to ∂ 0 . We label the components of ∂Q other than ∂ 0 as ∂ 1 , . . . , ∂ p . Suppose that we have a subset ∆ of ∂Q \ ∂ 0 with its decomposition ∆ = ∆ + ⊔ ∆ − satisfying the following two conditions: For each j = 1, . . . , p, • the two sets ∆ + ∩ ∂ j and ∆ − ∩ ∂ j are non-empty, finite and have the same cardinality; and • along ∂ j , points of ∆ + ∩ ∂ j and ∆ − ∩ ∂ j appear alternatively.
Complexes A(Q, ∆) and A(R, ∆). We denote by V a (Q, ∆) the set of isotopy classes relative to ∆ of simple arcs l in Q such that • l connects a point of ∆ + with a point of ∆ − and meets ∂Q only at its end points; and • l is not homotopic relative to ∆ to an arc in ∂Q which meets ∆ only at its end points.
Let A(Q, ∆) denote the abstract simplicial complex whose n-simplices are defined as a subset σ of V a (Q, ∆) such that we have |σ| = n + 1 and have representatives l 0 , . . . , l n of elements of σ with l j ∩ l k = ∂l j ∩ ∂l k for any distinct j and k. The set V a (R, ∆) and the complex A(R, ∆) are defined in the same manner after replacing Q with R in the last paragraph. We often identify an element of V a (Q, ∆) or V a (R, ∆) with its representative if there is no confusion.
In the rest of this subsection, we prove the following: As already mentioned, the complexes A(Q, ∆) and A(R, ∆) are special ones of the complex introduced and denoted by BZ(∆, ∆ 0 ) in [9], where high connectivity of it is discussed. The proof however does not care connectivity of it when g and p are small. We hence present a direct proof of Proposition 7.2.
In the case of (g, p) = (0, 1), both A(Q, ∆) and A(R, ∆) consist of finitely many vertices. The assertion in Proposition 7.2 for this case can directly be checked. In what follows, we assume (g, p) = (0, 1) and prove that A(R, ∆) is connected. Along a similar argument, connectivity of A(Q, ∆) is also proved. We thus omit the proof of it.
Let A * (R) denote the simplicial cone over A(R) with its cone point * . We then have the simplicial map π : A(R, ∆) → A * (R) defined by forgetting ∆, where π −1 ( * ) consists of all arcs in A(R, ∆) connecting two points of ∂ j for some j and homotopic relative to their end points to an arc in ∂ j . Note that π −1 ( * ) may be empty.
We now observe that for each arc u corresponding to a vertex of π −1 (A(R)), any arc corresponding to a vertex of the fiber π −1 (π(u)) is obtained by applying to u the twists about the component(s) of ∂R containing a point of ∂u. Let us explain this fact more precisely. We fix an orientation of R. For each j = 1, . . . , p, we put . , x j nj , y j nj appear in this order along the orientation of ∂ j induced by that of R. We define t j as a homeomorphism of R which is the identity outside a collar neighborhood N j of ∂ j and satisfies the equalities t j (x j k ) = y j k , t j (y j l ) = x j l+1 , t j (y j nj ) = x j 1 for each k = 1, . . . , n j and each l = 1, . . . , n j − 1.
Pick an arc u corresponding to a vertex of π −1 (A(R)). We first assume that the two points of ∂u lie in distinct components of ∂R, say ∂ 1 and ∂ 2 . We then have the equality ( †) π −1 (π(u)) = { t z 1 t w 2 u | z, w ∈ Z, z + w ∈ 2Z }. We next assume that the two points of ∂u lie in the same component of ∂R, say ∂ 1 . Choose an arc u 1 in π −1 (π(u)) connecting x 1 1 and y 1 1 . We may assume that u 1 ∩N 1 consists of exactly two components u + , u − with x 1 1 ∈ u + and y 1 1 ∈ u − , whereN 1 denotes the closure of N 1 . Put u 0 = u 1 \ N 1 . For each k = 2, . . . , n 1 , we define an essential simple arc u k in R as the union The arc u k connects x 1 1 and y 1 k and belongs to π −1 (π(u)). The set {u 1 , . . . , u n1 } is a simplex of A(R, ∆). We then have the equality ( ‡) π −1 (π(u)) = { t z 1 u k | z ∈ Z, k = 1, . . . , n 1 }. The following two lemmas show that there exists an edge or a vertex of A(R) whose inverse image under π spans a connected subcomplex of A(R, ∆). • a single component of ∂R contains both ∂u and ∂v; and • when we cut R along u and obtain a connected surface R u , the arc v connects the two boundary components of R u containing u. Then the full subcomplex of A(R, ∆) spanned by the union π −1 (π(u)) ∪ π −1 (π(v)) is connected.
Proof. We may assume that ∂u and ∂v are contained in ∂ 1 , and put ∂ = ∂ 1 . We use the same notation right before the lemma and put n = n 1 and t = t 1 . We also may assume that ∂u = ∂v = {x 1 1 , y 1 1 } and that u is decomposed into three arcs, u = u + ∪u 0 ∪u − , so that u + and u − are the two components of u∩N 1 with x 1 1 ∈ u + and y 1 1 ∈ u − ; and we have u 0 = u \ N 1 . To prove the lemma, by equation ( ‡), it suffices to show that there exists a path in A(R, ∆) connecting u and tu and consisting of vertices in π −1 (π(u)) ∪ π −1 (π(v)). If n ≥ 2, then define an essential simple arc w in R as the union w = u + ∪u 0 ∪t 2 u − . The sequence u, w, tu defines a path in A(R, ∆). We assume n = 1. The third assumption on u and v in the lemma implies that u is disjoint from either tv or t −1 v. It follows that either the sequence u, v, tu or the sequence u, tv, tu defines a path in A(R, ∆).
Lemma 7.4. Assume p ≥ 2. Let u be an arc corresponding to a vertex of A(R, ∆) and connecting distinct components of ∂R. Then the full subcomplex of A(R, ∆) spanned by π −1 (π(u)) is connected.
Proof of connectivity of A(R, ∆) in the case of (g, p) = (0, 1). We note that A(R) is connected by Theorem (a) in [12]. We also note that for any vertex x of A(R, ∆), the image of the link of x in A(R, ∆) under the map π : A(R, ∆) → A * (R) contains the link of π(x) in A(R).
Assume g ≥ 1 and pick an edge {u, v} of A(R, ∆) satisfying the condition in Lemma 7.3. Let w be a vertex of A(R, ∆). Since A(R) is connected, there exists a path in A(R) joining π(w) to π(u). The fact stated in the end of the previous paragraph implies that there exists a path in A(R, ∆) joining w to a vertex in π −1 (π(u)). Since any vertex in π −1 (π(u)) is joined to u in A(R, ∆) by Lemma 7.3, connectivity of A(R, ∆) follows. If g = 0 and p ≥ 2, then we can prove connectivity of A(R, ∆) in a similar way, using Lemma 7.4 in place of Lemma 7.3.
Let us make a comment on the proof of connectivity of A(Q, ∆) in the case of (g, p) = (0, 1). Let A * (Q) denote the simplicial cone over A(Q) with its cone point * . We then have the simplicial map π : A(Q, ∆) → A * (Q) defined by forgetting ∆. To prove connectivity of A(Q, ∆) along the proof for A(R, ∆), we need to know connectivity of the full subcomplex of A(Q) spanned by π(V a (Q, ∆)) \ { * }, in place of connectivity of A(R). The set π(V a (Q, ∆)) \ { * } is equal to the set of all vertices corresponding to arcs connecting two points of ∂Q \ ∂ 0 . Connectivity of this full subcomplex also follows from Theorem (a) in [12].

7.2.
Injections of D(X, ∂) and D(Y ). Let X = S g,3 and Y = S g,2 be surfaces with g ≥ 1 and fix a boundary component ∂ of X. In this subsection, we discuss the properties of the complexes D(X, ∂) and D(Y ) stated in the following two lemmas and prove Proposition 7.1. Let us say that a simplicial complex E is chain-connected if for any two simplices σ, τ of maximal dimension in E, there exists a sequence of simplices of maximal dimension in E, σ 0 , σ 1 , . . . , σ m , with σ 0 = σ and σ m = τ and with σ j ∩ σ j+1 a simplex of codimension one for each j = 0, 1, . . . , m − 1.
Lemma 7.5. In the above notation, the following assertions hold: (i) Let σ be a simplex of D(X, ∂) of codimension one. We denote by X σ the surface obtained by cutting X along arcs in σ. Then the number of simplices of maximal dimension in D(X, ∂) containing σ is equal to three if the component of X σ containing ∂ contains exactly two arcs in σ, and otherwise that number is equal to four.
Lemma 7.6. In the above notation, the following assertions hold: (i) For each simplex σ of D(Y ) of codimension one, the number of simplices of maximal dimension in D(Y ) containing σ is equal to three.
Before proving these two lemmas, let us recall basic facts on punctured surfaces and ideal arcs in them, which are fully discussed in [26]. Let T be a closed surface of positive genus g, and let P be a non-empty finite subset of T . The pair (T, P ) is then called a punctured surface. Let I denote the closed unit interval. We mean by an ideal arc in (T, P ) is the image of a continuous map f : I → T such that • we have f (∂I) ⊂ P and f (I \ ∂I) ⊂ T \ P ; • f is injective on I \ ∂I; and • there exists no closed disk D embedded in T with ∂D = f (I) and (D \ ∂D) ∩ P = ∅. Two ideal arcs l 1 , l 2 in (T, P ) are said to be isotopic if we have l 1 ∩ P = l 2 ∩ P ; and l 1 and l 2 are isotopic relative to l 1 ∩ P as arcs in (T \ P ) ∪ (l 1 ∩ P ). We mean by an ideal triangulation of (T, P ) is a cell division δ of T such that (a) the set of 0-cells of δ is P ; (b) each 1-cell of δ is an ideal arc in (T, P ); and (c) each 2-cell of δ is a triangle, that is, it is obtained by attaching a Euclidean triangle τ to the 1-skeleton of δ, mapping each vertex of τ to a 0-cell of δ, and each edge of τ to a 1-cell of δ. Let S be a surface of genus g with |P | boundary components. Suppose that T is obtained from S by shrinking each component of ∂S into a point and that P is the set of points into which components of ∂S are shrunken. The natural map from S onto T induces the bijection from V a (S) onto the set of isotopy classes of ideal arcs in (T, P ). Under this identification, a simplex of A(S) of maximal dimension corresponds to an ideal triangulation of T .
Proof of Lemma 7.6 (i). Let Y * denote the punctured surface obtained from Y by shrinking each component of ∂Y . We identify V a (Y ) with the set of isotopy classes of ideal arcs in Y * . Each simplex σ of D(Y ) of maximal dimension corresponds to a squaring of Y * , that is, when we cut Y * along arcs in σ, we obtain finitely many squares whose vertices are punctures of Y * and edges are arcs in σ. We see that • for each square Π of the squaring, diagonal vertices of Π correspond to the same puncture of Y * , and the two vertices of each edge of Π correspond to distinct punctures of Y * (see Figure 7 (a)); and • for each arc l in σ, the two squares having l as an edge are distinct. In other words, for each square Π of the squaring, any two distinct edges of Π correspond to distinct arcs in σ.
Each simplex of D(Y ) of maximal dimension consists of 4g arcs, and the number of squares in the squaring associated with it is equal to 2g. If we cut Y * along arcs in a simplex of D(Y ) of codimension one, then we obtain one hexagon H and 2g − 2 squares. There exist exactly three arcs in H each of which decomposes H into two squares. Lemma 7.6 (i) follows.
Proof of Lemma 7.5 (i). Let X * denote the punctured surface obtained from X by shrinking each component of ∂X. Let p 0 denote the puncture of X * corresponding to ∂. As in the proof of Lemma 7.6 (i), if we cut X * along arcs in a simplex of D(X, ∂) of maximal dimension, then we obtain 2g squares and one digon containing p 0 (see Figure 7 (b)). Such a simplex consists of 4g + 1 arcs. Let τ be a simplex of D(X, ∂) of codimension one, and cut X * along arcs in τ . If the component containing p 0 contains exactly four edges, then the number of simplices of maximal dimension containing τ is equal to four. Otherwise the component containing p 0 contains exactly two edges, and we have one hexagon. The number of simplices of maximal dimension containing τ is thus equal to three. Lemma 7.5 (i) follows.
Proof of Lemma 7.6 (ii). We prove that D(Y ) is connected, using the technique due to Putman [27] to show connectivity of a simplicial complex on which PMod(Y ) acts. Let l be the arc in Figure 8 (b). We pick an arc r corresponding to a vertex of D(Y ) and show that l and r can be connected by a path in D(Y ). We define T as the set consisting of the Dehn twists about the curves in Figure 8 (a) and their inverses. It is known that PMod(Y ) is generated by T (see [10]). Since l and r are sent to each other by an element of PMod(Y ), there exist elements h 1 , . . . , h n of T with r = h 1 · · · h n l. We note that for each h ∈ T , either hl = l or hl and l are disjoint. The sequence of vertices of D(Y ), l, h 1 l, h 1 h 2 l, . . . , h 1 · · · h n l = r, therefore forms a path in D(Y ). Connectivity of D(Y ) follows.
To prove Lemma 7.6 (ii), it suffices to show that the link of each simplex of D(Y ) of codimension at least two is connected. The idea to derive chain-connectivity from connectivity of such a link is due to Hatcher [12] and is also used in the proof of Proposition 4.7 in [6]. Let σ be a simplex of D(Y ) of codimension at least two. We identify the arc corresponding to a vertex of D(Y ) with an ideal arc in the punctured surface Y * . Let p + and p − denote the two punctures of Y * . We cut Y * along arcs in σ and obtain finitely many surfaces Y * 1 , . . . , Y * m . For each j = 1, . . . , m, let ∆ + j and ∆ − j denote the sets of points of Y * j corresponding to p + and p − , respectively, and set ∆ j = ∆ + j ∪ ∆ − j . For each j, the set ∆ j with this decomposition satisfies the two conditions stated in the beginning of Section 7.1. Each vertex of the complex A(Y * j , ∆ j ) is identified with a vertex of the link of σ in D(Y ). If there exist distinct j, k = 1, . . . , m with both A(Y * j , ∆ j ) and A(Y * k , ∆ k ) non-empty, then the link of σ is connected. Otherwise, since σ is of codimension at least two, there exists a unique j with A(Y * j , ∆ j ) of dimension at least one. By Proposition 7.2 (ii), A(Y * j , ∆ j ) is connected. Lemma 7.5 (ii) can also be proved along a similar idea using Proposition 7.2 and using Figure 9  It follows that if n(τ ) = 3, then n(φ(τ )) = 3. Any simplex of D(Y ) of maximal dimension containing φ(τ ) is therefore contained in the image of φ. As in the last paragraph, by Lemma 7.5 (ii), surjectivity of φ follows.

Surjectivity of superinjective maps
We are now ready to show surjectivity of any superinjective map from CP n (S) into itself and any superinjective map from CP s (S) into itself. 8.1. The case p = 2. Let S = S g,2 be a surface with g ≥ 2. Recall that we have the simplicial map π : C(S) → C * (S), whereS is the closed surface obtained from S by attaching disks to all components of ∂S. For each vertex v of C(S), we define C(S) v as the full subcomplex of C(S) spanned by π −1 (v), which is connected by Theorem 7.1 in [18]. We also have the simplicial maps θ n : CP n (S) → C * (S), θ s : CP s (S) → C * (S) associated to π. For a vertex v of C(S), we denote by CP n (S) v the full subcomplex of CP n (S) spanned by θ −1 n (v). The subcomplex CP s (S) v of CP s (S) is also defined in the same way. The following lemma will be used in the sequel. Proof. Pick a non-separating curve α inS. Lemma 4.5 in [22] shows that the link of each vertex of C(S) α is connected. Combining this fact with connectivity of C(S) α , we obtain assertion (i). Similarly, assertion (ii) is proved by using Lemma 4.10 in [22] asserting that the link of each vertex of C(S) β is connected for any separating curve β inS.
We define V n (S) as the subset of V (S) consisting of non-separating curves inS and define C n (S) as the full subcomplex of C(S) spanned by V n (S).
We now outline the proof of surjectivity of a superinjective map φ : CP n (S) → CP n (S). We first show that φ sends the fiber of θ n over each vertex of V n (S) onto the fiber of θ n of the same kind. It follows that φ induces a mapφ from V n (S) into itself. We next show thatφ defines a superinjective map from C n (S) into itself. The latter map is induced by an element of Mod * (S) due to Irmak [15] and is thus surjective. We then conclude surjectivity of φ.
Proof. Let X and X ′ denote the components of S a and S φ(a) of positive genus, respectively. We define ∂ and ∂ ′ as the boundary components of X and X ′ that correspond to α and Φ(α), respectively. We claim that φ induces an injective simplicial map from D(X, ∂) into D(X ′ , ∂ ′ ).
There is one-to-one correspondence between essential simple arcs in X connecting the two components of ∂X \ ∂ and curves in X cutting off a pair of pants containing the two components of ∂X \ ∂. The pair of α and such a curve in X is a 2-HBP in S. The same property holds for X ′ and ∂ ′ in place of X and ∂, respectively. Lemma 5.4 shows that φ induces a simplicial map from D(X, ∂) into D(X ′ , ∂ ′ ), which is injective because so is φ. By Proposition 7.1, this induced map is surjective. It follows that φ sends the set of 2-HBPs in Lk(a) containing α onto the set of 2-HBPs in Lk(φ(a)) containing Φ(α). Let α ′ denote the curve in a distinct from α. Applying the same argument to α ′ in place of α, we see that φ sends the set of 2-HBPs in Lk(a) containing α ′ onto the set of 2-HBPs in Lk(φ(a)) containing Φ(α ′ ). This is equivalent to that φ sends the set of 1-HBPs in Lk(a) containing α onto the set of 1-HBPs in Lk(φ(a)) containing Φ(α). The claim follows.
where U n (S) denotes the set of vertices of CP n (S).
Proof. We put α = θ n (a) and β = θ n (φ(a)), which are non-separating curves inS. Since φ preserves disjoint and equivalent HBPs and since CP n (S) α is connected by Lemma 8.1 (i), φ induces a simplicial map from CP n (S) α into CP n (S) β . Lemma 5.2 and Claim 8.3 show that this induced map sends the link of each vertex u of CP n (S) α onto the link of φ(u). The claim is proved. Claim 8.4 shows that φ induces a mapφ from V n (S) into itself withφ(θ n (a)) = θ n (φ(a)) for each HBP a in S. Proof. For any curves α, β ∈ V n (S), we have i(α, β) = 0 if and only if there exist a ∈ CP n (S) α and b ∈ CP n (S) β with i(a, b) = 0. Let us refer this fact as ( * ).
Thanks to Theorem 1.3 in [15],φ is induced by an element of Mod * (S). The map φ is thus surjective. Claim 8.4 implies that the image of the map φ : CP n (S) → CP n (S) contains all HBPs in S. Since for each 2-HBP a in S, φ sends the link of a onto the link of φ(a) by Lemma 5.2, we conclude that φ is surjective.
We turn to showing surjectivity of a superinjective map ψ : CP s (S) → CP s (S) when S = S g,2 with g ≥ 2. For each surface R, we denote by V s (R) the subset of V (R) consisting of separating curves in R and define C s (R) as the full subcomplex of C(R) spanned by V s (R). When g ≥ 3, we prove surjectivity of ψ, following the proof of Theorem 8.2 and associating to ψ a superinjective mapψ from C s (S) into itself, which is surjective due to the first author [20].
When g = 2, we cannot follow the last part of this proof because C s (S) is of dimension zero. In this case, we directly show that the map Ψ : V s (S) → V s (S) induced by ψ defines a superinjective map from C s (S) into itself. The latter map is surjective by [20], and thus so is ψ.
Theorem 8.6. Let S = S g,2 be a surface with g ≥ 2. Then any superinjective map ψ : CP s (S) → CP s (S) is surjective.
Proof. Throughout this proof, we mean by an HBP in S a separating HBP in S. Claim 8.7. Let a be a 1-HBP in S. We denote by α 0 the curve in a that does not separate the two components of ∂S, and denote by α 1 the curve in a distinct from α 0 . Then we have the equalities Proof. Choose a curve α 2 in S such that the pair {α 1 , α 2 } is a 1-HBP in S disjoint and distinct from a. We denote by Y and Z the components of S α1 containing α 0 and α 2 , respectively. Similarly, we denote by Y ′ and Z ′ the components of S Ψ(α1) containing Ψ(α 0 ) and Ψ(α 2 ), respectively. By Lemma 6.4, ψ induces an injective simplicial map from D(Y ) into D(Y ′ ) and an injective simplicial map from D(Z) into D(Z ′ ). Comparing the dimensions of these simplicial complexes, we see that Y and Y ′ are homeomorphic and that Z and Z ′ are homeomorphic. Proposition 7.1 shows that the induced map from D(Z) into D(Z ′ ) is surjective. The first equality in the claim then follows.
Let e be an element in the right hand side of the second equality in the claim, which is a 1-HBP in S. We denote by e 1 the curve in e distinct from Ψ(α 1 ). Since the 2-HBP {Ψ(α 0 ), e 1 } belongs to the right hand side of the first equality in the claim, there exists a curve d 1 in S with {α 0 , d 1 } ∈ Lk(a) 0 and ψ({α 0 , d 1 }) = {Ψ(α 0 ), e 1 }. We then have the equality e = {Ψ(α 1 ), e 1 } = ψ({α 1 , d 1 }) by Lemma 2.6. The second equality in the claim follows.
Recall that we have the simplicial map θ s : CP s (S) → C * (S) associated with the inclusion of S intoS. The proof of the following claim is obtained as a verbatim translation of that of Claim 8.4, by exchanging symbols appropriately and using Lemma 6.2 and Claim 8.7 in place of Lemma 5.2 and Claim 8.3.
where U s (S) denotes the set of vertices of CP s (S).
We now obtain the mapψ : V s (S) → V s (S) with the equalityψ(θ s (a)) = θ s (ψ(a)) for each HBP a in S. The following claim can also be verified along an argument of the same kind as in the proof of Claim 8.5.
Claim 8.9. The mapψ : V s (S) → V s (S) defines a superinjective map from C s (S) into itself.
If g ≥ 3, thenψ is surjective by Theorem 1.1 of [20], and surjectivity of ψ is shown along the end of the proof of Theorem 8.2. In the rest of the proof of Theorem 8.6, we assume g = 2 and show that the map Ψ : V s (S) → V s (S) defines a superinjective map from C s (S) into itself.
Claim 8.10. Assume g = 2. For each separating curve α in S which is not an HBC in S, we have the equalities Proof. We first assume that α does not separate the two components of ∂S. Let Q and Q ′ denote the components of S α and S Ψ(α) containing ∂S, respectively, which are homeomorphic to S 1,3 . For each separating curve β in Q, either β corresponds to an HBC in S or the pair {α, β} is an HBP in S. The same property holds for Q ′ and Ψ(α) in place of Q and α, respectively. It follows that ψ induces a superinjective map from C s (Q) into C s (Q ′ ), which is surjective by Theorem 1.1 in [20]. The first equality in the claim is proved. If b = {b 1 , b 2 } is an HBP in S with i(α, b) = 0 and α ∈ b, then any two of α, b 1 and b 2 form an HBP in S, and we have Ψ(α) ∈ ψ(b) by Lemma 2.6. The second equality in the claim thus holds.
We next assume that α separates the two components of ∂S. Let us denote by R 1 and R 2 the components of S α , and pick a curve β in R 2 with {α, β} a 1-HBP in S. We define R ′ 1 and R ′ 2 the components of S Ψ(α) with Ψ(β) ∈ V (R ′ 2 ). By Lemma 6.4, for any two vertices l 1 , l 2 of D(R 1 ), they form an edge of D(R 1 ) if and only if there exists a hexagon in CP s (S) satisfying the assumption in Proposition 6.1 and containing the HBPs {β, α}, {β, γ 1 } and {β, γ 2 }, where γ 1 and γ 2 are HBCs in R 1 defined by the arcs l 1 and l 2 , respectively. The same property holds for R ′ 1 , Ψ(α) and Ψ(β) in place of R 1 , α and β, respectively. The map ψ induces an injective simplicial map from D(R 1 ) into D(R ′ 1 ), which is surjective by Proposition 7.1. Similarly, ψ induces a simplicial isomorphism from D(R 2 ) onto D(R ′ 2 ). The first equality in the claim is thus proved. If b is an HBP in S with i(α, b) = 0 and α ∈ b, then b is a 2-HBP in S. Since Ψ(α) separates the two components of ∂S, we have Ψ(α) ∈ ψ(b). The second equality in the claim follows.
We thus proved that Ψ defines a superinjective map from C s (S) into itself, which is surjective by Theorem 1.1 in [20]. It follows that ψ is surjective.
8.2. The case p ≥ 3. We first prove the following: Proposition 8.11. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then the following assertions hold: (i) The full subcomplex of CP n (S) spanned by all vertices corresponding to 2-HBCs and p-HBPs is connected. (ii) If p ≥ 3, then the full subcomplex of CP s (S) spanned by all vertices corresponding to 2-HBCs and p-HBPs is connected.
Proof. We follow the idea in Lemma 2.1 of [27] to prove connectivity of simplicial complexes on which PMod(S) acts, as in the proof of Lemma 7.6 (ii). It is known that PMod(S) is generated by Dehn twists about the curves described in Figure 9 (a) (see [10]). Let a = {a 1 , a 2 } denote the non-separating p-HBP in Figure 9 (b). For any 2-HBC α in S, there exists h ∈ PMod(S) such that α is disjoint from ha. To prove assertion (i), it thus suffices to show that for each curve γ in Figure 9 (a), t γ a and a can be connected by a path in CP n (S) consisting of vertices corresponding to p-HBPs and 2-HBCs. This is true because t β1 a and a can be connected via the 2-HBC c 1 in Figure 9 (b). Assertion (i) follows. Let b = {b 1 , b 2 } denote the separating p-HBP in Figure 9 (b). For any 2-HBC α in S, there exists h ∈ PMod(S) such that α is disjoint from hb. For any separating p-HBP b ′ in S, there exists h ′ ∈ PMod(S) such that b ′ is disjoint from h ′ c 1 . Since b is disjoint from c 1 , we have the path b ′ , h ′ c 1 , h ′ b in CP s (S). To prove assertion (ii), it thus suffices to show that for each curve γ in Figure 9 (a), t γ b and b can be connected by a path in CP s (S) consisting of vertices corresponding to p-HBPs and 2-HBCs. This is true because t α2 b and b can be connected via the 2-HBC c 2 in Figure 9 (b); for each j = 3, . . . , p, t αj b and b can be connected via c 1 ; and t β2 b and b can be connected via c 1 .
Theorem 8.12. Let S = S g,p be a surface with g ≥ 2 and p ≥ 3, and let φ : CP n (S) → CP n (S) and ψ : CP s (S) → CP s (S) be superinjective maps. Then φ and ψ are surjective.
Proof. In Lemmas 3.6 and 3.7, we have already shown that for each j and each k, the map φ preserves j-HBPs and k-HBCs, respectively. We prove surjectivity of φ by induction on p. For each 2-HBC α in S, φ induces a map between the links of α and φ(α) in CP n (S). This induced map can be identified with a superinjective map from CP n (S g,p−1 ) into itself, which is surjective by the hypothesis of the induction. The image of φ thus contains all vertices of the link of φ(α). For each p-HBP b in S, φ induces a map between the links of b and φ(b) in CP n (S). For each curve β in b, the restriction of this induced map to the set of HBCs and HBPs containing β can be identified with a superinjective map from C(S 0,p+2 ) into itself. Since the latter map is surjective by Theorem 2 in [3], the image of φ contains all vertices of the link of φ(b). By Proposition 8.11 (i), φ is surjective.
Similarly, we can prove surjectivity of ψ by using Proposition 8.11 (ii).
Corollary 8.13. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then any superinjective map from CP(S) into itself is surjective.
8.3. Superinjective maps from CP n (S) into CP(S). Let S = S g,p be a surface with g ≥ 2 and p ≥ 2, and let φ be an automorphism of CP n (S). We denote by C nc (S) the full subcomplex of C(S) spanned by all vertices corresponding to either a non-separating curve in S or an HBC in S. Using Lemmas 3.9 and 5.3 and following a part of the proof of Theorem 6.1 in [22], we obtain a simplicial automorphism Φ of C nc (S) with φ({α, β}) = {Φ(α), Φ(β)} for any non-separating HBP {α, β} in S and with φ(γ) = Φ(γ) for any HBC γ in S. As asserted in Remark in p.102 in [15], Φ extends to a simplicial automorphism of C(S) and is thus induced by an element of Mod * (S) by Theorem 1 in [17]. We proved the following: Theorem 8.14. Let S = S g,p be a surface with g ≥ 2 and p ≥ 2. Then any automorphism of CP n (S) is induced by an element of Mod * (S).
Combining Lemma 3.10 and Theorems 8.2 and 8.12, we obtain the following: