Soojin Cho

Kyoungsuk Park

Alignments, crossings, cycles, inversions, and weak Bruhat order in permutation tableaux of type

Keywords: Alignments, crossings, cycles, inversions, and weak Bruhat order in permutation tableaux permutation tableaux of type B, alignment, crossing, inversion, Bruhat order, Coxeter group of type B, signed permutation

Introduction

There have been a great deal of work on permutation tableaux since they were introduced [START_REF] Steingrímsson | Permutation tableaux and permutation patterns[END_REF], in many different directions([Nad11, Bur07, CW07b, CW07a, CN09, CL11, CSSW12, CK11, CJVK13]). Permutation tableaux are in bijection with permutations and therefore provide another point of view to look at permutations in various types. Some statistics on (signed) permutations are very well understood in permutation tableaux (of type B), and statistics naturally defined on permutation tableaux make it possible to develop further combinatorial theories on Coxeter groups.

The inversion number of a signed permutation gives the length when we consider the signed permutation as an element in the corresponding Coxeter group of type B, and hence it plays an essential role to understand the Bruhat order on the Coxeter groups. However, there is no known way to understand inversions directly in the permutation tableaux. In the present article, we realize the inversion number and the covering relation in weak Bruhat order on Coxeter groups of type B, directly from the permutation tableaux of type B (Theorem 15, Theorem 13). Inversion numbers are closely related to alignments and crossings, which are relatively new statistics introduced by S. Corteel in [START_REF] Corteel | Crossings and alignments of permutations[END_REF] for (signed) permutations, and we start our work by closely looking at the alignments and crossings in permutation tableaux of type B. We prove an equation that writes the sum of alignments and crossings in terms of weak excedances and negatives in Theorem 7, which resolves a problem (open problem 3) posed by Corteel et al. in [START_REF] Corteel | Crossings of signed permutations and q-Eulerian numbers of type B[END_REF]. We also show that the number of cycles of a signed permutation counts the number of certain 1's in the corresponding bare tableau of type B. We make a remark that our works on permutation statistics have been known for the cases of type A (see Proposition 3), and we extend the results to cases of type B. The work on weak Bruhat order in permutation tableaux is new in both types A and B.

The present article is organized as follows: In Section 2 we introduce necessary notions and known results on signed permutations and permutation tableaux of type B. Alignments and crossings of signed permutations are understood in permutation tableaux of type B in Section 3, and the number of cycles of a signed permutation is realized in the corresponding bare tableau of type B in Section 4. In Section 5, we understand the inversion numbers and hence the weak Bruhat order in terms of permutation tableaux of type B.

Preliminaries

A signed permutation σ of length n is a permutation on [±n] = {±1, . . . , ±n} satisfying σ(-i) = -σ(i) for i ∈ [n] = {1, . . . , n}. The group of signed permutations is denoted by S B n , and the subgroup of (ordinary) permutations in S B n is denoted by

S n . One line notation σ = σ 1 , • • • , σ n of σ ∈ S B n means that σ(i) = σ i for i ∈ [n]. In cycle notation we write σ = (a 1,1 , • • • , a 1,k1 ) • • • (a m,1 , • • • , a m,km )
where {|a 1,1 |, . . . , |a 1,k1 |}, . . ., {|a m,1 |, . . . , |a m,km |} are mutually disjoint subsets of [n], to mean that σ(|a i,j |) = a i,j+1 with the convention a i,ki+1 = a i,1 for each i. If i k i = n then the given cycle notation is called the full cycle notation. Note that a single cycle (a) ∈ S B n is the signed permutation σ such that σ(|a|) = a fixing all other elements. Hence, if a > 0 then (a) is the identity permutation and we usually omit (a). For example, τ = -1, 2, 3 ∈ S B 3 is the signed permutation such that τ (1) = -1, τ (2) = 2, and τ (3) = 3, and (-1) is a cycle notation and (-1)(2)(3) is the full cycle notation of τ .

We give definitions of some statistics on signed permutations. Let σ ∈ S B n . i ∈ [n] is a weak excedance of σ if σ(i) ≥ i and the number of weak excedances of σ is denoted by wex(σ). i ∈ [n] is a drop of σ if σ(i) < i and the number of drops of σ is denoted by drop(σ). Note that wex(σ) + drop(σ) = n for all σ ∈ S B n . The number of negative integers in the one line notation of σ is denoted by neg(σ) and the number of cycles in the full cycle notation of σ is denoted by cyc(σ).

Corteel introduced alignments and crossings on permutations in [START_REF] Corteel | Crossings and alignments of permutations[END_REF], and they were also defined for signed permutations in [START_REF] Corteel | Crossings of signed permutations and q-Eulerian numbers of type B[END_REF]. We use the same definition of crossings and redefine alignments for signed permutations. Our definition of alignments is consistent with the one in [START_REF] Corteel | Crossings and alignments of permutations[END_REF] for permutations in S n .

Definition 1 Let σ ∈ S B n and i, j ∈ [n].

• (i, j) ∈ A nest if -i < -j < -σ(j) < -σ(i), -i < j ≤ σ(j) < -σ(i), or i < j ≤ σ(j) < σ(i). • (i, j) ∈ A EN (σ) if -i < 0 < -σ(i) < σ(j) < j or i ≤ σ(i) < σ(j) < j. • (i, j) ∈ A N E (σ) if σ(i) < i < j ≤ σ(j). • (i, j) ∈ C(σ) if i < j ≤ σ(i) < σ(j), -i < -j < -σ(i) < -σ(j), or -i < j ≤ -σ(i) < σ(j).
We

For positive integers k ≤ n, a (k, n)-diagram is a left-justified diagram of boxes in a k × (n -k) rectangle with λ i boxes in the ith row, where λ 1 ≥ λ 2 ≥ • • • ≥ λ k ≥ 0. A shifted (k, n)-diagram is a (k, n)-diagram
together with the stair shaped array of boxes added above, where the jth column (from the left) has (n -k -j + 1) additional boxes for j ∈

[n -k]. We call the (unique) (k, n)-diagram in a shifted (k, n)-diagram the (k, n)-subdiagram, and the (n -k) topmost boxes in a shifted (k, n)-diagram diagonals. See Figure 1.
We label the rows and columns of a (k, n)-diagram as follows: From the northeast corner to the southwest corner, follow the southeast border edges of the diagram and give labels 1, 2, . . . , n in order. If a south edge earned the label i then we label the corresponding column with i, and if an east edge earned the label j then we label the corresponding row with j. We put the labels on the left of each row and on the top of each column. For a shifted (k, n)-diagram, label the rows and columns of the (k, n)-subdiagram with the numbers in [n] first. Then label the remaining rows as follows; if the diagonal in a row is in the column labeled i, then we label the row with -i. We usually put the label on the left of each row and omit the column labels. We use row i, i ∈ [±n], to denote the row labeled by i and col j for the column labeled by j. See Figure 1. A permutation tableau of type B is a (0, 1)-filling of a shifted (k, n)-diagram that satisfies the following conditions:

(1) Every column has at least one 1.

(2) ( -condition or 1-hinge condition) A box with a 1 above it in the same column and a 1 to the left in the same row has a 1.

(3) If a diagonal has a 0, then there is no 1 in the same row.

A bare tableau of type B is a (0, 1)-filling of a shifted (k, n)-diagram that satisfies the previous conditions (1) and (3), and the following condition instead of (2):

(2') (0-hinge condition) A box with a 1 above it in the same column and a 1 to the left in the same row has a 0.

Permutation tableaux (or bare tableaux) of type A are permutation tableaux (or bare tableaux, respectively) of type B such that the diagonals are filled with all 0's. The length of any filling of a (shifted

) (k, n)- diagram is n.
The set of permutation tableaux of type B (or type A) of length n is denoted by PT B n (or PT n , respectively) and the set of bare tableaux of type B (or type A, respectively) of length n is denoted by BT B n (or BT n , respectively). As in [START_REF] Steingrímsson | Permutation tableaux and permutation patterns[END_REF], we can represent a permutation tableau of type B in a different way; fill in the boxes outside the diagram (within the k × (n -k) rectangle) with 2's; see Figure 2. We call this representation the extended representation of T . (1) if i is the label of a row of T , then ζ(T )(i) is the label of the row or the column that the zigzag path from row i ends,

1 -8 0 -6 1 -5 1 -3 0 1 1 2 0 4 1 7 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 -8 0 -6 1 -5 0 -3 1 1 1 2 0 4 1 7 0 0 0 1 0 1 1 1 0 0 0 1 0 0 1 -8 0 -6 1 -5 1 -3 0 1 1 2 0 4 1 7 0 1 1 0 1 1 2 1 1 0 1 1 2 1 1 1 2 2
(2) if -i is the label of a row of T and row (-i) has 0 in its diagonal, then ζ(T )(i) is the label of the row or the column that the zigzag path from col i ends, and

(3) if -i is the label of a row of T and row (-i) has 1 in its diagonal, then ζ(T )(-i) is the label of the row or the column that the zigzag path from row (-i) ends.

The zigzag map ζ bare : BT B n → S B n is defined in the same way. Zigzag maps ζ and ζ bare are described in Figure 3. Definition 2 Let T ∈ PT B n . There are three types of zeros in T . Note that there are two zigzag paths passing through a given 0, one passing vertically and the other passing horizontally.

1 -8 EE -6 1 -5 1 -3 EE 1 2 EE 4 1 7 0 1 1 EE 1 1 1 1 EE 1 1 1 1 1 1 2 1 -8 EE -6 1 -5 1 -3 EE 1 1 2 EE 4 1 7 0 1 1 EE 1 1 1 1 EE 1 1 1 1 1 6 1 1 EE -6 1 -5 1 -3 EE 1 1 2 EE 4 1 7 0 1 1 EE 1 1 1 1 EE 1 1 1 1 1 -8 3
• A 0 in T is of type EE if two zigzag paths passing through the 0 are both from rows of T . The number of 0's of type EE in T is denoted by zero EE (T ).

• A 0 in T is of type N N if two zigzag paths passing through the 0 are both from columns of T . The number of 0's of type N N in T is denoted by zero N N (T ).

• A 0 in T is of type EN if it is not in a zero row labeled by a negative integer and a zigzag path passing through the 0 is from a row and the other is from a column of T . The number of 0's of type EN in T is denoted by zero EN (T ).

A 0 in T is non-typed if it is not given a type of EE, N N , or EN . The number of typed 0's in T is denoted by zero(T ) = zero EE (T ) + zero N N (T ) + zero EN (T ), and the numbers of 1's and 2's in the extended representation of T are denoted by one(T ) and two(T ), respectively.

Note that a 0 in a zero row labeled by a negative integer is either of type EE or non-typed, and nontyped 0's appear only in zero rows labeled by a negative integer. The definition of zero(T ) is consistent with the one for permutation tableaux of type A, which is given in [START_REF] Steingrímsson | Permutation tableaux and permutation patterns[END_REF]. It is easy to see that the number of non-typed 0's in the zero row row (-i), i ∈ [n], is the number of zero rows above row (-i), including row (-i) itself. We use EE, N N , or EN to denote 0's of corresponding types in permutation tableaux for convenience.

We introduce some statistics on permutation tableaux or bare tableaux of type B. Let T be a permutation tableau or a bare tableau of type B. A 1 is a doubly essential one of T if it is both the topmost 1 in its column and the leftmost 1 in its row, and the number of doubly essential ones of T is denoted by dess(T ). A 1 is a superfluous one of T if it is not the topmost 1 in its column, and the number of superfluous ones of T is denoted by so(T ). The number of rows of T with 'positive labels', is denoted by row(T ) and the number of zero rows (filled with all 0's) of T with 'positive labels' is denoted by zerorow(T ). It is easy to see that each zero row of T ∈ PT

Lemma 5 Let T = ζ -1 (σ) or T = ζ -1 bare (σ) for σ ∈ S B n . Then for i ∈ [n],
i is a weak excedance of σ if and only if i is a row label of T , i is a drop of σ if and only if (-i) is a row label of T , and σ(i) < 0 if and only if (-i) is a row label of T and the diagonal of row (-i) is filled with a 1.

Alignments and crossings in permutation tableaux of type B

In this section, we understand the alignments and crossings of signed permutations in their corresponding permutation tableaux of type B. We remark that two zigzag paths in a permutation tableau of type B crossing at a 0 never cross again at another 0 due to the -condition. The following proposition refines and generalizes the result in [START_REF] Steingrímsson | Permutation tableaux and permutation patterns[END_REF] Proof (sketch): For each inequality of the definition of alignments, we consider two zigzag paths from columns or rows in a (or an extended) permutation tableau. Then, two paths cross at unique 0 in each case. P

We prove a theorem for the sum of alignments and crossings of a signed permutation, which extends the result on permutations by Corteel in [START_REF] Corteel | Crossings and alignments of permutations[END_REF].

Theorem 7 Let σ ∈ S B n . Then, al(σ) + cr(σ) = (n -wex(σ))(wex(σ) -1 + neg(σ)) - neg(σ) 2 . (8)
Proof (sketch): In the extended representation of T , there are n

+ (n -1) + • • • + (n -col(T ) + 1)
boxes and this is equal to zero(T ) + two(T ) + one(T ) plus the number of non-typed zeros in T . It is not hard to see that there are inversion of σ, if i < j and σ(i) > σ(j), or i ≤ j and σ(-i) > σ(j). The number of inversions of σ is denoted by inv(σ) and it is well known that (σ) = inv(σ). (See Proposition 8.1.1 in [START_REF] Björner | Combinatorics of Coxeter groups[END_REF].) The covering relation in weak Bruhat order on S B n is defined as follows; for σ, σ ∈ S B n , σ covers σ, denoted by σ ¡ σ , if σ = σs i for some i ∈ {0, 1, . . . , n -1} and (σ ) = (σ) + 1.

1 + • • • + (col(T ) -diag(T )) non-
Our main goal is to illustrate the covering relations in weak Bruhat order on S B n in terms of permutation tableaux of type B: Suppose that σ ¡ σ in S B n and let T = ζ -1 (σ) and T = ζ -1 (σ ). Then σ = σ s i for some i ∈ {0, 1, . . . , n -1} and (σ ) = (σ) + 1. We will describe how T and T are related.

(WB1): If s i = s 0 , then σ (1) is negative and T is easily obtained by adding one diagonal with 1; see Figure 6.

If s i = s 0 , then we have following five cases to consider. (WB2): σ(i) < i and σ(i + 1) ≥ i + 1: See Figure 6. (WB3): σ(i) = i and σ(i + 1) ≥ i + 1: See Figure 6. (WB4): σ(i) > i and σ(i + 1) > i + 1: We consider two types for (WB4). See Figure 7. (WB5): 0 < σ(i) < i and 0 < σ(i + 1) < i + 1: We consider two types for (WB5). See Figure 8. (WB6): σ(i) < 0 < i and σ(i + 1) < i + 1: We have two types for (WB6) depending on the sign of σ(i + 1). See Figure 9.

T 1 T -1 1 T i + 1 i T 1 i i + 1 T 0 • • • 0 i * • • • * i + 1 T * • • • * i row (i + 1) of T i + 1 0 • • • 0 0 0 1 0
T = 1 i i + 1 T = EE i i + 1 T = i i + 1 ••• ••• 0 0 1 1 1 1 T = i i + 1 ••• ••• 1 1 1 EE 0 0
Remark 12 In cases (WB5-1), (WB5-2), and (WB6-2), it is possible for us to have a zero column col i, and hence a zero row row (-i) as a result. In this case, delete col i and row (-i) and insert the new zero row row i instead in the resulting permutation tableau. For example, consider σ = -4, 1, 2, -3 ∈ S B 4 and σ = σs 2 £ σ. This is case (WB5-1), and col 2 in T is a zero column and row (-2) is a zero row. Thus we insert row 2 with all 0's, while deleting col 2 and row (-2) to make T a permutation tableau; see Figure 10.

T = 1 i + 1 i T = NN i + 1 i T = 0 1 • • • 0 1 • • • 1 1 i + 1 i T = 1 NN • • • 1 0 • • • 1 0 i + 1 i
Fig. 8: (WB5-1) and (WB5-2).

T = From the arguments that we have developed above, we can classify the covering relations in weak Bruhat order on S B n in terms of permutation tableaux of type B and also can prove a theorem on the inversion number of signed permutations. We considered all possible cases in which σ ¡ σ holds, and we can conclude as follows:

1 1 1 -(i + 1) -i T = 1 1 EE -(i + 1) -i T = -(i + 1) -i ••• ••• 0 0 0 1 1 1 1 T = -(i + 1) -i ••• ••• 1 1 1 EE 0 0 0 Fig. 9: (WB6-1) and (WB6-2). 1 -4 EE -3 EE -2 1 -1 0 0 1 0 1 1 T = -→ 1 -4 EE -3 EE -2 1 -1 0 0 1 0 NN 1 T = 1 -4 EE -3 1 -1 EE 2 0 1 EE 1 =
Theorem 13 For T , T ∈ PT B n , and corresponding signed permutations σ = ζ(T ), σ = ζ(T ), σ covers σ in weak Bruhat order if and only if T and T are in one of the relations; (WB1), (WB2), (WB3), (WB4-1), (WB4-2), (WB5-1), (WB5-2), (WB6-1), and (WB6-2) with some modification of zero column as in Remark 12.

Example 14 Let σ = -2, -4, 5, 3, 1 ∈ S B 5 and T = ζ -1 (σ) as in Example 9. We also let σ i = σs i and T i = ζ -1 (σ i ) for i ∈ {0, 1, 2, 3, 4}. Since the pair (2, 3) is not an inversion of σ, and the pairs (1, 2), (3, 4), (4, 5) are inversions of σ, σ ¡ σ 2 and σ j ¡ σ for j = 0, 1, 3, 4. The covering relations in weak Bruhat order of the corresponding permutation tableaux of type B are shown in Figure 11.

From Theorem 13 and induction on length of a signed permutation, we have following theorem. (16)

T 0 = 0 -5 0 -4 1 -2 EE 1 1 3 0 NN EN 1 1 1 T 1 = 0 -5 0 -4 1 -2 1 -1 1 3 0 NN EN 1 1 1 1 T 3 = 0 -5 1 -2 EE -1 EE 3 1 4 1 1 1 T 4 = 0 -5 0 -4 1 -2 EE -1 1 3 0 1 EN 1 1 1 1 T = 0 -5 0 -4 1 -2 EE -1 1 3 0 NN EN 1 1 1 1 T 2 = 0 -5 0 -4 1 -3 EE -1 1 2 0 NN EN 1 1 1 1 1 (WB1) (WB4-1) (

Fig. 1 :

 1 Fig. 1: A (4, 9)-diagram and a shifted (4, 9)-diagram with labelings.

Fig. 2 :

 2 Fig. 2: The permutation tableau, the bare tableau of type B, and the extended representation of the permutation tableau of type B corresponding to the signed permutation 2, 7, -5, 6, -4, 1, 8, -3. E. Steingrímsson and L. Williams defined a bijective zigzag map Φ : PT n → S n in [SW07] and it was extended to ζ : PT B n → S B n by Corteel and J. Kim in [CK11]. A bijective zigzag map Φ bare : BT n → S n was defined ([Bur07, Nad11, CK11]) and it can be naturally extended to a bijection ζ bare : BT B n → S B n .For a permutation tableau T of type B, a zigzag path from row j (or col i) in T , is the path starting from the left of row j (or the top of col i, respectively), moving east (or south, respectively) until it meets the right of a row or the bottom of a column where it changes the direction to either south or east whenever it meets a 1. Then the zigzag map ζ : PT B n → S B n is defined as follows: For T ∈ PT B n

Fig. 3 :

 3 Fig. 3: Zigzag maps in permutation tableaux of type B.

  B n (or T ∈ BT B n ) with positive label is corresponding to a fixed point of ζ(T ) (or ζ bare (T ), respectively). Certain statistics on permutation tableaux and bare tableaux (of type B) correspond to statistics on (signed) permutations through the zigzag maps ζ and ζ bare : Proposition 3 ([SW07, Bur07]) 1. For T ∈ PT n , wex(ζ(T )) = row(T ), cr(ζ(T )) = so(T ), al nest (ζ(T )) + al EN (ζ(T )) = zero(T ), and al N E (ζ(T )) = two(T ), 2. For T 0 ∈ BT n , cyc(ζ bare (T 0 )) = dess(T 0 ) + zerorow(T 0 ). Proposition 4 ([CK11, CJVK13]) For T ∈ PT B n , wex(ζ(T )) = row(T ), and cr(ζ(T )) = so(T ). We show that al nest (ζ(T )) + al EN (ζ(T )) = zero(T ) and al N E (ζ(T )) = two(T ) also hold for a permutation tableau T of type B in Section 3. Further, we prove that cyc(ζ bare (T 0 )) = dess(T 0 ) + zerorow(T 0 ) also holds for a bare tableau T 0 of type B in Section 4. The following lemma is clear from the definition of ζ and ζ bare , and Proposition 4.

  (see Theorem 14) to type B. Proposition 6 Let T ∈ PT B n . Then, al nest (ζ(T )) = zero EE (T ) + zero N N (T ), al EN (ζ(T )) = zero EN (T ), and al N E (ζ(T )) = two(T ).

  typed 0's and the number of superfluous 1's is col(T ). Then, we can obtain the equation of the theorem. P Since neg(σ) = 0 for σ ∈ S n , the equation 8 becomes al(σ) + cr(σ) = (n -wex(σ))(wex(σ) -1) which is Proposition 5 in [SW07]. A similar equation in Theorem 7 is proved by Corteel et al. (Proposition 4.3 in [CJVK13]) using pignose diagram, and it is posed as an open problem to give a proof of the proposition using permutation tableaux of type B. Our proof of Theorem 7 refines the equation and resolves the problem of Corteel et al. in [CJVK13].

Fig. 6 :

 6 Fig. 6: (WB1), (WB2), and (WB3).

Fig. 7 :

 7 Fig. 7: (WB4-1) and (WB4-2).

Fig. 10 :

 10 Fig. 10: Modify T by deleting col2 and row(-2), and inserting a zero row with labeling 2.

Theorem 15

 15 Let σ ∈ S B n and T = ζ -1 (σ) ∈ PT B n , then (σ) = inv(σ) = 2{zero EE (T ) + zero N N (T )} + one(T ).

Fig. 11 :

 11 Fig. 11: All covering relations in weak Bruhat order including T .

  let al nest (σ) = |A nest (σ)|, al EN (σ) = |A EN (σ)|, and al N E (σ) = |A N E (σ)|. We also let al(σ) = al nest (σ) + al EN (σ) + al N E (σ) be the number of alignments of σ and cr(σ) = |C(σ)| be the number of crossings of σ.

† This is an extended abstract of the full research paper [CP15]. ‡ This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education(NRF2011-0012398).

Example 9 Let T = ζ -1 (σ) for σ = -2, -4, 5, 3, 1 ∈ S B 5 . We have al nest (σ) = 2, al EN (σ) = 1, al N E (σ) = 2, and cr(σ) = 2. The extended representation of T is in Figure 4 and we have zero EE (T ) = 1, zero N N (T ) = 1, zero EN (T ) = 1, and two(T ) = 2. Hence, al nest (σ) = zero EE (T )+zero N N (T ) = 2, al EN (σ) = zero EN (T ) = 1, and al N E (σ) = two(T ) = 2. Moreover, since wex(σ) = 1 and neg(σ) = 2, we can check that al(σ) + cr(σ) = (5 -1)(1 -1 + 2) -2 2 = 7.

Fig. 4: The extended representation of T = ζ -1 (σ) where σ = -2, -4, 5, 3, 1.

Signed permutations and bare tableaux of type B

In this section, we prove a theorem on the number of cycles of signed permutations, which extends a theorem by A. Burstein (Theorem 4.2 in [START_REF] Burstein | On some properties of permutation tableaux[END_REF]).

Proof (sketch): Let σ = ζ bare (T ). We draw a forest of (binary) trees inside T ; 1's become vertices and two 1's are connected by an edge if they are adjacent vertices in a same row or in a same column, as it was done in [START_REF] Aval | Tree-like tableaux[END_REF]. Each positively labeled zero row in T is bijectively corresponding to an identity cycle (i). Moreover, each (connected) tree has a unique doubly essential 1 of T , and we can show that each tree is bijectively corresponding to a non-identity cycle in the full cycle notation of σ. P

Example 11 For T ∈ BT B 5 in Figure 5, we have dess(T ) = 2 and zerorow(T ) = 1. The corresponding signed permutation of T is σ = (1)(-2, 5, 4)(-3) in the full cycle notation, hence, cyc(σ) = 3.

Fig. 5: The bare tableau T corresponding to σ = (1)(-2, 5, 4)(-3).

Weak Bruhat order on Coxeter system of type B

In this section, we consider the weak Bruhat order on Coxeter system of type B in terms of permutation tableaux of type B. The group S B n with generators s 0 , s 1 , . . . , s n-1 forms the Coxeter system of type B, where s 0 = (-1), s i = (i, i + 1) for i ∈ [n -1] in cycle notation. The length of σ ∈ S B n , denoted by (σ), is defined as the minimum of k such that σ = s a1 . . . s a k . A pair (i, j) ∈ [n] × [n] is called an


Emily Barnard
email: esbarnar@ncsu.edu.

Nathan Reading
email: reading@math.ncsu.edu.

Coxeter-biCatalan combinatorics

Keywords: alternating arc diagram, doubled root poset, twin nonnesting partitions, twin sortable elements

We consider several counting problems related to Coxeter-Catalan combinatorics and conjecture that the problems all have the same answer, which we call the W -biCatalan number. We prove the conjecture in many cases.

Résumé. Nous considérons des problèmes énumératifs liés à la combinatoire de Coxeter-Catalan et conjecturons que tous les problèmes ont la même solution, que nous appelons le nombre W -biCatalan. Nous prouvons la conjecture dans de nombreux cas.

Introduction

This extended abstract considers enumeration problems closely related to Coxeter-Catalan combinatorics. (For background on Coxeter-Catalan combinatorics, see for example [START_REF] Armstrong | Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups[END_REF][START_REF] Fomin | Root systems and generalized associahedra[END_REF]). Each enumeration can be thought of as counting pairs of two "twin" Coxeter-Catalan objects. We now pose counting problems in several of the usual settings of Coxeter-Catalan combinatorics. The counting problems are conjectured to have the same answer in all of the settings. As we pose the problems, we discuss to what extent this conjecture is known. Most of the terms used below are new and will be explained later.

In the setting of sortable elements and Cambrian lattices/fans, the enumeration problem is to count

• maximal cones in the bipartite biCambrian fan (the common refinement of two bipartite Cambrian fans);

• pairs of twin c-sortable elements for bipartite c;

• classes in the bipartite biCambrian congruence (the meet of two bipartite Cambrian congruences);

• elements of the c-biCambrian lattice for bipartite c; or • c-bisortable elements for bipartite c.

In type A, c-bisortable elements for bipartite c are in bijection with certain pattern-avoiding permutations and with alternating arc diagrams. In type B, similar bijections exist with certain signed permutations and with centrally symmetric alternating arc diagrams. All of the objects listed above make sense for non-bipartite c, but the enumeration depends on the choice of c. We focus here on the bipartite choice.

In the setting of nonnesting partitions (antichains in the root poset), the enumeration problem is to count

• antichains in the doubled root poset.

Theorem 1.1 For crystallographic W , c-bisortable elements for bipartite c are in bijection with antichains in the doubled root poset. More specifically, for each k, the number of bipartite c-bisortable elements with k descents equals the number of k-element antichains in the doubled root poset.

Some of the enumerations and descent generating functions of bipartite c-bisortable elements are shown here. At present we have no conjectured formula the type-D descent generating functions.

A In the setting of clusters of almost positive roots (in the sense of [START_REF] Fomin | Y -systems and generalized associahedra[END_REF]), the problem is to count two closely related families of objects:

• maximal cones in the bicluster fan (common refinement of the cluster fan and its antipodal opposite), or • pairs of twin clusters.

A bijection between sortable elements and clusters from [START_REF] Reading | Clusters, Coxeter-sortable elements and noncrossing partitions[END_REF] extends to prove the following theorem.

Theorem 1.2 For all W , c-bisortable elements for bipartite c are in bijection with pairs of twin clusters.

We prove Theorem 1.2 in Section 2.4 by quoting results of [START_REF] Fomin | Y -systems and generalized associahedra[END_REF][START_REF] Reading | Clusters, Coxeter-sortable elements and noncrossing partitions[END_REF][START_REF] Reading | [END_REF]. While there is a notion of cclusters for any Coxeter element c, we emphasize that Theorem 1.2 refers to the original definition of clusters in [START_REF] Fomin | Y -systems and generalized associahedra[END_REF], which corresponds to a bipartite choice of c. A type-A version of twin c-clusters (in a not-necessarily-bipartite sense) were considered in a recent paper by Chatel and Pilaud [START_REF] Chatel | The Cambrian and Baxter-Cambrian Hopf algebras[END_REF], in the guise of twin Cambrian trees.

In the setting of noncrossing partitions, the problem is to count

• pairs of twin bipartite c-noncrossing partitions, or • pairs of twin bipartite pc, c ´1q-noncrossing partitions.

Theorem 1.3 For all W and bipartite c, the c-bisortable elements are in bijection with pairs of twin c-noncrossing partitions and with pairs of twin pc, c ´1q-noncrossing partitions.

Although the definitions of twin bipartite c-noncrossing partitions and pairs of twin bipartite pc, c ´1qnoncrossing partitions are made specifically to make Theorem 1.3 true, they are phrased naturally in the language of noncrossing partitions. We fill in these definitions in Section 2.5. We propose the terms W -biCatalan number and W -biNarayana number for the answers to the enumerations. Naturally, one would like a uniform formula for the W -biCatalan number, but we have not found one. A tantalizing near-miss is the non-formula

ś n i"1 h`ei´1 ei
, where h is the Coxeter number and the e i are the exponents. This expression captures the W -biCatalan numbers for W of types A n , B n , H 3 , and I 2 pmq-the "coincidental types" of [START_REF] Williams | [END_REF]-but fails to even be an integer in some other types. In every case, the expression is a surprisingly good estimate of the W -biCatalan number.

The remainder of this extended abstract is devoted to filling in definitions and details for the discussion above, and giving some more details of the type-A enumeration of bipartite c-bisortable elements.

BiCatalan objects

In this section, we fill in the definitions and details behind the enumeration problems discussed in the introduction.

Antichains in the doubled root poset and twin nonnesting partitions

The root poset of a finite crystallographic root system Φ is the set of positive roots in Φ, partially ordered by setting α ď β if and only if β ´α is in the nonnegative span of the simple roots. Recall that the dual of a poset pX, ďq is the poset with the same ground set X, satisfying x ď y in the dual poset if and only if x ě y in pX, ďq. The doubled root poset consists of the root poset, together with a disjoint copy of the dual poset, identified on the simple roots. Figure 1 shows the doubled root posets of types A 5 , B 3 , and D 4 .

The antichain counts in types A and B are easy and known, in the guise of lattice path enumeration. Antichains in the doubled root poset of type A n are in an easy bijection with lattice paths from p0, 0q to pn, nq with steps p1, 0q and p0, 1q. The bijection can be made so that the number of elements in the antichain corresponds to the number of right turns in the path (the number of times a p1, 0q-step immediately follows a p0, 1q-step). To specify a path with k right turns, we need only specify where the right turns are. This means choosing 0 ď x 1 ă ¨¨¨ă x k ď n´1 and 1 ď y 1 ă ¨¨¨ă y k ď n and placing right turns at px 1 , y 1 q, . . . , px k , y k q. Thus, as is well-known, there are `n k ˘2 paths with k right turns.

Antichains in the doubled root poset of type B n are similarly in bijection with lattice paths from p´n 1, ´n `1q to pn ´1, n ´1q with steps p1, 0q and p0, 1q that are symmetric with respect to the reflection in the line y " ´x. These are in turn in bijection with self-conjugate partitions in a p2n ´1q ˆp2n ´1q box. The generating function for such partitions is ś 2n´1 i"1 p1 `q2i´1 q gives the enumeration 2 2n´1 . Remark 2.1 It is not clear in general how one should define a "root poset" for a noncrystallographic root system. (See [1, Section 5.4.1] for a discussion.) For the obvious generalization of A 2 , B 2 and G 2 in type I 2 pmq and the H 3 root poset suggested in [START_REF] Armstrong | Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups[END_REF]Section 5.4.1], one can verify that Theorem 1.1 holds in these types as well. The support of a root β is the set of simple roots appearing with nonzero coefficient in the expansion of β in the basis of simple roots. The support of a set of roots is the union of the supports of the roots in the set. We write ∆ for the simple roots and, given a set A of roots, we write A ˝for the set of non-simple roots in A. If A 1 and A 2 are nonnesting partitions (i.e. antichains in the root poset), then pA 1 , A 2 q is a pair of twin nonnesting partitions if and only if A 1 X ∆ " A 2 X ∆, and supppA 1q X supppA 2q " H.

Given an antichain A in the doubled root poset, define A 1 to be the intersection of A with the root poset that forms the top of the doubled root poset. Define A 2 to be the intersection of A with the dual root poset that forms the bottom of the doubled root poset. The following proposition is easily proved using the observation that a root β in the top part of the doubled root poset is related to a root γ in the bottom part of the doubled root poset if and only if the supports of β and γ overlap.

Proposition 2.2

The map A Þ Ñ pA 1 , A 2 q is a bijection from antichains in the doubled root poset to pairs of twin nonnesting partitons.

BiCambrian fans

The Cambrian fan is a complete simplicial fan whose maximal faces are naturally in bijection [START_REF] Reading | Clusters, Coxeter-sortable elements and noncrossing partitions[END_REF][START_REF] Reading | [END_REF] with seeds in an associated cluster algebra of finite type and with noncrossing partitions. Furthermore, the Cambrian fan is the normal fan [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF][START_REF] Hohlweg | Permutahedra and generalized associahedra[END_REF] to a simple polytope called the generalized associahedron [START_REF] Chapoton | Polytopal realizations of generalized associahedra[END_REF][START_REF] Fomin | Y -systems and generalized associahedra[END_REF], which encodes much of the combinatorics of the associated cluster algebra. The noncrossing partitions can be found as the subspaces spanned by certain faces in the Cambrian fan.

The defining data of a Cambrian fan is a finite Coxeter group W and a Coxeter element c of W . We emphasize that the results discussed earlier in the introduction concern a special "bipartite" choice of c, as explained below, but for now we proceed with a discussion for general c. A Coxeter element is the product of a permutation of the simple generators of W , or equivalently it is an orientation of the Coxeter diagram of W . For fixed W , all choices of c give distinct but combinatorially isomorphic fans. Given a choice of W , we will assume the usual representation of W as a reflection group acting with trivial fixed subspace. The collection of reflecting hyperplanes in this representation is the Coxeter arrangement of W . The hyperplanes in the Coxeter arrangement cut space into cones, which constitute a fan called the Coxeter fan F. The maximal cones of the Coxeter fan are in bijection with the elements of W . The Cambrian fan CambpW, cq is the coarsening of the Coxeter fan obtained by gluing together maximal cones according to an equivalence relation on W called the c-Cambrian congruence.

For each Coxeter element c, the inverse element c ´1 is also a Coxeter element, corresponding to the opposite orientation of the diagram. We define the biCambrian fan biCambpW, cq to be the coarsest common refinement of the Cambrian fans CambpW, cq and CambpW, c ´1q. Since CambpW, cq and CambpW, c ´1q are coarsenings of F, so is biCambpW, cq. Naturally, biCambpW, c ´1q " biCambpW, cq. To illustrate the definition, take W of type B 2 with simple generator r and s. The c ´1-Cambrian fan coincides with the image of the c-Cambrian fan under the antipodal map. This is an immediate corollary of [START_REF] Reading | Sortable elements and Cambrian lattices[END_REF]Proposition 1.3], which is a statement about Cambrian congruences. See also [START_REF] Reading | Cambrian frameworks for cluster algebras of affine type[END_REF]Remark 3.26]. Thus we have the following proposition which amounts to an alternate definition of the biCambrian fan.

Proposition 2.3 The biCambrian fan biCambpW, cq is the coarsest common refinement of CambpW, cq and ´CambpW, cq.

Since CambpW, cq and CambpW, c ´1q are the normal fans of two generalized associahedra, a standard fact (see [START_REF] Ziegler | Lectures on polytopes[END_REF]Proposition 7.12]) yields the following result.

Proposition 2.4 For any W and c, the fan biCambpW, cq is the normal fan of a polytope, specifically, the Minkowski sum of the generalized associahedra dual to CambpW, cq and CambpW, c ´1q.

The definition of biCambpW, cq seems strange a priori, but it is well-motivated a posteriori by enumerative results. The first such result was first pointed out empirically (in the language of lattice congruences) in [20, Section 10] and later proven by J. West [START_REF] West | [END_REF] and then in [START_REF] Giraudo | Algebraic and combinatorial structures on Baxter permutations[END_REF][START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF]. When W is the symmetric group S n , the Coxeter diagram of W is a path. Taking c to be the linear orientation of that path (the linear Coxeter element), the number of maximal cones in biCambpW, cq is the Baxter number

2 npn`1q 2 ř n´1 k"0 `n`1 k ˘`n`1 k`1 ˘`n`1 k`2 ˘
, the number of Baxter permutations [START_REF] Baxter | On fixed points of the composite of commuting functions[END_REF][START_REF] Chung | The number of Baxter permutations[END_REF]. Once one sees that the Baxter number counts maximal cones of biCambpW, cq for W of type A and for a particular c, it is natural to look at other types of finite Coxeter group W , with the idea of defining a "W -Baxter number" for each finite Coxeter group W . Indeed, there is a good notion of a "type-B Baxter number" discovered by Dilks [START_REF] Dilks | Involutions on Baxter Objects[END_REF]. The Coxeter diagram of type B is also a path, and taking c to be a linear Coxeter element, the maximal cones of biCambpW, cq are counted by the type-B Baxter number. Despite the nice type-B result, there seems to be little hope for a reasonable definition of the W -Baxter number, because some types of Coxeter diagrams are not paths and thus it is not clear how to generalize the notion of a linear Coxeter element.

There is, however, a choice of Coxeter element that can be made uniformly for all finite Coxeter groups. Since the Coxeter diagram of any finite irreducible Coxeter group is a tree, the diagram is in particular bipartite. Thus we can fix a bipartition S `Y S ´of the diagram and orient each edge of the diagram from its vertex in S ´to its vertex in S `. The resulting Coxeter element is called a bipartite Coxeter element, and if c is a bipartite Coxeter element of W , we call biCambpW, cq a bipartite biCambrian fan.

Proposition 2.4 says that biCambpW, cq is the normal fan of a polytope, but does not guarantee that this polytope is simple (equivalently, that this fan is simplicial). In fact, simpleness fails for the linear Coxeter element of S n , and this failure can be seen already in S 4 . (See [18, Figure 13], which shows the Hasse diagram of a lattice that coincides with the 1-skeleton of this polytope.) The situation appears to be better in the bipartite case. The following conjecture is verified in types A and B.

Conjecture 2.5 If c is a bipartite Coxeter element, then biCambpW, cq is a simplicial fan.

The biCambrian congruence, twin sortable elements, and bisortable elements

A congruence on a lattice L is an equivalence relation respecting the meet and join operations. A general fact about finite lattices (see for example [21, Section 3]) says that congruence classes are intervals in the lattice and that the quotient of a finite lattice L modulo the congruence is isomorphic to the subposet induced by the set π Ó pLq of elements that are the bottoms of their congruence classes.

The maximal cones of the Coxeter fan F, partially ordered according to a suitable linear functional, form a lattice isomorphic to the weak order on W . (This fact is true either for the right or left weak order. We will work with the right weak order.) Each Coxeter element c specifies a congruence on the weak order called the c-Cambrian congruence. (See [START_REF] Reading | Cambrian lattices[END_REF] for the definition.) For each congruence class in the c-Cambrian congruence, the union of the corresponding maximal cones in F is itself a convex cone. The collection of all these convex cones and their faces is the c-Cambrian fan CambpW, cq described earlier.

Consider the set ConpLq of all congruences on a given lattice L. The set ConpLq is itself a sublattice of the lattice of set partitions of L. In particular, the meet of two congruences is the coarsest set partition of L refining both congruences. The c-biCambrian congruence is the meet, in ConpW q, of the Cambrian congruence specified by c and the Cambrian congruence specified by c ´1. The c-biCambrian congruence classes are thus in bijection with the maximal cones of biCambpW, cq. The c-biCambrian lattice is the quotient of the weak order modulo the biCambrian congruence.

We write π c

Ó for the projection taking each element of W to the bottom element of its c-Cambrian congruence class, and similarly π c Ó pwqq for any w in the class. The twin sortable elements are similar in spirit to the twin binary trees of [START_REF] Dulucq | Stack words, standard tableaux and Baxter permutations[END_REF]. Indeed, for W of type A and c linear, the connection is implicit in the construction in [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF] of a diagonal rectangulation from a pair of binary trees. (See also [START_REF] Law | The Hopf algebra of diagonal rectangulations[END_REF]Remark 6.6].)

The bottom elements of the biCambrian congruence classes are, of course, also in bijection with the biCambrian congruence classes. We coin the term c-bisortable elements for these bottom elements. Work is in progress to give a direct combinatorial characterization of bisortable elements. Each c-bisortable element v covers some number of elements in the c-biCambrian lattice. By a general fact on lattice quotients, v covers the same number of elements in the weak order on W . This number is despvq, the number of descents of v.

A general fact about lattice quotients of the weak order [20, Proposition 3.5] implies that, when biCambpW, cq is simplicial, the descent generating function of c-bisortable elements equals the hpolynomial of biCambpW, cq.

Twin clusters and bicluster fans

In a finite root system, the almost positive roots are those roots which either are positive, or are the negatives of simple roots. In [START_REF] Fomin | Y -systems and generalized associahedra[END_REF], almost positive roots were shown to index cluster variables in cluster algebras of finite type. Furthermore, a compatibility relation was defined on almost positive roots and (combinatorial) clusters of almost positive roots were defined to be the maximal sets of pairwise compatible almost positive roots. The combinatorial clusters were shown to correspond to the (algebraic) clusters of cluster variables.

Here, we will not need either the cluster-algebraic background, nor even the definition of compatibility. (These can be found in [START_REF] Fomin | Y -systems and generalized associahedra[END_REF][START_REF] Fomin | Cluster Algebras II: Finite Type Classification[END_REF].) Rather, for our purposes it will be enough to quote some results about combinatorial clusters and their relationship to sortable elements.

First, [START_REF] Fomin | Y -systems and generalized associahedra[END_REF]Theorem 1.8] states that all clusters C are of the same size, and furthermore, each is a basis for the root space (the span of the roots). Write R ě0 C for the nonnegative linear span of C. Then [START_REF] Fomin | Y -systems and generalized associahedra[END_REF]Theorem 1.10] states that the cones R ě0 C, for all clusters C, are the maximal cones of a complete simplicial fan. We call this fan the cluster fan.

We define the bicluster fan to be the coarsest common refinement of the cluster fan and its opposite. A pair pC 1 , C 2 q of clusters is called a pair of twin clusters if the cones R ě0 C and ´Rě0 C (the nonpositive linear span of C) intersect in a full-dimensional cone. It is immediate that maximal cones in the bicluster fan are in bijection with pairs of twin clusters.

For a bipartite choice of c, [25, Theorem 9.1] says that c-Cambrian fan is linearly isomorphic to the cluster fan. Theorem 1.2 follows immediately from the bijection between c-bisortable elements and maximal cones in biCambpW, cq, from Proposition 2.3, from this linear isomorphism, and from the bijection between maximal cones in the bicluster fan and pairs of twin clusters.

In [START_REF] Marsh | Generalized associahedra via quiver representations[END_REF] (see also [START_REF] Reading | Clusters, Coxeter-sortable elements and noncrossing partitions[END_REF]Section 7]), the construction of [START_REF] Fomin | Y -systems and generalized associahedra[END_REF], which uses a bipartite Coxeter element c, was shown to generalize to arbitrary choices of c. Thus one may consider c-clusters and the c-cluster fan. However, we emphasize again that all results stated in this paper for clusters refer to the bipartite choice of c.

Twin noncrossing partitions

The absolute order on a finite Coxeter group W is the prefix order (or equivalently the subword order) on W relative to the generating set T , the set of reflections in W . (By contrast, the prefix order relative to the simple reflections S is the weak order, while and subword order relative to S is the Bruhat order.) We will use the symbol ď T for the absolute order. The c-noncrossing partitions in a finite Coxeter group W are the elements of W contained in the interval r1, cs T in the absolute order on W . For details on the absolute order and noncrossing partitions, see for example [START_REF] Armstrong | Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups[END_REF]Chapter 2].

For our purposes, the key fact is a theorem of Brady and Watt. Let W be a finite Coxeter group of rank n represented as a reflection group in R n and let T be the set of reflections of W . For each reflection t P T , let β T be the corresponding positive root. Given w P r1, cs T , define a cone Theorem 2.6 For c bipartite, the map F c is a bijection from r1, cs T to the set of maximal cones in the c-Cambrian fan.

F c pwq " x P R n : x ¨βt ď 0 @ t ď T w, x ¨βt ě 0 @ t ď T cw ´1(
The astute reader will notice a difference between our definition of F c and the definition appearing in [5, Section 1]. The set of reflections t such that t ď T w is the intersection of T with some (not necessarily standard) parabolic subgroup of W . The definition in [START_REF] Brady | From permutahedron to associahedron[END_REF] imposes inequalities x ¨βt ď 0 only for those β t that are simple roots for that parabolic subgroup. Our definition imposes additional inequalities, all of which are implied by the inequalities for the simple roots. We similarly add additional redundant inequalities of the form x ¨βt ě 0.

Theorem 2.6 suggests a definition of twin noncrossing partitions. In fact, two natural definitions suggest themselves. We call a pair v, w of elements of r1, cs T twin c-noncrossing partitions if F c pvq X p´F c pwqq is full-dimensional. Similarly, we call a pair pv, wq P r1, cs T ˆr1, c ´1s T twin pc, c ´1q-noncrossing partitions if F c pvq X F c ´1 pwq is full-dimensional. Theorem 2.6 now immediately implies Theorem 1.3.

Enumerating bipartite c-bisortable elements in type A

In this section, we describe how bipartite c-bisortable elements of type A are in bijection with certain objects called alternating arc diagrams. We then prove the type-A enumeration of bipartite c-bisortable elements by counting alternating arc diagrams.

The Coxeter group of type A n is the symmetric group S n`1 . The Cambrian congruences on S n`1 are described in detail in [START_REF] Reading | Cambrian lattices[END_REF]. As a consequence of this description, we have the following proposition describing bottom elements of c-biCambrian congruence classes (the c-bisortable elements). Proposition 3.1 For c bipartite, a permutation x " x 1 ¨¨¨x n`1 is c-bisortable if and only if, for every descent x i ą x i`1 , there exists no k with x i`1 ă k ă k `1 ă x i such that k and k `1 are on the same side of the descent (i.e. k and k `1 both left of x i or both right of x i`1 ).

The avoidance condition in Proposition 3.1 can be rephrased in the languange of generalized pattern avoidance [START_REF] Babson | Generalized permutation patterns and a classification of the Mahonian statistics[END_REF].

In order to introduce alternating arc diagrams, we review the more general noncrossing arc diagrams from [START_REF] Reading | Noncrossing diagrams and canonical join representations[END_REF]. Beginning with n `1 distinct points on a vertical line, we draw some (or no) curves called arcs connecting the points. Each arc moves monotone upwards from one of the points to another, passing either to the left or to the right of each point in between. Furthermore no two arcs may intersect in their interiors, no two arcs may share the same upper endpoint, and no two arcs may share the same lower endpoint. We consider arc diagrams only up to their combinatorics, i.e. which pairs of points are joined by an arc and which points are left and right of each arc.

Given a permutation x " x 1 ¨¨¨x n`1 in S n`1 , we define a noncrossing arc diagram δpxq. We number the n `1 points 1, . . . , n `1 from bottom to top. Each descent x i ą x i`1 in x becomes an arc α in δpxq.

For each integer a with x i`1 ă a ă x i that occurs to the left of x i in x 1 ¨¨¨x n`1 , the a th point is left of the arc α. For each integer a with x i`1 ă a ă x i that occurs to the right of x i`1 in x 1 ¨¨¨x n`1 , the a th point is right of the arc α. It was shown in [START_REF] Reading | Noncrossing diagrams and canonical join representations[END_REF]Theorem 3.1] that δ is a bijection from permutations to noncrossing arc diagrams.

An alternating arc is an arc (in the sense of noncrossing digrams) that alternates between passing left of points and passing right of points (starting either on the right or on the left). An alternating (noncrossing) arc diagram is a noncrossing arc diagram all of whose arcs are alternating. Comparing the definition of δ with Proposition 3.1, we obtain the following proposition. Proposition 3.2 For W " S n`1 and c bipartite, the restriction of δ is a bijection from c-bisortable permutations with k descents to alternating arc diagrams on n `1 points with k arcs. Figure 3 shows several alternating noncrossing arc diagrams. From left to right they are δp5371624q, δp6745231q, and δp4627531q.

To prove the type-A enumeration of bipartite c-bisortable elements, we give a bijection between pairs pS, T q of subsets of rns and noncrossing alternating arc diagrams on n `1 vertices with |S| " |T | " k arcs. We begin with the simplest and most obvious case: the bijection between diagrams with one arc and pairs pi, jq with i, j P rns. First we set some terminology.

Recall that we number the arcs 1, . . . , n `1 from bottom to top. At times it will be convenient to refer to an arc by its endpoints, in which cases we adopt the notation, σ pi,jq for an arc connecting point i to point j with i ă j. When i `1 ă j, this notation can refer to two different arcs. We say that σ pi,jq has left orientation if the arc passes to the left of the point i `1. Similarly, σ pi,jq has right orientation if the arc passes to the right of i `1. Figure 4 shows the two arcs that could be called σ p1,6q for n `1 " 6. The left picture in the figure is an arc with left orientation. The bijection from alternating arcs to pairs pi, jq with i, j P rns maps each arc σ pi,i`1q to pi, iq. Each arc σ pi,jq has either left orientation or right orientation. If the orientation is left, then the arc is mapped to pi, j ´1q, and if right, it is mapped to pj ´1, iq.

We wish to generalize this process to alternating arc diagrams with k arcs. Based on what we learned in the k " 1 case, the naïve goal, given a pair of subsets pS, T q, is the following: If the numbers in S are smaller than the numbers in T , then the numbers in S should label the lower endpoints of arcs, while the numbers in tt `1 : t P T u should label the upper endpoints in an alternating diagram. If the numbers in S are larger than the numbers in T , then ts `1 : s P Su should label upper endpoints while T labels lower endpoints. The difference between these two cases should be recorded by the orientation (left or right) of the arcs in the diagram. Specifically, we will give the lowest arc in the diagram a left orientation if the numbers in S are lower than the numbers in T .

This naïve goal will be the basis for the bijection, but as stated, it can't possibly succeed. Take for example the following pair: pt1, 4, 6u , t2, 3, 5uq. The whole set S cannot be the set of lower endpoints, since it has the largest value in S Y tt `1 : t P T u. Similarly, ts `1 : s P Su has the smallest value in ts `1 : s P Su Y T , so ts `1 : s P Su can't be the set of upper endpoints. To try to salvage the idea, we will attempt to pair each element s P S with an element t P T and draw alternating arcs with endpoints s and t `1 if s ď t or endpoints t and s `1 if t ă s in such a way that the union of the arcs is noncrossing.

Two ways to do this (listing s first in each pair) are tp1, 2q, p4, 3q, p6, 5qu and tp1, 2q, p6, 3q, p4, 5qu, with corresponding diagrams shown in Figure 5.

We first observe that to obtain a noncrossing alternating arc diagram we must pair 1 with 2. Otherwise, if we pair 1 with 3, then either 4 or 6 must be paired with 2, and either way, there is a problem, as shown in the left picture of Figure 6. Or, if we pair 1 with 5, then we cannot pair 4 with 2, as shown in the middle picture of Figure 6, and we can't pair 6 with 2, as shown in the right picture of Figure 6. Having made this observation, we see that, up to changing the orientations of some arcs, the diagrams shown in Figure 5 are the only possibilities.

But which of the two alternating arc diagrams, and with which orientations, should correspond to the pair pt1, 4, 6u , t2, 3, 5uq? To answer this question, we decompose the problem into smaller problems and then return to the naïve goal. Specifically, we notice that all of the possible arc diagrams can naturally break apart at point 3. This suggests that we break apart the subsets in a corresponding way as pS 1 , T 1 q " pt1u , t2uq and pS 2 , T 2 q " pt4, 6u , t3, 5uq. The naïve approach now sends pS 1 , T 1 q to an arc with left orientation connecting points 1 and 3. Since each number in S 2 is greater than a corresponding number in T 2 , we send pS 2 , T 2 q to an arc with right orientation connecting 3 to 5 and an arc connecting 5 to 7. The final difficulty is to determine the orientation of the arc from 5 to 7, which orientation is not specified by the naïve approach. The solution to the difficulty is to further break pS 2 , T 2 q into pt4u , t3uq and pt6u , t5uq and apply the naïve approach to each piece. We thus see that we should orient the arc from 5 to 7 with right orientation and send pS, T q to the alternating diagram shown in the left picture in Figure 5.

With the intuition gained from this example, we now describe a bijection π from alternating arc diagrams on n `1 points to pairs of subsets rns of the same size.

Let Σ be an alternating arc diagram. Let P pΣq be the set of points p P rn `1s such that no arc in Σ passes left or right of p. (A point p P P pΣq may still be an endpoint of one or two arcs.) Write P pΣq " tp 0 , . . . , p m u with p 0 ă ¨¨¨ă p m . In every case, p 0 " 1 and p m " n `1. We will define m pairs of subsets pS 1 , T 1 q, . . . , pS m , T m q. For each i, the sets S i and T i will be subsets of tp i´1 , p i´1 `1, . . . , p i ´1u and will be determined by the part of Σ between p i´1 and p i .

If p i´1 " j and p i " j `1, then either Σ has an arc connecting j to j `1 or not. If so, then set pS i , T i q " ptju , tjuq. If not, then set pS i , T i q " pH, Hq.

Suppose p i´1 " j and p i ą j `1. Since j `1 is not in P pΣq, Σ has an arc that passes left or right of j `1. But since j is in P pΣq, that arc σ must have its lower endpoint at j. Since p i , p i`1 P P pΣq, every arc in Σ having one endpoint in tp i´1 , p i´1 `1, . . . , p i u also has its other endpoint in the same set. If σ has left orientation, that is, if it passes left of j `1, then we define S i to be the set of lower endpoints of arcs in tp i´1 , p i´1 `1, . . . , p i u and define T i to be the set of numbers t ´1 such that t is the upper endpoint of an arc in tp i´1 , p i´1 `1, . . . , p i u. If σ has right orientation then we switch the definitions of S i and T i .

We define πpΣq " p Ť m i"1 S i , Ť m i"1 T i q.

Theorem 3.3 The map π is a bijection from the set of alternating arc diagrams on n `1 points to the collection of pairs of subsets rns of the same size. For each k, the bijection restricts to a bijection from alternating arc diagrams with k arcs to pairs of subsets of size k.

The proof of Theorem 3.3, and many other details, are omitted from this extended abstract.

Fig. 1 :

 1 Fig. 1: Some doubled root posets

Fig. 2 :

 2 Fig. 2: Cambrian fans and the biCambrian fan

  Figure 2 shows, from left to right, the rs-Cambrian fan, the sr-Cambrian fan, and the rs-biCambrian fan.

´1Ó

  for the c ´1-Cambrian congruence. Two elements u and v are congruent in the c-Cambrian congruence if and only if π c Ó puq " π c Ó pvq and are congruent in the c ´1-Cambrian congruence if and only if π c ´1 Ó puq " π c ´1 Ó pvq. The congruence classes for the c-biCambrian congruence are the nonempty intersections of congruence classes of the two opposite c-Cambrian congruences. This gives us a natural way to associate a pair pπ c Ó pwq, π c ´1 Ó pwqq to each c-biCambrian congruence class. Specifically, u and v are congruent in the c-biCambrian congruence if and only if π c Ó puq " π c Ó pvq and π c ´1 Ó puq " π c ´1 Ó pvq. The bottom elements of the c-Cambrian congruence are called c-sortable elements. (In fact c-sortable elements have an independent combinatorial definition [22, Section 2], but were shown to be the bottom elements of c-Cambrian congruences in [23, Theorems 1.1&1.4].) Given elements u and v of W , we define the pair pu, vq to be a pair of twin pc, c ´1q-sortable elements of W if there exists w P W such that u " π c Ó pwq and v " π c ´1 Ó pwq. The considerations of the previous paragraph show that there is a bijection between congruence classes in the biCambrian congruence specified by c and pairs of twin pc, c ´1q-sortable elements of W . The bijection maps a congruence class to pπ c Ó pwq, π c ´1

.

  The following theorem combines [5, Theorem 1.1] with[START_REF] Brady | From permutahedron to associahedron[END_REF] Theorem 5.5].

Fig. 3 :Fig. 4 : 5 : 6 :

 3456 Fig. 3: Some alternating noncrossing arc diagrams

Acknowledgments

Bruno Salvy's and Paul Zimmermann's package GFUN [28] was helpful in guessing a formula for the D n -Catalan number. John Stembridge's posets and coxeter/weyl packages [29] were invaluable in counting antichains in the doubled root poset. The authors thank Christophe Hohlweg and Salvatore Stella, and several anonymous referees for helpful suggestions.

Supported in part by NSF grant DMS-0943855. ; Supported in part by NSF grant DMS-1101568. 1365-8050


Emily Barnard
email: esbarnar@ncsu.edu.

Emily Meehan
email: emeehan@ncsu.edu.

Shira Polster
email: spolste@ncsu.edu.

Nathan Reading
email: reading@math.ncsu.edu.

Universal geometric coefficients for the four-punctured sphere (Extended Abstract)

Keywords: cluster algebra, four-punctured sphere, Null Tangle Property, universal geometric coefficients

We construct universal geometric coefficients for the cluster algebra associated to the four-punctured sphere and obtain, as a by-product, the g-vectors of cluster variables. We also construct the rational part of the mutation fan. These constructions rely on a classification of the allowable curves (the curves which can appear in quasi-laminations). The classification allows us to prove the Null Tangle Property for the four-punctured sphere, thus adding this surface to a short list of surfaces for which this property is known. The Null Tangle Property then implies that the shear coordinates of allowable curves are the universal coefficients. We compute these shear coordinates to obtain universal geometric coefficients.

Résumé. Nous construisons des coefficients géométriques universels pour l'algèbre amassée associée à la sphère privée de 4 points, et obtenons ce faisant les g-vecteurs des variables d'amas. Nous construisons aussi la partie rationnelle de l'éventail de mutation. Ces constructions reposent sur la classification des courbes admissibles (les courbes qui peuvent apparaître dans les quasi-laminations). Cette classification nous permet de prouver la "Null Tangle Property" pour la sphère privée de 4 points, ajoutant ainsi cette surface à la courte liste de surfaces pour lesquelles cette propriété est connue. La "Null Tangle Property" implique alors que les coordonnées de décalage des courbes admissibles sont les coefficients universels. Nous calculons ces coordonnées de décalage pour obtenir les coefficients géométriques universels.

Introduction

The fundamental combinatorial datum specifying a cluster algebra is an exchange matrix, an n × n skew-symmetrizable (and in the special case considered here, skew-symmetric) integer matrix B. The remaining data specifying a cluster algebra can be thought of as a choice of coefficients. We consider the broad class of cluster algebras of geometric type, in which the choice of coefficients is a collection of vectors (geometric coefficients), each with n entries. The usual definition of cluster algebras of geometric type is [4, Definition 2.12], but we work with the broader definition given in [START_REF] Reading | Universal geometric cluster algebras[END_REF]Definition 2.8]. The relationship between the two definitions is described in [START_REF] Reading | Universal geometric cluster algebras[END_REF]Remark 2.9].

γ 1 γ 1 γ 2 γ 2 γ 3 γ 4 γ 4 γ 5 γ 6         0 1 -1 0 1 -1 -1 0 1 -1 0 1 1 -1 0 1 -1 0 0 1 -1 0 1 -1 -1 0 1 -1 0 1 1 -1 0 1 -1 0        
Fig. 1: A triangulation of the 4-punctured sphere and its signed adjacency matrix

Universal geometric coefficients are a choice of coefficients that are universal in the sense that any other choice of geometric coefficients can be obtained from the universal geometric coefficients by coordinate specialization. Constructing geometric coefficients is equivalent to constructing a basis, in the sense of mutation-linear algebra with respect to B. That is, we find a collection of vectors that is independent in a very strong sense and spanning in a similar strong sense. Closely related to this notion of basis is the mutation fan F B , a complete fan that encodes the combinatorics and geometry of mutations of B. In particular, one can read off this basis from the rays of F B .

In [START_REF] Fomin | Cluster algebras and triangulated surfaces. Part I: Cluster complexes[END_REF][START_REF] Fomin | Cluster algebras and triangulated surfaces. Part II: Lambda lengths[END_REF], it was shown that certain cluster algebras are modeled by the combinatorics and geometry/topology of triangulated surfaces. The goal of this paper is to construct universal geometric coefficients and describe the mutation fan for the exchange matrix B encoded by a certain triangulation T of a 2-sphere. The triangulation T , a combinatorial tetrahedron, is shown in Figure 1, along with its signed adjacency matrix B = B(T ). (See Definition 3.3.) Arrows in the picture indicate edgeidentifications, and the arcs defining edges of T are labeled γ i . We write B with rows and columns indexed by γ 1 , γ 2 , γ 3 , γ 4 , γ 5 , γ 6 in that order. The four vertices of the triangulation are called punctures, because cluster algebras associated to B can be understood in terms of the geometry of the 4-punctured sphere, with T taken to be an ideal triangulation. Universal coefficients for exchange matrices arising from triangulated surfaces are considered in general in [START_REF] Reading | Universal geometric cluster algebras from surfaces[END_REF].

Geometric coefficients are encoded by the interactions between two classes of curves, tagged arcs and allowable curves. Both classes are equipped with a notion of compatibility. Seeds in the cluster algebra correspond to tagged triangulations-maximal collections of pairwise compatible tagged arcs. One example is the triangulation shown in Figure 1. The intersections between an allowable curve λ and the arcs in a tagged triangulation T are encoded in a vector b(T, λ) called the shear coordinates or shear coordinate vector of λ with respect to T . The rational lamination fan F Q (T ) is the fan whose cones are the nonnegative spans of the shear coordinate vectors of collections of pairwise compatible allowable curves with respect to T . Assuming a property of the surface called the Null Tangle Property, universal coefficients are the shear coordinates of allowable curves and the rational cones in the mutation fan F B(T ) coincide with the cones of F Q (T ). Our main results are the following theorems.

Theorem 1.1 The 4-punctured sphere has the Null Tangle Property.

Theorem 1.2 Let B be the exchange matrix shown in Figure 1, arising from a triangulation of the 4punctured sphere. Then a complete list of universal geometric coefficients for B is obtained as follows: For each standard form b/a of a rational slope with 0 < b a ≤ ∞, take each vector listed below and apply coordinate permutations indicated by the given permutation group.

1.

- 25), (36), (123)(456)

b-1 2 , a 2 + 1, b-a-1 3. -b+1 2 , a 2 , b-a+1 2 , -b 2 , a+1 2 , b-a 2 (14), (
4. [-b, a, b -a, -b, a, b -a] (123)(456)
To prove Theorem 1.2, we classify tagged arcs and describe pairwise compatibility of tagged arcs, thus obtaining a characterization of all tagged triangulations of the 4-punctured sphere. The tagged arcs correspond bijectively to non-closed allowable curves, so we use the classification of tagged arcs to write down a classification of non-closed allowable curves and describe compatibility of non-closed allowable curves. We then separately classify closed allowable curves and extend the description of compatibility. Much of this curve classification is known. (See for example [START_REF] Keen | The Riley slice of Schottky space[END_REF][START_REF] Komori | The Riley slice revisited. The Epstein birthday schrift[END_REF].) Finally, we determine the shear coordinates of allowable curves. Having explicit shear coordinates allows us to prove the Null Tangle Property (Theorem 1.1). That property implies that our explicit shear coordinates are universal coefficients, and we obtain Theorem 1.2.

Explicit shear coordinates and the description of compatibility among allowable curves lead to an explicit description of the rational part of the mutation fan for the 4-punctured sphere. (This is a fan in R 6 .) The g-vector fan for the associated cluster algebra appears explicitly as a subfan of the mutation fan, so we also obtain the following theorem.

Theorem 1.3 Let B be the matrix of Theorem 1.2. Then the g-vectors of cluster variables associated to B T are the vectors listed as 1, 2, and 3 in Theorem 1.2, with the permutations of entries indicated.

Description of the rational part of the mutation fan leaves open the question of what additional (irrational) cones exist in the mutation fan. We conjecture that these irrational cones are all rays, and all are located on one 2-dimensional plane. Assuming the conjecture, we construct explicit universal coefficients over R as well.

The results discussed in this introduction allow us to work exclusively with surfaces, tagged arcs and allowable curves, leaving the detailed definitions of cluster algebras of geometric type, universal geometric coefficients, mutation-linear algebra, mutation fans, etc. to [START_REF] Reading | Universal geometric cluster algebras[END_REF] and the details of the connection between these concepts and surfaces to [START_REF] Reading | Universal geometric cluster algebras from surfaces[END_REF].

The remainder of this extended abstract is devoted to three tasks. In Section 2, we describe, in general terms, how key topological facts about the 4-punctured sphere, namely its relationship to the 4-punctured torus and to the Z 2 -punctured plane, are used in this paper. In Section 3, we give the definitions and results required to understand universal coefficients and the mutation fan for the 4-punctured sphere. In Section 4, we outline the proof of the main theorems and fill in some details.

Sphere, torus, and plane

In this section, we write S -4 for the 4-punctured sphere. The main tools in our arguments are two well-known covering spaces of S -4. First, the S -4 is doubly covered by the 4-punctured torus T -4. One way to picture the covering space is to skewer a donut so that the surface of the donut is punctured in 4 places and so that rotating the skewer through a half turn is a symmetry of the donut. The quotient of this 4-punctured torus modulo this rotation is a 4-punctured sphere. Second, the Z 2 -punctured plane R 2 -Z 2 is a covering space of S -4.

The covering of S -4 by R 2 -Z 2 has the following description, which also relates to the covering of S -4 by T -4. Consider the group G of rigid motions on R 2 generated by half turns about integer points. This group consists of all such rotations together with all even-integer translations (i.e. translations taking (0, 0) to points with even-integer coordinates). The even-integer translations constitute a normal subgroup H of G of index 2. The quotient (R 2 -Z 2 )/H is T -4 and the quotient (R 2 -Z 2 )/G is S -4. In each case, the natural map to the quotient is a covering map. The 2-element quotient group G/H acts on T -4 and (T -4)/(G/H) is S -4, so the covering map from (R 2 -Z 2 )/G to S -4 factors as the composition of the covering map from R 2 -Z 2 to T -4 followed by the covering map from T -4 to S -4. These constructions are pictured in Figures 2, 3, and4. Figure 2 shows R 2 with the points Z 2 marked by dots and an indication of half-turns. A fundamental domain for the action of G is indicated by a dark gray rectangle, and a fundamental domain for H is indicated by the entire striped square (including the dark gray rectangle). Figure 3 depicts (R 2 -Z 2 )/H as the striped square with edge identifications marked with arrows. The points marked by dots are deleted and, after the edge identifications, these points become the four punctures of the torus. As indicated in the picture, the unique element of G/H acts on (R 2 -Z 2 )/H by a half-turn of the square. Figure 4 depicts (R 2 -Z 2 )/G as the gray rectangle with edge identifications marked with arrows and deleted points, which become the punctures, labeled as 00, 01, 11, and 10.

(R 2 -Z 2 )/G
As discussed in Section 1, one main task in constructing the mutation fan/universal coefficients for S-4 is to classify and parametrize the isotopy types of curves in S -4. Before making a precise definition of the curves in question and a precise statement of the classification results, we describe these covering spaces and explain two basic ideas that allow us to use these covering spaces to classify curves. The covering of T -4 by R 2 -Z 2 essentially agrees ("filling in" the non-even punctures in First, if two curves are isotopic in S -4, then the isotopy lifts to an isotopy between lifts of the curves in T -4. This is also an isotopy between the lifts in T -1. Thus non-isotopic curves in T -1, each missing the other three punctures in T -4, map to non-isotopic curves in S -4.

R 2 -Z 2 ) with a covering of T -1 by R 2 -(2Z) 2
Second, we can use the covering to establish constraints on the curves that can appear in S -4. Specifically, each curve in S -4 lifts to two curves, related by the rotation of the torus described above, that don't intersect each other. This places constraints on which curves in the torus can appear as lifts of curves in S -4, and thus which curves can appear in S -4.

The connection between sphere and torus also appears in several other places in the proofs of our main results, although these details are omitted from this extended abstract.

It turns out that the argument used in [START_REF] Reading | Universal geometric coefficients for the once-punctured torus[END_REF] to prove the Null Tangle Property for the once-punctured torus can be adapted to prove the property for the 4-punctured sphere. We also find an interesting connection between the mutation fans for the once-punctured torus and the 4-punctured sphere: There is a 3-dimensional subspace U of R 6 such that the fan induced on U by the mutation fan for the sphere coincides with the mutation fan for the torus.

Surfaces, arcs, and curves

In this section, we review the basic definitions from [START_REF] Fomin | Cluster algebras and triangulated surfaces. Part I: Cluster complexes[END_REF][START_REF] Fomin | Cluster algebras and triangulated surfaces. Part II: Lambda lengths[END_REF][START_REF] Reading | Universal geometric cluster algebras from surfaces[END_REF] of marked surfaces, arcs, triangulations, allowable curves, and so forth, as well as the results linking these constructions to the mutation fan and to universal coefficients. In this paper we are only concerned with two marked surfaces-the once-punctured torus and the 4-times punctured sphere-and we quote the basic definitions and results as they apply to those two surfaces. The reader interested in other marked surfaces should consult the original definitions.

In general, a marked surface is a pair (S, M) where S is an orientable surface and M is a set of points in S called marked points. The pair (S, M) must satisfy certain conditions which we do not review here. In this paper, S is the sphere and M is a set of four points in the sphere. We will also sometimes consider the torus with exactly one marked point, but reserve the notation (S, M) for the sphere with four marked points. The constructions we consider are essentially concerned with the topology of the complement S \ M, so we call the marked points punctures and refer to (S, M) as the 4-punctured sphere. Definition 3.1 An arc in (S, M) is a curve γ in S such that:

• The endpoints of γ lie in the set M.

• γ is non-self-intersecting, except possibly at coinciding endpoints. In the case when its endpoints coincide, we call γ a loop. • γ has no punctures in its interior: i.e., γ intersects M at most at its endpoints.

• γ is not isotopic to the identity.

We consider arcs up to isotopy relative to M. Two arcs are compatible if there is an isotopy representative of each such that the two representatives do not intersect, except possibly at their endpoints. Definition 3.2 A tagged arc in (S, M) is an arc γ in (S, M), together with a designation (or "tagging") of each end of the arc as either plain or notched. A tagged arc must also satisfy one additional condition beyond the conditions on an arc:

• γ does not bound a disk containing exactly one puncture.

Two tagged arcs are compatible if one of the following conditions holds:

• The two underlying untagged arcs are the same, and their tagging agrees on one endpoint but not the other. • The two underlying untagged arcs are distinct and compatible, and any shared endpoints have the same tagging.

A tagged triangulation of (S, M) is a maximal collection of distinct pairwise compatible tagged arcs.

The most basic reason to consider marked surfaces in connection with cluster algebras is that the combinatorial structure of triangulations of marked surfaces is encoded by an exchange matrix. A deeper reason is that passing from one tagged triangulation to another by "flips" of tagged arcs corresponds to matrix mutation. See [2, Lemma 9.7] for details. Definition 3.3 Suppose T is a tagged triangulation of (S, M). The signed adjacency matrix B(T ) encodes the structure of T . The rows and columns of B(T ) are indexed by the arcs in T . Due to space restrictions, here we define B(T ) only in the case where all of the tagged arcs of T are tagged plain everywhere. In this case, T defines a decomposition of S into triangles, with each arc shared by two different triangles. For each pair α, β of arcs, the αβ-entry of B(T ) is the sum of contributions from each triangle of T . A triangle contributes +1 if α and β are arcs of the triangle with α immediately preceding β in a clockwise traversal of the triangle, or contributes -1 if the same is true for a counterclockwise traversal. The contribution is 0 otherwise. An example of this definition appears in Figure 1.

Aside from arcs, it is useful to consider an additional class of curves in (S, M). Definition 3.4 An allowable curve in (S, M) is a non-self-intersecting curve in S\M, not homotopic to a constant curve, that either

• spirals into a puncture at both ends, or • is closed.

We consider allowable curves up to isotopy. A curve may spiral into a puncture in a clockwise or counterclockwise manner, and curves that spiral in opposite directions are considered to be different curves. Two allowable curves are compatible if either there is an isotopy representative of each such that the two representatives do not intersect, or the two curves coincide except that their spiral direction disagrees at exactly one end. An (integral) quasi-lamination is a collection of pairwise compatible allowable curves with positive integer weights.

Given a tagged arc α in (S, M) there is a unique curve κ(α) which coincides with α except that, at each endpoint p, if α is tagged plain at p, then κ(α) spirals clockwise into p, and if α is tagged notched at p, then κ(α) spirals counterclockwise into p. It is immediate from the definitions that κ is a bijection from tagged arcs to allowable curves that are not closed, and that two tagged arcs α and γ are compatible if and only if the allowable curves κ(α) and κ(γ) are compatible. (See also [START_REF] Fomin | Cluster algebras and triangulated surfaces. Part I: Cluster complexes[END_REF]Definition 17.2] and [8, Lemma 5.1].) Thus κ takes tagged triangulations to maximal collections of non-closed pairwise compatible allowable curves. Despite this partial correspondence via the map κ, it is useful to consider allowable curves and quasi-laminations separately from tagged arcs and tagged triangulations in order to define shear coordinates. Definition 3.5 (Shear coordinates) Given a lamination L and a tagged triangulation T , the shear coordinate vector is a vector b(T, L) = (b γ (T, L) : γ ∈ T ) indexed by the tagged arcs γ in T . We define shear coordinates here only in the case where all of the tagged arcs of T are tagged plain everywhere.

The shear coordinates record how a lamination interacts with each arc and the two triangles that share it. Each allowable curve λ ∈ L contributes a quantity b γ (T, λ), and b γ (T, L) is the sum λ∈L w λ b γ (T, λ), where w λ is the weight of λ in L. To compute b γ (T, λ), we apply, if necessary, an isotopy to λ so as to minimize the number of intersection points of λ with γ. Then b γ (T, λ) is the sum, over each intersection of λ with γ, of a number that is -1, 0, or 1. The number is ±1 as shown in Figure 5 if λ intersects the two triangles as shown in the figure, and 0 otherwise. The arc γ is the diagonal of the square pictured and the curve λ is the vertical or horizonal dashed line.

+1

-1

Fig. 5: Shear coordinates

The key property of a marked surface that enables results about the mutation fan and about universal coefficients is the Null Tangle Property. Definition 3.6 A tangle in (S, M) is an arbitrary finite collection Ξ of allowable curves, each with an integer weight. In contrast with the definition of a lamination, there is no requirement of pairwise compatibility of curves and no requirement of positivity of weights. The shear coordinates b(T, Ξ) of a tangle Ξ with respect to a tagged triangulation T are computed as the weighted sum of the shear coordinates, with respect to T , of the curves in the tangle. A tangle is trivial if all of the weights are zero. A null tangle is a tangle Ξ such that, for any tagged triangulation T , the shear coordinates b(T, Ξ) are zero. The Null Tangle Property is the property of a marked surface that if Ξ is a null tangle then it is trivial.

The Null Tangle Property was proved in [START_REF] Reading | Universal geometric cluster algebras from surfaces[END_REF] for a family of surfaces coincidentally equal to the surfaces of finite growth (see [2, Section 11]), and for the once-punctured torus in [START_REF] Reading | Universal geometric coefficients for the once-punctured torus[END_REF]. We prove it in this work for the 4-punctured sphere (Theorem 1.1). Definition 3.7 Fix a tagged triangulation T . For any collection Λ of pairwise compatible allowable curves, let C Λ be the nonnegative R-linear span of the shear coordinates {b(T, λ) : λ ∈ Λ}. Let F Q (T ) be the collection of all cones C Λ . It is shown in [START_REF] Reading | Universal geometric cluster algebras from surfaces[END_REF]Theorem 4.10] that F Q (T ) is a rational simplicial fan. We call F Q (T ) the rational quasi-lamination fan for T .

We can now quote the results of [START_REF] Reading | Universal geometric cluster algebras from surfaces[END_REF] that we need. The following theorem is the combination of parts of

Proof outline, and some details

In this section, we outline the proofs of the main theorems and give some details. We continue to let (S, M) denote the 4-punctured sphere. We rely heavily on the covering maps described in Section 2. Each of these covering maps extends continuously to a map on the corresponding unpunctured spaces, taking punctures to punctures. We will thus speak of the action of the covering maps on punctures, even though the maps on the unpunctured spaces are only branched coverings.

We index the four punctures in the sphere according to their pre-images in the plane. Each integer point in R 2 maps to a puncture of the sphere, and two points map to the same puncture if and only if their coordinates agree modulo 2. Accordingly, we index the punctures as v pq (or when necessary v p,q ) where p and q are integers mod two. This indexing of the punctures is consistent with the numbering in Figure 4.

Each arc γ in (S, M) is in particular the image of some continuous map from the closed unit interval to S, with endpoints of the interval mapping into M. The definition ensures that the restriction γ S\M of γ to the open unit interval is a curve in S \ M. The endpoints of γ are recovered as the limits (within S) of γ S\M . When we consider the covering of S \ M by the 4-punctured torus or by the Z 2 -punctured plane, we must consider γ S\M . However, any lift of γ S\M to one of the covering spaces is a curve limiting, at each end, to a puncture. In particular, any lifting of γ S\M is the restriction to the open interval of a unique curve γ whose endpoints are punctures of the covering space. Thus it makes sense to talk about lifting an arc γ to one of the covering spaces, rather than lifting only its restriction γ S\M . (Some care must be taken when trying to apply "unique lifting" results to arcs.) Similarly, it makes sense to speak of projecting arcs down from the covering spaces.

The first step in proving our main results is to classify allowable curves and describe their compatibility. Because it is no harder, and because tagged arcs are of independent interest, we classify the non-closed allowable curves by first classifying tagged arcs and then applying the map κ.

Tagged arcs and tagged triangulations

Tagged arcs are specified by, among other data, a rational slope, i.e. a rational number or ∞. Rational slopes are in one-to-one correspondence with formal expressions b/a with gcd(a, b) = 1 such that a ≥ 0 and such that b = 1 whenever a = 0. Such an expression is the standard form of a rational slope. Consider an integer point [p, q] ∈ Z 2 and the standard form b/a of a rational slope. Because b/a is in standard form, the straight line segment connecting [p, q] to [p + a, q + b] intersects no other integer points. Let arc(a, b, {v p,q , v p+a,q+b }) be the projection to (S, M) of the line segment connecting [p, q] to [p + a, q + b]. This is an arc in (S, M) connecting the punctures v p,q and v p+a,q+b . Since the indices on punctures are interpreted mod 2, this arc only depends on [p, q] modulo 2. The set braces in the notation remind us that v p,q and v p+a,q+b appear symmetrically in the construction, because the line segment connecting [p + a, q + b] to [p + 2a, q + 2b] projects to the same arc in (S, M) as the line segment connecting [p, q] to [p + a, q + b]. Since b/a is in standard form, b and a are not both multiples of 2, so the set {v p,q , v p+a,q+b } has two distinct elements. For any standard form b/a, there are exactly two choices for the set {v p,q , v p+a,q+b }.

We use a similar notation for tagged arcs in (S, M) by attaching a superscript to the endpoints v p,q and/or v p+a,q+b to indicate notched tagging of the arc at that endpoint. There are four tagged arcs whose underlying arc is arc(a, b, {v p,q , v r,s }). They are arc(a, b, {v p,q , v r,s }), arc(a, b, {v p,q , v r,s }), arc(a, b, {v p,q , v r,s }), and arc(a, b, {v p,q , v r,s }). Let A be the set of triples (a, b, E) such that b/a is Fig. 6: tagged triangulations of the 4-punctured sphere the standard form for a rational slope and E is {v p,q , v r,s }, {v p,q , v r,s }, {v p,q , v r,s }, or {v p,q , v r,s } with

[p, q] + [a, b] = [r, s] modulo 2. Proposition 4.1 The map (a, b, E) → arc(a, b, E) is a bijection from A to {tagged arcs in (S, M)}.
In particular, there are no tagged loops in (S, M). This is easily understood: a tagged loop separates the sphere into two disks, one of which contains 0 or 1 punctures, but both possibilities are specifically excluded for tagged arcs in Definition 3.2. Proposition 4.2 Two tagged arcs whose underlying arcs coincide are compatible if and only if their tagging agrees at exactly one of their endpoints. Two tagged arcs arc(a, b, E) and arc(c, d, F ) whose underlying arcs do not coincide are compatible if and only if their taggings agree at each shared endpoint and |ad -bc| equals the number of shared endpoints (0, 1, or 2).

We call two distinct tagged arcs a coinciding pair if their underlying arcs coincide and their taggings make them compatible as described in Proposition 4.2. Rational slopes b/a and d/c with |ad -bc| = 1 are sometimes called Farey pairs. Accordingly, we call non-coinciding compatible pairs arc(a, b, E) and arc(c, d, F ) Farey-0 pairs (or parallel pairs), Farey-1 pairs, or Farey-2 pairs according to their number of shared endpoints. We overload the terms by also referring to "Farey-1 (or Farey-2) pairs of slopes."

With a description of compatibility of tagged arcs in hand, we describe the tagged triangulations of (S, M). By [2, Theorem 7.9], each tagged triangulation has the same number of arcs, and we have seen in Figure 1 that this number is 6. We illustrate the six combinatorial types of tagged triangulations in Figure 6. These pictures are drawn, not in the sphere illustrated in Figure 4, but rather in a more conventional sphere: the plane of the page together with the "point at infinity." Each combinatorial type can be tagged in more than one way. Specifically, at each puncture, except the punctures where there are already two distinct tags, endpoints of arcs can all be tagged plain or all be tagged notched, and this choice can be made independently at each puncture. To arrive at this list of combinatorial types, we view a tagged triangulation as a graph in which the punctures are vertices and arcs are edges. We first determine the possible degree sequences the corresponding graph may have. To differentiate between tagged triangulations with the same degree sequence, but different combinatorial types (eg. the upper right and lower right tagged triangulations in Figure 6) we also specify the number of coinciding pairs of arcs in the triangulation.

To completely understand tagged triangulations, we need to determine, for each combinatorial type, precisely what additional data are required to specify a unique tagged triangulation. In this extended abstract, we do this only for two of the combinatorial types.

We begin with the triangulation with degree sequence 3, 3, 3, 3, which we call the tetrahedron, and which appears as the upper left picture in Figure 6. Note that a Farey-2 pair divides the sphere into two once-punctured monogons, and the puncture inside each monogon must have degree 2. Any coinciding pair must be incident to a puncture of degree 2. Since no puncture has degree 2 in the tetrahedron, the tetrahedron contains no coinciding or Farey-2 pairs. It follows that the tagging at each puncture can be chosen arbitrarily, subject to the restriction that all taggings agree at each puncture. It also follows that any pair of tagged arcs incident to a single puncture form a Farey-1 pair and any pair of tagged arcs sharing no punctures form a Farey-0 pair. Thus once the tagging at each puncture has been chosen, selecting any three arcs which form a Farey-1 triple (a triple, each pair of which is a Farey-1 pair) determines the remaining three arcs of the tagged triangulation. We conclude that there is exactly one tetrahedron for each choice of taggings and each Farey-1 triple. Now consider a tagged triangulation with degree sequence 6, 2, 2, 2 containing three coinciding pairs, as shown in the upper right of Figure 6. We will call such a triangulation a pinwheel. After we select a vertex to have degree 6 and choose a tagging for that vertex, each pair of coinciding arcs is uniquely determined by a choice of slope. Since any two non-coinciding arcs in the pinwheel share exactly one vertex, the three slopes form a Farey-1 triple. Therefore the pinwheel triangulations are specified by a choice of vertex, a tagging of the vertex, and a Farey-1 triple.

Allowable curves and the rational lamination fan

Since κ is a bijection between tagged triangulations and maximal pairwise compatible sets of non-closed allowable curves, Proposition 4.1 can be rephrased as a classification of non-closed allowable curves. The classification of allowable curves is completed by the following proposition, which is well-known. (See for example [START_REF] Keen | The Riley slice of Schottky space[END_REF][START_REF] Komori | The Riley slice revisited. The Epstein birthday schrift[END_REF].) We omit the details here. Similarly, the classification of tagged triangulations can be rephrased as a classification of maximal pairwise compatible sets of non-closed allowable curves. These correspond to full-dimensional (6-dimensional) cones in the mutation fan F B . To complete the description of the rational part of the mutation fan, we consider maximal sets of pairwise compatible allowable curves containing at least one closed allowable curve. Any closed allowable curve in (S, M) cuts (S, M) into two twice-punctured disks, and no other closed allowable curve can be contained in either twice-punctured disk. Thus no two distinct closed allowable curves can be compatible. It is also not hard to convince oneself that a closed allowable curve and a non-closed allowable curve are compatible if and only if they are specified by the same slope. (In this case, the non-closed allowable curve spirals into the two punctures in one of the twice-punctured disks.) Thus there are exactly 8 allowable curves compatible with a given closed allowable curve.

Any maximal pairwise compatible set of allowable curves contains at most one closed curve. Each given closed allowable curve is contained in exactly 16 maximal collections of pairwise compatible allowable curves, each containing five curves. A given collection is obtained by choosing, for each of the two twice-punctured disks, which of the punctures should have opposite spiral directions and then specifying the spiral direction at the other puncture. These maximal pairwise compatible sets with one closed curve correspond to maximal 5-dimensional cones in F B .

The Null Tangle Property

With the classification of allowable curves in hand, we can prove the Null Tangle Property. The verification of the Null Tangle Property is a technical argument following the outline of the proof in [START_REF] Reading | Universal geometric coefficients for the once-punctured torus[END_REF] of the Null Tangle Property for the once-punctured torus. The first piece of the argument is to show that, in any null tangle, the weight of any non-closed curve is zero. Then one verifies that any null tangle involving only closed curves is trivial. We omit the details.

Shear coordinates

As before, let T = {γ i } be the triangulation of Figure 1. With the Null Tangle Property established, Theorem 3.8 says that the set of all shear coordinate vectors with respect to T constitutes universal geometric coefficients for B(T ). We conclude our outline of the proofs of the main results by describing the computation of shear coordinates that verifies Theorem 1.2.

Let λ be an allowable curve. As described in Definition 3.5, computing the shear coordinate b γi (T, λ) amounts to counting and categorizing the intersections of λ with γ i into crossings of type -1, 1 (nontrivial) and 0 (trivial) and summing these contributions. This is most easily done by taking a lift λ of λ to R 2 (specifically, the lift to the positive quadrant with one endpoint at the origin) and examining intersections with the lifts of γ i there. For example, let λ be the projection of the curve λ in R 2 shown in the left picture of Figure 7.

Each arc shown in the figure is the lift of an arc of the triangulation T in the 4-punctured sphere, and some of these are labeled with the numbering from Figure 1. Nonzero contributions to shear coordinates are shown in red in the picture, adding up to [-1, 2, 0, -1, 1, 0].

Initially, we restrict ourselves to curves with positive slopes and one endpoint at puncture v 00 (or, in the case of closed curves, "near" v 00 ). We further simplify computation by initially ignoring endpoint spirals, if they exist, and focusing solely on the linear interior of λ. We call any intersections between λ and lifts of γ i not arising from spirals "interior" intersections. Recalling our construction of allowable curves in Definition 3.4 as κ(α) for a tagged arc α, this simplification is natural: essentially, interior intersections are those arising from α , the arc α with taggings removed. We then add shear coordinate contributions from different types of tagging, (i.e., spiraling) on a case-by-case basis.

The triangulation T was chosen specifically to correspond to the fixed triangulation T 0 in [9, Section 5], allowing us to group arcs in T into pairs: 'horizontal' arcs γ 1 and γ 4 , 'vertical' arcs γ 2 and γ 5 , and 'diagonal' arcs γ 3 and γ 6 , corresponding, respectively, to the single arcs γ 1 , γ 2 , γ 3 ∈ T 0 . This construction allows us to reuse much of the proof of [START_REF] Reading | Universal geometric coefficients for the once-punctured torus[END_REF]Proposition 5.1]. It can be shown that interior intersections of λ with lifts of 'horizontal' (respectively, 'vertical') arcs are always non-trivial and alternate between γ 1 and γ 4 (respectively, γ 2 and γ 5 ). We show further that while not all interior intersections of λ with diagonal arcs are non-trivial, those that are alternate between γ 3 and γ 6 . The formulas in Theorem 1.2 follow after some straightforward computations.

The permutations of entries arise in Theorem 1.2 for two different reasons. First, we restricted to curves starting at/near v 00 . To consider other starting points, we can translate the lift, and this translation gives a permutation of arcs. For example, to change the starting point to v 01 , we translate the lift one unit up, and this acts as the permutation (14)(36) on the indices i of the γ i . Second, we restricted to positive slopes. Shear coordinates for curves with negative slopes can also be obtained by permutations of coordinates, using the idea that appeared in [9, Section 5]. We omit the details here, but provide an example in the two shear coordinate calculations of Figure 7.

Fig. 2 :

 2 Fig. 2: Fundamental domains for G and H on R 2 -Z 2

Fig. 3 :

 3 Fig. 3: (R 2 -Z 2 )/H and a fundamental domain for G/H

  . The latter covering leads to a classification of curves in T -1: The curves are parametrized by rational slopes. The covering of S -4 by T -4 allows us to borrow the T -1 curve-classification results and obtain curve-classification results for S -4: Curves are classified by rational slopes and by which, if any, punctures the curve connects.

[ 8 ,

 8 Theorem 4.10], [7, Theorem 8.7], [2, Proposition 7.10], [8, Theorem 7.3], and [7, Theorem 4.4]. Theorem 3.8 Suppose (S, M) has the Null Tangle Property and let T be any tagged triangulation of (S, M). Then • The fan F Q (T ) is the rational part of the mutation fan F B(T ) . • The g-vector fan of B(T ) is the set of all cones C Λ such that Λ is a collection of pairwise compatible non-closed allowable curves. (This statement must be modified if (S, M) is a closed surface with exactly one puncture.) • The shear coordinates of allowable curves constitute universal geometric coefficients for B(T ).

Proposition 4 . 3

 43 The allowable closed curves in (S, M) are the images, under the covering map, of straight lines in R 2 \Z 2 with (possibly infinite) rational slope. Two such images are isotopic if and only if the corresponding lines have the same slope.

1 Fig. 7 :

 17 Fig. 7: Some shear coordinate calculations

Acknowledgements

The authors thank Dylan Allegretti, Bill Floyd, Vladimir Fock, Alexander Goncharov, Allen Hatcher, and Lee Mosher for helpful responses to email queries.

Supported in part by NSF grants DMS-0943855 and CCF-1017217. Supported in part by NSF grants DMS-0943855 and CCF-1017217. Supported in part by NSF grants DMS-0943855 and CCF-1017217. Supported in part by NSF grant DMS-1101568. 1365-8050