# Denominator vectorsr and compatibility degrees in cluster algebras of finite type

Cesar Ceballos$^{1†}$ and Vincent Pilaud$^{2‡}$

**Abstract.** We present two simple descriptions of the denominator vectors of the cluster variables of a cluster algebra of finite type, with respect to any initial cluster seed: one in terms of the compatibility degrees between almost positive roots defined by S. Fomin and A. Zelevinsky, and the other in terms of the root function of a certain subword complex. These descriptions only rely on linear algebra, and provide simple proofs of the known fact that the *d*-vector of any non-initial cluster variable with respect to any initial cluster seed has non-negative entries and is different from zero.

**Résumé.** Nous présentons deux descriptions élémentaires des vecteurs dénominateurs des algèbres amassées de type fini pour tout amas initial: l'une en termes de degrés de compatibilité entre racines presque positives définis par S. Fomin et A. Zelevinsky, et l'autre en termes de la fonction racine d'un certain complexe de sous-mots. Ces descriptions ne reposent que sur l'algèbre linéaire et fournissent des preuves simples du fait (connu) que le *d*-vecteur de toute variable d'amas, qui n'est pas dans l'amas initial, a des entrées positives ou nulles et est différent du vecteur nul.

**Keywords:** Finite type cluster algebras, *d*-vectors, subword complexes.

## 1 Introduction

*Cluster algebras* were introduced by S. Fomin and A. Zelevinsky in [FZ02, FZ03a]. They are commutative rings generated by a (possibly infinite) set of *cluster variables*, which are grouped into overlapping *clusters*. The clusters can be obtained from any *initial cluster seed* $X = \{x_1, \dots, x_n\}$ by a mutation process. Each mutation exchanges a single variable *y* to a new variable *y'* satisfying a relation of the form $yy' = M_+ + M_-$, where $M_+$ and $M_-$ are monomials in the variables involved in the current cluster and distinct from *y* and *y'*. The precise content of these monomials $M_+$ and $M_-$ is controlled by a combinatorial object (a skew-symmetrizable matrix, or equivalently a weighted quiver [Kel12]) which is attached to each cluster and is also transformed during the mutation. We refer to [FZ02] for the precise definition of these joint dynamics. In [FZ02, Thm. 3.1], S. Fomin and A. Zelevinsky proved that given any initial cluster seed $X = \{x_1, \dots, x_n\}$, the cluster variables obtained during this mutation process are

<footnote>$^{1}$Department of Mathematics and Statistics, York University, Toronto, Ontario M3J 1P3, Canada</footnote>

<footnote>$^{2}$CNRS & LIX, École Polytechnique, 91128 Palaiseau, France</footnote>

<footnote>†Supported by DFG via the Research Training Group “Methods for Discrete Structures” and the Berlin Mathematical School.</footnote>

<footnote>‡Supported by the Spanish MICINN grant MTM2011-22792, by the French ANR grant EGOS 12 JS02 002 01, and by the European Research Project ExploreMaps (ERC StG 208471).</footnote>
Laurent polynomials in the variables $x_1, \dots, x_n$. That is to say, every non-initial cluster variable $y$ can be written in the form

$$y = \frac{F(x_1, \dots, x_n)}{x_1^{d_1} \dots x_n^{d_n}}$$

where $F(x_1, \dots, x_n)$ is a polynomial which is not divisible by any variable $x_i$ for $i \in [n]$. This intriguing property is called *Laurent Phenomenon* in cluster algebras [FZ02]. The *denominator vector* (or *d-vector* for short) of the cluster variable $y$ with respect to the initial cluster seed $X$ is defined as the vector $\mathbf{d}(X, y) := (d_1, \dots, d_n)$. The *d-vector* of the initial cluster variable $x_i$ is by definition $\mathbf{d}(X, x_i) := -e_i := (0, \dots, -1, \dots, 0)$.

Note that we think of the cluster variables as a set of variables satisfying some algebraic relations. These variables can be expressed in terms of the variables in any initial cluster seed $X = \{x_1, \dots, x_n\}$ of the cluster algebra. Starting from a different cluster seed $X' = \{x'_1, \dots, x'_n\}$ would give rise to an isomorphic cluster algebra, expressed in terms of the variables $x'_1, \dots, x'_n$ of this seed. Therefore, the *d-vectors* of the cluster variables depend on the choice of the initial cluster seed $X$ in which the Laurent polynomials are expressed. This dependence is explicit in the notation $\mathbf{d}(X, y)$. Note also that since the denominator vectors do not depend on coefficients, we restrict our attention to coefficient-free cluster algebras.

In this paper, we only consider finite type cluster algebras, i.e. cluster algebras whose mutation graph is finite. They were classified in [FZ03a, Thm. 1.4] using the Cartan-Killing classification for finite crystallographic root systems. In [FZ03a, Thm. 1.9], S. Fomin and A. Zelevinsky proved that in the cluster algebra of any given finite type, with a bipartite quiver as initial cluster seed,

(i) there is a bijection $\phi$ from almost positive roots to cluster variables, which sends the negative simple roots to the initial cluster variables;

(ii) the *d-vector* of the cluster variable $\phi(\beta)$ corresponding to an almost positive root $\beta$ is given by the vector $(b_1, \dots, b_n)$ of coefficients of the root $\beta = \sum b_i \alpha_i$ on the linear basis $\Delta$ formed by the simple roots $\alpha_1, \dots, \alpha_n$; and

(iii) these coefficients coincide with the *compatibility degrees* $(\alpha_i \parallel \beta)$ defined in [FZ03b, Sec. 3.1].

These results were extended to all cluster seeds corresponding to Coxeter elements of the Coxeter group (see e.g. [Kel12, Thm. 3.1 & Sec. 3.3]). More precisely, assume that the initial seed is the cluster $X_c$ corresponding to a Coxeter element $c$ (its associated quiver is the Coxeter graph oriented according to $c$). Then one can define a bijection $\phi_c$ from almost positive roots to cluster variables such that the *d-vector* of the cluster variable $\phi_c(\beta)$ corresponding to $\beta$, with respect to the initial cluster seed $X_c$, is still given by the vector $(b_1, \dots, b_n)$ of coordinates of $\beta = \sum b_i \alpha_i$ in the basis $\Delta$ of simple roots. Under this bijection, the collections of almost positive roots corresponding to clusters are called *c-clusters* and were studied by N. Reading [Rea07, Sec. 7].

In this paper, we provide similar interpretations for the denominators of the cluster variables of any finite type cluster algebra with respect to *any initial cluster seed* (acyclic or not):

(i) Our first description (Corollary 3.2) uses compatibility degrees: if $\{\beta_1, \dots, \beta_n\}$ is the set of almost positive roots corresponding to the cluster variables in any initial seed $X = \{\phi(\beta_1), \dots, \phi(\beta_n)\}$, then the *d-vector* of the cluster variable $\phi(\beta)$ corresponding to an almost positive root $\beta$, with respect to the initial cluster seed $X$, is given by the vector of compatibility degrees $((\beta_1 \parallel \beta), \dots, (\beta_n \parallel \beta))$ of [FZ03b, Sec. 3.1]. We also provide a refinement of this result parametrized by a Coxeter element $c$, using the bijection $\phi_c$ together with the notion of *c-compatibility degrees* (Corollary 3.3).
(ii) Our second description (Corollary 3.4) uses the recent connection [CLS13] between the theory of cluster algebras of finite type and the theory of subword complexes, initiated by A. Knutson and E. Miller [KM04]. We describe the entries of the $d$-vector in terms of certain coefficients given by the root function of a subword complex associated to a certain word.

These results lead to simple alternative proofs of the known fact that, in a cluster algebra of finite type, the $d$-vector of any non-initial cluster variable with respect to any initial cluster seed is non-negative and not equal to zero (Corollary 3.5).

Finally, we also provide explicit geometric interpretations for all the concepts and results in this paper for the classical types $A, B, C$ and $D$ in Section 4. Our interpretation in type $D$ is new and differs from known interpretations in the literature. It simplifies certain combinatorial and algebraic aspects and makes an additional link between the theory of cluster algebras and pseudotriangulations [RSS08].

The proofs of our results, omitted in this extended abstract, can be found in [CP13].

## 2 Preliminaries

Let $(W, S)$ be a finite crystallographic Coxeter system of rank $n$. We consider a root system $\Phi$, with simple roots $\Delta := \{\alpha_1, \dots, \alpha_n\}$, positive roots $\Phi^+$, and almost positive roots $\Phi_{\ge -1} := \Phi^+ \cup -\Delta$. We refer to [Hum90] for a reference on Coxeter groups and root systems.

Let $\mathcal{A}(W)$ denote the cluster algebra associated to type $W$, as defined in [FZ03a]. Each cluster is formed by $n$ cluster variables, and is endowed with a weighted quiver (an oriented and weighted graph on $S$) which controls the cluster dynamics. Since we will not make extensive use of it, we believe that it is unnecessary to recall here the precise definition of the quiver and cluster dynamics, and we refer to [FZ02, Kel12] for details. For illustrations, we recall geometric descriptions of these dynamics in types $A, B, C$, and $D$ in Section 4.

Let $c$ be a Coxeter element of $W$, and $c := (c_1, \dots, c_n)$ be a reduced expression of $c$. The element $c$ defines a particular weighted quiver $\mathcal{Q}_c$: the Coxeter graph of the Coxeter system $(W, S)$ directed according to the order of appearance of the simple reflections in $c$. We denote by $X_c$ the cluster seed whose associated quiver is $\mathcal{Q}_c$. Let $w_\circ(c) := (w_1, \dots, w_N)$ denote the *c-sorting word* for $w_\circ$, i.e. the lexically first subword of the infinite word $c^\infty$ which represents a reduced expression for the longest element $w_\circ \in W$. We consider the word $\mathcal{Q}_c := \text{cw}_\circ(c)$ and denote by $m := n + N$ the length of this word.

### 2.1 Cluster variables, almost positive roots, and positions in the word $\mathcal{Q}_c$

We recall here the above-mentioned bijections between cluster variables, almost positive roots and positions in the word $\mathcal{Q}_c$. We will see in the next sections that both the clusters and the $d$-vectors (expressed on any initial cluster seed $X$) can also be read off in these different contexts. Figure 1 summarizes these different notions and the corresponding notations. We insist that the choice of the Coxeter element $c$ and the choice of the initial cluster $X$ are not related. The former provides a labeling of the cluster variables by the almost positive roots or by the positions in $\mathcal{Q}_c$, while the latter gives an algebraic basis to express the cluster variables and to assign them $d$-vectors.

First, there is a natural bijection between cluster variables and almost positive roots, which can be parametrized by the Coxeter element $c$. Start from the initial cluster seed $X_c$ associated to the weighted quiver $\mathcal{Q}_c$ corresponding to the Coxeter element $c$. Then the $d$-vectors of the cluster variables of $\mathcal{A}(W)$ with respect to the initial seed $X_c$ are given by the almost positive roots $\Phi_{\ge -1}$. This defines a bijection $\phi_c$ from almost positive roots to cluster variables. Notice that this bijection depends on the choice of the
<figure><img src="image_1.png" /><figcaption>Fig. 1: Three different contexts for cluster algebras of finite type, their different notions of compatibility degrees, and the bijections between them. See Sections 2.1, 2.2 and 2.3 for definitions.</figcaption></figure>

Coxeter element $c$. When $c$ is a bipartite Coxeter element, it is the bijection $\phi$ of S. Fomin and A. Zelevinsky [FZ03a, Thm. 1.9] mentioned above. Transporting the structure of the cluster algebra $\mathcal{A}(W)$ through the bijection $\phi_c$, we say that a subset $B$ of almost positive roots forms a *c-cluster* iff the corresponding subset of cluster variables $\phi_c(B)$ forms a cluster of $\mathcal{A}(W)$. The collection of $c$-clusters forms a simplicial complex on the set $\Phi_{\ge -1}$ of almost positive roots called the *c-cluster complex*. This complex was described in purely combinatorial terms by N. Reading in [Rea07, Sec. 7]. Given an initial $c$-cluster seed $B := \{\beta_1, \dots, \beta_n\}$ in $\Phi_{\ge -1}$ and an almost positive root $\beta$, we define the $d$-vector of $\beta$ with respect to $B$ as $d_c(B, \beta) := d(\phi_c(B), \phi_c(\beta))$. If $c$ is a bipartite Coxeter element, then we speak about classical clusters and omit $c$ in the previous notation to write $d(B, \beta)$.

Second, there is a bijection $\chi_c$ from the positions in the word $Q_c = cw_\circ(c)$ to the almost positive roots as follows. The letter $c_i$ of $c$ is sent to the negative root $-\alpha_{c_i}$, while the letter $w_i$ of $w_\circ(c)$ is sent to the positive root $w_1 \cdots w_{i-1}(\alpha_{w_i})$. To be precise, note that this bijection depends not only on the Coxeter element $c$, but also on its reduced expression $c$. This bijection was defined by C. Ceballos, J.-P. Labbé and C. Stump in [CLS13, Thm. 2.2].

Composing the two maps described above provides a bijection $\psi_c$ from positions in the word $Q_c$ to cluster variables (precisely defined by $\psi_c := \phi_c \circ \chi_c$). Transporting the structure of $\mathcal{A}(W)$ through the bijection $\psi_c$, we say that a subset $I$ of positions in $Q_c$ forms a *c-cluster* iff the corresponding cluster variables $\psi_c(I)$ form a cluster of $\mathcal{A}(W)$. Moreover, given an initial $c$-cluster seed $I \subseteq [m]$ in $Q_c$ and a position $j \in [m]$ in $Q_c$, we define the $d$-vector of $j$ with respect to $I$ as $d_c(I, j) := d(\psi_c(I), \psi_c(j))$. It turns out that the $c$-clusters can be read off directly in the word $Q_c$ as follows.

**Theorem 2.1 ([CLS13, Thm. 2.2 & Coro. 2.3)** A subset $I$ of positions in $Q_c$ forms a $c$-cluster in $Q_c$ if and only if the subword of $Q_c$ formed by the complement of $I$ is a reduced expression for $w_\circ$.

**Remark 2.2** The previous theorem relates $c$-cluster complexes to subword complexes as defined by A. Knutson and E. Miller [KM04]. Given a word $Q$ on the generators $S$ of $W$ and an element $\pi \in W$, the subword complex $\mathcal{S}C(Q, \rho)$ is the simplicial complex whose faces are subwords $P$ of $Q$ such that the complement $Q \setminus P$ contains a reduced expression of $\pi$. See [CLS13] for more details on this connection.
## 2.2 The rotation map

In this section we introduce a rotation map $\tau_c$ on the positions in the word $Q_c$, and naturally extend it to a map on almost positive roots and cluster variables using the bijections of Section 2.1 (see Figure 1). The rotation map plays the same role for arbitrary finite type as the rotation of the polygons associated to the classical types A, B, C and D, see e.g. [CLS13, Thm. 8.10] and Section 4.

**Definition 2.3 (Rotation maps)** The rotation $\tau_c : [m] \to [m]$ is the map on the positions in the word $Q_c$ defined as follows. If $q_i = s$, then $\tau_c(i)$ is defined as the position in $Q_c$ of the next occurrence of $s$ if possible, and as the first occurrence of $w_0sw_0$ otherwise.

Using the bijections $\chi_c$ (resp. $\psi_c$) from the positions in the word $Q_c$ to almost positive roots (resp. to cluster variables), this rotation can also be regarded as a map on almost positive roots (resp. on cluster variables). For simplicity, we abuse notation and also write $\tau_c$ for the composition $\chi_c \circ \tau_c \circ \chi_c^{-1}$ and $\tau$ for the composition $\psi_c \circ \tau_c \circ \psi_c^{-1}$. These maps can also be expressed purely in terms of almost positive roots or cluster variables, see [CP13].

**Lemma 2.4** The rotation map preserves clusters:

(i) a subset $I \subset [m]$ of positions in the word $Q_c$ is a c-cluster if and only if $\tau_c(I)$ is a c-cluster;

(ii) a subset $B \subset \Phi_{\ge -1}$ of almost positive roots is a c-cluster if and only if $\tau_c(B)$ is a c-cluster; and

(iii) a subset $X$ of cluster variables is a cluster if and only if $\tau(X)$ is a cluster.

**Remark 2.5** Let $c$ be a bipartite Coxeter element, with sources corresponding to the positive vertices (+) and sinks corresponding to the negative vertices ($-$). Then, the rotation $\tau_c$ on the set of almost positive roots is the product of the maps $\tau_+, \tau_- : \Phi_{\ge -1} \to \Phi_{\ge -1}$ defined in [FZ03b, Sec. 2.2]. We refer the interested reader to that paper for the definitions of $\tau_+$ and $\tau_-$.

## 2.3 Three descriptions of c-compatibility degrees

In this section we introduce three notions of compatibility degrees on the set of cluster variables, almost positive roots, and positions in the word $Q_c$. We will see in Section 3 that these three notions coincide under the bijections of Section 2.1, and will use it to describe three different ways to compute d-vectors for cluster algebras of finite type. We refer again to Figure 1 for a summary of our notations in these three situations.

**On cluster variables.** Let $X = \{x_1, \dots, x_n\}$ be a set of cluster variables of $\mathcal{A}(W)$ forming a cluster, and let

$$y = \frac{F(x_1, \dots, x_n)}{x_1^{d_1} \cdots x_n^{d_n}} \qquad (1)$$

be a cluster variable of $\mathcal{A}(W)$ expressed in terms of the variables $\{x_1, \dots, x_n\}$ such that $F(x_1, \dots, x_n)$ is a polynomial which is not divisible by any variable $x_j$ for $j \in [n]$. Recall that the d-vector of $y$ with respect to $X$ is $d(X, y) = (d_1, \dots, d_n)$.

**Lemma 2.6** For cluster algebras of finite type, the i-th component of the d-vector $d(X, y)$ is independent of the cluster $X$ containing the cluster variable $x_i$.

**Definition 2.7 (Compatibility degree on cluster variables)** For any two cluster variables $x$ and $y$, we denote by $d(x, y)$ the $x$-component of the $d$-vector $d(X, y)$ for any cluster $X$ containing the variable $x$. We refer to $d(x, y)$ as the compatibility degree of $y$ with respect to $x$.
**On almost positive roots.** Extending the definition of [FZ03b, Sec. 3.1], we now define compatibility degrees on almost positive roots.

**Definition 2.8 (c-compatibility degree on almost positive roots)** *The c-compatibility degree on the set of almost positive roots is the unique function*

$$ \Phi_{\ge -1} \times \Phi_{\ge -1} \xrightarrow{\qquad} \mathbb{Z} \\ (\alpha, \beta) \xrightarrow{\qquad} (\alpha \|_c \beta) $$

characterized by the following two properties:

$$ (-\alpha_i \|_c \beta) = b_i, \quad \text{for all } i \in [n] \text{ and } \beta = \sum b_i \alpha_i \in \Phi_{\ge -1}, \qquad (2) $$

$$ (\alpha \|_c \beta) = (\tau_c \alpha \|_c \tau_c \beta), \quad \text{for all } \alpha, \beta \in \Phi_{\ge -1}. \qquad (3) $$

**Remark 2.9** *This definition is motivated by the classical compatibility degree defined by S. Fomin and A. Zelevinsky in [FZ03b, Sec. 3.1]. Namely, if c is a bipartite Coxeter element, then the c-compatibility degree ($\cdot \|_c \cdot$) coincides with the compatibility degree ($\cdot \| \cdot$) of [FZ03b, Sec. 3.1] except that ($\alpha \|_c \alpha$) = -1 while ($\alpha \| \alpha$) = 0 for any $\alpha \in \Phi_{\ge -1}$. Throughout this paper, we ignore this difference: we still call classical compatibility degree, and denote by ($\cdot \| \cdot$), the c-compatibility degree for a bipartite Coxeter element c.*

**On positions in the word $Q_c$.** We recall now the notion of root functions associated to c-clusters in $Q_c$, and use them in order to define a c-compatibility degree on the set of positions in $Q_c$. This description relies only on linear algebra and is one of the main contributions of this paper. The root function was defined by C. Ceballos, J.-P. Labbé, and C. Stump in [CLS13, Def. 3.2] and was extensively used by V. Pilaud and C. Stump in the construction of Coxeter brick polytopes [PS11].

**Definition 2.10 ([CLS13)]** *The root function $r(I, \cdot) : [m] \to \Phi$ associated to a c-cluster $I \subseteq [m]$ in $Q_c$ is defined by $r(I, j) := \sigma_{[j-1]\setminus I}^c(\alpha_{q_j})$, where $\sigma_X^c$ denotes the product of the reflections $q_x \in Q_c$ for $x \in X$ in this order. The root configuration of $I$ is the multiset $R(I) := \{\{r(I, i) | i \in I\}\}$.*

As proved in [CLS13, Sec. 3.1], the root function $r(I, \cdot)$ encodes exchanges in the c-cluster $I$. Namely, any $i \in I$ can be exchanged with the unique $j \notin I$ such that $r(I, j) = \pm r(I, j)$ (see [CLS13, Lem. 3.3]), and the root function can be updated during this exchange (see [CLS13, Lem. 3.6]). It was moreover shown in [PS11, Sec. 6] that the root configuration $R(I)$ forms a basis for $\mathbb{R}^n$ for any given initial c-cluster $I$ in $Q_c$. It enables us to decompose any other root on this basis to get the following coefficients, which will play a central role in the remainder of the paper.

**Definition 2.11 (c-compatibility degree on positions in $Q_c$)** *Fix any initial c-cluster $I \subseteq [m]$ of $Q_c$. For any position $j \in [m]$, we decompose the root $r(I, j)$ on the basis $R(I)$ as follows:*

$$ r(I, j) = \sum_{i \in I} \rho_i(j)r(I, i). $$

For $i \in I$ and $j \in [m]$, we define the c-compatibility degree as the coefficient

$$ \{i\|_c j\} = \begin{cases} \rho_i(j) & \text{if } j > i, \\ -\rho_i(j) & \text{if } j \le i. \end{cases} $$

**Lemma 2.12** *The coefficients $\{i\|_c j\}$ are independent of the c-cluster $I \subseteq [m]$ of $Q_c$ containing $i$.*
### 3 Main results: Three descriptions of d-vectors

The following result states that the three notions of compatibility degrees above are essentially the same. The proof can be found in [CP13].

**Theorem 3.1** The three notions of compatibility degrees on the set of cluster variables, almost positive roots, and positions in the word $Q_c$ coincide under the bijections of Section 2.1. More precisely, for every pair of positions $i, j$ in the word $Q_c$ we have

$$d(\psi_c(i), \psi_c(j)) = (\chi_c(i) \|_c \chi_c(j)) = \{i \|_c j\}.$$

In particular, if $c$ is a bipartite Coxeter element, then these coefficients coincide with the classical compatibility degrees of S. Fomin and A. Zelevinsky [FZ03b, Sec. 3.1] (except for Remark 2.9).

The following three statements are the main results of this paper and are direct consequences of Theorem 3.1. The first statement describes the denominator vectors in terms of the compatibility degrees of [FZ03b, Sec. 3.1].

**Corollary 3.2** Let $B := \{\beta_1, \dots, \beta_n\} \subseteq \Phi_{\ge -1}$ be a (classical) cluster in the sense of S. Fomin and A. Zelevinsky [FZ03a, Thm. 1.9], and let $\beta \in \Phi_{\ge -1}$ be an almost positive root. Then the d-vector $\mathbf{d}(B, \beta)$ of the cluster variable $\phi(\beta)$ with respect to the initial cluster seed $\phi(B) = \{\phi(\beta_1), \dots, \phi(\beta_n)\}$ is given by

$$\mathbf{d}(B, \beta) = ((\beta_1 \| \beta), \dots, (\beta_n \| \beta)),$$

where $(\beta_i \| \beta)$ is the compatibility degree of $\beta$ with respect to $\beta_i$ as defined by S. Fomin and A. Zelevinsky [FZ03b, Sec. 3.1] (except for Remark 2.9).

The next statement extends this result to any Coxeter element $c$ of $W$.

**Corollary 3.3** Let $B := \{\beta_1, \dots, \beta_n\} \subseteq \Phi_{\ge -1}$ be a c-cluster in the sense of N. Reading [Rea07, Sec. 7], and let $\beta \in \Phi_{\ge -1}$ be an almost positive root. Then the d-vector $\mathbf{d}_c(B, \beta)$ of the cluster variable $\phi_c(\beta)$ with respect to the initial cluster seed $\phi_c(B) = \{\phi_c(\beta_1), \dots, \phi_c(\beta_n)\}$ is given by

$$\mathbf{d}_c(B, \beta) = ((\beta_1 \|_c \beta), \dots, (\beta_n \|_c \beta)),$$

where $(\beta_i \|_c \beta)$ is the c-compatibility degree of $\beta$ with respect to $\beta_i$ as defined in Definition 2.8.

Finally, the third statement describes the denominator vectors in terms of the coefficients $\{i \|_c j\}$ obtained from the word $Q_c$.

**Corollary 3.4** Let $I \subseteq [m]$ be a c-cluster and $j \in [m]$ be a position in $Q_c$. Then the d-vector $\mathbf{d}_c(I, j)$ of the cluster variable $\psi_c(j)$ with respect to the initial cluster seed $\psi_c(I) = \{\psi_c(i) | i \in I\}$ is given by

$$\mathbf{d}_c(I, j) = (\{i \|_c j\})_{i \in I}.$$

These corollaries lead to simple proofs of the following statement.

**Corollary 3.5** For cluster algebras of finite type, the d-vector of a cluster variable that is not in the initial seed is non-negative and not equal to zero.

This corollary was conjectured by S. Fomin and A. Zelevinsky for arbitrary cluster algebras [FZ07, Conj. 7.4]. In the case of cluster algebras of finite type, this conjecture also follows from [CCS06, Thm. 4.4 & Rem. 4.5] and from [BMR07, Thm. 2.2], where the authors show that the d-vectors can be computed as the dimension vectors of certain indecomposable modules.
# 4 Geometric interpretations in types A, B, C and D

In this section, we present geometric interpretations for the classical types A, B, C, and D of the objects discussed in this paper: cluster variables, clusters, mutations, compatibility degrees, and *d*-vectors. These interpretations are classical in types A, B and C when the initial cluster seed corresponds to a bipartite Coxeter element, and can already be found in [FZ03b, Sec. 3.5] and [FZ03a, Sec. 12]. In contrast, our interpretation in type D slightly differs from that of S. Fomin and A. Zelevinsky since we prefer to use pseudotriangulations (we motivate this choice in Remark 4.1). Moreover, these interpretations are extended here to any initial cluster seed, acyclic or not.

We can associate to each classical finite type a geometric configuration, so that there is a correspondence between:

(i) cluster variables and *diagonals* (or centrally symmetric pairs of diagonals) in the geometric picture;

(ii) clusters and *geometric clusters*: triangulations in type A, centrally symmetric triangulations in types B and C, and centrally symmetric pseudotriangulations in type D (i.e. maximal crossing-free sets of centrally symmetric pairs of chords in the geometric picture);

(iii) cluster mutations and *geometric flips* (we can also express geometrically the exchange relations on cluster variables);

(iv) compatibility degrees and *crossing numbers* of (centrally symmetric pairs of) diagonals;

(v) *d*-vectors and *crossing vectors* of (centrally symmetric pairs of) diagonals.

Due to space limitations, we only detail the cases of types $A_n$ and $D_n$. A similar analysis in types $B_n$ and $C_n$, as well as explicit examples of computation for all classical finite types can be found in [CP13].

## 4.1 Type $A_n$

Consider the Coxeter group $A_n = \mathfrak{S}_{n+1}$, generated by the simple transpositions $\tau_i := (i \ i+1)$ for $i \in [n]$. The corresponding geometric picture is a convex regular $(n+3)$-gon. Cluster variables, clusters, exchange relations, compatibility degrees, and *d*-vectors in the cluster algebra $\mathcal{A}(A_n)$ can be interpreted geometrically as follows:

(i) Cluster variables correspond to (*internal*) *diagonals* of the $(n+3)$-gon. We denote by $\chi(\delta)$ the cluster variable corresponding to a diagonal $\delta$.

(ii) Clusters correspond to *triangulations* of the $(n+3)$-gon.

(iii) Cluster mutations correspond to *flips* between triangulations. See Figure 2.

<figure><img src="image_2.png" /><figcaption>Fig. 2: Flip in type A.</figcaption></figure>
Moreover, flipping diagonal pr to diagonal qs in a quadrilateral {$p, q, r, s$} results in the exchange relation

$$ \chi(pr) \cdot \chi(qs) = \chi(pq) \cdot \chi(rs) + \chi(ps) \cdot \chi(qr). $$

In this relation, we set $\chi(\delta) = 1$ when $\delta$ is a boundary edge of the $(n+3)$-gon.

(iv) Given any two diagonals $\theta, \delta$, the compatibility degree $d(\chi(\theta), \chi(\delta))$ between the corresponding cluster variables $\chi(\theta)$ and $\chi(\delta)$ is given by the crossing number $[\theta \parallel \delta]$ of the diagonals $\theta$ and $\delta$. By definition, $[\theta \parallel \delta]$ is equal to $-1$ if $\theta = \delta$, to $1$ if the diagonals $\theta \neq \delta$ cross, and to $0$ otherwise.

(v) Given any initial seed $T := \{\theta_1, \dots, \theta_n\}$ and any diagonal $\delta$, the $d$-vector of the cluster variable $\chi(\delta)$ with respect to the initial cluster seed $\chi(T)$ is the crossing vector $d(T, \delta) := ([\theta_1 \parallel \delta], \dots, [\theta_n \parallel \delta])$ of $\delta$ with respect to $T$.

## 4.2 Type $D_n$

Consider the Coxeter group $D_n$ of even signed permutations of $[n]$, generated by the simple transpositions $\tau_i := (i \ i + 1)$ for $i \in [n - 1]$ and by the operator $\tau_0$ which exchanges 1 and 2 and invert their signs. Note that $\tau_0$ and $\tau_1$ play symmetric roles in $D_n$ (they both commute with all the other simple generators except with $\tau_2$). This Coxeter group can be folded in type $C_{n-1}$, which provides a geometric interpretation of the cluster algebra $A(D_n)$ on a $2n$-gon with bicolored long diagonals [FZ03b, Sec. 3.5][FZ03a, Sec. 12.4]. In this section, we present a new interpretation of the cluster algebra $A(D_n)$ in terms of pseudotriangulations. The precise connection to the classical interpretation of type $D_n$ cluster algebras [FZ03b, Sec. 3.5][FZ03a, Sec. 12.4] is given in Remark 4.1.

We consider a regular convex $2n$-gon, together with a disk $D$ (placed at the center of the $2n$-gon), whose radius is small enough such that $D$ only intersects the long diagonals of the $2n$-gon. We denote by $D_n$ the resulting configuration, see Figure 3. The chords of $D_n$ are all the diagonals of the $2n$-gon, except the long ones, plus all the segments tangent to the disk $D$ and with one endpoint among the vertices of the $2n$-gon. Note that each vertex $p$ is adjacent to two of the latter chords; we denote by $p^L$ (resp. by $p^R$) the chord emanating from $p$ and tangent on the left (resp. right) to the disk $D$. Cluster variables, clusters, exchange relations, compatibility degrees, and $d$-vectors in the cluster algebras $A(D_n)$ can be interpreted geometrically as follows:

<figure><img src="image_3.png" /><figcaption>Fig. 3: The configuration $D_3$ with its 9 centrally symmetric pairs of chords (left). A centrally symmetric pseudotriangulation $T$ of $D_3$ (middle). The centrally symmetric pseudotriangulation of $D_3$ obtained from $T$ by flipping the chords $2^R$ and $2^L$.</figcaption></figure>
(i) Cluster variables correspond to centrally symmetric pairs of (internal) chords of the geometric configuration $D_n$. See Figure 3 (left). To simplify notations, we identify a chord $\delta$, its centrally symmetric copy $\bar{\delta}$, and the pair $\{\delta, \bar{\delta}\}$. We denote by $\chi(\delta) = \chi(\bar{\delta})$ the cluster variable corresponding to the pair of chords $\{\delta, \bar{\delta}\}$.

(ii) Clusters of $A(D_n)$ correspond to centrally symmetric pseudotriangulations of $D_n$ (i.e. maximal centrally symmetric crossing-free sets of chords of $D_n$). Each pseudotriangulation of $D_n$ contains exactly $2n$ chords, and partitions $\text{conv}(D_n) \setminus D$ into pseudotriangles (i.e. interiors of simple closed curves with three convex corners related by three concave chains). See Figure 3 (middle) and (right). We refer to [RSS08] for a complete survey on pseudotriangulations.

(iii) Cluster mutations correspond to flips of centrally symmetric pairs of chords between centrally symmetric pseudotriangulations of $D_n$. A flip in a pseudotriangulation $T$ replaces an internal chord $e$ by the unique other internal chord $f$ such that $(T \setminus e) \cup f$ is again a pseudotriangulation of $T$. To be more precise, deleting $e$ in $T$ merges the two pseudotriangles of $T$ incident to $e$ into a pseudoquadrangle $\square$ (i.e. the interior of a simple closed curve with four convex corners related by four concave chains), and adding $f$ splits the pseudoquadrangle $\square$ into two new pseudotriangles. The chords $e$ and $f$ are the two unique chords which lie both in the interior of $\square$ and on a geodesic between two opposite corners of $\square$. We refer again to [RSS08] for more details.

For example, the two pseudotriangulations of Figure 3 (middle) and (right) are related by a centrally symmetric pair of flips. We have represented different types of flips between centrally symmetric pseudotriangulations of the configuration $D_n$ in Figure 4.

As in types A, B, and C, the exchange relations between cluster variables during a cluster mutation can be understood in the geometric picture. More precisely, flipping $e$ to $f$ in the pseudoquadrangle $\square$ with convex corners $\{p, q, r, s\}$ (and simultaneously $\bar{e}$ to $\bar{f}$ in the centrally symmetric pseudoquadrangle $\bar{\square}$) results in the exchange relation

$$ \Pi(\square, p, r) \cdot \Pi(\square, q, s) = \Pi(\square, p, q) \cdot \Pi(\square, r, s) + \Pi(\square, p, s) \cdot \Pi(\square, q, r), $$

where

* $\Pi(\square, p, r)$ denotes the product of the cluster variables $\chi(\delta)$ corresponding to all chords $\delta$ of the geodesic from $p$ to $r$ in $\square$ — and similarly for $\Pi(\square, q, s)$,

* $\Pi(\square, p, q)$ denotes the product of the cluster variables $\chi(\delta)$ corresponding to all chords $\delta$ of the concave chain from $p$ to $q$ in $\square$ — and similarly for $\Pi(\square, q, r)$, $\Pi(\square, r, s)$, and $\Pi(\square, p, s)$.

For example, the four flips in Figure 4 result in the following relations:

$$ \chi(pr) \cdot \chi(qs) = \chi(pq) \cdot \chi(rs) + \chi(ps) \cdot \chi(qr), $$

$$ \chi(pr) \cdot \chi(q^R) = \chi(pq) \cdot \chi(r^R) + \chi(p^R) \cdot \chi(qr), $$

$$ \chi(pr) \cdot \chi(q\bar{p}) = \chi(pq) \cdot \chi(r\bar{p}) + \chi(\bar{p}^L) \cdot \chi(p^R) \cdot \chi(qr), $$

$$ \chi(\bar{p}^L) \cdot \chi(p^R) \cdot \chi(q^R) = \chi(pq) \cdot \chi(\bar{p}^R) + \chi(q\bar{p}) \cdot \chi(p^R). $$

Note that the last relation will always simplify by $\chi(p^R) = \chi(\bar{p}^R)$.
<figure><img src="image_4.png" /><figcaption>Fig. 4: Different types of flips in type D.</figcaption></figure>

(iv) Given any two centrally symmetric pairs of chords $\theta$, $\delta$, the compatibility degree $d(\chi(\theta), \chi(\delta))$ between the corresponding cluster variables $\chi(\theta)$ and $\chi(\delta)$ is given by the crossing number $[\theta \parallel \delta]$ of the pairs of chords $\theta$ and $\delta$. By definition, $[\theta \parallel \delta]$ is equal to $-1$ if $\theta = \delta$, and to the number of times that a representative diagonal of the pair $\delta$ crosses the chords of $\theta$ if $\theta \neq \delta$.

(v) Given any initial centrally symmetric seed pseudotriangulation $T := \{\theta_1, \dots, \theta_n\}$ and any centrally symmetric pair of chords $\delta$, the $d$-vector of the cluster variable $\chi(\delta)$ with respect to the initial cluster seed $\chi(T)$ is the crossing vector $\mathbf{d}(T, \delta) := ([\theta_1 \parallel \delta], \dots, [\theta_n \parallel \delta])$ of $\delta$ with respect to $T$.

**Remark 4.1** Our geometric interpretation of type D cluster algebras slightly differs from that of S. Fomin and A. Zelevinsky in [FZ03b, Sec. 3.5][FZ03a, Sec. 12.4]. Namely, to obtain their interpretation, we can just remove the disk in the configuration $\mathcal{D}_n$ and replace the centrally symmetric pairs of chords $\{p^\perp, \bar{p}^\perp\}$ and $\{p^\mathrm{R}, \bar{p}^\mathrm{R}\}$ by long diagonals $p\bar{p}$ colored in red and blue respectively. Long diagonals of the same color are then allowed to cross, while long diagonals of different colors cannot. Flips and exchange relations can then be worked out, with special rules for colored long diagonals, see [FZ03b, Sec. 3.5][FZ03a, Sec. 12.4]. Although our presentation is only slightly different from the classical presentation, we believe that it has certain advantages:

(i) Since there is no color code, it simplifies certain combinatorial and algebraic aspects (e.g. the notion of crossing, the $d$-vector, the cluster mutations, and the exchange relations are simpler to express).

(ii) It makes an additional link between cluster algebras and pseudotriangulations.
Acknowledgements

The first author would like to thank Sergei Fomin, Bernhard Keller, Andrei Zelevinsky, and specially Salvatore Stella for fruitful discussions at the MSRI workshop *Cluster Algebras in Combinatorics, Algebra and Geometry* in 2012. He also thanks the MSRI for providing a wonderful environment during the workshop. The main ideas used in this paper originated while we were trying to find general families of polytopal realizations of generalized associahedra given any initial cluster seed. We thank Paco Santos and Christian Stump for many discussions on these topics.

References

[BMR07] Aslak Bakke Buan, Robert J. Marsh, and Idun Reiten. Cluster-tilted algebras. *Trans. Amer. Math. Soc.*, 359(1):323–332 (electronic), 2007.

[CCS06] Philippe Caldero, Frédéric Chapoton, and Ralf Schiffler. Quivers with relations and cluster tilted algebras. *Algebr. Represent. Theory*, 9(4):359–376, 2006.

[CLS13] Cesar Ceballos, Jean-Philippe Labbé, and Christian Stump. Subword complexes, cluster complexes, and generalized multi-associahedra. *J. Algebraic Combin.*, 2013.

[CP13] Cesar Ceballos and Vincent Pilaud. Denominator vectors and compatibility degrees in cluster algebras of finite type. arXiv:1302.1052 (v1), 2013.

[FZ02] Sergey Fomin and Andrei Zelevinsky. Cluster algebras. I. Foundations. *J. Amer. Math. Soc.*, 15(2):497–529 (electronic), 2002.

[FZ03a] Sergey Fomin and Andrei Zelevinsky. Cluster algebras. II. Finite type classification. *Invent. Math.*, 154(1):63–121, 2003.

[FZ03b] Sergey Fomin and Andrei Zelevinsky. *Y*-systems and generalized associahedra. *Ann. of Math.* (2), 158(3):977–1018, 2003.

[FZ07] Sergey Fomin and Andrei Zelevinsky. Cluster algebras. IV. Coefficients. *Compos. Math.*, 143(1):112–164, 2007.

[Hum90] James E. Humphreys. *Reflection groups and Coxeter groups*, volume 29 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1990.

[Kel12] Bernhard Keller. Cluster algebras and derived categories. arXiv:1202.4161 (v4), 2012.

[KM04] Allen Knutson and Ezra Miller. Subword complexes in Coxeter groups. *Adv. Math.*, 184(1):161–176, 2004.

[PS11] Vincent Pilaud and Christian Stump. Brick polytopes of spherical subword complexes: A new approach to generalized associahedra. arXiv:1111.3349 (v2), 2011.

[Rea07] Nathan Reading. Clusters, Coxeter-sortable elements and noncrossing partitions. *Trans. Amer. Math. Soc.*, 359(12):5931–5958, 2007.

[RSS08] Günter Rote, Francisco Santos, and Ileana Streinu. Pseudo-triangulations — a survey. In *Surveys on discrete and computational geometry*, volume 453 of *Contemp. Math.*, pages 343–410. Amer. Math. Soc., Providence, RI, 2008.