Alexander Garver
email: garver0102@math.umn.edu.

Jacob P Matherne

A combinatorial model for exceptional sequences in type A

Keywords: quiver mutation, exceptional sequences, c-matrices, linear extensions

Exceptional sequences are certain ordered sequences of quiver representations. We use noncrossing edgelabeled trees in a disk with boundary vertices (expanding on T. Araya's work) to classify exceptional sequences of representations of Q, the linearly ordered quiver with n vertices. We also show how to use variations of this model to classify c-matrices of Q, to interpret exceptional sequences as linear extensions, and to give a simple bijection between exceptional sequences and certain chains in the lattice of noncrossing partitions. In the case of c-matrices, we also give an interpretation of c-matrix mutation in terms of our noncrossing trees with directed edges.

Résumé. Les suites exceptionnelles sont certaines suites ordonnées de représentations de carquois. Nous utilisons des arbres aux arêtes étiquetés et aux sommets dans le bord d'un disque (expansion sur le travail de T. Araya) pour classifier les suites exceptionnelles de représentations du carquois linéairement ordonné à n sommets. Nous exploitons des variations de ce modèle pour classifier les c-matrices dudit carquois, pour interpréter les suites exceptionnelles comme des extensions linéaires, et pour donner une bijection élémentaire entre les suites exceptionnelles et certaines chaînes dans le réseau des partitions sans croisement. Dans le cas des c-matrices, nous donnons également une interprétation de la mutation des c-matrices en termes des arbres sans croisement aux arêtes orientés.

Introduction

Exceptional sequences are certain ordered sequences of quiver representations introduced in [START_REF] Gorodentsev | Exceptional vector bundles on projective spaces[END_REF] to study exceptional vector bundles on P 2 . Maximal such sequences called complete exceptional sequences also have connections with combinatorics as they are in bijection with maximal chains in the lattice of noncrossing partitions by the work of [START_REF] Ingalls | Noncrossing partitions and representations of quivers[END_REF] and [START_REF] Hubery | A categorification of non-crossing partitions[END_REF]. More recently, complete exceptional sequences were shown to be intrinsically related to acyclic cluster algebras with principal coefficients via the work of Speyer and Thomas [START_REF] Speyer | Acyclic cluster algebras revisited[END_REF]. They appear as certain orderings of the c-vectors of a c-matrix in such a cluster algebra.

We take a combinatorial approach to the study of exceptional sequences. In [START_REF] Araya | Exceptional sequences over path algebras of type A n and non-crossing spanning trees[END_REF], Araya establishes a bijection between the set of complete exceptional collections in type A and the collection of certain chord diagrams called noncrossing spanning trees. It is this simple combinatorial model that serves as the vehicle to our results. Proofs of all of our results will appear in [START_REF] Garver | A combinatorial model for exceptional sequences in type A[END_REF].

In Section 3, we decorate Araya's diagrams with edge-labelings and oriented edges so that they can keep track of both the ordering of the representations in a complete exceptional sequence as well as the signs of the rows in the c-matrix it came from. While Araya's diagrams classify complete exceptional collections, we show that the new decorated diagrams classify more complicated objects called exceptional sequences (Theorem 3). In this language, we give a rule for mutation of oriented diagrams arising from c-matrices in Section 4. We remark that our work is connected to that of Goulden and Yong [START_REF] Goulden | Tree-like properties of cycle factorizations[END_REF] who used edgelabeled noncrossing spanning trees in a disk to study factorizations of the long cycle p1, 2, . . . , n `1q P S n`1 by a collection of transpositions.

The work of Speyer and Thomas (see [START_REF] Speyer | Acyclic cluster algebras revisited[END_REF]) allows complete exceptional sequences to be obtained from c-matrices. In [ONAS `13], the number of complete exceptional sequences in type A n is given, and there are more of these than there are c-matrices. Thus, it is natural to ask exactly which c-matrices appear as Araya's diagrams. We give an answer to this question in Section 5 (Theorem 5).

In Section 6 we ask how many complete exceptional sequences can be formed using the representations in a complete exceptional collection. We interpret this number as the number of linear extensions of the poset determined by the chord diagram of the complete exceptional collection. This also gives an interpretation of complete exceptional sequences as linear extensions.

In Section 7, we give several applications of the theory in type A, including combinatorial proofs that two reddening sequences produce isomorphic ice quivers (see [START_REF] Keller | Cluster algebras and derived categories[END_REF] for a general proof in all types using deep category-theoretic techniques) and that there is a bijection between exceptional sequences and certain chains in the lattice of noncrossing partitions.

Exceptional Sequences

We begin by defining quivers and exchange matrices, which serve as the starting point in our study of exceptional sequences.

Quiver Mutation

A quiver Q is a directed graph without loops or 2-cycles. In other words, Q is a 4-tuple pQ 0 , Q 1 , s, tq, where Q 0 " rms :" t1, 2, . . . , mu is a set of vertices, Q 1 is a set of arrows, and two functions s, t : Q 1 Ñ Q 0 defined so that for every α P Q 1 , we have spαq α Ý Ñ tpαq. An ice quiver is a pair pQ, F q with Q a quiver and F Ă Q 0 frozen vertices with the additional restriction that any i, j P F have no arrows of Q connecting them. We refer to the elements of Q 0 zF as mutable vertices. By convention, we assume Q 0 zF " rns and F " rn `1, ms :" tn `1, n `2, . . . , mu. Any quiver Q can be regarded as an ice quiver by setting Q " pQ, Hq.

The mutation of an ice quiver pQ, F q at mutable vertex k, denoted µ k , produces a new ice quiver pµ k Q, F q by the three step process:

(1) For every 2-path i Ñ k Ñ j in Q, adjoin a new arrow i Ñ j.

(2) Reverse the direction of all arrows incident to k in Q.

(3) Delete any 2-cycles created during the first two steps.

We show an example of mutation below depicting the mutable (resp. frozen) vertices in black (resp. blue).

pQ, F q = 1 2 3 4 µ2 Þ ÝÑ 1 2 3 4 = pµ 2 Q, F q
The information of an ice quiver can be equivalently described by its (skew-symmetric) exchange matrix. Given pQ, F q, we define B " B pQ,F q " pb ij q P Z nˆm :" tn ˆm integer matricesu by

b ij :" #ti α Ñ j P Q 1 u ´#tj α Ñ i P Q 1 u.
Furthermore, ice quiver mutation can equivalently be defined as matrix mutation of the corresponding exchange matrix. Given an exchange matrix B P Z nˆm , the mutation of B at k P rns, also denoted µ k , produces a new exchange matrix µ k pBq " pb 1 ij q with entries b 1 ij :"

" ´bij : if i " k or j " k b ij `|b ik |b kj `bik |b kj | 2 : otherwise.
For example, the mutation of the ice quiver above (here m " 4 and n " 3) translates into the following matrix mutation. Note that mutation of matrices or ice quivers is an involution (i.e. µ k µ k pBq " B).

B pQ,F q " » - 0 2 0 0 ´2 0 1 0 0 ´1 0 ´1 fi fl µ2 Þ ÝÑ » - 0 ´2 2 0 2 0 ´1 0 ´2 1 0 ´1 fi fl " B pµ2Q,F q .
Given a quiver Q, we define its framed (resp. coframed) quiver to be the ice quiver p Q (resp. q Q) where p Q 0 p" q Q 0 q :" Q 0 \ rn `1, 2ns, F " rn `1, 2ns, and p Q 1 :" Q 1 \ ti Ñ n `i : i P rnsu (resp. q Q 1 :" Q 1 \ tn `i Ñ i : i P rnsu). Now given p Q we define the exchange tree of p Q, denoted ET p p Qq, to be the (a priori infinite) graph whose vertices are quivers obtained from p Q by a finite sequence of mutations and with two vertices connected by an edge if and only if the corresponding quivers are obtained from each other by a single mutation. Similarly, define the exchange graph of p Q, denoted EGp p Qq, to be the quotient of ET p p Qq where two vertices are identified if and only if there is a frozen isomorphism of the corresponding quivers (i.e. an isomorphism that fixes the frozen vertices). Such an isomorphism is equivalent to a simultaneous permutation of the rows and the first n columns of one of the corresponding exchange matrices.

Given p Q, we define the c-matrix Cpnq " C R pnq (resp. C " C R ) of R P ET p p Qq (resp. R P EGp p Qq) to be the submatrix of B R where Cpnq :" pb ij q iPrns,jPrn`1,2ns (resp. C :" pb ij q iPrns,jPrn`1,2ns ). We let c-mat(Q) :" tC R : R P EGp p Qqu. By definition, B R (resp. C) is only defined up to simultaneous permutations of its rows and its first n columns (resp. up to permutations of its rows) for any R P EGp p Qq. A row vector of a c-matrix, Ý Ñ c , is known as a c-vector. The celebrated theorem of Derksen, Weyman, and Zelevinsky [DWZ10, Theorem 1.7], known as the Sign-Coherence of c-vectors, states that for any R P ET p p Qq and i P rns the c-vector Ý Ñ c i is a nonzero element of Z n ě0 or Z n ď0 . Thus we say a c-vector is either positive or negative.

For the purposes of this paper, we will only be concerned with the linearly ordered A n quiver Q shown below with its framed quiver p Q.

Q " 1 2 ¨¨¨n n ´1 o o o o o o o o p Q " 1 2 ¨¨¨n ´1 n n `1 n `2 2n ´1 2n o o O O o o O O o o o o O O O O

Representations of quivers

A representation V " ppV i q iPQ0 , pϕ α q αPQ1 q of a quiver Q is an assignment of a k-vector space V i to each vertex i and a k-linear map ϕ α : V spαq Ñ V tpαq to each arrow α where k is an algebraically closed field. The dimension vector of V is the vector dimpV q :" pdim k V i q iPQ0 . Here is an example of a representation, with dimpV q " p3, 3, 2q, of the mutable part of the quiver depicted in Section 2.1.

2 4 1 3 2 2 0 1 3 8 0 3 5 k 3 k 3 k 2 2 4 0 1 7 2 1 5 3 0 0 3 5 » 3 12 4 22 1 0 - Let V " ppV i q iPQ0
, pϕ α q αPQ1 q and W " ppW i q iPQ0 , p α q αPQ1 q be two representations of a quiver Q. A morphism θ : V Ñ W consists of a collection of linear maps θ i : V i Ñ W i that are compatible with each of the linear maps in V and W . That is, for each arrow α P Q 1 , we have θ tpαq ˝ϕα " α ˝θspαq . An isomorphism of quiver representations is a morphism θ : V Ñ W where θ i is a k-vector space isomorphism for all i P Q 0 . We define V ' W :" ppV i ' W i q iPQ0 , pϕ α ' α q αPQ1 q to be the direct sum of V and W . We say that a nonzero representation V is indecomposable if it is not isomorphic to a direct sum of two nonzero representations.

For the linearly ordered A n quiver, it is a standard exercise to show that its indecomposable representations up to isomorphism are exactly the representations X i,j with 0 ď i ă j ď n defined as

1 i j n X i,j :" 0 0 ÐÝ ¨¨¨0 ÐÝ 0 0 ÐÝ k 1 ÐÝ ¨¨¨1 ÐÝ k 0 ÐÝ 0 0 ÐÝ ¨¨¨0 ÐÝ 0.
We remark that representations of Q can equivalently be regarded as modules over the path algebra kQ. As such, one can define Ext s pV, W q (s ě 0) and HompV, W q for any representations V and W . We refer the reader to [START_REF] Assem | Elements of the representation theory of associative algebras[END_REF] for more details on representations of quivers.

An exceptional sequence ξ " pV 1 , . . . , V k q (k ď n :" #Q 0 ) is an ordered list of exceptional representations V j of Q (i.e. V j is indecomposable and Ext s pV j , V j q " 0 for all s ě 1) satisfying HompV j , V i q " 0 and Ext s pV j , V i q " 0 if i ă j for all s ě 1. We define an exceptional collection ξ " tV 1 , . . . , V k u to be a set of exceptional representations V j of Q that can be ordered in such a way that they define an exceptional sequence. When k " n, we say ξ (resp. ξ) is a complete exceptional sequence (CES) (resp. complete exceptional collection (CEC)). For the linearly ordered quiver, a representation is exceptional if and only if it is indecomposable.

The following result of Speyer and Thomas gives a beautiful connection between c-matrices of an acyclic quiver Q and CESs. It serves as motivation for our work. Before stating it, we remark that any c-vector Ý Ñ c of an acyclic quiver Q satisfies Ý Ñ c " ˘dimpV q for some indecomposable representation of Q

[Cha12]. Theorem 1 ([ST13]) Let C P c-matpQq, let t Ý
Ñ c i u iPrns denote the c-vectors of C, and let Ý Ñ c i " ˘dimpV i q for some indecomposable representation of Q. There exists a permutation σ P S n such that pV σp1q , ..., V σpnq q is a CES with the property that if there exist positive c-vectors in C, then there exists k P rns such that Ý Ý Ñ c σpiq is positive if and only if i P rk, ns, and Hom kQ pV i , V j q " 0 if Ý Ñ c i , Ý Ñ c j have the same sign. Conversely, any set of n vectors having these properties defines a c-matrix whose rows are t Ý Ñ c i u iPrns .

3 Chord diagrams and exceptional sequences

We henceforth fix n P N and use Q to denote the linearly ordered A n quiver.

A chord diagram d " tcpi , j qu Prks with k P rns is a graph embedded in a disk with n `1 vertices, called marked points, on the boundary of the disk. The marked points are labeled 0, 1, ..., n counterclockwise starting from the top of the disk. We let cpi, jq denote the chord connecting the marked points labeled i and j. Furthermore, we require that the chords are pairwise non-intersecting in the interior of the disk and that the underlying graph of d is a forest. We similarly define a labeled (resp. oriented) chord diagram, denoted dpkq " tpcpi , j q, s qu Prks (resp. Ý Ñ d " t Ý Ñ c pi , j qu Prks ), to be a chord diagram each of whose chords are labeled by an integer s P rks bijectively (resp. whose chords Ý Ñ c pi , j q are oriented from i to j ). We give examples of each notion of chord diagram of type A 3 below. Theorem 2 ( [START_REF] Araya | Exceptional sequences over path algebras of type A n and non-crossing spanning trees[END_REF]) Let E :" tcomplete exceptional collectionsu, D :" tdiagrams d " tcpi , j qu Prns u.

The map E Ñ D defined by ξ " tX i1,j1 , . . . , X in,jn u Þ Ñ tcpi , j qu Prns is a bijection.

Let dpkq be a labeled diagram, let i be any marked point, and let ppcpi, j j1 q, s 1 q, . . . , pcpi, j jr q, s r qq be the complete list of chords in dpkq involving i ordered so that chords appearing later in the list are clockwise from those earlier in the list in dpkq. We say the chord-labeling of dpkq is good if for each marked point i one has s 1 ă ¨¨¨ă s r . The labeling of the diagram in the previous example is not good.

We now state our first main result. Let Dpkq denote the set of diagrams with k chords and with good labelings and let Epkq :" texceptional sequences ξ " pV 1 , . . . , V k qu.

Theorem 3 Let k P rns. One has a bijection Epkq Ñ Dpkq given by ξ " pX i1,j1 , . . . , X i k ,j k q Þ Ñ tpcpi , j q, k `1 ´ qu Prks .

Proof Sketch: A sequence of representations pV 1 , . . . , V k q is exceptional if and only if pV i , V j q is an exceptional pair (i.e. an exceptional sequence of length 2) for all i, j P rks where i ă j. It can be shown that X i ,j and X i 1 ,j 1 determine exactly one exceptional sequence if and only if the chords cpi , j q and cpi 1 , j 1 q intersect at exactly one marked point (this fact can be deduced from [Ara13, Lemma 3.2]). If i " i 1 , one shows that the only exceptional sequence determined by X i ,j and X i 1 ,j 1 is either pX i ,j , X i ,j 1 q if j ă j 1 or pX i ,j 1 , X i ,j q if j 1 ă j . If j ă j 1 (resp. j 1 ă j ), then cpi , j q (resp. cpi , j 1 q) is clockwise from cpi , j 1 q (resp. cpi , j q). In all other instances where the chords corresponding to X i ,j and X i 1 ,j 1 intersect at a marked point, one shows that the unique exceptional sequence ξ " pV 1 , V 2 q with V i corresponding to a chord c i for i " 1, 2 determined by X i ,j and X i 1 ,j 1 has c 1 appearing clockwise from c 2 . This condition on exceptional pairs translates into the good labeling property for diagrams. l

Mutation of oriented chord diagrams

In this section, we will develop a process of mutation for oriented diagrams that is analogous to the previously defined mutation for quivers and exchange matrices. The following lemma gives a way to associate an oriented diagram to any given c-matrix.

Lemma 1 Let C P c-matpQq with t Ý Ñ c i u iPrns its c-vectors. Let Ý Ñ c i " ˘dimpX i1,i2 q where the sign of Ý Ñ c i is determined by C. There is an injective map c-matpQq

Ñ Ý Ñ D :" toriented diagrams Ý Ñ d " t Ý Ñ c pi , j qu Prns u given by Ý Ñ c i Þ Ñ " Ý Ñ c pi 1 , i 2 q : Ý Ñ c i is positive Ý Ñ c pi 2 , i 1 q : Ý Ñ c i is negative.
Thus each c-matrix C determines a unique oriented diagram denoted Ý Ñ d C with n oriented chords.

The next lemma will be helpful in describing mutation of oriented diagrams in this section. It will also be helpful in classifying c-matrices in the next section. We have found that oriented diagrams arising from c-matrices via Lemma 1 have certain chords which share an endpoint via Lemma 2. We now keep track of how oriented diagrams are affected when their corresponding c-matrices are mutated (via the mutation of exchange matrices in Section 2.1). Just as for quivers, mutation of diagrams is a local property-that is, the chords which do not share an endpoint with the mutating chord are not affected by mutation. The way that intersecting chords are affected depends on exactly which endpoint they share. In the theorem below, we give one of our main results-a mutation formula for oriented diagrams arising from c-matrices.

q ‰ sgnp Ý Ñ c k pRqq, replace Ý Ñ c j pi 1 pjq, i 2 pjqq with Ý Ñ c j ppi 1 pjqq 1 , pi 2 pjqq 1 q where aq pi 1 pjqq 1 " i 2 pkq, pi 2 pjqq 1 " i 2 pjq if i 1 pkq " i 1 pjq, bq pi 1 pjqq 1 " i 1 pjq, pi 2 pjqq 1 " i 1 pkq if i 2 pkq " i 2 pjq, cq pi 1 pjqq 1 " i 1 pkq, pi 2 pjqq 1 " i 2 pjq if i 2 pkq " i 1 pjq, dq pi 1 pjqq 1 " i 1 pjq, pi 2 pjqq 1 " i 2 pkq if i 1 pkq " i 2 pjq. iiq replace Ý Ñ c k pi 1 pkq, i 2 pkqq with Ý Ñ c k pi 2 pkq, i 1 pkqq.
Remark 1 Our notion of mutation expands on Araya's notion of mutation of exceptional pairs, which is an operation on unoriented chord diagrams (see [Ara13, Lemma 5.2]).

Remark 2 The process of oriented diagram mutation requires the information of the mutable part of the ice quiver R.

We conclude this section with an example of mutation of oriented chord diagrams associated to cmatrices in type A 3 . Letting R " p Q with exchange matrix B, we first apply µ 1 . We use both iq and iiq in Theorem 4 to obtain Ý Ñ d µ1C . Note that the chord Ý Ñ c p2, 3q corresponding to 3 was not affected. Next, we apply µ 3 to B 1 " µ 1 B. Since sgnpb 1 32 q " 1 " sgnp Ý Ñ c 3 pµ 1 Rqq, we only use iiq from Theorem 4 to obtain Ý Ñ d µ3µ1C . Notice that the chord Ý Ñ c p0, 1q corresponding to 1 was not affected.

1 2 3 4 5 6 o o O O o o O O O O µ1 Þ ÝÑ 1 2 3 4 5 6 / / o o O O O O _ _ µ3 Þ ÝÑ 1 2 3 4 5 6 / / / / O O _ _ 0 1 2 3 0 1 2 3 0 1 2 3 -→ -→ µ 1 µ 3

Reachable CECs and classification of c-matrices

The bijection in Theorem 2 associates to every CEC ξ a corresponding chord diagram d. It is worth noting in A 3 , there do not exist oriented versions of the following three diagrams obtainable by diagram mutation. This behavior occurs in type A n for every n ě 3. In this section, we classify exactly which CECs appear by classifying diagrams instead. Along the way, we obtain a diagrammatic classification of c-matrices.

A CEC ξ is said to be reachable if there exists an orientation of the diagram Lemma 3 Let C P c-matpQq, let k P r0, ns be any marked point of the disk, and let I :" ti 1 ă i 2 ă ¨¨¨ă i m u Ă r0, ns denote the vertices of the disk that are connected to

d of ξ (see Theorem 2), denoted Ý Ñ d , such that Ý Ñ d " Ý Ñ d C for some C P c-matpQq. Let Ý Ñ d P Ý Ñ D
k in Ý Ñ d C . Then Ý Ñ d C
is weakly separated at k in the sense that there exists s, t P rms such that inp

Ý Ñ d C , kq " ti s ă i s`1 ă ¨¨¨ă i t´1 ă i t u and outp Ý Ñ d C , kq " Izinp Ý Ñ d C , kq or one of outp Ý Ñ d C , kq or inp Ý Ñ d C , kq is empty.
This lemma gives some slight restrictions on the orientation of chords in oriented diagrams arising from c-matrices. The following theorem greatly reduces the number of possible configurations. The corollary below gives a complete classification of c-matrices in terms of oriented chord diagrams.

Corollary 1 The injective image of the map c-matpQq Ñ Ý Ñ D defined in Lemma 1 consists of exactly the oriented diagrams that are weakly separated at each marked point and which contain none of the configurations of Theorem 5 as subdiagrams.

From this description of c-matrices, we see exactly which oriented diagrams are reachable via diagram mutation.

Exceptional sequences and linear extensions

In this section, we consider the problem of counting the number of complete exceptional sequences arising from a given CEC. It turns out this problem can be restated as the problem of counting the number of linear extensions of certain posets.

Let n `1 be the number of marked points on the boundary of the disk. Let cpi, jq be a chord inside the disk. We define a clockwise (resp. counterclockwise) rotation of cpi, jq about i to be cpi, j ´1q (resp. cpi, j `1q) where j ´1 (resp. j `1) denotes the congruence class of j ´1 (resp j `1) mod n `1.

Let d P D. Define the poset of d, denoted P d , to be the partially ordered set whose underlying set is the set of chords of d with the relations x ď y if x and y intersect at a marked point i P r0, ns and y is a chord obtained from x by a sequence of clockwise rotations of x about i. This construction defines a poset because any oriented cycle in the Hasse diagram of P d arises from a cycle in d. Since d is a tree, the diagram has no cycles. In Figure 1 In general, the map D Ñ PpDq :" tP d : d P Du is not injective. For instance, each of the two diagrams in Figure 2 Let P be a finite poset with m " #P. Let f : P Ñ m be an injective, order-preserving map (i.e. x ď y implies f pxq ď f pyq for all x, y P P) where m is the linearly-ordered poset with m elements. We call f a linear extension of P. We denote the set of linear extensions of P by L pPq.

Theorem 7 Let d P D and let ξ denote the corresponding complete exceptional collection. Let CESpξq denote the set of CESs that can be formed using only the representations appearing in ξ. Then the map CESpξq Ñ L pP d q defined by pX i1,j1 , . . . , X in,jn q T hm 3 Þ ÝÑ tpcpi , j q, qu Prns Þ ÝÑ pf pcpi , j qq :" q is a bijection.

Applications

Here we showcase some interesting results that follow easily from our main theorems.

Labeled trees

In [SW86, p. 67], Stanton and White gave a nonpositive formula for the number of vertex-labeled trees with a fixed number of leaves. By connecting our work with that of Goulden and Yong [START_REF] Goulden | Tree-like properties of cycle factorizations[END_REF], we obtain a positive expression for this number. Proof: Observe that

ÿ d P D : d has r chords cpij, ij `1q #L pP d q " ÿ d P D : d has r chords cpij, ij `1q
#tgood labelings of du " # " dpnq P Dpnq : dpnq has r chords cpi j , i j `1q for some i 1 , . . . , i r P r0, ns * where we consider i j `1 mod n `1. By [GY02, Theorem 1.1], we have a bijection between diagrams d P D with r chords of the form cpi j , i j `1q for some i 1 , . . . , i r P r0, ns with good labelings and elements of T n`1 prq. l

Corollary 2 We have pn `1q n´1 " ř dPD #L pP d q.

Reddening sequences

In [START_REF] Keller | Cluster algebras and derived categories[END_REF], Keller proves that for any quiver Q, any two reddening mutation sequences applied to p Q produce isomorphic ice quivers. As mentioned in [START_REF] Keller | Quiver mutation and combinatorial DT-invariants[END_REF], his proof is highly dependent on representation theory and geometry, but the statement is purely combinatorial-we give a combinatorial proof of this result for the linearly ordered quiver Q.

Let R P EGp p Qq. A mutable vertex i P R 0 is called green if there are no arrows j Ñ i in R with j P rn `1, ms. Otherwise, i is called red. A sequence of mutations µ ir ˝¨¨¨˝µ i1 is reddening if all mutable vertices of the quiver µ ir ˝¨¨¨˝µ i1 p p Qq are red. Recall that an isomorphism of quivers that fixes the frozen vertices is called a frozen isomorphism. We now state the theorem.

Noncrossing partitions and exceptional sequences

A partition of rns is a collection π " tB α u αPI P 2 rns of subsets of rns called blocks that are nonempty, pairwise disjoint, and whose union is rns. We denote the lattice of set partitions of rns by Π n . A set partition π " tB α u αPI P Π n is called noncrossing if for any i ă j ă k ă where i, k P B α1 and j, P B α2 , one has B α1 " B α2 . We denote the lattice of noncrossing partitions of rns by N C A pnq.

Label the vertices of a convex n-gon S with elements of rns so that reading the vertices of S counterclockwise determines an increasing sequence mod n. We can thus regard π " tB α u αPI P N C A pnq as a collection of convex hulls B α of vertices of S where B α has empty intersection with any other block B α 1 .

Let n " 5. The following partitions all belong to Π 5 , but only π 1 , π 2 , π 3 P N C A p5q.

π 1 " tt1u, t2, 4, 5u, t3uu, π 2 " tt1, 4u, t2, 3u, t5uu, π 3 " tt1, 2, 3u, t4, 5uu, π 4 " tt1, 3, 4u, t2, 5uu

Below we represent the partitions π 1 , . . . , π 4 as convex hulls of sets of vertices of a convex pentagon. We see from this representation that π 4 R N C A p5q.

Lemma 2

 2 Let R P EGp p Qq, let B " pb ij q denote its exchange matrix with c-matrix C, and let Ý Ñ d C denote the oriented diagram associated to C. If b kj ‰ 0 for some k, j P rns, then the oriented chords Ý Ñ c k pi 1 pkq, i 2 pkqq and Ý Ñ c j pi 1 pjq, i 2 pjqq of Ý Ñ d C corresponding to k and j share an endpoint.

  and let k P r0, ns denote a marked point on the disk. Define the following subsets of the vertices of the disk outp Ý Ñ d , kq :" ti P r0, ns : Ý Ñ c pk, iq P Ý Ñ d u and inp Ý Ñ d , kq :" tj P r0, ns : Ý Ñ c pj, kq P Ý Ñ d u.

Theorem 5 A

 5 CEC ξ is reachable if and only if there exists an orientation of the chords of its associated diagram d, denoted Ý Ñ d , so that Ý Ñ d is weakly separated at each marked point and Ý Ñ d has no subdiagram of any of the following forms:

Fig. 1 :

 1 Fig. 1: A diagram and its poset.Fig. 2: Two diagrams with the same poset.

Fig. 2 :

 2 Fig. 1: A diagram and its poset.Fig. 2: Two diagrams with the same poset.

  have P d " 4 where 4 denotes the linearly-ordered poset with 4 elements. Our next result characterizes the posets arising from diagrams in D. Theorem 6 A poset P P PpDq if and only if iq each x P P has at most two covers and covers at most two elements iiq the underlying graph of the Hasse diagram of P has no cycles iiiq the Hasse diagram of P is connected.

Theorem 8

 8 Let T n`1 prq :" ttrees on rn `1s with r leavesu and D :" tdiagrams d " tcpi , j qu Prns u. Then #T n`1 prq " ÿ d P D : d has r chords cpij, ij `1q #L pP d q.

  Theorem 10 Let k P rns. There is a bijection between Epkq and the following chains in N C A pn `1q" ttiuu iPrn`1s ă π 1 ă ¨¨¨ă π k P pN C A pn `1qq k`1 : π j " pπ j´1 ztB α , B β uq \ tB α \ B β u for some B α ‰ B β in π j´1 * .

  Theorem 9 If µ ir ˝¨¨¨˝µ i1 and µ js ˝¨¨¨˝µ j1 are two reddening sequences of p Q, then there is a frozen isomorphism µ ir ˝¨¨¨˝µ i1 p p Qqµ js ˝¨¨¨˝µ j1 p p Qq. Proof: Let µ ir ˝¨¨¨˝µ i1 be any reddening sequence. Denote by C the c-matrix of µ ir ˝¨¨¨˝µ i1 p p Qq. By Corollary 1, C corresponds to an oriented diagram Ý Ñ d C with all chords of the form Ý Ñ c pj, iq for some i and j satisfying i ă j. As Ý Ñ d C avoids the configurations of Theorem 5, we conclude that Ý Ñ d C " t Ý Ñ c pi, i ´1qu iPrns so C " ´In . Since c-matrices are in bijection with ice quivers in EGp p Qq (see [NZ12, Thm 1.2]) and since q Q is an ice quiver in EGp p Qq whose c-matrix is ´In , we obtain the desired result. l

Acknowledgements

Helpful insight was given during conversations with E. Barnard, J. Geiger, G. Muller, G. Musiker, D. Rupel, D. Speyer, and G. Todorov. M. Kulkarni helped with some of the diagrams, and P. Achar gave assistance with the French abstract. We thank G. Muller and G. Musiker for their helpful comments on drafts of our abstract and S. A. Csar whose PhD thesis defense inspired us to see the connections between exceptional sequences and linear extensions. We also thank the 2014 Mathematics Research Communities program for giving us an opportunity to work on this exciting problem as well as for giving us a stimulating (and beautiful) place to work.

This author was supported by a Research Training Group, RTG grant DMS-1148634. ; This author was supported by a Graduate Assistance in Areas of National Need fellowship, GAANN grant P200A120001. 1365-8050

Here we give examples of the bijection from the previous theorem with k " 4.

8 Future directions

In this work, we have only worked out the combinatorics of exceptional sequences associated to the linearly oriented A n Dynkin diagram. However, exceptional sequences are defined for any acyclic quiver.

We have made progress in extending our work to the following quiver of type D n and would like to extend our results to all acyclic orientations of simply-laced Dynkin diagrams.

We have characterized the posets P d that arise from diagrams d P D and have shown that the number of linear extensions of P d equals the number of complete exceptional sequences that can be formed from the CEC ξ corresponding to d. In forthcoming work (see [GM]), we will present a method for computing the linear extensions of the posets P d and explain the connections between such linear extensions and the theory of factorizations of the long cycle p1, 2, . . . , n`1q P S n`1 by a set of transpositions (see [START_REF] Goulden | Tree-like properties of cycle factorizations[END_REF]).


Sophie Burrill

Stephen Melczer

Marni Mishna

A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape

Keywords: Young tableaux, nonnesting partitions, matchings, Baxter permutations, bijections, oscillating tableaux

Tableau sequences of bounded height have been central to the analysis of k-noncrossing set partitions and matchings. We show here that families of sequences that end with a row shape are particularly compelling and lead to some interesting connections. First, we prove that hesitating tableaux of height at most two ending with a row shape are counted by Baxter numbers. This permits us to define three new Baxter classes which, remarkably, do not obviously possess the antipodal symmetry of other known Baxter classes. Oscillating tableau of height bounded by k ending in a row are in bijection with Young tableaux of bounded height 2k. We discuss this recent result, and some generating function implications. Many of our proofs are analytic in nature, so there are intriguing combinatorial bijections to be found.

Résumé. Les séquences de tableau de hauteur bornée sont au centre de l'analyse des partages et couplages. Nous montrons que les familles de squences qui se terminent par une seule ligne sont particulièrement fascinantes. Tout d'abord, nous prouvons que les tableaux hésitants de hauteur au plus deux se terminant par une seule ligne sont dénombrés par les nombres de Baxter. Cela nous permet de définir trois nouvelles classes Baxter qui, remarquablement, ne possèdent évidemment pas la symétrie antipodes des autres classes Baxter connus. Nous discutons le résultat récent qui dit que les tableaux oscillants de hauteur au plus k se terminant dans une ligne sont en bijection avec les tableaux de Young de hauteur au plus 2k. Nos preuves sont analytiques, il y a donc des bijections combinatoires intrigantes à trouvs.

Introduction

The counting sequence for Baxter permutations, whose elements

B n = n k=1 n+1 k-1 n+1 k n+1 k+1 n+1 1 n+1 2
are known as Baxter numbers, is a fascinating combinatorial entity, enumerating a diverse selection of combinatorial classes and resurfacing in many contexts which do not a priori appear connected. The recent comprehensive survey of Felsner, Fusy, Noy and Orden [START_REF] Felsner | Bijections for Baxter families and related objects[END_REF] finds many structural commonalities among these seemingly diverse families of objects.

Here we describe three new combinatorial classes which are enumerated by Baxter numbers. These classes have combinatorial bijections between them, but do not share many of the properties of the other known Baxter classes aside from a natural Catalan subclass. Rather, they connect to the restricted arc diagram family of objects, whose study was launched by Chen, Deng, Du, Stanley and Yan [START_REF] William | Crossings and nestings of matchings and partitions[END_REF]. We have discovered a bridge between classic Baxter objects and sequences of tableaux, and consequently walks in Weyl chambers. The main focus of this article is tableau sequences that end in a (possibly empty) row shape: as these correspond to a family of lattice walks that end on a boundary, we are able to deduce enumerative results and find surprising connections to other known combinatorial structures. Another consequence of this construction is a new generating tree description for Baxter numbers.

Our main results are Theorem 1 and Theorem 2. They use the integer lattice W k = {(x k , . . . , x 1 ) :

x k > • • • > x 1 > 0, x i ∈ N}.
All of the other combinatorial classes referenced in the statement are defined in the next section.

Theorem 1

The following classes are in bijection for all nonnegative integers m, n and k:

1. H (k)
n,m : the set of hestitating tableaux of length 2n, with maximum height bounded by k, starting from ∅, ending in a strip of length m;

L (k)

n,m : the set of W k -hesitating lattice walks of length 2n, starting at δ = (k, k -1, . . . , 1) ending at (m + k, k -1, . . . , 1); The equivalence (1) ≡ (2) follows almost immediately from the proof of Theorem 3.6 of [START_REF] William | Crossings and nestings of matchings and partitions[END_REF]. We discuss it in Section 3. We then prove the equivalence (1) ≡ (3), by providing an explicit bijection. It is a slight modification of the bijection φ used in the proof of Theorem 4.3 of [START_REF] William | Crossings and nestings of matchings and partitions[END_REF].

Ω

It is well known that both L

n,0 and Ω

n,0 are of cardinalty C n , the Catalan number of index n. Furthermore, we have the following theorem, proved in Section 4.

Theorem 2 Let (k) m(n) = |L (k) n,m |. The number of walks in L (2) n,m over all possible values of m is equal to the Baxter number of index n + 1. That is, n m=0 (2) m (n) = B n+1 .
The related class of oscillating tableaux that end in a row also gives rise to some interesting results. The proof of this theorem is analogous to the proof of the previous theorem, and we do not present it here. Rather, we are highly intrigued by a fourth class that also appears to be in bijection.

Conjecture 4

The set of W k -oscillating lattice walks of length n ending at the boundary {(m + k, k -1, . . . , 1) : m ≥ 0} is in bijection with standard Young tableaux of size n, with height bounded by 2k.

As far as we can tell, this was first conjectured by Burrill [START_REF] Burrill | A generating tree approach to k-nonnesting arc diagrams[END_REF]. Using the lattice path characterization, we access generating function expressions, and prove the conjecture for k ≤ 8. We discuss the strong evidence for Conjecture 4 in Section 5.

The Combinatorial Classes

We now describe the combinatorial classes mentioned in the two main theorems.

Tableaux families

There are three tableaux families that we consider.

oscillating tableau This is a sequence of Ferrers diagrams such that at every stage a box is either added, or deleted. The sequences start from an empty shape, and have a specified ending shape. The size is the length of the sequence.

standard Young tableau This is an oscillating tableau where boxes are only added and never removed.

hesitating tableau This is a variant of the oscillating tableaux. They are even length sequences of Ferrers diagrams that start from an empty tableaux. The sequence is composed of pairs of moves of the form: (i) do nothing then add a box; (ii) remove a box then do nothing; or (iii) add a box then remove a box.

In each case, if no diagram in the sequence is of height k + 1, we say that the tableau has height bounded by k. This is how we arrive to the set

H (k)
n,m , of hestitating tableaux of length 2n, with height bounded by k, ending in the shape (m) (i) .

Lattice walks

We focus on two different lattice path families. We are interested in walks in the region (ii)

W k = {(x 1 , x 2 , . . . , x k ) : x i ∈ Z, x 1 > x 2 > • • • > x k > 0} starting at the point δ = (k, k -1, . . . , 1)
. Let e i be the elementary vector with a 1 at position i and 0 elsewhere. We permit steps that do nothing, which we call "stay steps".

The class of W k -oscillating walks starts at δ and takes steps of type e i or -e i , for

1 ≤ i ≤ k. We define O (k)
n,m to be the set of oscillating walks in W k of length n, ending at the point me 1 + δ. A W k -hesitating walk is of even length, and steps occur in the following pairs: (i) a stay step followed by an e i step; (ii) a -e i step followed by a stay step; (iii) an e i step follow by -e j step. We focus on L (k) n,m : the set of hesitating lattice walks of length 2n in W k , starting at (k, k -1, . . . , 1) and ending at (m + k, k -1, . . . , 1).

(i) Here, (0) ≡ ∅ (ii) Remark this model is a reparametrization of the region considered in [START_REF] William | Crossings and nestings of matchings and partitions[END_REF]. We slightly shift the notation of [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF].

Open arc diagrams

Matchings and set partitions are two combinatorial classes that have natural representations using arc diagrams. In the arc diagram representation of a set partition of {1, 2, . . . , n}, a row of increasing vertices is labelled from 1 to n. A partition block {a 1 , a 2 , . . . , a j }, ordered a 1 < a 2 < . . . < a j , is represented by the arcs (a 1 , a 2 ), (a 2 , a 3 ), . . . , (a j-1 , a j ) which are always drawn above the row of vertices. The set partition π = {{1, 3, 7}, {2, 8}, {4}, {5, 6}} is depicted as an arc diagram in Figure 1. Matchings are represented similarly, with each pair contributing an arc. A set of k arcs (i 1 , j 1 ), . . . , (i k , j k ) form a k-1 2 3 4 5 6 7 8

Fig. 1: The set partition π = {1, 3, 7}, {2, 8}, {4}, {5, 6}

nesting if i 1 < i 2 < • • • < i k < j k < • • • < j 2 < j 1 . They form an enhanced k-nesting if i 1 < i 2 < • • • < i k ≤ j k < • • • < j 2 < j 1 . They form a k-crossing if i 1 < i 2 < • • • < i k < j 1 < j 2 < • • • < j k .
Figure 2 illustrates a 3-nesting, an enhanced 3-nesting, and a 3-crossing. A partition is k-nonnesting if it does not contain any collection of edges that form a k-nesting. Recently, Burrill, Elizalde, Mishna and Yen [START_REF] Burrill | A generating tree approach to k-nonnesting partitions and permutations[END_REF] generalized arc diagrams by permitting semi-arcs: in the diagrams, each arc must have a left endpoint, but not necessarily a right endpoint. The notion of k-nesting is generalized to a future k-nesting, which is a pattern with an open arc to the left of a (k -1)-nesting, and a future enhanced k-nesting is defined similarly. An example is given in Figure 2. Burrill et al. [START_REF] Burrill | A generating tree approach to k-nonnesting partitions and permutations[END_REF] conjectured that open partition diagrams with no future enhanced 3-nestings, nor enhanced 3-nestings were counted by Baxter numbers.

Bijections

We now give the bijections to prove Theorem 1. Table 1 illustrates the different mappings in the case of n = 2, k = 2.

Tableaux to walks

The bijection between

H (k) n,m and L (k)
n,m is a straightforward consequence of the proof of Theorem 3.6 of [START_REF] William | Crossings and nestings of matchings and partitions[END_REF]. The authors give the bijection explicitly for vacillating tableaux, but the results follow directly for the case of hesitating tableaux. In their bijection, a shape λ = (λ 1 , . . . , λ k ) in a hesitating tableaux corresponds to a point in position δ + λ = (λ 1 + k, λ 2 + k -1, . . . , λ k + 1) in the hestitating walk.

Arc diagrams and tableaux

We modify Chen et al.'s bijection between set partitions and hesitating tableaux to incorporate the possibility that an edge is not closed. In this abstract, we simply describe how to modify Marberg's presentation Proof: We prove this by describing how to process open arcs. We assume the reader has some familiarity with the original bijection to have a brief presentation of our bijection. We read diagrams from left to right, and insert and delete cells under the same rules as Marberg [START_REF] Marberg | Crossings and nestings in colored set partitions[END_REF]. The insertion depends on the right endpoints of the arcs. If the diagram has n vertices, we incrementally label the right endpoints of the open arcs with labels n + 1 to n + m from left to right, as seen in Figure 3.

Tableaux H (2) 2,m Walks L (2) 2,m Open partitions Ω (2) 2,m m = 0 ∅ ∅ ∅ (2,1)-(3,1)-(2,1)-(3,1)-(2,1) ∅ ∅ ∅ ∅ (2,1)-(2,1)-(3,1)-(2,1)-(2,1) ∅ ∅ ∅ (2,1)-(3,1)-(2,1)-(2,1)-(3,1) m = 1 ∅ ∅ (2,
Recall how vertices are processed in this bijection. Each vertex corresponds to two steps; if i is a left endpoint, first do nothing and then insert its (possibly artificial) right endpoint into the tableau; if i is a right endpoint, delete it from the tableau and then do nothing; if i is both a right endpoint of some arc (i , i) and left endpoint of (i, i ), first insert i into the tableaux and then delete i. If i is a fixed point, first insert i, then delete i. The insertion is done with RSK, and the deletion is simple cell deletion.

In this process, the values corresponding to open arcs are inserted in the tableau in order, and are never deleted. By RSK, they will all be in the same row. Once the other points are deleted, all that will remains is a single row of length m.

The inverse map of Marberg (and ultimately Chen et al.) is similarly adapted. 2

4 When k = 2 the complete generating function is Baxter

Baxter permutations

Baxter numbers comprise entry A001181 of the Online Encylopedia of Integer Sequences (OEIS) [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF], and their main interpretation is the number of permutations σ of n such that there are no indicies i < j < k satisfying σ(j + 1) < σ(i) < σ(k) < σ(j) or σ(j) < σ(k) < σ(i) < σ(j + 1). They were introduced by Baxter [START_REF] Baxter | On fixed points of the composite of commuting functions[END_REF] in a question about compositions of commuting functions, and have since been found in many places in combinatorics.

Chung et al. [START_REF] Chung | The number of Baxter permutations[END_REF] found the explicit formula for the n th Baxter number given in Section 1, and also gave a second order linear recurrence:

8(n + 2)(n + 1)B n + (7n 2 + 49n + 82)B n+1 -(n + 6)(n + 5)B n+2 = 0. (1)
We prove Theorem 2 by a a generating function argument. We use the notation x = 1

x , and work in the ring of formal series Q

[x, x][[t]]. The operator P T x (resp N T x ) extracts positive (resp. negative) powers of x in series of Q[x, x][[t]
]. We relate this to the diagonal operator ∆ defined by : ∆ i,j∈N f i,j

x i t j = n f n,n t n . A bivariate series in Q[x][[t]
] is D-finite with respect to t and x if the set of its partial derivatives spans a finite dimensional vector space over Q. Lipshitz [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]

proved that if F (x, t) ∈ Q[x][[t]] is D-finite then so is f (t) = ∆F (x, t
). This result is effective, and creative telescoping strategies have resulted in efficient algorithms for computing such differential equations [START_REF] Chyzak | An extension of zeilberger's fast algorithm to general holonomic functions[END_REF][START_REF] Bostan | Creative telescoping for rational functions using the griffiths-dwork method[END_REF]: that is, given a system of differential equations satisfied by F (x, t), one can compute the linear differential equation satisfied by ∆F (x, t) = f (t). There are several implementations in various computer algebra systems, such as Mgfun by Chyzak in Maple [START_REF] Chyzak | Holonomic systems and automatic proofs of identities[END_REF], and the HolonomicFunctions package of Koutschan in Mathematica [START_REF] Koutschan | A fast approach to creative telescoping[END_REF].

Roughly, the strategy is to use elimination in an Ore algebra or an ansatz of undetermined coefficients to compute differential operators annihilating the multivariate integral

1 2πi Ω F (x, t/x) x dx = ∆F (x, t), (2)
where Ω is an appropriate contour in C containing the origin.

A generating function for hesitating walks ending on an axis

We recall Proposition 12 of Bousquet-Mélou and Xin [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF]; As noted earlier, we have shifted our indices, and our presentation of their results are duely adapted. Here Q k is the first quadrant Q k = {(x 1 , . . . , x k ) :

x i > 0}.

Proposition 6 (Bousquet-Mélou and Xin, Propostion 12 of [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF]) For any starting and ending points λ and µ in W k , the number of W k -hesitating walks going from λ to µ can be expressed in terms of the number of Q k hesitating walks as follows:

w k (λ, µ, n) = π∈S k (-1) π q k (λ, π(µ), n),
where (-1) π is the sign of π and π(µ 1 , . . . , µ k ) = (µ π(1) , . . . , µ π(k) ).

The result is proved by a classic reflection argument using a simple sign reversing involution between pairs of walks; the walks restricted to W k appear as fixed points. We restrict to k = 2, and define

H(x; t) = i,n
q 2 ((2, 1), (i, 1), 2n)x i t n and V (y; t) = i,n q 2 ((2, 1), (1, i), 2n)y i t n .

By applying the proposition we see immediatetly that

W (x, t) = i,n
w 2 ((2, 1), (i, 1), 2n)

x i t n = H(x; t) -V (x; t). (3)
Their explicit Proposition 13 is key to our solution.

Proposition 7 (Bousquset-Mélou and Xin, Proposition 13 of [START_REF] Bousquet | On partitions avoiding 3-crossings[END_REF]) The series H(x; t) and V (y; t) which count Q 2 -hesitating walks of even length ending on the x-axis and on the y-axis, satisfy

xH(x; t) = P T x Y t(1+x) (x 2 -Y 2 /x 2 + Y /x 3 ) (4)
x 2 V (x; t) = N T x Y t(1+x) (x 2 -Y 2 /x 2 + Y /x 3 ), ( 5
)
where Y is the algebraic function

Y = -tx 2 + (1 -2t)x -t t 2 x 4 -2 tx 3 + (-2 t 2 -4 t + 1) x 2 -2 tx + t 2 2t (1 + x) .
Using this, we can express W (x, t) as a diagonal. Define

G(x, t) = Y t(1 + x) x 2 -Y 2 /x 2 + Y /x 3 . ( 6
)
Lemma 8 The generating function for the class of walks of W 2 -hesitating walks of even length end on the x-axis defined

W (t) = i,n w 2 ((2, 1), (i, 1), n)t n satisfies W (t) = ∆ G 1 x , xt -G(x, xt) 1 1 -x . (7)
Proof: We remark that W (t) = H(1; t) -V (1; t) by Equation 3. We apply Proposition 7, and then convert P T and N T operators to diagonal operations by straightforward series manipulation: Furthermore, the Equation 1 implies that the shifted generating function for the Baxter numbers written above also satisfies this differential equation. As the solution space of the differential operator L is a vector space of dimension 5; to prove equality it is sufficient to show that the first five terms of the generating functions are equal. We have verified that the initial terms in the series agree for over 200 terms. 2

H(1; t) = P T x G(x, t)| x=1 = ∆ G 1 x , xt 1 1 -x , V (1; t) = ∆ G(x, xt) 1 1 -x . (8

A new generating tree

A generating tree for a combinatorial class expresses recursive structure in a rooted plane tree with labelled nodes. The objects of size n are each uniquely generated, and the set of objects of size n comprise the n th level of the tree. They are useful for enumeration, and for showing that two classes are in bijection. One consequence of Theorem 2 is a new generating tree construction for Baxter objects. Several different formalisms exist for generating trees, notably [START_REF] Banderier | Generating functions for generating trees[END_REF]. The central properties are as follows. Every object γ in a combinatorial class C is assigned a label (γ) ∈ Z k , for some fixed k. There is a rewriting rule on these labels with the property that if two nodes have the same label then the ordered list of labels of their children is also the same. We consider labels that are pairs of positive integers, specified by { Root : [i, j] → Succ([i, j])}, where Root is the label of the root.

Two generating trees for Baxter objects are known in the literature, and one consequence of Theorem 1 is a third, using the generating tree for Ω (k) given by Burrill et al. [START_REF] Burrill | A generating tree approach to k-nonnesting partitions and permutations[END_REF]. This tree differs from the other two already at the third level, illustrating a very different decomposition of the objects. For the three different systems, we give the succession rules, and the first 5 levels of the tree (unlabelled) in Figure 4.

Standard Young tableaux of bounded height

Chen et al. [START_REF] William | Crossings and nestings of matchings and partitions[END_REF] give an analogy comparing the relationship between oscillating tableaux and irreducible representations of the Brauer algebra to the relationship of standard Young tableaux and the symmetric group. Indeed, there are many connections between standard Young tableaux of bounded height and oscillating tableaux of bounded height, but we were unable to find any consideration of the following conjecture.

Conjecture 10

The set of oscillating lattice walks of length n in W k ending at the boundary {(m + k, k -1, . . . , 1) : m ≥ 0} is in bijection with the set of standard Young tableaux of size n, of height bounded by 2k.

The case of k = 1 is straightforward. An oscillating walk in W 1 is simply a sequence of e 1 and -e 1 steps such that at any point the number of e 1 is greater than or equal to the number of -e 1 . There is a simple bijection to standard Young tableaux of height 2: Given an oscillating walk as a sequence of steps, w = w 1 , w 2 , . . . , w n , the standard Young tableaux is filled by putting entry j on the top row of the tableau if w j = e 1 , and on the second row if w j = -e 1 . However, the interaction between the steps is less straightforward in higher dimensions. Eric Fusy remarked to us that the inverse RSK bijection maps standard Young tableaux to involutions, as the images of pairs of identical tableaux. This does not directly give our matching diagrams, but it is a promising candidate for a bijection.

To give evidence for this conjecture, we first give expressions for the exponential generating functions using determinants of matrices filled with Bessel functions. For any k the equivalence could be verified in this manner, and we have done so for k ≤ 8. It is possible that very explicit manipulations might also give an answer.

Next we express Young tableaux as walks, and use standard generating function techniques for the ordinary generating functions. This gives us a different characterization of the bijection in terms of walks, and two expressions for the generating functions as diagonals of rational functions. The technical details of the constructions are reserved for the long version of this article.

A determinant approach

Our first approach to settling this conjecture is a direct appeal to two recent enumerative results. In this section, b j (x) = I j (2x) = n (2x) 2n+j n!(n+j)! , the hyperbolic Bessel function of the first kind of order j. Let the Ỹk (t) be the exponential generating function for the class of standard Young tableaux with height bounded by k. Formulas for Ỹk (t) follow from works of Gordon, Houten, Bender and Knuth [START_REF] Gordon | Notes on plane partitions[END_REF][START_REF] Gordon | Notes on plane partitions. I, II[END_REF][START_REF] Bender | Enumeration of plane partitions[END_REF], which depend on the parity of k. We are only interested in the even values here.

Theorem 11 ( [15, 16, 3]) The exponential generating function for the class of standard Young tableaux of height bounded by 2k is given by

Ỹ2k (t) = det[b i-j (t) + b i+j-1 (t)] 1≤i,j≤k .
Around the same time, Grabiner-Magyar [START_REF] Grabiner | Random walks in Weyl chambers and the decomposition of tensor powers[END_REF] determined an exponential generating function for O (k) n (λ; µ), the number of oscillating lattice walks of length n from λ to µ, which stay within the k-dimensional Weyl chamber W k and take steps in the positive or negative unit coordinate vectors.

Theorem 12 ) For fixed λ, µ ∈ W k , the exponential generating function for O n (λ; µ) satisfies

O λ,µ (t) = n≥0 |O n (λ; µ)| t n n! = det b µi-λj (2t) -b µi+λj (2t) 1≤i,j≤k .
We specialize the start and end positions as λ = δ = (d, d -1, . . . , 1) and µ = δ + me 1 = (d + m , d -1, . . . , 1) = (m, d -1, . . . , 1). We are interested in the sum over all values of m, and define O k (t) ≡ m≥0 O δ,me1+δ (t). Using their result we deduce the following.

Proposition 13

The exponential generating function for the class of oscillating tableaux ending with a row shape is the finite sum

Õk (t) = k-1 u=0 (-1) u 2k-1-2u =u (I ) det(I i-j -I kd-i-j ) 0≤i≤k-1,i =u,1≤j≤k-1 .
This follows from the fact that the infinite sum which arises from direct application of Grabiner and Magyar's formula telescopes, using also the identity b -k = b k . Our conjecture is equivalent to Õk (t) = Ỹ2k (t). Here are the first two values:

Õ1 (t) = Ỹ2 (t) = b 0 + b 1 , Õ2 (t) = Ỹ4 (t) = b 2 0 + b 0 b 1 + b 0 b 3 -2b 1 b 2 -b 2 2 -b 2 1 + b 1 b 3 .
The determinants are easy to compute for small values, and they agree for k ≤ 8.

A diagonal approach

Using Theorem 3, we can reformulate the conjecture to be strictly in terms of lattice paths by viewing standard Young tableaux as oscillating tableaux with no deleting steps.

Conjecture 14

The set of oscillating lattice walks of length n in W k starting at δ = (k, k -1, . . . , 1) and ending at the boundary at the boundary {me 1 + δ : m ≥ 0} is in bijection with the set of oscillating lattice walks of length n in W 2k , using only positive steps (e j ), starting at δ and ending anywhere in the region.

To approach this, we consider the set of walks separately using some standard enumeration techniques: namely the orbit sum method and results on reflectable walks in Weyl Chambers. Some of the enumerative parallels of these strategies in this context are discussed in [START_REF] Melczer | Asymptotic lattice path enumeration using diagonals[END_REF]. The advantage of these diagonal representations is potential access to asymptotic enumeration formulas, and possibly alternative combinatorial representations. All of the generating functions are D-finite, and we can use the work of [START_REF] Bostan | Creative telescoping for rational functions using the griffiths-dwork method[END_REF] to determine bounds on the shape of the annihilating differential equation.

Theorem 15

The ordinary generating function for oscillating walks starting at δ and ending on the boundary {me 1 + δ : m ≥ 0}, is given by the following formula:

O k (t) = ∆ t 2d-1 (z 3 z 2 4 • • • z k-2 k )(z 1 + 1) 1≤j<i≤k (z i -z j )(z i z j -1) • 2≤i≤k (z 2 i -1) 1 -t(z 1 • • • z k )(z 1 + z 1 + • • • z d + z d )
.

The proof of Theorem 15 is a rather direct application of Gessel and Zeilberger's formula for reflectable walks in Weyl chambers. By applying an orbit sum analysis, we derive the following expression. There are still some points to verify in the computation, so although we believe it, and have verified it up to k = 8, this form remains as a conjecture. Conjecture 16 The ordinary generating function for standard Young tableau of height at most k is

Y k (t) = ∆ (z 1 • • • z k-1 )Φ(z) (1 -t(z 1 • • • z k-1 )S(z))(1 -z 1 ) • • • (1 -z k-1 )
,

where

S(z) = z 1 + z 1 z 2 + • • • + z k-1 z k-2 + z k-1 , and
Φ(z) = (z 1 z k-1 -1) (z 1 • • • z k-1 ) k-1 k-2 j=1 (z 1 z j -z j+1 ) k-1 j=2 (z k-1 z j -z j-1 ) k-3 j=1 k-1 k=j+2 (z j z k -z j+1 z k-1 ).
In order to prove the conjecture, giving an explicit diagonal representation for the generating function of the number of standard Young tableaux of a given height, it is sufficient to prove that for every d σ∈G (-1) sgn(g) σ(z1

• • • z d-1 ) = (z1z k-1 -1) (z1 • • • z k-1 ) k-1 k-2 j=1 (z1zj-zj+1) k-1 j=2 (z k-1 zj-zj-1) k-3 j=1 k-1 k=j+2 (zjz k -zj+1z k-1 ),
where G is the finite group of rational transformations of R

Conclusion

These problems are clearly begging for combinatorial proofs. There are a huge number of candidates for Baxter objects to choose from, and hopefully the Catalan subclasses are retained.

The diagonal expressions in Section 5.2, which are of interest in their own right, are also compelling in a wider context. We are quite interested in the conjecture of Christol on whether or not globally bounded D-finite series can always be expressed as a diagonal of a rational function. The class of standard Young tableau of bounded height is a very intriguing case, and follows our study of lattice path walks [START_REF] Melczer | Asymptotic lattice path enumeration using diagonals[END_REF] wherein we consider the study of diagonal expressions for known D-finite classes.

  : open partition diagrams of length n with m open arcs, but with no enhanced (k +1)-nesting, nor future enhanced (k + 1)-nesting.

Theorem 3

 3 The following classes are in bijection:1. Oscillating tableaux of length n, maximum height bounded by k ending in a strip of length m; 2. The set of W k -oscillating lattice walks of length n ending at (m + k, k -1, . . . , 1); 3. Open matching diagrams of length n with no (k + 1)-nesting, nor future (k + 1)-nesting, with m open arcs.

Fig. 2 :

 2 Fig. 2: A 3-nesting, an enhanced 3-nesting, a 3-crossing, and a future enhanced 3-nesting

1Fig. 3 :Proposition 5

 35 Fig. 3: Preparing an open diagram for the bijection.

Fig. 4 :

 4 Fig. 4: The first five levels of each of the Baxter generating tree. They are respectively from [4] [7] [9].

  d-1 generated by φ1 : (z1, . . . , z d-1 ) → (z1z2, . . . , z d-1 ) (1 < k < d -1) φ k : (z1, . . . , z d-1 ) → (z1, . . . , z k-1 , z k-1 z k z k+1 , z k+1 , . . . , z d-1 ) φ d-1 : (z1, . . . , z d-1 ) → (z1, . . . , z d-1 , z d-2 z d-1 ), which acts on f ∈ R[z 1 , . . . , z d ] by σ(f (z 1 , . . . , z d-1 )) = f (σ(z 1 , . . . , z d-1 )). It can be shown that G is isomorphic to the symmetric group S d , however the action of its elements in terms such as σ(z 1 • • • z d-1 ) is less clear.

) 2

 2 Theorem 9 Let B n be the number of Baxter permutations of size n. Then W (t) = B n+1 t n .Proof: We prove this using effective computations for D-finite closure properties. Using the Mathematica package of Koutschan[START_REF] Koutschan | A fast approach to creative telescoping[END_REF] we use our expression for W (t) as a diagonal to calculate that it satisfies the differential equation L • W (t) = 0, where L is the differential operator L :=t4 (t + 1) (8 t -1) D t 5 + t 3 -20 + 147 t + 176 t 2 D t 4 + 4 t 2 -30 + 241 t + 304 t 2 D t 3 + 12 t -20 + 191 t + 256 t 2 D t 2 + 24 -5 + 72 t + 104 t 2 D t + 240 + 384 t.

Acknowledgements

We are extremely grateful to Eric Fusy, Julien Courtiel, Sylvie Corteel, Lily Yen, Yvan le Borgne and Sergi Elizalde for stimulating conversations, and important insights.

† Supported by an NSERC Alexander Graham Bell Canada Graduate Scholarship ‡ Supported by an NSERC Discovery Grant 1365-8050 c 2015


Anne-Sophie Gleitz
email: anne-sophie.gleitz@unicaen.fr

Generalised cluster algebras and q-characters at roots of unity

Keywords: representation theory, (generalised) cluster algebras, quantum affine algebras, restricted integral form, q-characters, ε-characters, Kirillov-Reshetikhin modules, quantum loop algebras

, have studied the restricted integral form U res ε ( g) of a quantum affine algebra Uq( g) where q = ε is a root of unity. Our main result states that the Grothendieck ring of a tensor subcategory C ε Z of representations of U res ε (Lsl2) is a generalised cluster algebra of type C l-1 , where l is the order of ε 2 . We also state a conjecture for U res ε (Lsl3), and sketch a proof for l = 2.

), ainsi que Frenkel et Mukhin (2002), ont étudié la forme entière restreinte d'une algèbre affine quantique Uq( g) où q = ε est une racine de l'unité. Notre résultat principal affirme que l'anneau de Grothendieck d'une sous-catégorie tensorielle C ε Z de représentations de U res ε (Lsl2) est une algèbre amassée généralisée de type C l-1 , où l est l'ordre de ε 2 . Nous conjecturons une propriété similaire pour U res ε (Lsl3) et donnons un aperçu de la preuve pour l = 2.

Introduction

Cluster algebras have been introduced in 2001 by Fomin and Zelevinski [START_REF] Fomin | Cluster algebras I: Foundations[END_REF]. These rings have special generators, called cluster variables. For every cluster x, and every cluster variable x ∈ x, there is a unique cluster (x \ {x}) ∪ {x }, and an exchange relation

xx = m + + m - (1.1)
where m ± are exchange monomials in x \ {x}. Fomin and Zelevinsky [START_REF] Fomin | Cluster algebras II: Finite type classification[END_REF] have proved a classification theorem for cluster algebras with finitely many clusters (also called of finite type), in terms of Cartan matrices. We are interested in generalised cluster algebras, introduced by Shapiro and Chekhov in 2011 [START_REF] Chekhov | Teichmüller spaces of Riemann surfaces with orbifold points of arbitrary order and cluster variables[END_REF], which differ from standard cluster algebras by the form of their exchange relations. Finite type classification and combinatorial behaviour stay the same [START_REF] Chekhov | Teichmüller spaces of Riemann surfaces with orbifold points of arbitrary order and cluster variables[END_REF]. We exhibit some interesting bases of a generalised cluster algebra A n of Cartan type C n , which will be relevant in representation theory.

On the other hand, for a finite-dimensional complex Lie algebra g, let U ε (Lg) denote the quantum enveloping algebra of the loop algebra of g, where the quantum parameter ε is a root of unity in C * . In the spirit of Hernandez and Leclerc's papers [START_REF] Hernandez | Cluster algebras and quantum affine algebras[END_REF][START_REF] Hernandez | A cluster algebra approach to q-characters of Kirillov-Reshetikhin modules[END_REF], we consider a certain tensor category C ε Z of the category of finite-dimensional representations of U ε (Lg), and prove that when g = sl 2 , the Grothendieck ring of C ε Z is isomorphic to A l-1 (see Theorem 4.2), where l is the order of ε 2 . Moreover, this isomorphism maps the basis of classes of simple objects of C ε Z to the basis of (generalised) cluster monomials, multiplied by Tchebychev polynomials in the single generator of the coefficient ring. For g = sl 3 and l = 2, we prove a similar result, where A l-1 is replaced by a generalised cluster algebra of type G 2 . Extensive computations with Maple allow us to formulate a conjecture for g = sl 3 and l > 2.

2 Generalised cluster algebras

Background

We recall, following [START_REF] Chekhov | Teichmüller spaces of Riemann surfaces with orbifold points of arbitrary order and cluster variables[END_REF], the definition and the main structural properties of generalised cluster algebras (see also [START_REF] Nakanishi | Structure of seeds in generalized cluster algebras[END_REF]). For a fixed integer n ∈ N * , let B = (b ij ) ∈ M n (Z) be a skew-symmetrisable matrix, i.e. such that there exists an integer diagonal matrix D = diag( d1 . . . dn ) such that DB is skew-symmetric.

Suppose that for each index k ∈ 1, n , there is an integer d k ∈ N that divides all coefficients b jk in the k-th column. Introduce the notation

β jk := b jk d k ∈ Z. (2.1)
Let (P, •, ⊕) be a commutative semifield, called the coefficient group. For example, one can take for P the tropical semifield Trop(λ 1 , . . . , λ n ) generated by some indeterminates λ 1 , . . . , λ n . This is by definition the set of Laurent monomials in the λ i 's, with ordinary multiplication and tropical addition i

λ ai i ⊕ i λ bi i = i λ min(ai,bi) i .
Let F = ZP(t 1 , . . . , t n ) be the ambient field of rational functions in n independent variables, where ZP is the integer group ring of P. For a collection of variables p i = (p i,0 , p i,1 , . . . , p i,di ) ∈ P di+1 (i ∈ 1, n ), define the corresponding homogeneous exchange polynomial

θ i [p i ](u, v) := di r=0 p i,r u r v di-r ∈ ZP[u, v].
(2.2) Definition 2.1 A generalised seed is a triple (x, p, B) where (i) the tuple x = {x 1 , . . . , x n }, called a cluster, is a collection of algebraically independent elements of F, called cluster variables, which generate F over Frac ZP;

(ii) the matrix B = (b ij ) ∈ M n (Z), called the exchange matrix, is skew-symmetrisable;

(iii) p = (p 1 , . . . , p n ) is a coefficient tuple, where for every i ∈ 1, n , the tuples p i = (p i,0 , p i,1 , . . . , p i,di ) in P di+1 are the coefficients of the i-th exchange polynomial θ i .

The triple (x, {θ 1 , . . . , θ n }, B) is also called a generalised seed.

Definition 2.2

The generalised mutation in direction k ∈ 1, n , is the operation that transforms a generalised seed (x, p, B) into another generalised seed µ k (x, p, B) := (x , p , B ) given by (i) matrix mutation:

the matrix B = (b ij ) is defined by b ij = -b ij if i = k or j = k b ij + 1 2 (|b ik |b kj + b ik |b kj |) otherwise (2.3)
(ii) cluster mutation:

x i = x i if i = k x k x k = θ k [p k ](u + k , u - k ) (2.4)
where we define

u + k := n j=1 x [β jk ]+ j and u - k := n j=1 x [-β jk ]+ j . (2.5)
(iii) coefficient mutation:

                 p k,r = p k,d k -r p i,r p i,r-1 =          (p k,d k ) β ki p i,r p i,r-1 if i = k and b ki ≥ 0 (p k,0 ) β ki p i,r p i,r-1 if i = k and b ki ≤ 0 (2.6)
It follows easily from the definition of matrix mutation that for each k, r ∈ 1, n , the integer d k divides all coefficients in the k-th column of µ r (B). Moreover, note that µ r is an involution. We say that two generalised seeds are mutation-equivalent if one can be obtained from the other by performing a finite sequence of mutations. Definition 2.3 The generalised cluster algebra A(p, B) = A(x, {θ 1 , . . . , θ n }, B) of rank n, corresponding to the generalised seed (x, {θ 1 , . . . , θ n }, B), is the ZP-subalgebra of F generated by all cluster variables from all the seeds that are mutation-equivalent to the initial seed (x, {θ 1 , . . . , θ n }, B).

A cluster monomial in A(p, B) is a monomial in the cluster variables involving only variables belonging to a single cluster. We say that a generalised cluster algebra is of finite type if it has finitely many cluster variables. The Laurent phenomenon from [START_REF] Fomin | Cluster algebras I: Foundations[END_REF] remains true for generalised cluster algebras.

Theorem 2.4 ([4, Theorem 2.5]) Every generalised cluster variable is a Laurent polynomial in the initial cluster variables.

Generalised cluster algebras of finite type can also be classified in terms of Cartan matrices.

A generalised cluster algebra of type C n

Recall that the exchange graph of a cluster algebra is the graph whose vertices are the clusters, and two clusters are linked by an edge if they can be obtained from each other by one mutation. We know from [START_REF] Fomin | Cluster algebras II: Finite type classification[END_REF]Section 12.3] that for a cluster algebra of type C n , the exchange graph is isomorphic to the n-dimensional cyclohedron. It has a nice description in terms of triangulations of a regular (2n+2)-gon P 2n+2 . Theorem 2.5 allows us to use the same labeling system for a generalised cluster algebra of type C n . In particular, mutations can be seen as flips between triangulations of P 2n+2 . Each vertex of the exchange graph corresponds to a centrally symmetric triangulation, and two such triangulations are linked by an edge if they can be obtained from each other either by a flip involving two diameters, or by a pair of centrally symmetric flips. Note that each centrally symmetric triangulation contains a unique diameter.

Let C be the circle in which P 2n+2 is inscribed, and let Θ be the central symmetry around the center of C . Let us identify the set Σ of vertices of P 2n+2 with the cyclic group

Z/(2n + 2)Z ∼ = 2Z/(4n + 4)Z,
by labelling the vertices clockwise: 0,2,4,. . . ,2n, 2n + 2,2n + 4,. . . , 4n + 2, with the natural additive law induced by the cyclic group. We now rename half of the vertices: for each k ∈ 0, n , write

(2n + 2) + 2k := 2k.
(2.7)

In particular, 2n + 2 = 0 and 2n + 2 = 0. (2.8)

By convention, if a and b are neighbours in P 2n+2 , we set x ab = 1. Note that each cluster variable x ab may also be labelled by the set O ab .

Definition 2.6 Let P = Trop(λ). For an integer n ∈ N, n ≥ 2, we denote by A n = A(x, {θ 0 1 , . . . , θ 0 n }, B) the generalised cluster algebra defined by the initial seed: x = {x 1 , . . . , x n },

θ 0 i (u, v) = u + v (i ∈ 1, n -1 ), θ 0 n (u, v) = u 2 + λuv + v 2 , (2.9)
and

B :=             0 1 0 0 0 . . . 0 -1 0 1 0 0 . . . 0 0 -1 0 1 0 . . . 0 0 0 -1 0 . . . . . . . . . . . . . . . . . . . . . . . . 1 0 0 0 . . . 0 -1 0 2 0 0 0 . . . 0 -1 0             . ( 2

.10)

Thus A n is the Z[λ ±1 ]-subalgebra of F generated by the cluster variables. We will rather work with a variant of A n , in which the coefficient λ is not assumed to be invertible. Definition 2.7 Let A n be the Z[λ]-subalgebra of F generated by the cluster variables of A n .

As above, we label the cluster variables of A n (or A n ) by Θ-orbits of diagonals of P 2n+2 . The initial cluster variables corresponding to the initial seed are as follows (see Figure 1):

x k := x 2n,2k (k ∈ 1, n ).
(2.11) Note that the exchange polynomials θ 0 i , i < n, are not affected by mutation; they coincide with standard exchange relations. Moreover, flipping a diameter while keeping a non-crossing, centrally-symmetric triangulation of P 2n+2 , gives another diameter (it is easy to see that the quadrilaterals in which diameters are flipped, are always rectangles). This implies that there is only one variable of the form x a,ā in each cluster, and it is obtained by mutating another x b, b. We show the following explicit result in [START_REF] Gleitz | Quantum affine algebras at roots of unity and generalised cluster algebras[END_REF]. Proposition 2.8 In the generalised cluster algebra A n , the following exchange relations between variables x ab and x cd hold, up to rotation (i.e. index shifting):

1. If a = b, c = d, and the quadrilateron [acbd] is contained in one half of the circle C , we have a standard exchange relation of the form (2.13)

x 2n,2k+2 x 2d-2,2r+2 = x 2n,2r+2 x 2d-2,2k+2 + x 2n,2d-2 x 2k+2,2r+2 , (2.12
The monomials with coefficient 1 correspond to the Ptolemy rule in the second diagram of Figure 2. (2.14)

We call a pair of centrally symmetric diagonals of P 2n+2 small if the corresponding set O ab contains only one element. The attached variables x ab are also called small. We show that A n has some interesting bases. For k ∈ N, denote by S k (u) ∈ Z[u] the k-th Tchebychev polynomial of the second kind, given by

S k (u) 2 = S k-1 (u)S k+1 (u) + 1 (2.15)
with initial conditions S 0 (u) = 1 and S 1 (u) = u.

Proposition 2.9 The set S of all monomials in the small variables forms a Z-basis of A n . Equivalently, A n is the polynomial ring with coefficients in Z in the small variables. Moreover, the set

B := {S k (λ) • m, k ∈ N, m ∈ M 0 } (2.16)
is a Z-basis of A n , where M 0 is the set of cluster monomials of A n .

The basis B will be meaningful in representation theory.

Quantum loop algebras and ε-characters

Let l be an integer, l ≥ 2. Introduce the root of unity

ε :=            exp iπ l if l is even exp 2iπ l if l is odd (3.1)
Thus l is the order of ε 2 , and we have ε 2l = 1. Following [START_REF] Frenkel | The q-characters at roots of unity[END_REF], let us also write ε * := ε l 2 = 1.

Let g be a finite-dimensional complex simple Lie algebra of simply-laced type, with Dynkin diagram δ, vertex set I = 1, n and Cartan matrix C = (a ij ) i,j∈I . Denote by α i the simple roots, by i the fundamental weights and by P the weight lattice [START_REF] Bourbaki | Groupes et algèbres de Lie[END_REF].

Let q be an indeterminate; then C(q) is the field of rational functions of q with complex coefficients, and C[q, q -1 ] is the ring of complex Laurent polynomials in q.

Let U q ( g) be the quantum affine algebra associated with g [START_REF] Frenkel | The q-characters of representations of quantum affine algebras, Recent developments in quantum affine algebras and related topics[END_REF]. This is a Hopf algebra over C(q). Denote by U q (Lg) the quantum loop algebra, which is isomorphic to a quotient of U q ( g) where the central charge is mapped to 1. Therefore, U q (Lg) inherits a Hopf algebra structure.

We will be interested in finite-dimensional representations of U q ( g), on which the central charge acts trivially. It is then sufficient to consider finite-dimensional representations of U q (Lg), and we will focus on these onwards.

Let U res q (Lg) be the restricted integral form obtained from U q (Lg) [START_REF] Chari | Quantum affine algebras at roots of unity[END_REF]; it is a C[q, q -1 ]-Hopf algebra. Let us now specialise U res q (Lg) at the root of unity ε, by setting

U res ε (Lg) := U res q (Lg) ⊗ C[q,q -1 ] C (3.2) via the algebra homomorphism f ε : C[q, q -1 ] → C such that f ε (q) = ε.
Consider the category C q of finite-dimensional type 1 representations of the quantum loop algebra U q (Lg) for q an indeterminate (see [2, Section 11.2]); it is monoidal, abelian and non semisimple. An object V in C q has a q-character χ q (V ) [START_REF] Frenkel | The q-characters of representations of quantum affine algebras, Recent developments in quantum affine algebras and related topics[END_REF], which is an element of Z[Y ±1 i,a , i ∈ I, a ∈ C(q)]. The simple objects of C q are parametrised [START_REF] Frenkel | The q-characters of representations of quantum affine algebras, Recent developments in quantum affine algebras and related topics[END_REF] by the highest monomial of their q-characters, which is a dominant monomial, i.e. it contains only positive exponents. If S is a simple object of C q such that the highest monomial of χ q (S) is m, then S will be denoted by L(m) [START_REF] Leclerc | Quantum loop algebras, quiver varieties, and cluster algebras[END_REF]. For i ∈ I, k ∈ N * , a ∈ C(q), the simple object

W (i) k,a = L(Y i,a Y i,aq 2 . . . Y i,aq 2(k-1) ) (3.3)
is called a Kirillov-Reshetikhin module. In particular

W (i) 1,a = L(Y i,a
) is a fundamental module. By convention, W (i) 0,a is the trivial representation for any a, i. The following result was conjectured in [START_REF] Kuniba | Functional relations in solvable lattice models: I. Functional relations and representation theory[END_REF] and proved in [START_REF] Nakajima | t-analogs of q-characters of Kirillov-Reshetikhin modules of quantum affine algebras[END_REF] (see also [START_REF] Hernandez | The Kirillov-Reshetikhin conjecture and solutions of T-systems[END_REF]):

Theorem 3.1 ([15, 10]) The classes [W (i) k,a ] in K 0 (C q ) satisfy a system of equations called T -system: [W (i) k,a ][W (i) k,aq 2 ] = [W (i) k+1,a ][W (i) k-1,aq 2 ] + j∼i [W (j) k,aq ] (i ∈ I, k ∈ N * , a ∈ C(q)), (3.4)
where j ∼ i means that j is a neighbour of i in the Dynkin diagram δ.

Example 3.2 If g = sl 2 , the T -system reads [W (1) k,a ][W (1) k,aq 2 ] = [W (1) k+1,a ][W (1) k-1,aq 2 ] + 1 (k ∈ N * ). (3.5)
Let C ε be the category of finite-dimensional type 1 U res ε (Lg)-modules. Let K 0 (C ε ) be its Grothendieck ring. An object V in C ε has an ε-character χ ε (V ) [START_REF] Frenkel | The q-characters at roots of unity[END_REF], which is an element of Z[Y ±1 i,a , i ∈ I, a ∈ C * ]. The parametrisation of the simple objects by their highest dominant monomials also holds on C ε , with q replaced by ε (see [START_REF] Chari | Quantum affine algebras at roots of unity[END_REF][START_REF] Frenkel | The q-characters at roots of unity[END_REF]). The simple module whose highest weight monomial is m will be written L(m).

In particular, the fundamental modules of U res ε (Lg) are the simple objects L(Y i,a ), where i ∈ I, a ∈ C * , and the standard modules are the tensor products of fundamental modules. The simple module L(m) is called prime if it cannot be written as a tensor product of non-trivial modules.

The ring

K 0 (C ε ) is the ring of polynomials Z[[L(Y i,a )] i ∈ I, a ∈ C * ] (see [5, Section 3.1]).
For a simple object V of C q , with highest weight vector v, it is known [5, Proposition 2.5] that the U res q (Lg)-module

V res := U res q (Lg) • v is a free C[q, q -1 ]-module. Put V res ε = V res ⊗ C[q,q -1
] C, where as above q acts on C by multiplication by ε. This is a U res ε (Lg)-module called the specialisation of V at q = ε. Frenkel and Mukhin [START_REF] Frenkel | The q-characters at roots of unity[END_REF] prove that for a simple module V in C q , the ε-character χ ε (V res ε ) is obtained by substituting q → ε in χ q (V ). The ε-characters χ ε thus satisfy combinatorial properties similar to q-characters ([5, Section 3.2]).

Since the Dynkin diagram δ is a bipartite graph, we may choose a partition of the vertices I = I 0 I 1 , where each edge connects a vertex of I 0 with a vertex of I 1 . For i ∈ I d (d = 0, 1), set ξ i := d. For i ∈ I and a ∈ C * , introduce the following notation:

Y i,a := l-1 j=0 Y i,aε 2j+ξ i . (3.6) Note that since ε 2l = 1, we have Y i,ε 2r = Y i,1 for any r ∈ Z. A monomial in the variables Y i,a is called l-acyclic if it is not divisible by Y j,b for any j ∈ I, b ∈ C * .
Frenkel and Mukhin [START_REF] Frenkel | The q-characters at roots of unity[END_REF] describe a quantum Frobenius map Fr : U res ε (Lg) → U res ε * (Lg) that gives rise to the Frobenius pullback

Fr * : K 0 (Rep U res ε * (Lg)) -→ K 0 (C ε ), (3.7)
and prove that this is the injective ring homomorphism such that

Fr * ([L(Y i,a )]) = [L(Y i,a )].
The following theorem was proved by Chari and Pressley for roots of unity of odd order [START_REF] Chari | Quantum affine algebras at roots of unity[END_REF] and generalised by Frenkel and Mukhin [START_REF] Frenkel | The q-characters at roots of unity[END_REF] to roots of unity of arbitrary order.

L(m) ∼ = L(m 0 ) ⊗ L(m 1 ), (3.8)
using the decomposition m = m 0 m 1 , where m 1 is a monomial in the variables Y i,a , and m 0 is l-acyclic.

Note that L(m 1 ) is the Frobenius pullback of an irreducible U res ε * (Lg)-module L( m 1 ), and the ε-

character χ ε (Fr * (L( m 1 ))) is obtained from χ ε * (L( m 1 )) by replacing each Y ±1 i,a l by Y ±1 i,aε ξ i . In fact, since ε * = 1, the category Rep U res ε * (Lg)
is equivalent to Rep Lg, so ε * -characters are easy to compute. Therefore, the computation of ε-characters of simple objects of C ε is reduced, by Theorem 3.3, to understanding the ε-characters of all representations L(m 0 ) where m 0 is l-acyclic.

Let C ε Z be the full subcategory of C ε whose objects M have all their composition factors L(m) such that m contains only variables of the form Y i,ε 2k+ξ i , where i ∈ I and k ∈ Z. For example, the modules

z i := L(Y i,1 ) are objects of C ε Z . Let K 0 (C ε Z ) be the Grothendieck ring of C ε Z . This is the subring of K 0 (C ε ) generated by the classes [L(Y i,ε 2k+ξ i )], i ∈ I, k ∈ Z. 4 Cluster structure on K 0 (C ε Z ) in type A 1
Let us introduce the following notation for specialised Kirillov-Reshetikhin modules:

W ε (k, a, i) := W (i) k,a res ε (i ∈ I, k ∈ N, a ∈ C * ). (4.1)
In type A 1 , that is, for g = sl 2 , we have I = {1}, so we drop the index i in the above notation. We also drop the index i = 1 in the variables Y 1,ε n and introduce the notation

Y n := Y 1,ε n and Y 1 = Y 0 Y 2 . . . Y 2l-2 (4.2)
for any integer n. We then have Y 2l+n = Y n for every n. With this new notation, we have

W ε (k, ε 2r ) = L(Y 2r Y 2r+2 Y 2r+4 . . . Y 2(r+k-1) ) (k, r ∈ 0, l -1 ), z 1 = L(Y 1 ). (4.3)
To each module W ε (k, ε 2r ) with k < l and r ∈ 1, l , attach the diagonal [2r -2, 2r + 2k] of the 2l-gon P 2l defined in Section 2. The following result is a reformulation of a theorem of Chari and Pressley [START_REF] Chari | Quantum affine algebras at roots of unity[END_REF].

Theorem 4.1 ([3, Theorem 9.6]) For g = sl 2 , the simple objects of C ε Z are exactly the modules below:

r t=1 L(Y 2dt . . . Y 2(dt+kt-1) ) ⊗at ⊗ L(Y a 1 ) = r t=1 W ε (k t , ε 2dt ) ⊗at ⊗ L(Y a 1 ) (4.4)
where r ∈ N * , k 1 , . . . , k r ∈ 0, l -1 , d 1 , . . . , d r ∈ Z, a 1 , . . . , a r , a ∈ N, with the condition that for every t = s ∈ 1, r , the diagonals [2d t -2, 2d t + 2k t ] and [2d s -2, 2d s + 2k s ] do not cross inside P 2l .

It follows from Theorem 4.1 that the prime simple modules of U res ε (Lsl 2 ) are the modules W ε (k, ε 2d ) (k < l, r ∈ 1, l ) and the Frobenius pullbacks L(Y a 1 ) (a ∈ N * ). The modules W ε (k, ε 2r ), for k < l -1, satisfy the T -system (3.5), and the ε-characters behave like their q-character counterparts. The (l -1)-th relation is different from the T -system:

χ ε (L(Y 0 Y 2 Y 4 . . . Y 2(l-2) ))χ ε (L(Y 2 Y 4 . . . Y 2(l-1) )) = χ ε (L(Y 2 Y 4 . . . Y 2(l-2) )) • χ ε (z 1 ) + 1 + χ ε (L(Y 2 Y 4 . . . Y 2(l-2) )) 2 . ( 4.5)
We can now state our main result, proved in [START_REF] Gleitz | Quantum affine algebras at roots of unity and generalised cluster algebras[END_REF]. Recall the generalised cluster algebra A n defined in Section 2, Definition 2.7. Let R = K 0 (C ε Z ) be the Grothendieck ring of C ε Z for g = sl 2 and ε as in (3.1). Theorem 4.2 There exists a ring isomorphism ϕ :

A l-1 → R, such that ϕ(x 2r,2d ) = [L(Y 2r+2 . . . Y 2d-2 )] (r, d ∈ 0, l -1 , |r -d| < l), ϕ(λ) = [z 1 ]. (4.6)
The Z-basis S of A l-1 is mapped by ϕ to the basis of classes of standard modules in R. The Z-basis B of A l-1 consisting in generalised cluster monomials (see (2.16)) is mapped to the basis B of classes of simple modules in R.

5 Type A 2

For any integer n ∈ Z and any vertex i = 1, 2 of the Dynkin diagram, we set Y i,n := Y i,ε n , where we consider the second index modulo 4. We also write

Y 1 = Y 1,0 Y 1,2 and Y 2 = Y 2,1 Y 2,3 .
Theorem 5.1 Any simple finite-dimensional U res ε (Lsl 3 )-module L(m) can be written

L(m) = L(Y k 1 Y 2 ) ⊗ L(m 0 )
, where L(m 0 ) is one of the following eight tensor products:

(i) L(Y 1,0 ) ⊗a ⊗ L(Y 1,0 Y 2,1 ) ⊗b (ii) L(Y 2,1 ) ⊗a ⊗ L(Y 1,0 Y 2,1 ) ⊗b (iii) L(Y 1,0 ) ⊗a ⊗ L(Y 1,0 Y 2,3 ) ⊗b (iv) L(Y 2,3 ) ⊗a ⊗ L(Y 1,0 Y 2,3 ) ⊗b (v) L(Y 1,2 ) ⊗a ⊗ L(Y 1,2 Y 2,1 ) ⊗b (vi) L(Y 2,1 ) ⊗a ⊗ L(Y 1,2 Y 2,1 ) ⊗b (vii) L(Y 1,2 ) ⊗a ⊗ L(Y 1,2 Y 2,3 ) ⊗b (viii) L(Y 2,3 ) ⊗a ⊗ L(Y 1,2 Y 2,3 ) ⊗b .
This follows from Theorem 3.3 and some direct computations of ε-characters. The following identities can also be checked directly.

Proposition 5.2

The following identities hold, for i ∈ {0, 2} and j ∈ {1, 3}.

χ ε (L(Y 1,i ))χ ε (L(Y 2,j )) = χ ε (L(Y 1,i Y 2,j )) + 1 χ ε (L(Y 1,i Y 2,1 ))χ ε (L(Y 1,i Y 2,3 )) = χ ε (L(Y 1,i )) 3 + χ ε (L(Y 1,i )) 2 χ ε (L(Y 2 )) +χ ε (L(Y 1,i ))χ ε (L(Y 1 )) + 1 χ ε (L(Y 1,0 Y 2,j ))χ ε (L(Y 1,2 Y 2,j )) = χ ε (L(Y 2,j )) 3 + χ ε (L(Y 2,j )) 2 χ ε (L(Y 1 )) +χ ε (L(Y 2,j ))χ ε (L(Y 2 )) + 1. (5.1)
The Grothendieck ring R := K 0 (C ε Z ) for g = sl 3 , l = 2, is isomorphic to a polynomial ring:

R ∼ = Z[[L(Y 1,0 )], [L(Y 1,2 )], [L(Y 2,1 )], [L(Y 2,3 )]]. (5.2)
Recall that for g = sl 3 , the Grothendieck ring of the finite-dimensional representations of g is isomorphic to the polynomial ring Z[[V ( 1 )], [V ( 2 )]]. In this case, the simple modules are of the form V (a 1 1 + a 2 2 ) with (a 1 , a 2 ∈ N). They are mapped by the Frobenius pullback to polynomials S a1,a2 ([L(Y 1 )], [L(Y 2 )]) that can be computed inductively using the Littlewood-Richardson rule.

Let G be the generalised cluster algebra of type G 2 , with P = Trop(λ 1 , λ 2 ), initial cluster {x 1 , x 2 }, exchange matrix

B = 0 3 -1 0 , and initial exchange polynomials θ 0 1 (u, v) = u + v, θ 0 2 (u, v) = u 3 + λ 1 u 2 v + λ 2 uv 2 + v 3 .
There are eight cluster variables x 1 , . . . , x 8 , organised as in Figure 3.

Let G be the Z[λ 1 , λ 2 ]-subalgebra of the ambient field F generated by the cluster variables of G. As for A n , one can also check that G is isomorphic to a polynomial ring: (5.5)

G ∼ = Z[x 1 , x 3 , x 5 , x 7 ]. ( 5
The Z-basis E ⊂ G of monomials in x 1 , x 3 , x 5 , x 7 is mapped by η to the basis of classes of standard modules in R. Moreover, the Z-basis H of generalised cluster monomials of G is mapped to the basis B of classes of simple modules in R.

Our various computations have led us to the following conjecture.

Conjecture 5.4 For l ≥ 2, the Grothendieck ring of C ε Z , is isomorphic to a generalised cluster algebra G l of rank 2l -2. An initial seed of G l is given by the exchange matrix

                      0

Theorem 2 . 5 ([ 4 ,

 254 Theorem 2.7]) Generalised cluster algebras of finite type follow the same Cartan-Killing classification as standard cluster algebras.

  Consider a pair {[a, b], [ā, b]} of centrally symmetric diagonals. We may choose [a, b] to represent the Θ-orbit of this pair. The segment [a, b] divides the circle C into two arcs. The Θ-orbits of the vertices of P 2n+2 that lie on the smallest arc form a set denoted by O ab . For example, if a < b ∈ 0, 2n , the set O ab consists of the Θ-orbits of a + 2, a + 4,. . . , b -2. In general, we have O ab = O ba = O āb = Ob ā. We label cluster variables by the corresponding Θ-orbits of diagonals. Namely, if b = a, the variable x ab corresponds to the pair of diagonals {[a, b], [ā, b]}. If b = a, the variable x aa corresponds to the diameter {[a, a]}. Thus we have x ab = x ba = x āb = xb ā.

Figure 1 :

 1 Figure 1: The initial cluster of An

  ) which corresponds to the Ptolemy rule in the first diagram of Figure 2. 2. if a = b and c = d, we have a generalised exchange relation of the form x 2n,2n x 2k,2k = x 2 2n,2k + x 2 2k,2n + λx 2n,2k x 2n,2k .

Figure 2 :

 2 Figure 2: Generalised exchange relations for An We also have the following useful identity for multiplying a diagonal by a diameter: if a = b and c = d, relations are of the form x 2n,2k x 2d,2d = λx 2n,2d x 2d,2k + x 2n,2d x 2k,2d + x 2d,2k x 2d,2n .(2.14)

Theorem 3 . 3 ([ 5 ,

 335 Theorem 5.4]) Let L(m) be a simple object of C ε . Then

. 3 )(x 5 , x 4 )Figure 3 :Theorem 5 . 3

 354353 Figure 3: The clusters in type G2 Theorem 5.3 For l = 2 and g = sl 3 , there exists a ring isomorphism η: G → R such that η(x 1 ) = [L(Y 1,0 )] η(x 2 ) = [L(Y 1,0 Y 2,3 )] η(x 3 ) = [L(Y 2,3 )] η(x 4 ) = [L(Y 1,2 Y 2,3 )] η(x 5 ) = [L(Y 1,2 )] η(x 6 ) = [L(Y 1,2 Y 2,1 )] η(x 7 ) = [L(Y 2,1 )] η(x 8 ) = [L(Y 1,0 Y 2,1 )] η(λ 1 ) = [L(Y 1 )] η(λ 2 ) = [L(Y 2 )]

6 )

 6 the cluster variables correspond tox 2k+1 = [L(Y 1,0 Y 1,2l-2 . . . Y 1,2l-2k )] (k ∈ 0, l -2 ), x 2k = [L(Y 2,2l-1 Y 2,2l-3 . . . Y 2,2l-2k+1 )] (k ∈ 1, l -2 ), x 2l-2 = [L(Y 1,0 Y 1,2l-2 Y 1,2l-4 . . . Y 1,4 Y 2,2l-1 Y 2,2l-3 Y 2,2l-5 . . . Y 2,5 Y 2,3 )].The coefficients are λi = [L(Y i )], i = 1, 2, where Y 1 = Y 1,0 Y 1,2 . . . Y 1,2l-2 and Y 2 = Y 2,1 Y 2,3 . . . Y 2,2l-1 .

The initial exchange polynomials are

Moreover, the generalised cluster monomials are mapped to classes of simple modules.

Remark 5.5 For l > 2, the above generalised cluster algebras are of infinite type, so we only hope for an inclusion of the cluster monomials in the set of classes of simple modules L(m) where m is l-acyclic.