DOI 10.1007/s10801-009-0210-3
Cluster expansion formulas and perfect matchings
Gregg Musiker·Ralf Schiffler
Received: 2 March 2009 / Accepted: 3 November 2009 / Published online: 19 November 2009
© Springer Science+Business Media, LLC 2009
Abstract We study cluster algebras with principal coefficient systems that are asso- ciated to unpunctured surfaces. We give a direct formula for the Laurent polynomial expansion of cluster variables in these cluster algebras in terms of perfect matchings of a certain graphGT ,γ that is constructed from the surface by recursive glueing of elementary pieces that we call tiles. We also give a second formula for these Laurent polynomial expansions in terms of subgraphs of the graphGT ,γ.
Keywords Cluster algebra·Triangulated surface·Principal coefficients· F-polynomial·Snake graph
1 Introduction
Cluster algebras, introduced in [17], are commutative algebras equipped with a dis- tinguished set of generators, the cluster variables. The cluster variables are grouped into sets of constant cardinalityn, the clusters, and the integernis called the rank of the cluster algebra. Starting with an initial cluster x= {x1, . . . , xn}(together with a skew symmetrizable integern×nmatrixB=(bij)and a coefficient vector y=(yi)
The first author is supported by an NSF Mathematics Postdoctoral Fellowship, and the second author is supported by the NSF grant DMS-0908765 and by the University of Connecticut.
G. Musiker (
)Department of Mathematics, Room 2-336, Massachusetts Institute of Technology, 77 Massachusetts Ave., Cambridge, MA 02139, USA
e-mail:musiker@math.mit.edu R. Schiffler
Department of Mathematics, University of Connecticut, 196 Auditorium Road, Storrs, CT 06269-3009, USA
e-mail:schiffler@math.uconn.edu
whose entries are elements of a torsion-free abelian groupP), the set of cluster vari- ables is obtained by repeated application of so-called mutations. Note that this set may be infinite.
It follows from the construction that every cluster variable is a rational function in the initial cluster variablesx1, x2, . . . , xn. In [17], it is shown that every cluster variableu is actually a Laurent polynomial in thexi, that is,ucan be written as a reduced fraction
u=f (x1, x2, . . . , xn) n
i=1xidi , (1)
wheref ∈ZP[x1, x2, . . . , xn] anddi ≥0. The right-hand side of (1) is called the cluster expansion ofuin x.
The cluster algebra is determined by the initial matrixBand the choice of the coef- ficient system. A canonical choice of coefficients is the principal coefficient system, introduced in [18], which means that the coefficient groupPis the free abelian group onngeneratorsy1, y2, . . . , yn, and the initial coefficient vector y= {y1, y2, . . . , yn} consists of thesengenerators. In [18], the authors show that knowing the expansion formulas in the case where the cluster algebra has principal coefficients allows one to compute the expansion formulas for arbitrary coefficient systems.
Inspired by the work of Fock and Goncharov [13–15] and Gekhtman, Shapiro, and Vainshtein [22,23] which discovered cluster structures in the context of Teichmüller theory, Fomin, Shapiro, and Thurston [16,20] initiated a systematic study of the clus- ter algebras arising from triangulations of a surface with boundary and marked points.
In this approach, cluster variables in the cluster algebra correspond to arcs in the sur- face, and clusters correspond to triangulations. In [32], building on earlier results in [31,33], this model was used to give a direct expansion formula for cluster variables in cluster algebras associated to unpunctured surfaces, with arbitrary coefficients, in terms of certain paths on the triangulation.
Our first main result in this paper is a new parameterization of this formula in terms of perfect matchings of a certain weighted graph that is constructed from the surface by recursive glueing of elementary pieces that we call tiles. To be more precise, let xγ be a cluster variable corresponding to an arcγin the unpunctured surface, and let dbe the number of crossings betweenγ and the triangulationT of the surface. Then γ runs throughd+1 triangles ofT and each pair of consecutive triangles forms a quadrilateral which we call a tile. So we obtaind tiles, each of which is a weighted graph, whose weights are given by the cluster variablesxτassociated to the arcsτ of the triangulationT.
We obtain a weighted graphGT ,γ by glueing the d tiles in a specific way and then deleting the diagonal in each tile. To any perfect matchingP of this graph we associate its weightw(P )which is the product of the weights of its edges, hence a product of cluster variables. We prove the following cluster expansion formula:
Theorem3.1
xγ=
P
w(P ) y(P ) xi1xi2. . . xid,
where the sum is over all perfect matchingsP ofGT ,γ,w(P )is the weight ofP, and y(P )is a monomial in y.
We also give a formula for the coefficientsy(P ) in terms of perfect matchings as follows. TheF-polynomialFγ, introduced in [18], is obtained from the Laurent polynomialxγ (with principal coefficients) by substituting 1 for each of the cluster variablesx1, x2, . . . , xn. By [32, Theorem 6.2, Corollary 6.4], theF-polynomial has constant term 1 and a unique term of maximal degree that is divisible by all the other occurring monomials. The two corresponding matchings are the unique two matchings that have all their edges on the boundary of the graphGT ,γ. With respect to the construction of Sect.3.2,P−is the matching ofGT ,γ using the western edge of tileS˜1. Now, for an arbitrary perfect matchingP, the coefficienty(P )is determined by the set of edges of the symmetric differenceP−P =(P−∪P )\(P−∩P )as follows.
Theorem5.1 The setP−P is the set of boundary edges of a (possibly discon- nected) subgraphGP ofGT ,γ which is a union of tilesGP =
j∈JSj. Moreover, y(P )=
j∈J
yij.
Note thaty(P−)=1. As an immediate corollary, we see that the corresponding g-vector, introduced in [18], is
gγ=deg
w(P−) xi1· · ·xid
.
Our third main result is yet another description of the formula of Theorem3.1in terms of the graphGT ,γ only, see Theorem6.1.
Theorem3.1has interesting intersections with work of other people. In [10], the authors obtained a formula for the denominators of the cluster expansion in typesA, D, andE, see also [4]. In [5–7], an expansion formula was given in the case where the cluster algebra is acyclic and the cluster lies in an acyclic seed. Palu generalized this formula to arbitrary clusters in an acyclic cluster algebra [28]. These formulas use the cluster category introduced in [3], and in [9] for type A, and do not give information about the coefficients.
Recently, Fu and Keller generalized this formula further to cluster algebras with principal coefficients that admit a categorification by a 2-Calabi–Yau category [21], and, combining results of [1] and [2,24], such a categorification exists in the case of cluster algebras associated to unpunctured surfaces.
In [8,26,34,35], cluster expansions for cluster algebras of rank 2 are given; in [11, 19,30], the caseAis considered. In Sect. 4 of [30], Propp describes two constructions of snake graphs, the latter of which are unweighted analogues for the case A of the graphsGT ,γ that we present in this paper. Propp assigns a snake graph to each arc in the triangulation of ann-gon and shows that the numbers of matchings in these graphs satisfy the Conway–Coxeter frieze pattern induced by the Ptolemy relations
on then-gon. In [25], a cluster expansion for cluster algebras of classical type is given for clusters that lie in a bipartite seed.
The formula fory(P )given in Theorem5.1also can be formulated in terms of height functions, as found in literature such as [12] or [29]. We discuss this connection in Remark5.3of Sect.5.
The paper is organized as follows. In Sect.2, we recall the construction of cluster algebras from surfaces of [20]. Section3contains the construction of the graphGT ,γ
and the statement of the cluster expansion formula. Section4is devoted to the proof of the expansion formula. The formula fory(P )and the formula for theg-vectors is given in Sect.5. In Sect.6, we present the expansion formula in terms of subgraphs and deduce a formula for theF-polynomials. We give an example in Sect.7.
2 Cluster algebras from surfaces
In this section, we recall the construction of [20] in the case of surfaces without punctures.
LetS be a connected oriented two-dimensional Riemann surface with boundary andM a nonempty finite set of marked points in the closure ofSwith at least one marked point on each boundary component. The pair(S, M)is called bordered sur- face with marked points. Marked points in the interior ofSare called punctures.
In this paper, we will only consider surfaces(S, M)such that all marked points lie on the boundary ofS, and we will refer to(S, M)simply as an unpunctured surface.
We say that two curves inSdo not cross if they do not intersect each other except that endpoints may coincide.
Definition 1 An arcγ in(S, M)is a curve inSsuch that (a) the endpoints are inM,
(b) γ does not cross itself,
(c) the relative interior ofγis disjoint from the boundary ofS, (d) γ does not cut out a monogon or a digon.
Curves that connect two marked points and lie entirely on the boundary ofSwith- out passing through a third marked point are called boundary arcs. Hence an arc is a curve between two marked points, which does not intersect itself nor the boundary except possibly at its endpoints and which is not homotopic to a point or a boundary arc.
Each arc is considered up to isotopy inside the class of such curves. Moreover, each arc is considered up to orientation, so if an arc has endpointsa, b∈M, then it can be represented by a curve that runs froma tob, as well as by a curve that runs frombtoa.
For any two arcsγ , γ inS, lete(γ , γ)be the minimal number of crossings of γ and γ, that is, e(γ , γ) is the minimum of the numbers of crossings of arcs α andα, whereαis isotopic toγ, andα is isotopic toγ. Two arcsγ , γare called compatible ife(γ , γ)=0. A triangulation ofSis a maximal collection of compatible arcs together with all boundary arcs. The arcs of a triangulation cut the surface into
Table 1 Examples of
unpunctured surfaces b g m surface
1 0 n+3 polygon
1 1 n−3 torus with disk removed
1 2 n−9 genus 2 surface with disk removed
2 0 n annulus
2 1 n−6 torus with 2 disks removed 2 2 n−12 genus 2 surface with 2 disks removed
3 0 n−3 pair of pants
triangles. Since (S, M)is an unpunctured surface, the three sides of each triangle are distinct (in contrast to the case of surfaces with punctures). Any triangulation hasn+melements,n of which are arcs in S, and the remaining melements are boundary arcs. Note that the number of boundary arcs is equal to the number of marked points. Each arc will correspond to a cluster variable, whereas each boundary arc will correspond to the multiplicative identity 1 in the cluster algebra.
Proposition 2.1 The numbernof arcs in any triangulation is given by the formula n=6g+3b+m−6, wheregis the genus ofS,bis the number of boundary compo- nents, andm= |M|is the number of marked points. The numbernis called the rank of(S, M).
Proof [20, 2.10].
Note thatb >0 since the set M is not empty. Table1 gives some examples of unpunctured surfaces.
Following [20], we associate a cluster algebra to the unpunctured surface(S, M) as follows. Choose any triangulationT, letτ1, τ2, . . . , τnbe theninterior arcs ofT, and denote them boundary arcs of the surface by τn+1, τn+2, . . . , τn+m. For any triangleΔinT, define the matrixBΔ=(bΔij)1≤i≤n,1≤j≤nby
bΔij=
⎧⎪
⎪⎪
⎪⎨
⎪⎪
⎪⎪
⎩
1 ifτiandτj are sides ofΔwithτj followingτiin the counter-clockwise order;
−1 ifτiandτj are sides ofΔwithτj followingτiin the clockwise order;
0 otherwise.
Note that this matrix is the transpose of the matrix defined in [20]. Then define the matrixBT =(bij)1≤i≤n,1≤j≤nbybij=
ΔbΔij, where the sum is taken over all trian- gles inT. Note that the boundary arcs of the triangulation are ignored in the definition ofBT. LetB˜T =(bij)1≤i≤2n,1≤j≤nbe the 2n×nmatrix whose uppern×npart isBT
and whose lowern×npart is the identity matrix. The matrixBT is skew-symmetric, and each of its entriesbij is either 0,1,−1,2, or−2, since every arcτ can be in at most two triangles. An example wherebij =2 is given in Fig.1.
Fig. 1 A triangulation with b23=2
LetA(xT,yT, BT)be the cluster algebra with principal coefficients for the tri- angulation T, that is, A(xT,yT, BT) is given by the seed (xT,yT, BT) where xT = {xτ1, xτ2, . . . , xτn} is the cluster associated to the triangulation T, and the initial coefficient vector yT =(y1, y2, . . . , yn) is the vector of generators of P= Trop(y1, y2, . . . , yn). We refer to [18, Definition 2.2] for the definition of tropical semifield.
For the boundary arcs, we definexτk=1,k=n+1, n+2, . . . , n+m.
For eachk=1,2, . . . , n, there is a unique quadrilateral inT \ {τk}in whichτk is one of the diagonals. Letτkdenote the other diagonal in that quadrilateral. Define the flipμkT to be the triangulation(T \ {τk})∪ {τk}. The mutationμkof the seedΣT in the cluster algebraAcorresponds to the flipμkof the triangulationT in the following sense: The matrixμk(BT)is the matrix corresponding to the triangulationμkT, the clusterμk(xT)is (xT \ {xτk})∪ {xτ
k}, and the corresponding exchange relation is given by
xτkxτ
k =xρ1xρ2y++xσ1xσ2y−,
wherey+, y−∈Pare some coefficients, andρ1, σ1, ρ2, σ2are the sides of the quadri- lateral in whichτk andτk are the diagonals, withρ1opposite toρ2, andσ1opposite toσ2, see [20].
For convenience, we recall the definition of mutation in the cluster algebra. We use the notation[i]+=max(i,0),[1, n] = {1, . . . , n}, and
sgn(i)=
⎧⎪
⎨
⎪⎩
−1 ifi <0;
0 ifi=0;
1 ifi >0.
Let⊕denote the addition inP.
Definition 2 (Seed mutations) Let(x,y, B)be a seed, and letk∈ [1, n]. The seed mutationμkin directionktransforms(x,y, B)into the seedμk(x,y, B)=(x,y, B) defined as follows:
• The entries ofB=(bij )are given by
bij=
−bij ifi=korj=k;
bij+sgn(bik)[bikbkj]+ otherwise. (2)
• The coefficient tuple y=(y1, . . . , yn)is given by
yj =
⎧⎨
⎩
yk−1 ifj=k;
yjyk[bkj]+(yk⊕1)−bkj ifj=k.
(3)
• The cluster x=(x1, . . . , xn)is given byxj =xj forj =k, whereasxk is deter- mined by the exchange relation
xk =yk
xi[bik]++ x[−i bik]+ (yk⊕1)xk
. (4)
3 Expansion formula
In this section, we will present an expansion formula for the cluster variables in terms of perfect matchings of a graph that is constructed recursively using so-called tiles.
3.1 Tiles
For the purpose of this paper, a tileSkis a planar four-vertex graph with five weighted edges having the shape of two equilateral triangles that share one edge, see Fig.2.
The weight on each edge of the tileSkis a cluster variable. The unique interior edge is called diagonal, and the four exterior edges are called sides ofSk. We shall useSk
to denote the graph obtained fromSk by removing the diagonal.
Now letT be a triangulation of the unpunctured surface(S, M). If τk∈T is an interior arc, thenτklies in precisely two triangles inT, henceτkis the diagonal of a unique quadrilateralQτkinT. We associate to this quadrilateral a tileSkby assigning the weightxkto the diagonal and the weightsxa, xb, xc, xdto the sides ofSkin such a way that there is a surjective mapφk:Qτk→Skwhich restricts to a homeomorphism between the respective interiors and which sends the arc labeledτi,i=a, b, c, d, k to the edge with weightxi, see Fig.2. Ifk=1, we require that φ1 is such that its restriction to the interior is an orientation-preserving homeomorphism, but fork >1, we allow the restriction ofφkto be any homeomorphism.
3.2 The graphGT ,γ
LetT be a triangulation of an unpunctured surface(S, M), and letγ be an arc in (S, M) which is not in T. If necessary, replaceγ with an isotopic arc so that γ intersects transversally each of the arcs inT and minimizes the number of crossings
Fig. 2 The tileSk
Fig. 3 Glueing tilesSkand Sk+1along the edge weighted x[γk]
with each of these arcs. An example is given in Fig.9. Choose an orientation onγ and lets∈Mbe its starting point, and lett∈Mbe its endpoint. We denote by
p0=s, p1, p2, . . . , pd+1=t
the points of intersection ofγ andT in order alongγ under the orientation chosen above. Leti1, i2, . . . , id be such thatpk lies on the arcτik∈T. Note thatik may be equal toijeven ifk=j. In the example in Sect.7, this sequence isi1, i2, i3, i4, i1, i2. LetS˜1,S˜2, . . . ,S˜d be a sequence of tiles so thatS˜k is isomorphic to the tileSik for k=1,2, . . . , d. In the example in Sect.7, this sequence isS1, S2, S3, S4, S1, S2.
Forkfrom 0 tod, letγkdenote the segment of the pathγfrom the pointpkto the pointpk+1. Eachγk lies in exactly one triangleΔk inT, and if 1≤k≤d−1, then Δkis formed by the arcsτik, τik+1, and a third arc that we denote byτ[γk]. Note that the arcτ[γk] may be a boundary arc. In the example in Sect.7, the triangle Δ0has sidesτ5, γ1, andτ4; the triangleΔ1has sidesγ2, γ1, andτ6.
We will define a graphGT ,γ by recursive glueing of tiles. Start withGT ,γ ,1∼= ˜S1, where, if necessary, we rotate the tileS˜1 so that the diagonal goes from northwest to southeast, and the starting pointp0ofγ is in the southwest corner ofS˜1. For all k=1,2, . . . , d−1, letGT ,γ ,k+1be the graph obtained by adjoining the tileS˜k+1to the tileS˜kof the graphGT ,γ ,k along the edge weightedx[γk], see Fig.3. We always orient the tiles so that the diagonals go from northwest to southeast. This implies that the tiles in odd positions have the orientation induced from the surface and the tiles in even positions have the opposite orientation. Note that the edge weightedx[γk]is either the northern or the eastern edge of the tileS˜k.
Finally, we defineGT ,γ to beGT ,γ ,d.
LetGT ,γ be the graph obtained fromGT ,γ by removing the diagonal in each tile, that is,GT ,γ is constructed in the same way asGT ,γ but using the graphsSikinstead ofSik. For an example see, Fig.10.
A perfect matching of a graph is a subset of the edges so that each vertex is covered exactly once by an edge in the perfect matching. We define the weightw(P ) of a perfect matchingP ofGT ,γ to be the product of the weights of all edges inP. 3.3 Cluster expansion formula
Let(S, M)be an unpunctured surface with triangulationT, and letA=A(xT,yT, B) be the cluster algebra with principal coefficients in the initial seed(xT,yT, B)defined in Sect.2. Take an arbitrary cluster variable inAthat is not in the initial cluster x.
Since each cluster variable inAcorresponds to an arc in(S, M), we can denote our
cluster variable byxγ whereγ is an arc not inT. Choose an orientation ofγ, and letτi1,τi2, . . . , τid be the arcs of the triangulation that are crossed byγ in this order, with multiplicities possible. LetGT ,γ be the graph constructed in Sect.3.2.
Theorem 3.1 With the above notation,
xγ=
P
w(P ) y(P ) xi1xi2. . . xid,
where the sum is over all perfect matchingsP ofGT ,γ,w(P )is the weight ofP, and y(P )is a monomial in yT.
The proof of Theorem3.1will be given in Sect.4.
4 Proof of Theorem3.1
We will use results of [32] to prove the theorem. Throughout this section, T is a triangulation of an unpunctured surface (S, M), γ is an arc in S with a fixed orientation, and s∈M is its starting point and t ∈M is its endpoint. Moreover, p0=s, p1, p2, . . . , pd+1=tare the points of intersection ofγandT in order along γ under the orientation chosen above, andi1, i2, . . . , id are such thatpk lies on the arcτik∈T. Letγk denote the segment ofγ between the pointspk, pk+1.
4.1 Complete(T , γ )-paths
Following [33], we will consider pathsα inS that are concatenations of arcs and boundary arcs in the triangulationT, more precisely, α=(α1, α2, . . . , α(α))with αi ∈T for i=1,2, . . . , (α), and the starting point ofαi is the endpoint ofαi−1. Such a path is called aT-path.
We call aT-pathα=(α1, α2, . . . , α(α))a complete(T , γ )-path if the following axioms hold:
(T1) The even arcs are precisely the arcs crossed byγin order, that is,α2k=τik. (T2) For allk=0,1,2, . . . , d, the segmentγk is homotopic to the segment of the
pathα that starts at the pointpk, then goes alongα2k to the starting point of α2k+1, then alongα2k+1to the starting point ofα2k+2, and then along α2k+2 until the pointpk+1.
We define the Laurent monomialx(α)of the complete(T , γ )-pathαby x(α)=
iodd
xαi
ieven
xα−1
i .
Remark 4.1
• Every complete(T , γ )-path starts and ends at the same points asγ, because of (T2).
• Every complete(T , γ )-path has length 2d+1.
• For all arcsτ in the triangulationT, the number of times thatτ occurs asα2k is exactly the number of crossings betweenγ andτ.
• In contrast to the ordinary(T , γ )-paths defined in [33], complete(T , γ )-paths al- low backtracking.
• The denominator of the Laurent monomialx(α)is equal toxi1xi2· · ·xid.
Example 4.2 The following are two examples of complete(T , γ )-paths, in the situa- tion in Fig.9.
(τ5, τ1, τ2, τ2, τ2, τ3, τ7, τ4, τ5, τ1, τ2, τ2, τ8), (τ4, τ1, τ1, τ2, τ3, τ3, τ4, τ4, τ5, τ1, τ2, τ2, τ8).
4.2 Universal cover
Letπ: ˜S→S be a universal cover of the surfaceS, and letM˜ =π−1(M)andT˜= π−1(T ).
Chooses˜∈π−1(s). There exists a unique liftγ˜ ofγ starting ats. Then˜ γ˜ is the concatenation of subpathsγ˜0,γ˜1, . . . ,γ˜d+1 whereγ˜k is a path from a pointp˜k to a pointp˜k+1such thatγ˜kis a lift ofγk andp˜k∈π−1(pk)fork=0,1, . . . , d+1. Let
˜
t= ˜pd+1∈π−1(t ).
Fork from 1 to d, letτ˜ik be the unique lift ofτik running through p˜k, and let
˜
τ[γk] be the unique lift ofτ[γk] that is bounding a triangle inS˜ withτ˜ik andτ˜ik+1. Eachγ˜k lies in exactly one triangleΔ˜k inT˜. LetS(γ )˜ ⊂ ˜S be the union of the tri- anglesΔ˜0,Δ˜1, . . . ,Δ˜d+1, and letM(γ )˜ = ˜M∩ ˜S(γ )andT (γ )˜ = ˜T ∩ ˜S(γ ). Then (S(γ ),˜ M(γ ))˜ is a simply connected unpunctured surface of whichT (γ )˜ is a triangu- lation. This triangulationT (γ )˜ consists of arcs, respectively boundary arcs,τ˜ik,τ˜[γk] withk=1,2, . . . , d, and two boundary arcs incident to s˜ and two boundary arcs incident tot˜. The simple connectedness ofS(γ )˜ follows from the simple connected- ness of the universal cover and the fact that the vertices of each triangle lie on the boundary of the universal cover. The fact thatT (γ )˜ is a triangulation follows from the homotopy lifting property ofS. Moreover, this triangulation does not contain any˜ internal triangles, since eachτ˜[γk]is a boundary arc.
The underlying graph ofT (γ )˜ is the graph with vertex setM(γ )˜ and whose set of edges consists of the (unoriented) arcs inT (γ ).˜
By [32, Sect. 5.5], we can compute the Laurent expansion ofxγ using complete (T (γ ),˜ γ )-paths in˜ (S(γ ),˜ M(γ )).˜
4.3 Folding
The graphGT ,γ was constructed by glueing tilesS˜k+1 to tilesS˜k along edges with weightx[γk], see Fig.3. Now we will fold the graph along the edges weightedx[γk], thereby identifying the two triangles incident tox[γk],k=1,2, . . . , d−1.
To be more precise, the edge with weightx[γk], that lies in the two tilesS˜k+1and S˜k, is contained in precisely two trianglesΔk andΔk inGT ,γ:Δk lying inside the
tileS˜k andΔk lying inside the tileS˜k+1. BothΔk andΔk have weights x[γk],xk, xk+1, but opposite orientations. CuttingGT ,γ along the edge with weightx[γk], one obtains two connected components. LetRk be the component that contains the tile S˜kandRk+1the component that containsS˜k+1.
The folding of the graphGT ,γ alongx[γk]is the graph obtained by flippingRk+1 and then glueing it toRk by identifying the two trianglesΔk andΔk. In this new graph, we can now fold along any of the edgesx[γ] withk=, by cutting along x[γ], defining subgraphsRk,andRk,+1in a similar way, and then flippingRk,+1 and glueing it toRk,by identifying the two trianglesΔandΔ.
The graph obtained by consecutive folding ofGT ,γ along all edges with weight x[γk]fork=1,2, . . . , d−1, is isomorphic to the underlying graph of the triangulation T (γ )˜ of the unpunctured surface(S(γ ),˜ M(γ )). Indeed, there clearly is a bijection˜ between the triangles in both graphs, and, in both graphs, the way the triangles are glued together is uniquely determined byγ.
We obtain a map that we call the folding map φ:
perfect matchings inGT ,γ
→
complete(T (γ ),˜ γ )-paths˜ in(S(γ ),˜ M(γ ))˜
P → α˜P
as follows. First, we associate a pathαP inGT ,γ to the matchingP as follows. Let αP be the path starting ats going along the unique edge ofP that is incident tos, then going along the diagonal of the first tileS˜1, then along the unique edge ofP that is incident to the endpoint of that diagonal, and so forth. The fact thatP is a perfect matching guarantees that each endpoint of a diagonal is incident to a unique edge inP, and from the construction ofGT ,γ it follows that each edge inP connects two endpoints of two distinct diagonals. It is clear from the construction ofGT ,γ that one can never come back to the same vertex, and therefore the path must reacht.
SinceP has cardinalityd +1, the pathαP consists of 2d+1 edges, thusα= (α1, α2, . . . , α2d+1). Now we defineα˜P =(α˜1,α˜2, . . . ,α˜2d+1)by folding the path αP. Thus, ifP= {β1, β3, . . . , β2d−1, β2d+1}, where the edges are ordered according toγ, thenφ (P )=(α˜1,α˜2, . . . ,α˜2d+1), whereα˜2k+1is the image ofβ2k+1under the folding, andα˜2k = ˜τik is the arc crossingγ˜ atp˜k. Then φ (P )satisfies the axiom (T1) by construction. Moreover,φ (P ) satisfies the axiom (T2), because, for each k=0,1, . . . , d, the segment of the pathφ (P ), which starts at the pointp˜k, then goes alongα˜2k to the starting point ofα˜2k+1, then alongα˜2k+1 to the starting point of
˜
α2k+2, and then alongα˜2k+2until the pointp˜k+1, is homotopic to the segmentγ˜k, since both segments lie in the simply connected triangleΔ˜k formed byτ˜ik,τ˜ik+1, and
˜
τ[γk]. Therefore, the folding mapφis well defined.
Note that it is possible thatα˜k,α˜k+1is backtracking, that is,α˜kandα˜k+1run along the same arcτ˜∈ ˜T (γ ).
Example 4.3 Figure4displays an example of a perfect matching P, whose edges are the solid bold lines, of the graphGT ,γ of Fig.10. The matching contains edges labeled x5, x2, x8, x4, x4, x1, x3. The figure also shows the corresponding (not yet
Fig. 4 Example of complete (T , γ )path associated to a matching
folded) complete(T , γ )-path obtained by inserting the diagonalsτ1, τ2, τ3, τ4, τ1, τ2, given as dashed bold lines. In the surface in Fig. 9, the corresponding complete (T , γ )-path
αP =(τ5, τ1, τ2, τ2, τ8, τ3, τ4, τ4, τ4, τ1, τ1, τ2, τ3) is obtained by folding the path in Fig.4.
4.4 Unfolding the surface
Letαbe a boundary arc in(S(γ ),˜ M(γ ))˜ that is not adjacent to s˜and not adjacent tot˜. Then there is a unique triangleΔinT (γ )˜ in whichαis a side. The other two sides ofΔare two consecutive arcs, which we denote byτ˜j andτ˜j+1, see Fig.5.
By cutting the underlying graph ofT (γ )˜ alongτ˜j, we obtain two pieces. LetRj+1 denote the piece that containsα,τ˜j+1andt. Similarly, cutting(S(γ ),˜ M(γ ))˜ along
˜
τj+1, we obtain two pieces, and we denote byRjthe piece that containss,τ˜j, andα.
The graph obtained by unfolding alongαis the graph obtained by flippingRjand then glueing it toRj+1alongα. In this new graph, we label the edge ofRj that had the labelτ˜j+1byτ˜jb+1and the edge ofRj+1that had the labelτ˜j byτ˜jb, indicating that these edges are on the boundary of the new graph, see Fig.5. Now, in the graph obtained from unfolding alongα, we can continue unfolding along (the image of) a different boundary arcαin(S(γ ),˜ M(γ ))˜ that is not adjacent tos˜and not adjacent tot, again using the unique triangle˜ Δ inT (γ )˜ in which α is a side, cutting the graph obtained from unfolding alongα along τ˜j to obtainRj+1 and cutting the graph obtained from unfolding alongαalongτ˜j+1to obtainRj, then flipping and glueing in a similar way will give a new graph obtained fromT (γ )˜ by consecutive unfolding alongαandα.
Lemma 4.4 The graph obtained by repeated unfolding of the underlying graph of T (γ )˜ along all boundary edges not adjacent tos or t is isomorphic to the graph GT ,γ. Moreover, for each unfolding along an edgeα, the edges labeled τ˜jb,τ˜jb+1 are on the boundary ofGT ,γ and carry the weightsxj, xj+1, respectively, the edges
Fig. 5 Completion of paths
labeledτ˜j,τ˜j+1are diagonals inGT ,γ and carry the weightsxj, xj+1, respectively, andαis an interior edge ofGγ that is not a diagonal and carries the weightx[γj].
Proof This follows from the construction.
4.5 Unfolding map We define the map
{complete(T (γ ),˜ γ )˜ −paths} → {perfect matchings ofGT ,γ}
˜
α=(α˜1,α˜2, . . . ,α˜2d+1)→Pα˜= {β1, β3, β5, . . . , β2d+1} whereβ1= ˜α1,β2d+1= ˜α2d+1, and
β2k+1=
α˜2k+1 ifα˜2k+1is a boundary arc inT (γ ),˜
˜
τjb ifα˜2k+1= ˜τj is an arc inT (γ ).˜
We will show that this map is well defined. Supposeβ2k+1andβ2+1have a com- mon endpointx. Thenα˜2k+1andα˜2+1have a common endpointyin(S(γ ),˜ M(γ )),˜ and the two edges are not separated in the unfolding described in Lemma4.4. Conse- quently, there is no triangle inT (γ )˜ that is contained in the subpolygon spanned by
˜
α2k+1andα˜2+1, and henceα˜2k+1is equal toα˜2l+1. This implies that every arc in the subpath(α˜2k+1,α˜2k+2, . . . ,α˜2+1)is equal to the same arcτ˜j, and the only way this can happen is when=k+1 and(α˜2k+1,α˜2k+2, . . . ,α˜2+1)=(τ˜j,τ˜j,τ˜j)and both endpoints ofτ˜j are incident to an interior arc other thanτ˜j. In this case,τ˜j bounds the two trianglesτ˜j−1,τ˜j,τ˜[γj−1]andτ˜j,τ˜j+1,τ˜[γj]inT (γ ). Unfolding along˜ τ˜[γj−1]
andτ˜[γj]will produce edgesβ2k+1andβ2+1that are not adjacent, see Fig.6.
This shows that no vertex ofGT ,γ is covered twice inPα˜.
To show that every vertex ofGT ,γ is covered inPα˜, we use a counting argument.
Indeed, the number of vertices ofGT ,γ is 2(d+1), and, on the other hand, 2d+1 is the length ofα, since˜ α˜ is complete, and thusPα˜hasd+1 edges. The statement fol- lows since everyβj ∈Pα˜ has two distinct endpoints. This shows thatPα˜ is a perfect matching and our map is well defined.
Lemma 4.5 The unfolding mapα˜→Pα˜ is the inverse of the folding mapP → ˜αP. In particular, both maps are bijections.
Proof Letα˜ =(α˜1,α˜2, . . . ,α˜2d+1)be a complete(T (γ ),˜ γ )-path. Then˜ α˜Pα˜ =(α1, α2, . . . , α2d+1)whereα2k+1is the image under folding of the arcτ˜jbifα˜2k+1= ˜τj
Fig. 6 Unfolding alongτ˜[γj−1]andτ˜[γj]
is an arc inT (γ )˜ or, otherwise, the image under the folding of the arcα˜2k+1. Thus α2k+1= ˜α2k+1. Moreover,α2k=τik= ˜α2k, and thusα˜Pα˜ = ˜α.
Conversely, letP = {β1, β3, . . . , β2d−1, β2d+1} be a perfect matching ofGT ,γ. ThenPα˜P = { ˜β1,β˜3, . . . ,β˜2d−1,β˜2d+1}where
β˜2k+1=
α˜2k+1 ifα˜2k+1is a boundary arc,
˜
τjb ifα˜2k+1= ˜τj is an arc
=
τ˜[γj] ifβ2k+1= ˜τ[γj],
˜
τjb ifβ2k+1= ˜τjb.
HencePα˜P=P.
Combining Lemma4.5with the results of [32], we obtain the following theorem.
Theorem 4.6 There is a bijection between the set of perfect matchings of the graph GT ,γ and the set of complete(T , γ )-paths in(S, M)given byP →π(˜αP), whereα˜P
is the image ofP under the folding map, andπis induced by the universal coverπ: S˜→S. Moreover, the numerator of the Laurent monomialx(π(α˜P))of the complete (T , γ )-pathπ(α˜P)is equal to the weightw(P )of the matchingP.
Proof The map in the theorem is a bijection, because it is the composition of the folding map, which is a bijection, by Lemma4.5, and the mapπ, which is a bijection, by [32, Lemma 5.8]. The last statement of the theorem follows from the construction
of the graphGT ,γ.
Example 4.7 The unfolding of the path
˜
α=(τ5, τ1, τ2, τ2, τ8, τ3, τ4, τ4, τ4, τ1, τ1, τ2, τ3) in the surface of Fig.9is the perfect matchingPα˜=P of Example4.3.
4.6 Proof of Theorem3.1
It has been shown in [32, Theorem 3.2] that xγ =
α
x(α)y(α), (5)
where the sum is over all complete(T , γ )-pathsα in(S, M),y(α)is a monomial in yT, and
x(α)=
kodd
xαk
keven
xα−1
k . (6)
Applying Theorem4.6to (5) yields xγ=
P
w(P )y(P )(xi1xi2· · ·xid)−1, (7) where the sum is over all perfect matchingsP ofGT ,γ,w(P )is the weight of the matching and y(P )=y(π(α˜P)), by definition. This completes the proof of Theo- rem3.1.
5 A formula fory(P )
In this section, we give a description of the coefficientsy(P )in terms of the match- ingP. First, we need to recall some results from [32].
Recall thatT is a triangulation of the unpunctured surface(S, M)and thatγis an arc in(S, M)that crossesT exactlyd times. We also have fixed an orientation for γ and denote bys=p0, p1, . . . , pd, pd+1=t the intersection points ofγ andT in order of occurrence onγ. Leti1, i2, . . . , idbe such thatpklies on the arcτik∈T for k=1,2, . . . , d. Fork=0,1, . . . , d, letγkdenote the segment of the pathγ from the pointpk to the pointpk+1. Eachγk lies in exactly one triangleΔk inT. If 1≤k≤ d−1, the triangleΔk is formed by the arcsτik, τik+1 and a third arc that we denote byτ[γk].
The orientation of the surfaceSinduces an orientation on each of these triangles in such a way that, whenever two trianglesΔ, Δshare an edgeτ, then the orienta- tion ofτ inΔis opposite to the orientation ofτ inΔ, There are precisely two such orientations. We assume without loss of generality thatS has the “clockwise orien- tation,” that is, in each triangleΔ, going around the boundary ofΔaccording to the orientation ofS, is clockwise when looking at it from outside the surface.
Let α be a complete (T , γ )-path. Then α2k =τik is a common arc of the two trianglesΔk−1andΔk. We say thatα2k isγ-oriented if the orientation ofα2k in the pathαis the same as the orientation ofτik in the triangleΔk, see Fig.7.
It is shown in [32, Theorem 3.2] that
y(α)=
k:α2kisγ-oriented
yik. (8)
