Cluster expansion formulas and perfect matchings.

*(English)*Zbl 1246.13035Cluster algebras, introduced in [S. Fomin and A. Zelevinsky, J. Am. Math. Soc. 15, no. 2, 497–529 (2002; Zbl 1021.16017)], 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,\ldots,x_n\) over the quotient field of the integer group ring \(\mathbb{ZP}\). Thus \(\mathbf{x}=\{x_1,x_2,\ldots,x_n\}\) is a transcendence basis for \(\mathcal{F}\). For every \(k=1,2,\ldots,n\), the mutation \(\mu_k(\mathbf{x})\) of the cluster \(\mathbf{x}=\{x_1,x_2,\ldots,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) \] in \(\mathcal{F}\), where \(y_k^+,y_k^-\) are certain monomials in \(y_1,y_2,\ldots,y_n\). Mutations also change the attached matrix \(B\) as well as the coefficient vector \(\mathbf{y}\). The set of all cluster variables is the union of all clusters obtained from an initial cluster \(\mathbf{x}\) by repeated mutations.

It follows from the construction that every cluster variable is a rational function in the initial cluster variables \(x_1,x_2,\ldots,x_n\). In S. Fomin and A. Zelevinsky [loc. cit.], 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,\ldots,x_n)}{\prod_{i=1}^n x_i^{d_i}}, \] where \(f\in\mathbb{ZP}[x_1,x_2,\ldots,x_n]\) and \(d_i\geq 0\). The right hand side of this equation is called the cluster expansion of \(u\) in \(\mathbf{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 [S. Fomin and A. Zelevinsky, Compos. Math. 143, No. 1, 112–164 (2007; Zbl 1127.16023)], which means that the coefficient group \(\mathbb{P}\) is the free abelian group on \(n\) generators \(y_1,y_2,\ldots,y_n\), and the initial coefficient tuple \(\mathbf{y}=\{y_1,y_2,\ldots,y_n\}\) consists of these \(n\) generators. Note 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.

In the landmark paper [S. Fomin, M. Shapiro and D. Thurston, Acta Math. 201, No. 1, 83–146 (2008; Zbl 1263.13023)], the authors 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. Note that 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.

In the paper under review, the authors study cluster algebras with principal coefficient systems associated to unpunctured surfaces. They give a direct formula for the Laurent polynomial expansion of cluster variables in these cluster algebras in terms of perfect matchings of a certain weighted graph that is constructed from the surface by recursive glueing of elementary pieces called 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 is called a tile. So they 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\). Then they 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 \(P\) of this graph one can associate its weight \(w(P)\) which is the product of the weights of its edges, hence a product of cluster variables. They prove the following cluster expansion formula:

Theorem 3.1. \[ x_\gamma = \sum_P \frac{w(P)\,y(P)}{x_{i_1}x_{i_2}\ldots x_{i_d}}, \] where the sum is over all perfect matchings \(P\) of \(G_{T,\gamma}\), \(w(P)\) is the weight of \(P\), and \(y(P)\) is a monomial in \(\mathbf{y}\).

They also give a formula for the coefficients \(y(P)\) in terms of perfect matchings. There are two corresponding matchings which are the unique two matchings that have all their edges on the boundary of the graph \(G_{T,\gamma}\). Denote by \(P_-\) the one with \(y(P_-)=1\) and the other by \(P_+\). Now, for an arbitrary perfect matching \(P\), the coefficient \(y(P)\) is determined by the set of edges of the symmetric difference \(P_-\ominus P =(P_-\cup P)\setminus (P_-\cap P)\) as follows.

Theorem 5.1. The set \(P_-\ominus P\) is the set of boundary edges of a (possibly disconnected) subgraph \(G_P\) of \(G_{T,\gamma}\) which is a union of tiles \( G_P =\bigcup_{j\in J} S_j. \) Moreover, \[ y(P)=\prod_{j\in J} y_{i_j}. \]

The third main result of this paper is yet another description of the formula of Theorem 3.1 in terms of the graph \(G_{T,\gamma}\) 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,\gamma}\) 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 \(P_-\) 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 6.1. The cluster expansion of the cluster variable \(x_\gamma\) is given by \[ x_\gamma=\sum_{k=0}^d \;\sum_{H\in \mathcal{H}_k} \frac{w(\partial H\ominus P_-)\,y(H)}{x_{i_1} x_{i_2}\cdots x_{i_d}}. \]

It is worth pointing out that, in a sequel to the present paper [G. Musiker, R. Schiffler and L. Williams, Adv. Math. 227, No. 6, 2241–2308 (2011; Zbl 1331.13017)], the authors give expansion formulas for the cluster variables in cluster algebras from arbitrary surfaces (allowing punctures) and prove the positivity conjecture for these cluster algebras.

To be more precise, let \(\mathcal{F}\) be the field of rational functions in the indeterminates \(x_1,x_2,\ldots,x_n\) over the quotient field of the integer group ring \(\mathbb{ZP}\). Thus \(\mathbf{x}=\{x_1,x_2,\ldots,x_n\}\) is a transcendence basis for \(\mathcal{F}\). For every \(k=1,2,\ldots,n\), the mutation \(\mu_k(\mathbf{x})\) of the cluster \(\mathbf{x}=\{x_1,x_2,\ldots,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) \] in \(\mathcal{F}\), where \(y_k^+,y_k^-\) are certain monomials in \(y_1,y_2,\ldots,y_n\). Mutations also change the attached matrix \(B\) as well as the coefficient vector \(\mathbf{y}\). The set of all cluster variables is the union of all clusters obtained from an initial cluster \(\mathbf{x}\) by repeated mutations.

It follows from the construction that every cluster variable is a rational function in the initial cluster variables \(x_1,x_2,\ldots,x_n\). In S. Fomin and A. Zelevinsky [loc. cit.], 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,\ldots,x_n)}{\prod_{i=1}^n x_i^{d_i}}, \] where \(f\in\mathbb{ZP}[x_1,x_2,\ldots,x_n]\) and \(d_i\geq 0\). The right hand side of this equation is called the cluster expansion of \(u\) in \(\mathbf{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 [S. Fomin and A. Zelevinsky, Compos. Math. 143, No. 1, 112–164 (2007; Zbl 1127.16023)], which means that the coefficient group \(\mathbb{P}\) is the free abelian group on \(n\) generators \(y_1,y_2,\ldots,y_n\), and the initial coefficient tuple \(\mathbf{y}=\{y_1,y_2,\ldots,y_n\}\) consists of these \(n\) generators. Note 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.

In the landmark paper [S. Fomin, M. Shapiro and D. Thurston, Acta Math. 201, No. 1, 83–146 (2008; Zbl 1263.13023)], the authors 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. Note that 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.

In the paper under review, the authors study cluster algebras with principal coefficient systems associated to unpunctured surfaces. They give a direct formula for the Laurent polynomial expansion of cluster variables in these cluster algebras in terms of perfect matchings of a certain weighted graph that is constructed from the surface by recursive glueing of elementary pieces called 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 is called a tile. So they 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\). Then they 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 \(P\) of this graph one can associate its weight \(w(P)\) which is the product of the weights of its edges, hence a product of cluster variables. They prove the following cluster expansion formula:

Theorem 3.1. \[ x_\gamma = \sum_P \frac{w(P)\,y(P)}{x_{i_1}x_{i_2}\ldots x_{i_d}}, \] where the sum is over all perfect matchings \(P\) of \(G_{T,\gamma}\), \(w(P)\) is the weight of \(P\), and \(y(P)\) is a monomial in \(\mathbf{y}\).

They also give a formula for the coefficients \(y(P)\) in terms of perfect matchings. There are two corresponding matchings which are the unique two matchings that have all their edges on the boundary of the graph \(G_{T,\gamma}\). Denote by \(P_-\) the one with \(y(P_-)=1\) and the other by \(P_+\). Now, for an arbitrary perfect matching \(P\), the coefficient \(y(P)\) is determined by the set of edges of the symmetric difference \(P_-\ominus P =(P_-\cup P)\setminus (P_-\cap P)\) as follows.

Theorem 5.1. The set \(P_-\ominus P\) is the set of boundary edges of a (possibly disconnected) subgraph \(G_P\) of \(G_{T,\gamma}\) which is a union of tiles \( G_P =\bigcup_{j\in J} S_j. \) Moreover, \[ y(P)=\prod_{j\in J} y_{i_j}. \]

The third main result of this paper is yet another description of the formula of Theorem 3.1 in terms of the graph \(G_{T,\gamma}\) 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,\gamma}\) 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 \(P_-\) 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 6.1. The cluster expansion of the cluster variable \(x_\gamma\) is given by \[ x_\gamma=\sum_{k=0}^d \;\sum_{H\in \mathcal{H}_k} \frac{w(\partial H\ominus P_-)\,y(H)}{x_{i_1} x_{i_2}\cdots x_{i_d}}. \]

It is worth pointing out that, in a sequel to the present paper [G. Musiker, R. Schiffler and L. Williams, Adv. Math. 227, No. 6, 2241–2308 (2011; Zbl 1331.13017)], the authors give expansion formulas for the cluster variables in cluster algebras from arbitrary surfaces (allowing punctures) and prove the positivity conjecture for these cluster algebras.

Reviewer: Xueqing Chen (Whitewater)

##### MSC:

13F60 | Cluster algebras |

05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

16G20 | Representations of quivers and partially ordered sets |

##### References:

[1] | Amiot, C.: Cluster categories for algebras of global dimension 2 and quivers with potential. Ann. Inst. Fourier (to appear) · Zbl 1239.16011 |

[2] | Assem, I., Brüstle, T., Charbonneau-Jodoin, G., Plamondon, P.G.: Gentle algebras arising from surface triangulations. Preprint, arXiv:0903.3347 · Zbl 1242.16011 |

[3] | Buan, A.; Marsh, R.; Reineke, M.; Reiten, I.; Todorov, G., Tilting theory and cluster combinatorics, Adv. Math., 204, 572-612, (2006) · Zbl 1127.16011 |

[4] | Buan, A. B.; Marsh, R.; Reiten, I., Denominators of cluster variables, J. Lond. Math. Soc., 79, 589-611, (2009) · Zbl 1237.16009 |

[5] | Caldero, P.; Chapoton, F., Cluster algebras as Hall algebras of quiver representations, Comment. Math. Helv., 81, 595-616, (2006) · Zbl 1119.16013 |

[6] | Caldero, P.; Keller, B., From triangulated categories to cluster algebras II, Ann. Sci. École Norm. Sup. (4), 39, 983-1009, (2006) · Zbl 1115.18301 |

[7] | Caldero, P.; Keller, B., From triangulated categories to cluster algebras, Invent. Math., 172, 169-211, (2008) · Zbl 1141.18012 |

[8] | Caldero, P.; Zelevinsky, A., Laurent expansions in cluster algebras via quiver representations, Mosc. Math. J., 6, 411-429, (2006) · Zbl 1133.16012 |

[9] | Caldero, P.; Chapoton, F.; Schiffler, R., Quivers with relations arising from clusters \((A\_{}\{n\}\) case), Trans. Am. Math. Soc., 358, 1347-1364, (2006) · Zbl 1137.16020 |

[10] | Caldero, P.; Chapoton, F.; Schiffler, R., Quivers with relations and cluster tilted algebras, Algebr. Represent. Theory, 9, 359-376, (2006) · Zbl 1127.16013 |

[11] | Carroll, G., Price, G.: Unpublished result |

[12] | Elkies, N.; Kuperberg, G.; Larsen, M.; Propp, J., Alternating-sign matrices and domino tilings (Part I), J. Algebr. Comb., 1, 11-132, (1992) · Zbl 0779.05009 |

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

[14] | Fock, V.; Goncharov, A., Moduli spaces of local systems and higher Teichmüller theory, Publ. Math. Inst. Hautes Études Sci., 103, 1-211, (2006) · Zbl 1099.14025 |

[15] | Fock, V.; Goncharov, A., Dual Teichmüller and lamination spaces, No. 11, 647-684, (2007), Zürich · Zbl 1162.32009 |

[16] | Fomin, S., Thurston, D.: Cluster algebras and triangulated surfaces. Part II: Lambda lengths. Preprint (2008). http://www.math.lsa.umich.edu/ fomin/Papers/cats2.ps · Zbl 07000309 |

[17] | Fomin, S.; Zelevinsky, A., Cluster algebras I. Foundations, J. Am. Math. Soc., 15, 497-529, (2002) · Zbl 1021.16017 |

[18] | Fomin, S.; Zelevinsky, A., Cluster algebras IV: Coefficients, Comput. Math., 143, 112-164, (2007) · Zbl 1127.16023 |

[19] | Fomin, S., Zelevinsky, A.: Unpublished result |

[20] | Fomin, S.; Shapiro, M.; Thurston, D., Cluster algebras and triangulated surfaces. Part I: Cluster complexes, Acta Math., 201, 83-146, (2008) · Zbl 1263.13023 |

[21] | Fu, C., Keller, B.: On cluster algebras with coefficients and 2-Calabi-Yau categories. Trans. Am. Math. Soc. (to appear). arXiv:0710.3152 · Zbl 1201.18007 |

[22] | Gekhtman, M.; Shapiro, M.; Vainshtein, A., Cluster algebras and Poisson geometry, Mosc. Math. J., 3, 899-934, (2003) · Zbl 1057.53064 |

[23] | Gekhtman, M.; Shapiro, M.; Vainshtein, A., Cluster algebras and Weil-Petersson forms, Duke Math. J., 127, 291-311, (2005) · Zbl 1079.53124 |

[24] | Labardini-Fragoso, D.: Quivers with potentials associated to triangulated surfaces. Proc. Lond. Math. Soc. (to appear). arXiv:0803.1328 · Zbl 1241.16012 |

[25] | Musiker, G.: A graph theoretic expansion formula for cluster algebras of classical type. Ann. Comb. (to appear). arXiv:0710.3574 · Zbl 1233.05118 |

[26] | Musiker, G., Propp, J.: Combinatorial interpretations for rank-two cluster algebras of affine type. Electron. J. Comb. 14(1) (2007), Research Paper 15, 23 pp. (electronic). arXiv:math/0602408 · Zbl 1140.05053 |

[27] | Musiker, G., Schiffler, R., Williams, L.: Positivity for cluster algebras from surfaces. Preprint. arXiv:0906.0748 · Zbl 1331.13017 |

[28] | Palu, Y., Cluster characters for triangulated 2-Calabi-Yau triangulated categories, Ann. Inst. Fourier, 58, 2221-2248, (2008) · Zbl 1154.16008 |

[29] | Propp, J.: Lattice structure for orientations of graphs. Preprint (1993). arXiv:0209.5005 [math] |

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

[31] | Schiffler, R.: A cluster expansion formula \((A\_{}\{n\}\) case), Electron. J. Comb. 15 (2008), #R64 1. arXiv:math.RT/0611956 · Zbl 1184.13064 |

[32] | Schiffler, R.: On cluster algebras arising from unpunctured surfaces II. Adv. Math. (to appear). arXiv:0809.2593 · Zbl 1238.13029 |

[33] | Schiffler, R.; Thomas, H., On cluster algebras arising from unpunctured surfaces, Int. Math. Res. Not., 17, 3160-3189, (2009) · Zbl 1171.30019 |

[34] | Sherman, P.; Zelevinsky, A., Positivity and canonical bases in rank 2 cluster algebras of finite and affine types, Mosc. Math. J., 4, 947-974, (2004) · Zbl 1103.16018 |

[35] | Zelevinsky, A.: Semicanonical basis generators of the cluster algebra of type \(A^{(1)}_1 \). Electron. J. Comb. 14(1) (2007), Note 4, 5 pp. (electronic). arXiv:math.RA/0606775 · Zbl 1144.16015 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.