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

HAL
open science

Lattice structure of Grassmann-Tamari orders

Thomas Mcconville

► To cite this version:

Thomas Mcconville. Lattice structure of Grassmann-Tamari orders. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.417-428, 10.46298/dmtcs.2460 . hal-01337806

HAL Id: hal-01337806

https://hal.science/hal-01337806

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Lattice structure of Grassmann-Tamari orders

Thomas McConville¹†

¹School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

**Abstract.** The Tamari order is a central object in algebraic combinatorics and many other areas. Defined as the transitive closure of an associativity law, the Tamari order possesses a surprisingly rich structure: it is a congruence-uniform lattice. In this work, we consider a larger class of posets, the Grassmann-Tamari orders, which arise as an ordering on the facets of the non-crossing complex introduced by Pylyavskyy, Petersen, and Speyer. We prove that the Grassmann-Tamari orders are congruence-uniform lattices, which resolves a conjecture of Santos, Stump, and Welker. Towards this goal, we define a closure operator on sets of paths inside a rectangle, and prove that the biclosed sets of paths, ordered by inclusion, form a congruence-uniform lattice. We then prove that the Grassmann-Tamari order is a quotient lattice of the corresponding lattice of biclosed sets.

**Résumé.** L'ordre Tamari est un objet central dans la combinatoire algébrique et de nombreux autres domaines. Définie comme la fermeture transitive d'une loi d'associativité, l'ordre Tamari possède une structure étonnamment riche: il est un treillis congruence uniforme. Dans ce travail, nous considérons une classe plus large de posets, les ordres Grassmann-Tamari, qui découlent comme un ordre sur les facettes du complexe non-croisement introduit par Pylyavskyy, Petersen, et Speyer. Nous démontrons que les ordres Grassmann-Tamari sont treillis congruence uniformes, ce qui résout une conjecture de Santos, Stump, et Welker. Pour atteindre cet objectif, nous définissons un opérateur de fermeture sur des ensembles de chemins à l'intérieur d'un rectangle, et prouver que les ensembles bifermé de chemins, ordonné par inclusion, forment un réseau de congruence uniforme. Nous démontrons ensuite que l'ordre Grassmann-Tamari est un treillis quotient du treillis correspondant d'ensembles bifermé.

**Keywords:** Tamari lattice, congruence-uniform, lattice quotient, noncrossing complex, Grassmann-Tamari associated, biclosed sets

## 1 Introduction

The Tamari lattice is a poset of proper bracketings of a word, with covering relations defined by the associativity law. Tamari lattices and their generalizations have appeared in many parts of the literature. We recommend the book [14] for an introduction to many recent developments on these posets.

In this extended abstract, we consider a new generalization of the Tamari lattice, the *Grassmann-Tamari order*, introduced by Santos, Stump, and Welker [12]. One of the conjectures they pose is that these posets are lattices. We give an affirmative answer to this conjecture, and show that some of the very good lattice properties of Tamari lattices hold in this larger family of posets; see Theorem 1.1 for a precise statement.

The Grassmann-Tamari order $GT_{k,n}$ is a partial order on the maximal "non-crossing" subsets of $\binom{[n]}{k}$, the $k$-element subsets of $\{1, \dots, n\}$. Two sets $I, J \in \binom{[n]}{k}$ are crossing if $i_t < j_t < i_{t+1} < j_{t+1}$ for some

<footnote>†Email: mcco0489@umn.edu. Supported by RTG grant NSF/DMS-1148634</footnote>
<figure><img src="image_3.png" /><figcaption>**Fig. 1:** (left) Two paths kissing along the indicated segment from *v* to *v'*. The paths correspond to the sets 145 and 246, which are crossing. (right) A maximal family of non-kissing paths excluding horizontal and vertical paths.</figcaption></figure>

$t$ where $I - J = \{i_1 < \cdots < i_l\}$ and $J - I = \{j_1 < \cdots < j_l\}$. The sets $I, J$ are non-crossing otherwise. For example, $\{1, 4, 5\}$ and $\{2, 3, 6\}$ are non-crossing, whereas $\{1, 4, 5\}$ and $\{2, 4, 6\}$ are crossing. The non-crossing complex $\Delta_{k,n}^{NC}$ is the collection of all pairwise non-crossing subsets of $\binom{[n]}{k}$.

For $l \ge 1$, let $C_l$ be a chain poset with $l$ elements. The complex $\Delta_{k,n}^{NC}$ may be realized as a regular, unimodular, Gorenstein triangulation of the order polytope $O_{k,n}$ on $C_k \times C_{n-k}$; i.e., the polytope in $\mathbb{R}^{k(n-k)}$ defined by the inequalities $0 \le x_{i,j} \le 1$, $x_{i,j} \le x_{i+1,j}$, and $x_{i,j} \le x_{i,j+1}$ for $1 \le i \le k$, $1 \le j \le n-k$ ([6, Theorem 8.1] or [12, Theorem 1.7]). This triangulation of $O_{k,n}$ is distinct from the equatorial triangulation defined in [10], which is not flag in general. As a consequence of this geometric realization, after removing cone points, $\Delta_{k,n}^{NC}$ is a pure, thin complex of dimension $(k-1)(n-k-1)-1$. Moreover, there exists a simple polytope, the *Grassmann-associahedron*, with facial structure anti-isomorphic to $\Delta_{k,n}^{NC}$. In the full paper, we present an alternative proof of this result by constructing the dual Grassmann-associahedron by a sequence of suspensions and edge-stellations, starting from an empty complex.

Any triangulation of $O_{k,n}$ naturally gives rise to a monomial basis for the coordinate ring of the Grassmannian, the $\mathbb{C}$-algebra generated by the maximal minors of a $k \times n$ matrix of indeterminates ($x_{ij}$) [6]. Namely, a monomial $\prod_1^r x_{I_j}$ is in the basis if $\{I_1, \dots, I_r\}$ is a face of the triangulation. The classical standard basis for this algebra is indexed by semistandard Young tableaux. The columns of a semistandard Young tableaux satisfy a compatibility condition that resembles a non-nesting analogue of the non-crossing condition defined above. Thus these two bases may be viewed as "opposite" in some sense. One may hope to develop a straightening law for these monomials, though we do not pursue this here.

Let $\mathcal{J}$ be the set of order ideals of $C_k \times C_{n-k}$. The *Hibi ideal* is the ideal generated by $\{x_I x_J - x_{I \cap J} x_{I \cup J} : I, J \in \mathcal{J}\}$ in the polynomial ring on $\{x_I : I \in \mathcal{J}\}$. By results of [13], regular unimodular triangulations of $O_{k,n}$ are in bijection with squarefree monomial initial ideals of the Hibi ideal. As observed in the introduction of [12], the triangulation induced by $\Delta_{k,n}^{NC}$ corresponds to a particularly nice initial ideal. We refer to the survey [2, Section 6] for more background on Hibi ideals.

There is a natural orientation on the dual graph of $\Delta_{k,n}^{NC}$. If two facets $F_1 = F \cup \{I\}$, $F_2 = F \cup \{J\}$ are adjacent, then there is a unique index $t$ for which $i_t < j_t < i_{t+1} < j_{t+1}$ where $I - J = \{i_1 < \cdots < i_l\}$ and $J - I = \{j_1 < \cdots < j_l\}$. We orient the edge $F_1 \to F_2$ if the pair $\{i_t, i_{t+1}\}$ is lexicographically smaller than $\{j_t, j_{t+1}\}$. For example, $\{145, 146, 236, 245\}$ and $\{146, 236, 245, 246\}$ are adjacent facets of $\Delta_{3,6}^{NC}$ with orientation $\{145, 146, 236, 245\} \to \{146, 236, 245, 246\}$ since 145 and 246 cross at 15 and 26. Defined by Santos, Stump, and Welker in [12], the *Grassmann-Tamari order* $GT_{k,n}$ is the transitive closure of this relation. The smallest Grassmann-Tamari order not isomorphic to a Tamari lattice is drawn in Figure 4.
The non-crossing condition translates to a *non-kissing* condition on paths via the standard bijection between $k$-subsets of $[n]$ and paths in a $k \times (n-k)$ rectangle with South and East steps. For example, the set $\{1, 4, 5\}$ corresponds to the path from the NW-corner to the SE-corner of a $3 \times 3$ rectangle such that the first, fourth, and fifth steps are to the South, while the others are to the East. Two paths $p_1, p_2$ in the plane are *kissing* if they agree on some subpath between vertices $v$ and $v'$, $p_1$ enters $v$ from the West and leaves $v'$ to the South, and $p_2$ enters $v$ from the North and leaves $v'$ to the East; see Figure 1. The non-kissing complex $\Delta^{NK}(\lambda)$ associated to a (possibly not rectangular) shape $\lambda$ is the collection of pairwise non-kissing paths supported by $\lambda$. A poset $GT(\lambda)$ analogous to the Grassmann-Tamari orders may be defined on the facets of this complex. We call $GT(\lambda)$ the *Grid-Tamari order*; see Section 2. If $\lambda$ is a $k \times (n-k)$ rectangle, then $GT(\lambda)$ is isomorphic to $GT_{k,n}$.

Our main result is

**Theorem 1.1** For any shape $\lambda$, $GT(\lambda)$ is a congruence-uniform lattice.

We recall congruence-uniformity and related lattice properties in Section 3.

To prove Theorem 1.1, we express $GT(\lambda)$ as a lattice quotient of a much simpler lattice. Namely, we define a finite topological space whose clopen sets, which we call *biclosed sets*, form a congruence-uniform lattice under inclusion. Then we define a map from the collection of biclosed sets to facets of the non-kissing complex that carries this lattice structure. A similar approach was applied by Nathan Reading to prove that Tamari posets are lattice quotients of the weak order on the symmetric group (see e.g. [8]).

The rest of this extended abstract is organized as follows. In Section 2, we establish the purity and thinness of the non-kissing complex combinatorially, similar to the methodology employed in [12] for proving purity and thinness of the non-crossing complex. We close the section by defining the orientation on the dual graph of the non-kissing complex whose transitive closure is a Grid-Tamari order. We emphasize that this directed graph is acyclic as a *consequence* of Theorem 1.1. A geometric proof of acyclicity in the non-crossing case appears in [12].

To set up the appropriate generalization of the weak order, we prove some general results on biclosed sets in Section 3. Biclosed sets may be defined for any closure operator on a set, though the resulting poset of biclosed sets may not be interesting. We provide some conditions on the closure that makes the poset of biclosed sets a semidistributive or congruence-normal lattice. In particular, these conditions are satisfied by the convex closure on the positive roots of a finite root system.

In Section 4, we introduce a poset of biclosed subsets of segments in a shape $\lambda$. We show that this poset satisfies the hypotheses given in Section 3, so it is a congruence-uniform lattice.

A special lattice congruence on the lattice of biclosed sets of segments is presented in Section 5. In Section 6, we define a map $\eta$ from biclosed sets of segments to the facets of the non-kissing complex, and show that the fibers of $\eta$ are precisely the equivalence classes of this lattice congruence. We deduce Theorem 1.1 by comparing the order induced by $\eta$ with the Grid-Tamari order.

In this extended abstract, most of the intermediary results are illustrated by example in place of proof. Proofs will appear in the full version.

## 2 Non-kissing complexes

A *shape* $\lambda$ is a finite (vertex)-induced subgraph of the $\mathbb{Z} \times \mathbb{Z}$ square grid. A vertex $v \in \lambda$ is *interior* if $\lambda$ contains the $2 \times 2$ grid centered at $v$. Otherwise, $v$ is a *boundary vertex*. A horizontal (vertical) edge $e$ of $\lambda$ is *interior* if the $1 \times 2$ (2 $\times$ 1) box centered at $e$ is contained in $\lambda$.
<figure><img src="image_4.png" /><figcaption>Fig. 2: A shape with a path $w_0, w_1, w_2, w_3, w_4$.</figcaption></figure>

A *path* supported by $\lambda$ is a sequence of vertices $v_0, \dots, v_t$ such that

• $v_0$ and $v_t$ are boundary vertices,

• $v_1, \dots, v_{t-1}$ are interior vertices, and

• $v_i$ is one step South or East of $v_{i-1}$ for all $i$.

A path supported by $\lambda$ is called a *segment* if its endpoints are also interior vertices. If $s$ is a segment containing vertices $v$ and $v'$, then $s[v, v']$ denotes the sub-segment of $s$ whose endpoints are $v$ and $v'$. The initial (terminal) vertex of a segment $s$ is denoted $s_{\text{init}}$ ($s_{\text{term}}$).

A path $w_0, w_1, w_2, w_3, w_4$ is drawn in Figure 2. This path contains the segment $w_2, w_3$, for example. Two paths $p_1, p_2$ are *kissing* if they share vertices $v, v'$ such that

• $p_1[v, v'] = p_2[v, v']$,

• $p_1$ enters $v$ from the West and leaves $v'$ to the South, and

• $p_2$ enters $v$ from the North and leaves $v'$ to the East.

Otherwise $p_1$ and $p_2$ are *non-kissing*. The *non-kissing complex* $\Delta^{NK}(\lambda)$ is the flag simplicial complex whose faces are collections of pairwise non-kissing paths supported by $\lambda$. As horizontal and vertical paths are non-kissing with any path, we define the *reduced non-kissing complex* $\tilde{\Delta}^{NK}(\lambda)$ to be the deletion of all horizontal and vertical paths from $\Delta^{NK}(\lambda)$.

Although a pair of non-kissing paths may twist around each other several times, there is a natural way to totally order paths that contain a specific edge. Let $e$ be an interior edge of $\lambda$. If $p_1$ and $p_2$ are distinct non-kissing paths containing $e$, then they agree on some maximal subpath $p_1[v, v']$ containing $e$. Order $p_1 <_e p_2$ if either $p_1$ enters $v$ from the North or $p_1$ leaves $v'$ to the South. We note that both cases may not occur if $v$ or $v'$ is a boundary vertex.

If $F$ is a set of non-kissing paths, we say a path $p \in F$ is the *bottom path* (top path) at an edge $e$ if $p$ is minimal (maximal) in $F$ with respect to $<_e$.

**Theorem 2.1** Let $F$ be a facet of $\Delta^{NK}(\lambda)$.

1. The map that takes an interior edge $e$ to the top path at $e$ is a bijection between vertical interior edges of $\lambda$ and non-horizontal paths in $F$.
2. For paths $p \in F$ with at least one turn, there exists a unique path $q$ distinct from $p$ such that $F - \{p\} \cup \{q\}$ is non-kissing. Moreover, $p$ and $q$ kiss at a unique segment.

A simplicial complex is *pure* if its facets all have the same dimension. A pure complex is *thin* if every face of codimension 1 is contained in exactly two facets. Theorem 2.1 immediately implies the following corollary.

**Corollary 2.2** For any shape $\lambda$, the reduced non-kissing complex $\tilde{\Delta}^{NK}(\lambda)$ is a pure, thin simplicial complex.

**Example 2.3** We illustrate Theorem 2.1 with the facet $F = \{145, 146, 236, 245\}$ of $\tilde{\Delta}_{3,6}^{NC}$. The sets in $F$ correspond to the four non-kissing paths drawn in Figure 1. Including the two vertical paths 234 and 345, each of the six paths in $F \cup \{234, 345\}$ is the top path at a unique interior vertical edge.

The unique facet distinct from $F$ containing $F - \{145\}$ is $(F - \{145\}) \cup \{246\}$. If one removes 145 from $F$, then 245 is on top at two different vertical edges. The segment supported by 245 between these two vertical edges is the unique segment along which the paths 145 and 246 kiss.

The dual graph of a pure thin complex is the set of facets where two facets are adjacent if they intersect at a codimension 1 face. We define an orientation on the dual graph of $\tilde{\Delta}^{NK}(\lambda)$ as follows. Let $F_1, F_2$ be adjacent facets, and let $p_1 \in F_1 - F_2$, $p_2 \in F_2 - F_1$. Then $p_1$ and $p_2$ are kissing at a unique segment, say $p_1[v, v']$. Orient the edge $F_1 \to F_2$ if $p_1$ enters $v$ from the West (so $p_2$ enters $v$ from the North). Let $\text{GT}(\lambda)$ be the transitive closure of this relation.

**Theorem 2.4** (see [12], Theorem 2.17) $\text{GT}(\lambda)$ is a partially ordered set.

We call $\text{GT}(\lambda)$ the *Grid-Tamari order*. When $\lambda$ is a $2 \times n$ rectangle, $\text{GT}(\lambda)$ is the usual Tamari lattice. For general $\lambda$, Theorem 2.4 is far from obvious. In [12], it is proved for all rectangle shapes by identifying $\text{GT}(\lambda)$ with a poset of facets of a regular triangulation of a polytope, whose order is induced by a generic linear functional. We prove this combinatorially in Section 6 along with Theorem 1.1 by identifying $\text{GT}(\lambda)$ with a lattice quotient of some other lattice.

## 3 Biclosed Sets

A closure operator on a set $S$ is an operator $X \mapsto \bar{X}$ on subsets of $S$ such that for $X, Y \subseteq S$,

$$X \subseteq \bar{X},$$

$$\bar{X} = \bar{X}, \text{ and}$$

$$X \subseteq Y \text{ implies } \bar{X} \subseteq \bar{Y}.$$

In addition, we assume $\emptyset = \emptyset$. A subset $X$ of $S$ is *closed* if $X = \bar{X}$. A subset $X$ is *biclosed* if $X$ and $S \setminus X$ are both closed. We let $\text{Bic}(S)$ be the poset of biclosed subsets of $S$ ordered by inclusion. By our assumption, $S$ and $\emptyset$ are always biclosed.

What we call biclosed sets are often called clopen sets elsewhere in the literature; see, for example [11]. The term biclosed typically refers to a subset of a convex geometry which is 2-closed and whose complement is 2-closed. We choose the term biclosed because all of the closure operators we consider come from some convex geometry in this way. This connection will be explained further in the full paper.
A collection $\mathcal{B}$ of subsets of $S$ is ordered by single-step inclusion if for all $X, Y \in \mathcal{B}$ such that $X \subsetneq Y$ there exists $y \in Y \setminus X$ such that $X \cup \{y\} \in \mathcal{B}$. If $\emptyset, S \in \mathcal{B}$ and $\mathcal{B}$ is ordered by single-step inclusion, then it is a graded poset with rank function $X \mapsto |X|$ for $X \in \mathcal{B}$; in particular, every maximal chain has length $|S|$.

A lattice $L$ is meet-semidistributive if $L$ satisfies $x \wedge z = y \wedge z \Rightarrow (x \vee y) \wedge z = x \wedge z$ for $x, y, z \in L$. A lattice is join-semidistributive if its dual is meet-semidistributive. A lattice is semidistributive if it is both meet- and join-semidistributive. We give some criteria on semidistributivity for biclosed sets.

**Theorem 3.1** Let $S$ be a set with a closure operator. If

1. Bic($S$) is ordered by single-step inclusion, and

2. $W \cup (\overline{X \cup Y}) \setminus \overline{W}$ is biclosed for $W, X, Y \in \text{Bic}(S)$ with $W \subseteq X \cap Y$, then Bic($S$) is a semidistributive lattice.

Suppose Bic($S$) is a lattice. If $W, X, Y \in \text{Bic}(S)$ with $W \subseteq X \cap Y$, then

$$X \cup Y \subseteq W \cup (\overline{X \cup Y}) \setminus \overline{W} \subseteq \overline{X \cup Y} \subseteq X \vee Y,$$

so $X \vee Y$ and $W \cup (\overline{X \cup Y}) \setminus \overline{W}$ are equal if the latter is biclosed.

**Example 3.2** The inversion set of a permutation $\pi$ of $[n]$ is the collection of pairs $\{i, j\}$ for which $\pi^{-1}(i) > \pi^{-1}(j)$. For example, the inversion set of 2314 is $\{12, 13\}$. The weak order on permutations of $[n]$ is the ordering by inclusion of inversion sets.

The weak order on permutations may be identified with a collection of “biclosed” subsets of $\binom{[n]}{2}$, ordered by inclusion. A subset $X$ of $\binom{[n]}{2}$ is closed if $\{i, k\}$ is in $X$ whenever $\{i, j\}$ and $\{j, k\}$ are in $X$ for some $j$ with $i < j < k$. Then $X$ is biclosed if both $X$ and $\binom{[n]}{2} - X$ are closed. The map taking a permutation to its inversion set is an isomorphism between the weak order and the poset of biclosed subsets of $\binom{[n]}{2}$.

More generally, the weak order on any finite Coxeter group may be identified with a poset of biclosed sets of positive roots ordered by inclusion. That these posets are ordered by single-step inclusion is well-known. Dyer proved that $W \cup (\overline{X \cup Y}) \setminus \overline{W}$ is a biclosed set whenever $W, X, Y$ are biclosed and $W \subseteq X \cap Y$ [4]. He also proved this holds for infinite root systems if $X \cup Y$ is finite. By Theorem 3.1 we may deduce that the weak order for finite lower intervals of (possibly infinite) Coxeter groups is a semidistributive lattice. Other proofs of semidistributivity appear in [5] and [7]; see also [9, Section 8] for a refinement of this result.

A subset $C$ of a poset $P$ is order-convex if $z \in C$ whenever $x, y \in C$ and $x \le z \le y$. Given an order-convex subset $C$ of $P$, the doubling $P[C]$ is the induced subposet of $P \times \{0, 1\}$ with elements

$$P[C] = (P_{\le C} \times \{0\}) \sqcup [(P - P_{\le C}) \cup C] \times \{1\},$$

where $P_{\le C} = \{x \in P : (\exists c \in C) x \le c\}$. If $P$ is a lattice, then $P[C]$ is a lattice where

$$(x, \epsilon) \vee (y, \epsilon') = \begin{cases} (x \vee y, \max(\epsilon, \epsilon')) & \text{if } x \vee y \in P_{\le C}, \\ (x \vee y, 1) & \text{otherwise} \end{cases},$$
<figure><img src="image_5.png" /><figcaption>Fig. 3: A sequence of doublings, ending with the weak order on $\mathfrak{S}_4$.</figcaption></figure>

for $(x, \epsilon), (y, \epsilon') \in P[C]$. A finite lattice $L$ is congruence-normal if there exists a sequence of lattices $L_1, \dots, L_t$ such that $L_1$ is the one-element lattice, $L_t = L$, and for all $i$, there exists an order convex subset $C_i$ of $L_i$ such that $L_{i+1} \cong L_i[C_i]$. A finite lattice is congruence-uniform (or bounded) if it is both congruence-normal and semidistributive.

The weak order on permutations is a congruence-normal lattice; see Figure 3 for a sequence of doublings that creates the weak order on $\mathfrak{S}_4$. The general case is discussed in Example 3.5.

Congruence-normal and congruence-uniform lattices admit other characterizations in terms of lattice congruences [3]. Additionally, congruence-uniform lattices may be characterized as lattice quotients of free lattices for which every fiber is a closed interval. As free lattices on finite sets are typically infinite, this interval property is quite special.

For our purposes, it is easier to employ Reading's characterization of congruence-normal lattices by CN-labelings defined as follows. For elements $x$ and $y$ of a poset $P$, $y$ covers $x$ if $x < y$ and $x \le z \le y$ implies $x = z$ or $z = y$ for $z \in P$. We write $x \prec y$ if $y$ covers $x$, and let $\text{Cov}(P)$ denote the set of pairs $(x, y)$ for which $x \prec y$. An edge-labeling of a poset $P$ is a function from $\text{Cov}(P)$ to some label set $R$. An edge-labeling $\lambda: L \to R$ from a lattice $L$ to a poset $(R, \preceq)$ is a CN-labeling if $L$ and its dual $L^*$ satisfy the following condition: For elements $x, y, z \in L$, $(z, x), (z, y) \in \text{Cov}(L)$ and maximal chains $C_1, C_2 \in [z, x \lor y]$ with $x \in C_1, y \in C_2$,

(CN1) The elements $x' \in C_1, y' \in C_2$ such that $(x', x \lor y), (y', x \lor y) \in \text{Cov}(L)$ satisfy

$$ \lambda(z, x) = \lambda(y', x \lor y), \quad \lambda(z, y) = \lambda(x', x \lor y). $$

(CN2) If $(u, v) \in \text{Cov}(C_1)$ with $z < u, v < x \lor y$, then $\lambda(z, x) \prec \lambda(u, v)$ and $\lambda(z, y) \prec \lambda(u, v)$.

(CN3) The labels on $\text{Cov}(C_1)$ are all distinct.

**Theorem 3.3 ([7], Theorem 4)** A finite lattice $L$ is congruence-normal if and only if it admits a CN-labeling.

A CN-labeling of the Grassmann-Tamari order $\text{GT}_{3,6}$ is drawn in Figure 4.

**Theorem 3.4** Let $(S, \prec)$ be a poset with a closure operator. Assume that

1. $\text{Bic}(S)$ is ordered by single-step inclusion,

2. $W \cup (X \cup Y) \setminus W$ is biclosed for $W, X, Y \in \text{Bic}(S)$ with $W \subseteq X \cap Y$, and
<figure><img src="image_6.png" /><figcaption>Fig. 4: (left) GT$_{3,6}$ (right) Ordering on edge labels</figcaption></figure>

3. if $x, y, z \in S$ with $z \in \overline{\{x, y\}} - \{x, y\}$ then $x \prec z$ and $y \prec z$.

Then $\text{Bic}(S)$ is a congruence-normal lattice.

The first hypothesis in Theorem 3.4 gives a natural labeling of the covering relations in $\text{Bic}(S)$. The third hypothesis gives an order structure on these labels. The proof of Theorem 3.4 amounts to showing that this labeling is a CN-labeling.

**Example 3.5** For the closure operator on $([n]_2)$ in Example 3.2, we define a partial order $\{i, j\} \le \{k, l\}$ if $k \le i < j \le l$. As this partial order satisfies property (3), we deduce that the weak order on permutations is congruence-normal by Theorem 3.4. This holds more generally for the weak order of any finite Coxeter group ([1, Theorem 6] or [7, Theorem 27]).

# 4 Biclosed Sets of Segments

For the remainder of this abstract, we fix a shape $\lambda$ and let $S$ denote the set of segments supported by $\lambda$, partially ordered by inclusion. Two segments $s$ and $t$ are *composable* if $s_{\text{term}}$ is one unit North or West of $t_{\text{init}}$. If $s$ and $t$ are composable, then the composite $s \circ t$ is the segment containing both $s$ and $t$. Given a set $X$ of segments of $\lambda$, say $X$ is *closed* if $s \circ t \in X$ whenever $s, t \in X$ and $s \circ t$ exists; see Figure 5. We let $\text{Bic}(S)$ denote the poset of biclosed sets of segments, as in Section 3.

**Example 4.1** Suppose $\lambda$ is a $2 \times n$ rectangle. Labeling the interior vertices 1, ..., $n-1$ from left to right, a segment $s$ may be identified with the set $\{i, j\} \in (\begin{bmatrix} n \\ 2 \end{bmatrix})$ where $i$ is the label on $s_{\text{init}}$ and $j-1$ is the label on $s_{\text{term}}$. The closure on segments then agrees with the closure on $(\begin{bmatrix} n \\ 2 \end{bmatrix})$ defined in Example 3.2. Hence, $\text{Bic}(S)$ is isomorphic to the weak order on permutations of $[n]$.

**Theorem 4.2** For $S$ and $\lambda$ defined above,
<figure><img src="image_7.png" /><figcaption>Fig. 5: (1) Two composable segments. (2) A biclosed set X of five segments. (3) $X^{\perp}$. (4) $X^{\uparrow}$.</figcaption></figure>

1. Bic(S) is ordered by single-step inclusion,

2. $W \cup \overline{(X \cup Y)} - W$ is biclosed for $W, X, Y \in \text{Bic}(S)$ with $W \subseteq X \cap Y$, and

3. if $s, t, u \in S$ such that $s \circ t = u$, then $s \subsetneq u$ and $t \subsetneq u$.

Applying Theorems 3.1 and 3.4, we deduce

**Corollary 4.3** Bic(S) is a congruence-uniform lattice.

The hypotheses of Theorems 3.1 and 3.4 were chosen with two examples in mind, namely the 2-closure on finite root systems and the closure operator defined in this section. For the 2-closure on a real simplicial hyperplane arrangement, the first two hypotheses hold, but the third may not. In this case, a weaker version of the acyclic condition is enough to prove congruence-normality [7, Theorem 25].

An alternative approach to the proof of congruence-uniformity of Bic(S) would be to apply some of the results of [11]. In their language, the (po)set S forms an algebraic closure space of semilattice type. From their general results about such spaces, the congruence-uniformity of Bic(S) then follows from its semidistributivity.

# 5 A quotient of Bic(S)

If $s, t \in S$ such that $t \subseteq s$, we say $t$ is a SW-subsegment (NE-subsegment) of $s$ if

* $s_{\text{init}} = t_{\text{init}}$ or $s$ enters $t_{\text{init}}$ from the North (West), and

* $s_{\text{term}} = t_{\text{term}}$ or $s$ leaves $t_{\text{term}}$ to the East (South).

Given a biclosed set $X$ of segments, let $X^{\perp}$ be the set of segments $s$ in $X$ such that $t$ is in $X$ whenever $t$ is a SW-subsegment of $s$. Let $X^{\uparrow}$ be the set of segments $s$ such that there exists $t$ in $X$ that is a NE-subsegment of $s$. An example is shown in Figure 5.

**Lemma 5.1** The following results hold.

1. $X \mapsto X^{\uparrow}$ is a closure operator on Bic(S).

2. $X \mapsto X^{\downarrow}$ is a closure operator on the dual of Bic(S).
3. $X^{\downarrow} = Y^{\downarrow}$ if and only if $X^{\uparrow} = Y^{\uparrow}$ for $X, Y \in \text{Bic}(S)$.

An equivalence relation $\Theta$ on a lattice $L$ is a *lattice congruence* if $x \equiv y \bmod \Theta$ implies $x \vee z \equiv y \vee z$ mod $\Theta$ and $x \wedge z \equiv y \wedge z$ mod $\Theta$ for $x, y, z \in L$. The set of equivalence classes $L/\Theta$ of a lattice congruence forms a lattice where $[x] \vee [y] = [x \vee y]$ and $[x] \wedge [y] = [x \wedge y]$ for $x, y \in L$. We say $L/\Theta$ is a *quotient lattice* of $L$, and the natural map $L \mapsto L/\Theta$ is a *lattice quotient map*. The following characterization of lattice congruences is well-known.

**Proposition 5.2** Let $\Theta$ be an equivalence relation on a finite lattice $L$. If

1. the equivalence classes of $\Theta$ are all closed intervals of $L$, and

2. the maps $\pi^{\uparrow}$ and $\pi_{\downarrow}$ taking an element of $L$ to the largest (respectively, smallest) element of its equivalence class are both order-preserving,

then $\Theta$ is a lattice congruence.

Let $\Theta$ be the equivalence relation on $\text{Bic}(S)$ where $X \equiv Y$ mod $\Theta$ if $X^{\downarrow} = Y^{\downarrow}$. Using Lemma 5.1 with Proposition 5.2, we deduce

**Corollary 5.3** $\Theta$ is a lattice congruence on $\text{Bic}(S)$.

**Example 5.4** Let $\lambda$ be the $2 \times n$ rectangle from Example 4.1. If $X$ is a biclosed subset of $S$, then $X^{\downarrow}$ is the set obtained by removing horizontal segments for which some initial part is not in $X$. The set $X^{\uparrow}$ is obtained by adding horizontal segments to $X$ for which some initial part is not in $X$ but the corresponding terminal part is in $X$. By this observation it follows that $X^{\downarrow}$ is the largest biclosed set for which $(X^{\uparrow})^{\downarrow} = X^{\downarrow}$. In particular, the equivalence classes are all closed intervals of the form $[X^{\downarrow}, X^{\uparrow}]$ for some $X \in \text{Bic}(S)$. Moreover, $\pi^{\uparrow}(X) = X^{\uparrow}$ and $\pi_{\downarrow}(X) = X^{\downarrow}$, so $\pi^{\uparrow}$ and $\pi_{\downarrow}$ are both order-preserving maps, thus verifying Corollary 5.3 in this case. The argument for general shapes follows similar reasoning.

When $\lambda$ is a $2 \times n$ rectangle, the bijection in Example 4.1 takes biclosed sets $X$ for which $X^{\downarrow} = X$ to inversion sets of 312-avoiding permutations. Indeed, if a permutation $\sigma = \sigma_1 \cdots \sigma_n$ contains a 312 pattern, say with values $i < j < k$, then the corresponding biclosed set $X$ has a long segment labeled $\{i, k\}$ for which the initial part $\{i, j\}$ is not in $X$.

# 6 The Grid-Tamari order as a lattice quotient

Let $E_V$ denote the set of interior vertical edges in $\lambda$ and let $\mathcal{P}$ be the set of paths supported by $\lambda$.

We define a function $\eta : \text{Bic}(S) \to 2^{\mathcal{P}}$ as follows. Let $X \in \text{Bic}(S)$ be given. If $e \in E_V$ is an edge from $u$ to $v$, let $p_e$ be the path such that for interior vertices $u' \in p_e[\cdot, u]$ and $v' \in p_e[v, \cdot]$:

(i) if $p_e[u', u]$ is (not) in $X$ then $p_e$ enters $u'$ from the North (West); and

(ii) if $p_e[v, v']$ is (not) in $X$ then $p_e$ leaves $v'$ to the East (South).

Let $\eta(X)$ be the union of $\{p_e : e \in E_V\}$ with the set of horizontal paths supported by $\lambda$. For example, if $X$ is the biclosed set of six black segments in Figure 6, each of the six interior vertical edges corresponds to a non-horizontal path in $\eta(X)$. In Figure 6, the four paths corresponding to the four marked purple edges are drawn. The other two vertical edges correspond to vertical paths.
<figure><img src="image_8.png" /><figcaption>Fig. 6: The four non-vertical and non-horizontal paths in η(X) where X is the set of black segments.</figcaption></figure>

**Proposition 6.1** *η(X)* is a maximal collection of non-kissing paths.

When Bic(*S*) is viewed as a lattice, we claim that η defines a lattice quotient map, thus endowing the set of facets of Δ<sup>NK</sup>(λ) with the structure of a lattice. Explicitly, we claim that η is surjective, and if X and Y are biclosed, then η(X) = η(Y) if and only if X ≡ Y mod Θ.

To prove this claim, we define another function φ from facets of Δ<sup>NK</sup>(λ) to Bic(S) as follows. For a path *p*, let A<sub>*p*</sub> be the set of SW-subsegments of *p*. If *F* is a facet of Δ<sup>NK</sup>(λ), we define φ(*F*) to be ⋃<sub>*p*∈*F*</sub> A<sub>*p*</sub>. It may be shown that φ and η are inverse bijections between facets of Δ<sup>NK</sup>(λ) and biclosed sets X for which X↓ = X.

To complete the proof of Theorem 1.1, it remains to show that the ordering on facets of Δ<sup>NK</sup>(λ) induced by η is identical to the Grid-Tamari order. For this, it suffices to compare covering relations.

Acknowledgements

I thank Nathan Reading for pointing out the reference [11]. I also thank Christian Stump for making his data on Grassmann-Tamari orders available for my use. Lastly, I thank Nathan Reading, Vic Reiner, Pasha Pylyavskyy, and the referees for many helpful remarks in the preparation of this extended abstract.

References

[1] Nathalie Caspard, Claude Le Conte de Poly-Barbut, and Michel Morvan. Cayley lattices of finite coxeter groups are bounded. *Advances in Applied Mathematics*, 33(1):71–94, 2004.

[2] Aldo Conca, Serkan Hosten, and Rekha R Thomas. Nice initial complexes of some classical ideals. *Contemporary Mathematics*, 423:11–42, 2007.

[3] Alan Day. Congruence normality: the characterization of the doubling class of convex sets. *Algebra Universalis*, 31(3):397–406, 1994.

[4] Matthew Dyer. On the weak order of coxeter groups. *arXiv preprint arXiv:1108.5557*, 2011.

[5] Claude Le Conte de Poly-Barbut. Sur les treillis de coxeter finis. *Mathématiques, informatique et sciences humaines*, 32(125):41–57, 1994.

[6] T Kyle Petersen, Pavlo Pylyavskyy, and David Speyer. A non-crossing standard monomial theory. *Journal of Algebra*, 324(5):951–969, 2010.
[7] Nathan Reading. Lattice and order properties of the poset of regions in a hyperplane arrangement. *Algebra Universalis*, 50(2):179–205, 2003.

[8] Nathan Reading. From the tamari lattice to cambrian lattices and beyond. In *Associahedra, Tamari Lattices and Related Structures*, pages 293–322. Springer, 2012.

[9] Nathan Reading and David Speyer. Sortable elements in infinite coxeter groups. *Transactions of the American Mathematical Society*, 363(2):699–761, 2011.

[10] Victor Reiner and Volkmar Welker. On the charney–davis and neggers–stanley conjectures. *Journal of Combinatorial Theory, Series A*, 109(2):247–280, 2005.

[11] Luigi Santocanale and Friedrich Wehrung. Lattices of regular closed subsets of closure spaces. *arXiv preprint arXiv:1307.1480*, 2013.

[12] Francisco Santos, Christian Stump, and Volkmar Welker. Noncrossing sets and a grassmann associ-
ahedron. *arXiv preprint arXiv:1403.8133*, 2014.

[13] Bernd Sturmfels. Grobner bases and convex polytopes, university lecture series, vol. 8. *American Mathematical Society, Providence, RI*, 1996.

[14] Dov Tamari, Folkert Müller-Hoissen, Jean Marcel Pallo, and James D Stasheff. *Associahedra, Tamari Lattices and Related Structures: Tamari Memorial Festschrift*. Birkhäuser, Springer, 2012.