The number of elements in the mutation class of a quiver of type D n
Aslak Bakke Buan
Department of Mathematical Sciences
Norwegian University of Science and Technology, Norway [email protected]
Hermund Andr´e Torkildsen
Department of Mathematical Sciences
Norwegian University of Science and Technology, Norway [email protected]
Submitted: Jan 20, 2009; Accepted: Apr 14, 2009; Published: Apr 22, 2009 Mathematics Subject Classification: 16G20, 16G70, 05E15, 20F55
Abstract
We show that the number of quivers in the mutation class of a quiver of Dynkin type Dn is given by P
d|nφ(n/d) 2dd
/(2n) for n ≥ 5. To obtain this formula, we give a correspondence between the quivers in the mutation class and certain rooted trees.
Introduction
Quiver mutation is an important ingredient in the definition of cluster algebras [FZ1]. It is an operation on quivers, which induces an equivalence relation on the set of quivers.
The mutation class M of a quiver Q consists of all quivers mutation equivalent to Q.
If Q is a Dynkin quiver, then M is finite. In [T] an excplicit formula for |M| is given for Dynkin type An. Here we give an explicit formula for the number of quivers in the mutation class of a quiver of Dynkin type Dn. The formula is given by
d(n) = P
d|nφ(n/d) 2dd
/(2n) if n≥5,
6 if n= 4,
where φ is the Euler function.
The proof for this formula consists of two parts. The first part shows that the mutation class of type Dn is in 1–1 correspondence with the triangulations (with tagged edges) of
a punctured n-gon, up to rotation and inversion of tags. This is a generalization of the method used in [T] to count the number of elements in the mutation class of quivers of Dynkin type An. Here we are strongly using the ideas in [FST] and [S].
In the second part we count the number of (equivalence classes of) triangulations of a punctured n-gon, by describing an explicit correspondence to a certain class of rooted trees. A tree in this class is constructed by taking a family of full binary trees T1, . . . , Ts
such that the total number of leaves is n, and then adding a node S and an edge from this node to the root of Ti for eachi, such that S becomes a root (Figure 21 displays all such trees for n= 5).
When these rooted trees are considered up to rotation at the root, they are in 1–
1 correspondence with the above mentioned equivalence classes of triangulations of the puncturedn-gon. To count these rooted trees we use a simple adaption of a known formula found in [I] and [St, exercise 7.112 b].
We also point out a mutation operation on these rooted trees, corresponding to the other mutation operations involved (on triangulations and on quivers).
Our formula and the bijection to triangulations of the puncturedn-gon were presented at the ICRA in Torun, August 2007 [T2].
After completing our work, we learnt about the paper [GLZ]. They also generalize the methods in [T] to prove the bijection from the mutation class of Dn to triangulations of the punctured n-gon. However, their method of counting triangulations is very different from ours. They use the classification of quivers of mutation type Dn, recently given in [V]. The authors of [GLZ] end up with a very different formula than ours. In particular, their formula is not explicit, and it seems they get a different output than we get, e.g. for n= 6.
We are grateful to Hugh Thomas for several useful discussions and for the idea of making use of binary trees as an alternative to rooted planar trees. We would also like to thank Dagfinn Vatne for useful discussions.
1 Quiver mutation
LetQbe a quiver with no multiple arrows, no loops and no oriented cycles of length two.
Mutation of Qat the vertex k gives a quiver Q′ obtained fromQ in the following way.
1. Add a vertex k∗.
2. If there is a path i → k → j, then if there is an arrow from j to i, remove this arrow. If there is no arrow fromj to i, add an arrow from ito j.
3. For any vertex ireplace all arrows from itok with arrows fromk∗ toi, and replace all arrows from k to i with arrows fromi to k∗.
4. Remove the vertex k.
It is easy to see that mutating Q twice at k gives Q. We say that two quivers Q and Q′ are mutation equivalent ifQ′ can be obtained fromQby a finite number of mutations.
The mutation class of Q consists of all quivers mutation equivalent to Q. Figure 1 gives all quivers in the mutation class of D4, up to isomorphism.
•4
•1 //•2 //•3
•4
•1 //•2 •3oo
•4
•1 •2oo //•3
•4
BB BB BB BB
•1 •2 33
OO
oo •3oo
•4
•1oo •OO2 //
•3
•4
•1 33•2oo •3
``BB
BB BB
BB
Figure 1: The mutation class of D4.
It is know from [FZ3] that the mutation class of a Dynkin quiver Q is finite. An explicit formula for the number of equivalence classes in the mutation class of any quiver of type An was given in [T].
The Catalan numberC(i) can be defined as the number of triangulations of ani+2-gon with i−1 diagonals. It is given by
C(i) = 1 i+ 1
2i i
.
The number of equivalence classes in the mutation class of any quiver of type An is then given by the formula [T]
a(n) =C(n+ 1)/(n+ 3) +C((n+ 1)/2)/2 + (2/3)C(n/3)
where the second term is omitted if (n+ 1)/2 is not an integer and the third term is omitted if n/3 is not an integer. This formula counts the triangulations of the disk with n diagonals [B].
2 Cluster-tilted algebras
The cluster category was defined independently in [BMRRT] for the general case and in [CCS] for the An case. Let Db(modH) be the bounded derived category of the finitely
generated modules over a finite dimensional hereditary algebra H over a field K. In [BMRRT] the cluster category was defined as the orbit category C =Db(modH)/τ−1[1], where τ is the Auslander-Reiten translation and [1] the suspension functor. The cluster- tilted algebras are the algebras of the form Γ = EndC(T)op, where T is a cluster-tilting object in C (see [BMR1]). In this paper we will mostly consider the case where the underlying graph of the quiver ofH is of Dynkin type D.
If Γ = EndC(T)op for a cluster-tilting object T inC, andC is the cluster category of a path algebra of type Dn, then we say that Γ is of type Dn.
Let Q be a quiver of a cluster-tilted algebra Γ. From [BMR2] it is known that if Q′ is obtained from Qby a finite number of mutations, then there is a cluster-tilted algebra Γ′ with quiver Q′. Moreover, Γ is of finite representation type if and only if Γ′ is of finite representation type [BMR1]. We also have that Γ is of type Dn if and only if Γ′ is of type Dn. It is well known that we can obtain all orientations of a Dynkin quiver by reflections, and hence all orientations of a Dynkin quiver are mutation equivalent.
From [BMR3, BIRS] we know that a cluster-tilted algebra is up to isomorphism uniquely determined by its quiver (see also [CCS2]).
It follows from this that the number of non-isomorphic cluster-tilted algebras of type Dn is equal to the number of equivalence classes in the mutation class of any quiver with underlying graph Dn.
3 Category of diagonals of a regular n + 3-gon
In [CCS] Caldero, Chapoton and Schiffler considered regular polygons with n+ 3 vertices and triangulations of such polygons. A diagonal is a straight line between two non- adjacent vertices on the border of the polygon, and a triangulation is a maximal set of diagonals which do not cross. A triangulation of an (n + 3)-gon consists of exactly n diagonals. In [CCS] the category of diagonals of such polygons was defined, and it was shown to be equivalent to the cluster category, as defined in Section 2, in the An case.
It was also shown that a cluster-tilting object in the cluster category C corresponds to a triangulation of the regular (n+ 3)-gon in the Ancase. In [T] it was shown that there is a bijection between isomorphism classes of cluster-tilted algebras of typeAn(or equivalently isomorphism classes of quivers in the mutation class of any quiver with underlying graph An) and triangulations of the disk with n diagonals (i.e. triangulations of the regular (n+ 3)-gon up to rotation).
For any triangulation of the regular (n+ 3)-gon we can define a quiver withn vertices in the following way. The vertices are the midpoints of the diagonals. There is an arrow between i and j if the corresponding diagonals bound a common triangle. The orientation isi→j if the diagonal corresponding to j can be obtained from the diagonal corresponding toiby rotating anticlockwise about their common vertex. It is also known from [CCS] that all quivers obtained in this way are quivers of cluster-tilted algebras of type An. This means that we can define a function γn from the mutation class of An to the set of all triangulations of the regular (n+ 3)-gon. There is an induced function eγn
from the mutation class ofAnto the set of all triangulations of the disk with ndiagonals.
It was shown in [T] that eγn is a bijection.
0 1
0 1
0 1 0 1 0 100001111
00 00 00 00 00 00 00 00 00 00
11 11 11 11 11 11 11 11 11 11
0000000 0000000 0000000 0000000 0000000 0000000 0000000
1111111 1111111 1111111 1111111 1111111 1111111 1111111
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000
1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111
00000000 00000000 0000 11111111 11111111 1111
Figure 2: A triangulation ∆ of the regular 8-gon and the corresponding quiver γ5(∆) of typeA5.
4 Category of diagonals of a punctured regular n -gon
In this paper we will consider theDncase and we will first recall some results and notions from [S] and [FST].
LetPn be a regular polygon withn vertices and one puncture in the center. Diagonals (or edges) will be homotopy classes of paths between two vertices on the border of the polygon. We follow the definitions from [S].
Let δa,b be an oriented path between two vertices a 6= b on the border of Pn in counterclockwise direction, such that δa,b does not run through the same point twice.
Also letδa,a be the path that runs froma toa, i.e. around the polygon exactly one time.
We define |δa,b| to be the number of vertices on the path δa,b, including a and b.
An edge is a triple (a, α, b) whereaandbare vertices on the border of the polygon and α is an oriented path froma tob lying in the interior ofPn and that is homotopic toδa,b. Furthermore, the path should not cross itself and |δa,b| ≥ 3. Two edges are equivalent if they start in the same vertex, end in the same vertex and are homotopic.
Let E be the set of equivalence classes of edges, and denote by Ma,b the equivalence class of edges in E going from a tob. In [S] the set of tagged edges is defined as follows.
{Ma,bǫ |Ma,b ∈E, ǫ∈ {−1,1} with ǫ= 1 ifa6=b}
From now on tagged edges will be called diagonals. Diagonals starting and ending in the same vertex a will be represented as lines between the puncture and the vertex a.
Diagonals with ǫ =−1 will be drawn with a tag on it. In some cases we will draw them as loops.
The crossing number e(Ma,bǫ , Nc,dǫ′ ) is the minimal number of intersection of represen- tations ofMa,bǫ and Nc,dǫ′ in the interior of the punctured polygon. Whena =b and c=d, we let the crossing number be 1 ifa 6=cand ǫ6=ǫ′ and 0 otherwise. If e(Ma,bǫ , Nc,dǫ′ ) = 0, we say that Ma,bǫ and Nc,dǫ′ do not cross.
Now we can define a triangulation of the punctured n-gon, which is a maximal set of non-crossing diagonals. Any such set will have n elements [S]. See some examples of triangulations of the punctures 6-gon in Figure 3.
Figure 3: Examples of triangulations of the punctured 6-gon.
[S] defines a category which is equivalent to the cluster catecory in the Dn case in the following way. The objects are direct sums of diagonals (tagged edges), and the morphism space from α to β is spanned by sequences of elementary moves modulo the mesh-relations. The equivalence between this category C and the cluster category in the Dn case was proved in [S]. Furthermore we have the following important results:
• dim Ext1C(α, β) is equal to the crossing number of α and β.
• A cluster-tilting object corresponds to a triangulation.
• The Auslander-Reiten translation of a diagonal from a to b is given by clockwise rotation of the diagonal if a 6=b. If a= b the AR-translation is given by clockwise rotation and inverting the tag.
Let Tn be the set of all triangulations ofPn, and let ∆ be an element in Tn. We can assign to ∆ a quiver in the following way (see [FST]). Just as in theAn case, the vertices are the midpoints of the diagonals. There is an arrow betweeniandj if the corresponding diagonals bound a common triangle. The orientation isi→j if the diagonal corresponding toj can be obtained from the diagonal corresponding toiby rotating anticlockwise about their common vertex. In the case when there are two diagonals α and α′ between the puncture and the same vertex on the border, both adjacent to a diagonal β and a border edge δ, we consider the triangle with edges α, β and δ separately from the triangle with edges α′, β and δ, when thinking of α andα′ as loops around the puncture. If we end up with an oriented cycle of length 2, delete both arrows in the cycle. See some examples in Figure 4.
Figure 4: Some examples of triangulations and corresponding quiver.
Let Mn be the mutation class of Dn, i.e. all quivers obtained by repeated mutations from Dn, up to isomorphisms of quivers. We can define a function ǫn :Tn→ Mn, where we setǫn(∆) =Q∆ for any triangulation inTn. It is known thatQ∆is a quiver of Dynkin typeDn and that all quiver of type D can be obtained this way, hence ǫ is surjective.
We can define a mutation operation on a triangulation. If α is a diagonal in a trian- gulation, then mutation atα is defined as replacingα with another diagonal such that we obtain a new triangulation. This can be done in one and only one way. It is known that mutation of quivers commutes with mutation of triangulations under ǫ (see [S, FST]).
5 Bijection between the mutation class of a quiver of type D
nand triangulations up to rotation and inverting tags
Here we adapt the methods and ideas of [T] to obtain a bijection between the mutation class of a quiver of type Dn and the set of triangulations of a punctured n-gon up to rotations and inversion of tags. See also [GLZ].
We say that a diagonal from a to b is close to the border if |δ(a, b)| = 3. For a quiver Q∆ corresponding to a triangulation ∆, we will always denote by vα the vertex in Q∆ corresponding to the diagonal α. From now on we let n ≥ 5. Let us denote by Sn the triangulation of Pn shown in Figure 5. Note that this triangulation and the triangulationSn with all tags inverted are the only triangulations that correspond to the quiver consisting of the oriented cycle of length n, Qn.
Lemma 5.1 Let ∆ be a triangulation of Pn, with ∆6=Sn. Then there exists a diagonal in ∆which is close to the border.
Proof: Let ∆ be a triangulation of Pn. If ∆ is not Sn, then there is at least one diagonal α which connects two vertices on the border. See Figure 6.
Consider the non-punctured surface B determined by this diagonal. If α is not close to the border, there exist a diagonal that divides the surface B into two smaller surfaces.
By induction, there exists a diagonal close to the border.
00 11
000000 000000 000000 000000 000000 000000
111111 111111 111111 111111 111111 111111
00000000 00000000 00000000 00000000 00000000 00000000
11111111 11111111 11111111 11111111 11111111 11111111 000000 000000 000000 000000 000000 000000
111111 111111 111111 111111 111111
111111000000000000000000000000000000000000000000 1111111 1111111 1111111 1111111 1111111 1111111
00000000 00000000 00000000 00000000 00000000 00000000
11111111 11111111 11111111 11111111 11111111 11111111
000000 000000 000000 000000 000000 000000
111111 111111 111111 111111 111111 111111
000000 000000 000000 000000 000000 000000
111111 111111 111111 111111 111111 111111
Figure 5: Triangulation Rn corresponding to the quiver consisting of the oriented cycle of length n.
00 11
α Α
Β
Figure 6: The diagonal α divides the polygon into a punctured and a non-punctured surface.
Lemma 5.2 If a diagonal α of a triangulation ∆ is close to the border, then the corre- sponding vertex vα in ǫn(∆) =Q∆ is either a source, a sink or lies on an oriented cycle of length 3.
Proof: Suppose α is a diagonal close to the border. We have to consider the eight cases shown in Figure 7. In the first picture in Figure 7, α corresponds to a source since no other vertex except vβ can be adjacent to vα, or else the corresponding diagonal would cross β. In the second picture α corresponds to a sink. In picture three, four, five and six, there are arrows betweenvα,vβ and vβ′, and in the last two pictures, there are arrows between vα, vβ and vγ, so vα lies on an oriented cycle of length 3.
Let ∆ be a triangulation of Pn and letα be a diagonal close to the border. We define a triangulation ∆/α ofPn obtained from ∆ by lettingα be a border edge and leaving all the other diagonals unchanged. We write ∆/αfor the new triangulation obtained and we say that we factor out α. See Figure 8. Note that this operation is well-defined for each case in Figure 7.
α β
α β
α β
β
α β
β
α β
β
α β
β
α
β β
γ
α
γ β
β
Figure 7: See the proof of Lemma 5.2
α
Figure 8: Factoring out a diagonal close to the border.
Lemma 5.3 Let ∆ be a triangulation of Pn, with ∆ 6= Sn and let ǫn(∆) = Q∆ be the corresponding quiver. If α is a diagonal close to the border in ∆, then the quiver Q∆/vα
obtained from Q∆ by factoring out the vertex vα is connected and of type Dn−1. Further- more, we have that ǫn−1(∆/α) =Q∆/vα, when α is close to the border.
Proof: By Lemma 5.2 we have that Q∆/vα is connected. It is also straightforward to verify that ǫn−1(∆/α) = Q∆/vα for each case, and hence Q∆/vα is of type Dn−1 since
∆/αis a triangulation of Pn−1.
Now we describe what happens when we factor out a vertex corresponding to a diagonal not close to the border. We need to consider two cases. We first deal with the case when α is a diagonal not going between the puncture and the border.
Lemma 5.4 Let ∆ be a triangulation and ǫn(∆) = Q∆. If we factor out a vertex in Q∆ corresponding to a diagonal that is not close to the border and that is not a diagonal between the puncture and the border, then the resulting quiver is disconnected.
Proof: Let α be a diagonal not close to the border and not between the puncture and the border. Then the diagonal divides Pn into two surfaces A and B. See Figure 6. Let β be a diagonal in A and β′ a diagonal in B. If β and β′ would determine a common triangle, the third diagonal would crossα, hence there is no arrow between the subquiver determined by A and the subquiver determined by B, except those passing through vα. It follows that factoring out vα disconnects the quiver.
Let ∆ be a triangulation of Pn and let α be a diagonal between the puncture and a vertex bi on the border of the polygon. We want to understand the effect of factoring out vα (see Figure 9). InPn, create a new vertex cbetween bi−1 and bi and a new vertex d between bi and bi+1, such that we obtain a (n + 2)-polygon. Let all diagonals that started in bi now start in d and all diagonals ending in bi now end in c. Remove the diagonal α and identify the puncture with the vertex bi. If there were two diagonals between the puncture andbi, remove both and draw a diagonal fromctod. Leave all the other diagonals unchanged. We will see that this is a triangulation of the non-punctured (n+ 2)-polygon in the next lemma.
b
b b
b
i i−2 i+1
i−1
b
b
bi
i+1
i−1
c
d bi−2
α
b
b
bi
i+1
i−1
c
d bi−2
α
i−1
b
b b
b
i i−2 i+1
Figure 9: Factoring out a diagonal from the puncture to the border.
Recall thatγnis the function from the set of all triangulations of the regular (n+3)-gon to the mutation class ofAn, defined in Section 2. We have the following.
Lemma 5.5 Let ∆ be a triangulation and ǫn(∆) = Q∆. If α is a diagonal between the puncture and the border, then the quiver Q∆/vα obtained from Q∆ by factoring out vα is connected and of type An−1. Furthermore, we have that γn+2(∆/α) =Q∆/vα when α is a diagonal between the puncture and a vertex on the border.
Proof: It is clear that ∆/α has n−1 diagonals and that no diagonals cross. This means that the new triangulation is a triangulation of the (n+ 2) polygon without a puncture.
We want to show that all triangles are preserved by factoring out a diagonal as described above and hence we will have that γn+2(∆/α) =Q∆/vα, and thatQ∆/vα is of type An−1. First suppose that there is only one diagonal from the puncture to the vertex bi (see Figure 9). Then it is easy to see that all triangles are preserved. Next, suppose there are two diagonals α and β from the puncture to bi. In this case we add a new diagonal β′ between bi−1 and bi+1 and remove α and β. Then the diagonals bounding a common triangle withβ before factoring outαwill bound a common triangle withβ′ after factoring out α.
Summarizing, we get the following Proposition.
Proposition 5.6 Let ∆ be a triangulation and let ǫn(∆) = Q∆ be the corresponding quiver. Thenǫn−1(∆/α) =Q∆/vα is of typeDn−1if and only if the corresponding diagonal α is close to the border.
Proof: From Lemma 5.3, we have that if α is close to the border, then Q∆/vα is of type Dn−1. If α is not close to the border, we have by Lemma 5.4 and Lemma 5.5 thatQ∆/vα
is either disconnected or of type An−1.
If ∆ is a triangulation ofPn, we want to add a diagonalαand a vertex on the polygon such that α is a diagonal close to the border and such that ∆∪α is a triangulation of Pn+1. Consider any border edge m on Pn. We consider the eight different cases for the triangle containing m, as shown in Figure 10. We can define the extension at m for each case. See Figure 7 for the corresponding extensions.
β m
m
β m
β
β m
β β
m β
β
m
β β
m
β β
m β β
Figure 10: Extension atm.
For a given diagonal β, there are at most three ways to extend the polygon with a
diagonal α such that α is adjacent to β. These extensions give non-isomorphic quivers, except when the triangulation is Sn.
Combining Lemma 5.1 and Lemma 5.3, we get that for a quiver Q which is not Qn, there always exist a vertex v such that Q′ obtained from Q by factoring out v is connected and a quiver of a cluster-tilted algebra of type D. Furthermore, such a vertex must correspond to a diagonal close to the border in any triangulation ∆ such that ǫn(∆) = Q∆.
For a triangulation ∆ of Pn, let us denote by ∆(i) the triangulation obtained from
∆ by rotating i steps in the clockwise direction. Also denote by ∆−1 the triangulation obtained from ∆ by inverting all tags. We define an equivalence relation on Tn where we let ∆ ∼ ∆(i) for all i and ∆−1 ∼ ∆. We define a new function eǫn : (Tn/∼) → Mn
induced from ǫn. This is well-defined, and since ǫn is a surjection, we also have thateǫn is a surjection. We actually have the following.
Theorem 5.7 The functioneǫn : (Tn/∼)→ Mn is bijective for all n≥5.
Proof: We already know that eǫn is surjective.
Suppose eǫn(∆) =eǫn(∆′). We want to show that ∆ = ∆′ in (Tn/∼) using induction.
It is straightforward to check that eǫ5 : (T5/∼) → M5 is injective. Suppose eǫn−1 : (Tn−1/∼)→ Mn−1 is injective. Letα be a diagonal close to the border in ∆, with image vαinQ, whereQis a representative foreǫn(∆). Then the diagonalα′in ∆′ corresponding to vα inQis also close to the border by Proposition 5.6. We haveeǫn−1(∆/α) =eǫn−1(∆′/α′) = Q/vα, and hence by hypothesis, ∆/α= ∆′/α′ in (Tn/∼).
We can obtain ∆ and ∆′ from ∆/α= ∆′/α′ by extending the polygon at some border edge. Fix a diagonal β in ∆ such that vα and vβ are adjacent. This can be done since Q is connected. Let β′ be the diagonal in ∆′ corresponding to vβ. By the above there are at most three ways to extend ∆/α such that the new diagonal is adjacent to β. It is clear that these extensions will be mapped by ǫen to non-isomorphic quivers. Also there are at most three ways to extend ∆′/α′ such that the new diagonal is adjacent to β′, and all these extensions are mapped to non-isomorphic quivers, thus ∆ = ∆′ in (Tn/∼).
Corollary 5.8 The number d(n) of elements in the mutation class of any quiver of type Dn is equal to the number of triangulations of the punctured regular n polygon up to rotations and inverting all tags.
6 Equivalences on the cluster category in the D
ncase
Since the Auslander-Reiten translation τ is an equivalence, it is clear that if T is a cluster-tilting object in C, then the cluster-tilted algebras EndC(T)op and EndC(τ T)op are isomorphic. We know that τ corresponds to rotation of diagonals. In [T] it was proven that if T and T′ are cluster-tilting objects in C, then the cluster-tilted algebras EndC(T)op and EndC(T′)op are isomorphic if and only if T′ =τiT for ani∈ Z in the An
case.
Let α be a diagonal (indecomposable object in C). If α is a diagonal between the puncture and the border, let α−1 denote the diagonal α with inverted tag. We define
µα=
(α−1 if α is a diagonal between the puncture and the border, α otherwise.
If α is not a diagonal between the puncture and the border, then clearly τnα = α.
Now, let αbe a diagonal between the puncture and the border. Suppose n is even. Then it is clear from combinatorial reasons thatτnα =α and that τiα6=α−1 for any i. Ifn is odd, then τnα = α−1 and hence τn = µ. See Figure 11 for an example of an AR-quiver in the D5 case.
Theorem 6.1 LetT andT′ be cluster-tilting objects inC. Then the cluster-tilted algebras EndC(T)op and EndC(T′)op are isomorphic if and only if T′ =µiτjT i, j ∈Z.
Proof: Let ∆ be a triangulation corresponding toT and ∆′ a triangulation corresponding to T′. If T′ 6≃τiT for any i, then ∆′ is not obtained from ∆ by a rotation. If T′ 6≃µT, then ∆ 6= ∆−1. It then follows from Theorem 5.7 that EndC(T)op is not isomorphic to EndC(T′)op.
It is clear that µis an equivalence on the cluster category, since µ2 = id.
0000 1111 0000 1111
0000 1111
0000 1111
0000 1111 0000 1111
0000 1111
0000 1111
0000 1111
0000 1111 0000 1111
0000 1111
0000 1111
0000 1111
0000 1111 0000 1111
0000 1111
0000 1111
0000 1111
0000 1111 0000 1111
0000 1111
0000 1111
0000 1111 0000
1111
Figure 11: AR quiver for the cluster category in the D5 case.
7 The number of triangulations of punctured poly- gons
In this section we want to find an explicit formula for the number of triangulations of punctured polygons up to rotation and tags. Let Bn be the set of equivalence classes of trees such that
• any full subtree not including the root is binary and every inner node has either two or no children,
• there are exactly n leaves and
• two trees are equivalent if one can be obtained from the other by rotating at the root.
As before, letT5/∼be the set of triangulations of the puncturedn-gon, where rotations and inverting tags gives equivalent triangulations. In this section we will draw certain tagged edges as loops. If there are two diagonals between the puncture and the same vertex, we will draw one diagonal as a loop. See Figure 12.
0
1 01
0000000 1111111
Figure 12: Drawing tagged edges as loops
We define a function σ : Tn/∼→ Bn by assigning to a triangulation a tree. Let ∆ be a triangulation. We let σ(∆) be the tree obtained in the following way. Draw an edge between two triangles E and E′ if they are adjacent and their common diagonal is not a diagonal between the puncture and the border. Note that a loop in this case is not an edge between the puncture and the border. When a triangleE contains one or two border edges, also draw one or two edges from the vertex to the outside of the polygon, crossing the border edges. These will be the leaf edges. Then identify the vertices adjacent to the puncture to be the root in the tree. See Figure 13 for some examples.
It is clear that σ is a well-defined function. Our aim is to show that σ is a bijection.
Let the tree Rn be the tree consisting of exactly n edges from the root, as shown in Figure 14. Note that this is the unique tree which is the image of the triangulation Sn.
Now we want to define a function λ : Bn → Tn/∼ and we will see that this is the inverse of σ.
Given a treeT with n leaves, we will here describeλ(T). We know that an inner edge of a tree (an edge not going to a leaf) corresponds to a diagonalα not going between the puncture and the border.
Suppose α is an inner edge of T. Let T′ be the full subtree of T with root ending in α. If T′ has n leaves, we draw a segment of a polygon consisting of n border edges. See Figure 15. Suppose the subtree to the left of the root in T′ has r ≥ 2 leaves. Then we draw a diagonal β fromv1 tovr+1. If r+ 16=n we draw a diagonal δ fromvr+1 tovn+1. We can continue like this with β and δ until we made a complete triangulation of the segment of the polygon, by induction.
Now, supposeT haskedges from the root, namelyt1, t2, ..., tk. Suppose the full subtree with root ending in ti has di leaves. Then P
idi =n. Draw a punctured polygon with n
00 11
Figure 13: Triangulation and corresponding tree.
000000 000000 000000 000
111111 111111 111111 111
00 00 00 0
11 11 11 1
000000 000000 000000 000
111111 111111 111111 111 00 11
Figure 14: The tree Rn consisting of exactlyn edges from the root.
v
v
v
v
v
1
2
r+1
n n+1
α
β δ
Figure 15
border edges and draw kdiagonals between the puncture and vertices on the border such that each segment has di border edges in anticlockwise direction.
For each segment defined by ti, apply the procedure described above to obtain a triangulation of the segment. See Figure 16.
00 11
00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000
11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111
00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000
11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111
Figure 16
It is clear from the construction that λ is the inverse of σ, so we have the following.
Theorem 7.1 σ :Tn → Bn is a bijection.
The number of rooted planar trees with n+ 1 nodes where rotating at the root gives equivalent trees, is given by the formula
X
d|n
φ(n/d) 2d
d
/(2n)
n d(n) 3 4 4 6 5 26 6 80 7 246
n d(n) 8 810 9 2704 10 9252 11 32066 12 112720 Table 1: Some values of d(n).
where φ is the Euler function (see [I] and the references given there and exercise 7.112 b in [St]).
The number of planar trees with n+ 1 nodes and the number of planar binary trees with n+ 1 leaves are both given by the n’th Catalan number. It follows that the number of elements in Bn is given by the above formula.
Corollary 7.2 The number d(n) of elements in the mutation class of any quiver of type Dn is given by:
d(n) = P
d|nφ(n/d) 2dd
/(2n) if n ≥5,
6 if n = 4,
where φ is the Euler function.
We proved this for n ≥5 and for n = 4 the number is 6. See Figure 1 for all quivers in the mutation class of D4. See Table 1 for some values of d(n).
8 Mutation of trees
We want to define a mutation operation on the elements in B, and we want this to commute with mutation of triangulations. Mutating a triangulation at a given diagonal is defined as removing this diagonal and replacing it with another one to obtain a new triangulation. This can be done in one and only one way.
Let ∆ be a triangulation in Tn and let σ(∆) =T be the corresponding tree. An inner edge of T corresponds to a diagonal in ∆ not going from the puncture to the border, since the edges crosses these diagonals when we construct T from ∆. However, when we construct T from ∆, no edges in T crosses a diagonal between the puncture and the border. To define mutation onT corresponding to mutating at a diagonalα between the puncture and the border, we instead define mutation at two adjacent edges from the root in T, namely the two edges from the root in T separated by α.
1. Letv1be an edge from the root inT. The mutation ofT atv1 is a new tree obtained in the following way. Remove the edge v1. Identify the root of the full subtree of T ending in v1 with the root in T. See the first picture in Figure 17.
2. Let x and y be two adjacent edges from the root of T. The mutation of T at x and y is a new tree obtained in the following way. Disconnect the full subtree of T containing x and y. Add an edge v1 from the root and connect the subtree to the end of v1. See the second picture in Figure 17.
3. Let v be an inner edge not going from the root or to a leaf. The mutation of T at v is a new tree obtained in the following way. Suppose v is an edge from the nodes rtot, going down in the tree. Letxbe the other edge starting inr, and lety and z be the two edges starting int. See the third and fourth picture in Figure 17.
Suppose x goes to the left from r and v goes to the right, as in the third picture.
Disconnect the full subtree with t as a root. Remove the edge v and identifyr with t. Disconnect the full subtree T′ containing xand y. Create a new vertexv′ starting inr and identify the root of T′ with the node ending in v′. See the third picture in Figure 17. If x goes to the right from r and v goes to the left, we define mutation atv in a similar way as shown in the fourth picture.
We claim that mutation of a tree as defined above commutes with mutation of trian- gulations. We leave the details of the proof to the reader.
Proposition 8.1 Mutation of trees commutes with mutations of triangulations and quiv- ers.
Sketch of proof:
For mutation of type 3, we mutate at a diagonal not going between the puncture and the border, so we are in the situation shown in Figure 18. We see that mutation of trees commutes with mutation of triangulations.
For mutation of type 1 and 2 we have to consider the three cases shown in Figure 19.
In these cases we also see that mutation as defined above commutes with mutation of triangulations.
Figure 20 and 21 shows the mutations of type 1 and 2 for both triangulations and trees in theD5 case. Note that mutation of type 2 adds an edge from the root, or equivalently replaces a diagonal not between the puncture and the border with a diagonal between the puncture and the border. Mutation of type 1 is the opposite operation. This defines a tree of mutations as shown in Figure 20 and 21, where going down in the tree corresponds to mutatation of type 1 and going up in the tree corresponds to mutation of type 2. If we drew arrows for mutations of type 3, the arrows would go to trees (or triangulations) in the same level in the tree of mutations. It is easy to see that this holds in general for any n.
v
mx y v
2v
v
x y
2
1 m
v
v v
v
x y
2
1 m
v
mx y v
2x v
y z
x y z
v’ z
x y
v x
y z
y z x
z v’
y
x
Figure 17: Mutation of a tree.
x
y v z
x
y v’
z
Figure 18: Mutation of triangulations and trees commute. See proof of Proposition 8.1.
00 00 11
11 0000
1111
00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000
11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000
1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111
0 00 00 00 0 00 00 00 0 00 00 00 00 00 00 00 0 00 00 00 0
1 11 11 11 1 11 11 11 1 11 11 11 11 11 11 11 1 11 11 11 1
000000 000000 000000 000000 111111 111111 111111 111111 0000 0000 0000 00
1111 1111 1111 11
000000 000000 000
111111 111111 111
000000 000000 000 000000 000
111111 111111 111 111111 111
0000 0000 0000 0000 00 00
1111 1111 1111 1111 11 11
00000 00000 11111 11111
00 00 00 0 00 00 00 0 00 00 00 00 00 00 00 0 00 00 00 0
11 11 11 1 11 11 11 1 11 11 11 11 11 11 11 1 11 11 11 1
0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000
1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111 1111111111111111
00 11
0000 1111
0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000
1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111 1111111
Figure 19: Mutation of triangulations and trees commutes. See proof of Proposition 8.1.
Figure 20: All triangulations of type D5.
Figure 21: All trees of type D5.
References
[B] Brown, W. G. Enumeration of triangulations of the disk, Proc. London Math. Soc., 14, 746-768 (1964).
[BIRS] Buan A., Iyama O., Reiten I., Smith D.Mutation of cluster-tilting objects and potentials, arXiv:0710.4335.
[BMRRT] Buan A., Marsh R., Reineke M., Reiten I., Todorov G. Tilting theory and cluster combinatorics, Advances in mathematics, 204 (2), 572-618 (2006).
[BMR1] Buan A., Marsh R., Reiten I.Cluster-tilted algebras, Trans. Amer. Math. Soc., 359, no.
1, 323–332 (2007).
[BMR2] Buan A., Marsh R., Reiten I.Cluster mutation via quiver representations, Commentarii Mathematici Helvetici, Volume 83 no.1, 143-177 (2008).
[BMR3] Buan A. B., Marsh R., Reiten I. Cluster-tilted algebras of finite representation type, Journal of Algebra, Volume 306, Issue 2, 412-431 (2006).
[BV] Buan A. B., Vatne D. F. Derived equivalence classification for cluster-tilted algebras of type An, Journal of Algebra, 319, 2723-2738 (2008).
[CCS] Caldero P., Chapoton F., Schiffler R. Quivers with relations arising from clusters (An case), Trans. Amer. Math. Soc. 358 , no. 3, 1347-1364 (2006).
[CCS2] Caldero P., Chapoton F., Schiffler R.Quivers with relations and cluster tilted algebras, Algebras and Representation Theory 9, no. 4, 359-376 (2006).
[FST] Fomin S., Shapiro M., Thurston D. Cluster algebras and triangulated surfaces. Part I:
Cluster complexes, Acta Math. 201, 83-146 (2008).
[FZ1] Fomin S., Zelevinsky A.Cluster algebras I: Foundations, J. Amer. Math. Soc. 15, 497-529 (2002).
[FZ2] Fomin S., Zelevinsky A.Y-systems and generalized associahedra, Annals of Mathematics 158, no. 3, 977-1018 (2003).
[FZ3] Fomin S., Zelevinsky A. Cluster algebras II: Finite type classification, Inventiones Math- ematicae 154, 63-121 (2003).
[GLZ] Ge W., Lv H., Zhang S.Cluster-tilted algebras of type Dn, arXiv:0812.0650v2 (2008).
[I] The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/ njas/sequences/.
[S] Schiffler R. A geometric model for cluster categories of type Dn, J. Alg. Comb. 27, no. 1, 1-21 (2008).
[St] Stanley R. P.Enumerative Combinatorics, volume 2, Cambridge studies in Advanced Math- ematics 62, Cambridge University Press (1999).
[T] Torkildsen H. A.Counting cluster-tilted algebras of type An, International Electronic Jour- nal of Algebra, no. 4, 149-158 (2008).
[T2] Torkildsen H. A.Counting cluster-tilted algebras of finite representation type, talk at ICRA, Torun (2007).
[V] Vatne D. F. The mutation class of Dn quivers, arXiv:0810.4789v1 (2008).
