数理解析研究所講究録
第 1991 巻 2016 年 43-53

43

COMBINAT0RIAL SUPERRIGIDITY FOR GRAPHS ASSOCIATED TO
SURFACES
JAVIER ARAMAYONA

ABSTRACT. We introduce a number of conditions on graphs built from arcs and/or
curves on a topological surface. We prove that, under these conditions, every injective alternating simplicial map between two of these graphs is induced by a subsurface
inclusion between the underlying surfaces.
We then explain why pants graphs satisfy these conditions, thus recovering the superrigidity result obtained in [1]. We also describe a more sophisticated version of theconditions that gives a similar result for flip graphs, as obtained in [2]. Finally, we
explain why Hatcher-Thurston graphs and curve graphs do not satisfy the conditions,and explain a more general rigidity phenomenon for Hatcher-Thurston graphs, recently
obtained by J. Hern\’andez [7].

1. INTRODUCTION

uller spaces and mapping class
A large number of problems in the study ofgroups may be understood in combinatorial terms, through the various graphs of arcs
and/or curves that one can associate to a surface. Prominent examples of such graphs
include the curve graph, the arc graph, the pants graph, etc.
A common feature of these graphs is that they are simplicially rigid: every automorphism of the graph is induced by an element of the mapping class group of the underlying
surface. In fact, Brendle-Margalit [3] have recently proved that this is the case for any
complex of curves that satisfies certain general conditions.
Expanding on these rigidity results, it was shown in [1] that pants graphs (see Section4) are superrigid. More concretely, if has complexity at least 2, then every injective
simplicial map
between pants graphs is induced by a subsurface inclusion$Teich\fbox{Error::0x0000}$$S$$\mathcal{P}(S)arrow \mathcal{P}(S’)$$S\mapsto S’.$

Using a similar array of ideas, although in a significantly more complicated setting, theanalogous result holds for flip graphs of surfaces (see again Section 4): if is “complicatedenough”, then every injective simplicial map between flip graphs is induced by a subsurface
inclusion [2].
The purpose of this note is to abstract out”’ the ideas behind the proof of the main
result in [1], in terms of rather general conditions on the class of graphs associated to thesurface, with the hope that these ideas may be applicable to other classes of graphs.
Rather informally, suppose that to each connected orientable surface we have associ, built from arcs and/or curves on , which satisfies certain
ated a simplic\’ial graphaxiomatic conditions: these arc the conditions $(G1)-(G7)$ described in the next section.
In this setting, we will prove that a certain class of injective maps between two of thesegraphs are always induced by an inclusion between the underlying surfaces:$S$$\langle$$S$$\mathcal{G}(S)$Received December 31, 2015.

$S$

44
Theorem 1.1. Suppose the class of graphs
satisfies the conditions $(Gl)-(G7)$
introduced in Section 2. Supposeandare connected orientable surfaces for which
there exists an injective alternating map. Then is induced by a subsurface$S\mapsto S’.$
inclusion$\mathcal{G}$

$S’$

$S$

$\mathcal{G}(S)arrow \mathcal{G}(S’)$$\phi$

Remark 1.2. In recent work, Erlandsson-Fanoni [4] have proved that every injective
simplicial map between two “multicurve graphs”’ is induced by a subsurface inclusion,
subject to certain conditions on the topology of the underlying surfaces and the numberof curves defining a vertex of the graph. As the authors point out, it is not true that anarbitrary injection between multicurve graphs arises in this way. In particular, the graphs
considered in [4] do not satisfy the axioms given in Section 2, more concretely axiom (G7);see [4] for details.
The plan of the paper is as follows. In Section 2 we will introduce all the necessary
background and terminology, as well as the conditions $(G1)-(G7)$ mentioned in Theorem
1.1. In Section 3 we will give a proof of Theorem 1.1. Finally, in Section 4, we will explore
a number of known classes of graphs (e.g. curve graphs, pants graphs, etc), explaining ineach case whether they (do not) satisfy the conditions $(G1)-(G7)$ of Theorem 1.1.
Acknowledgements. These ideas sprouted during a visit to the Universidad de Zaragoza
under a 2014 Campus Iberus grant. I would like to thank the Campus Iberus scheme forfinancial support, and the University of Zaragoza for its hospitality. I feel indebted to T.
Koberda and H. Parlier for many insightful exchanges. I am also grateful to V. Erlandsson
and F. Fanoni for conversations.

2. GRAPHS
2.1. Arcs and curves. Throughout,will denote a connected, orientable surface offinite topological type, and $Pa$ (possibly empty) set of marked points on . By a curveon we mean a free isotopy class of essential simple closed curves on ; here, a simple
closed curve is said to be essential if it does not bound a disk with at most one marked
point. By an arc we mean an isotopy class, relative endpoints, of simple arcs on withboth endpoints on , and whose interior is disjoint from . The arc and curve complex$AC(S)$ is the simplicial complex whose -simplices are sets of $d+1$ pairwise disjoint
arcs/curves on $S.$
$S$

$S$

$S$

$S$

$S$

$P$

$P$

$d$

2.2. A class of graphs. We now proceed to describe the class of graphs that we willconsider. To each orientable surface we will associate an abstract simplicial graphbuilt from arcs and/or curves on , and which satisfies the conditions $(G1)-(G7)$ below.
The first one describes what is the vertex set of:(G1) There exists a positive integer $d=d(\mathcal{G}(S))$ such that each vertex of
is a$(d-1)$ -simplex in. In other words, every vertex ofhas the form$S$$\mathcal{G}(S)$$S$$\mathcal{G}(S)$$\mathcal{G}(S)$$\mathcal{A}C(S)$$v$$\mathcal{G}(S)$$\{a_{1}, \cdots, a_{d}\},$

where eachis either an arc or a curve on . We stress the fact that may
depend on $S.$
The next condition informally asscrts that edges ofcorrespond to “flipping” anarc or a curve on :(G2) For every vertices
with $v\in 1k(u)$ , the cardinality of $u\cap v$ is $d-1.$$S$$a_{i}$$\mathcal{G}(S)$$S$$u,$ $v\in \mathcal{G}(S)$

$d$

45
Also, we want to consider connected graphs only:(G3) The graphis connected.
Roughly speaking, the next condition ensures that one can flip every element of every:
vertex of(G4) For every vertex
and all $a\in v$ , there exists $v’\in 1k(v)$ with$\mathcal{G}(S)$$\mathcal{G}(S)$$v\in \mathcal{G}(S)$$v\backslash (v\cap v’)=\{a\}.$Here, lk(v) denotes the link of the vertex , that is the set of vertices adjacent to it. Before
we state the next cond\’ition, we need the following definition:
Definition 2.1 (Extendable set). Let $MC\mathcal{A}C(S)$ be a non-empty finite set. We say. We say that $M$ has
withthat $M$ is extendable if there exists a vertex of$M’$$k\geq1$
on such that
deficiency
if there exists an extendable set
has elements
and $M\cup M’$ is a vertex of.
has deficiency , then it has
Remark 2.2. Observe that if an extendable set on$u’,$$d(\mathcal{G}(S))-k$ elements. Observe also that if
are vertices with $u’\in 1k(v)$ then
$v$

$v$

$M\subset\wedge v$$\mathcal{G}(S)$$M^{l}$$S$$k$$\mathcal{G}(S)$

$S$

$k$

$v$

$u,$

$u,$

$u\cap u’=u\cap u’\cap v$

is either empty or else is an extendable set, in which case it has deficiency 1 or 2.

The following condition asserts that the graphs
sidering subsurfaces.
(G5) If is an essential subsurfacc of $S’$ , thenextendable set on then$S$$\mathcal{G}\langle S$) behave well with respect to con-$\mathcal{G}(S)\subset \mathcal{G}(S’)$. Moreover, if $M$ is an$S$$\mathcal{G}_{M}(S)\cong \mathcal{G}(S-M)$,

that
spanned by those vertices of
wheredenotes the subgraph ofcontain $M.$:
The next property provides a base case”’ for the superrigidity of the graphs$andd(\mathcal{G}(S))=d(\mathcal{G}(S’))$$(G6\rangle Let S, S’ be$ surfaces, with. there exists anconnected
injective simplicial map$\mathcal{G}_{M}(S)$$\mathcal{G}(S)$$\mathcal{G}(S)$$\langle$$\mathcal{G}(S)$$S$$\mathcal{G}(S)arrow \mathcal{G}(S’)$

then $S’$ is the disjoint union of connected surfaces S\’i, .. . , , in such way that, up
to reordering indices:(a)for $i=2$ , . . . , , andis induced by a homeomorphism(b) The restricted (injective) map$S_{k}’$$k$$\mathcal{G}(S_{i})=\emptyset$$\mathcal{G}(S)arrow \mathcal{G}(S_{1}’)$S$arrow$

S\’i.

We now proceed to state our final condition, which guarantees the existence of certain
special closed paths in. Before doing so we need the following definition, which is adirect translation to our setting of the concept of (alternating tuple”’ for the pants graphfrom [1].
$\mathcal{G}(S)$consists of $n\in$Definition 2.3 (Alternating circuit). An alternating circuit insuch that (counting indices mod, 5 vertices ,in, and paths , . . . ,}$n)$ :(1)
is a path from to$\tau$

$\{4$

$\}$

$v_{1}$$\gamma_{i}$$v_{n}$$\gamma_{1}$$v_{\iota’}$$v_{i+1}.$$\gamma_{n}$$\mathcal{G}(S)$$\mathcal{G}(S)$46(2)
if $|i-j|>1$ , and$set\cap\{u|u\in\gamma_{i}\}$(3) Theis an extendable set of deficiency 1.
$\gamma_{i}\cap\gamma_{i+1}=\{v_{i+1}\}.$$\gamma_{i}\cap\gamma_{j}=\emptyset$(4) If2.

$u\in\gamma_{1}-\{v_{i+1}\}$

and$v\in\gamma_{i+1}-\{v_{i+1}\}$

then$u\cap v$

is an extendable set of deficiency

Informally, exactly $d-1$ arcs/curves do not change along, and it is one of thesearcs/curves that is “flipped” when passing from to. We remark that the existenceof an alternating circuit in
immediately implies that
. The fact that$n\leq 5$ in the definition above has the following observation as an immediate consequence;
we state it as a separate lemma as it will be useful in the proof of Theorem 1.1:$\gamma_{i}$$\gamma_{i}$$\gamma_{i+1}$$d(\mathcal{G}(S))\geq 2$$\mathcal{G}(S)$Lemma 2.4. Suppose$\tau\subseteq \mathcal{G}(S)$is an alternating circuit. Then
$M=\cap\{u|u\in\tau\}$is either empty or else is an extendable set of deficiency 2.

Armed with the definition above, the last condition is:(G7) Letbe vertices with $w\in 1k(v)$ , and such that $u\cap v\cap w$ is an extendable
set of deficiency 2. Then there exists an alternating circuit incontaining$u,$ $v,$ $w$$u,$$\mathcal{G}(S)$$u, v, w.$

2.3. Alternating maps. Before closing this section, we define the notion of an alternating map, and observe that such maps send alternating circuits to alternating circuits.
Definition 2.5 (Alternating map). We say that a map :if, for every
vertices ofwith $w\in 1k(v)$ , we have:$\phi$$u,$ $v,$ $w$$u\cap v\cap w$$\mathcal{G}(S)$$\mathcal{G}(S)arrow \mathcal{G}(S’)$

is alternating$u,$

has deficiency 2 $\Leftrightarrow\phi(u)\cap\phi(v)\cap\phi(w)$ has deficiency 2.

The following is an immediate consequence of the definitions of alternating map andalternating circuit:Lemma 2.6. Let
circuit$\tau\subset \mathcal{G}(S)$:, the path$\phi$$\mathcal{G}(S)arrow \mathcal{G}(S’)$

be an injective alternating map. For everlt alternating
is an alternating circuit.

$\phi(\tau)\subseteq \mathcal{G}(S’)$

be an alternating circuit. Making reference to the notation in thedefinition of alternating circuit above, let , . . . , be the vertices and , . . . , be thepaths between them, with $n\in\{4$ , 5 . We consider the pathagainwith respect to the same notation, has vertices
,...,
,...,
and paths

Proof. Let$\tau\subset \mathcal{G}(S)$$v_{1}$$v_{n}$$\gamma_{1}$$\gamma_{n}$$\phi(\tau)\subset \mathcal{G}(S’)which_{\}}$$\}$$\phi(v_{1})$$\phi(v_{n})$$\phi(\gamma_{1})$$\phi(\gamma_{n})$between them.
We now verify thatsatisfies conditions (1) $-(4)$ in Definition 2.5. First, it isimmediate that it satisfies (1), since is simplicial, and (2), as it is injective. For (3),let , . . . ,be the vertices of , where $w_{1}=v_{i}$ and $w_{k}=v_{i+1}$ . Since is alternating,$\phi(\tau)$$\phi$$w_{1}$$w_{k}$

we have that$\phi$$\gamma_{i}$has deficiency 1. Since the same is true for, it follows that$\phi(w_{j})\cap\phi(w_{j+1})\cap\phi(w_{j+2})$$\phi(w_{j+1})\cap\phi(w_{j+2})\cap\phi(w_{j+3})$$\phi(w_{j})\cap\phi(w_{j+1})\cap\phi(w_{j+2})\cap\phi(w_{j+3})$

also has deficiency 1. Repeating this argument we obtain thatsatisfies property (3).
This, combined with the fact that is alternating, implies that it also satisfies (4), whichfinishes the proof.
$\phi(\tau)$$\phi$$\square$47
3. PROOF OF THEOREM 1.1
In this section we will prove of Theorem 1.1. A large part of the argument needed iscontained in the following lemma:

Lemma 3.1. Suppose that the class of graphs
satisfies conditions $(Gl)-(G7)$ above,and that. Let
befor which there exists an alternating injectivemap$\mathcal{G}$$d(\mathcal{G}(S))\geq 2$$S,$ $S^{l}$$surface\mathcal{S}$$\phi:\mathcal{G}\langle 8)arrow \mathcal{G}(S’)$

Thentendable set $M$ onvertex of.

$d(\mathcal{G}(S\rangle)\leq d(\mathcal{G}(S’))$$v$. Moreover, if the inequality is strict then there exists an ex-, with $d(\mathcal{G}(S’))-d(\mathcal{G}(8))$ elements, such that $MC\phi(v)$ for every$\mathcal{G}(S)$arbitrary vertex of, which we will use to identify the extendable setof the statement. By (G1), we may write

Proof. Fix$M$$S^{J}$

.

$an$

$v$

$\mathcal{G}(S)$$v=\{a_{1}, \cdots , (x_{d}\},$

where
that

$d=d(\mathcal{G}(S\rangle)$. From (G2) and (G4), we know that there exist $v_{1,}v_{d}\in 1k(v)$ such$v\backslash (v\cap v_{i})=\{a_{i}\}$for all $i=1$ , , . By construction, if $i\neq j$ thenhas deficiency 2, andtherefore
also has deficiency 2 as is alternating. It follows that theintersection of distinct’s is either empty or else is an extendable set of deficiency. Since every vertex ofelements, we deduce thathas$d$$v_{i}\cap v_{j}=v\cap v_{i}\cap v_{j}$$\cdots$$\phi(v)\cap\phi(v_{i})\cap\phi(v_{j})$
$k$

$k$

$\phi$$\phi(v_{i})$$\mathcal{G}(S’)$$d^{l}=d(\mathcal{G}(S’))$$d\leq d’,$so the first part of the theorem holds. Suppose from now on that $d<d’$ , which in turnimplies that
$M:=\phi(v_{1})\cap..

.\cap\phi(v_{d})$is is an extendable set of $d’-d$ elements.
Once we have identified a candidate extendable set $M$ on , we now claim if is any, then $M\subset\phi(w)$ for every vertex $w\in 1k(u)$ . We first prove the claim in thevertex of
special case when $u=v$ . Let $w\in$ &(v), and , . . . , be the vertices identified above.
Then there exists exactly one $i=1$ , . . . , such that
$S$

$u$

$\mathcal{G}(S)$$v_{1}$$v_{d}$$d$$v\cap v_{i}=v\cap w=\{a_{i}\}.$

Since$\phi$is alternating, then $\phi(v)\cap\phi(v_{i})\cap\phi(w)$ has deficiency 1, and as such
$M\subseteq\phi(v)\cap\phi(v_{i})=\phi(v)\cap\phi(v_{i})\cap\phi(w)$.

In particular, $M\subset\phi(w)$ , asConsider now the general case $u\neq v$ . As
is connected, by (G3), it suﬃces toestablish the claim in the case when $u\in 1k(v)$ . Let $w\in 1k(u)$ ; we want to show that
$M\subseteq\phi(w)$ . To this end,
observe first that $u\cap v\cap w$ is an extendable set of deficiency 1$u\capv\cap w$ has deficiency 1. In this case, $\phi(u)\cap\phi(v)\cap\phi(w)$ hasor 2. Suppose first that
deficiency 1 as well, since is alternating, and therefore $M\subseteq\phi(w)$ , as$desi_{1}\cdot ed.$$\mathcal{G}(S)$$\phi$$Mc\phi(u)\cap\phi(v)=\phi(u)\cap\phi(v)\cap\phi(w)$.

Therefore, it remains to consider the case when $u\cap v\cap w$ has deficiency 2, which inturn implies that $\phi(u)\cap\phi(v)\cap\phi(w)$ has deficiency 2 also, again since is alternating.
$\phi$

48$w.$
containing
By condition (G7) above, there exists an alternating circuit
is also an alternating circuit. Let be the uniqueUsing Lemma 2.6, the image pathvertex of that is distinct from and spans an edge with , noting that $M\subset\phi(z)$ by
the discussion in the paragraph above; in particular,$\tau\subset \mathcal{G}(S)$

$v$

$u$

$\tau$$u,$ $v,$$z$$\phi(\tau)$.
As $\phi(z)\cap\phi(v)\cap\phi(u)$ has deficiency 2, Lemma 2.4 tells us that
$M\subset\phi(z)\cap\phi(v)\cap\phi(u)$$\phi(z)\cap\phi(v)\cap\phi(u)=\phi(z)\cap\phi(v)\cap\phi(u)\cap\phi(w)$and thus$M\subseteq\phi(w)$,, as desired.
$\square$Remark 3.2. Observe that, in fact, in the above lemma we have not made use of conditions (G5) and (G6), and hence the result holds in slightly more generality.

At this point, we are in a position to prove Theorem 1.1:

Proof of Theorem 1.1. Let$S$

and $S’$ be connected orientable surfaces for which there exists

an injective alternating map.
Write $d=d(\mathcal{G}(S))$ and $d’=d(\mathcal{G}(S’))$ . By Lemma 3.1, we know that$\phi:\mathcal{G}(S)arrow \mathcal{G}(S’)$$d\leq d’.$If $d=d’$ , then (G6) implies$S’=S_{1}’u\ldots uS_{k}’,$for $i=2$ , . . . , , and the restricted
in such way that, up to reordering indices,(S\’i) is induced by a homeomorphism $Sarrow S_{1}’$ . As a consequence,(injective) map (S)the map is induced by a subsurface embedding $S\mapsto S’$ , as we wanted to prove.
On the other hand, if $d<d’$ then Lemma 3.1 again implies that there exists an extendable set $M\subset S’$ , with $d’-d$ elements, such that$k$$\mathcal{G}(S_{i})=\emptyset$$\mathcal{G}$$arrow \mathcal{G}$$\phi$$\phi(\mathcal{G}(S))\subseteq \mathcal{G}_{M}(S’)\cong \mathcal{G}(S’-M)$,

where the above isomorphism is guaranteed by condition (G5). Now, $d(\mathcal{G}(S’-M))=d,$and we conclude as above with $S’-M$ instead of $S’.$$\square$

4. EXAMPLES AND NON-EXAMPLESIn this section we will discuss certain well-known classes of graphs of arcs or curves on
and, in each case, we will explain why they (do not) satisfy the conditions $(G1)-(G7)$
described above. To the best of our knowledge the only example of a class of graphs thatsatisfy such conditions is that of pants graphs of surfaces; see below. Thus we ask:$S$

Problem 4.1. Is there a natural class of graphs associated to a surface, other than pants
graphs, that satisfies conditions $(Gl)-(G7)$ abov$e^{}?$

Next, we will examine the interesting case of the flip graph, as it does not satisfy
conditions (G1) $-(G7)$ but still forms a superrigid class of graphs, as shown in [2].
Although the ideas of the proof of this result are similar in spirit to those discussed here,
the situation is significantly more involved, especially to due to the presence of vertices
with non-isomorphic links.

49
Next, we discuss the case of Hatcher-Thurston graphs and explain why they do notsatisfy conditions $(G1)-(G7)$ . We will comment on a more general classification, due toJes Hern\’andez [7], of the possible simplicial injections between two Hatcher-Thurston
graphs in the case where the domain surface is closed.
Finally, we discuss the case of curve graphs, and explore some possible versions ofsupel.rigidity for them.
$\mathfrak{U}S ノ$4.1. Pants graphs. Let be a connected orientable surface. The pants graphisthe simplicial graph whose vertices are pants decompositions on , up to isotopy, andonly if they are related bywhere two such decompositions are adjacent inif
an elementary move. Recall that the latter means that the two decompositions have all
but one curves in common, and the remaining two curves either intersect once and fill aone-holed torus, or intersect twice and fill a four-holed sphere. See Figure 1.
$S$$\mathcal{P}(S)$$S$$\mathcal{P}(S)$$a1$

FIGURE 1. The two types of elementary move.

We now explain why
satisfies the conditions $(G1)-(G7)$ above, provided hascomplexity at least 2. In a nutshell, and rather informally, the reason boils down to thefact thatis “built from”’ Farey graphs, which are simplicially rigid; moreover, there
is a bijective correspondence between Farey graphs inand multicurves of cardinality
one less than the complexity of $S.$
First,
evidently satisfies (G1) and (G2), with$S$$\mathcal{P}(S)$$\mathcal{P}(S)$$\mathcal{P}(S)$$\mathcal{P}(S)$$d=d(\mathcal{P}(S))=3g-3+p,$

and are, respectively, the genus and number of punctures of . The fact thatis connected is due originally to Hatcher-Thurston [5]; see also [8] for a combinatorial proof. The fact thatsatisfies (G4) is also obvious: every curve in a pants
decomposition may be the subject of an elementary move. Condition (G5) is easy as well:
if is an essential
face of , then a pants decomposition of extends (in a nonunique way) to a pants decomposition $P’$ of $S’$ by first choosing a pants decomposition$M$ of $S’-S$ and then setting $P^{J}=P\cup M.$
where

$g$

$S$

$p$

$\mathcal{P}(S)$$\mathcal{P}(S)$$S$$sub_{Su1}\cdot$

$S’$

$P$

$S$

50
As mentioned above, all the diﬃculty is reduced to proving thatsatisfies (G6)
is precisely the complexity ofand (G7). We first treat condition (G6). Since
in this particular case condition (G6) asserts:, with connected, and(G6) Let $S’$ be orientable surfaces of the same complexity
suppose there is an injective simplicial map. Then$\mathcal{P}(S\rangle$$S,$$d(\mathcal{P}(S))$$S,$$\geq 2$$S$$\mathcal{P}(S)arrow \mathcal{P}(S)$$S’=S_{1}’u\ldots uS_{k}’$in such way that:(1)$\mathcal{P}(S_{i})=\emptyset$

for $i=2$ , . .. , , and$k$(2) The restricted (injective) map$\mathcal{P}$(S)$arrow \mathcal{P}$(S\’i) is induced by a homeomorphism$Sarrow S_{1}’.$

Let $S,$ $S’$ be surfaces as above, andfact that$\phi$:$\mathcal{P}(S)arrow \mathcal{P}(S’)$

an injective simplicial map. The$S’=S_{1}’u\ldots uS_{k}’,$with (up to reordering the indices)
for $i=2$ , . .. , is contained in the proof of
Theorem 3(c) of [1], whose argument essentially boils down to the combination of Lemma
3.1 above and the fact that Farey graphs are simplicially rigid.
Thus we get that, abusing notation, gives an injective simplicial map$k$$\mathcal{P}(S_{i})=\emptyset$$\phi$$\phi:\mathcal{P}(S)arrow \mathcal{P}(S_{1}’)$.

Now, S\’i has the same complexity as , by Theorem 3(b) of [1], whose proof is essentiallycontained that of Lemma 3.1. Therefore. Again by the rigidityof Farey graphs (for details, see Claim III of the proof of Theorem 3 of [1]), the map(S\’i) is also surjective and therefore an isomorphism. Since: (S)the classification of pants graphs up to isomorphism (which appears as Lemma 12 in [1])implies that there is a homeomorphism(and thus a subsurface inclusion $S\mapsto S’$ )which induces , as claimed.
Finally, the fact thathas (G7) is Lemma 10 of [1], although the terminology
is diﬀerent; namely, in $[1],($ alternating circuits”’ are called “alternating -tuples (with$n=4$ , 5
See the case of the Hatcher-Thurston graph below for the proof of theanalogous statement, which follows a similar, although simpler, argument.
In the light of the discussion above, we obtain from Theorem 1.1 that, so long as
has complexity 2, every alternating injective simplicial map
is induced bya subsurface inclusion $S\mapsto S’$ . Moreover, it turns out that every injective map between
pants graphs is always alternating (see Lemma 7 of [1], whose proof rests again upon thesimplicial rigidity of Farey graphs) and therefore we have the main result in [1]:$S$$d(\mathcal{P}(S))=d(\mathcal{P}(S_{1}’))$$\phi$$d(\mathcal{P}(S))\geq 2,$$arrow \mathcal{P}$$\mathcal{P}$$Sarrow S_{1}’$$\phi$$\mathcal{P}(S)$

$n$

$)$

$S$

$\mathcal{P}(S)arrow \mathcal{P}(S)$Theorem 4.2 ([1]). Let $S’$ be connected orientable surfaces, such that has complexity
at least 2. If there exists an injective simplicial map :then there exists
a subsurface inclusion $S\mapsto S’$ that induces
$S$

$S,$

$\phi$$\mathcal{P}(S)arrow \mathcal{P}(S’)$$\phi.$

4.2. Flip graphs. Let be a compact, connected and orientable surface, of genus $g\geq 0$with $b\geq 0$ boundary components. Moreover, assume that has $p+q>0$ marked points,, subject to the condition thatwith $p\geq 0$ in the interior of and the other $q\geq 0$ inevery component ofmust contain at least one marked point.
A triangulation on is a set of arcs on that is maximal with respect to inclusion.
Observe that a triangulation contains exactly $d(S)=6g+3b+3p+q-6$ arcs. The
$S$

$S$

$S$

$\partial S$$\partial S$

$S$

$S$

51
is the simplicial graph whose vertices are triangulations of , and where
two triangulations are adjacent if and only if they share exactly $d(S)-1$ arcs. Note
this implies that the remaining two arcs intersect exactly once; we say that the two
is locally finite, as every vertex has
triangulations diﬀer by a “fiip” Observe thatvalence at most (but not always equal to) $d(S)$ .
Flip graphs satisfy some, but not all, of the conditions $(G1)-(G7\rangle$ . The major obstaclein this direction is the presence of triangulations with “unflippable” arcs. More concretely,
there are triangulations which contain an arc with the property that there does notexist any vertex withflip graph$S$$\mathcal{F}(S)$$\mathcal{F}(S)$

$a$

$v$

$v’$

$v-(v\cap v’)=\{a\}$).
(see Figure 2). In other words, condition $(G4)$ does not hold forsatisfies (G1) and (G2) with $d=6g+3b+3p+$
It is immediate, however, thathas properties (G3) (i.e. it is connected) and (G5).
$q-6$ . Similarly, one sees that$\mathcal{F}\langle S$$\mathcal{F}(S)$$\mathcal{F}(S)$With considerable eﬀort, and as long as is not exceptional it is possible to bypass thesatisfies a weakening of condition (G7); seefailure of condition (G3) and prove that
Propositions 2.2 and 2.3 of [2]. Here, we say that the surface is exceptional if it is an
essential subsurface of (and possibly equal to) a torus with at most two marked points,
or a sphere with at most four marked points. This property turns out to be enough toshow, after a significant amount of work, that
also has property (G6), see Theorem
1.4 of [2].
At this point one may apply a similar strategy to the one described in the previous
section to prove that alternating injective maps between flip graphs are always inducedby subsurface inclusions. However, as was the case with pants graph, alternating injective
maps between flip graphs are automatically alternating, and thus one has the following$S$$\mathcal{F}(S\rangle$$S$$\mathcal{F}(S)$result, proved in [2]Theorem 4.3 ([2]). Suppose is non-exceptional. Then every injective simplicial map:
is induced by a subsurface inclusion $Sarrow S’.$$S$$\phi$$\mathcal{F}(S)arrow\overline{f-}(S’)$

FIGURE 2. An unflippable arc of a triangulation

4.3. Hatcher-Thurston graphs. Let be a connected orientable surface of genus $g\geq 2,$
possibly with punctures. A cut system on is a set $M$ of pairwise disjoint curves such
$S$

$S$

$g$

is homeomorphic to a spherethat the result of cutting open along the elements ofwith punctures.
is the simplicial graph whose vertices
The Hatcher-Thurston graph (or cut graph))
if and only if they
are cut systems on , and where two cut systems are adjacent inhave $g-1$ curves in common, and the remaining two curves intersect exactly once. The(in fact, a certain 2-complex obtained from it) was used by Wajnryb [10] tograph
study presentations of mapping class groups.
$M$

$S$

$\mathcal{K}(S)$$S$$\mathcal{K}(S)$$\mathcal{K}(8)$52
By construction,satisfies (G1), (G2) with $d(\mathcal{K}(S))=g$ . Wajnryb proved [10]thatis connected and thus satisfies (G3). The fact that it also satisfies (G4) is also
obvious. To verify (G5) we argue as in the case of pants graphs. Suppose we are given$S\subset S’$ ,and choose a cut system $M$ of $S’-S$ ; then every cut system of extends tothe cut system $v\cup M$ of $S’.$
To see that (G7) holds for, let
be vertices ofwith $w\in 1k(v)$ , suchthat $u\cap v\cap w$ is an extendable set of deficiency 2. As such, we may write:$\mathcal{K}(S)$$\mathcal{K}(S)$$v$$\mathcal{K}(S)$$u,$ $v,$ $w$$u=\{a’, b, C_{3}, .

$\mathcal{K}(S)$

.

.

$S$

$u,$

, c_{g}\},$$v=\{a, b, c_{3}, .

.., c_{g}\},$$w=\{a, b’, C_{3}, .

.., c_{g}\},$

andwith $i(a, a’)=1$ and $i(b, b’)=1$ . If $i(a’, b’)=0$ , then the closed path$uarrow varrow warrow Zarrow u$

is an alternating circuit (with $n=4$ ), where $z=\{a’, b’, c_{3}, . . . , c_{g}\}$ . So suppose that
. Choose a nonseparating curve such that$i(a’, b’)\neq 0$$b”$$i(b”, a)=i(b”, a’)=i(b”, c_{j})=0$

for all , and$j$$i(b”, b)=1.$

Consider the vertex $w’=\{a, bc_{3}, . . . , c_{g}\}$ . Now, and $w’$ may be connected by a pathinwhich misses and whose every vertex contains the curves $a’,$ , . . . , ; see,for instance, Lemma 3 of [6]. Considering the vertex$w$$\rho$$\mathcal{K}(S)$$w$$c_{3}$$z=\{a’, bc_{3}, .

.

$c_{g}$., c_{g}\},$

we see that the closed path$uarrow varrow warrow^{\rho}W’arrow Zarrow u$

is an alternating circuit (with $n=4$ again).
In spite of the surge of optimism after this discussion, we remark the statement ofTheorem 1.1 does not hold for Hatcher-Thurston graphs, as there exist injective maps
between Hatcher-Thurston graphs that are not induced by subsurface inclusions. To
construct examples of these, start with a closed surface of genus $g\geq 2$ and endow
with a hyperbolic metric. We realize every simple closed curve on by the uniquegeodesic in its isotopy class. The union of all such geodesics has measure zero, and thus
we can choose a point in the complement, thus obtaining an injective simplicial map
;
$S$

$S$

$S$

$p$

$\mathcal{K}(S)arrow \mathcal{K}(S-\{p\})$observe that there are no continuous injective maps $Sarrow S-\{p\}$ . We may now repeat
this process a finite number of times, and”attach” pairs of punctures on the new surface
to obtain, for any $g\geq 2$ , an injective simplicial map,
wheredenotes the surface of genus and with punctures. In ongoing work, Jes\’us
Hernandez [7] has proved that, in fact, every injective alternating map between HatcherThurston graph arises in this way, as long as the domain surface is closed and has genus
at least 3.
$\mathcal{K}(S_{g,0})arrow \mathcal{K}(S_{g’,n})$$S_{h,k}$

$h$

$k$

53
4.4. Curve graphs. The curve graph $C(S)$ is the simplicial graph whose vertices are(isotopy classes of essential simple closed) curves on , and where two such curves are
if they can be realized disjointly on
adjacent in$C(S)$
satisfies (G1) and (G2) with $d=d(C(S))=1$ . A pleasant exercise
We see thatshows that $C(S)$ is connected as long as has complexity at least 2.
Since there are no extendable sets with respect to $C(S)$ , we immediately get thatsatisfies (G4), (G5) and (G7).
However, curve graphs do not satisfy (G6), as there are simplicial injections between
curve graphs that do not arise from homeomorphisms, or even inclusions, between theunderlying surfaces. Indeed, using the same argument as in the case of Hatcher-Thurston
graphs, we see that there are injective simplicial maps
$C(S)arrow C(S-\{p\})$ ,which cannot be induced by a subsurface inclusion if is closed, for instance. Motivated)mentioned above, we ask:by the result of J. Hern\’andez on Hatcher-Thurston
$S$

$S.$

$C(S\rangle$$S$$C(S\rangle$$S$$gra\mathfrak{x}$$hs$) $arrow C(S-\{p\})$ be
Problem 4.4. Let be a closed surface of genus $g\geq 2$ . Let :$C(S-\{p\})arrow
C(S)$puncture-forgetting”
the natural
an injective simplicial map, and :map. Is it true thatis always an isomorphis$S$$\phi$$C\langle S$$7|$$\pi 0\phi$$m^{J}?$REFERENCES[1] J. Aramayona, Simplicial embeddings between pants graphs. Geometriae Dedicata, 144 (2010).
[2] J. Aramayona, T. Koberda, H. Parlier, Injective maps between flip graphs. To appear in Annalcs del’Institut Fourier.
[3] T. Brendle, D. Margalit, work in progress.
[4] V. Erlandsson, F. Fanoni, Simplicial embeddings between multicurve graphs, preprint.
[5J A. E. Hatcher, W. P. Thurston, A presentation for the mapping class group of a closed orientablesurface, Topology, 19 (1980)[6] E. Irmak, M Korkmaz, Automorphisms of the Hatcher-Thurston complex. Israel J. Math. 162 (2007[7] J. Hernandez, work in progress.
[8] A. Putman, A note on the connectivity of certain complexes associated to surfaces, Enseign. Math.
(2) 54 (2008)[9] K. J. Shackleton, Combinatorial rigidity in curve complexes and mapping class groups, Pacific Journalof Mathematics, 230, No. 1, 2007[10] B. Wajnryb, A simple presentation for the mapping class group of an orientable surface. Israel J.
Math. 45 (1983)$\rangle$

MATEM\’ATICAS, UNIVERSIDAD AUT\’oNOMA DE MADRIDDEPARTMENTO. es-mail address: javier.
$D\Sigma$$E$$ara\iota nayona\Phi ua\iota n$