# Perfect Matchings and Cluster Algebras of
Classical Type

Gregg Musiker†

Mathematics Department, Massachusetts Institute of Technology, Cambridge, MA 02139

**Abstract.** In this paper we give a graph theoretic combinatorial interpretation for the cluster variables that arise in most cluster algebras of finite type. In particular, we provide a family of graphs such that a weighted enumeration of their perfect matchings encodes the numerator of the associated Laurent polynomial while decompositions of the graphs correspond to the denominator. This complements recent work by Schiffler and Carroll-Price for a cluster expansion formula for the $A_n$ case while providing a novel interpretation for the $B_n$, $C_n$, and $D_n$ cases.

**Résumé.** Dans cet article nous donnons une interprétation combinatoire en termes de théorie des graphes pour les variables de clusters qui apparaissent dans la plupart des algèbres à clusters de type fini. En particulier, nous décrivons une famille de graphes tels qu’une énumération pondérée de leurs matchings parfaits encode le numérateur du polynôme de Laurent associé, tandis que les décompositions du graphe correspondent au dénominateur. Ceci complète les récents travaux de Schiffler et Carroll-Price qui donnent une formule pour le développement d’une variable de cluster dans le cas $A_n$, tout en fournissant une nouvelle interprétation dans les cas $B_n$, $C_n$ et $D_n$.

**Keywords:** cluster algebras, classical type, perfect matchings, Laurentness, positivity

## 1 Introduction

Several years ago, Sergey Fomin and Andrei Zelevinsky introduced a new mathematical object known as a cluster algebra which is related to a host of other combinatorial and geometric topics. Some of these include canonical bases of semisimple algebraic groups, generalized associahedra, quiver representations, tilting theory, and Teichmüller theory. In the proceeding we will use the definitions and conventions used in Fomin and Zelevinsky’s initial papers, (9; 11). Starting with a subset $\{x_1, x_2, \dots, x_n\}$ of cluster algebra $\mathcal{A}$, one applies binomial exchange relations to obtain additional generators of $\mathcal{A}$, called cluster variables. The (possibly infinite) set of cluster variables obtained this way generate $\mathcal{A}$ as an algebra. It was proven in (9) and (10) that any cluster variable is a Laurent polynomial in $\{x_1, x_2, \dots, x_n\}$, i.e. of the form

$$ \frac{P(x_1, \dots, x_n)}{x_1^{a_1} x_2^{a_2} \dots x_n^{a_n}} \quad (\text{Note that } x_i = \frac{1}{x_i^{-1}} \text{ is also allowed}) $$

<footnote>†This work was done with support of an NSF Mathematical Sciences Postdoctoral Fellowship.</footnote>
where $P(x_1, \dots, x_n)$ is a polynomial with integer coefficients (not divisible by any monomial) and the exponents $a_i$ are (possibly negative) integers. It is further conjectured that the polynomials $P(x_1, \dots, x_n)$ have *nonnegative* integer coefficients for any cluster algebra. However, this conjecture has been proved in a limited number of cases, including the bipartite finite type case, as proved in (11), the case of rank two affine cluster algebras as demonstrated in (4), (19), (24), and (26) as well as cluster algebras arising from acyclic quivers with acyclic initial seed (6).

The finite type case is defined as the case where the cluster variable generation procedure only yields a finite set of cluster variables associated to $\mathcal{A}$. By a combinatorial and geometric miracle, one which has sparked much interest in these algebras, the cluster algebras of finite type exactly correspond to the Lie algebras of finite type. Furthermore, in these cases, the cluster variables (except for the $x_i$'s) have denominators with *nonnegative* exponents and can be put in a 1-to-1 correspondence with the positive roots of the associated root system.

Study of the particular finite type cluster algebra of type $A_n$, also known as the Ptolemy algebra has been especially fruitful as it can be realized in terms of the Grassmannian and Plücker embedding. In 2003, as part of the REACH research group under Jim Propp's direction, Gabriel Carroll and Gregory Price (7) described two combinatorial interpretations of the associated cluster variables, one in terms of paths and one in terms of perfect matchings. Further, Ralf Schiffler recently independently discovered and extended the paths interpretation (22). Additionally, Schiffler and Hugh Thomas have recently obtained such results for cluster algebras arising from unpunctured surfaces (23).

In the present paper, we go beyond $A_n$, and describe a combinatorial interpretation for the cluster variables in all four families of finite type, namely $A_n$, $B_n$, $C_n$, and $D_n$, for the coefficient-free case. Our combinatorial model will involve perfect matchings, in the spirit of (19), and agrees with Carroll and Price's interpretation in the $A_n$ case. Unlike the aforementioned work we do not attempt to give the Laurent expansion of cluster variables in terms of any seed but only in terms of the initial bipartite seed, whose definition we remind the reader of below. By restricting ourselves to expansions in this initial seed, we are able to explicitly write down families of graphs which encode the cluster algebra using weighted perfect matchings.

We shall use the following notation throughout this paper. Let $G = (V, E)$ be a finite graph with vertex set $V = \{v_1, \dots, v_m\}$ and edge set $E \subseteq \{\{u, v\} : u, v \in V\}$. For each edge $e \in E$, we set $w_e$ to be the weight of $e$, where $w_e$ is allowed to be 1 or $x_i$ for $i \in \{1, 2, \dots, n\}$. A *perfect matching* $M$ of graph $G$ is a subset of $E$ such that for every vertex $v \in V$, there is exactly one edge $e \in M$ containing $v$. The weight of a perfect matching is defined to be the product $w(M) = \prod_{e \in M} w_e$, and we let $P(G)$ denote the matching polynomial, or matching enumerator, of graph $G$, defined as

$$P(G) = \sum_{M \text{ is a perfect matching of } G} w(M).$$

The result of this paper is the following theorem.

**Theorem 1** Let $\Phi$ be a root system of classical type and denote its positive roots as $\Phi_+$. For each such $\Phi$, we explicitly construct a family of graphs, $G_{\Phi}$, with the following three properties.

1. $|G_{\Phi}| = |\Phi_+|$.

2. For each positive root $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_n)$, there exists a unique $G_{\alpha}^{\Phi} \in G_{\Phi}$ that can be efficiently identified.
### 3. We have the cluster expansion formula

$$x[\alpha]^{\Phi} = \frac{P(G_{\alpha}^{\Phi})}{x_{1}^{\alpha_{1}} \cdots x_{n}^{\alpha_{n}}}$$

where $x[\alpha]^{\Phi}$ denotes the cluster variable corresponding to positive root $\alpha$ (in type $\Phi$) under Fomin and Zelevinsky's bijection.

Given graph $G \in \mathcal{G}_{\Phi}$, we are able to determine for which $\alpha \in \Phi_{+}$ we have $G = G_{\alpha}^{\Phi}$ by breaking down $G$ into tiles. More precisely, we let a family of tiles $\mathcal{T} = \{T_1, \dots, T_n\}$ be a finite set of graphs, with weighted edges, such that each $T_i$ is isomorphic to a cycle graph. Given the face and edge weighting of graph $G$, we decompose $G$ into a union of such tiles by gluing together certain edges.

We shall use the convention from (11), so that the initial exchange matrix $B = \|b_{ij}\|_{i,j=1}^{n}$ contains columns of like sign. Any rank $n$ cluster algebra of finite type has such a seed consisting of a cluster of initial variables $\{x_1, \dots, x_n\}$ and a set of $n$ binomial exchange relations of the form $x_j x'_j = \prod_{i=1}^{n} x_i^{|b_{ij}|} + 1$. After mutating in the $k$th direction, i.e. applying an exchange relation of the form $x_k x'_k = \text{binomial}$, we obtain a new seed with cluster $\{x_1, x_2, \dots, x_n\} \cup \{x'_k\} \setminus \{x_k\}$ and exchange matrix $B' = \|b'_{ij}\|_{i,j=1}^{n}$ such that the $b'_{ij}$'s satisfy

$$b'_{ij} = \begin{cases} -b_{ij} & \text{if } i=k \text{ or } j=k, \\ b_{ij} + \max(-b_{ik}, 0) \cdot b_{kj} + b_{ik} \cdot \max(b_{kj}, 0) & \text{otherwise.} \end{cases}$$

As we mention below in Remark 2, we shall use an ordering of mutations in this paper so that we need only work with binomial exchanges of the form $x_k x'_k = (\text{Monomial} + 1)$. Note that we shall use the notation $P_{\alpha}(x_1, x_2, \dots, x_n)$ to denote the numerator of the cluster variable with denominator $x_1^{\alpha_1} x_2^{\alpha_2} \cdots x_n^{\alpha_n}$ despite its similarity with the notation of $P(G)$ for the matching polynomial of graph $G$.

The outline of the paper is as follows. We proceed to prove Theorem 1 separately for the four families of non-exceptional type, starting with the well-studied case of $A_n$. Since the type of the cluster algebra will frequently be clear from context, we will simply denote tiles as $T_i$ or graphs as $G_{\alpha}$ (instead of $G_{\alpha}^{\Phi}$). We end with some comments and directions for further research.

**Remark 1** In (12), Fomin and Zelevinsky explicitly constructed Fibonacci polynomials for types $A_n$ and $D_n$. A slight variant, and generalization of these polynomials to other types, are defined in (13), where they are referred to as F-polynomials. These polynomials are also combinatorially constructed and give expansions of $Y_{\alpha}$'s which are algebraically related to the cluster variables.

## 2 $A_n$

The work in this section was done independently of the work of Carroll-Price (7) and the work of Schiffler (22) mentioned in the introduction. We will use the notation and the techniques of this section later in the paper for the $C_n$ and $D_n$ cases. We begin by reviewing the necessary characteristics of the cluster algebra of type $A_n$. Recall that Lie algebra $A_n$ has a Dynkin diagram consisting of a line of $n$ vertices connected by edges of weight one.
Thus the associated Cartan matrix is a tri-diagonal matrix with a diagonal of 2's and a super- and sub-diagonal consisting of -1's. Thus using the convention given in (11) the associated exchange matrix is

$$B^{A_n} = \|b_{ij}\| = \begin{bmatrix} 0 & 1 & 0 & 0 & \dots & 0 & 0 \\ -1 & 0 & -1 & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & 1 & \dots & 0 & 0 \\ 0 & 0 & -1 & 0 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \dots & (-1)^{n+1} & 0 \end{bmatrix}$$

Notice that every row has like sign and that the matrix is skew-symmetrizable (and in fact skew-symmetric

in this case). The bipartite seed for a cluster algebra of type $A_n$ therefore consists of an initial cluster of variables $\{x_1, x_2, \dots, x_n\}$ and exchange matrix $B^{A_n}$ which encodes the following exchange binomials, reading down the columns, $x_1x'_1 = x_2 + 1$, $x_2x'_2 = x_1x_3 + 1$, $x_3x'_3 = x_2x_4 + 1$, ..., $x_{n-1}x'_{n-1} = x_{n-2}x_n + 1$, and $x_nx'_n = x_{n-1} + 1$. We describe a set of tiles from which we will build our family of graphs. In the case of $A_n$, let tiles $T_1, \dots, T_n$ be squares defined as follows:

**Definition 1** Tile $T_1$'s northern edge is given weight $x_2$ while the other three are given weight 1. Tile $T_n$'s southern edge is weighted with value $x_{n-1}$ and the rest are weighted with value 1. Finally all other $T_i$ have a weight of $x_{i+1}$ given to their northern edge, $x_{i-1}$ for their southern edge while the eastern and western edges are given weight 1.

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

The tiles for cluster algebra of type $A_5$.

Let $\mathcal{G}_{A_n}$ be the set of graphs that can be built from these $n$ tiles given the following gluing rule.

**Rule 1** Without allowing reflections or rotations of the tiles, tile $T_i$ can be glued to tile $T_j$ if and only if the identified edge (as an edge of $T_i$) lies clockwise from an edge weighted $x_j$ and clockwise from an edge weighted $x_i$ (as an edge of $T_j$).

Since tile $T_i$ only contains edges of weight $x_{i+1}$ and $x_{i-1}$, and these weights appear across from each other, this rule uniquely describes how the blocks can connect.

**Lemma 1** Given the above tiles, $T_{A_n}$, and the above gluing rule, the collection of possible graphs is enumerated by the set of subsets

$$\{T_i, T_{i+1}, \dots, T_{j-1}, T_j\}$$

for $1 \le i < j \le n$.

This collection $\mathcal{G}_{A_n}$ has the same cardinality as the set of positive roots of the Lie algebra of type $A_n$ using the bijection

$$T_i \cup T_{i+1} \cup T_{i+2} \cup \dots \cup T_{j-1} \cup T_j \to (0, \dots, 0, 1, \dots, 1, 0, \dots, 0).$$

As shown in (11), this implies that the cardinality is also the same as the number of non-initial cluster variables for the bipartite cluster algebra of type $A_n$.
**Proposition 1** The set of graphs $\mathcal{G}_{A_n}$ is in bijection with the set of non-initial cluster variables for a coefficient-free cluster algebra of type $A_n$ and satisfy the statement of Theorem 1.

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

The collection $\mathcal{G}_{A_5}$.

**Proof:** See (20) for a proof using a variant of Kuo condensation (17) and a technique referred to as excision. $\square$

**Remark 2** For all $n$, if we start with the above exchange matrix $B^{A_n}$ and apply the binomial exchanges corresponding to relations 1, 3, 5, ..., $n$ (resp. $n-1$) if $n$ is odd (resp. even) the resulting exchange matrix is $-B$. Afterward, applying the relations 2, 4, 6, ..., $n-1$ (resp. $n$) if $n$ is odd (resp. even) to exchange matrix $-B^{A_n}$ results in the initial exchange matrix $B^{A_n}$. In fact, in both of these cases, the order of the exchanges does not matter, and the intermediate exchange matrices will have columns of like sign for all relevant $x_k$ not already exchanged. By the definition of matrix mutation, this procedure will in fact work for any cluster algebra where the seed has an exchange matrix that is tri-diagonal ($b_{ij} = 0$ if $|i-j| \neq 1$). Thus we can calculate a row of cluster variables at a time by applying the exchange relations relative to the two previous rows. The tri-diagonal condition includes the cases $A_n$, $B_n$, $C_n$, and $G_2$ and minor modifications to the procedure will allow it to work for $D_n$.

**Remark 3** Consider a new lattice $\{z_i^{(j)}\}$ consisting of connected subsets of $\mathcal{T}_{A_n}$ such that $T_i \in z_i^{(j)} \iff T_i$ appears in the graph associated to $x_i^{(j)}$ and add columns consisting of empty sets on the left-hand and right-hand sides of this lattice. This lattice satisfies a tropical-like diamond condition where one of the four following hold: $a = b \cup c$ and $d = b \cap c$, $a = b \cap c$ and $d = b \cup c$, $b = a \cup d$ and $c = a \cap d$, or $b = a \cap d$ and $c = a \cup d$.

**Remark 4** Such lattices are known as frieze patterns, and were studied by Conway and Coxeter (8) in the 1970's. Such patterns have also been studied in connection with cluster algebras in work of Caldero
notation $T_1$ through $T_n$ to refer to a collection of tiles, $\mathcal{T}_{C_n}$, related to $C_n$. We construct $\mathcal{T}_{C_n}$ from $\mathcal{T}_{A_n}$ by first replacing $T_2$ with a hexagon having weights 1, $x_1$, 1, $x_1$, 1, and $x_3$ in clockwise order starting from the top. We let $T_1$ be a trapezoid with a single weighted edge of $x_2$ on its northern side. Note that $T_1$ is homeomorphic to its previous definition. Then for all $i > 2$ we define $T_i$, for type $C$, as a counterclockwise rotation of the $A_n$-tile $T_i$, including the boundary tile $T_n$ which have a single weighted edge of $x_{n-1}$ on its eastern side.

<figure><img src="image_3.png" /><figcaption>Tiles for $C_5$.</figcaption></figure>

The gluing rule will be more complicated now that hexagons are involved. As in the $A_n$ and $B_n$ cases, we do not allow rotations or reflections of the tiles $T_1, T_3, T_4, \dots, T_n$; those tiles must be connected in the orientations as described above. However, we do allow a 120° clockwise rotation of tile $T_2$. As a first approximation, the set of graphs $\mathcal{G}_{C_n}$ will include any graphs that can be constructed from $\mathcal{T}_{C_n}$ while conforming to Rule 1. Any such graph will resemble either a *tower* of tiles $T_a$ through $T_b$ for $3 \le a \le b \le n$, a *base* involving hexagon $T_2$ with or without trapezoid $T_1$ on its western side, or may be a complex of a tower beginning with $T_3$ on top of a base. In addition, we enlarge the set of $\mathcal{G}_{C_n}$ by allowing any graphs that obey the following second rule:

**Rule 2** The trapezoidal tile $T_1$ may appear twice if and only if the lift of the graph to $\mathcal{G}_{C_\infty}$ (i.e. $n$ arbitrarily large) has one of the following three forms:

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

where $3 \le m_1 < m_2$, $m_1$, $m_2$ are both odd, and in the third case, the leftmost tile $T_2$ has the usual orientation and the rightmost tile $T_2$ is rotated clockwise 120°.

Notice that Rule 1 is now broken when we connect trapezoid $T_1$ to a hexagon $T_2$ on its left. Furthermore, in the last of these cases, we have adjoined an additional arc which had not been allowed or required in previous examples. However, there is precedent for using such additional arcs, see Section 3 of (19). One can check that the collection of graphs $\mathcal{G}_{C_n}$ obeying Rule 1 or Rule 2 has the cardinality equal to the number of positive roots for $C_n$.

**Proposition 3** The set of graphs $\mathcal{G}_{C_n}$ is in bijection with the set of non-initial cluster variables for a coefficient-free cluster algebra of type $C_n$ such that the statement of Theorem 1 holds.
**Proof:** See (20). We use diagonal-by-diagonal analysis of the lattice to recursively prove this combinatorial interpretation. □

We obtain a lattice where the NW to SE diagonals dictate the right towers and NE to SW diagonals dictate the left towers. There is one caveat: the *empty tower*, $Tow_0$, is now allowed. Thus one has to determine from context whether a graph consisting of a single tower is of the form $Tow_0 \cup Tow_R$ or $Tow_L \cup Tow_0$. Alternatively, we can picture the SE corner as sitting directly above the NE corner of the lattice to form a half-diamond.

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

The collection $\mathcal{G}_{C_4}$.

We were able to analyze $B_n$ based on $A_{2n-1}$ using a folding procedure. Analogously we can analyze $D_n$ using $C_{n-1}$ and an *unfolding* procedure. We label the Dynkin diagram for $D_n$ starting with 1 and $\bar{1}$ on the left, and label the rest in a line from 2 to $n-1$. Indexing the rows and columns in the order
`{1, 1, 2, 3, ..., n - 1}`, the corresponding exchange matrix is therefore

$$ \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & \dots & 0 & 0 \\ -1 & -1 & 0 & -1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & \dots & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 & \dots & 0 & 0 \\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ 0 & 0 & 0 & 0 & 0 & \dots & (-1)^n & 0 \end{bmatrix}. $$

We split the odd and even initial variables into the first two rows, in a zig-zagging pattern, just as before. We then mutate in the order 1, 1, 3, 5, ..., n (resp. n - 1) if n is odd (resp. even) to get the third row, followed by mutation via 2 then 4, 6, ... n - 1 (resp. n) if n is odd (resp. even) to get the fourth row.

The advantage of such an ordering is that the mutated exchange matrix, which we use to encode the binomial exchanges, is always the same, up to sign. We notice that the analogue of the diamond condition for this case is $ad - bc = 1$ if $b = x_i^{(j)}$ with $i \ge 2$ and

$$ x_2^{(j-1)} x_2^{(j+1)} - x_1^{(j)} x_{\bar{1}}^{(j)} x_3^{(j)} = 1 \quad (1) $$

$$ x_1^{(j-1)} x_1^{(j+1)} - x_2^{(j)} = 1 \quad (2) $$

$$ x_{\bar{1}}^{(j-1)} x_{\bar{1}}^{(j+1)} - x_2^{(j)} = 1 \quad (3) $$

on the western boundary.

We let $\mathcal{T}_{D_n}$ be $\mathcal{T}_{C_{n-1} \cup \{T_{\bar{1}}\}}$ where $T_{\bar{1}}$ is the same tile as $T_1$ except with a different label. We also change tile $T_2$ so that it is still a hexagon, but has weights 1, $x_1$, 1, $x_{\bar{1}}$, 1, and $x_3$ going around clockwise from the top. Following the arguments of Lemmas 5, 6, 7, and 8 of (20) result in the same graph theoretic interpretation and lattice structure. We use Rule 3 which is analogous to Rule 2.

**Rule 3** Notice that when we apply Rule 1 to set of tiles $\mathcal{T}_{D_n}$, we get a set of graphs consisting of a base of $T_2$ or $T_1 \cup T_2$ adjoining a tower of $T_a \cup \dots \cup T_b$, as before. We enlarge the set of graphs by allowing a base of $T_{\bar{1}} \cup T_2$ (with or without an accompanying tower), and also allow both tile $T_1$ and tile $T_{\bar{1}}$ to appear if and only if the lift of the graph to $\mathcal{G}_{D_\infty}$ (i.e. n arbitrarily large) is a variant of one of the three special forms of Rule 2, except with the leftmost trapezoid $T_1$ replaced with $T_{\bar{1}}$ in the first two cases, and in the third case, the rightmost trapezoid $T_1$ is replaced by $T_{\bar{1}}$, the leftmost tile $T_2$ has the usual orientation and the rightmost tile $T_2$ is rotated 120° clockwise, (so the weights are 1, $x_3$, 1, $x_1$, 1 and $x_{\bar{1}}$ starting from the top going clockwise).

Let $\mathcal{T}_{D_n}$ be defined as above and $\mathcal{G}_{D_n}$ be the set of graphs constructed according to Rules 1 and 3. In particular, this construction will be quite analogous to that of $\mathcal{G}_{C_{n-1}}$.

**Proposition 4** The set $\mathcal{G}_{D_n}$ is in bijection with the set of non-initial cluster variables for a coefficient-free cluster algebra of type $D_n$ such that the statement of Theorem 1 holds.

**Remark 6** As indicated, the proof follows from the exact same logic as Lemmas 5 through 8 of (20). The only caveat is that as a consequence of the proof, that $x_1^{(j)}$ will sometimes be a tower on base $T_1 \cup T_2$, and sometimes contain base $T_{\bar{1}} \cup T_2$. In particular, $x_1^{(2j-1)}$ contains $T_1$ if and only if j is odd, and so we get an alternating behavior.
**Remark 7** Recent independent work of Karin Baur and Robert Marsh (2) has given a combinatorial interpretation for the integers arising as the cluster variables of a cluster algebra of type $D_n$ with acyclic seed after specializing the initial cluster to be $\{1, 1, \dots, 1\}$. In particular, they consider ideal triangulations of the punctured $n$-gon, and provide a model involving (partial) matchings which yield a frieze pattern of integers satisfying analogues of relations (1), (2), and (3). In contrast, our work in the present paper provides the cluster variables of a cluster algebra with initial cluster $\{x_1, x_2, \dots, x_n\}$ and bipartite seed.

# 5 $G_2$

The case of $G_2$ is the only cluster algebra of exceptional finite type for which we have been able to extend our graph theoretic interpretation. We are able to do so since this case is analogous to $C_3$. We use collection $\mathcal{T}_{G_2} = \{T_1, T_2\}$ with tile $T_1$ as in the $C_n$ case, and tile $T_2$ is again a hexagon, but now has all three nontrivial weights being value $x_1$. There are six possible graphs that correspond to the non-initial cluster variables.

<figure><img src="image_6.png" /><figcaption>Graphs for a cluster algebra of type $G_2$.</figcaption></figure>

$G_2$ has Dynkin diagram $\mathbf{\&}$ and exchange matrix $\begin{bmatrix} 0 & 1 \\ -3 & 0 \end{bmatrix}$.

# 6 Future Directions

Given the previous sections, coefficient-free cluster algebras of type $A_n, B_n, C_n, D_n$, or $G_2$ have a combinatorial interpretation as a family of graphs such that the numerators of the cluster variables enumerate the weighted number of matchings and the denominators encode the occurrences of faces. Thus Theorem 1 is true in all of these cases. The next step would be to extend Theorem 1 to include cluster algebras of type $E_6, E_7, E_8$, and $F_4$, and thus have the result for all cluster algebras of finite type.

**Remark 8** Even though the Dynkin diagrams for the $E_n$'s are simply laced, fitting cluster algebras of these three types into patterns analogous to those of the $A_n$'s and $D_n$'s has been notoriously hard. Such difficulties have rose elsewhere such as in the original proof of positivity in (11), and also in recent models using T-paths on triangulated surfaces, for example in (13) or (14) among other work.
Additionally, in the work of Schiffler and Carroll-Price for $A_n$, the cluster algebra considered is specifically the Ptolemy algebra, a cluster algebra with coefficients. In the *T*-paths model, the boundary of the polygon gives rise to $(n+3)$ additional coefficients which can be included in the exchange relations and cluster expansion formula. Since the graphs we obtain in the above combinatorial interpretations are weighted so sparsely, perhaps a certain number of coefficients can be handled by the graph-model as well.

In (19), an analogous interpretation is given for rank 2 cluster algebras of affine type and unpublished work (15; 18) done as a part of REACH, as described in (21), gives a graph theoretic interpretation for a totally cyclic rank 3 cluster algebra. This totally cyclic rank 3 cluster algebra corresponds to a triangulated surface of genus one with exactly one puncture (i.e. interior marked point). Such a cluster algebra has been studied geometrically including work of (3). Perhaps these graph theoretical interpretations could be extended to other cluster algebras thus providing proofs of Fomin and Zelevinsky's positivity conjecture for even further cases.

Lastly, we note that all the examples discussed above are families of *planar* graphs associated to generators of cluster algebras. When expanding our scope to include more complicated cluster algebras, is the category of planar graphs too restrictive? More specifically, why did we need the extra arcs in the $C_n, D_n, G_2$, and affine $A_1^{(2)}$ cases? Perhaps it is an artifice of taking a higher dimensional object and projecting to two dimensions.

**Acknowledgments.** The author would like to thank Andrei Zelevinsky for numerous helpful conversations including referring the author to (12) where Fibonacci polynomials appear. Discussions with Sergey Fomin, Jim Propp, Ralf Schiffler, and Hugh Thomas have also been very useful. I wanted to especially thank Hugh Thomas and Andrei Zelevinsky for their comments on an earlier draft of this paper.

## References

[1] I. Assem, D. Simson, and A. Skowronski, *Elements of the representation theory of associated algebras*. Vol. 1. Techniques of representation theory. London Mathematical Society Student Texts, **65**. Cambridge University Press, Cambridge, 2006.

[2] K. Baur and R. Marsh, Ptolemy relations for punctured discs, preprint (2007) arXiv/math:CO/07111443

[3] A. Beineke, T. Brüstle and L. Hille, Cluster-cyclic quivers with three vertices and the Markov Equation, preprint (2006) arXiv/math/RA/0612213.

[4] P. Caldero and A. Zelevinsky, Laurent expansions in cluster algebras via quiver representations, *Moscow Math. J.* **6** (2006), 411-429.

[5] P. Caldero and F. Chapoton, Cluster algebras as Hall algebras of quiver representations, *Comment. Math. Helv.* **81** (2006), 595-616.

[6] P. Caldero and M. Reineke, On the quiver Grassmannian in the acyclic case, preprint (2006) arXiv/math/RT/0611074.

[7] G. Carroll and G. Price, Two new combinatorial models for the Ptolemy recurrence, unpublished memo (2003).
[8] J. Conway and H.S.M. Coxeter, Triangulated polygons and frieze patterns, *Math. Gaz.* **57** (1973), 87-94.

[9] S. Fomin and A. Zelevinsky, Cluster algebras I: Foundations, *J. Amer. Math. Soc.* **15** (2002), 497-529.

[10] S. Fomin and A. Zelevinsky, The Laurent phenomenon, *Adv. in Applied Math.* **28** (2002), 119-144.

[11] S. Fomin and A. Zelevinsky, Cluster algebras II: Finite type classification, *Invent. Math.* **154** (2003), 63-121.

[12] S. Fomin and A. Zelevinsky, Y-systems and generalized associahedra, *Ann. of Math.* **158** (2003), 977-1018.

[13] S. Fomin and A. Zelevinsky, Cluster algebras IV: Coefficients, *Compositio Mathematica* **143** (2007), 112-164.

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

[15] A. Itsara, G. Musiker, J. Propp, and R. Viana, Combinatorial interpretations for the Markoff numbers, unpublished memo (2003).

[16] V. Kac *Infinite dimensional Lie algebras*, 3rd edition, Cambridge University Press, 1990.

[17] E. Kuo, Applications of graphical condensation for enumerating matchings and tilings, *Theoret. Comput. Sci.* **319** (2004), 29-57.

[18] G. Musiker, A conjectured combinatorial interpretation for the Markoff numbers, unpublished memo (2002).

[19] G. Musiker and J. Propp, Combinatorial interpretations for rank-two cluster algebras of affine type, *Electron. J. Combin.* **14** no. 1, Research Paper 15 (2007), 1-23.

[20] G. Musiker, A graph theoretical expansion formula for cluster algebras of classical type, preprint (2007) arXiv/math:CO/07103574.

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

[22] R. Schiffler, A cluster expansion formula ($A_n$ case), preprint (2006) arXiv/math:RT/0611956.

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

[24] P. Sherman and A. Zelevinsky, Positivity and canonical bases in rank 2 cluster algebras of finite and affine types, *Moscow Math. J.* **4** (2004), No. 4, 947-974.

[25] H. Thomas, Personal communication.

[26] A. Zelevinsky, Semicanonical basis generators of the cluster algebra of type $A_1^{(1)}$, *Electron. J. Combin.* **14** no. 1, Note 5 (2007), 1-4.