# Tamari Lattices for Parabolic Quotients of the Symmetric Group

Henri Mühle, Nathan Williams

► To cite this version:

Henri Mühle, Nathan Williams. Tamari Lattices for Parabolic Quotients of the Symmetric Group. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.973-984, 10.46298/dmtcs.2534 . hal-01337754

HAL Id: hal-01337754

https://hal.science/hal-01337754

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 Attribution 4.0 International License
# Tamari Lattices for Parabolic Quotients of the Symmetric Group

Henri Mühle† and Nathan Williams‡

LIAFA, CNRS et Université Paris Diderot, Case 7014, F-75205 Paris Cedex 13, France

LaCIM, Université du Québec à Montréal, C.P. 8888, Succ. Centre-Ville, Montréal, Québec, H3C 3P8, Canada

**Abstract.** We present a generalization of the Tamari lattice to parabolic quotients of the symmetric group. More precisely, we generalize the notions of 231-avoiding permutations, noncrossing set partitions, and nonnesting set partitions to parabolic quotients, and show bijectively that these sets are equinumerous. Furthermore, the restriction of weak order on the parabolic quotient to the parabolic 231-avoiding permutations is a lattice quotient. Lastly, we suggest how to extend these constructions to all Coxeter groups.

**Résumé.** Nous présentons une généralisation du treillis de Tamari aux quotients paraboliques du groupe symétrique. Plus précisément, nous généralisons les notions de permutations qui évitent le motif 231, les partitions non-croisées, et les partitions non-emboîtées aux quotients paraboliques, et nous montrons de façon bijective que ces ensembles sont équipotents. En restreignant l'ordre faible du quotient parabolique aux permutations paraboliques qui évitent le motif 231, on obtient un quotient de treillis d'ordre faible. Enfin, nous suggérons comment étendre ces constructions à tous les groupes de Coxeter.

**Keywords:** Symmetric group, Parabolic quotients, Tamari lattice, Noncrossing partitions, Nonnesting partitions, Aligned elements, 231-avoiding permutations

## 1 Introduction

The *Tamari lattice* $T_n$ was introduced by D. Tamari as a partial order on binary bracketings of a string of length $n+1$ [13]. The number of such bracketings is given by the $n$th *Catalan number* $\mathrm{Cat}(n) := \frac{1}{n+1} \binom{2n}{n}$. A. Björner and M. Wachs observed in [3, Section 9] that $T_n$ is the sublattice of the weak order on $S_n$ consisting of the subset $\mathfrak{S}_n(231)$ of permutations whose inversions sets satisfy a certain “compressed” condition (the notation reflects that these permutations are more commonly refered to as the 231-avoiding permutations). This observation was the precursor to N. Reading’s definition of the *Cambrian lattices*, which may be described as the restriction of the weak order of a finite Coxeter group to certain *aligned elements*, which are also characterized via their inversion sets [8]. The Cambrian lattices thus naturally generalize the Tamari lattice to any finite Coxeter group and any Coxeter element.

<footnote>†Email: henri.muehle@liafa.univ-paris-diderot.fr. H.M. is supported by a Public Grant overseen by the French National Research Agency (ANR) as part of the "Investissements d'Avenir" Program (Reference: ANR-10-LABX-0098).</footnote>

<footnote>‡Email: nathan.f.williams@gmail.com. N.W. is supported by a postdoctoral position at LaCIM.</footnote>
In this abstract, we propose a new generalization of the Tamari lattice to parabolic quotients $\mathfrak{S}_n^J$ of the symmetric group by introducing a distinguished subset of permutations, denoted by $\mathfrak{S}_n^J(231)$, that play the role of the 231-avoiding permutations for the parabolic quotient. We characterize these permutations both in terms of a generalized notion of pattern avoidance, and—in our opinion, more naturally—in terms of their inversion sets.

**Theorem 1** Let $S$ denote the set of simple transpositions of $\mathfrak{S}_n$ for $n > 0$. For $J \subseteq S$, the restriction of the weak order to $\mathfrak{S}_n^J(231)$ forms a lattice, which we call $\mathcal{T}_n^J$—the Tamari lattice for the parabolic quotient $\mathfrak{S}_n^J$. Furthermore, $\mathcal{T}_n^J$ is a lattice quotient of the weak order on $\mathfrak{S}_n^J$.

When $J = \emptyset$, we recover the Tamari lattice on 231-avoiding permutations. In the remainder of this article, we refer to $\mathcal{T}_n^J$ as the *parabolic Tamari lattice*.(i) We recall the necessary definitions for parabolic quotients of the symmetric group in Section 2 and prove Theorem 1 in Section 3.

N. Reading’s aligned elements of a Coxeter group $W$ have a markedly different description as the *sorted elements*, generalizing the result that 231-avoiding permutations are precisely those permutations that are stack-sortable [5, Exercise 2.2.1.4-5]. For any Coxeter element, these sorted elements provide a bridge between two famous families of Coxeter-Catalan objects, namely *W-noncrossing partitions* and *W-clusters* [9]. Remarkably, these objects are enumerated uniformly by a simple product formula depending on the degrees of $W$ [12, Remark 2]. Although we no longer have a product formula for $|\mathfrak{S}_n^J(231)|$, we are able to generalize certain other Catalan objects to the parabolic setting. In Sections 4 and 5 we generalize noncrossing and nonnesting partitions to parabolic quotients as the sets $NC_n^J$ and $NN_n^J$, and we prove bijectively that our three parabolic generalizations are equinumerous.

**Theorem 2** For $n > 0$ and $J \subseteq S$, we have

$$|\mathfrak{S}_n^J(231)| = |NC_n^J| = |NN_n^J|.$$

Finally, we propose a generalization of $\mathcal{T}_n^J$ to any element of any Coxeter group in Section 6.

# 2 The Symmetric Group

In this section, we recall the definitions of weak order, 231-avoiding permutations, and parabolic quotients.

## 2.1 Weak Order

The *symmetric group* $\mathfrak{S}_n$ is the group of permutations of $[n] := \{1, 2, \dots, n\}$. Let $S := \{s_1, s_2, \dots, s_{n-1}\}$ denote the set of *simple transpositions* of $\mathfrak{S}_n$, i.e. $s_i := (i i+1)$ for $i \in [n-1]$. It is well known that $\mathfrak{S}_n$ is isomorphic to the Coxeter group $A_{n-1}$, and so admits a presentation of the form

$$\mathfrak{S}_n = \langle S \mid s_i^2 = (s_i s_j)^2 = (s_i s_{i+1})^3 = 1, \text{ for } 1 \le i < j \le n-1, |i-j| > 1 \rangle.$$

Although this abstract focuses on constructions for $\mathfrak{S}_n$, many of the definitions may be generalized to Coxeter groups (see the discussion in Section 6).

We may specify permutations using their one-line notation: $w = w_1 w_2 \cdots w_n$, where $w_i = w(i)$ for $i \in [n]$. The *inversion set* of $w \in \mathfrak{S}_n$ is defined by $\text{inv}(w) = \{(i, j) \mid 1 \le i < j \le n \text{ and } w_i > w_j\}$.

<footnote>(i) This nomenclature is slightly ambiguous, since it could refer to either parabolic quotients or parabolic subgroups—but the Tamari lattice of a parabolic subgroup is a direct product of Tamari lattices, and so deserves no special name.</footnote>
The weak order Weak($\mathfrak{S}_n$) is the partial order defined by $u \le_S v$ if and only if $\mathrm{inv}(u) \subseteq \mathrm{inv}(v)$. We refer the reader to [2, Section 3] for more background on the weak order, in particular in the broader context of Coxeter groups. A remarkable property of Weak($\mathfrak{S}_n$) is that it is a lattice [2, Theorem 3.2.1]. Recall further that there is a unique maximal element $w_0$ in Weak($\mathfrak{S}_n$) whose one-line notation is $w_0 = n(n-1)\cdots 1$. We denote the identity permutation by $e$.

A permutation $w \in \mathfrak{S}_n$ is called 231-avoiding if there exists no triple $i < j < k$ such that $w_k < w_i < w_j$. Let $\mathfrak{S}_n(231)$ denote the set of 231-avoiding permutations of $\mathfrak{S}_n$. These elements may also be specified by a “compressed” condition on their inversion sets—an inversion set $\mathrm{inv}(w)$ is compressed if $i < j < k$ and $(i, k) \in \mathrm{inv}(w)$ implies that $(i, j) \in \mathrm{inv}(w)$. Then $w \in \mathfrak{S}_n(231)$ if and only if $\mathrm{inv}(w)$ is compressed [3, Section 9]. We recall the following result due to A. Björner and M. Wachs, which will serve as a definition of the Tamari lattice $\mathcal{T}_n$ for our purposes.

**Theorem 3** ([3, Theorem 9.6(ii)]). The poset $(\mathfrak{S}_n(231), \le_S)$ is isomorphic to the Tamari lattice $\mathcal{T}_n$.

## 2.2 Parabolic Quotients

Recall that any subset $J \subseteq S$ generates a subgroup of $\mathfrak{S}_n$ isomorphic to a direct product of symmetric groups of smaller rank. We call such a subgroup *parabolic*, and we denote it by $(\mathfrak{S}_n)_J$. Moreover, we define the *parabolic quotient* of $\mathfrak{S}_n$ with respect to $J$ by

$$ \mathfrak{S}_n^J = \{w \in \mathfrak{S}_n \mid w <_S ws \text{ for all } s \in J\}. $$

The set $\mathfrak{S}_n^J$ thus consists of the minimal length representatives of the right cosets of the corresponding parabolic subgroup. By [2, Proposition 2.4.4], any permutation $w \in \mathfrak{S}_n$ can be uniquely written as $w = w^J \cdot w_J$, for $w^J \in \mathfrak{S}_n^J$ and $w_J \in (\mathfrak{S}_n)_J$.

We further define the *parabolic weak order* Weak($\mathfrak{S}_n^J$) by the cover relations $ws \le_S^J w$ if and only if $ws \in \mathfrak{S}_n^J$ for some $s \in S$. Weak($\mathfrak{S}_n^J$) has a longest element $w_0$, is isomorphic to the weak order interval $[e, w_0^J]$, and is therefore a lattice. In particular this allows us to use $\le_S$ instead of $\le_S^J$.

# 3 Tamari Lattices for Parabolic Quotients of $\mathfrak{S}_n$

In this section, we define $\mathfrak{S}_n^J(231)$—a generalization of the set of 231-avoiding permutations to parabolic quotients of the symmetric group. We characterize the inversion sets of the permutations in $\mathfrak{S}_n^J(231)$ and prove that $(\mathfrak{S}_n^J(231), \le_S)$ is a lattice.

## 3.1 *Aligned Elements for Parabolic Quotients of $\mathfrak{S}_n$*

Let $J := S \setminus \{s_{j_1}, s_{j_2}, \dots, s_{j_r}\}$, and let $\mathrm{B}(J)$ be the set partition of $[n]$ given by the parts

$$ \{\{1, \dots, j_1\}, \{j_1 + 1, \dots, j_2\}, \dots, \{j_{r-1} + 1, \dots, j_r\}, \{j_r + 1, \dots, n\}\}. $$

We call the parts of $\mathrm{B}(J)$ the *J-regions*. We indicate the parts of $\mathrm{B}(J)$ in the one-line notation of a permutation $w \in \mathfrak{S}_n^J$ by vertical bars.

**Lemma 4** If $w \in \mathfrak{S}_n^J$, then the one-line notation of $w$ has the form

$$ w = w_1 < \cdots < w_{j_1} | w_{j_1+1} < \cdots < w_{j_2} | \cdots | w_{j_r} < \cdots < w_n. $$
**Definition 5** A permutation $w \in \mathfrak{S}_n^J$ is *J-231-avoiding* if there exist no three indices $i < j < k$, all of which lie in different *J*-regions, such that $w_k < w_i < w_j$ and $w_i = w_k + 1$. Let $\mathfrak{S}_n^J(231)$ denote the set of *J*-231-avoiding permutations of $\mathfrak{S}_n^J$.

**Example 6** The left image in Figure 1 shows $\text{Weak}(\mathfrak{S}_4^{\{s_2\}})$, where the gray permutations are precisely the $\{s_2\}$-231-avoiding permutations. Notice that the longest permutation $4|23|1$ is not 231-avoiding, since it contains the subsequence 231. However, since the 2 and the 3 lie in the same $\{s_2\}$-region this sequence does not form a $\{s_2\}$-231-pattern.

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** The parabolic Tamari lattice $T_4^{\{s_2\}}$. The poset on the left has every permutation of the parabolic quotient $\mathfrak{S}_4^{\{s_2\}}$ with the $\{s_2\}$-231-sortable elements marked in gray; the poset in the middle is labeled by the $\{s_2\}$-noncrossing partitions on [4], as in Definition 20; the poset on the right is labeled by the $\{s_2\}$-nonnesting partitions on [4].</figcaption></figure>

In the case $J = \emptyset$, the set of J-231-avoiding permutations is equal to the set of 231-avoiding permutations.

**Proposition 7** If $w \in \mathfrak{S}_n$ has a 231-pattern, then there exist indices $i < j < k$ such that $w_k < w_i < w_j$ and $w_i = w_k + 1$. Consequently, $\mathfrak{S}_n^\emptyset(231) = \mathfrak{S}_n(231)$

We now generalize A. Björner and M. Wachs’ definition of compressed inversion sets to parabolic quotients. We remark that the compressed inversion sets are a special case of N. Reading’s aligned condition, which generalizes the notion to any finite Coxeter group and any Coxeter element.

**Definition 8** An inversion set $\text{inv}(w)$ for a permutation $w \in \mathfrak{S}_n^J$ is *J-compressed* if for any three indices $i < j < k$ such that $w_i = w_k + 1$ with $i, j,$ and $k$ each in different *J*-regions, it follows that $(i, j) \in \text{inv}(w)$.

**Lemma 9** A permutation $w \in \mathfrak{S}_n^J$ is J-231-avoiding if and only if $\text{inv}(w)$ is J-compressed.

## 3.2 Tamari Lattices for Parabolic Quotients of $\mathfrak{S}_n^J$

Now we prove the first part of Theorem 1, namely that $(\mathfrak{S}_n^J(231), \leq_S)$ is a lattice. The proof follows from the next lemma, which is modeled after [8, Lemma 5.6], a result that covers the case $J = \emptyset$.
**Lemma 10** For every $w \in \mathfrak{S}_n^J$, there exists some $w' \in \mathfrak{S}_n^J$ such that $\mathrm{inv}(w')$ is the unique maximal set under containment among all $J$-compressed inversion sets $\mathrm{inv}(u) \subseteq \mathrm{inv}(w)$. In other words, for every $w \in \mathfrak{S}_n^J$, there exists a unique maximal $J$-231-avoiding permutation $w'$ with $w' \le_S w$.

**Proof:** We pick $w \in \mathfrak{S}_n^J$, and proceed by induction on the cardinality of $\mathrm{inv}(w)$. If $\mathrm{inv}(w) = \emptyset$, then $\mathrm{inv}(w)$ is $J$-compressed and the claim holds trivially. Suppose that $|\mathrm{inv}(w)| = r$, and that the claim is true for all $x \in \mathfrak{S}_n^J$ with $|\mathrm{inv}(x)| < r$.

If $\mathrm{inv}(w)$ is already $J$-compressed, then we set $w' = w$ and we are done. Otherwise, Lemma 9 implies that $w$ contains an instance of a $J$-231-pattern, which means that there are indices $i < j < k$ that all lie in different $J$-regions such that $w_k < w_i < w_j$ and $w_i = w_k + 1$. Consider the lower cover $u$ of $w$ that has $w_i$ and $w_k$ exchanged, i.e. $u = s_{w_k}w$. In particular, we have $\mathrm{inv}(w) = \mathrm{inv}(u) \cup \{(i, k)\}$. By induction hypothesis, there exists some $u' \in \mathfrak{S}_n^J$ such that $\mathrm{inv}(u')$ is the unique maximal $J$-compressed inversion set that is contained in $\mathrm{inv}(u)$. We claim that $w' = u'$.

In order to prove this claim, we pick some element $v \in \mathfrak{S}_n^J$ such that $\mathrm{inv}(v)$ is $J$-compressed and $\mathrm{inv}(v) \subseteq \mathrm{inv}(w)$. By construction, we have $(i, j) \notin \mathrm{inv}(w)$, and hence $(i, j) \notin \mathrm{inv}(v)$. Since $\mathrm{inv}(v)$ is $J$-compressed it follows by definition that $v_i \neq v_k + 1$. We want to show that $\mathrm{inv}(v) \subseteq \mathrm{inv}(u)$, which amounts to showing that $(i, k) \notin \mathrm{inv}(v)$ because $\mathrm{inv}(w) \setminus \mathrm{inv}(u) = \{(i, k)\}$.

We assume the opposite, and in view of the previous reasoning it follows that $v_i > v_k + 1$. Let $d$ be the index such that $v_d = v_k + 1$, and let $e$ be the index such that $v_i = v_e + 1$. Since $w_i = w_k + 1$, we observe:

$$ \text{either } w_d < w_k \text{ or } w_d > w_i, \text{ and} \quad (D) $$

$$ \text{either } w_e < w_k \text{ or } w_e > w_i. \quad (E) $$

We have the following relations: $v_j > v_i > v_e \ge v_d > v_k$. (If $v_j < v_i$, then $(i, j) \in \mathrm{inv}(v) \subseteq \mathrm{inv}(w)$, which is a contradiction.) We now distinguish five cases:

(i) Assume $d < i < k$. Hence $(d, k), (i, k) \in \mathrm{inv}(v) \subseteq \mathrm{inv}(w)$. It follows that $w_d > w_k$, and (D) implies $w_d > w_i$. Lemma 4 implies that $d$ and $i$ lie in different $J$-regions. Since $\mathrm{inv}(v)$ is $J$-compressed, we conclude that $(d, i) \in \mathrm{inv}(v)$. Hence $v_i < v_d = v_k + 1 < v_i$, which is a contradiction.

(ii) Assume $i < d < k$. Hence $(i, d), (d, k), (i, k) \in \mathrm{inv}(v) \subseteq \mathrm{inv}(w)$. It follows that $w_i > w_d$ and $w_d > w_k$, which contradicts (D).

(iii) Assume $i < e < k$. Hence $(i, e), (e, k), (i, k) \in \mathrm{inv}(v) \subseteq \mathrm{inv}(w)$. It follows that $w_i > w_e$ and $w_e > w_k$, which contradicts (E).

(iv) Assume $i < k < e$. Hence $(i, k), (i, e) \in \mathrm{inv}(v) \subseteq \mathrm{inv}(w)$. It follows that $w_i > w_e$, and (E) implies $w_e < w_k$. Lemma 4 implies that $k$ and $e$ lie in different $J$-regions. Since $\mathrm{inv}(v)$ is $J$-compressed, we conclude that $(k, e) \in \mathrm{inv}(v)$. Hence $v_i = v_e + 1 < v_k + 1 < v_i$, which is a contradiction.

(v) Assume $e < i < k < d$, which in particular implies that $v_e > v_d$. Hence $(e, d), (e, k), (i, d), (i, k) \in \mathrm{inv}(v) \subseteq \mathrm{inv}(w)$. It follows that $w_i > w_d$ as well as $w_e > w_k$. Now (D) and (E) imply $w_d < w_k$ and $w_e > w_i$, respectively. Lemma 4 implies that $e, i, k$ and $d$ all lie in different $J$-regions.

Let $e'$ be the smallest element in the $J$-region of $e$ such that $v_{e'} > v_d$, and let $d'$ be the largest element in the $J$-region of $d$ such that $v_{d'} < v_{e'}$. We record that $e' \le e < i < j < k < d \le d'$, and we proceed by induction on $v_{e'} - v_{d'}$. If $v_{e'} = v_{d'} + 1$, then $(e', i) \in \mathrm{inv}(v)$, since $\mathrm{inv}(v)$ is $J$-compressed. Lemma 4 implies that $v_e > v_{e'} > v_i = v_e + 1$, which is a contradiction. If $v_{e'} > v_{d'} + 1$, then there must be some index $f$ with $v_{e'} > v_f > v_{d'} + 1$. If $f < i$ and they do not lie in the same $J$-region, then we can consider the triple $(f, i, d')$, and we obtain a contradiction by induction, since $v_f - v_{d'} < v_{e'} - v_{d'}$. If
$f > i$ and they do not lie in the same $J$-region, then we can consider the triple $(e', i, f)$, and we obtain a contradiction by induction, since $v_{e'} - v_f < v_{e'} - v_{d'}$. If $f$ and $i$ lie in the same $J$-region, then we can consider the triple $(f, j, d')$, and we obtain a contradiction by induction, since $v_f - v_{d'} < v_{e'} - v_{d'}$. (Note that we can prove the induction base verbatim using $v_j$ instead of $v_i$.)

We have thus shown that $(i, k) \notin \text{inv}(v)$, which implies $\text{inv}(v) \subseteq \text{inv}(u)$. By induction assumption it follows that $\text{inv}(v) \subseteq \text{inv}(u')$, which proves $w' = u'$. The reformulation of this statement follows from Lemma 9. $\square$

**Proposition 11** The poset $(\mathfrak{S}_n^J(231), \le_S)$ is a lattice.

**Proof:** Let $w_1, w_2 \in \mathfrak{S}_n^J(231)$, and let $u = w_1 \wedge w_2$ denote their meet in weak order. Lemma 10 implies that there exists a unique maximal element $u' \in \mathfrak{S}_n^J(231)$ with $u' \le_S w_1, w_2$, which then necessarily must be the meet of $w_1$ and $w_2$ in $(\mathfrak{S}_n^J(231), \le_S)$. Since $(\mathfrak{S}_n^J(231), \le_S)$ is a finite meet-semilattice with a greatest element ($w_0^J$ is trivially $J$-231-avoiding), it is a classical lattice-theoretic result that it must be a lattice. $\square$

Lemma 7 implies that the set $\mathfrak{S}_n^\emptyset(231)$ coincides with the set of all classical 231-avoiding permutations of $\mathfrak{S}_n$, and Theorem 3 states that $(\mathfrak{S}_n^\emptyset(231), \le_S)$ is isomorphic to the Tamari lattice $\mathcal{T}_n$. In view of Proposition 11, we feel it is justified to denote the poset $(\mathfrak{S}_n^J(231), \le_S)$ by $\mathcal{T}_n^J$, and call it the *parabolic Tamari lattice*.

**Remark 12** Consider the parabolic subgroup $(\mathfrak{S}_n)_J$, and let $(w_0)_J$ denote the longest permutation in this subgroup. It is straightforward to show that the poset of all 231-avoiding permutations in the interval $[e, (w_0)_J]$ is an interval of the Tamari lattice $\mathcal{T}_n$.

If we consider instead parabolic *quotients*, then even though the elements in $\mathfrak{S}_n^J$ form the interval $[e, w_0^J]$, the lattice $\mathcal{T}_n^J$ is not an interval in $\mathcal{T}_n$. For example, $\mathcal{T}_4^{\{s_2\}}$ is depicted in Figure 1. Observe that $w_0^{\{s_2\}} = 4|23|1$ is not 231-avoiding, and hence is not an element of $\mathcal{T}_4$. However, recent work by L.-F. Préville-Ratelle and X. Viennot suggests that $\mathcal{T}_n^J$ is an interval in $\mathcal{T}_{2n+2}[7]$.

**Remark 13** We remark that the lattice $\mathcal{T}_n^J$ is not in general a sublattice of $[e, w_0^J]$. Consider again the case when $n=4$ and $J = \{s_2\}$. Then the meet of $w_1 = 4|13|2$ and $w_2 = 3|24|1$ in weak order is $3|14|2$, while their meet in $\mathcal{T}_4^{\{s_2\}}$ is $2|14|3$.

In certain special cases, for example when $J = \emptyset$ or when $J = S \setminus \{s\}$, we do obtain sublattices.

### 3.3 Parabolic Tamari Lattices are Lattice Quotients

In this section, we prove that $\mathcal{T}_n^J$ is a lattice quotient of the weak order interval $[e, w_0^J]$, completing the proof of Theorem 1. Recall from [8, Section 3] that an equivalence relation $\Theta$ on a lattice $(L, \le)$ is a lattice congruence if and only if all equivalence classes $[x]_\Theta$ are intervals, and the projections that map $x$ to the least or greatest element in $[x]_\Theta$, respectively, are both order-preserving.

By Lemma 10, we obtain a projection $\Pi_\downarrow^J : \mathfrak{S}_n^J \to \mathfrak{S}_n^J(231)$ by $\Pi_\downarrow^J(w) = w'$, where $w'$ is the unique maximal $J$-231-avoiding permutation below $w$.

**Lemma 14** The fibers of $\Pi_\downarrow^J$ are order-convex, i.e. if $u <_S x <_S v$ and $\Pi_\downarrow^J(u) = \Pi_\downarrow^J(v)$, then $\Pi_\downarrow^J(u) = \Pi_\downarrow^J(x)$.
We now define a set of permutations “dual” to the J-231-avoiding permutations$^{(ii)}$. We say a permutation $w \in \mathfrak{S}_n^J$ is J-132-avoiding if there are no three indices $i < j < k$, all of which lie in different J-regions, such that $w_i < w_k < w_j$ and $w_k = w_i + 1$. We can prove the following result analogously to Lemma 10.

**Lemma 15** For any $w \in \mathfrak{S}_n^J$, there is a unique minimal J-132-avoiding permutation $w'$ with $w \le_S w'$.

Hence we obtain a map $\Pi_{\downarrow}^J : \mathfrak{S}_n \to \mathfrak{S}_n^J(132)$ that maps $w$ to the unique minimal J-132-avoiding permutation $w'$ above $w$.

**Lemma 16** The maps $\Pi_{\downarrow}^J$ and $\Pi_{\uparrow}^J$ are order-preserving.

**Lemma 17** Let $u, v \in \mathfrak{S}_n^J$ with $u \le_S v$. The following are equivalent:

(i) $\Pi_{\downarrow}^J(u) = \Pi_{\downarrow}^J(v)$.

(ii) $u$ is obtained from $v$ by a J-231 $\to$ J-132-move, i.e. there are indices $i < j < k$ in different J-regions with $v_k < v_i < v_j$ and $v_i = v_k + 1$ such that $\mathrm{inv}(v) \setminus \mathrm{inv}(u) = \{(i, k)\}$.

**Lemma 18** For any $u, v \in \mathfrak{S}_n^J$ with $\Pi_{\downarrow}^J(u) = \Pi_{\downarrow}^J(v)$ we have $\Pi_{\uparrow}^J(u) = \Pi_{\uparrow}^J(v)$

**Proof:** Let us first assume that $u \le_S v$. If $u \le_S v$, then—since $\Pi_{\downarrow}^J(u) = \Pi_{\downarrow}^J(v)$—Lemma 17 implies that there must be a J-231 pattern in $v$ that is not present in $u$. In other words there are indices $i < j < k$, all of which lie in different J-regions with $v_k < v_i < v_j$ and $v_i = v_k + 1$, and $u$ is obtained from $v$ by removing the inversion $(i, k)$. Hence we have $u_i < u_k < u_j$ and $u_k = u_i + 1$, which forms a J-132-pattern in $u$. We have $u \le_S v \le_S \Pi_{\downarrow}^J(u) \le_S \Pi_{\uparrow}^J(v)$, and since $\Pi_{\downarrow}^J(v)$ is minimal among all J-132-avoiding permutations above $v$, we obtain the desired equality. If $u \le_S v$ do not form a cover relation, we find the desired equality by repeated application of the previous reasoning.

Finally, suppose that $u$ and $v$ are incomparable. We conclude that $\Pi_{\downarrow}^J(u \wedge v) = \Pi_{\downarrow}^J(u)$, since $\Pi_{\downarrow}^J(u)$ is the unique maximal J-231-avoiding permutation below both $u$ and $v$. In view of the reasoning in the first paragraph, we find $\Pi_{\uparrow}^J(u) = \Pi_{\uparrow}^J(u \wedge v) = \Pi_{\uparrow}^J(v)$, as desired. $\square$

**Proposition 19** The fibers of $\Pi_{\downarrow}^J$ induce a lattice congruence on $[e, w_o^J]$, and the corresponding quotient lattice is $T_n^J$.

**Proof:** The fibers of $\Pi_{\downarrow}^J$ induce an equivalence relation on $\mathfrak{S}_n^J$ by setting $u \sim v$ if and only if $\Pi_{\downarrow}^J(u) = \Pi_{\downarrow}^J(v)$. Lemma 10 implies that the equivalence classes have a least element. Lemma 18 implies together with Lemma 15 that equivalence classes have a greatest element, and Lemma 14 implies that the equivalence class $[w] \sim$ is in fact equal to the interval $[\Pi_{\downarrow}^J(w), \Pi_{\uparrow}^J(w)]$. Lemma 16 now completes the proof. $\square$

**Proof of Theorem 1:** This follows from Propositions 11 and 19. $\square$

<footnote>(ii) The notion of the “dual” of J-231-avoiding permutations follows from the well-known antiautomorphism of $\mathfrak{S}_n^J$, given by $x \mapsto w_o x(w_o)_J$ [2, Proposition 2.5.4].</footnote>
# 4 Parabolic Noncrossing Partitions

In this section, we define noncrossing partitions for parabolic quotients $NC_n^J$ and we give a bijection between $NC_n^J$ and $\mathfrak{S}_n^J(231)$.

A set partition of $[n]$ is a collection $\mathbf{P} = \{P_1, P_2, \dots, P_s\}$ of subsets of $[n]$ with the property that $P_i \cap P_j = \emptyset$ for $1 \le i < j \le s$, and $\cup_{i=1}^s P_i = \{1, 2, \dots, n\}$. The elements $P_i$ of $\mathbf{P}$ are called the *parts* of $\mathbf{P}$. A pair $(a, b)$ is a *bump* of $\mathbf{P}$ if $a, b \in P_i$ for some $i \in \{1, 2, \dots, s\}$ and there is no $c \in P_i$ with $a < c < b$.

**Definition 20** A partition $\mathbf{P}$ of $[n]$ is *J-noncrossing* if it satisfies the following three conditions:

(NC1) If $i$ and $j$ lie in the same $J$-region, then they are not contained in the same part of $\mathbf{P}$.

(NC2) If two distinct bumps $(i_1, i_2)$ and $(j_1, j_2)$ of $\mathbf{P}$ satisfy $i_1 < j_1 < i_2 < j_2$, then either $i_1$ and $j_1$ lie in the same $J$-region or $i_2$ and $j_1$ lie in the same $J$-region.

(NC3) If two distinct bumps $(i_1, i_2)$ and $(j_1, j_2)$ of $\mathbf{P}$ satisfy $i_1 < j_1 < j_2 < i_2$, then $i_1$ and $j_1$ lie in different $J$-regions.

We denote the set of all $J$-noncrossing set partitions of $[n]$ by $NC_n^J$.

If $J = \emptyset$, then we recover the classical noncrossing set partitions. We now introduce a combinatorial model for the $J$-noncrossing partitions. We draw $n$ dots, labeled by the numbers $1, 2, \dots, n$, on a straight line, and highlight the $J$-regions by grouping the corresponding dots together. For any bump $(i, j)$ in $\mathbf{P} \in NC_n^J$, we draw an arc connecting the dots corresponding to $i$ and $j$, respectively, that passes below all dots corresponding to indices $k > i$ that lie in the same $J$-region as $i$, and above all other dots between $i$ and $j$. See the bottom left of Figure 2 for an illustration.

Using this combinatorial model for $NC_n^J$, we now prove the following theorem.

**Theorem 21** For $n > 0$ and $J \subseteq S$, we have $|\mathfrak{S}_n^J(231)| = |NC_n^J|$.

**Proof:** Let $w \in \mathfrak{S}_n^J$. We construct a set partition $\mathbf{P}$ of $\{1, 2, \dots, n\}$ by associating a bump $(i, j)$ with any inversion $(i, j) \in \text{inv}(w)$ satisfying $w_i = w_j + 1$. If $(i, j)$ is a bump of $\mathbf{P}$, then it follows from Lemma 4 that $i$ and $j$ lie in different $J$-regions, and therefore condition (NC1) is satisfied. Suppose $(i_1, i_2)$ and $(j_1, j_2)$ are two different bumps of $\mathbf{P}$ with $i_1 < j_1 < i_2 < j_2$, but neither $i_1, j_1$ nor $i_2, j_2$ are in the same block. If $w_{i_1} < w_{j_1}$, then $(i_1, j_1, i_2)$ induces a $J$-231-pattern in $w$, which is a contradiction. If $w_{i_1} > w_{j_1}$, it follows that $w_{j_1} < w_{i_2}$, and then $(j_1, i_2, j_2)$ induces a $J$-231-pattern in $w$, which is a contradiction. Hence (NC2) is satisfied. Finally, suppose that $(i_1, i_2)$ and $(j_1, j_2)$ are two different bumps of $\mathbf{P}$ with $i_1 < j_1 < j_2 < i_2$ such that $i_1$ and $j_1$ are in the same $J$-region. Lemma 4 implies $w_{i_1} < w_{j_1}$. It follows that $(i_1, j_1, i_2)$ induces a $J$-231-pattern in $w$, which is a contradiction. Hence (NC3) is satisfied, and so $\mathbf{P} \in NC_n^J$.

Conversely, let $\mathbf{P} \in NC_n^J$. We construct a permutation $w \in \mathfrak{S}_n^J(231)$ where every bump $(i, j)$ of $\mathbf{P}$ corresponds to an inversion $(i, j) \in \text{inv}(w)$ with $w_i = w_j + 1$. We proceed by induction on $n$. The case $n = 1$ is trivial. Suppose that for any $n' < n$ we can construct a $J'$-231-avoiding permutation of $\mathfrak{S}_{n'}^{J'}$ from a given $J'$-noncrossing set partition of $[n']$, where $J'$ is the restriction of $J$ to $[n']$. That is, two entries $i, j \in [n']$ lie in the same $J'$-region if and only if they lie in the same $J$-region.
We denote the set of all $J$-nonnesting partitions of $[n]$ by $NN_n^J$. If $J = \emptyset$, then we recover the classical nonnesting set partitions.

Recall that the *root poset* of $\mathfrak{S}_n$ is the poset $\Phi_+ = (T, \leq)$, where $T$ is the set of all transpositions of $\mathfrak{S}_n$, and we have $(i_1 i_2) \leq (j_1 j_2)$ if and only if $i_1 \geq j_1$ and $i_2 \leq j_2$. The *parabolic root poset* of $\mathfrak{S}_n$, denoted by $\Phi_+^J$, is the order filter of $\Phi_+$ generated by the adjacent transpositions not in $J$. The $J$-nonnesting partitions of $[n]$ are then in bijection with the order ideals in this parabolic root poset. See the top-left part of Figure 2 for an example. We now prove the following theorem bijectively.

**Theorem 24** For $n > 0$ and $J \subseteq S$, we have $|NN_n^J| = |NC_n^J|$.

**Proof:** We begin with the construction of a bijection from $NN_n^J$ to $NC_n^J$ for the case of maximal parabolic quotients, i.e. where $J = S \setminus \{s_k\}$ for $k \in [n]$. We label the transposition $(i \ j)$ in $\Phi_+^J$ by the arc $(k+1-i, n+1-j+k)$, which yields the following labeling of $\Phi_+^J$ (under a suitable rotation):

$$ \begin{array}{ccccccc} (k, (k+1)) & \cdots & (k, (n-1)) & (k, n) & & & \\ \vdots & & \vdots & & \vdots & & \\ (2, (k+1)) & \cdots & (2, (n-1)) & (2, n) & & & \\ (1, (k+1)) & \cdots & (1, (n-1)) & (1, n) & & & \end{array} $$

The $J$-nonnesting set partition corresponding to an order ideal in $\Phi_+^J$ is the one whose bumps are the labels of the minimal elements not in the order ideal. Since $B(J) = \{\{1, 2, \dots, k\}, \{k+1, k+2, \dots, n\}\}$, condition (NC3) ensures that every $J$-noncrossing partition is also $J$-nonnesting and vice versa.

Now suppose that $J = S \setminus \{s_{k_1}, s_{k_2}, \dots, s_{k_r}\}$, and let $I$ be an order ideal of $\Phi_+^J$. We construct a noncrossing partition $P \in NC_n^J$ inductively starting from the partition with no parts. First, we split $I$ in two parts, a part $A$ containing all the transpositions in $I$ that lie above $s_{k_1}$ in $\Phi_+^J$, and a part $B$ containing all the other transpositions in $I$. We think of $B$ as an order ideal in $\Phi_+^{J \setminus \{s_{k_1}\}}$, and can thus construct a $(J \setminus \{s_{k_1}\})$-noncrossing set partition of $\{k_1+1, k_1+2, \dots, n\}$ by induction. Now we choose all those columns in part $A$ that either lie outside the order filter generated by $s_{k_2}, \dots, s_{k_r}$ or that have an element of $I$ in part $B$ directly below them. (We thus pick the columns of $A$ that are “supported” by $B$.) Let $l_1, l_2, \dots, l_r$ denote the column labels from the inductive step of the part of $B$ that supports $A$. Any bump starting in $\{1, 2, \dots, k_1\}$ can end either in $\{k_1+1, k_1+2, \dots, k_2\}$ or in $\{l_1, l_2, \dots, l_r\}$ in order not to cross any existing bumps. We label the transpositions in the chosen part of $A$ as follows:

$$ \begin{array}{ccccccc} (k_1, (k_1+1)) & \cdots & (k_1, k_2) & (k, l_1) & (k, l_2) & \cdots & (k, l_r) \\ \vdots & & \vdots & & \vdots & & \vdots \\ (2, (k_1+1)) & \cdots & (2, k_2) & (2, l_1) & (2, l_2) & \cdots & (2, l_r) \\ (1, (k_1+1)) & \cdots & (1, k_2) & (1, l_1) & (1, l_2) & \cdots & (1, l_r) \end{array} $$

The labels corresponding to the minimal transpositions that are not in $I$ within these chosen columns then yield the remaining bumps. By construction, the resulting partition is $J$-noncrossing.

The reverse map follows from temporarily forgetting about the bumps from the first $J$-region, and using the smaller $J$-noncrossing partition to construct part $B$ of the order ideal inductively. From there, we can again identify the “supported” columns in part $A$, and the bumps starting in the first $J$-region then give the remaining elements of the order ideal. $\square$
**Example 25** Consider the *J*-nonnesting set partition of [10] shown at the top left of Figure 2 indicated by the dark gray region. The construction of the smaller parabolic noncrossing partitions is shown in the middle and right part of that figure, and the resulting *J*-noncrossing partition is shown at the bottom left.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Figure illustrating how to combine parts A and B.</figcaption></figure>

**Proof of Theorem 2:** This follows from Theorems 21 and 24. □

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

# 6 Generalizations

Let $W$ be a Coxeter group with geometric realization in $V$ so that the elements of $W$ correspond to the regions of $V-\mathcal{R}$, where $\mathcal{R}$ is the set of hyperplanes corresponding to the reflections of $W$. N. Reading has defined a method for slicing hyperplanes into pieces, which he calls *shards* [10]—these pieces correspond naturally to join-irreducible elements, and so all that follows can be rephrased using join-irreducibles and canonical join representations, or inversion sets and covered reflections.

We can geometrically rephrase the construction of the *J*-231-sortable elements in an attractive way using N. Reading's shards. Fix $c = s_1s_2\cdots s_n$ in type $A_n$, let $\mathbf{w}_c^J(c)$ be the *c*-sorting word for $w_c^J$, and let $\mathcal{R}_{\mathbf{w}_c^J(c)}$ be the set of shards crossed by the gallery corresponding to $\mathbf{w}_c^J(c)$ (in other words, for each hyperplane in the inversion set of $w_c^J$, $\mathbf{w}_c^J(c)$ selects a connected piece of that hyperplane). Then the *J*-231-sortable elements are exactly those elements which are minimal in the regions $V - \mathcal{R}_{\mathbf{w}_c^J(c)}$.

This suggests the following definition for *any* Coxeter group $W$, *any* element $w \in W$, and *any* reduced word $\mathbf{w}$ for $w$.

**Definition 26** Fix a Coxeter group $W$, an element $w \in W$, and a reduced word $\mathbf{w}$ for $w$. Let $\mathcal{R}_w$ be the set of shards crossed by the gallery corresponding to $\mathbf{w}$. An element $u \in [e, w]$ is called *w-sortable* if and only if every lower facet of $u$ lies on a shard in $\mathcal{R}_w$.

Although it is tempting to conjecture that the poset defined as the restriction of weak order on $[e, w]$ to the $w$-sortable elements is always a lattice, this statement turns out to be false. For example, take
$w = s_2s_1s_2s_3s_4s_2s_3s_1s_2s_1$ in $A_4$ (we do not know of any counterexamples in rank less than 4). We have been unable to determine necessary and sufficient conditions on $W$ and $w$ for the resulting poset to be a lattice, although taking $w$ to be a $c$-sorting word seems like a reasonable condition to consider further.

Restricting Definition 26 to $c$-sorting reduced words for longest elements of parabolic quotients $w_◦^J(c)$ generalizes the construction of this abstract to any finite Coxeter group and any Coxeter element. We do not know if the resulting posets are in general lattices, but many features do generalize, including the definitions of noncrossing and nonnesting partitions (although they are not always equinumerous) [14]. For example, we have the following analogue to the cluster complex using work of C. Ceballos, J.-P. Labbé, and C. Stump [4] and V. Pilaud and C. Stump [6].

**Definition 27** Fix a finite Coxeter group $W$, a Coxeter element $c$ and a parabolic quotient $J$. Define the (non-reduced) word in simple generators $Q = cw_◦(c)$ and consider the set $S_c(W^J)$ of subwords of $Q$ whose complements contain a reduced word for $w_◦^J$.

When $J = \emptyset$, the subword complex $S_c(W^J)$ is isomorphic to the $c$-cluster complex, and it is known that the flip graph of $S_c(W^J)$ is isomorphic to the restriction of weak order to the $c$-KH elements [4]. We conjecture that the flip graph $S_c(W^J)$ is isomorphic to the restriction of $[e, w_◦^J]$ to the $w_◦^J(c)$-elements [14], and we are interested in the extent to which Definitions 26 and 27 are linked.

## Acknowledgements

The second author would like to thank D. Stanton, V. Reiner, and H. Thomas for their support and guidance, and N. Reading and C. Ceballos for helpful conversations.

## References

[1] C. A. Athanasiadis, *On Noncrossing and Nonnesting Partitions for Classical Reflection Groups*, Elec. J. Combin. (1998).

[2] A. Björner and F. Brenti, *Combinatorics of Coxeter Groups*, Springer, New York, 2005.

[3] A. Björner and M. L. Wachs, *Shellable and Nonpure Complexes and Posets II*, Trans. Amer. Math. Soc. **349** (1997), 3945–3975.

[4] C. Ceballos, J.-P. Labbé, and C. Stump, *Subword Complexes, Cluster Complexes, and Generalized Multi-Associahedra*, J. Algebraic Combin. **39** (2014), 17–51.

[5] D. E. Knuth, *The Art of Computer Programming, Vol. 1, Fundamental Algorithms*, 3rd ed., Addison-Wesley, Reading, MA, 1973.

[6] V. Pilaud and C. Stump, *Brick Polytopes of Spherical Subword Complexes and Generalized Associahedra*, Adv. Math. **276** (2015), 1–61.

[7] L.-F. Préville-Ratelle and X. Viennot, *An Extension of Tamari Lattices*, arXiv:1406.3787 (2014).

[8] N. Reading, *Cambrian Lattices*, Adv. Math. **205** (2006), 313–353.

[9] N. Reading, *Clusters, Coxeter-Sortable Elements and Noncrossing Partitions*, Trans. Amer. Math. Soc. **359** (2007), 5931–5958.

[10] N. Reading, *Noncrossing Partitions and the Shard Intersection Order*, J. Algebraic Combin. **33** (2011), 483–530.

[11] N. Reading, *Noncrossing Arc Diagrams and Canonical Join Representations*, arXiv:1405.6904 (2014).

[12] V. Reiner, *Non-Crossing Partitions for Classical Reflection Groups*, Discrete Math. **177** (1997), 195–222.

[13] D. Tamari, *Monoides Préordonnés et Chaînes de Malcev*, Thèse de Mathématiques, Université de Paris, 1951.

[14] N. Williams, *Cataland*, Dissertation, University of Minnesota, 2013.