Emily Gunawan
email: egunawan@umn.edu.

Gregg Musiker
email: musiker@umn.edu.

Atomic Bases and T -path Formula for Cluster Algebras of Type D

Keywords: cluster algebra, triangulated surface, atomic basis

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Cluster algebras, introduced by Fomin and Zelevinsky [START_REF] Fomin | Cluster algebras I: Foundations[END_REF] in 2000, are commutative algebras equipped with a distinguished set of generators, called cluster variables, which can be constructed recursively starting from an initial set of n cluster variables. We are interested in cluster algebras arising from bordered surfaces with marked points [START_REF] Fock | Moduli spaces of local systems and higher Teichmüller theory[END_REF][START_REF] Fock | Cluster ensembles, quantization and the dilogarithm[END_REF][START_REF] Michael Gekhtman | Cluster algebras and Weil-Petersson forms[END_REF][START_REF] Fomin | Cluster algebras and triangulated surfaces. I. Cluster complexes[END_REF]. In particular, we study cluster algebras of type D n (type D for short), which are of finite type (as classified in [START_REF] Fomin | Cluster algebras II: Finite type classification[END_REF]) and correspond to oncepunctured n-gons, as also described in detail in [START_REF] Schiffler | A geometric model for cluster categories of type D n[END_REF]. Other, related work on type D cluster algebra combinatorial models include [START_REF] Fomin | Cluster algebras II: Finite type classification[END_REF][START_REF] Baur | Frieze patterns for punctured discs[END_REF][START_REF] Ceballos | Cluster algebras of type D: Pseudotriangulations approach[END_REF].

Our first result is a Laurent polynomial expansion formula for cluster variables arising from a oncepunctured polygon in terms of certain paths (called T o -paths) on an ideal triangulation T o of the surface. This is an extension of the T -path formula which is given for any unpunctured surface by Schiffler and Thomas [START_REF] Schiffler | On cluster algebras arising from unpunctured surfaces[END_REF][START_REF] Schiffler | On cluster algebras arising from unpunctured surfaces II[END_REF]. Our proof takes advantage of two facts proven by the second author, Schiffler, and Williams: (1) a Laurent polynomial expansion formula for cluster variables arising from any surface in terms of perfect matchings of a snake graph [START_REF] Musiker | Positivity for cluster algebras from surfaces[END_REF], and (2) a bijection between these perfect matchings and T -paths arising from any unpunctured surface [START_REF] Musiker | Cluster expansion formulas and perfect matchings[END_REF]. The motivation behind having a T o -path formula for type D is discussed in the next paragraph.

Our second result is a specific case of a result of [START_REF] Cerulli | Positivity in skew-symmetric cluster algebras of finite type[END_REF][START_REF] Cerulli | Quivers with potentials associated to triangulated surfaces, Part III: tagged triangulations and cluster monomials[END_REF], proven by representation theoretic methods, that the basis consisting of all cluster monomials is in fact the atomic basis for any skewsymmetric cluster algebra of finite type (see Section 4.1). We give a combinatorial proof of this fact for coefficient-free cluster algebras of type D. Our proof relies heavily on the T o -path formula for type D and is inspired by Dupont and Thomas' work in [START_REF] Dupont | Atomic bases of cluster algebras of types A and[END_REF] on atomic bases for cluster algebras of type A and A.

In Section 2, we provide background material on ideal triangulations and tagged triangulations, focusing on the case of once-punctured polygons. Section 3 presents our first result (Theorem 3.11), an extension of the T -path formula of [START_REF] Schiffler | On cluster algebras arising from unpunctured surfaces II[END_REF][START_REF] Schiffler | On cluster algebras arising from unpunctured surfaces[END_REF] to once-punctured polygons. Finally, in Section 4, we give our second and main result (Lemma 4.5), which is a combinatorial proof, using the T -path formula, that the cluster monomials form the atomic basis for any type D cluster algebra. The proofs of both results are available in [START_REF] Gunawan | T-path formula and atomic bases for cluster algebras of type D[END_REF].

2 Background: Cluster algebras arising from once-punctured disks For the reader's convenience, we begin by reviewing terminology arising in the theory of cluster algebras from marked surfaces from [FST08, Sections 2 and 7]. We restrict our attention to the case of a oncepunctured polygon, which often simplifies the notation. Let C n denote a once-punctured n-gon, i.e. a disk with a marked point (called the puncture) in the interior and n marked points on the boundary. Definition 2.1 (Ordinary arcs) A boundary edge of C n is a segment of the boundary between two consecutive boundary marked points. An ordinary arc γ of C n is a curve (considered up to isotopy) in C n such that the endpoints of γ are marked points, γ does not cross itself except possibly at its endpoints, γ does not cross the boundary of C n except possibly at its endpoints, and γ is not contractible to a marked point or homotopic to a boundary edge.

A radius is an arc between a boundary marked point and the puncture. Following [START_REF] Dupont | Atomic bases of cluster algebras of types A and[END_REF], a peripheral arc is an arc with both endpoints on the boundary. An -loop is a loop cutting out a once-punctured monogon with a sole puncture inside it. An -loop is considered a peripheral, ordinary arc. Definition 2.2 (Compatibility of ordinary arcs, ideal triangulations) Two distinct ordinary arcs are said to be compatible if they do not intersect except possibly at endpoints. Also, each arc is compatible with itself. A maximal (by inclusion) collection of distinct, pairwise compatible ordinary arcs is called an ideal triangulation. The ordinary arcs of an ideal triangulation cut the surface into ideal triangles. We call an -loop and the radius it encloses a self-folded triangle.

Definition 2.3 (Tagged arcs) A tagged arc of C n is obtained by marking ("tagging") each endpoint of an ordinary arc (that is not an -loop) β either plain or notched such that the endpoints of β on the boundary must be tagged plain. A notched tagging is indicated by a bow tie (see Figure 1(a)). Note that a tagged arc never cuts out a once-punctured monogon, i.e. an -loop is not a tagged arc.

Definition 2.4 (Compatibility of tagged arcs, tagged triangulations of C n ) The following is a complete list of possible compatible pairs {α, β} of tagged arcs of C n . Note that every endpoint on the boundary must be tagged plain.

• α and β are two peripheral arcs that do not intersect in the interior of C n .

• α and β are a peripheral arc and a radius that do not intersect in the interior of C n .

• α and β are two radii both adjacent to the same boundary marked point (tagged plain) but α is tagged plain at the puncture and β is tagged notched at the puncture.

• α and β are two radii with distinct boundary endpoints (tagged plain at boundary endpoints) and tagged the same way at the puncture.

• α and β are equal.

A maximal (by inclusion) collection of distinct, pairwise compatible tagged arcs is called a tagged triangulation. A collection of pairwise compatible tagged arcs (considered with multiplicity) is called a multi-tagged triangulation. Definition 2.5 (Representing ordinary arcs as tagged arcs) Any ordinary arc β can be represented by a tagged arc ι(β) as follows. Suppose β is an -loop (based at marked point v) which encloses a radius r, where r is the unique (ordinary) arc connecting v and the puncture P . Then ι(β) is obtained by tagging r plain at v and notched at P . Otherwise, ι(β) is simply β with both endpoints tagged plain. See Figure 1(a).

Theorem 2.6 ([FST08, Theorem 7.11, Example 6.7]) Let T be a tagged triangulation of C n and let A be the cluster algebra associated to T . Then the tagged triangulations of C n are in bijection with the unlabeled seeds of A, and the tagged arcs γ of C n are in bijection with the cluster variables x γ , and so a multi-tagged triangulation Γ corresponds to a cluster monomial x Γ (see Definition 4.1).

Notation 2.7 If γ is a tagged arc, let γ (p) denote the arc obtained from γ by changing the notching at the puncture P . If T is a tagged triangulation, let T (p) denote the tagged triangulation that is obtained from T by replacing each γ ∈ T by γ (p) .

If is an -loop enclosing a radius r, denote

x := x r x r (p) . If β is a boundary edge, set x β := 1.

(T o , γ)-path expansion formula

We extend Schiffler and Thomas' work [START_REF] Schiffler | On cluster algebras arising from unpunctured surfaces II[END_REF][START_REF] Schiffler | On cluster algebras arising from unpunctured surfaces[END_REF] to cover ordinary arcs in a once-punctured disk C n . Following [Sch10, Section 3], we will use the following setup throughout the rest of the paper.

• Let S be an unpunctured surface or S = C n . Let T o be an ideal triangulation of S and let γ / ∈ T o be an ordinary arc of S. Recall that an -loop is considered an ordinary arc.

• Choose an orientation on γ, and let s and t be the starting point and the finishing point of γ. Denote by s = p 0 , p 1 , p 2 , . . . , p d+1 = t the points of intersection of γ and T o in order. Since γ is considered up to homotopy, we pick a representative so that d is minimal. Let i 1 , i 2 , . . . , i d be such that τ i k is the arc of T o containing p k . See Figure 2(a) where τ i k (k = 1, . . . , 5) are labeled 1, 2, , r and .

• For k = 0, 1, . . . , d, let γ k denote the segment of γ between the points p k and p k+1 , and let k denote the (unique) ideal triangle of T o that γ k crosses.

• For k = 1, . . . , d -1, define arc τ [γ k ] to be τ [γ k ] = the 3rd arc in k if k is not self-folded, the radius in k if k is self-folded.
Denote the side of 0 that lies clockwise of τ i1 by τ

[γ d+1 ] . If 0 (respectively, d ) is self-folded, then τ [γ0] = τ [γ-1] (respectively, τ [γ d ] = τ [γ d+1 ]
) is the radius. In Figure 2(a),

τ [γ0] = b 1 , τ [γ-1] = b 4 , τ [γ d ] = 2, τ [γ d+1 ] = b 3 .
Definition 3.1 (Quasi-arc) If τ is an ordinary radius of C n between a marked point v on the boundary and the puncture P , let an associated quasi-arc τ be a curve (not passing through P ) which satisfies the following:

1. τ is between v and a (non-marked) point P in the vicinity of P . (Note that another quasi-arc associated to τ incident to P may use a different point P .)

2. τ agrees with the arc τ outside of a radius-ball around P .

If τ is a peripheral arc, we let the associated quasi-arc be τ itself. We label a quasi-arc with the label of the arc that it is associated to.

Definition 3.2 (Extension of complete (T o , γ)-path from [Sch10, Definition 2], [MS10, Section 4.1]) A T o -path w = (w 1 , w 2 , . . . , w length(w)
) is a concatenation of steps, oriented quasi-arcs and boundary edges of the ideal triangulation T o of S, such that the starting point of a step w i is the finishing point of the previous step w i-1 . We say that w is a complete (T o , γ)-path if the following axioms hold: It is clear that this definition agrees with the complete T -paths of [START_REF] Schiffler | On cluster algebras arising from unpunctured surfaces II[END_REF][START_REF] Musiker | Cluster expansion formulas and perfect matchings[END_REF] for unpunctured surfaces. For short, we will refer to a complete (T o , γ)-path as simply a (T o , γ)-path (or a T o -path) for the rest of this paper. By abuse of notation, whenever we say we are going along an arc or a side of an ideal triangle k (as part of a T o -path), we mean traversing an associated quasi-arc. Note that except for the case when τ is a radius, no abuse of notation is actually needed.

Remark 3.3 We collect the following observations regarding conditions (T1) and (T2).

• By (T1), the length (w) of w is always 2d + 1, where d is the number of times that γ intersects T o .

• It is possible to have w k = w k+1 and, if k is odd, to have w k = w k+1 = w k+2 . However, since w 2k = τ i k and w 2(k+1) = τ i k+1 by (T1) but τ i k = τ i k+1 , no more than three consecutive steps can coincide.

• The homotopy condition of (T2) requires each w 2k+1 (k = 0, . . . , d) to traverse a side of the ideal triangle k .

Definition 3.4 (Laurent monomial from a T o -path) We identify each step with the label of the quasiarc/boundary edge which it traverses and define the Laurent monomial x(w) corresponding to a complete (T o , γ)-path w by x(w) = i odd

x wi i even

x -1 wi Remark 3.5 Two or more (T o , γ)-paths may correspond to the same Laurent monomial, e.g. see Example 3.12. For each (T o , γ)-path w, the denominator of x(w), before reducing, is equal to x i1 , x i2 , . . . , x i d which corresponds to the arcs τ i1 , . . . , τ i d of T o which cross γ.

Definition 3.6 (Backtrack, non-backtrack cycle) Let w be a T o -path, let τ be an arc of T o , and let (w k , w k+1 ) be a pair of consecutive steps going along τ .

• If τ is a peripheral arc, we say that (w k , w k+1 ) is a backtrack if it is contractible (equivalently, if w k and w k+1 are opposite orientations of τ ).

• If τ is a radius between the puncture P and a marked point v on the boundary, then we say that (w k , w k+1 ) is a backtrack if one of the following holds:

1. w k ends at v, so that (w k , w k+1 ) is a (non-cyclic) concatenation of two associated quasi-arcs P ; v ; P where P and P are in the vicinity of the puncture (Figure 5(a)).

τ [γ3] = ṙ τ i4 = r τ [γ4] = r b 3 2 τ [γ6] = b 3 τ [γ5] = 2 τ [γ-1] = b 4 τ [γ0] = b 1 τ [γ1] = b 2
(c) (b 1 , 1, 2, r, r, , b 3 ) 1 2 r b 3 b 4 b 1 b 2 (d) (b 1 , 1, 2, , r, r, b 3 ) ṙ r r b 3 2 b 3 2 b 4 b 1 b 2 1 (e) (b 4 , 1, b 2 , r, r, , b 3 ) ṙ r r b 3 2 b 3 2 b 4 b 1 b 2 1 (f) (b 4 , 1, b 2 , , ṙ, r, b 3 ) ṙ r r b 3 2 b 3 2 b 4 b 1 b 2 1 (g) (b 1 , 1, 2, r, r, , b 3 ) ṙ r r b 3 2 b 3 2 b 4 b 1 b 2 1 (h) (b 1 , 1, 2, , ṙ, r, b 3 )
Fig. 3: The four (T o , γ)-paths (and their lifts) which contain a (counterclockwise) non-backtrack r, r. All backtracks have been omitted, and steps are not drawn exactly along the arcs/boundary edges for illustration purposes. • Otherwise, (w k , w k+1 ) is homotopic to a non-contractible loop starting and ending at at a marked point v on the boundary, and we say that (w k , w k+1 ) is a non-backtrack cycle.

• Two special non-backtrack cycles are as follows. Let τ be a radius and let (w k , w k+1 ) start at the boundary and goes around the puncture exactly once. We say that (w k , w k+1 ) is a counterclockwise non-backtrack if it goes counterclockwise (Figure 5 We say that γ crosses the radius of a self-folded triangle in the counterclockwise direction (respectively, clockwise direction) if it matches (respectively, if γ has the opposite orientation of) Figure 2(a).

Lemma 3.8 Let T o be an ideal triangulation and let w be a (T o , γ)-path containing a non-backtrack cycle (w k , w k+1 ). Then (w k , w k+1 ) must go along associated quasi-arcs of the radius r of a self-folded triangle (and hence, T o contains a self-folded triangle, and γ crosses r). Furthermore, the orientation of γ as it crosses r determines whether (w k , w k+1 ) is a clockwise or counterclockwise non-backtrack.

Proposition 3.9 A (T o , γ)-path w is uniquely determined by its sequence of labels w 1 , . . . , w 2d+1 , forgetting the orientations of the steps and whether a consecutive pair is a non-backtrack or a backtrack.

Remark 3.10 To illustrate Proposition 3.9, consider the (T o , γ)-path of Figure 3(a) ,,r,r,,b 3 ).

w = (b 4 , 1, b 2 , 2, 2,
The pair (w 8 , w 9 ) = (r, r) is a counterclockwise non-backtrack along the radius r, and w 10 goes clockwise around . Consider a different path w (see Figure 4) which goes along the same sequence of arcs such that (w 8 , w 9 ) is a clockwise non-backtrack along the radius, and w 10 goes counterclockwise around . Even though w is homotopic to γ, the segment γ 4 is not homotopic to [p 4 , p 5 ] w , which violates Definition 3.2 (T2).

Theorem 3.11 (T o -path formula for C n , an extension of [Sch10, Theorem 3.1], [ST09, Theorem 3.2]) Let T o be an ideal triangulation of C n , let γ / ∈ T o be an ordinary arc of C n , and let x γ denote the corresponding element in the cluster algebra which arises from C n . Then

x γ = w x(w)
where the sum is taken over all (T o , γ)-paths. The formula does not depend on the choice of orientation on γ.

Example 3.12 The nine (T o , γ)-paths from Figure 2(a) are as follows (with the backtracks underlined): ,,r,r,,,b 3 ) ,r,r,,,b 3 )

(1.) (b 4 , 1, b 2 , 2, b 3 , , r, r, , , b 3 ) (2.) (b 4 , 1, 1, 2,
(3.) (b 1 , 1, 2, 2, 2, , , r, r, , 2) (4.) (b 1 , 1, 2, 2, b 3 , , r, r, , , b 3 ) (5.) (b 4 , 1, b 2 , 2, 2, , , r, r, , 2) (6.) (b 4 , 1, b 2 , 2, 2, , , r, r, , b 3 ) (7.) (b 4 , 1, b 2 , 2, 2, , r, r, , , b 3 ) (8.) (b 1 , 1, 2, 2, 2, , , r, r, , b 3 ) (9.) (b 1 , 1, 2, 2, 2,
The last four of these (T o , γ)-paths contain a (counterclockwise) non-backtrack (r, r) and are illustrated in Figure 3. They are drawn so that the backtracks are ignored.

We apply Theorem 3.11 and replace each (x r x )/(x x r x ) with 1/x and each x with x r x r (p) to get

x γ =(x b4 x b2 x b3 x b3 + x b4 x 1 x r x r (p) x b3 + x b1 x 3 2 + x b1 x 2 b3 x 2 + x b4 x b2 x 2 2 + 2 x b4 x b2 x b3 x 2 + 2 x b1 x b3 x 2 2 ) /(x 1 x 2 x r x r (p) )
where x bj = 1 for each boundary edge b j .

Proof of Theorem 3.11 (sketch): For full details, see [START_REF] Gunawan | T-path formula and atomic bases for cluster algebras of type D[END_REF]. Let S γ be the union of the ideal triangles k (k = 0, . . . , d) crossed by γ. Following [MSW11, Section 7], we construct a triangulated (d + 3)-gon S γ that is modeled after S γ so that the internal edges τ i1 , τ i2 , . . . , τ i d of S γ have the same labels as τ i1 , τ i2 , . . ., τ i d , and the boundary edges τ

[γ-1] , τ [γ0] , τ [γ1] , τ [γ2] , . . ., τ [γ d-1 ] , τ [γ d ] , τ [γ d+1 ] of S γ correspond to arcs or boundary edges τ [γ-1] , τ [γ0] , τ [γ1] , τ [γ2] , . . ., τ [γ d-1 ] , τ [γ d ] , τ [γ d+1
] belonging to S γ . Every triangle k in S γ corresponds to an ideal triangle in T o , and their orientations agree. When k is a self-folded triangle with radius r and -loop , its lift k is formed by two lifts of r and a lift of . We construct the lift γ of γ in a similar way. Figure 2(b) illustrates the lift γ of γ on the lift S γ of S γ of Figure 2(a).

Step 1: We prove that the covering map π : S γ → S γ induces a bijection π : { ( S γ , γ)-paths on S γ } → { (T o , γ)-paths on S γ } π( w 1 , w 2 , . . . , w 2d+1 ) = (π( w 1 ), π( w 2 ), . . . , π( w 2d+1 )).

We observe that a pair ( w k , w k+1 ) from a ( S γ , γ)-path w goes along the same edge on S γ if and only if their image (w k , w k+1 ) is a backtrack. For example, in Figure 3, every pair ( ṙ, r) or (r, r) on S γ corresponds to a (counterclockwise) non-backtrack (r, r) on C n .

Step 2: [MS10, Lemma 4.5] gives a bijection F from the perfect matchings of the snake graph G T o ,γ onto the ( S γ , γ)-paths on S γ . Certain diagonals in G T o ,γ correspond to the arcs τ i k crossed by γ, and these correspond to the even steps of each ( S γ , γ)-path. For each matching E of G T o ,γ , the matched edges correspond to the odd steps of the ( S γ , γ)-path F (E).

Step 3: The bijections π and F compose to form a bijection between (T o , γ)-paths on C n and perfect matchings of the snake graph G T o ,γ .

Step 4: Per [MSW11, Theorem 4.10], the T o -Laurent expansion of x γ is given by

x γ = E x(E) cross(T o , γ)
where the sum is over all perfect matchings E of G T o ,γ and cross(T o , γ) = Recall that, in the case that A arises from a surface, a cluster corresponds to a tagged triangulation and a cluster monomial corresponds to a multi-tagged triangulation. See Definition 2.4 for a list of compatible pairs of tagged arcs of C n .

The concepts of positive elements and atomic bases were first introduced in [START_REF] Sherman | Positivity and canonical bases in rank 2 cluster algebras of finite and affine types[END_REF] for the case of an annulus with one marked point on each boundary. Definition 4.2 (Positive elements and atomic bases) An element y ∈ A is called positive if the Laurent expansion of y in the variables of every cluster of A has non-negative coefficients.

A Z-linear basis B of A is called an atomic basis of A if any positive element of A is a non-negative Z-linear combination of B. Note that, if such a B exists, B is the collection of all indecomposable positive elements (i.e. elements which cannot be written as a sum of positive elements) of A, hence it is unique. Proof: [HL10, Nak11], [START_REF] Caldero | From triangulated categories to cluster algebras[END_REF], and [START_REF] Cerulli | Positivity in skew-symmetric cluster algebras of finite type[END_REF][START_REF] Cerulli | Quivers with potentials associated to triangulated surfaces, Part III: tagged triangulations and cluster monomials[END_REF] give representation theoretic proofs for (4.1), (4.2), and (4.3), respectively. [START_REF] Musiker | Positivity for cluster algebras from surfaces[END_REF] and [START_REF] Musiker | Bases for cluster algebras from surfaces[END_REF] provide combinatorial arguments for (4.1) and (4.2), respectively, and [START_REF] Dupont | Atomic bases of cluster algebras of types A and[END_REF] gives a combinatorial proof for the type A for (4.3). We present in [START_REF] Gunawan | T-path formula and atomic bases for cluster algebras of type D[END_REF] a combinatorial proof of (4.3) which relies on the T o -path formula (Theorem 3.11) and is inspired by [START_REF] Dupont | Atomic bases of cluster algebras of types A and[END_REF]. 2

Recall that a proper Laurent monomial in variables u i is a product of the form u c1 1 • • • u cr r where at least one of the c i is negative. Note that, by the same logic used in [SZ04, CL12, DT13], if A is a cluster algebra of type D and B is the set of cluster monomials and if (4.1) and (4.2) are assumed, then (4.3) is a direct consequence of the following. Lemma 4.5 Consider a once-punctured polygon C n . For every tagged triangulation T and every multitagged triangulation Σ which is not compatible with T , the T -expansion of x Σ is a sum of proper Laurent monomials.

Remark 4.6 A general version of Lemma 4.5 is known as the proper Laurent monomial property (following [START_REF] Cerulli | Quivers with potentials associated to triangulated surfaces, Part III: tagged triangulations and cluster monomials[END_REF]) which was proven for cluster algebras from surfaces in [START_REF] Cerulli | Quivers with potentials associated to triangulated surfaces, Part III: tagged triangulations and cluster monomials[END_REF] and then for any skewsymmetric cluster algebras in [START_REF] Cerulli Irelli | Linear independence of cluster monomials for skew-symmetric cluster algebras[END_REF], using representation theoretic arguments in both cases.

Proof (sketch): Suppose x Σ is a cluster monomial not compatible with a tagged triangulation T , i.e. Σ contains an arc σ which is not in T . For brevity, suppose that all tagged arcs of Σ\T are peripheral and the corresponding ideal triangulation T o has no self-folded triangle. For full details and the rest of the cases, see [START_REF] Gunawan | T-path formula and atomic bases for cluster algebras of type D[END_REF].

Step 1: We choose a tagged arc σ ∈ Σ\T such that σ is as close as possible to the puncture and, if possible, σ only crosses every arc of T at most once. Let (T, σ)-cross (respectively, (T, σ)-doublecross) be the set of arcs of T which σ crosses (respectively, the set of arcs of T which σ crosses twice).

Step 2: For each (T, σ)-path w, we compare the number of odd steps (contributing to the numerator of x(w)) and the number of even steps (contributing to the denominator of x(w)) that belong to (T, σ)-cross and (T, σ)-doublecross. This allows us to show that each term in the T -expansion of x σ is of negative degree either with respect to the cluster variables corresponding to (T, σ)-cross or with respect to the cluster variables corresponding to (T, σ)-doublecross.

Step 3: Similarly, for each factor x β in the product of x Σ , we consider a (T, β)-path and compare the number of odd steps versus the number of even steps to show that every term in the T -expansion of x β has non-positive degree with respect to both the cluster variables corresponding to (T, σ)-cross and the cluster variables corresponding to (T, σ)-doublecross.

Step 4: It follows, since σ ∈ Σ and every term in the T -expansion of x Σ has non-positive degree with respect to both (T, σ)-cross and (T, σ)-doublecross, that every term in the T -expansion of x Σ has negative degree with respect to either (T, σ)-cross or (T, σ)-doublecross.

Further directions

It is not known for a general cluster algebra whether its set of indecomposable positive elements forms an atomic basis. Examples of cluster algebras where this fails to happen are those of rank 2 where the exchange matrix looks like 0 b -c 0 with bc ≥ 5 [START_REF] Lee | Positivity and tameness in rank 2 cluster algebras[END_REF].

Per [MSW13, Conjecture 1.5], we are exploring the existence of atomic bases for type D n-1 cluster algebras (which arise from (n -3)-gons with 2 punctures). Toward this goal, we would like to extend the T o -path expansion formula to general bordered surfaces with more than 1 puncture. Additionally, the T opath formula presented in this paper was only done for ordinary arcs in the setting of ideal triangulations. It would be desirable to prove a similar formula for tagged arcs in the setting of tagged triangulations.

  An ideal triangulation T o and the corresponding tagged triangulation T = ι(T o ). P (b) Wheel-like triangulation around the puncture.

  A self-folded triangle around the puncture where a, b are peripheral arcs or boundary edges.

Fig. 1 :

 1 Fig. 1: Ideal triangulations of a once-punctured polygon.

Remark 2. 8

 8 Due to [MSW11, Proposition 3.15], it is enough to work with only two types of tagged triangulations T: one where T has all plain-tagged radii (so that T o has a local wheel-like triangulation as in Figure1(b)), and one where T has two parallel radii, one tagged plain and the other tagged notched at the puncture (so that T o has a self-folded triangle as in Figure1(c)).

  [γ0] and the other side by τ [γ-1] . Similarly, denote the side of d that lies clockwise of τ i d by τ [γ d ] and the other side by τ

(

  T1) Each even step w 2k (k = 1, . . . , d) is a quasi-arc associated to arc τ i k . Recall that τ i1 , . . . , τ i d is the sequence of arcs crossed by γ in order. (T2) For k = 1, 2, . . . , d -1, let [p k , p k+1 ] w denote the segment of w starting at the point p k following w 2k , continuing along w 2k+1 and w 2(k+1) until the point p k+1 . Then the segment γ k is homotopic to [p k , p k+1 ] w . If S = C n , then we mean homotopy in the disk minus the puncture. In addition, -The segment γ 0 is homotopic to the segment [s, p 1 ] w of the path starting at the point s = p 0 following w 1 and w 2 until the point p 1 ; -The segment γ d is homotopic to the segment [p d , t] w of the path starting at the point p d following w 2d and w 2d+1 until the point p d+1 = t;

  Arc γ of C 4 where d = 5.

  Lifted arc γ on the constructed triangulated (5 + 3)-gon Sγ .

Fig. 2 :

 2 Fig. 2: The construction of the triangulated polygon Sγ and lifted arc γ for an arc γ of Cn.

Fig. 4 :

 4 Fig. 4: A non-(T o , γ)-path (and its lift on Sγ) that goes along the same arcs as the (T o , γ)-path of Figure 3(a).

  2. (w k , w k+1 ) is a contractible concatenation of two associated quasi-arcs v ; P ; v where P is in the vicinity of the puncture (Figure5(b)).

  (c)), and a clockwise non-backtrack if it goes clockwise (Figure 5(d)).

Fig. 5 :

 5 Fig. 5: The four possibilities of a pair (w k , w k+1 ) of consecutive steps along a radius τ . Note that Figure 5 illustrates all four possibilities for a pair (w k , w k+1 ) along a radius. Definition 3.7

  Combinatorial proof of atomic bases for type D Definition 4.1 (Cluster monomials) Let A be a skew-symmetric cluster algebra. A cluster monomial is a monomial in cluster variables all belonging to a single cluster.

Remark 4. 3

 3 To prove that a collection B ⊂ A is an atomic basis of A, it suffices to verify the following:Every element of B is a positive element of A. (4.1) B is a Z-linear basis of A.(4.2) Every positive element y ∈ A can be written as a Z ≥0 -linear combination of B. (4.3) Theorem 4.4 ([Cer11]) If A is a cluster algebra of type A, D, or E, the cluster monomials of A form the atomic basis of A.

Acknowledgements

The authors would like to thank Pasha Pylyavskyy, Vic Reiner, and Peter Webb for looking over an early version of this paper, Hugh Thomas for helpful discussions, and the referees for many useful comments. The authors were supported by NSF Grants DMS-1067183 and DMS-1148634. This paper is an abridged version of [GM14].

Supported by NSF Grants DMS-1067183 and DMS-1148634. Supported by NSF Grants DMS-1067183 and DMS-1148634. 1365-8050


Woong Kook
email: woongkook@snu.ac.kr

Kang-Ju Lee

Weighted Tree-Numbers of Matroid Complexes

Keywords: matroid complex, weighted combinatorial Laplacians, weighted tree-numbers

We give a new formula for the weighted high-dimensional tree-numbers of matroid complexes. This formula is derived from our result that the spectra of the weighted combinatorial Laplacians of matroid complexes consist of polynomials in the weights. In the formula, Crapo's β-invariant appears as the key factor relating weighted combinatorial Laplacians and weighted tree-numbers for matroid complexes.

Résumé. Nous présentons une nouvelle formule pour les nombres d'arbres pondérés de grande dimension des matroïdes complexes. Cette formule est dérivée du résultat que le spectre des Laplaciens combinatoires pondérés des matroïdes complexes sont des polynômes à plusieurs variables. Dans la formule, le β-invariant de Crapo apparaît comme étant le facteur clé reliant les Laplaciens combinatoires pondérés et les nombres d'arbres pondérés des matroïdes complexes.

Introduction

The purpose of this paper is to give a new formula for the weighted tree-numbers of matroid complexes. As a high-dimensional analogue of Cayley-Prüfer theorem [START_REF] Moon | Counting labelled trees[END_REF], Kalai [19] found the formula for the weighted tree-numbers of standard simplexes. Continuing his study, Adin [START_REF] Adin | Counting colorful multi-dimensional trees[END_REF] presented a formula for the tree-numbers of complete colorful complexes and posed the problem of finding their weighted treenumbers. Duval, Klivans, and Martin [START_REF] Duval | Simplicial matrix-tree theorems[END_REF] obtained a formula of the weighted tree-numbers of shifted complexes, developing simplicial matrix-tree theorem. We derive a formula of the weighted tree-numbers of the independent set complex of matroids (Theorem 9). In particular, we answer Adin's question in [START_REF] Adin | Counting colorful multi-dimensional trees[END_REF]Section 6 (b)].

Combinatorial Laplacians and high-dimensional tree-numbers

Adin [START_REF] Adin | Counting colorful multi-dimensional trees[END_REF] studied high-dimensional tree-number of simplicial complexes via combinatorial Laplacians, and similar studies were conducted in [8, 11-13, 20, 26-28, 30, 34]. For a finite graph, Temperley's formula demonstrates how the number of spanning trees and the detereminant of a combinatorial Laplacian are related.

Theorem 1 [START_REF] Temperley | On the mutual cancellation of cluster integrals in Mayer's fugacity series[END_REF]Temperley's formula] Let G be a finite loopless graph with n vertices with its Laplacian matrix L(G), and J the all 1 ′ s matrix. If we denote the number of spanning trees of G by k(G), then

det(L(G) + J) = n 2 ⋅ k(G).

◻

As we shall see, L(G) + J is the 0-th combinatorial Laplacian for the chain complex of G as a 1dimensional complex.

Temperley's formula has been generalized to high-dimensional complexes [START_REF] Duval | Simplicial matrix-tree theorems[END_REF][START_REF] Duval | Cellular spanning trees and Laplacians of cubical complexes[END_REF][START_REF] Kim | Logarithmic tree-numbers for acyclic complexes[END_REF]. In this paper, we will focus on the following type of complexes. A finite simplicial complex will be called Z-APC (Z-acyclic in positive codimension) if its reduced homology over Z is trivial except possibly in the top dimension (refer to [START_REF] Duval | Simplicial matrix-tree theorems[END_REF] for the origin of this terminology). The independent set complex IN (M ) of a matroid M , which is the main object of study in this paper, is Z-APC because it is shellable [START_REF] Björner | The homology and shellability of matroids and geometric lattices[END_REF]. We may refer to IN (M ) as a matroid complex, also.

Let {C i , ∂ i } be an augmented chain complex of a finite Z-APC complex Γ of dimension d with the augmentation

∂ 0 ∶ C 0 → Z given by ∂ 0 (v) = 1 for every vertex v in Γ. Recall that, for i ∈ [-1, d], the i-th combinatorial Laplacian ∆ i ∶ C i → C i is defined by ∆ i = ∂ t i ∂ i + ∂ i+1 ∂ t i+1 .
Note that if Γ is a finite graph, then ∂ t 0 ∂ 0 = J and ∂ 1 ∂ t 1 = L(G). Hence, Temperley's formula can be restated as det(∆ 0 ) = n 2 k(G).

Let Γ i be the set of all i-simplices, and Γ (i) the i-skeleton of Γ. For a non-empty subset S ⊂ Γ i , define Γ S = S ∪ Γ (i-1) as an i-dimensional subcomplex of Γ. For i ∈ [-1, d], a non-empty subset B ⊂ Γ i is an i-dimensional tree (or, simply, i-tree) if 1) . We will denote the set of all i-trees in Γ by B i = B i (Γ) with B -1 = {∅}. Define the i-th tree-number of Γ to be

(1) H i (Γ B ) = 0, (2) H i-1 (Γ B ) is finite, and (3) H j (Γ B ) = 0 for j ≤ i -2. Note that condition (3) is a consequence of the fact Γ (i-1) B = Γ (i-
k i = k i (Γ) = B∈Bi H i-1 (Γ B ) 2 .
The following is a generalization of Temperley's formula showing a relationship between ∆ i and unweighted high-dimensional tree-numbers k i .

Theorem 2 [20, Proposition 7] Let k i be the i-th tree-number of a Z-APC complex Γ . Then

(1) det ∆ -1 = k 0 (2) det ∆ i = k i-1 k 2 i k i+1 for i ∈ [0, d -1] (3) det ∆ d = k d-1 if
Γ is acyclic, and 0 otherwise. ◻

3 Weighted combinatorial Laplacians and weighted tree-numbers

As a refined enumerator of tree-numbers, we discuss weighted tree-numbers. For example, Cayley-Prüfer theorem [START_REF] Moon | Counting labelled trees[END_REF] gives an enumeration of the spanning trees of complete graphs according to their vertex degrees, and Kalai's formula [19, Theorem 3 ′ ] gives an enumeration of high-dimensional tree-numbers of standard simplexes according to their vertex degrees. Other examples of weighted Laplacians and weighted tree-numbers can be found in [START_REF] Duval | Simplicial matrix-tree theorems[END_REF][START_REF] Duval | Cellular spanning trees and Laplacians of cubical complexes[END_REF][START_REF] Martin | Pseudodeterminants and perfect square spanning tree counts[END_REF]. In [START_REF] Martin | Pseudodeterminants and perfect square spanning tree counts[END_REF], the weights of different dimensions were considered simultaneously, and we will develop similar ideas for matroid complexes in this paper.

Let Γ be Z-APC. For each vertex v ∈ Γ 0 , let x v be an indeterminate and define the weight of v to be

X v = x 2 v .
For each face σ ∈ Γ i , define x σ = ∏ v∈σ x v and define the weight of σ to be

X σ = v∈σ X v = (x σ ) 2 .
Denote by F a field containing R and all indeterminates x v . Let Ĉi be the F-vector space of i-chains in Γ. The weighted boundary operator ∂i ∶ Ĉi → Ĉi-1 is defined as follows. For each oriented i-face

[σ] = [v 0 , v 1 , . . . , v i ], ∂i [σ] = i j=0 (-1) j x vj [σ -v j ].
Equivalently, ∂i can be defined as

∂i = W -1 i-1 ∂ i W i
where W i is the diagonal matrix whose diagonal entry corresponding to the i-face σ ∈ Γ i is x σ . Define the i-th weighted combinatorial Laplacian ∆i ∶ Ĉi → Ĉi to be the i-th combinatorial Laplacian of the weighted chain complex { Ĉi , ∂i }, i.e.,

∆i = ∂t i ∂i + ∂i+1 ∂t i+1 .
Example 1 Let K be an (abstract) simplicial complex on a vertex set {1, 2, 3, 4, 5} whose facets are {124, 125, 134, 135, 145, 234, 235, 245} (see Fig. 1). Suppose that the rows and columns of ∂2 ∶ Ĉ2 → Ĉ1 are ordered lexicographically. Then ∂2 is given by

[124] [125] [134] [135] [145] [234] [235] [245] ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ [12] x4 x5 0 0 0 0 0 0 [13] 0 0 x4 x5 0 0 0 0 [14] -x2 0 -x3 0 x5 0 0 0 [15] 0 -x2 0 -x3 -x4 0 0 0 [23] 0 0 0 0 0 x4 x5 0 [24] x1 0 0 0 0 -x3 0 x5 [25] 0 x1 0 0 0 0 -x3 -x4 [34] 0 0 x1 0 0 x2 0 0 [35] 0 0 0 x1 0 0 x2 0 [45] 0 0 0 0 x1 0 0 x2 . ◻ Fig. 1: a realization of K
We introduce the definition of weighted high-dimensional tree-numbers by Kalai [START_REF] Kalai | Enumeration of Q-acyclic simplicial complexes[END_REF].

Definition 3 For i ∈ [0, d],
define the i-th weighted tree-number of Γ to be

ki = ki (Γ) = B∈Bi H i-1 (Γ B ) 2 X B . (3.1)
where

X B = σ∈B X σ is the weight of B ∈ B i . Define k-1 = 1.
For each B ∈ B i , define the degree of a vertex v ∈ Γ 0 in B to be the number of facets in Γ B containing v, denoted by deg B v. When Γ is a graph, this definition of degree is the same as that in graph theory. Then equation (3.1) becomes

B∈Bi H i-1 (Γ B ) 2 v∈Γ0 X v deg B v ,
which explains why weighted tree-numbers are often called degree-weighted tree-numbers. Note that if X v = 1 for all v ∈ Γ 0 , then we recover the i-th (unweighted) tree-number k i . An example of degree-weighted tree-numbers is the following Cayley-Prüfer [START_REF] Moon | Counting labelled trees[END_REF] theorem for complete graphs.

T ∈B1(Kn) n i=1 X deg T (i) i = X 1 X 2 ⋯X n (X 1 + X 2 + ⋯ + X n ) n-2 . A high-dimensional analogue of this theorem is Kalai's formula [19, Theorem 3 ′ ] B∈Bi(Σ) H i-1 (Γ B ) n i=1 X deg B (i) i = (X 1 X 2 ⋯X n ) n-2 i-1 (X 1 + X 2 + ⋯ + X n ) n-2 i (3.2)
where Σ is the standard simplex on n vertices.

The following is the weighted version of Theorem 2.

Theorem 4

The following holds for a Z-APC complex Γ of dimension d:

(1) det ∆-1 = k0 (2) det ∆i = (∏ σ∈Γi-1 X σ ) -1 (∏ σ∈Γi X σ ) -1 ki-1 k2 i ki+1 for i ∈ [0, d -1] (3) det ∆d = (∏ σ∈Γ d-1 X σ ) -1 kd-1 (∏ σ∈Γ d X σ ) if Γ is
acyclic, and 0 otherwise. ◻

From now on, let Γ be an acyclic complex of dimension d + 1. The reason for considering dimension d + 1 is that we will apply an acyclization to a Z-APC complex of dimension d.

By using Theorem 2, a relation was found between the generating function of the logarithmic determinants of combinatorial Laplacians and that of the logarithmic tree-numbers, which makes it efficient to compute the tree-numbers [20, Theorem 8]. The following theorem is the weighted version of this relation. We introduce formal logarithm having the following property: log XY = log X + log Y for nonzero X, Y ∈ F.

Theorem 5 Let D(x), K(x), and F (x) be given as follows.

(1) D(x) = ∑ d+1 i=-1 ωi x i+1 where ωi = log det ∆i

(2) K(x) = ∑ d i=0 κi x i where κi = log ki (3) F (x) = ∑ v∈Γ0 log X v (∑ d i=0 f v,i x i+1 ) -f v,d+1
x d+1 where f v,i is the number of i-faces in Γ containing v.

Then we have

D(x) = (1 + x) 2 K(x) -(1 + x)F (x), or K(x) = (1 + x) -2 D(x) + (1 + x) -1 F (x).

◻

From this theorem, one can recover Kalai's formula (equation (3.2)).

In addition, we express weighted tree-numbers in terms of the monomials corresponding to all vertices and eigenvalues of weighted combinatorial Laplacians. The following theorem is the weighted version of [12, equation (11)] obtained from Theorem 5.

Theorem 6 Let Λ be the set of all distinct eigenvalues of the total weighted Laplacian ⊕ d+1 i=-1 ∆i and let m λ,i be the multiplicity of λ in ∆i , i.e., det ∆i = ∏λ ∈ Λ λm λ,i . The d-th weighted tree-number kd of Γ is

vertices v of Γ (X v ) χ((lk v) (d-2) ) λ∈ Λ λa λ,d
where

a λ,d = ∑ d-1
j=-1 (-1) d-j-1 (dj)m λ,j and the link of a vertex v is given by

lk v = {σ ∈ Γ σ ∩ {v} = ∅, σ ∪ {v} ∈ Γ},
and (lk v) (d-2) denotes the (d -2)-skeleton of lk v. ◻

One can regard the characteristic polynomial of ∆ as an element in F[x], and its eigenvalues as elements in the algebraic closure of F.

Weighted combinatorial Laplacians of matroid complexes

An interesting question concerning combinatorial Laplacians is which complexes have integral spectra.

There are some known complexes with this property: chessboard [START_REF] Friedman | On the Betti numbers of chessboard complexes[END_REF], matching [START_REF] Dong | Combinatorial Laplacian of the matching complex[END_REF], matroid [START_REF] Kook | Combinatorial Laplacians of matroid complexes[END_REF], shifted [START_REF] Duval | Shifted simplicial complexes are Laplacian integral[END_REF], and shifted cubical complexes [START_REF] Duval | Cellular spanning trees and Laplacians of cubical complexes[END_REF]. Then a natural question for the weighted combinatorial Laplacians is which complexes have spectra that consist of polynomials. Duval, Klivans, and Martin showed that the spectra of the weighted combinatorial Laplacians of shifted complexes consist of polynomials and used their result to give the weighted tree-numbers of shifted complexes [START_REF] Duval | Simplicial matrix-tree theorems[END_REF]. We show that matroid complexes have polynomial spectra and will use these to find the weighted tree-numbers of matroid complexes. First, we review the spectra of the unweighted combinatorial Laplacians of matroid complexes [START_REF] Kook | Combinatorial Laplacians of matroid complexes[END_REF]. Let M be a loopless matroid, r its rank function, L(M ) its lattice of flats, and µ(V, W ) the Möbius function on L(M ) × L(M ). Define the α-invariant α(M ) of M to be the unsigned reduced Euler characteristic of its matroid complex IN (M ). For convenience, we will denote µ(W V ) = µ(V, W ) and d = r(M ) -1.

Theorem 7 [25, Corollary 18] Let Λ be the set of all distinct eigenvalues of the total Laplacian

⊕ d i=-1 ∆ i of a matroid complex IN (M ). Then Λ = { E ∖ V ∶ V ∈ L(M ) and α(V ) ≠ 0}
and, for each λ ∈ Λ, its multiplicity m λ,i in ∆ i is given by

V ∶ E∖V =λ W ∶r(W )=i+1 α(V )µ(W V ).

◻

We present the weighted version of the above theorem. Let F be a field containing R and all indeterminates x e for each element e in the ground set E of M . For each e ∈ E, define the weight of e to be X e = x 2 e . For each non-empty set S ⊂ E, define S = ∑ e∈S X e and ∅ = 0. Theorem 8 Let Λ be the set of all distinct eigenvalues of the total weighted Laplacian ⊕ d i=-1 ∆i of a matroid complex IN (M ) where ∆i is the i-th weighted combinatorial Laplacian of M . Then

Λ = { E ∖ V ∶ V ∈ L(M ) and α(V ) ≠ 0}
and, for each λ = E ∖ V ∈ Λ, its multiplicity m λ,i in ∆i is given by

W ∶r(W )=i+1 α(V )µ(W V ).
In particular, the spectra of ⊕ d i=-1 ∆i consist of polynomials in X e 's. ◻

Weighted tree-numbers of matroid complexes

We show that the weighted tree-numbers of matroid complexes have a nice factorization according to the degrees of their vertices. Our method is different from what was used to find the formula for the weighted tree-numbers of a shifted complex [START_REF] Duval | Simplicial matrix-tree theorems[END_REF]. While the reduced Laplacian in the top dimension was used in [START_REF] Duval | Simplicial matrix-tree theorems[END_REF], we use all of the combinatorial Laplacians.

To begin, we review two important invariants of a matroid M which will appear in the formula. One is α(M ) which equals the unsigned reduced Euler characteristic χ(IN (M )) of IN (M ). Note that α(M ) has other interpretations as follows:

α(M ) = µ L(M * ) ( 0, 1) = rk Hr(M)-1 (IN (M )) = T M (0, 1),
where M * is the dual matroid of M , and T M (x, y) the Tutte polynomial of M .

The other is Crapo's β(M ) which is defined as follows [START_REF] Crapo | A higher invariant for matroids[END_REF]:

β(M ) = (-1) r(M ) A⊂E(M ) (-1) A r(A) .
For our purpose, it will be useful to take the following equivalent definition of β(M ) (used in [START_REF] White | Combinatorial Geometries[END_REF]Chapter 7.3]).

β(M ) = (-1) r(M ) V ∈L(M ) µ( 0, V )r(V ).
It is also known that β(M ) equals the unsigned reduced Euler characteristic of the reduced broken circuit complex [START_REF] Björner | The homology and shellability of matroids and geometric lattices[END_REF]. The following is the main theorem of this paper.

Theorem 9 The d-th weighted tree-number kd

(M ) = kd (IN (M )) of a matroid complex IN (M ) is e∈E X ( B(M e) -α(M e)) e flats V of M ( e∉V X e ) α(V )β(M V ) .
where B(M ) denotes the number of bases of a matroid M . Here, 2) ) .

B(M e) -α(M e) = χ(IN (M e) (d -
(This equality comes from the shellability of matroid complexes.) ◻

This theorem is proved using Theorem 6 and Theorem 8. By setting X e = 1 for all e ∈ E, we can recover (unweighted) tree-numbers of matroid complexes [24, Theorem 2]. To simplify their formulas, we introduce a convolution of α-invariant and β-invariant. 2). Then the cycle matroid complex IN ) of M is the simplicial complex K in Example 1 (see Fig. 1). We apply our theorem to compute the weighted tree-numbers of the matroid complex IN (M ).

First, for each vertex e in IN (M ), the matroid complex IN (M e) of the contraction M e consists of 4 vertices and so χ((IN (M e)) (0) ) = 3.

Second, for each flat V in M , let us compute α(V ) and β(M V ).

• If V = ∅, then α(V ) = 1 and β(M V ) = β(M ) = 1.

• If V has only one element, then α(V ) = 0 .

• If V is {1, 2, 3} or {3, 4, 5}, then α(V ) = 1 and β(M V ) = 1.

• If V = M , then β(M V ) = β(∅) = 0.

Therefore, k2 (M ) = X 3 1 X 3 2 X 3 3 X 3 4 X 3 5 (X 1 + X 2 + X 3 + X 4 + X 5 )(X 1 + X 2 )(X 4 + X 5 )

and we obtain k 2 (M ) = 2 2 ⋅ 5. ◻

Definition 10

 10 For λ ∈ Λ = { E ∖ V ∶ V ∈ L(M ) and α(V ) ≠ 0}, define a convolution of α-invariant and β-invariant with respect to λ asα ○ λ β = V ∈L(M )∶ E∖V =λ α(V )β(M V ).Theorem 11 [24, Theorem 5] The d-th tree-number k d (M ) = k d (IN (M )) of a matroid complex IN (M ) is λ∈Λ λ α○ λ β . ◻ Example 2 Let M = M (G) be the cycle matroid of G where G is a graph K 4e (see Fig.

Fig. 2 :

 2 Fig. 2: a graph G = K4 -e

Acknowledgements

The authors would like to thank Prof. V. Reiner, Prof. A. Duval, Prof. C. Klivans, and Prof. J. Martin for helpful conversations concerning high-dimensional trees. We also would like to thank anonymous referees for helpful comments and suggestions.

This work was partially supported by Research Resettlement Fund for the new faculty of SNU and BK21 PLUS SNU Mathematical Sciences Division. This work was partially supported by BK21 PLUS SNU Mathematical Sciences Division and Kwanjeong Educational Foundation. 1365-8050

Applications: Complete colorful complexes

We give the weighted version of Adin's formula for the tree-numbers of complete colorful complexes, answering the question posed in [START_REF] Adin | Counting colorful multi-dimensional trees[END_REF]Section 6 (b)]. Define a complete colorful complex as follows. For each t ∈ [r], let E t = {e 1,t , e 2,t , . . . , e nt,t } be a set of vertices representing color t. Let E = ⊔ r t=1 E t . Define complete colorful complex K = K(n 1 , . . . , n r ) to be a simplicial complex on a vertex set E whose faces are subsets of E each containing at most one element from each E t , i.e.,

Note that K is isomorphic to the matroid complex of ⊕ r t=1 U 1,nt where U 1,nt is a rank 1 uniform matroid on n t elements. FThe dimension of K is d = r -1. In addition, for each i ∈ [1, d], the i-th skeleton K (i) is a matroid complex.

For each t ∈ [r], denote the weights of e 1,t , e 2,t , . . . , e nt,t by X 1,t , X 2,t , . . . , X nt,t , respectively. For each

where e j (Y 1 , . . . , Y n ) is the j-th elementary symmetric polynomial. In particular, 1) .

◻

The weighted top-dimensional tree-number of a complete colorful complex was computed by Aalipour and Duval.

We recover Adin's formula for the unweighted tree-numbers of complete colorful complexes from the above weighted version, by setting X 1,t = ⋅ ⋅ ⋅ = X nt,t = 1 for all t ∈ [r]. (The top-dimensional tree-number of a complete colorful complex was suggested by Bolker [START_REF] Bolker | Simplicial geometry and transportation polytopes[END_REF].) Corollary 13 [1, Theorem 1.5] For i ∈ [1, d], we have

In particular,

◻

Note that the 1-dimensional skeleton of a complete colorful complex is a complete multipartite graph. By using the above theorem, we obtain the weighted spanning tree-numbers of complete multipartite graphs (For that of a complete bipartite graph, see [START_REF] Stanley | Enumerative Combinatorics[END_REF]Exercise 5.30]).

Let K n1,...,nr be a complete multipartite graph with an r-partition (V 1 , . . . , V r ). For each t ∈ [r], let V t = {v 1,t , . . . , v nt,t }, and denote the weights of v 1,t , . . . , v nt,t by X 1,t , . . . , X nt,t , respectively. For a complete bipartite graph K m,n with a bipartition (A, B) where A = {u 1 , . . . , u m } and B = {v 1 , . . . , v n }, let X 1 , . . . , X m (resp. Y 1 , . . . , Y n ) be the weights of u 1 , . . . , u m (resp. v 1 , . . . , v n ).

Corollary 14

The weighted spanning tree-number of K n1,...,nr is given by

In particular, the weighted spanning tree-number of K m,n is given by

◻

When each color set has only one element, we recover Kalai's formula for the weighted tree-numbers of standard simplexes.

Corollary 15 [19, Theorem 1, 3 ′ ] Let Σ be the standard simplex on n vertices. For each vertex v j ∈ (Σ) 0 , let X j be its weight. Then the i-th weighted tree-number is given by

In particular, its i-th tree-number is given by

. ◻


Travis Scrimshaw

Rigged configurations of type D (3) 4 and the filling map

Keywords: rigged configuration, Kirillov-Reshetikhin crystal, bijection

We give a statistic preserving bijection from rigged configurations to a tensor product of Kirillov-Reshetikhin crystals N i=1 B 1,s i in type D

(3) 4

by using virtualization into type D

(1)

4 . We consider a special case of this bijection with B = B 1,s , and we obtain the so-called Kirillov-Reshetikhin tableaux model for the Kirillov-Reshetikhin crystal.

Résumé. Nous donnons une bijection prservant les statistiques entre les configurations gréées et les produits tensoriels de cristaux de Kirillov-Reshetikhin N i=1 B 1,s i de type D

4 , via une virtualisation en type D

(1) 4 . Nous considérons un cas particulier de cette bijection pour B = B 1,s et obtenons ainsi les modèles de tableaux appelés Kirillov-Reshetikhin pour le cristal Kirillov-Reshetikhin.

Introduction

Rigged configurations were first introduced by Kerov, Kirillov, and Reshetikhin in [START_REF] Kerov | Combinatorics, the Bethe ansatz and representations of the symmetric group[END_REF][START_REF] Kirillov | The Bethe ansatz and the combinatorics of Young tableaux[END_REF] as combinatorial objects that index solutions to the Bethe Ansatz for the Heisenberg spin chains. Rigged configurations were shown to be in bijection with semi-standard tableaux and classical highest weight elements of a tensor power of the vector representation in type A [START_REF] Chari | On the fermionic formula and the Kirillov-Reshetikhin conjecture[END_REF] n . This bijection was then extended to Littlewood-Richardson tableaux [START_REF] Kirillov | A bijection between Littlewood-Richardson tableaux and rigged configurations[END_REF], to non-exceptional types [START_REF] Okado | A crystal to rigged configuration bijection for nonexceptional affine algebras, Algebraic combinatorics and quantum groups[END_REF], and to type E (1) 6 [START_REF] Okado | KKR type bijection for the exceptional affine algebra E (1) 6 , Algebraic groups and quantum groups[END_REF]. This bijection Φ between rigged configurations and the tensor powers has been further expanded to include classically highest weight elements in a tensor product of certain Kirillov-Reshetikhin (KR) crystals [START_REF] Kirillov | A bijection between Littlewood-Richardson tableaux and rigged configurations[END_REF][START_REF]Virtual crystals and fermionic formulas of type D (2) n+1 , A (2) 2n , and C (1) n[END_REF][START_REF] Okado | Affine crystal structure on rigged configurations of type D (1) n[END_REF][START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF][START_REF] Schilling | X = M for symmetric powers[END_REF].

Rigged configurations have been shown to display remarkable representation theoretic properties. A (classical) crystal structure was first given for simply-laced types [START_REF]Crystal structure on rigged configurations[END_REF], which was then extended to all finite types [START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF] and affine types [START_REF] Salisbury | A rigged configuration model for B(∞)[END_REF]. While Φ is defined recursively, making it difficult to work with, it preserves certain natural statistics (cocharge and energy), giving a bijective proof of the X = M conjecture of [START_REF] Hatayama | Remarks on fermionic formula, Recent developments in quantum affine algebras and related topics[END_REF][START_REF] Hatayama | Paths, crystals and fermionic formulae, MathPhys odyssey[END_REF]. Furthermore, the combinatorial R-matrix transforms into the identity map on rigged configurations under Φ. Rigged configurations are also well-behaved under virtualization [START_REF]Virtual crystals and fermionic formulas of type D (2) n+1 , A (2) 2n , and C (1) n[END_REF][START_REF]Virtual crystals and Kleber's algorithm[END_REF][START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF], a process of realizing a non-simply-laced type crystal inside of a simply-laced type, and embeddings B(λ) -→ B(µ) where λ ≤ µ component-wise, leading to a model for B(∞) [START_REF] Salisbury | A rigged configuration model for B(∞)[END_REF].

KR crystals in non-exceptional types were given a combinatorial model in [START_REF] Fourier | Kirillov-Reshetikhin crystals for nonexceptional types[END_REF] using Kashiwara-Nakashima tableaux [START_REF] Kashiwara | Crystal graphs for representations of the q-analogue of classical Lie algebras[END_REF]. The bijection Φ has also lead to a new tableaux model for KR crystals, coined Kirillov-Reshetikhin (KR) tableaux, using filled rectangular tableaux [START_REF] Okado | Affine crystal structure on rigged configurations of type D (1) n[END_REF][START_REF] Schilling | A bijection between type D (1) n crystals and rigged configurations[END_REF][START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF]. The map between Kashiwara-Nakashima tableaux [START_REF] Kashiwara | Crystal graphs for representations of the q-analogue of classical Lie algebras[END_REF] and the KR tableaux is called the filling map.

The goal of this work is to extend Φ to type D

(3) 4

and describe the filling map. For this extended abstract, we will be focusing on the KR crystals B 1,s and the rigged configurations associated with tensor products of the form N i=1 B 1,si . In particular, we show Φ is a classical crystal isomorphism, and we describe the filling map for B 1,s . We do so by showing the filling map and bijection commute with the virtualization map, proving more special cases of many of the conjectures stated in [START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF].

This extended abstract is organized as follows. In Section 2, we give background on crystals, virtualization, and rigged configurations. In Section 3, we describe the bijection Φ. In Section 4, we describe the filling map . In Section 5, we describe the virtualization map and our main results. In Section 6, we give possible extensions to B 2,s and some open questions. We conclude in Section 7 with some examples using Sage [START_REF] Stein | Sage Mathematics Software (Version 6.4)[END_REF].

Background

Crystals

For this extended abstract, let g be the Kac-Moody algebra of type D

(3) 4 with index set I = {0, 1, 2}, generalized Cartan matrix A = (A ij ) i,j∈I , weight lattice P , root lattice Q, fundamental weights {Λ i | i ∈ I}, simple roots {α i | i ∈ I}, and simple coroots {h i | i ∈ I}. There is a canonical pairing , : P ∨ × P -→ Z defined by h i , α j = A ij , where P ∨ is the dual weight lattice. Let g 0 denote the classical subalgebra of type G 2 with index set I 0 = {1, 2}, weight lattice P , root lattice Q, fundamental weights {Λ 1 , Λ 2 }, and simple roots {α 1 , α 2 }.

An abstract U q (g)-crystal is a nonempty set B together with a weight function wt : B -→ P , crystal operators e a , f a : B -→ B {0}, and maps ε a , ϕ a : B -→ Z {-∞} for a ∈ I, subject to the conditions

1. ϕ a (b) = ε a (b) + h a , wt(b) for all a ∈ I, 2. if e a b ∈ B, then ε a (e a b) = ε a (b) -1, ϕ a (e a b) = ϕ a (b) + 1, and wt(e a b) = wt(b) + α a . 3. if f a b ∈ B, then ε a (f a b) = ε a (b) + 1, ϕ a (f a b) = ϕ a (b) -1, and wt(f a b) = wt(b) -α a . 4. f a b = b if and only if b = e a b for b, b ∈ B and a ∈ I, 5. if ϕ a (b) = -∞ for b ∈ B, then e a b = f a b = 0. We define for all b ∈ B ε a (b) = max{k ∈ Z ≥0 | e k a b = 0}, ϕ a (b) = max{k ∈ Z ≥0 | f k a b = 0}. (2.1)
Rigged configurations of type D

4 and the filling map 675

1 2 3 0 3 2 1 ∅ 1 2 1 1 2 1 0 0 0 0 Fig. 2.2: The KR crystal B 1,1 of type D (3) 4 which is isomorphic to B(Λ1) ⊕ B(0) as Uq(g0)-crystals.
An abstract U q (g)-crystal with ε a and ϕ a defined as above is called a regular crystal.

Let B 1 and B 2 be abstract U q (g)-crystals. The tensor product of crystals B 2 ⊗ B 1 is defined to be the Cartesian product B 2 × B 1 with the crystal structure

e i (b 2 ⊗ b 1 ) = e i b 2 ⊗ b 1 if ε i (b 2 ) > ϕ i (b 1 ), b 2 ⊗ e i b 1 if ε i (b 2 ) ≤ ϕ i (b 1 ), ε i (b 2 ⊗ b 1 ) = max ε i (b 2 ), ε i (b 1 ) -h i , wt(b 2 ) f i (b 2 ⊗ b 1 ) = f i b 2 ⊗ b 1 if ε i (b 2 ) ≥ ϕ i (b 1 ), b 2 ⊗ f i b 1 if ε i (b 2 ) < ϕ i (b 1 ), ϕ i (b 2 ⊗ b 1 ) = max ϕ i (b 1 ), ϕ i (b 2 ) + h i , wt(b 1 ) wt(b 2 ⊗ b 1 ) = wt(b 2 ) + wt(b 1 ).
Remark 2.1 Our tensor product convention is the opposite to that given in [START_REF]On crystal bases of the q-analogue of universal enveloping algebras[END_REF].

Let B 1 and B 2 be two abstract U q (g)-crystals. A crystal morphism ψ : B 1 -→ B 2 is a map B 1 {0} -→ B 2 {0} with ψ(0) = 0 such that for b ∈ B 1 1. if ψ(b) ∈ B 2 , then wt(ψ(b)) = wt(b), ε i (ψ(b)) = ε i (b), and ϕ i (ψ(b)) = ϕ i (b);

we have ψ(f

i b) = f i ψ(b) provided ψ(f i b) = 0 and f i ψ(b) = 0.
A crystal embedding or isomorphism is a crystal morphism such that the induced map B 1 {0} -→ B 2 {0} is an embedding or bijection respectively. A crystal morphism is strict if it commutes with all crystal operators.

If an abstract U q (g)-crystal B is isomorphic to the crystal basis of an integrable U q (g)-module, we simply say B is a U q (g)-crystal. In particular, an irreducible highest weight U q (g 0 )-module with highest weight λ admits a crystal basis [START_REF] Kashiwara | Crystalizing the q-analogue of universal enveloping algebras[END_REF], which we denote by B(λ). Moreover there is a unique element u λ ∈ B(λ) such that wt(u λ ) = λ and e a u λ = 0 for all a ∈ I 0 . For each dominant integral weight

λ = k 1 Λ 1 + k 2 Λ 2 , we can associate a partition (k 1 + k 2 , k 2 ).
We can realize B(λ) as semistandard tableaux of shape λ filled with entries in B(Λ 1 ) whose crystal structure is given by embedding into B(Λ 1 ) ⊗|λ| using the reverse far-eastern reading word. The resulting tableaux were explicitly described by Kang and Misra [START_REF] Kang | Crystal bases and tensor product decompositions of U q (G 2 )modules[END_REF].

Kirillov-Reshetikhin crystals

An important class of finite dimensional U q (g)-representations are Kirillov-Reshetikhin (KR) modules W r,s indexed by r ∈ I 0 and s ∈ Z >0 . KR modules are characterized by their Drinfeld polynomials [START_REF] Chari | Quantum affine algebras and their representations, Representations of groups[END_REF][START_REF]Twisted quantum affine algebras[END_REF] and correspond to the minimal affinization of B(sΛ r ) [START_REF] Chari | On the fermionic formula and the Kirillov-Reshetikhin conjecture[END_REF]. The KR modules W 1,s admit a crystal basis called Kirillov-Reshetikhin (KR) crystals and denoted by B 1,s . As U q (g 0 )-crystals, we have B 1,s ∼ = s k=1 B(kΛ 1 ), and B 1,s is a perfect crystal [START_REF] Kashiwara | Perfect crystals for U q (D (3) 4 )[END_REF]. This means we can use a semi-infinite tensor product of B 1,s to realize highest weight U q (g)-crystals, see [START_REF] Hong | Introduction to quantum groups and crystal bases[END_REF] for details.

There is a statistic called energy defined on B = N i=1 B 1,si [START_REF] Hatayama | Remarks on fermionic formula, Recent developments in quantum affine algebras and related topics[END_REF]. First we define the local energy function on B 1,s ⊗ B 1,t as follows. The combinatorial R-matrix is the unique U q (g)-crystal isomorphism (2.

R : B 1,s ⊗ B 1,t -→ B 1,t ⊗ B 1,s [10]. Let c ⊗ c = R(b ⊗ b ). H e i (b ⊗ b ) = H(b ⊗ b ) +      -1 i = 0
2)

The local energy function is defined up to an additive constant [START_REF] Kang | Affine crystals and vertex models, Infinite analysis, Part A, B[END_REF], and so we normalize H by the condition

H(1 s ⊗ 1 t ) = 0 where 1 k is row of length k filled with 1. Next we define D B 1,s : B 1,s → Z by D B 1,s (b) = H(b ⊗ b ) -H(1 s ⊗ b ), (2.3)
where b is the unique element such that ϕ(b ) = sΛ 0 . Then we define

D(b N ⊗ • • • ⊗ b 1 ) = 1≤i<j≤N H i R i+1 R i+2 • • • R j-1 + N j=1 D B 1,s j R 1 R 2 • • • R j-1 , (2.4)
where R i and H i are the combinatorial R-matrix and local energy function, respectively, acting on the i-th and (i + 1)-th factors and D B 1,s j acts on the rightmost factor. We say the energy of an element b ∈ B is D(b).

Rigged configurations

(a,i)∈H0 im (a) i α a = (a,i)∈H0 iL (a) i Λ a -λ, (2.5) where m (a)
i is the number of parts of length i in the partition ν (a) . We denote the set of (L, λ)-configurations by C(L, λ). The vacancy numbers of ν ∈ C(L; λ) are defined as

p (a) i = j≥1 min(i, j)L (a) j - (b,j)∈H0 A ab min(i, j)m (b) j .
(2.6)

A rigged configuration of classical weight λ is a (L; λ)-configuration ν, along with a sequence of multisets of integers J = {J Example 2.2 Rigged configurations will be depicted with vacancy numbers on the left and labels on the right. For example,

3 1 5 1 -2 -2
is a rigged configuration of weight 2Λ 1 + Λ 2 with L is given by L Denote by RC * (L; λ) the set of valid highest weight rigged configurations. Rigged configurations have an abstract U q (g 0 )-crystal structure [START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF]. To obtain the weight, we first note that we can compute the classical weight by wt(ν, J)

= (a,i)∈H0 i L (a) i Λ a -m (a) i α a . (2.7)
We can extend this to wt : RC(L; λ) -→ P by wt(ν, J) = k 0 Λ 0 + wt(ν, J), where k 0 is such that wt(ν, J), c = 0 with c the canonical central element of g (i.e., we make wt(ν, J) be level 0).

Explicitly, if wt(ν, J) = c 1 Λ 1 + c 2 Λ 2 , then we have k 0 = -2c 1 -3c 2 .
Next we recall the crystal operators. Definition 2.3 Let g 0 be a Lie algebra of finite type and L a multiplicity array. Let (ν, J) be a valid rigged configuration. Fix a ∈ I 0 and let x be the smallest label of (ν, J) (a) , the strings associated to ν (a) .

1. If x ≥ 0, then set e a (ν, J) = 0. Otherwise, let be the minimal length of all strings in (ν, J) (a) which have label x. The rigged configuration e a (ν, J) is obtained by replacing the string ( , x) with the string ( -1, x + 1) and changing all other labels so that all colabels remain fixed.

2. If x > 0, then add the string (1, -1) to (ν, J) (a) . Otherwise, let be the maximal length of all strings in (ν, J) (a) which have label x and replace the string ( , x) by the string ( + 1, x -1). In both cases, change all other labels so that all colabels remain fixed. If the result is a valid rigged configuration, then it is f a (ν, J) . Otherwise f a (ν, J) = 0.

Remark 2.4

The condition for highest weight rigged configurations matches with the usual crystal theoretic definition; i.e., that e a (ν, J) = 0 for all (ν, J) ∈ RC * (L; λ).

Example 2.5 Let (ν, J) be the rigged configuration from Example 2.2. Then

e 1 (ν, J) = 0, e 2 (ν, J) = 0 1 2 1 -1 -1 , f 1 (ν, J) = 1 -1 -1 3 -1 -1 -1 -1 , f 2 (ν, J) = 0.
Let RC(L; λ) denote the set generated from RC * (L; λ) by the crystal operators. Let RC(L) be the closure under the crystal operators of the set RC * (L) = λ∈P + RC * (L; λ).

Theorem 2.6 ([27]

) Let g 0 be a Lie algebra of finite type. For (ν, J) ∈ RC * (L; λ), let X (ν,J) be the closure of (ν, J) under e a , f a for a ∈ I 0 . Then X (ν,J) ∼ = B(λ) as U q (g 0 )-crystals.

There is a statistic called cocharge on rigged configurations given by cc(ν, J) = 1 2

a,b∈I0 i,j∈Z>0

(α a |α b ) min(i, j)m (a) i m (b) j + (a,i)∈H0 x∈J (a) i x. (2.8)
Moreover cocharge is invariant under e a and f a for a ∈ I 0 [START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF].

Virtual crystals

Let g be the Kac-Moody algebra with index set I of type D

4 and g 0 be of type D 4 . We consider the diagram folding φ : I I defined by φ(0) = 0, φ(2) = 1, and φ(1) = φ(3) = φ(4) = 2. The folding φ restricts to a diagram folding of type g 0 g 0 , and by abuse of notation, we also denote this folding by φ.

Remark 2.7 To simplify our notation, for any object X or X of g 0 , we denote the corresponding object of g 0 by X.

Furthermore, the folding φ induces an embedding of weight lattices Ψ : P -→ P given by

Λ a → b∈φ -1 (a) Λ b , α a → b∈φ -1 (a) α b . (2.9)
This gives an embedding of crystals as sets v : B(λ) -→ B Ψ(λ) , and let V (λ) denote the image of v.

We can define a crystal structure on V which is induced from the crystal B Ψ(λ) by

e v := b∈φ -1 (a) e b , f v := b∈φ -1 (a) f b , ε v a := ε x , ϕ v a := ϕ x , wt := Ψ -1 • wt, (2.10)
where we fix some x ∈ φ -1 (a). We say the pair V (λ), B Ψ(λ) is a virtual crystal and the isomorphism v is the virtualization map. Proposition 2.8 ( [START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF]) Let g 0 be of finite type. Then we have B(λ) ∼ = V (λ) as U q (g 0 )-crystals.

In particular, we can define a virtualization map on rigged configurations by

ν (b) = ν (a) , (2.11a)
J (b) i = J (a) i (2.11b)
for all b ∈ φ -1 (a) [START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF].

The basic algorithm δ

We begin by describing the basic step δ : RC(B 1,1 ⊗ B * ) -→ RC(B * ), where B * is some tensor product of KR crystals. Each step δ returns some element b ∈ B 1,1 , which we use to create B. We note that this is the special case of the algorithm given in [START_REF] Mohammad | Soliton cellular automata constructed from a U q (g)-Crystal B n,1 and Kirillov-Reshetikhin type bijection for U q (E (1) 6 )-Crystal B[END_REF] for type D

4 . Set 0 = 1. Do the following process for a = 1. Find the minimal integer i ≥ a-1 such that ν (a) has a singular string of length i. If no such i exists, then set b = a and a = ∞ and terminate. Otherwise set a = i and repeat the above process for a = 2.

Suppose the process has not terminated. We remove the selected (singular) string of length 1 from consideration. If there are no singular or quasi-singular strings in ν (a) larger than 2 or if 2 = 1 and there is only one string of length 1 in ν (1) , then set b = 3 and terminate. Otherwise find the smallest i ≥ 2 that satisfies one of the following three mutually exclusive conditions:

(S) J (1,i) is singular and i > 1;

(P) J (1,i) is singular and i = 1;

(Q) J (1,i) is quasi-singular.

If (P) holds, set b = ∅, and 3 = i and terminate. If (S) holds, set 3 = i -1, 3 = i, say case (S) holds for a = n, and continue. If (Q) holds, find the minimal j > i such that (S) holds. If no such j exists, set b = 0 and terminate. Else set 3 = j and say case (Q, S) holds and continue.

Suppose the process has not terminiated, and let a = 2. If a = a+1 , then set a = a , afterwards reset a = a -1, and say case (S2) holds for a. Otherwise find the minimal index i ≥ a+1 such that ν (a) has a singular string of length i. If no such i exists, set b = a + 1 and terminate. Otherwise set a = i and repeat this for a = 1 (there must exists at least two singular strings if 3 = 1 and case (S2) does not hold). If the process has not terminated, set b = 1. Set all undefined a and a for a = 1, 2, 3 to ∞.

Change in the rigged configuration

The rigged configurations change under δ as follows. We first remove a box from a in ν (a) for a = 1, 2, and if case (S2) holds for a, we remove another box from that particular row, otherwise we remove a box from a . If case (S) holds, then remove two boxes from 3 and make the resulting string singular. If case (Q) holds, remove a box from 3 and make the resulting string singular. If case (Q, S) holds, then we remove both boxes corresponding to 3 and 3 , but we make the smaller one (i.e. the row corresponding to 3 ) singular and the larger one quasi-singular. Also make all the changed strings in ν (2) singular.

Remark 3.1 We can determine the inverse algorithm by roughly doing the opposite of the above; in paritcular, selecting largest (quasi)singular strings at most as long as before.

Fig. 2 . 1 :

 21 Fig. 2.1: Dynkin diagram of type D

2 .

 2 we have ψ(e i b) = e i ψ(b) provided ψ(e i b) = 0 and e i ψ(b) = 0;

  and e 0 (b ⊗ b ) = b ⊗ e 0 b and e 0 (c ⊗ c) = c ⊗ e 0 c, 1 i = 0 and e 0 (b ⊗ b ) = e 0 b ⊗ b and e 0 (c ⊗ c) = e 0 c ⊗ c, 0 otherwise.

Let H 0 =

 0 I 0 × Z >0 . Consider a multiplicity array L = L (a) i ∈ Z ≥0 | (a, i) ∈ H 0 and a dominant integral weight λ of g 0 . A (L; λ)-configuration is a sequence of partitions ν = {ν (a) | a ∈ I} such that

|

  (a, i) ∈ H 0 } such that |J (a) i | = m

  in weakly decreasing order.) So to each row of length i, we have an integer x ∈ J (a) i and we call the pair (i, x) a string. The integers x ∈ J (a) i are called label, rigging, or Rigged configurations of type D (3) 4 and the filling map 677 quantum number. The colabel of a string (i, x) is defined as p (a) i -x. A rigged configuration is highest weight if min J (a) i ≥ 0 for all (a, i) ∈ H 0 and is valid if max J say a string (i, a) is singular if p (a) i = x and is quasi-singular if p (a) i = x -1 and max J

= 0 .

 0 See Section 7 on how to construct this example in Sage.

3

  The bijection Φ Consider a tensor product of KR crystals B = N i=1 B ri,si . We write RC(B) for RC(L) with L(a) i equal to the number of factors B a,i occurring in B. In this section, we describe the map Φ : RC(B) -→ B. Rigged configurations of type D (3) 4 and the filling map 679

Example 3 . 2

 32 Using the rigged configuration (ν, J) from Example 2.2 andB = B 1,1 ⊗ B 1,2 ⊗ B 2,1 .Applying the map δ, we get b = 3 and

Acknowledgements

The author would like to thank Masato Okado for a very valuable discussion and pointing out the reference [17]. The author would also like to thank Anne Schilling for reading a draft of this extended abstract and her mentorship.

† Partially supported by NSF grant OCI-1147247 1365-8050 c 2015

Extending to arbitrary rectangles

We now extend Φ to B = N i=1 B 1,si by defining the map ls : RC(B 1,s ⊗ B * ) -→ RC(B 1,1 ⊗ B 1,s-1 ⊗ B * ), which is known as left-split. On the rigged configurations, the map ls is the identity (but perhaps increases the vacancy numbers) and a strict crystal embedding. Thus iterating ls with δ, we obtain a map Φ : RC(B) -→ B.

Filling map

We determine the highest weight rigged configurations for B 1,s by using the virtual Kleber algorithm [START_REF]Virtual crystals and Kleber's algorithm[END_REF]. Lemma 4.1 Consider the KR crystal B 1,s . We have RC(B 1,s ) = s k=0 RC(B 1,s ; kΛ 1 ). Moreover the highest weight rigged configurations in RC(B 1,s ; kΛ 1 ) are given by ν (1) = (s -k, s -k) and ν (2) = (s -k) with all labels 0. From Lemma 4.1 and the U q (g 0 )-crystal decomposition of B 1,s is multiplicity free, there exists a natural U q (g 0 )-crystal isomorphism ι : RC(B 1,s ) -→ B 1,s . For type D

(3) 4 , we note that kΛ 1 can be considered as the partition (k). 4 and consider the classical component B(kΛ 1 ) ⊆ B 1,s . The filling map fill : B 1,s -→ (B 1,1 ) ⊗s is given by adding s-k 2 copies of the horizontal domino 1 1 and an additional ∅ if s -k is odd.

Let T 1,s denote the image of B 1,s under fill written as a 1 × s rectangle. We note that T 1,s inherits a classical crystal structure from (B 1,1 ) ⊗s . We give a U q (g)-crystal structure to T 1,s by following [START_REF] Kashiwara | Perfect crystals for U q (D (3) 4 )[END_REF][START_REF] Yamada | Scattering rule in soliton cellular automaton associated with crystal base of U q (D (3) 4 )[END_REF] as the conditions for e 0 and f 0 are preserved under the filling map.

Proposition 4.4

The filling map fill :

We also can show the following. is given column-bycolumn by

Using Lemma 5.1 and the analogue of Φ in type D

(1)

4 [START_REF] Okado | Affine crystal structure on rigged configurations of type D (1) n[END_REF][START_REF] Schilling | A bijection between type D (1) n crystals and rigged configurations[END_REF], we can show the following.

4 . The virtualization map v commutes with the map Φ.

We need to define the complement rigging map θ : RC(B) -→ RC(B r ) by sending (ν, J) → (ν, J ), where J is obtained by x = p (a) i -x for all labels x and B r are the factors of B in reverse order. That is to say θ maps each label x to its colabel. We can define δ := θ • δ • θ, and using the virtualization map, Proposition 4.5, and the results of [START_REF] Schilling | A bijection between type D (1) n crystals and rigged configurations[END_REF], we can show the following.

Using the results on the combinatorial R-matrix in [START_REF] Yamada | Scattering rule in soliton cellular automaton associated with crystal base of U q (D (3) 4 )[END_REF], we can show the following.

Then following [START_REF] Schilling | X = M for symmetric powers[END_REF]Sec. 8], the map rs := θ • ls •θ preserves statistics using [START_REF] Yamada | Scattering rule in soliton cellular automaton associated with crystal base of U q (D (3) 4 )[END_REF]. From Lemma 5.4, the R-matrix preserves statistics. Thus iterating rs and R-matrices, we preserve statistics to N i=1 B 1,1 . Then we use the results of [START_REF] Sakamoto | Rigged configurations and Kashiwara operators[END_REF][START_REF] Schilling | A bijection between type D (1) n crystals and rigged configurations[END_REF] and Theorem 5.2 to obtain our main result. n given in [START_REF] Okado | Affine crystal structure on rigged configurations of type D (1) n[END_REF], we can show the following. Theorem 5.6 Let B = B 1,s . Then Φ = fill •ι with fill as in Definition 4.2 as U q (g 0 )-crystal morphisms.

Thus we can define a U q (g)-crystal structure on RC(B) by extending Φ to be a U q (g)-crystal isomorphism. Thus we have a special case in type D

(3) 4 of the conjectures given in [START_REF] Schilling | Crystal structure on rigged configurations and the filling map for non-exceptional affine types[END_REF].

Extensions and questions

The U q (g 0 )-crystal decomposition of B 2,s and the highest weight rigged configurations will appear in the full version of this work. The author hopes to use this to determine the filling map for B 2,s .

There is a map lt : RC(B 2,1 ⊗ B * ) -→ RC(B 1,1 ⊗ B 1,1 ⊗ B * ) called left-top which adds a singular string of length 1 to ν (1) . In the full version, this is used to extend the U q (g 0 )-crystal isomorphism Φ to tensor products also containing B 2,1 . Example 6.1 Continuing from Example 3.2, we obtain

The computations for the Kleber algorithm can be modified to determine the U q (g 0 )-crystal decomposition of B r,s of type G

(1) 2 . However there is a difficulty with determining what the map δ should be. This would need to be overcome to define the filling map for type

There is a conjecture [START_REF]Virtual crystals and Kleber's algorithm[END_REF]Conj. 3.7] that we can realize B 1,s of type

4 . Therefore obtaining a direct description of e 0 and f 0 on rigged configurations could lead to an answer to this conjecture using the results of [START_REF] Okado | Affine crystal structure on rigged configurations of type D (1) n[END_REF]. The author hopes to have this description and prove this conjecture in this special case in the full version of this work.

Examples using Sage

The bijection Φ and the rigged configurations have been implemented by the author in Sage [START_REF] Stein | Sage Mathematics Software (Version 6.4)[END_REF]. We begin by setting up the Sage environment to give a more concise printing. sage: RiggedConfigurations.global_options(display="horizontal")

We construct our the rigged configuration from Example 2.2 by specifying the partitions and corresponding labels. We apply the full bijection and print the output using Sage's ASCII art.


Suho Oh

Hwanchul Yoo

Matching Ensembles(Extended Abstract)

Keywords: Matchings, Bipartite Graphs, Spanning trees, Simplices, Product of two simplices, Subdivisions, Triangulations

We introduce an axiom system for a collection of matchings that describes the triangulation of product of simplices.

Résumé. Nous introduisons un système d'axiomes pour une collection de couplages qui décrit la triangulation de produit de simplexes.

Introduction

Triangulations of a product of two simplices are beautiful and important objects. In this paper, we describe a new combinatorial model for describing the triangulations of product of two simplices, ∆ n-1 × ∆ d-1 .

The model we use is called matching ensemble; it was motivated by matching fields introduced and studied by [START_REF] Bernstein | Combinatorics of maximal minors[END_REF]. The (n, d)-matching field, for n ≥ d, is a collection of bijections ("matchings") between d-element subsets of [n] = {1, . . . , n} and the set [d] = {1, . . . , d}. A matching field is coherent if it satisfies linkage property, which is similar to the basis exchange axiom for matroids. These objects were used to study the Newton polytope of the product of all maximal minors of an n-by-d matrix of indeterminates.

We define an (n, d)-matching ensemble as a collection of matchings between subsets of [n] and subsets of [d] such that:

• there is exactly one matching between every pair with same cardinality,

• a submatching of any matching is in the collection, and

• the matchings contained in the collection satisfy the linkage property.

There is a bijection between (n, d)-matching ensembles and triangulations of ∆ n-1 × ∆ d-1 . This is an extended abstract, and the proof of this claim can be found in [START_REF] Oh | Triangulations of product of two simplices and matching ensembles[END_REF]. Following [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF], we will study ∆ n-1 ×∆ d-1 using a class of polytopes associated to bipartite graphs G ⊆ K n,d , called root polytopes. We think of the complete bipartite graph K n,d as having a set of left vertices {1, . . . , n} and a set of right vertices { 1, . . . , d}. We define Q G to denote the convex hull of points e i -ej for edges (i, j) of G where e 1 , . . . , e n , e1, . . . , e d are the coordinate vectors in R n+d . When G is the complete bipartite graph

K n,d , the polytope Q G is exactly ∆ n-1 × ∆ d-1 .
Definition 2.1. A triangulation of a polytope P is a subdivision of P into a union of simplices of the same dimension as P such that each simplex is the convex hull of some subset of vertices of P and any two simplices intersect properly, i.e., the intersection of any two simplices is their common face.

(2,2)

(1,1) (1,2) (1,3) (2,1)
(2,3) Fig. 1: An example of a triangulation of ∆1 × ∆2. Figure 1 is an example of a triangulation of ∆ 1 × ∆ 2 . We will be studying the triangulation of ∆ n-1 × ∆ d-1 . The simplices of the triangulations can be described via spanning trees due to the following lemma: Lemma 2.2 (Lemma 12.5 of [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF]). For a subgraph H ⊆ K n,d , the polytope Q H is a n+d-2 dimensional simplex if and only if H is a spanning tree of K n,d . All n + d -2 dimensional simplices of this form have the same volume If we look at the triangulation in Figure 1, one of the simplices is a convex hull of e 1 -e1, e 1 -e3, e 2 -e1, e 2 -e2. This is encoded as a spanning tree in Figure 2 having edges (1, 1), (1, 3), (2, 1), (2, 2). We express this tree as (13, 12), standing for the fact that the first left vertex is connected to first and third vertex (13) on the right, and the second right vertex is connected to first and second (12) vertex on the right.

1 (n+d-2)! .
Lemma 2.2 tells us that a triangulation of ∆ n-1 × ∆ d-1 is a collection of simplices {Q T1 , . . . , Q Ts }, for some spanning trees T 1 , . . . , T s of K n,d such that Q K n,d = ∪Q Ti and each intersection Q Ti ∩ Q Tj is the common face of the two simplices. Lemma 2.2 combined with Theorem 12.2 of [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF], implies that:

Lemma 2.3. A triangulation of ∆ n-1 ×∆ d-1 contains exactly n+d-2 d-1 of n+d-2 dimensional simplices.
For two spanning trees T and T of K n,d , let U (T, T ) be union of edges of T and T with edges of T oriented from left to right and edges of T oriented from right to left. A directed cycle is a sequence of directed edges (i 1 , i 2 ), (i 2 , i 3 ), . . . , (i k-1 , i k ), (i k , i 1 ) such that all i 1 , . . . , i k are distinct. We say that T and T are compatible if the directed graph U (T, T ) has no directed cycles of length ≥ 4, and incompatible if not. An example is given in Figure 3. The pair on the right is incompatible, since we get a cycle (1, 1), ( 1, 2), (2, 2), ( 2, 1) (Here we write the right vertices as 1, 2, 3) which alternates between the edges of the two trees. Combining Lemma 12.6, Definition 12.7, Lemma 12.7 of [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF], we get the following: Proposition 2.4. A collection of spanning trees of K n,d encodes a triangulation of ∆ n-1 × ∆ d-1 if and only if it satisfies the following two conditions:

• The collection contains exactly n+d-2 d-1 number of spanning trees.

• Any pair inside the collection is compatible.

An example of such collection of spanning trees of K 3,3 is given in Figure 4. Any pair of trees inside the collection is compatible, and there are correct number of trees. Hence this collection encodes a triangulation of ∆ 2 × ∆ 2 , where each spanning tree corresponds to a simplex inside the triangulation. The picture in the middle is a mixed subdivision of 3∆ 2 which corresponds to the triangulation via the Cayley trick. For details on the connection between mixed subdivisions of n∆ d-1 and ∆ n-1 × ∆ d-1 , please refer to [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF] or [START_REF] Oh | Triangulations of product of two simplices and matching ensembles[END_REF].

Extracting matchings from a triangulation

Given two sets A and B of equal cardinality, the matching is a bijection between A and B. We think of this as a bipartite graph, with left vertex set A and right vertex set B, and edge set given by the set of edges (a, π(a)) where π is the bijection between A and B. Given a collection of spanning trees that encodes a triangulation of ∆ n-1 × ∆ d-1 , let us collect all matchings that appears as a subgraph in any of the trees of the collection. For example, the matchings we get from Figure 1 A collection of matchings obtained from Figure 4 would consist of all edges of K 3,3 and the matchings that appear in Figure 6.

In the next section, we are going to show that we can classify the collection of matchings coming from triangulations, and give an explicit axiomatic system for them. The collection of matchings that satisfy the axiom (hence will correspond to a triangulation) will be called a Matching Ensemble.

Matching Ensemble

In this section, we will define matching ensembles. To do so, we will borrow the notion of matching fields and linkage axiom which was used in [START_REF] Bernstein | Combinatorics of maximal minors[END_REF]. Although the matching fields used in [START_REF] Bernstein | Combinatorics of maximal minors[END_REF] Definition 4.1. We say that a collection M of matchings between subsets of [n] and subsets of [d] forms a matching field (with parameters (n, d)) if it satisfies the following two axioms:

• There is exactly one matching for any pair

I ⊆ [n], J ⊆ [d] such that |I| = |J|.
• Let M be a matching between I and J. Let M be a matching obtained by taking a subgraph of M .

Then M is also in M.

If a matching field M also satisfies the following axioms, we call it a matching ensemble:

(left linkage) Let M be a matching between I and J in M. Pick any v ∈ [n] \ I. Then there is an edge (i, j) ∈ M that we can replace with (v, j) to get another matching M in M.

(right linkage) Let M be a matching between I and J in M. Pick any v ∈ [d] \ J. Then there is an edge (i, j) ∈ M that we can replace with (i, v) to get another matching M in M.

The collection of matchings described in Figures 5 and6 are examples of matching ensembles.

Theorem 4.2. The extraction method described in the previous section is actually a bijection between triangulations of ∆ n-1 × ∆ d-1 and (n, d)-matching ensembles.

The proof of this theorem is quite technical, and will be omitted in this extended abstract. Matching Ensemble is a powerful tool for dealing with triangulations of ∆ n-1 × ∆ d-1 . For example, [START_REF] Ceballos | Dyck path triangulations and extendability[END_REF] recently solved an extendability problem on triangulations by using our model of Matching Ensembles. There is an interesting conjecture by Santos:

Conjecture 4.3 [START_REF] Santos | The Cayley trick and triangulations of products of simplices[END_REF]). Fix n and d and consider ∆ n-1 × ∆ d-1 . Any two triangulations of this polytope are connected by a sequence of flips.

We say that there is a flip between two triangulations, if these two triangulations have a common subdivision and the only triangulations obtained by refining that subdivision is the two we started with. If one considers the case when d = 3, this corresponds to the usual flips of triangular and rhombus tiles [START_REF] Ardila | Flag arrangements and triangulations of products of simplices[END_REF]. This is considered a very hard problem, since the usual model of describing triangulations via collection of spanning trees does not capture flips efficiently. In order to solve this conjecture using matching ensembles, we would first need to work on the following problems: Question 4.4. Can we describe subdivisions of ∆ n-1 × ∆ d-1 using a model similar to matching ensembles?

Answering this question would give us an insight on what operation of matchings would correspond to flips of triangulations, and possibly lead to a proof of Santos's conjecture.

  1365-8050 c 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France 2 Triangulation of ∆ n-1 × ∆ d-1

Fig. 2 :

 2 Fig. 2: Spanning tree of K2,3 which encodes the simplices in Figure 1.

Fig. 3 :

 3 Fig.3: The pair to the left is compatible. The pair to the right is incompatible.

Fig. 4 :

 4 Fig.4: A collection of spanning trees of K3,3 that encodes a triangulation of ∆2 × ∆2.

Fig. 5 :

 5 Fig. 5: A collection of matchings obtained from Figure 2.

Fig. 6 :

 6 Fig. 6: A collection of matchings obtained from Figure 4. Only the matchings of size > 1 are listed.

  only concerns d-by-d matchings, we extend the definition

	0 0 1 1 00 1 00 00 11 11 00 00 00 11 11 11 2 11 3	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 1 11 2 3	00 00 00 11 11 11 00 00 00 11 11 11 0 0 1 1	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11	0 0 1 1 00 00 00 11 11 11 00 00 00 11 11 11	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11	0 0 1 1 00 00 00 11 11 11 00 00 00 11 11 11	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11
			0 0 1 1 00 00 00 11 11 11 00 00 00 11 11 11	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11	0 0 1 1 00 00 00 11 11 11 00 00 00 11 11 11	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11	0 0 1 1 00 00 00 11 11 11 00 00 00 11 11 11	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11
			0 0 1 1 00 00 00 11 11 11 00 00 00 11 11 11	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11	0 0 1 1 00 00 00 11 11 11 00 00 00 11 11 11	00 00 00 11 11 11 00 00 00 11 11 11 00 00 00 11 11 11	0 0 1 1