# Cluster algebras of unpunctured surfaces and snake graphs

Gregg Musiker<fnref n="1" />† and Ralf Schiffler<fnref n="2" />‡

**Abstract.** We study cluster algebras with principal coefficient systems that are associated 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 graph $G_{T,γ}$ 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 graph $G_{T,γ}$.

**Résumé.** Nous étudions des algebres amassees avec coefficients principaux associees aux surfaces. Nous présentons une formule directe pour les developpements de Laurent des variables amassees dans ces algebres en terme de couplages parfaits d'un certain graphe $G_{T,γ}$ que l'on construit a partir de la surface en recollant des pieces elementaires que l'on appelle carreaux. Nous donnons aussi une seconde formule pour ces developpements en termes de sous-graphes de $G_{T,γ}$.

**Keywords:** cluster algebra, triangulated surface, principal coefficients, F-polynomial, height function, snake graphs

## 1 Introduction

Cluster algebras, introduced in (FZ1), are commutative algebras equipped with a distinguished set of generators, the cluster variables. The cluster variables are grouped into sets of constant cardinality $n$, the clusters, and the integer $n$ is called the rank of the cluster algebra. Starting with an initial cluster $\mathbf{x}$ (together with a skew symmetrizable integer $n \times n$ matrix $B = (b_{ij})$ and a coefficient vector $\mathbf{y} = (y_i)$ whose entries are elements of a torsion-free abelian group $\mathbb{P}$) the set of cluster variables is obtained by repeated application of so called mutations. To be more precise, let $\mathcal{F}$ be the field of rational functions in the indeterminates $x_1, x_2, \dots, x_n$ over the quotient field of the integer group ring $\mathbb{Z}\mathbb{P}$. Thus $\mathbf{x} = \{x_1, x_2, \dots, x_n\}$ is a transcendence basis for $\mathcal{F}$. For every $k = 1, 2, \dots, n$, the mutation $\mu_k(\mathbf{x})$ of the cluster $\mathbf{x} = \{x_1, x_2, \dots, x_n\}$ is a new cluster $\mu_k(\mathbf{x}) = \mathbf{x} \setminus \{x_k\} \cup \{x'_k\}$ obtained from $\mathbf{x}$ by replacing the cluster variable $x_k$ by the new cluster variable

$$x'_{k} = \frac{1}{x_{k}} \left( y_{k}^{+} \prod_{b_{ki} > 0} x_{i}^{b_{ki}} + y_{k}^{-} \prod_{b_{ki} < 0} x_{i}^{-b_{ki}} \right) \quad (1)$$

<footnote n="1">¹ Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139</footnote>

<footnote n="2">² Department of Mathematics, University of Connecticut, Storrs, CT, 06269-3009</footnote>

<footnote>†Supported by an NSF Mathematical Sciences Postdoctoral Fellowship, grant DMS-0703691.</footnote>

<footnote>‡Supported by the NSF grant DMS-0700358 and by the University of Connecticut</footnote>
in $\mathcal{F}$, where $y_k^+$, $y_k^-$ are certain monomials in $y_1, y_2, \dots, y_n$. Mutations also change the attached matrix $B$ as well as the coefficient vector $y$, see (FZ1).

The set of all cluster variables is the union of all clusters obtained from an initial cluster $x$ by repeated mutations. Note that this set may be infinite.

It is clear from the construction that every cluster variable is a rational function in the initial cluster variables $x_1, x_2, \dots, x_n$. In (FZ1) it is shown that every cluster variable $u$ is actually a Laurent polynomial in the $x_i$, that is, $u$ can be written as a reduced fraction

$$u = \frac{f(x_1, x_2, \dots, x_n)}{\prod_{i=1}^{n} x_i^{d_i}}, \qquad (2)$$

where $f \in \mathbb{Z}\mathbb{P}[x_1, x_2, \dots, x_n]$ and $d_i \ge 0$. The right hand side of equation (2) is called the *cluster expansion* of $u$ in $x$.

The cluster algebra is determined by the initial matrix $B$ and the choice of the coefficient system. A canonical choice of coefficients is the *principal coefficient system*, introduced in (FZ2), which means that the coefficient group $\mathbb{P}$ is the free abelian group on $n$ generators $y_1, y_2, \dots, y_n$, and the initial coefficient tuple $y = \{y_1, y_2, \dots, y_n\}$ consists of these $n$ generators. In (FZ2), 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 (FG1; FG2; FG3) and Gekhtman, Shapiro and Vainshtein (GSV1; GSV2) which discovered cluster structures in the context of Teichmüller theory, Fomin, Shapiro and Thurston (FST; FT) initiated a systematic study of the cluster 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 surface, and clusters correspond to triangulations. In (S2), building on earlier results in (S1; ST), 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 parametrization 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_\gamma$ be a cluster variable corresponding to an arc $\gamma$ in the unpunctured surface and let $d$ be the number of crossings between $\gamma$ and the triangulation $T$ of the surface. Then $\gamma$ runs through $d+1$ triangles of $T$ and each pair of consecutive triangles forms a quadrilateral which we call a tile. So we obtain $d$ tiles, each of which is a weighted graph, whose weights are given by the cluster variables $x_\tau$ associated to the arcs $\tau$ of the triangulation $T$.

We obtain a weighted graph $G_{T,\gamma}$ by glueing the $d$ tiles in a specific way and then deleting the diagonal in each tile. To any perfect matching $M$ of this graph we associate its weight $w(M)$ which is the product of the weights of its edges, hence a product of cluster variables. We prove the following cluster expansion formula:

**Theorem 1.1.**

$$x_{\gamma} = \sum_{M} \frac{w(M) y(M)}{x_{i_1} x_{i_2} \dots x_{i_d}},$$

where the sum is over all perfect matchings $M$ of $G_{T,\gamma}$, $w(M)$ is the weight of $M$, and $y(M)$ is a monomial in $y$.
We also give a formula for the coefficients $y(M)$ in terms of perfect matchings as follows. The $F$-polynomial $F_γ$, introduced in (FZ2) is obtained from the Laurent polynomial $x_γ$ (with principal coefficients) by substituting 1 for each of the cluster variables $x_1, x_2, \dots, x_n$. By (S2, Theorem 6.2, Corollary 6.4), the $F$-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 graph $G_{T,γ}$. We denote by $M_-$ the one with $y(M_-) = 1$ and the other by $M_+$. Now, for an arbitrary perfect matching $M$, the coefficient $y(M)$ is determined by the set of edges of the symmetric difference $M_- \ominus M = (M_- \cup M) \setminus (M_- \cap M)$ as follows.

**Theorem 1.2.** The set $M_- \ominus M$ is the set of boundary edges of a (possibly disconnected) subgraph $G_M$ of $G_{T,γ}$ which is a union of tiles $G_M = \cup_{j \in J} S_j$. Moreover,

$$y(M) = \prod_{j \in J} y_{i_j}.$$

As an immediate corollary, we see that the corresponding $g$-vector, introduced in (FZ2), is

$$g_{\gamma} = \deg \left( \frac{w(M_{-})}{x_{i_1} \cdots x_{i_d}} \right).$$

This follows from the fact that $y(M_-) = 1$.

Our third main result is yet another description of the formula of Theorem 1.1 in terms of the graph $G_{T,γ}$ only. In order to state this result, we need some notation. If $H$ is a graph, let $c(H)$ be the number of connected components of $H$, let $E(H)$ be the set of edges of $H$, and denote by $\partial H$ the set of boundary edges of $H$. Define $\mathcal{H}_k$ to be the set of all subgraphs $H$ of $G_{T,γ}$ such that $H$ is a union of $k$ tiles $H = S_{j_1} \cup \cdots \cup S_{j_k}$ and such that the number of edges of $M_-$ that are contained in $H$ is equal to $k + c(H)$. For $H \in \mathcal{H}_k$, let

$$y(H) = \prod_{S_{i_j} \text{ tile in } H} y_{i_j}.$$

**Theorem 1.3.** The cluster expansion of the cluster variable $x_γ$ is given by

$$x_{\gamma} = \sum_{k=0}^{d} \sum_{H \in \mathcal{H}_k} \frac{w(\partial H \ominus M_-) y(H)}{x_{i_1} x_{i_2} \cdots x_{i_d}}.$$

Theorem 1.1 has interesting intersections with work of other people. In (CCS2), the authors obtained a formula for the denominators of the cluster expansion in types $A, D$ and $E$, see also (BMR). In (CC; CK; CK2) 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 (Pa). These formulas use the cluster category introduced in (BMRRT), and in (CCS) 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 (FK), and, combining results of (A) and (ABCP; LF), such a categorification exists in the case of cluster algebras associated to unpunctured surfaces.

In (SZ; CZ; Z; MP) cluster expansions for cluster algebras of rank 2 are given, in (Pr1; CP; FZ3) the case $A$ is considered. In section 4 of (Pr1), Propp describes two constructions of snake graphs, the
latter of which are unweighted analogues for the case A of the graphs $G_{T,\gamma}$ that we present in this paper. Propp assigns a snake graph to each arc in the triangulation of an $n$-gon and shows that the numbers of matchings in these graphs satisfy the Conway-Coxeter frieze pattern induced by the Ptolemy relations on the $n$-gon. In (M) a cluster expansion for cluster algebras of classical type is given for clusters that lie in a bipartite seed, and the forthcoming work of (MSW) will concern cluster expansions for cluster algebras with principal coefficients arising from any surface (with or without punctures), for an arbitrary seed.

**Remark 1.4.** The formula for $y(M)$ given in Theorem 1.2 also can be formulated in terms of height functions, as found in literature such as (EKLP) or (Pr2). As described in section 3 of (Pr2), one way to define the height function on the faces of a bipartite planar graph $G$, covered by a perfect matching $M$, is to superimpose each matching with the fixed matching $M_0$ (the unique matching of minimal height). In the case where $G$ is a snake graph, we take $M_0$ to be $M_-$, one of the two matchings of $G$ only involving edges on the boundary. Color the vertices of $G$ black and white so that no two adjacent vertices have the same color. In this superposition, we orient edges of $M$ from black to white, and edges of $M_-$ from white to black. We thereby obtain a spanning set of cycles, and removing the cycles of length two exactly corresponds to taking the symmetric difference $M \ominus M_-$. We can read the resulting graph as a relief-map, in which the altitude changes by $+1$ or $-1$ as one crosses over a contour line, according to whether the counter-line is directed clockwise or counter-clockwise. By this procedure, we obtain a height function $h_M : F(G) \to \mathbb{Z}$ which assigns integers to the faces of graph $G$. When $G$ is a snake graph, the set of faces $F(G)$ is simply the set of tiles $\{S_j\}$ of $G$. Comparing with the definition of $y(M)$ in Theorem 1.2, we see that

$$y(M) = \prod_{S_j \in F(G)} y_j^{h_M(j)}.$$

An alternative definition of height functions comes from (EKLP) by translating the matching problem into a domino tiling problem on a region colored as a checkerboard. We imagine an ant starting at an arbitrary vertex at height 0, walking along the boundary of each domino, and changing its height by $+1$ or $-1$ as it traverses the boundary of a black or white square, respectively. The values of the height function under these two formulations agree up to scaling by four.

The paper is organized as follows. In section 2, we recall the construction of cluster algebras from surfaces of (FST). Section 3 contains the construction of the graph $G_{T,\gamma}$ and the statement of the cluster expansion formula. Proofs of our results appear in sections 4-6 of (MS). We close with an example in section 4.

## 2 Cluster algebras from surfaces

In this section, we recall the construction of (FST) in the case of surfaces without punctures.

Let $S$ be a connected oriented 2-dimensional Riemann surface with boundary and $M$ a non-empty set of marked points in the closure of $S$ with at least one marked point on each boundary component. The pair $(S, M)$ is called a *bordered surface with marked points*. Marked points in the interior of $S$ are called *punctures*.

In this paper we will only consider surfaces $(S, M)$ such that all marked points lie on the boundary of $S$, and we will refer to $(S, M)$ simply by *unpunctured surface*.

We say that two curves in $S$ do not cross if they do not intersect each other except that endpoints may coincide. An arc $\gamma$ in $(S, M)$ is a curve in $S$ such that
(a) the endpoints are in $M$,

(b) $\gamma$ does not cross itself,

(c) the relative interior of $\gamma$ is disjoint from $M$ and from the boundary of $S$,

(d) $\gamma$ does not cut out a monogon or a digon.

Curves that connect two marked points and lie entirely on the boundary of $S$ without 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 endpoints $a, b \in M$ then it can be represented by a curve that runs from $a$ to $b$, as well as by a curve that runs from $b$ to $a$.

For any two arcs $\gamma, \gamma'$ in $S$, let $e(\gamma, \gamma')$ be the minimal number of crossings of $\gamma$ and $\gamma'$, that is, $e(\gamma, \gamma')$ is the minimum of the numbers of crossings of arcs $\alpha$ and $\alpha'$, where $\alpha$ is isotopic to $\gamma$ and $\alpha'$ is isotopic to $\gamma'$. Two arcs $\gamma, \gamma'$ are called *compatible* if $e(\gamma, \gamma') = 0$. A triangulation is a maximal collection of compatible arcs together with all boundary arcs. The arcs of a triangulation cut the surface into *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 has $n+m$ elements, $n$ of which are arcs in $S$, and the remaining $m$ elements are boundary arcs. Note that the number of boundary arcs is equal to the number of marked points.

**Proposition 2.1.** *The number $n$ of arcs in any triangulation is given by the formula $n = 6g + 3b + m - 6$, where $g$ is the genus of $S$, $b$ is the number of boundary components and $m = |M|$ is the number of marked points. The number $n$ is called the rank of $(S, M)$.*

*Proof.* (FST, 2.10)

<figure><img src="image_1.png" /></figure>

Note that $b > 0$ since the set $M$ is not empty. Following (FST), we associate a cluster algebra to the unpunctured surface $(S, M)$ as follows. Choose any triangulation $T$, let $\tau_1, \tau_2, \dots, \tau_n$ be the $n$ interior arcs of $T$ and denote the $m$ boundary arcs of the surface by $\tau_{n+1}, \tau_{n+2}, \dots, \tau_{n+m}$. For any triangle $\Delta$ in $T$ define a matrix $B^\Delta = (b_{ij}^\Delta)_{1\le i\le n, 1\le j\le n}$ by

$$b_{ij}^{\Delta} = \begin{cases} 1 & \text{if } \tau_i \text{ and } \tau_j \text{ are sides of } \Delta \text{ with } \tau_j \text{ following } \tau_i \text{ in counter-clockwise order;} \\ -1 & \text{if } \tau_i \text{ and } \tau_j \text{ are sides of } \Delta \text{ with } \tau_j \text{ following } \tau_i \text{ in clockwise order;} \\ 0 & \text{otherwise.} \end{cases}$$

(Note that this sign convention agrees with that of (S2) and differs from that (FST).) Then define the matrix $B_T = (b_{ij})_{1\le i\le n, 1\le j\le n}$ by $b_{ij} = \sum_{\Delta} b_{ij}^{\Delta}$, where the sum is taken over all triangles in $T$. Note that the boundary arcs of the triangulation are ignored in the definition of $B_T$. Let $\tilde{B}_T = (b_{ij})_{1\le i\le 2n, 1\le j\le n}$ be the $2n \times n$ matrix whose upper $n \times n$ part is $B_T$ and whose lower $n \times n$ part is the identity matrix. The matrix $B_T$ is skew-symmetric and each of its entries $b_{ij}$ is either 0, 1, -1, 2, or -2, since every arc $\tau$ can be in at most two triangles.
Let $\mathcal{A}(\mathbf{x}_T, \mathbf{y}_T, B_T)$ be the cluster algebra with principal coefficients in the triangulation $T$, that is, $\mathcal{A}(\mathbf{x}_T, \mathbf{y}_T, B_T)$ is given by the seed $(\mathbf{x}_T, \mathbf{y}_T, B_T)$ where $\mathbf{x}_T = \{x_{\tau_1}, x_{\tau_2}, \dots, x_{\tau_n}\}$ is the cluster associated to the triangulation $T$, and the initial coefficient vector $\mathbf{y}_T = (y_1, y_2, \dots, y_n)$ is the vector of generators of $\mathbb{P} = \text{Trop}(y_1, y_2, \dots, y_n)$. For the boundary arcs we define $x_{\tau_k} = 1, k = n+1, n+2, \dots, n+m$.

For each $k = 1, 2, \dots, n$, there is a unique quadrilateral in $T \setminus \{\tau_k\}$ in which $\tau_k$ is one of the diagonals. Let $\tau'_k$ denote the other diagonal in that quadrilateral. Define the flip $\mu_k T$ to be the triangulation $T \setminus \{\tau_k\} \cup \{\tau'_k\}$. The mutation $\mu_k$ of the seed $\Sigma_T$ in the cluster algebra $\mathcal{A}$ corresponds to the flip $\mu_k$ of the triangulation $T$ in the following sense. The matrix $\mu_k(B_T)$ is the matrix corresponding to the triangulation $\mu_k T$, the cluster $\mu_k(\mathbf{x}_T)$ is $\mathbf{x}_T \setminus \{x_{\tau_k}\} \cup \{x_{\tau'_k}\}$, and the corresponding exchange relation is given by

$$x_{\tau_k} x_{\tau'_k} = x_{\rho_1} x_{\rho_2} y^+ + x_{\sigma_1} x_{\sigma_2} y^-,$$

where $y^+, y^-$ are some coefficients, and $\rho_1, \sigma_1, \rho_2, \sigma_2$ are the sides of the quadrilateral in which $\tau_k$ and $\tau'_k$ are the diagonals, such that $\rho_1, \rho_2$ are opposite sides and $\sigma_1, \sigma_2$ are opposite sides too.

# 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 tile $\bar{S}_k$ is a planar four vertex graph with five weighted edges having the shape of two equilateral triangles that share one edge, see Figure 1(a). The weight on each edge of the tile $\bar{S}_k$ is a single variable. The unique interior edge is called diagonal and the four exterior edges are called sides of $\bar{S}_k$. We shall use $S_k$ to denote the graph obtained from $\bar{S}_k$ by removing the diagonal.

Now let $T$ be a triangulation of the unpunctured surface $(S, M)$. If $\tau_k \in T$ is an interior arc, then $\tau_k$ lies in precisely two triangles in $T$, hence $\tau_k$ is the diagonal of a unique quadrilateral $Q_{\tau_k}$ in $T$. We associate to this quadrilateral a tile $\bar{S}_k$ by assigning the weight $x_k$ to the diagonal and the weights $x_a, x_b, x_c, x_d$ to the sides of $\bar{S}_k$ in such a way that there is a homeomorphism $\bar{S}_k \to Q_{\tau_k}$ which sends the edge with weight $x_i$ to the arc labeled $\tau_i$, $i = a, b, c, d, k$, see Figure 1(a).

## 3.2 The graph $\bar{G}_{T,\gamma}$

Let $T$ be a triangulation of an unpunctured surface $(S, M)$ and let $\gamma$ be an arc in $(S, M)$ which is not in $T$. Choose an orientation on $\gamma$ and let $s \in M$ be its starting point, and let $t \in M$ be its endpoint. We denote by

$$p_0 = s, p_1, p_2, \dots, p_{d+1} = t$$

the points of intersection of $\gamma$ and $T$ in order. Let $i_1, i_2, \dots, i_d$ be such that $p_k$ lies on the arc $\tau_{i_k} \in T$. Note that $i_k$ may be equal to $i_j$ even if $k \neq j$. Let $\tilde{S}_1, \tilde{S}_2, \dots, \tilde{S}_d$ be a sequence of tiles so that $\tilde{S}_k$ is isomorphic to the tile $\bar{S}_{i_k}$, for $k = 1, 2, \dots, d$.

For $k$ from 0 to $d$, let $\gamma_k$ denote the segment of the path $\gamma$ from the point $p_k$ to the point $p_{k+1}$. Each $\gamma_k$ lies in exactly one triangle $\Delta_k$ in $T$, and if $1 \le k \le d-1$ then $\Delta_k$ is formed by the arcs $\tau_{i_k}, \tau_{i_{k+1}}$, and a third arc that we denote by $\tau_{[\gamma_k]}$.

We will define a graph $\bar{G}_{T,\gamma}$ by recursive glueing of tiles. Start with $\bar{G}_{T,\gamma,1} \cong \tilde{S}_1$, where we orient the tile $\tilde{S}_1$ so that the diagonal goes from northwest to southeast, and the starting point $p_0$ of $\gamma$ is in the
<figure><img src="image_2.png" /><figcaption>Fig. 1: (a) The tile $\bar{S}_k$; (b) Glueing tiles $S_k$ and $S_{k+1}$ along the edge weighted $x_{[\gamma_k]}$</figcaption></figure>

southwest corner of $\tilde{S}_1$. For all $k = 1, 2, \dots, d-1$ let $\bar{G}_{T,\gamma,k+1}$ be the graph obtained by adjoining the tile $\tilde{S}_{k+1}$ to the tile $\tilde{S}_k$ of the graph $\bar{G}_{T,\gamma,k}$ along the edge weighted $x_{[\gamma_k]}$, see Figure 1(b). We always orient the tiles so that the diagonals go from northwest to southeast. Note that the edge weighted $x_{[\gamma_k]}$ is either the northern or the eastern edge of the tile $\tilde{S}_k$. Finally, we define $\bar{G}_{T,\gamma}$ to be $\bar{G}_{T,\gamma,d}$.

Let $G_{T,\gamma}$ be the graph obtained from $\bar{G}_{T,\gamma}$ by removing the diagonal in each tile, that is, $G_{T,\gamma}$ is constructed in the same way as $\bar{G}_{T,\gamma}$ but using tiles $S_{i_k}$ instead of $\bar{S}_{i_k}$.

A perfect matching of a graph is a subset of the edges so that each vertex is covered exactly once. We define the weight $w(M)$ of a perfect matching $M$ to be the product of the weights of all edges in $M$.

## 3.3 Cluster expansion formula

Let $(S, M)$ be an unpunctured surface with triangulation $T$, and let $\mathcal{A} = \mathcal{A}(\mathbf{x}_T, \mathbf{y}_T, B)$ be the cluster algebra with principal coefficients in the initial seed $(\mathbf{x}_T, \mathbf{y}_T, B)$ defined in section 2. Each cluster variable in $\mathcal{A}$ corresponds to an arc in $(S, M)$. Let $x_\gamma$ be an arbitrary cluster variable corresponding to an arc $\gamma$. Choose an orientation of $\gamma$, and let $\tau_{i_1}, \tau_{i_2}, \dots, \tau_{i_d}$ be the arcs of the triangulation that are crossed by $\gamma$ in this order, with multiplicities possible. Let $G_{T,\gamma}$ be the graph constructed in section 3.2.

**Theorem 1.1.**

$$x_{\gamma} = \sum_{M} \frac{w(M) y(M)}{x_{i_1} x_{i_2} \dots x_{i_d}},$$

where the sum is over all perfect matchings $M$ of $G_{T,\gamma}$, $w(M)$ is the weight of $M$, and $y(M)$ is the monomial given in Theorem 1.2.

## 4 Example

We illustrate Theorem 1.1, Theorem 1.2 and Theorem 1.3 in an example. Let $(S, M)$ be the annulus with two marked points on each of the two boundary components, and let $T = \{\tau_1, \dots, \tau_8\}$ be the triangulation shown in Figure 2.

The corresponding cluster algebra has the following principal exchange matrix and quiver.

$$\left[ \begin{array}{cccc} 0 & 1 & 0 & -1 \\ -1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \\ 1 & 0 & 1 & 0 \end{array} \right]$$
<figure><img src="image_3.png" /><figcaption>Fig. 2: Triangulated surface with dotted arc $\gamma$</figcaption></figure>

Let $\gamma$ be the dotted arc in Figure 2. It has $d = 6$ crossings with the triangulation. The sequence of crossed arcs $\tau_{i_1}, \dots, \tau_{i_6}$ is $\tau_1, \tau_2, \tau_3, \tau_4, \tau_1, \tau_2$, and the corresponding segments $\gamma_0, \dots, \gamma_6$ of the arc $\gamma$ are labeled in the figure. Moreover, $\tau_{[\gamma_1]} = \tau_6$, $\tau_{[\gamma_2]} = \tau_8$, $\tau_{[\gamma_3]} = \tau_7$, $\tau_{[\gamma_4]} = \tau_5$ and $\tau_{[\gamma_5]} = \tau_6$.

The graph $G_{T,\gamma}$ is obtained by glueing the corresponding six tiles $\tilde{S}_1, \tilde{S}_2, \tilde{S}_3, \tilde{S}_4, \tilde{S}_1$, and $\tilde{S}_2$. The result is shown in Figure 3.

Theorems 1.1 and 1.2 imply that $x_{\gamma}(x_{i_1}x_{i_2}\cdots x_{i_d})$ is equal to

$$
\begin{array}{l @{\quad + \quad} l @{\quad + \quad} l}
x_5 x_2 x_2 x_3 x_1 x_2 x_8 & x_4 x_6 x_2 x_3 x_1 x_2 x_8 y_1 & \\
x_5 x_2 x_2 x_7 x_5 x_2 x_8 y_4 & x_4 x_6 x_2 x_7 x_5 x_2 x_8 y_1 y_4 & \\
x_5 x_2 x_8 x_4 x_5 x_2 x_8 y_3 y_4 & x_5 x_2 x_2 x_7 x_4 x_6 x_8 y_4 y_1 & \\
x_4 x_6 x_8 x_4 x_5 x_2 x_8 y_1 y_3 y_4 & x_4 x_6 x_2 x_7 x_4 x_6 x_8 y_1 y_4 y_1 & \\
x_5 x_2 x_8 x_4 x_4 x_6 x_8 y_3 y_4 y_1 & x_5 x_2 x_2 x_7 x_4 x_1 x_3 y_4 y_1 y_2 & \\
x_4 x_1 x_3 x_4 x_5 x_2 x_8 y_1 y_2 y_3 y_4 & x_4 x_6 x_8 x_4 x_4 x_6 x_8 y_1 y_3 y_4 y_1 & \\
x_4 x_6 x_2 x_7 x_4 x_1 x_3 y_1 y_4 y_1 y_2 & x_5 x_2 x_8 x_4 x_4 x_1 x_3 y_3 y_4 y_1 y_2 & \\
x_4 x_1 x_3 x_4 x_4 x_6 x_8 y_1 y_2 y_3 y_4 y_1 & x_4 x_6 x_8 x_4 x_4 x_1 x_3 y_1 y_3 y_4 y_1 y_2 & \\
& x_4 x_1 x_3 x_4 x_4 x_1 x_3 y_1 y_2 y_3 y_4 y_1 y_2 &
\end{array}
$$
<figure><img src="image_4.png" /><figcaption>Fig. 3: Construction of the graphs $\bar{G}_{T,\gamma}$ and $G_{T,\gamma}$</figcaption></figure>

which is equal to

$$
\begin{align*}
& x_1 x_2^3 x_3 && + x_1 x_2^2 x_3 x_4 y_1 \\
+ & x_2^3 y_4 && + x_2^2 x_4 y_1 y_4 \\
+ & x_2^2 x_4 y_3 y_4 && + x_2^2 x_4 y_1 y_4 \\
+ & x_2 x_1^2 y_1 y_3 y_4 && + x_2 x_1^2 y_1^2 y_4 \\
+ & x_2 x_4^2 y_3 y_4 y_1 && + x_1 x_2^2 x_3 x_4 y_1 y_2 y_4 \\
+ & x_1 x_2 x_3 x_4^2 y_1 y_2 y_3 y_4 && + x_4^3 y_1^2 y_3 y_4 \\
+ & x_1 x_2 x_3 x_4^2 y_1^2 y_2 y_4 && + x_1 x_2 x_3 x_4^2 y_3 y_4 y_1 y_2 \\
+ & x_1 x_3 x_4^3 y_1^2 y_2 y_3 y_4 && + x_1 x_3 x_4^3 y_1^2 y_2 y_3 y_4 \\
+ & x_1^2 x_3^2 x_4^2 y_1^2 y_2^2 y_3 y_4. &&
\end{align*}
$$
The first term corresponds to the matching $M_-$ consisting of the boundary edges weighted $x_5$ and $x_2$ in the first tile, $x_2$ in the third tile, $x_1$ and $x_3$ in the fourth, $x_2$ in the fifth and $x_8$ in the sixth tile. The twelfth term corresponds to the matching $M$ consisting of the horizontal edges of the first three tiles and the horizontal edges of the last two tiles. Thus $M_- \ominus M = (M_- \cup M) \setminus (M_- \cap M)$ is the union of a cycle around the first tile and a cycle around the third, fourth and fifth tiles, hence $y(M) = y_{i_1}y_{i_3}y_{i_4}y_{i_5} = y_1y_3y_4y_1$.

To illustrate Theorem 1.3, let $k = 2$. Then $\mathcal{H}_k$ consists of the subgraphs $H$ of $G_{T,\gamma}$ which are unions of two tiles and such that $E(H) \cap M_-$ has three elements if $H$ is connected, respectively four elements if $H$ has two connected components. Thus $\mathcal{H}_2$ has three elements

$$ \mathcal{H}_2 = \{S_{i_3} \cup S_{i_4}, S_{i_4} \cup S_{i_5}, S_{i_1} \cup S_{i_4}\} $$

corresponding to the three terms

$$ x_2^2 x_4 y_3 y_4, x_2^2 x_4 y_1 y_4 \text{ and } x_2^2 x_4 y_1 y_4. $$

**Acknowledgements.** The authors would like to thank Jim Propp and Lauren Williams for useful conversations related to this work. This paper is an abridged version of (MS).

## References

[A] C. Amiot, Cluster categories for algebras of global dimension 2 and quivers with potential, preprint, arXiv:0805.1035.

[ABCP] I. Assem, T. Brüstle, G. Charbonneau-Jodoin, P.G. Plamondon, Gentle algebras arising from surface triangulations, in preparation.

[BMRRT] A. Buan, R. Marsh, M. Reineke, I. Reiten and G. Todorov, Tilting theory and cluster combinatorics, Adv. Math. 204 (2006), 572-612, arXiv:math.RT/0402054.

[BMR] A. B. Buan, R. Marsh and I. Reiten, Denominators of cluster variables, preprint, arXiv:0710.4335.

[CC] P. Caldero and F. Chapoton, Cluster algebras as Hall algebras of quiver representations, Comment. Math. Helv. 81 (2006), 595-616, arXiv:math.RT/0410187.

[CCS] P. Caldero, F. Chapoton and R. Schiffler, Quivers with relations arising from clusters ($A_n$ case), Trans. Amer. Math. Soc. 358 (2006), no. 3, 1347-1364, arXiv:math.RT/0401316.

[CCS2] P. Caldero, F. Chapoton and R. Schiffler, Quivers with relations and cluster tilted algebras, Algebr. and Represent. Theory 9, (2006), no. 4, 359-376, arXiv:math.RT/0411238.

[CK] P. Caldero and B. Keller, From triangulated categories to cluster algebras, Invent. Math. 172 (2008), 169-211, arXiv:math.RT/0506018.

[CK2] P. Caldero, B. Keller, From triangulated categories to cluster algebras II, Ann. Sci. École Norm. Sup. (4) 39 (2006), no. 6, 983-1009, arXiv:math.RT/0510251.
[CZ] P. Caldero and A. Zelevinsky, Laurent expansions in cluster algebras via quiver representations, *Mosc. Math. J.* **6** (2006), no. 3, 411–429, arXiv:math.RT/0604054.

[CP] G. Carroll and G. Price, (unpublished result).

[EKLP] N. Elkies, G. Kuperberg, M. Larsen, J. Propp, Alternating-Sign Matrices and Domino Tilings (Part I), *J. Algebraic Combin.* **1** (1992), no. 2, 11–132, arXiv:math/9201305.

[FG1] V. Fock and A. Goncharov, Moduli spaces of local systems and higher Teichmüller theory. *Publ. Math. Inst. Hautes Études Sci.* No. 103 (2006), 1–211.

[FG2] V. Fock and A. Goncharov, Cluster ensembles, quantization and the dilogarithm, preprint (2003), arXiv:math AG/0311149.

[FG3] V. Fock and A. Goncharov, Dual Teichmüller and lamination spaces. Handbook of Teichmüller theory. Vol. I, 647–684, IRMA Lect. Math. Theor. Phys., 11, Eur. Math. Soc., Zürich, 2007.

[FST] S. Fomin, M. Shapiro and D. Thurston, Cluster algebras and triangulated surfaces. Part I: Cluster complexes, preprint (2006), arXiv:math/0608367.

[FT] S. Fomin and D. Thurston, Cluster algebras and triangulated surfaces. Part II: Lambda lengths, preprint (2008).

[FZ1] S. Fomin and A. Zelevinsky, Cluster algebras I. Foundations, *J. Amer. Math. Soc.* **15**(2), (2002), 497–529 (electronic), arXiv:math.RT/0104151.

[FZ2] S. Fomin and A. Zelevinsky, Cluster Algebras IV: Coefficients, *Comp. Math.* **143** (2007), 112–164, arXiv:math.RA/0602259.

[FZ3] S. Fomin and A. Zelevinsky, (unpublished result).

[FK] C. Fu and B. Keller, On cluster algebras with coefficients and 2-Calabi-Yau categories, preprint (2008), arXiv:0710.3152.

[GSV1] M. Gekhtman, M. Shapiro and A. Vainshtein, Cluster algebras and Poisson geometry. *Mosc. Math. J.* **3** (2003), no. 3, 899–934, 1199, arXiv:math.QA/0208033.

[GSV2] M. Gekhtman, M. Shapiro and A. Vainshtein, Cluster algebras and Weil-Petersson forms. *Duke Math. J.* **127** (2005), no. 2, 291–311, arXiv:math.QA/0309138.

[LF] D. Labardini-Fragoso, Quivers with potentials associated to triangulated surfaces, preprint (2008), arXiv:0803.1328.

[MP] G. Musiker and J. Propp, Combinatorial interpretations for rank-two cluster algebras of affine type. *Electron. J. Combin.* **14** (2007), no. 1, Research Paper 15, 23 pp. (electronic). arXiv:math/0602408.

[M] G. Musiker, A graph theoretic expansion formula for cluster algebras of classical type, to appear in *Ann. Comb.*, arXiv:0710.3574.
[MS] G. Musiker and R. Schiffler, Cluster expansion formulas and perfect matchings, (submitted) arXiv:0810.3638.

[MSW] G. Musiker. R. Schiffler, and L. Williams, Positivity for cluster algebras from surfaces, in preparation.

[Pa] Y. Palu, Cluster characters for triangulated 2-Calabi-Yau categories, to appear in *Annales de l'Institut Fourier*, arXiv:math/0703540.

[Pr1] J. Propp, The combinatorics of frieze patterns and Markoff numbers, preprint (2005), arXiv:math.CO/0511633.

[Pr2] J. Propp, Lattice structure for orientations of graphs, preprint (1993), arXiv:math/0209.5005.

[S1] R. Schiffler, A cluster expansion formula ($A_n$ case), *Electron. J. Combin.* **15** (2008), #R64 1, arXiv:math.RT/0611956.

[S2] R. Schiffler, On cluster algebras arising from unpunctured surfaces II, preprint (2008), arXiv:0809.2593.

[ST] R. Schiffler and H. Thomas, On cluster algebras arising from unpunctured surfaces, preprint (2007), arXiv:0712.4131.

[SZ] P. Sherman and A. Zelevinsky, Positivity and canonical bases in rank 2 cluster algebras of finite and affine types. *Mosc. Math. J.* **4** (2004), no. 4, 947–974, 982, arXiv:math.RT/0307082.

[Z] A. Zelevinsky, Semicanonical basis generators of the cluster algebra of type $A_1^{(1)}$. *Electron. J. Combin.* **14** (2007), no. 1, Note 4, 5 pp. (electronic), arXiv:math.RA/0606775.