The νν-Tamari Lattice and the νν-associahedron

We start by introducing the concept of _ν _ν-Tamari lattices using the conventions in [17]. We denote by _ν ν a lattice path with finitely many east and north steps. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F\nu $$\end{document}Fν be the Ferrers diagram weakly above _ν _ν, inside the smallest rectangle containing ν ν. We denote by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\nu $$\end{document}Aν the set of lattice points weakly above ν ν, which are inside \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F\nu $$\end{document}Fν. For a lattice point \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p\in A\nu $$\end{document}p∈Aν, we denote by d(p) the lattice distance from p to the top-left corner of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F\nu $$\end{document}Fν.

Definition 5

(_ν ν-tree [17]) For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ p, q \in A\nu $$\end{document}p,q∈Aν, we say that p and q are _ν ν-incompatible, denoted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p \not \sim q$$\end{document}p≁q, if and only if p is southwest (SW) of q or p is northeast (NE) of q, and the smallest rectangle containing p and q lies completely inside \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ F\nu $$\end{document}Fν. A ν ν-tree is a maximal collection of pairwise _ν ν-compatible elements in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\nu $$\end{document}Aν. Its elements are called nodes and the top left corner is called root. We associate a rooted binary tree to each _ν _ν-tree T by connecting every _p∈ T_p∈T other than the root to the next in north or west direction, see Fig. 3 (Left).

Definition 6

(_ν _ν-Tamari lattice [17]) Two _ν _ν-trees _T,T'_T,T′ are related by a right rotation (or increasing flip) if _T'_T′ can be obtained from T by exchanging _q∈ T_q∈T with _q'∈ T'_q′∈T′ as shown in Fig. 2 with _p,r∈ T,T'_p,r∈T,T′. The ν ν-Tamari lattice is the rotation poset of _ν _ν-trees. An example of the Hasse diagram of the _ν _ν-Tamari lattice for _ν =ENEEN_ν=ENEEN is the edge graph of Fig. 5.

Fig. 2: Right rotation

Definition 7

(_ν _ν-Tamari Complex [17]) The ν ν-Tamari complex is the simplicial complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{T}\mathcal{C}(\nu $$\end{document}TC(ν) of pairwise _ν ν-compatible sets in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\nu $$\end{document}Aν. The dimension of a face I is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {dim}(I)=|I|-1$$\end{document}dim(I)=|I|-1. The facets are the _ν _ν-trees.

Definition 8

(ν ν-subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q\nu ,w\nu )$$\end{document}SC(Qν,wν) [17]) Given a lattice path ν ν we label each lattice point \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p \in A\nu $$\end{document}p∈Aν by the transposition \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s{d(p)+1}$$\end{document}sd(p)+1, see Fig. 3 (Middle) for an example. Furthermore, define \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q_\nu $$\end{document}Qν as the word obtained by reading the associated transpositions from bottom to top, and the columns from left to right. The element \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w_\nu $$\end{document}wν is the product of transpositions in the complement of a _ν ν-tree, see Fig. 3 (Right). The complements of ν ν-trees are reduced expressions of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w\nu $$\end{document}wν in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q\nu $$\end{document}Qν and the effect of a rotation keeps \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w\nu $$\end{document}wν constant.

Fig. 3: Left: a νν-tree for ν =ENEENν=ENEEN. Middle: lattice points \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\nu $$\end{document}Aν labeled by transpositions; the corresponding word is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q_\nu =(s_3,s_2,s_1,s_4,s_3,s_2,s_4,s_3,s_5,s_4)$$\end{document}Qν=(s3,s2,s1,s4,s3,s2,s4,s3,s5,s4). Right: complement of νν-tree and its corresponding element \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w_\nu =s_2s_3s_2s_4=[1,4,3,5,2,6]$$\end{document}wν=s2s3s2s4=[1,4,3,5,2,6]_

The reason why \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w_\nu $$\end{document}wν is independent of the choice of T follows from the connection between _ν _ν-trees and pipe dreams.

Definition 9

(Pipe dream [12, 18]) A pipe dream P is a filling of a triangular shape with crosses and elbows , the lines are called pipes. A pipe dream is called reduced if every pair of pipes crosses at most once. We label the pipes entering on the left from top to bottom with the numbers from 1 to n. The permutation w(P) is the exiting permutation of pipes on the top of the figure, in one line notation. Figure 4 shows an example of two reduced pipe dreams with exiting permutation [1, 4, 3, 5, 2, 6].

Fig. 4: Pipe dreams for νν-trees \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_1$$\end{document}T1 and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_2$$\end{document}T2

To each _ν _ν-tree T we associate a pipe dream P(T) by placing elbows at all nodes of the _ν ν-tree and outside \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F\nu $$\end{document}Fν. This is illustrated in Fig. 4 for two _ν _ν-trees related by a rotation. Note that the exiting permutation remains unchanged, because the action of a tree rotation on pipe dreams exchanges one elbow between two pipes i and j with the unique crossing between pipes i and j (in our example, pipes 3 and 4).

Proposition 2

([17]) The map sending _T→ P(T)_T→P(T) is a bijection between _ν ν-trees and reduced pipe dreams with exiting permutation \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w\nu $$\end{document}wν.

This connection allows us to provide a nice description of the _ν _ν-Tamari complex as a well chosen subword complex.

Theorem 3

([17]) The ν ν-subword complex \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}\mathcal{C}(Q\nu , w\nu )$$\end{document}SC(Qν,wν) is isomorphic to the _ν _ν-Tamari complex.

The interior faces of the _ν _ν-Tamari complex can be characterized as follows.

Definition 10

([19]) A node q in a _ν _ν-tree T is called an ascent if there exists a node in T to the north and another to the east of q. Equivalently, ascents of T are the nodes of T on which we can apply a right rotation.

Lemma 1

([19]) The interior faces I of the _ν _ν-Tamari complex are in bijective correspondence with pairs (T, A), where T is a _ν _ν-tree and A is a subset of its ascents, via the map _I=T ∖ A_I=T\A.

As we can observe from Fig. 5, the _ν _ν-Tamari lattice has a very rich underlying geometric structure. Its Hasse diagram can be geometrically realized as the edge graph of a polytopal complex called the _ν _ν-associahedron [12]. The construction in [12] uses techniques from tropical geometry. The goal of this work is to give new realizations in terms of brick polyhedra. The following is a purely combinatorial definition.

Definition 11

(_ν _ν-Associahedron [12]) The ν ν-associahedron is a polytopal complex induced by an arrangement of tropical hyperplanes, whose poset of faces (ordered by containment) is anti-isomorphic to the poset of interior faces of the _ν _ν-Tamari complex (that is the poset of interior faces ordered by reverse containment).

Corollary 1

([19]) The faces of the _ν _ν-associahedron are in correspondence with pairs (T, A), where T is a _ν _ν-tree and A is a subset of its ascents. The dimension of the face corresponding to (T, A) is the cardinality |A|.

Example 1

(_ν _ν-Associahedron for _ν =ENEEN_ν=ENEEN) Consider the _ν _ν-subword complex for _ν =ENEEN_ν=ENEEN, the _ν _ν-associahedron is shown in Fig. 5, and its edge graph is the Hasse diagram of the _ν _ν-Tamari lattice. The interior face \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_1$$\end{document}I1 illustrated in Fig. 5 corresponds to the orange line segment, while the interior face \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_2$$\end{document}I2 corresponds to the red pentagon. Note that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_2 \subseteq I_1$$\end{document}I2⊆I1, but the face corresponding to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_1$$\end{document}I1 is contained in the face corresponding to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I_2$$\end{document}I2. The containment poset of interior faces is reversed.

Fig. 5: νν-Associahedron for ν =ENEENν=ENEEN