The ADE affair, 3

Clusters, and the associated cluster algebras and cluster categories, form a hot topic in mathematics at the moment. Clusters are connected with topics such as Poisson geometry, integrable systems, representation theory and total positivity as well as combinatorial enumeration.

I learned a bit about clusters in two excellent talks at the Algebra, Combinatorics and Dynamics meeting in Belfast in August 2010, by David Jordan and Peter Jørgensen.

This is an exposition of the introductory part of the theory, not including most of the applications hinted at above, but describing a question to which the people I spoke to didn’t know the answer.

I should stress that I am not at all an expert on clusters. The fact that I don’t know something doesn’t mean that it isn’t known! Readers who want to know more are referred to the papers of Fomin and Zelevinsky, especially “Cluster algebras II” in Inventiones Math. 154 (2003), 53-121.

A recurrence

Consider the recurrence relation

xn+3 = (xn+1xn+2+1)/xn.

Because of the denominators, it might seem that we can’t expect this recurrence to produce integer sequences. Nevertheless, starting with 1,1,1, we obtain 1,1,1,2,3,7,11,26,41,97,153,362,571,…, which is sequence number A005246 in Neil Sloane’s On-Line Encyclopedia of Integer Sequences, where a number of occurrences of it are logged, in particular the fact that it gives the denominators of the continued fraction convergents to √3. Alternatively it gives integer solutions to


The terms satisfy the linear recurrence a(n) = 4a(n−2)−a(n−4).

We are going to see why this and similar recurrences produce integer sequences.

Quiver mutation

The next definition is not quite standard, but I will stick to it here. A quiver is a finite directed graph (with multiple edges allowed) with the properties

  • there are no loops;
  • there are no 2-cycles (i.e. all edges between two vertices point in the same direction).

About the last condition: we regard an edge (v,u) as the negative of an edge (u,v), so that two oppositely directed edges between u and v would cancel out. We will often have to add n edges (u,v) to a quiver. If u and v are unconnected, or there are already m edges from u to v, this is unproblematic; if there are m edges from v to u, the result is nm edges from u to v if n>m, or mn edges from v to u if m>n (or no edges at all if m=n).

The operation μu of mutation of a quiver Q at a vertex u consists of doing the following:

  • reverse the directions of all edges incident with u;
  • for any two vertices v and w, if there were k edges from v to u and l edges from u to w before mutation, then we add kl edges from v to w (with the convention outlined in the preceding paragraph).

Exercise: μu is an involution (that is, doing it a twice returns us to the starting quiver).

We will work with three running examples.

Example 1: Consider the quiver with two vertices 1 and 2, with a single edge from 1 to 2. Both the mutations μ1 and μ2 have the effect of reversing this edge.

Example 2: Consider the quiver consisting of a directed path from 1 to 3 on the vertex set {1,2,3}. Mutations at 1 and 3 each reverse a single edge, so that any orientation of the path can be obtained by a sequence of mutations.

Mutation at 2 is a bit more complicated. We reverse the edges (1,2) and (2,3); and, according to the second clause of the definition, we add the edge (1,3). Thus we have produced an oriented triangle (1,3,2).

If we now mutate this triangle at vertex 1, we reverse the edges (1,3) and (2,1); the added edge (2,3) cancels the existing edge (3,2), and we have the directed path (3,1,2).

So we can contain all three paths on the three vertices, each with all possible orientations of edges, together with the two orientations of the triangle.

It is not difficult to check that these 14 quivers are closed under mutation. It happens that 14 is the fifth Catalan number, and counts the number of dissections of a hexagon into triangles. This is no coincidence. It can be shown that the number of quivers obtained from an orientation of a path of length n is the (n+3)rd Catalan number.

Example 3: Take the transitive tournament on {1,2,3} with edges (1,2), (2,3) and (1,3): that is, the total order (1,2,3) on this set.

Mutation at 1 gives the total order (2,3,1), and mutation at 3 gives the total order (3,1,2). Mutation at 2, however, gives the oriented triangle (1,3,2) with the edge (1,3) doubled. If we now mutate this graph at 1 or 3, we reverse all the edges; then mutating at 2, we get the other three transitive tournaments.

The set of 12 quivers consisting of six transitive tournaments and six oriented triangles each with an edge doubled is closed under mutation.

Exercise: Show that any orientation of the edges of a tree can
be obtained from any other by a sequence of mutations.

Remark: Given a quiver Q, is the set of quivers which can be obtained from Q by mutation finite or infinite? I don’t know the answer to this question. In all the examples above, the set is finite. But starting from an oriented triangle where all edges have multiplicity at least 2 and one has multiplicity greater than 2, it is possible to obtain infinitely many quivers by mutation.

Clusters and cluster variables

A seed is an ordered pair (Q,(x1,…,xn)), where Q is a
quiver (with vertices numbered 1,…,n) and x1,…,xn are
variables which are algebraically independent over C (so that
the field C(x1,…,xn) of rational functions of these
variables is a pure transcendental extension of C with transcendence
degree n).

We extend the operation of mutation to act on seeds in the following odd-looking way:


where yi = xi for iu, and

yu = (∏xv+∏xw)/xu.

The two products are over edges (u,v) originating at u and edges (w,u) terminating at u respectively (multiple edges require the variables to be repeated as often as necessary), and empty products are taken to be 1.

We note two easy things and one non-trivial fact about this operation.

  • μu acting on seeds is an involution.
  • y1,…,yn are algebraically independent generators for C(x1,…,xn). For we have expressed yu as a rational function of the xs, and the fact that the transformation is invertible shows that we can go back.
  • After any sequence of mutations, if the final cluster variables are
    expressed in terms of the original ones, the denominators are all
    monomials in the original variables.

The variables that arise in this process are called cluster variables. The second component of any seed is a cluster.

Example 1: Let Q and Q* be the quivers with edge (1,2) and (2,1) respectively. Applying μ1 and μ2 in turn, the cluster variables are (writing (x,y) for (x1,x2)):

  • (x,y)
  • ((y+1)/x,y)
  • ((y+1)/x,(x+y+1)/xy)
  • ((x+1)/y,(x+y+1)/xy)
  • ((x+1)/y,x)
  • (y,x)

and then the sequence continues with the pairs reversed, returning to its starting point after ten steps.

So there are ten clusters, consisting of five pairs (involving reversing the terms in an ordered pair), of the five cluster variables.

It is not entirely clear whether the cluster variables should form a set or a sequence. There are five sets of cluster variables in this case.

If we successively mutate at the vertices alternately, we generate a recurrence relation

xn+2 = (1+xn+1)/xn,

which returns to its starting point after five steps. With x1=x2=1, we get the sequence (1,1,2,3,2,1,1,2,…).

We see that the same quiver can be associated with different clusters in a mutation-closed set. However, the following theorem holds:

In the mutation-closure of a single seed, two seeds with the same cluster are equal.

However, the proof of this theorem requires a good deal of theory. I feel that it calls for a more direct proof!

Example 2:
In this case, calculation shows that there are just nine cluster variables, and fourteen (unordered) clusters.

Example 3:
In this example, we saw that mutating the transitive tournament (1,2,3) at 1 produces the transitive tournament (2,3,1). Mutating this at 2 produces (3,1,2), and mutating this at 3 gets us back to (1,2,3).

But the cluster variables do not return to their original values. If we take the original variables to be (x1,x2,x3), and the first mutation to change x1 to x4, then x4=(x2x3+1)/x1. Then we can let the next new cluster variable be x5, and so on; we have the recurrence relation

xn+3 = (xn+1xn+2+1)/xn

with which we began this account.

Specialising the starting variables to 1, the theorem about denominators shows that all cluster variables obtained will have denominator 1, that is, will be integers, as claimed. But the sequence with which we began clearly grows for ever, so the set of cluster variables in this case must be infinite.

The main result of the paper of Fomin and Zelevinsky mentioned earlier (and the reason for discussing clusters in this series) is
the following:

The set of cluster variables arising from a given seed is finite if and only if the quiver is an orientation of one of the ADE diagrams.

This result is particularly intriguing since in most cases, the symmetry exhibited by the root system associated with the diagram is not apparent at all from its geometric realization.

In the next section we look at this a bit further.

Actually their result is a bit more general; I have simplified the presentation. They have a formulation which also allows orientations of the diagrams with multiple bonds, which I will discuss later in the series.


Once we have found the smallest mutation-closed set of quivers containing a given n-vertex quiver, we have a set with n involutions on it, and it is natural to ask what group they generate. In the finite case described by the preceding theorem, it might be natural to expect that this group would be the Coxeter group associated with the diagram; but this turns out not to be the case!

In each of our three examples, the set of quivers is closed under reversing all its edges. The equivalence relation whose classes consist of a quiver and its reverse is preserved by mutation. So in each case the group is imprimitive, with a system of blocks of imprimitivity of size 2.

In Example 1, there are only two quivers, and the group is C2. It is not too hard to show that in Example 2, the group is the semidirect product of the elementary abelian group of order 26 by S7, while in Example 3, it is PSL(2,5) (the rotation group of an icosahedron acting on its twelve faces).

Needless to say, I know no general theory which would have predicted these

The seed-mutations are again involutions on the set of all seeds in a mutation-closed class. The group they generate has the group acting on quivers as a homomorphic image.

In Example 1, the seed-mutation group is dihedral of order 10. The rotations map to the identity and the reflections to the non-trivial permutation of the quivers. I am not sure what happens in the other cases.

So I end with the general problem:

What are the cluster groups associated with clusters for the ADE diagrams? Is there any connection with either the Coxeter groups, or the 3-dimensional rotation groups, of these types?

Previous | Next

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems and tagged , , , , , . Bookmark the permalink.

1 Response to The ADE affair, 3

  1. The answer to the question “given a quiver Q, is the set of quivers which can be obtained from Q by mutation finite or infinite?” is known: the paper arXiv:0811.1703 by Felikson, Shapiro and Tumarkin has the following abstract, which explains the situation, namely

    “In 2003, Fomin and Zelevinsky obtained Cartan-Killing type classification of all cluster algebras of finite type, i.e. cluster algebras having only finitely many distinct cluster variables. A wider class of cluster algebras is formed by cluster algebras of finite mutation type which have finitely many exchange matrices (but are allowed to have infinitely many cluster variables). In this paper we classify all cluster algebras of finite mutation type with skew-symmetric exchange matrices. Besides cluster algebras of rank 2 and cluster algebras associated with triangulations of surfaces there are exactly 11 exceptional skew-symmetric cluster algebras of finite mutation type. More precisely, 9 of them are associated with root systems $E_6$, $E_7$, $E_8$, $\widetilde E_6$, $\widetilde E_7$, $\widetilde E_8$, $E_6^{(1,1)}$, $E_7^{(1,1)}$, $E_8^{(1,1)}$; two remaining were recently found by Derksen and Owen. We also describe a criterion which determines if a skew-symmetric cluster algebra is of finite mutation type, and discuss growth rate of cluster algebras.”

    This result is not terribly well-known, even among relative experts, I think.

    Also, there is a small technicality to watch out for, in that the quivers under consideration need not be connected (i.e. the underlying unoriented graphs need not be connected), and so the Fomin-Zelevinsky classification is strictly speaking a correspondence with semisimple Lie algebras, thus disjoint unions of ADE quivers. The cluster algebra associated to several ADE quivers is simply the tensor product of the cluster algebras associated to each, so it is natural to restrict to the connected case. (The exchange graph, with vertices the clusters and an edge if one cluster is a (single) mutation of the other, for the tensor product is the Cartesian product of the exchange graphs for the components, thus is still finite if the components are of finite (i.e. ADE) type.)

    Finally, there is also another interesting group/graph question one can ask, about automorphisms of the cluster structure. This is discussed in a paper by Assem, Schiffler and Shramchenko (arXiv:1009.0742).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.