# Bijactions in Cataland

Nathan Williams*

LaCIM, Montréal, Québec, Cananda

**Abstract.** In this abstract, I will survey the story of two enumerative miracles that relate certain Coxeter-theoretic objects and other poset-theoretic objects. The first miracle relates reduced words and linear extensions, while the second may be thought of as relating group elements and order ideals. The purpose of this abstract is to use a conjecture from my thesis to present both miracles in the same light.

**Résumé.** Dans ce résumé, j'étudie l'histoire de deux miracles énumératifs qui relient certains objets de la théorie de Coxeter et d'autres objets de la théorie des posets. Le premier miracle relie des mots réduits et des extensions linéaires, tandis que le second relie des éléments du groupe et des idéaux d'ordre. Le but de ce résumé est d'utiliser une conjecture de ma thèse afin de présenter les deux miracles sous la même lumière.

**Keywords:** Cambrian, Catalan, Coxeter, subword, toggle

## 1 Introduction

In this abstract, I will survey the story of two enumerative miracles that relate certain Coxeter-theoretic objects and other poset-theoretic objects. The first miracle relates reduced words and linear extensions, while the second may be thought of as relating group elements and order ideals. The purpose of this abstract is to use a conjecture from my thesis to display both miracles in the same light [W].

The remainder of this introductory section is used to motivate the plausibility of such relationships by recalling a case for which the correspondences are immediate [Stem]. Section 2 is then devoted to defining the Coxeter-theoretic objects using the braid arrangement, while Section 3 similarly interprets the poset-theoretic objects in the Shi arrangement. These two sections are wedded in Figure 3. The punchline of this abstract lies in the tantalizing and explicit analogy drawn in Theorem 4.1 and Conjecture 4.4.

Let $(W, S)$ be a finite Coxeter system and for $w \in W$ let $\mathcal{R}(w)$ be the set of reduced words in the simple generators $S$ for $w$. If $w, w' \in \mathcal{R}(w)$, we say that $w$ and $w'$ lie in the same *commutation class* if one may be transformed into the other using only commutations. An element $w \in W$ is *fully commutative* if all reduced words for $w$ are in the same commutation class. Such elements enjoy many delightful properties—for example, the weak order interval $\text{Weak}(W, w) := [e, w]_S$ is a distributive lattice for $w$ fully commutative [Stem].

Let $w = s_1 \cdots s_k$ be a reduced $S$-word for a fully commutative element $w$. Define a partial order $\le$ on $[k]$ by the transitive closure of the relations $i < j$ if $i < j$ and $s_i$ and $s_j$ don't commute. This partial

<footnote>*Email: nathan.f.williams@gmail.com.</footnote>
ordering defines a “root poset” $\Phi^+(W, w)$ on $[k]$ called a *heap*, which for $W$ crystallographic coincides with the restriction of the root poset $\Phi^+(W)$ to the inversions of $w$. If $w, w'$ are two reduced words for a fully commutative element $w$, then it is not hard to see that $\Phi^+(W, w)$ and $\Phi^+(W, w')$ are isomorphic. We may therefore refer to the heap $\Phi^+(W, w)$ for $w$ fully commutative.

We write $\mathcal{L}(\mathcal{P})$ for the set of linear extensions of a poset $\mathcal{P}$ and $\mathcal{J}(\mathcal{P})$ for its set of order ideals. The entire structure of the interval Weak$(W, w)$ is now described by $\Phi^+(W, w)$, as illustrated in Figure 1.

**Theorem 1.1 (Stem)**

For $w$ fully commutative,

$$1. |\mathcal{L}(\Phi^+(W, w))| = |\mathcal{R}(w)|; \text{ and}$$

$$2. |\mathcal{J}(\Phi^+(W, w))| = |\text{Weak}(W, w)|.$$

Note that when $w$ is fully commutative, inversion sets for elements in Weak$(W, w)$ are order ideals in $\Phi^+(W, w)$.

It seems nothing short of a miracle, then, that the root poset $\Phi^+(W)$ often behaves like a heap for the longest element $w_0 \in W$ (definitions are given in Section 3.1 and 2.2). That is, not only does the equality $|\mathcal{L}(\Phi^+(W))| = |\mathcal{R}(w_0)|$ hold in many types, but there is also a subset of elements of $W$—N. Reading’s sortable elements, Sort$(W, c)$, defined in Section 2.3—for which $|\mathcal{J}(\Phi^+(W))| = |\text{Sort}(W, c)|$.

More precisely, we state a companion theorem to Theorem 1.1.

<figure><img src="image_1.png" /><figcaption>Fig. 1: The heap for the fully commutative element $w = s_2s_1s_3s_2 \in A_3$ is isomorphic to the poset $[2] \times [2]$. Weak$(A_3, w) \cong \mathcal{J}([2] \times [2])$ is pictured above.</figcaption></figure>

**Theorem 1.2 (Stan84, EG, Hai92, W, Rein, Read)**

$$1. |\mathcal{L}(\Phi^+(W))| = |\mathcal{R}(w_0)| \text{ for } W \text{ of type } A_n, B_n, H_3, \text{ or } I_2(m); \text{ and}$$

$$2. |\mathcal{J}(\Phi^+(W))| = |\text{Sort}(W, c)| \text{ for } W \text{ not of type } H_4,$$

The remainder of this abstract will be devoted to unravelling these two statements in tandem.

# 2 Coxeter-theoretic objects

On the Coxeter-theoretic side, we require two sets of objects: reduced words for the longest element and sortable elements. Both sets of objects have natural cyclic actions, which turn out to be related. Using the braid arrangement, I will describe these objects and their cyclic actions geometrically.

## 2.1 The braid arrangement

Let $(W, S)$ be a *finite Coxeter system*—a group $W$ with presentation

$$\langle S : (ss')^{m(s,s')} = e \rangle,$$

where $m(s, s') = 1$ iff $s = s'$, $m(s, s') = m(s', s) \in \mathbb{N} \cup \{\infty\}$, and $e$ is the identity.
We quickly review the geometric representation of finite Coxeter systems. Let $V$ be a vector space over $\mathbb{R}$ with basis $\Delta(W) := \{\alpha_s : s \in S\}$; these $\alpha_s$ are called *simple roots*. Define a symmetric bilinear form $B$ on $V$ by $B(\alpha_s, \alpha_{s'}) = -\cos(\frac{\pi}{m(s,s')})$. For each $s \in S$, define a reflection $s : V \to V$ by $s(\beta) := \beta - 2B(\alpha_s, \beta)\alpha_s$. This extends uniquely to an injective homomorphism from $W$ to $GL(V)$. The *root system* for $W$ is defined by

$$ \Phi(W) := \{w(\alpha_s) : w \in W, s \in S\}. $$

Any $\alpha \in \Phi(W)$ may be written uniquely in the form $\alpha = \sum_{s \in S} c_s \alpha_s$, where either each $c_s \ge 0$ or each $c_s \le 0$. The *positive roots* $\Phi^+(W)$ are those roots that may be expressed as a nonnegative sum of the $\alpha_s$, and are in bijection with the *reflections* $T := \{wsw^{-1} : w \in W, s \in S\}$. We write $\alpha_t$ for the positive root corresponding to the reflection $t$. For $\alpha \in \Phi(W)$ and $p \in \mathbb{Z}$, define the hyperplane

$$ H_{\alpha,p} := \{v \in V : B(\alpha, v) = p\}. $$

**Definition 2.1** The braid arrangement is the set of hyperplanes

$$ \text{Braid}(W) := \{H_{\alpha,0} : \alpha \in \Phi^+(W)\}. $$

The connected regions or *chambers* of $V \setminus \cup_{\alpha \in \Phi^+(W)} H_{\alpha,0}$ are in bijection with the elements of $W$. The *fundamental chamber A* is chosen to correspond to the identity element; the element $w$ then corresponds to the chamber $wA$.

Semisimple Lie algebras provide one motivation for the geometric representation. A root system is associated to each semisimple Lie algebra, and the hyperplanes perpendicular to the roots divide the space $V$ into chambers; the reflections in these hyperplanes generate a group that permutes the chambers. Such groups are a subset of the finite irreducible Coxeter groups called Weyl groups or *crystallographic Coxeter groups*, because their root systems satisfy the additional hypothesis that $\frac{2(\beta, \alpha)}{(\alpha, \alpha)} \in \mathbb{Z}$ for $\alpha, \beta \in \Phi(W)$. The non-crystallographic finite irreducible Coxeter groups are $H_3, H_4$, and $I_2(m)$ for $m \neq 2, 3, 4, 6$.

## 2.2 Reduced words

**Definition 2.2** Define a gallery in a hyperplane arrangement $\mathcal{H}$ to be a sequence of chambers

$$ (C_0, C_1, \dots, C_\ell), $$

where $C_i$ and $C_{i+1}$ share the bounding hyperplane $H_{i+1}$. Let $\text{Path}(C, C', \mathcal{H})$ be the set of minimal-length galleries from $C$ to $C'$ in $\mathcal{H}$.

When $\mathcal{H} = \text{Braid}(W)$, a gallery $w \in \mathcal{R}(w) := \text{Path}(A, wA, \text{Braid}(W))$ spells out a reduced word for $w$ in the simple reflections $S$, where we abbreviate $w = (A, s_{i_1}A, s_{i_1}s_{i_2}A, \dots, s_{i_1}s_{i_2}\cdots s_{i_\ell}A)$ as $w = s_{i_1}s_{i_2}\cdots s_{i_\ell}$; we define $w$'s length $\ell_S(w) := \ell$. The inversion sequence $\text{inv}(w) := (\alpha_1, \alpha_2, \dots, \alpha_\ell)$ records the order in which the hyperplanes $H_{\alpha_i, 0}$ are crossed by $w \in \mathcal{R}(w)$. The unordered set of traversed hyperplanes is independent of the gallery $w$ and is called $w$'s inversion set.

**Definition 2.3** Finite Coxeter groups have a unique longest element $w_0$ whose inversion set is all of $\Phi^+(W)$. The inversion sequence of $w_0 \in \mathcal{R}(w_0)$ imposes a total ordering $<_{w_0}$ on all positive roots called a *root order*.
Root orders are often given in the literature as certain tableaux: they correspond with the notion of P. Edelman and C. Greene's balanced tableaux in type $A_n$ [EG].

We define an action on a reduced word $w_0 \in \mathcal{R}(w_0)$, denoting conjugation by $w_0$ by $\bar{w} := w_0ww_0$.

**Definition 2.4** Let $N := \ell_S(w_0) = |\Phi^+(W)|$. Define $\mathfrak{Pro} : \mathcal{R}(w_0) \to \mathcal{R}(w_0)$ by

$$ \mathfrak{Pro} (s_1 s_2 s_3 \cdots s_N) := s_2 s_3 \cdots s_N \bar{s}_1. $$

If we let the W-permutahedron be the adjacency graph of chambers in the braid arrangement for W, then $w_0 \in \mathcal{R}(w_0)$ is a path from $e$ to $w_0$ and $\bar{w}_0$ may be drawn as the complementary path back from $w_0$ to $e$. Their concatenation $w_0 \bar{w}_0$ traces out a loop around the W-permutahedron; acting by $\mathfrak{Pro}$ is simply a rotation of this loop. As $\ell_S(w_0) = N$, $\mathfrak{Pro}$ has order $N$ if $\bar{s} = s$ for $s \in S$ and order $2N$ otherwise.

We may rephrase Definition 2.4 in terms of Hurwitz operators on inversion sequences, thereby sacrificing efficiency for homology with Definition 3.4. The definition

$$ \mathfrak{Pro}_i(\mathrm{inv}(\mathbf{w}_0)) = \mathfrak{Pro}_i(\alpha_{t_1}, \dots, \alpha_{t_i}, \alpha_{t_{i+1}}, \dots, \alpha_{t_N}) := (\alpha_{t_1}, \dots, t_i(\alpha_{t_{i+1}}), \alpha_{t_i}, \dots, \alpha_{t_N}), $$

allows us to factor Definition 2.4 as $\mathrm{inv}(\mathfrak{Pro}(\mathbf{w}_0)) = (\mathfrak{Pro}_{N-1} \cdots \mathfrak{Pro}_2 \mathfrak{Pro}_1)(\mathrm{inv}(\mathbf{w}_0))$.

## 2.3 Sortable elements

In light contrast to the theory of fully commutative elements summarized in Section 1, we must restrict our attention from all elements of W to the subset consisting of N. Reading's c-sortable elements. For a generalization that includes these two extremes as special cases, see Chapter 5 of [W].

Let $n := |S|$ and let $\pi$ be a permutation on $[n]$. A Coxeter element $c = s_{\pi_1}s_{\pi_2}\cdots s_{\pi_n}$ is a product of the simple reflections in any order. Fix a Coxeter element $c$ and choose any reduced word $c \in \mathcal{R}(c)$ (this choice is immaterial, since any two such words will agree up to commutations). The c-sorting word $w(c)$ of $w$ is the lexicographically first (in position) reduced S-subword of $w$ of the word

$$ c^{\infty} = (s_{\pi_1}s_{\pi_2}\cdots s_{\pi_n} \mid s_{\pi_1}s_{\pi_2}\cdots s_{\pi_n} \mid s_{\pi_1}s_{\pi_2}\cdots s_{\pi_n} \mid \cdots). $$

An element $w \in W$ is c-sortable if its c-sorting word defines a decreasing sequence of subsets of positions in $c$. We denote the set of c-sortable elements by $\mathrm{Sort}(W, c)$.

The W-Catalan number is the uniform formula

$$ \mathrm{Cat}(W) := \prod_{i=1}^{n} \frac{h+d_i}{d_i}, $$

where the $d_i$ are the degrees of W and the Coxeter number $h := 2N/n$ is the order of a Coxeter element $c$. For the symmetric group $W = \mathfrak{S}_n$, it is easy to check that $\mathrm{Cat}(W)$ specializes to the classical Catalan number $\mathrm{Cat}(\mathfrak{S}_n) = \frac{1}{n+1} \binom{2n}{n}$. Of the over two hundred objects counted by $\mathrm{Cat}(\mathfrak{S}_n)$ that R. Stanley has compiled, one example is D. Knuth's stack-sortable (231-avoiding) permutations, which coincide with the c-sortable elements when $W = \mathfrak{S}_n$ and $c = (123 \dots n)$. The c-sortable elements therefore generalize the stack-sortable permutations in two directions simultaneously: from $\mathfrak{S}_n$ to an arbitrary Coxeter group, and from the cycle $(123 \dots n)$ to an arbitrary Coxeter element [Read]. Remarkably, the Catalan number is robust enough to survive this generalization—just as stack-sortable permutations are counted by $\mathrm{Cat}(\mathfrak{S}_n)$,
the number of c-sortable elements is counted by Cat($W$). The proof of this enumeration has so far resisted a uniform treatment and to date remains case-by-case.

To bridge the gap between reduced words for the longest element and sortable elements—and to draw tight the analogy at the heart of this abstract—we use a marvelous description of clusters due to C. Ceballos, J.-P. Labbé, and C. Stump [CLS], building on work of A. Woo. N. Reading has shown that sortable elements and clusters are in bijection.

**Definition 2.5 ([CLS])** Fix the word in simple reflections $\mathbf{Q} = (\mathbf{Q}_1, \mathbf{Q}_2, \dots, \mathbf{Q}_{N+n}) := \mathbf{c}w_0(\mathbf{c})$. The $(W, c)$-subwords are the elements of the set

$$S(W, c) := \{(i_1 \le i_2 \le \dots \le i_N) : \mathbf{Q}_{i_1} \mathbf{Q}_{i_2} \dots \mathbf{Q}_{i_N} = w_0\}.$$

We now extend the cyclic action $\mathfrak{P}\mathfrak{t}\mathfrak{o}$ from $\mathcal{R}(w_0)$ to $S(W, c)$. Shift a subword in $S(W, c)$ one position to the left to obtain a subword of $\mathbf{Q}' = s_{\pi_2} \cdots s_{\pi_n} \mathbf{w}_0(\mathbf{c})\bar{s}$ (the leftmost letter $s$ is sent to the rightmost letter $\bar{s}$). If $c' = s^{-1}cs$ then, up to commutations, $s_{\pi_2} \cdots s_{\pi_n} \mathbf{w}_0(\mathbf{c})\bar{s} = \mathbf{c}'\mathbf{w}_0(\mathbf{c}')$, so that the resulting sub-word corresponds to a subword in $S(W, c')$ [CLS]. This defines a map $\mathfrak{C}\mathfrak{a}\mathfrak{m}\mathfrak{b}_s : S(W, c) \to S(W, s^{-1}cs)$.

**Definition 2.6** Let $\mathbf{c} = s_{\pi_1}s_{\pi_2}\cdots s_{\pi_n}$ be a reduced $S$-word for $\mathbf{c}$. Define the $c$-Cambrian rotation $\mathfrak{C}\mathfrak{a}\mathfrak{m}\mathfrak{b}_c : S(W, c) \to S(W, c)$ by

$$\mathfrak{C}\mathfrak{a}\mathfrak{m}\mathfrak{b}_c := \mathfrak{C}\mathfrak{a}\mathfrak{m}\mathfrak{b}_{s_{\pi_n}} \cdots \mathfrak{C}\mathfrak{a}\mathfrak{m}\mathfrak{b}_{s_{\pi_2}} \mathfrak{C}\mathfrak{a}\mathfrak{m}\mathfrak{b}_{s_{\pi_1}}.$$

As with $\mathcal{R}(w_0)$, we find it convenient to complete the word $\mathbf{Q}$ to the word $\overline{\mathbf{Q}\mathbf{Q}}$, so that $\mathfrak{C}\mathfrak{a}\mathfrak{m}\mathfrak{b}_c$ becomes a simple rotation of the longer word. It is essential to note here that, up to commutations,

$$\overline{\mathbf{Q}\mathbf{Q}} = \mathbf{c}w_0(\mathbf{c})\overline{\mathbf{c}w_0(\mathbf{c})} = \mathbf{c}^{h+2}.$$

It follows that an $(h+2)$-fold application of $\mathfrak{C}\mathfrak{a}\mathfrak{m}\mathfrak{b}_c$ is the identity. Let the $(W, c)$-Cambrian graph be the graph with vertices the positions in $S(W, c)$ and edges between the subwords $(i_1 \le i_2 \le \dots \le i_N)$ and $(j_1 \le j_2 \le \dots \le j_N)$ if $|\{i_1, i_2, \dots, i_N\} \setminus \{j_1, j_2, \dots, j_N\}| = 1$. Cambrian rotation is an automorphism of the Cambrian graph.

# 3 Poset-theoretic objects

There are two combinatorial structures on arbitrary posets that we will consider: linear extensions and order ideals. Each of these has a natural cyclic action whose orbit structure is wild in general, but well-behaved for root posets. As the Coxeter-theoretic objects of Section 2 were defined using the braid arrangement, we similarly interpret the poset-theoretic objects in the Shi arrangement (when possible).

## 3.1 The Shi arrangement and root posets

**Definition 3.1 ([Shi])** The $W$-Shi arrangement is the set of hyperplanes

$$\mathrm{Shi}(W) := \{H_{\alpha, i} : \alpha \in \Phi^+(W) \text{ and } i = 0, 1\}.$$

For $W$ crystallographic, J.-Y. Shi proved that $\mathrm{Shi}(W)$ has $(h+1)^n$ regions by showing that the inverses of the elements of the *affine group* labeling the minimal alcoves of the $\mathrm{Shi}(W)$ regions coalesce into a $(h+1)$-fold dilation of the fundamental alcove [Shi]. While regions of the braid arrangement are naturally labeled by elements of $W$, regions of $\mathrm{Shi}(W)$ are called the *$W$-parking functions*.
An order ideal of a poset $\mathcal{P}$ is a set $I \subseteq \mathcal{P}$ such that if $p \in I$ and $p' < p$, then $p' \in I$. We write $\mathcal{J}(\mathcal{P})$ for the set of all order ideals of $\mathcal{P}$, which forms a distributive lattice under inclusion. The root poset for a Coxeter group $W$ is a partial order on positive roots given by $\alpha \le \beta \in \Phi^+(W)$ if $\beta - \alpha$ is a nonnegative sum of positive roots. Order ideals of the root poset may be used to label the regions of $\mathrm{Shi}(W)$ in the following way (i).

**Theorem 3.2 ([Shi])** For crystallographic $W$, the regions of $\mathrm{Shi}(W)$ in the chamber $wA$ are in bijection with order ideals in the subposet of $\Phi^+(W)$ consisting of the non-inversions of $w$.

Root posets (as defined above) for non-crystallographic $W$ do not enjoy the same properties as their crystallographic brethren. Nevertheless, in types $H_3$ and $I_2(m)$, D. Armstrong constructed surrogate root posets with desirable behavior [Arm]. These posets are given in Figure 2, and we will refer to them as the root posets of types $H_3$ and $I_2(m)$. In type $I_2(m)$, these are natural generalizations of the root posets for the crystallographic dihedral types $A_2$, $B_2$, and $G_2$, and may be labeled by reflections in an obvious way. The root poset for $H_3$ may be explained through a folding of $D_5$, but it also arises from the fully commutative quotient $(H_3, I_2(5))$. M. Cuntz and C. Stump have computed that there is no fully satisfactory poset for $H_4$.

## 3.2 Linear extensions

Let $\mathcal{P}$ be a poset with $N$ elements and let $[N] = \{1, 2, \dots, N\}$. A linear extension of $\mathcal{P}$ is a bijection $\mathcal{L} : \mathcal{P} \to [N]$ such that if $p < p'$, then $\mathcal{L}(p) < \mathcal{L}(p')$. We write $\mathcal{L}(\mathcal{P})$ for the set of linear extensions of $\mathcal{P}$. Just as reduced words for the longest element are galleries in $\mathrm{Braid}(W)$, linear extensions of the positive root poset may be seen as galleries in $\mathrm{Shi}(W)$.

To see both simultaneously in $\mathrm{Shi}(W)$, we identify three regions: the fundamental alcove $A_0 := \{x : B(\alpha, x) \ge 0 \text{ for } \alpha \in \Delta \text{ and } B(-\alpha_0, x) \le 1\}$ (where $\alpha_0$ is the highest root in $\Phi^+(W)$), the region $P := \{x : B(\alpha, x) \ge 1 \text{ for } \alpha \in \Delta\}$, and the region $N := \{x : B(\alpha, x) \le 0 \text{ for } \alpha \in \Delta\}$. The following proposition follows from Theorem 3.2 and the discussion above, and is illustrated in Figure 3.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** D. Armstrong's surrogate root posets of types $H_3$ and $I_2(m)$, labeled by reflections.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** Galleries in $\mathrm{Shi}(A_2)$ from $A_0$ (middle, in dark gray) to $N$ (top right) and from $A_0$ to $P$ (bottom left).</figcaption></figure>

<footnote>(i) I thank B. Rhoades for explaining this to me.</footnote>
**Proposition 3.3** For W crystallographic,

• $\mathrm{Path}(A_0, N, \mathrm{Shi}(W)) = \mathcal{R}(w_0)$; and

• $\mathrm{Path}(A_0, P, \mathrm{Shi}(W)) = \mathcal{L}(\Phi^+(W))$.

The required cyclic action on linear extensions is M.-P. Schützenberger’s ubiquitous promotion. R. Stanley has written an excellent survey article on the theory [Stan09].

**Definition 3.4** Let $\mathcal{L}$ be a linear extension of a poset $\mathcal{P}$ with $N$ elements, and let $\mathrm{Pro}_i(\mathcal{L})$ be the linear extension obtained from $\mathcal{L}$ by switching the labels $i$ and $i + 1$ if $\mathcal{L}^{-1}(i)$ and $\mathcal{L}^{-1}(i + 1)$ do not have a covering relation. Define promotion $\mathrm{Pro} : \mathcal{L}(\mathcal{P}) \to \mathcal{L}(\mathcal{P})$ by

$$ \mathrm{Pro} := \mathrm{Pro}_{N-1}\mathrm{Pro}_{N-2}\cdots\mathrm{Pro}_1. $$

This definition should be digested along with the discussion following Definition 2.4. Note that promotion is often equivalently defined using *jeu-de-taquin*.

## 3.3 Order ideals

Similarly to how the sortable elements may be seen as certain regions in Braid($W$), Theorem 3.2 states that order ideals of the root poset are in bijection with regions of $\mathrm{Shi}(W)$ that lie in the chamber $A$. We emphasize these objects with their own definition.

**Definition 3.5** For W a crystallographic Coxeter group, $H_3$, or $I_2(m)$, the nonnesting partitions $\mathrm{NN}(W)$ are the order ideals in the root poset $\Phi^+(W)$.

The nonnesting partitions are so named because of their combinatorial model in type $A_n$, where they are realized as set partitions of $[n+1]$ avoiding “nesting” configurations (in reference to this model, we use the symbol $\mathcal{R}$ for a particular nonnesting partition, while reserving $\mathcal{W}$ for a noncrossing partition). The nonnesting partitions are intrinsically quite different from the sortable elements and subwords of Section 2.3: they do not depend on a Coxeter element and the extension to $H_3$ and $I_2(m)$—though undeniably correct—is strangely artificial. Most importantly, the nonnesting partitions have been uniformly counted by $\mathrm{Cat}(W)$, while the noncrossing partitions, sortable elements, and clusters have not [CP].

We act on order ideals using P. Cameron and D. Fon-der-Flaass’s *toggles* [CF].

**Definition 3.6** For each $p \in \mathcal{P}$, define $\mathrm{Tog}_p : \mathcal{J}(\mathcal{P}) \to \mathcal{J}(\mathcal{P})$ by

$$ \mathrm{Tog}_p(I) := \begin{cases} I \cup \{p\} & \text{if } p \notin I \text{ and if } p' < p \text{ then } p' \in I; \\ I \setminus \{p\} & \text{if } p \in I \text{ and if } p' > p \text{ then } p' \notin I; \text{ and} \\ I & \text{otherwise.} \end{cases} $$

That is, $\mathrm{Tog}_p$ acts by *toggling* the element $p$ if possible. These operators are immediately seen to satisfy $\mathrm{Tog}_p^2(I) = I$ and $(\mathrm{Tog}_p \mathrm{Tog}_{p'})^2(I) = I$ when $p$ and $p'$ do not have a covering relation. Given a sequence of poset elements $(p_1, p_2, \dots, p_i)$, we abbreviate $\mathrm{Tog}_{p_1 p_2 \dots p_i} := \mathrm{Tog}_{p_1} \dots \mathrm{Tog}_{p_i}$.

In [SW], J. Striker and I interpreted promotion of linear extensions of certain posets as an element of a toggle group acting on *columns*; for such posets, there was a conjugate action given by acting on *rows* which we called *rowmotion*. An extension of this idea was used in [RS] to uniformly prove a CSP for all minuscule posets. H. Thomas remarked to me that the column order of toggles given in [SW]
corresponded to a root order in type $A_n$, and suggested that a *nonnesting c-Kreweras complement* be defined by $Tog_{\mathrm{inv}(w_0(c))}$. But it is well-known that there are two natural actions on W-Catalan objects: the Kreweras complement (corresponding to rotation of noncrossing matchings in type A) and Cambrian rotation (corresponding in type A to rotation of triangulations). Drawing on H. Thomas's observation, I was able to find the following definition. It is not much of an exaggeration to say that the entire worth of this abstract is contained in it and Conjecture 4.4. For further discussion, see Section 4.4 of [W].

**Definition 3.7** *Define the nonnesting c-Cambrian rotation $\mathrm{Camb}_c : \mathrm{NN}(W) \to \mathrm{NN}(W)$ by*

$$ \mathrm{Camb}_c := \mathrm{Tog}_{\mathrm{inv}(w_0(c))} \mathrm{Tog}^+_{\mathrm{inv}(w_0(c))}, $$

$$ \text{where } \mathrm{Tog}_{\alpha}^{+}(\mathcal{M}) := \begin{cases} \mathrm{Tog}_{\alpha}(\mathcal{M}) & \text{if } \alpha \notin \Delta(W); \\ \mathcal{M} & \text{otherwise,} \end{cases} \quad \text{and } \mathrm{Tog}_{\alpha_1 \alpha_2 \cdots \alpha_i}^{+} := \mathrm{Tog}_{\alpha_1}^{+} \cdots \mathrm{Tog}_{\alpha_i}^{+} \mathrm{Tog}_{\alpha_1}^{+}. $$

Just as Definitions 2.4 and 3.4 were twisted into similar forms, it is possible to factor Definition 2.6 as a walk on the $(W, c)$-Cambrian graph in the order suggested by Definition 3.7 [W].

# 4 Miracles

With four cyclic actions in our quiver—$\mathfrak{Pro}$ on $\mathcal{L}(\Phi^+(W))$, Pro on $\mathcal{R}(w_0)$, $\mathrm{Camb}_c$ on $\mathcal{S}(W, c)$, and $\mathrm{Camb}_c$ on $\mathrm{NN}(W)$—we fix our sights on Theorem 1.2. In this section, we show how these actions induce the two bijections of Theorem 1.2; we call the two resulting maps *bijactions*, as they are bijections induced by actions. *Caution:* Theorem 1.2 has been proven, the induced map for Part 1 of Theorem 1.2 has been proven to be a bijection, but the induced map for Part 2 of Theorem 1.2 is, for now, conjectural.

## 4.1 Theorem 1.2, Part 1: Galleries

**Theorem 4.1** For $W$ a Coxeter group of type $A_n, B_n, H_3$, or $I_2(m)$, there is a bijaction between $\mathcal{L}(\Phi^+(W))$ under $\mathfrak{Pro}$ and $\mathcal{R}(w_0)$ under Pro.

As stated, this theorem is false in other types (other than the redundancy incurred by $D_3$). For example, in $D_4$ we have $|\mathcal{L}(\Phi^+(D_4))| = 2400$ and $|\mathcal{R}(w_0)| = 2316$, while in $F_4$, $|\mathcal{L}(\Phi^+(F_4))| = 2311020 = 2^2 \cdot 3^2 \cdot 5 \cdot 37 \cdot 347$ and $|\mathcal{R}(w_0)| = 2144892 = 2^2 \cdot 3 \cdot 47 \cdot 3803$. (ii)

In the crystallographic types $A_n, B_n$, and $G_2$, Section 3.1 implies that Part 1 of Theorem 1.2 may be rephrased as the equality $|\mathrm{Path}(A_0, P, \mathrm{Shi}(W))| = |\mathrm{Path}(A_0, N, \mathrm{Shi}(W))|$. It is tempting—though almost certainly overly bold—to use this language to generalize to the $m$-Shi arrangement.

Before revealing the promised bijaction, we briefly review some history. Based on computations by P. Edelman, J. Goodman, and R. Pollack, R. Stanley observed the surprising coincidence that $|\mathcal{R}(w_0)|$ in type $A_n$ and $|\mathcal{L}(\Phi^+(A_n))|$ both begin 1, 2, 16, 768, ... [Stan84]. He was able to prove this equinumeration with symmetric functions [Stan84]. P. Edelman and C. Greene later produced a gorgeous bijection from $\mathcal{L}(\Phi^+(A_n))$ to $\mathcal{R}(w_0)$ using equivariance of $\mathfrak{Pro}$ and Pro [EG]. M. Haiman proved that an analogous map was a bijection from $\mathcal{L}(\Phi^+(B_n))$ to $\mathcal{R}(w_0)$, confirming a conjecture of R. Proctor [Hai92]. Theorem 4.1 is therefore only a tiny extension of these spectacular results.

<footnote>(ii) I thank R. Edman for computing $|\mathcal{R}(w_0)|$ in $F_4$.</footnote>
**Bijaction 4.2.** The Edelman-Greene bijection from $\mathcal{L}(\Phi^+(W))$ to $\mathcal{R}(w_0)$ is given as follows. Beginning with $\mathcal{L} \in \mathcal{L}(\Phi^+(W))$, compute the orbit

$$(\mathrm{Pro}^{N-1}(\mathcal{L}), \mathrm{Pro}^{N-2}(\mathcal{L}), \dots, \mathcal{L}).$$

The corresponding reduced word is then given by replacing each linear extension $\mathrm{Pro}^k(\mathcal{L})$ in this sequence by the simple reflection $s_i$ such that $(\mathrm{Pro}^k(\mathcal{L})(\alpha_{s_i})) = N$.

As mentioned above, this is proven for types A and B in [EG] and [Hai92], respectively. For $I_2(m)$, the correspondence between the two reduced words for $w_0$ and the two linear extensions of D. Armstrong's "positive root poset" of Table 2 is immediate. Lastly, there are 286 linear extensions of the "positive root poset" of type $H_3$, divided as 2 * 3, 2 * 5, and 18 * 15 under Pro (where $i * j$ is short for $i$ orbits of size $j$). These orbits equivariantly map to orbits of reduced words for the longest element under $\mathfrak{Pro}$.

<figure><img src="image_4.png" /><figcaption>These map to the reduced word $s_3s_1s_2s_1s_2 s_3s_1s_2s_1s_2 s_3s_1s_2s_1s_2$, as illustrated in the table below.</figcaption></figure>

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

## 4.2 Theorem 1.2, Part 2: Regions

**Conjecture 4.4** For W a Coxeter group not of type $H_4$, there is a bijection between $\mathcal{J}(\Phi^+(W))$ under $\mathrm{Camb}_c$ and $\mathcal{S}(W, c)$ under $\mathrm{Camb}_c$.

We again review some history. The precursor to Conjecture 4.4 is a conjecture of D. Panyushev [Pan], which was refined by D. Bessis and V. Reiner [BR]. D. Armstrong, C. Stump, and H. Thomas proved this conjecture by expertly exploiting a coincidence between the Kreweras complement on noncrossing partitions and rowmotion on nonnesting partitions. Using parabolic induction, this coincidence allowed them to uniformly characterize a bijection between the two sets [AST]. The advantage of Cambrian rotation over the Kreweras complement is that we are able to avoid all inductive unpleasantness.

**Bijaction 4.5** The bijaction from $\mathcal{J}(\Phi^+(W))$ to $\mathcal{S}(W, c)$ is given as follows. As remarked after Definition 2.5, we may use commutations to write a subword of $\mathbf{Q}$ in $\mathcal{S}(W, c)$ as a subword of $\mathbf{Q}\overline{\mathbf{Q}} = c^{h+2}$.
Beginning with a nonnesting partition $\mathcal{N}$, compute the orbit

$$ (\mathcal{N}, \mathrm{Camb}_c(\mathcal{N}), \mathrm{Camb}_c^2(\mathcal{N}), \dots, \mathrm{Camb}_c^{h+1}(\mathcal{N})). $$

The subword of $c^{h+2}$ is given by replacing each nonnesting partition $\mathrm{Camb}_c^k(\mathcal{N})$ in this sequence by a copy of $c$, marking those simple roots that lie in $\mathrm{Camb}_c^k(\mathcal{N})$.

Conjecture 4.4 has been verified in all types of rank less than or equal to 8 using Bijaction 4.5. Observe that Bijactions 4.2 and 4.5 have a very similar flavor.

<figure><img src="image_6.png" /><figcaption>One four element $\mathrm{Camb}_c$-orbit is illustrated below, along with the subword of $\mathcal{Q} = \mathrm{cw}_0(\mathcal{C})$ it determines.</figcaption></figure>

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

# 5 Conclusion

In this section, we return to the fully commutative motivation from the Introduction and tie Theorems 1.1 and 1.2 together with four pairs of identities. I apply some reasonable conclusions from these identities to Part 1 of Theorem 1.2, but I am unable to offer any explanation for the generality of Part 2.

Define the posets $\square_n := [n] \times [n]$, $\sqcup_n = \mathcal{J}([2] \times [n])$, and $\mathfrak{a}_n := \mathcal{J}^n([2] \times [2])$. These are the (Gaussian) root posets for certain maximal parabolic quotients $W^J$ whose longest element $w_0^J$ is fully commutative. All such parabolic quotients were classified by J. Stembridge in [Stem], and their root posets coincide in crystallographic type with the minuscule posets. The following theorem relates Theorems 1.1 and 1.2.

**Theorem 5.1** We have the following equalities:

$$ |\mathcal{L}(\Phi^+(A_n))| = 2^{n(n-1)/2} |\mathcal{L}(\mathfrak{q}_n)|, \quad 2^n |\mathcal{J}(\Phi^+(A_n) \times [k])| = |\mathcal{J}(\mathfrak{q}_n \times [2k+1])|; $$

$$ |\mathcal{L}(\Phi^+(B_n))| = |\mathcal{L}(\square_n)|, \quad |\mathcal{J}(\Phi^+(B_n) \times [k])| = |\mathcal{J}(\square_n \times [k])|; $$

$$ |\mathcal{L}(\Phi^+(H_3))| = |\mathcal{L}(\mathfrak{q}_5)|, \quad |\mathcal{J}(\Phi^+(H_3) \times [k])| = |\mathcal{J}(\mathfrak{q}_5 \times [k])|; \text{ and} $$

$$ |\mathcal{L}(\Phi^+(I_2(2m)))| = |\mathcal{L}(\mathfrak{a}_{m-2})|, \quad |\mathcal{J}(\Phi^+(I_2(2m)) \times [k])| = |\mathcal{J}(\mathfrak{a}_{m-2} \times [k])| \text{ for } m \ge 2. $$
We will refer to an equation in Theorem 5.1 by its row $(A, B, H$, or $I$) and its column $(\mathcal{L}$ or $\mathcal{J}$). The hook-length and shifted hook-length formulas prove $\mathcal{AL}$ and $\mathcal{BL}$. R. Proctor simultaneously established $\mathcal{BL}$ and $\mathcal{BJ}$ with a representation-theoretic proof of $\mathcal{BJ}$ [Pro83], while K. Purbhoo in unpublished work and M. Haiman in [Hai92] found beautiful *jeu-de-taquin* bijections for $\mathcal{AL}$ and $\mathcal{BL}$, respectively. I believe that the remaining equalities are new or trivial. (iii)

Given the appearance of *jeu-de-taquin*, it is perhaps not surprising that $\mathcal{BL}$, $\mathcal{HL}$, and $\mathcal{IL}$ can be refined to say that the linear extensions on either side of the equals sign have the same orbit structure under Pro. As for $\mathcal{AL}$, if we define $\mathcal{L}(\mathcal{P}, i) := \{\mathcal{L} \in \mathcal{L}(\mathcal{P}) : \mathrm{Pro}^i(\mathcal{L}) = \mathcal{L}\}$, then I showed in [W] that $\mathcal{L}(\Phi^+(A_n), \frac{n(n+1)}{d})$ is nonempty for $d$ odd with $d|n$ or $d|(n+1)$, and computations suggest that $|\mathcal{L}(\Phi^+(A_n), \frac{n(n+1)}{d})| = 2^{\lceil \frac{n(n-1)}{2d} \rceil} |\mathcal{L}(\mathcal{J}_n, \frac{n(n+1)}{2d})|$. An accompanying CSP is conjectured in [W].

By virtue of J. Stembridge's classification [Stem], there can be no analogue of Theorem 5.1 in other types. This offers at least a partial explanation for the disappointing failure of Edelman-Greene maps in general type, suggesting that the existence of an Edelman-Greene map is contingent on the existence of an underlying fully commutative poset. We also obtain a reason that there are no known enumerative formulas for general multi-triangulations as either subword complexes or as the order ideals $\mathcal{J}(\Phi^+(W) \times [k])$—the known formulas are really disguised formulas for the Gaussian posets on the right-hand sides of $A\mathcal{J}$, $B\mathcal{J}$, $H\mathcal{J}$, and $I\mathcal{J}$ [CLS]. These failures place Part 1 of Theorem 1.2 in good company with at least fifteen other phenomena that correlate with being of type $A_n$, $B_n$, $H_3$, and $I_2(m)$, the most elementary being that the degrees $d_1 \le d_2 \le \dots \le d_n$ of $W$ form an arithmetic sequence [Mil].

The generality of Part 2 of Theorem 1.2—especially in the face of the narrowness of Part 1—remains a mystery.

## Acknowledgements

This abstract is based on parts of my thesis, which was completed in September 2013 under Dennis Stanton at the University of Minnesota. I am grateful to my former advisor Dennis Stanton and to Vic Reiner for their guidance and support. I am indebted to Hugh Thomas for his insight and generosity. I thank Drew Armstrong, François Bergeron, Cesar Ceballos, Alejandro Morales, Brendon Rhoades, Jesica Striker, and Christian Stump for helpful conversations, and I thank Vincent Pilaud for suggesting that I compile this story here.

<footnote>(iii) A. Morales, G. Panova, and I have a simple representation-theoretic proof of $A\mathcal{J}$, but I don't know of any such proof for $H\mathcal{J}$. It would be nice to complete the picture with a *jeu-de-taquin* bijection for $HL$.</footnote>
References

[Arm] D. Armstrong. Generalized noncrossing partitions and combinatorics of Coxeter groups. Amer. Math. Soc., 2009.

[AST] D. Armstrong, C. Stump, and H. Thomas. A uniform bijection between nonnesting and noncrossing partitions. *Tran. Amer. Math. Soc.*, 365(8):4121–4151, 2013.

[BR] David Bessis and Victor Reiner. Cyclic sieving of noncrossing partitions for complex reflection groups. *Annals of Combinatorics*, pages 1–26, 2009.

[CF] P. Cameron and D. Fon-Der-Flaass. Orbits of antichains revisited. *Europ. J. Combin.*, 16(6):545–554, 1995. ISSN 0195-6698.

[CLS] C. Ceballos, J.-P. Labbé, and C. Stump. Subword complexes, cluster complexes, and generalized multi-associahedra. *J. Algebraic Combin.*, pages 1–35, 2011.

[CP] P. Cellini and P. Papi. Ad-nilpotent ideals of a Borel subalgebra II. *J. Algebra*, 258(1):112–121, 2002.

[EG] P. Edelman and C. Greene. Balanced tableaux. *Advances in Mathematics*, 63(1):42–99, 1987.

[Hai92] M. Haiman. Dual equivalence with applications, including a conjecture of Proctor. *Discrete Math.*, 99(1):79–113, 1992.

[Mil] A. Miller. Foulkes characters for complex reflection groups. Preprint, 2013.

[Pan] D. Panyushev. On orbits of antichains of positive roots. *Europ. J. Combin.*, 30(2):586–594, 2009.

[Pro83] R. Proctor. Shifted plane partitions of trapezoidal shape. *Proc. Amer. Math. Soc.*, 89(3):553–559, 1983.

[Pro84] R. Proctor. Bruhat lattices, plane partition generating functions, and minuscule representations. *European Journal of Combinatorics*, 5(4):331–350, 1984.

[Read] N. Reading. Cambrian lattices. *Advances in Mathematics*, 205(2):313–353, 2006.

[Rein] V. Reiner. Non-crossing partitions for classical reflection groups. *Discrete Mathematics*, 177(1):195–222, 1997.

[RS] D. Rush and X. Shi. On orbits of order ideals of minuscule posets. *J. of Algebraic Combin.*, pages 1–25, 2011.

[Shi] J.-Y. Shi. Sign types corresponding to an affine Weyl group. *J. London Math. Soc.*, 2(1):56–74, 1987.

[Stan84] R. P. Stanley. On the number of reduced decompositions of elements of Coxeter groups. *Europ. J. Combin.*, 5(4):359–372, 1984.

[Stan09] R. P. Stanley. Promotion and evacuation. *Electron. J. Combin.*, 16(2):R9, 2009.

[Stem] J. Stembridge. On the fully commutative elements of Coxeter groups. *J. Algebraic Combin.*, 5(4):353–385, 1996.

[SW] J. Striker and N. Williams. Promotion and rowmotion. *Europ. J. Combin.*, 33(8):1919–1942, 2012.

[W] N. Williams. Cataland. Ph.D. Thesis, 2013.