Coxeter-biCatalan combinatorics

Emily Barnard, Nathan Reading

► To cite this version:

Emily Barnard, Nathan Reading. Coxeter-biCatalan combinatorics. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.157-168, 10.46298/dmtcs.2519 . hal-01337831

HAL Id: hal-01337831

https://hal.science/hal-01337831v1

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Coxeter-biCatalan combinatorics

Emily Barnard† and Nathan Reading‡

Department of Mathematics, North Carolina State University, Raleigh, NC, USA

**Abstract.** 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.

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

# 1 Introduction

This extended abstract considers enumeration problems closely related to Coxeter-Catalan combinatorics. (For background on Coxeter-Catalan combinatorics, see for example [1, 11]). 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*-sorted 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.

<footnote>†Email: esbarnar@ncsu.edu. Supported in part by NSF grant DMS-0943855.</footnote>

<footnote>‡Email: reading@math.ncsu.edu. Supported in part by NSF grant DMS-1101568.</footnote>
**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.

$$ \frac{A_n}{\binom{2n}{n}} \mid \frac{B_n}{2^{2n-1}} \mid \frac{D_n}{6 \cdot 4^{n-2} - 2 \binom{2n-4}{n-2}} \mid \frac{E_6}{1700} \mid \frac{E_7}{8872} \mid \frac{E_8}{54066} \mid \frac{F_4}{196} \mid \frac{H_3}{56} \mid \frac{H_4}{550} \mid \frac{I_2(m)}{2m} $$

$$ \begin{array}{c|l} A_n & \sum_{k=0}^{n} \binom{n}{k}^2 q^k \\ \hline B_n & \sum_{k=0}^{n} \binom{2n}{2k} q^k \\ \hline D_4 & 1 + 20q + 42q^2 + 20q^3 + q^4 \\ \hline D_5 & 1 + 35q + 136q^2 + 136q^3 + 35q^4 + q^5 \\ \hline D_6 & 1 + 54q + 343q^2 + 600q^3 + 343q^4 + 54q^5 + q^6 \\ \hline E_6 & 1 + 66q + 415q^2 + 736q^3 + 415q^4 + 66q^5 + q^6 \\ \hline F_4 & 1 + 44q + 106q^2 + 44q^3 + q^4 \\ \hline G_2 & 1 + 10q + q^2 \\ \hline H_3 & 1 + 27q + 27q^2 + q^3 \\ \hline I_2(m) & 1 + (2m - 2)q + q^2. \end{array} $$

In the setting of clusters of almost positive roots (in the sense of [12]), 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 [22] 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 [12, 22, 25]. While there is a notion of c-clusters for any Coxeter element c, we emphasize that Theorem 1.2 refers to the original definition of clusters in [12], 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 [7], 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 (c, c⁻¹)-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 (c, c⁻¹)-noncrossing partitions.

Although the definitions of twin bipartite c-noncrossing partitions and pairs of twin bipartite (c, c⁻¹)-noncrossing 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.
<figure><img src="image_2.png" /><figcaption>Fig. 1: Some doubled root posets</figcaption></figure>

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* $\prod_{i=1}^{n} \frac{h+e_i-1}{e_i}$, 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(m)$—the “coincidental types” of [31]—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.

## 2 BiCatalan objects

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

### 2.1 Antichains in the doubled root poset and twin nonnesting partitions

The *root poset* of a finite crystallographic root system $\Phi$ is the set of positive roots in $\Phi$, partially ordered by setting $\alpha \le \beta$ if and only if $\beta - \alpha$ is in the nonnegative span of the simple roots. Recall that the dual of a poset $(X, \le)$ is the poset with the same ground set $X$, satisfying $x \le y$ in the dual poset if and only if $x \ge y$ in $(X, \le)$. 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 $(0, 0)$ to $(n, n)$ with steps $(1, 0)$ and $(0, 1)$. 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 $(1, 0)$-step immediately follows a $(0, 1)$-step). To specify a path with $k$ right turns, we need only specify where the right turns are. This means choosing $0 \le x_1 < \dots < x_k \le n-1$ and $1 \le y_1 < \dots < y_k \le n$ and placing right turns at $(x_1, y_1), \dots, (x_k, y_k)$. Thus, as is well-known, there are $\binom{n}{k}$ paths with $k$ right turns.

Antichains in the doubled root poset of type $B_n$ are similarly in bijection with lattice paths from $(-n+1, -n+1)$ to $(n-1, n-1)$ with steps $(1, 0)$ and $(0, 1)$ 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 $(2n-1) \times (2n-1)$ box. The generating function for such partitions is $\prod_{i=1}^{2n-1} (1+q^{2i-1})$ 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(m)$ and the $H_3$ root poset suggested in [1, Section 5.4.1], one can verify that Theorem 1.1 holds in these types as well.
<figure><img src="image_3.png" /><figcaption>Fig. 2: Cambrian fans and the biCambrian fan</figcaption></figure>

The **support** of a root $\beta$ is the set of simple roots appearing with nonzero coefficient in the expansion of $\beta$ 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 $\Delta$ for the simple roots and, given a set $A$ of roots, we write $A^{\circ}$ 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 $(A_1, A_2)$ is a pair of **twin nonnesting partitions** if and only if $A_1 \cap \Delta = A_2 \cap \Delta$, and $\text{supp}(A_1^{\circ}) \cap \text{supp}(A_2^{\circ}) = \emptyset$.

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 $\beta$ in the top part of the doubled root poset is related to a root $\gamma$ in the bottom part of the doubled root poset if and only if the supports of $\beta$ and $\gamma$ overlap.

**Proposition 2.2** *The map $A \mapsto (A_1, A_2)$ is a bijection from antichains in the doubled root poset to pairs of twin nonnesting partitions.*

## 2.2 BiCambrian fans

The Cambrian fan is a complete simplicial fan whose maximal faces are naturally in bijection [22, 25] with seeds in an associated cluster algebra of finite type and with noncrossing partitions. Furthermore, the Cambrian fan is the normal fan [15, 16] to a simple polytope called the **generalized associahedron** [6, 12], 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** $\mathcal{F}$. The maximal cones of the Coxeter fan are in bijection with the elements of $W$. The Cambrian fan $\text{Camb}(W, c)$ 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** $\text{biCamb}(W, c)$ to be the coarsest common refinement of the Cambrian fans $\text{Camb}(W, c)$ and $\text{Camb}(W, c^{-1})$. Since $\text{Camb}(W, c)$ and $\text{Camb}(W, c^{-1})$ are coarsenings of $\mathcal{F}$, so is $\text{biCamb}(W, c)$. Naturally, $\text{biCamb}(W, c^{-1}) = \text{biCamb}(W, c)$. To illustrate the definition, take $W$ of type $B_2$ with simple generator $r$ and $s$. Figure 2 shows, from left to right, the $rs$-Cambrian fan, the $sr$-Cambrian fan, and the $rs$-biCambrian fan.
The $c^{-1}$-Cambrian fan coincides with the image of the $c$-Cambrian fan under the antipodal map. This is an immediate corollary of [23, Proposition 1.3], which is a statement about Cambrian congruences. See also [26, 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 biCamb$(W, c)$ is the coarsest common refinement of Camb$(W, c)$ and – Camb$(W, c)$.*

Since $\mathrm{Camb}(W, c)$ and $\mathrm{Camb}(W, c^{-1})$ are the normal fans of two generalized associahedra, a standard fact (see [32, Proposition 7.12]) yields the following result.

**Proposition 2.4** *For any $W$ and $c$, the fan biCamb$(W, c)$ is the normal fan of a polytope, specifically, the Minkowski sum of the generalized associahedra dual to Camb$(W, c)$ and Camb$(W, c^{-1})$.*

The definition of biCamb$(W, c)$ 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 [30] and then in [14, 18]. 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 biCamb$(W, c)$ is the Baxter number
$$ \frac{2}{n(n+1)^2} \sum_{k=0}^{n-1} \binom{n+1}{k} \binom{n+1}{k+1} \binom{n+1}{k+2} $$
the number of Baxter permutations [3, 8].

Once one sees that the Baxter number counts maximal cones of biCamb$(W, c)$ 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 [9]. The Coxeter diagram of type B is also a path, and taking $c$ to be a linear Coxeter element, the maximal cones of biCamb$(W, c)$ 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_+ \cup 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 biCamb$(W, c)$ a **bipartite biCambrian fan**.

**Proposition 2.4** says that biCamb$(W, c)$ 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 biCamb$(W, c)$ is a simplicial fan.*

## 2.3 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 $\pi_{\downarrow}(L)$ of elements that are the bottoms of their congruence classes.

The maximal cones of the Coxeter fan $\mathcal{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 [21] for the definition.) For each congruence class in the *c-Cambrian congruence*, the union of the corresponding maximal cones in $\mathcal{F}$ is itself a convex cone. The collection of all these convex cones and their faces is the *c-Cambrian fan* $\text{Camb}(W, c)$ described earlier.

Consider the set $\text{Con}(L)$ of all congruences on a given lattice $L$. The set $\text{Con}(L)$ 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 $\text{Con}(W)$, 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 $\text{biCamb}(W, c)$. The *c-biCambrian lattice* is the quotient of the weak order modulo the biCambrian congruence.

We write $\pi_{\downarrow}^c$ for the projection taking each element of $W$ to the bottom element of its $c$-Cambrian congruence class, and similarly $\pi_{\downarrow}^{c^{-1}}$ for the $c^{-1}$-Cambrian congruence. Two elements $u$ and $v$ are congruent in the $c$-Cambrian congruence if and only if $\pi_{\downarrow}^c(u) = \pi_{\downarrow}^c(v)$ and are congruent in the $c^{-1}$-Cambrian congruence if and only if $\pi_{\downarrow}^{c^{-1}}(u) = \pi_{\downarrow}^{c^{-1}}(v)$. 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 $(\pi_{\downarrow}^c(w), \pi_{\downarrow}^{c^{-1}}(w))$ to each $c$-biCambrian congruence class. Specifically, $u$ and $v$ are congruent in the $c$-biCambrian congruence if and only if $\pi_{\downarrow}^c(u) = \pi_{\downarrow}^c(v)$ and $\pi_{\downarrow}^{c^{-1}}(u) = \pi_{\downarrow}^{c^{-1}}(v)$.

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 $(u, v)$ to be a pair of *twin* $(c, c^{-1})$-*sortable elements* of $W$ if there exists $w \in W$ such that $u = \pi_{\downarrow}^c(w)$ and $v = \pi_{\downarrow}^{c^{-1}}(w)$. 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 $(c, c^{-1})$-sortable elements of $W$. The bijection maps a congruence class to $(\pi_{\downarrow}^c(w), \pi_{\downarrow}^{c^{-1}}(w))$ for any $w$ in the class. The twin sortable elements are similar in spirit to the twin binary trees of [10]. Indeed, for $W$ of type A and $c$ linear, the connection is implicit in the construction in [18] of a diagonal rectangulation from a pair of binary trees. (See also [18, 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 $\text{des}(v)$, the number of descents of $v$.

A general fact about lattice quotients of the weak order [20, Proposition 3.5] implies that, when $\text{biCamb}(W, c)$ is simplicial, the descent generating function of $c$-bisortable elements equals the $h$-polynomial of $\text{biCamb}(W, c)$.
## 2.4 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 [12], 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 [12, 13].) Rather, for our purposes it will be enough to quote some results about combinatorial clusters and their relationship to sortable elements.

First, [12, 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 $\mathbb{R}_{\ge 0}C$ for the nonnegative linear span of $C$. Then [12, Theorem 1.10] states that the cones $\mathbb{R}_{\ge 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 $(C_1, C_2)$ of clusters is called a pair of **twin clusters** if the cones $\mathbb{R}_{\ge 0}C$ and $-\mathbb{R}_{\ge 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 $\text{biCamb}(W, c)$, 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 [19] (see also [22, Section 7]), the construction of [12], 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$.

## 2.5 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 $\leq_T$ for the absolute order. The $c$-noncrossing partitions in a finite Coxeter group $W$ are the elements of $W$ contained in the interval $[1, c]_T$ in the absolute order on $W$. For details on the absolute order and noncrossing partitions, see for example [1, 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 $\mathbb{R}^n$ and let $T$ be the set of reflections of $W$. For each reflection $t \in T$, let $\beta_T$ be the corresponding positive root. Given $w \in [1, c]_T$, define a cone

$$F_c(w) = \{ \mathbf{x} \in \mathbb{R}^n : \mathbf{x} \cdot \beta_t \le 0 \ \forall t \le T \ w, \ \mathbf{x} \cdot \beta_t \ge 0 \ \forall t \ge T \ cw^{-1} \}.$$

The following theorem combines [5, Theorem 1.1] with [5, Theorem 5.5].

**Theorem 2.6** For $c$ bipartite, the map $F_c$ is a bijection from $[1, c]_T$ to the set of maximal cones in the $c$-Cambrian fan.
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 \leq_T w$ is the intersection of $T$ with some (not necessarily standard) parabolic subgroup of $W$. The definition in [5] imposes inequalities $x \cdot \beta_t \leq 0$ only for those $\beta_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 \cdot \beta_t \geq 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 $[1, c]_T$ **twin c-noncrossing partitions** if $F_c(v) \cap (-F_c(w))$ is full-dimensional. Similarly, we call a pair $(v, w) \in [1, c]_T \times [1, c^{-1}]_T$ **twin (c, c^{-1})-noncrossing partitions** if $F_c(v) \cap F_{c^{-1}}(w)$ is full-dimensional. Theorem 2.6 now immediately implies Theorem 1.3.

### 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 [21]. 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 \cdots 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 language of generalized pattern avoidance [2].

In order to introduce alternating arc diagrams, we review the more general **noncrossing arc diagrams** from [24]. 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 \cdots x_{n+1}$ in $S_{n+1}$, we define a noncrossing arc diagram $\delta(x)$. 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 $\alpha$ in $\delta(x)$. For each integer $a$ with $x_{i+1} < a < x_i$ that occurs to the left of $x_i$ in $x_1 \cdots x_{n+1}$, the $a$th point is left of the arc $\alpha$. For each integer $a$ with $x_{i+1} < a < x_i$ that occurs to the right of $x_{i+1}$ in $x_1 \cdots x_{n+1}$, the $a$th point is right of the arc $\alpha$. It was shown in [24, Theorem 3.1] that $\delta$ is a bijection from permutations to noncrossing arc diagrams.

An **alternating arc** is an arc (in the sense of noncrossing diagrams) 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 $\delta$ with Proposition 3.1, we obtain the following proposition.

**Proposition 3.2** For $W = S_{n+1}$ and c bipartite, the restriction of $\delta$ is a bijection from c-bisortable permutations with $k$ descents to alternating arc diagrams on $n+1$ points with $k$ arcs.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Some alternating noncrossing arc diagrams</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4: Two alternating arcs</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5: Two arc diagrams</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6: Non-diagrams</figcaption></figure>

Figure 3 shows several alternating noncrossing arc diagrams. From left to right they are $\delta(5371624)$, $\delta(6745231)$, and $\delta(4627531)$.

To prove the type-A enumeration of bipartite c-bisortable elements, we give a bijection between pairs $(S, T)$ of subsets of $[n]$ 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 $(i, j)$ with $i, j \in [n]$. First we set some terminology.

Recall that we number the arcs $1, \dots, 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, $\sigma_{(i,j)}$ 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 $\sigma_{(i,j)}$ has **left orientation** if the arc passes to the left of the point $i+1$. Similarly, $\sigma_{(i,j)}$ has **right orientation** if the arc passes to the right of $i+1$. Figure 4 shows the two arcs that could be called $\sigma_{(1,6)}$ for $n+1=6$. The left picture in the figure is an arc with left orientation. The bijection from alternating arcs to pairs $(i, j)$ with $i, j \in [n]$ maps each arc $\sigma_{(i,i+1)}$ to $(i, i)$. Each arc $\sigma_{(i,j)}$ has either left orientation or right orientation. If the orientation is left, then the arc is mapped to $(i, j-1)$, and if right, it is mapped to $(j-1, i)$.

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 $(S, T)$, 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 $\{t+1:t \in T\}$ should label the upper endpoints in an alternating diagram. If the numbers in $S$ are larger than the numbers in $T$, then $\{s+1:s \in S\}$ 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: $(\{1, 4, 6\}, \{2, 3, 5\})$. The whole set $S$ cannot be the set of lower endpoints, since it has the largest value in $S \cup \{t+1:t \in T\}$. Similarly, $\{s+1:s \in S\}$ has the smallest value in $\{s+1:s \in S\} \cup T$, so $\{s+1:s \in S\}$ can't be the set of upper endpoints. To try to salvage the idea, we will attempt to pair each element $s \in S$ with an element $t \in T$ and draw alternating arcs with endpoints $s$ and $t+1$ if $s \le 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 {$(1, 2), (4, 3), (6, 5)$} and {$(1, 2), (6, 3), (4, 5)$}, 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 ({1, 4, 6}, {2, 3, 5})? 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 ($S_1, T_1$) =
({1}, {2}) and ($S_2, T_2$) = ({4, 6}, {3, 5}). The naïve approach now sends ($S_1, T_1$) 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 ($S_2, T_2$) 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 ($S_2, T_2$) into ({4}, {3}) and ({6}, {5})
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 ($S, T$) to the alternating diagram shown in the left picture in Figure 5.

With the intuition gained from this example, we now describe a bijection $\pi$ from alternating arc dia-
grams on $n+1$ points to pairs of subsets $[n]$ of the same size.

Let $\Sigma$ be an alternating arc diagram. Let $P(\Sigma)$ be the set of points $p \in [n+1]$ such that no arc in $\Sigma$ passes left or right of $p$. (A point $p \in P(\Sigma)$ may still be an endpoint of one or two arcs.) Write $P(\Sigma) = \{p_0, \dots, p_m\}$ with $p_0 < \dots < p_m$. In every case, $p_0 = 1$ and $p_m = n+1$. We will define $m$ pairs of subsets $(S_1, T_1), \dots, (S_m, T_m)$. For each $i$, the sets $S_i$ and $T_i$ will be subsets of $\{p_{i-1}, p_{i-1}+1, \dots, p_i-1\}$ and will be determined by the part of $\Sigma$ between $p_{i-1}$ and $p_i$.

If $p_{i-1} = j$ and $p_i = j+1$, then either $\Sigma$ has an arc connecting $j$ to $j+1$ or not. If so, then set $(S_i, T_i) = (\{j\}, \{j\})$. If not, then set $(S_i, T_i) = (\emptyset, \emptyset)$.

Suppose $p_{i-1} = j$ and $p_i > j + 1$. Since $j+1$ is not in $P(\Sigma)$, $\Sigma$ has an arc that passes left or right of $j+1$. But since $j$ is in $P(\Sigma)$, that arc $\sigma$ must have its lower endpoint at $j$. Since $p_i, p_{i+1} \in P(\Sigma)$, every arc in $\Sigma$ having one endpoint in $\{p_{i-1}, p_{i-1} + 1, \dots, p_i\}$ also has its other endpoint in the same set. If $\sigma$ 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 $\{p_{i-1}, p_{i-1} + 1, \dots, p_i\}$ and define $T_i$ to be the set of numbers $t-1$ such that $t$ is the upper endpoint of an arc in $\{p_{i-1}, p_{i-1} + 1, \dots, p_i\}$. If $\sigma$ has right orientation then we switch the definitions of $S_i$ and $T_i$.

$$
\text{We define } \pi(\Sigma) = (\bigcup_{i=1}^{m} S_i, \bigcup_{i=1}^{m} T_i).
$$

**Theorem 3.3** The map $\pi$ is a bijection from the set of alternating arc diagrams on $n+1$ points to the collection of pairs of subsets $[n]$ 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.
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.

References

[1] D. Armstrong, *Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups*. Mem. Amer. Math. Soc. **202** (2009), no. 949.

[2] E. Babson and E. Steingrímsson, *Generalized permutation patterns and a classification of the Mahonian statistics*. Sém. Lothar. Combin. **44** (2000), Art. B44b, 18 pp. (electronic).

[3] G. Baxter, *On fixed points of the composite of commuting functions*. Proc. Amer. Math. Soc. **15** (1964) 851–855.

[4] T. Brady and C. Watt, *Non-crossing partition lattices in finite real reflection groups*. Trans. Amer. Math. Soc., **360** (2008), 1983–2005.

[5] T. Brady and C. Watt, *From permutahedron to associahedron*. Proc. Edinb. Math. Soc. (2) **53** (2010), no. 2, 299–310.

[6] F. Chapoton, S. Fomin and A. Zelevinsky, *Polytopal realizations of generalized associahedra*. Canad. Math. Bull. **45** (2002) no. 4, 537–566.

[7] G. Chatel and V. Pilaud, *The Cambrian and Baxter-Cambrian Hopf algebras*. Preprint, 2014. (arXiv:1411.3704)

[8] F. R. K. Chung, R. L. Graham, V. E. Hoggatt Jr. and M. Kleiman, *The number of Baxter permutations*. J. Combin. Theory Ser. A **24** (1978), no. 3, 382–394.

[9] K. Dilks, *Involutions on Baxter Objects*. Preprint, 2014. (arXiv:1402.2961)

[10] S. Dulucq and O. Guibert, *Stack words, standard tableaux and Baxter permutations*. Discrete Math. **157** (1996), no. 1–3, 91–106.

[11] S. Fomin and N. Reading, *Root systems and generalized associahedra*. IAS/Park City Math. Ser. **13**, 63–131.

[12] S. Fomin and A. Zelevinsky, *Y-systems and generalized associahedra*. Ann. of Math. (2) **158** (2003), no. 3, 977–1018.

[13] S. Fomin and A. Zelevinsky, *Cluster Algebras II: Finite Type Classification*. Inventiones Mathematicae **154** (2003), 63–121.

[14] S. Giraudo, *Algebraic and combinatorial structures on Baxter permutations*. Preprint, 2010 (arXiv:1011.4288).
[15] C. Hohlweg and C. E. M. C Lange, *Realizations of the associahedron and cyclohedron*. Discrete Comput. Geom. **37** (2007), no. 4, 517–543.

[16] C. Hohlweg, C. Lange and H. Thomas, *Permutahedra and generalized associahedra*. Adv. Math. **226** (2011), no. 1, 608–640.

[17] O. Iyama, I. Reiten, N. Reading, and H. Thomas, *article in preparation*.

[18] S. E. Law and N. Reading, *The Hopf algebra of diagonal rectangulations*. J. Combin. Theory Ser. A **119** (2012), no. 3, 788–824.

[19] R. Marsh, M. Reineke and A. Zelevinsky, *Generalized associahedra via quiver representations*. Trans. Amer. Math. Soc. **355** (2003) no. 10, 4171–4186.

[20] N. Reading, *Lattice congruences, fans and Hopf algebras*. J. Combin. Theory Ser. A **110** (2005) no. 2, 237–273.

[21] N. Reading, *Cambrian lattices*. Adv. Math. **205** (2006) no. 2, 313–353.

[22] N. Reading, *Clusters, Coxeter-sortable elements and noncrossing partitions*. Trans. Amer. Math. Soc. **359** (2007), no. 12, 5931–5958.

[23] N. Reading, *Sortable elements and Cambrian lattices*. Algebra Universalis **56** (2007), no. 3-4, 411–437.

[24] N. Reading, *Noncrossing diagrams and canonical join representations*. Preprint, 2014. (arXiv:1405.6904)

[25] N. Reading and D. E. Speyer, *Cambrian Fans*. J. Eur. Math. Soc. (JEMS) **11** no. 2, 407–447.

[26] N. Reading and D. E. Speyer, *Cambrian frameworks for cluster algebras of affine type*. In preparation, 2015.

[27] V. Reiner, *Non-crossing partitions for classical reflection groups*, Discrete Math. **177** (1997), no. 1-3, 195–222.

[28] B. Salvy and P. Zimmermann. *GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable*. ACM Trans. Math. Softw. **20** (1994), no. 2, 163–177.

[29] J. Stembridge, *Maple packages for symmetric functions, posets, root systems, and finite Coxeter groups*. Available at http://www.math.lsa.umich.edu/~jrs/maple.html.

[30] J. West, *personal communication*, 2006.

[31] N. Williams, *Cataland*. Ph.D. Thesis, University of Minnesota, 2013.

[32] G. Ziegler, *Lectures on polytopes*. Graduate Texts in Mathematics, **152**. Springer-Verlag, New York, 1995.