Séminaire Lotharingien de Combinatoire 79 (2020), Article B79d

EXCEPTIONAL AND MODERN INTERVALS OF THE TAMARI LATTICE

BAPTISTE ROGNERUD

Abstract. In this article we use the theory of interval-posets recently introduced by Châtel and Pons in order to describe some interesting families of intervals in the Tamari lattices. These families are defined as interval-posets avoiding specific configurations. At first, we consider exceptional interval-posets and we show that they correspond to the intervals which are obtained as images of non-crossing trees in the Dendriform operad. We also show that the exceptional intervals are exactly the intervals of the Tamari lattices induced by intervals in the posets of non-crossing partitions. In the second part, we introduce the notion of modern and infinitely modern interval-posets. We show that the modern intervals are in bijection with the new intervals of the Tamari lattices in the sense of Chapoton. Finally, we consider the family of infinitely modern intervals and we prove that there are as many infinitely modern interval-posets of size n as there are ternary trees with n inner vertices.

1. Introduction

The family of the Tamari lattices is extremely rich from the point of view of combinatorial algebra. It has two main interpretations as posets of type A. First, the Tamari lattice on the set of binary trees with n inner vertices, denoted by Tam_{n}, is isomorphic to the poset of tilting modules over a linearly oriented quiver of type A_{n} (see [BK04] and [HU05] for more details. A bijection between tilting modules and binary trees was already defined by Gabriel [Gab81]). On the other hand, it is part of the Cambrian lattices of type A_{n−1} (see [Rea06] for more details). Finally, let DW_{n} be the distributive lattice of upper ideals in the poset of positive roots of the root system of type A_{n−1}. Then the Tamari lattice Tam_{n} is conjecturally deeply related to DW_{n} (see [Cha12, Conjecture 5.3] for more details).

As another intriguing feature of this lattice, we have its poset of intervals. It was proved by Chapoton that there is a beautiful formula for the number of intervals in the Tamari lattice:

number of intervals in Tam_{n} =\frac{2(4n + 1)!}{(n + 1)!(3n + 2)!}.

It is remarkable that this formula has such a simple factorized form. More recently, in [Cha17], Chapoton associated to any finite poset P a polynomial in 4 variables that enumerates the intervals of P and he proved that the polynomial of the Tamari lattice has a very particular behavior (this particular behavior is not shared with generic posets).

In this article, we continue to investigate the set of intervals of the Tamari lattices. We use the theory of interval-posets introduced by Châtel and Pons in [CP15] in order to study two families of intervals. As intervals of the Tamari lattice, they seem to have a rather complicated and unnatural description. However, they have a very simple description in terms of interval-posets avoiding specific configurations.

The author has been supported by the IDEX BMM/PN/AM/N^{o} 2016-096c.

In the first part of the article, we consider the family appearing as images of noncrossing trees in the dendriform operad. These objects were introduced by Chapoton in [Cha07], and it was proved in [CHNT08] that they are intervals in the Tamari lattice. In Theorem 3.6, we complete this result by giving a precise description of these intervals in terms of interval-posets. This description is used in another article, providing a proof of Conjecture 3.1 of [Cha12] (see [Rog18] for more details). By construction, these intervals are in bijection with the non-crossing trees. In particular, in the Tamari lattice of size n, there are \frac{1}{2n+1} \binom{3n}{n} such intervals. We call them exceptional because they are also in bijection with the set of exceptional sequences (up to an equivalence relation) in the bounded derived category of a linearly oriented quiver of type A (see [Ara13] and [Cha16, Section 3] for more information). We would need to introduce too many algebraic objects to really explain what we have in mind here, but we expect this relation with the exceptional sequences to be much more than a bijection.

At an elementary level, the exceptional intervals turn out to have another nice description in terms of non-crossing partitions. It is well-known that the Tamari lattice is a refinement of the poset of non-crossing partitions. More precisely, if NC_{n} denotes the poset of non-crossing partitions of size n, then there is an increasing bijection ϕ : NC_{n} → Tam_{n} (a bijective homomorphism of posets). In Theorem 3.11, we prove that an interval of Tam_{n} is of the form [ϕ(π_{1}), ϕ(π_{2})] for an interval [π_{1}, π_{2}] of noncrossing partitions if and only if it is exceptional.

In the second part of the article, we consider the family of new intervals of the Tamari lattices. It was shown by Chapoton that there is a structure of operad on the set of intervals of the Tamari lattice (see [Cha17] for more details). The new intervals are exactly the intervals that cannot be obtained as compositions of smaller intervals. There is also a nice formula for the number of such intervals:

number of new intervals in Tam_{n} = 3 · \frac{2^{n−2}(2n − 2)!}{(n − 1)!(n + 1)!}.

In Section 4, we find the description of the interval-poset corresponding to a new interval and we deduce an intrinsic characterization of these intervals. Our main tool is what we call the raise of an interval-poset. This operation increases the size of an interval-poset by 1, and shifts by 1 all the increasing relations of the poset. After shifting the increasing relations by 1, the result is not necessarily a poset since the new increasing relations may contradict the decreasing ones. In order to avoid this problem, we introduce the family of modern interval-posets and show that they are exactly the interval-posets for which the raise is also an interval-poset. Then we prove that an interval is new if and only if its interval-poset is the raise of a modern interval-poset. In terms of binary trees, the raise sends an interval [S_{1}, T_{1}] to the interval [S, T] where S (respectively T) is obtained by grafting the root of S_{1} (respectively T_{1}) on the first (respectively second) leaf of the unique binary tree of size 1 denoted by Y.

In the last section, we consider the interval-posets for which all the successive raises are interval-posets. We call them infinitely modern. It seems that this family of intervals has not been considered before. Using a double statistic on the set of interval-posets, we recover the triangular decomposition of the Fuss–Catalan number \frac{1}{2n+1} \binom{3n}{n} introduced by Aval in [Ava08]. As corollary, we prove in Theorem 5.7 that there are as many infinitely modern interval-posets of size n as there are ternary trees with n inner vertices. Acknowledgement. This work was done when I was a postdoc at the University of Strasbourg and I am grateful to Frédéric Chapoton for introducing me to this subject, for his support, his comments and the many things he taught me. I am also grateful to Camille Combe for the many discussions about the last part of this article. I am very grateful to the referee for the careful reading of this paper.

2. Interval-posets, intervals of the Tamari lattices and conventions

In this section, we recall the construction of interval-posets of Châtel and Pons introduced in [CP15] and we recall that they are in bijection with the intervals of the Tamari lattice. One should note that this bijection is not canonical. More precisely, it depends on the various choices that one has to make in order to define the Tamari lattices as partial orders on sets of binary trees. This is why we start by carefully stating our conventions.

Let n ∈ ℕ. A (planar) binary tree of size n is a graph embedded in the plane which is a tree, has n vertices with valence 3, n + 2 vertices with valence 1 and a distinguished univalent vertex called the root. The other vertices of valence 1 are called the leaves of the tree. For the rest of the paper, when we speak about vertices of the tree, we have in mind the trivalent vertices. The planar binary trees are pictured with their root at the bottom and their leaves at the top.

With this fixed convention, we can speak about left and right children of a vertex of a binary tree T. For us the child of a vertex is connected to his parent by a single edge. A descendant is a child, grandchild, great-grandchild, and so on. If v is a vertex of T, we let T_{1} (respectively T_{2}) be the subtree with root the left child (respectively right child) of v. We say that T_{1} (respectively T_{2}) is the left subtree (respectively right subtree) of v.

Let Tam_{n} be the set of all binary trees with n vertices. It is well-known that the cardinality of this set is the Catalan number c_{n} = \frac{1}{n+1} \binom{2n}{n}.

There is a partial order relation on Tam_{n} which was introduced by Tamari in [Tam62]. It is defined as the transitive closure of the following covering relations. A tree T is covered by a tree S if they only differ in some neighborhood of an edge by replacing the configuration in T by the configuration in S. The poset Tam_{n} is known to be a lattice.

A binary search tree is a binary tree labeled by integers such that, if a vertex x is labeled by k, then the vertices of the left subtree (respectively right subtree) of x are labeled by integers less than or equal (respectively superior) to k.

If T is a binary tree with n vertices, there is a unique labeling of the vertices by each of the integers 1, 2, …, n that makes it a binary search tree. This procedure is sometimes called the in-order traversal of the tree or simply as the in-order algorithm (recursively visit left subtree, root and right subtree). The first vertex visited by the algorithm is labeled by 1, the second by 2 and so on. See figure 1 for an example. Since this labeling is canonical, we will allow ourself to identify vertices with their label.

Using this labeling, a binary tree T with n vertices induces a partial order relation ◁ on the set {1, 2, …, n} by setting i ◁ j if and only if the vertex labeled by i is in the subtree with root j.

When (P, ◁) is a partial order on the set {1, 2, …, n}, one can use the natural total ordering of the integers 1, 2, …, n, which we denote by <, to split the relations ◁ in two families. Let a, b be two integers with 1 ⩽ a < b ⩽ n. If a ◁ b we say that the relation is increasing. On the other hand, if b◁a, we say that the relation is decreasing. We denote the sets of decreasing and increasing relations of P by Dec(P) and Inc(P), respectively.

There is a particularly nice way to draw such a poset (P, ◁). If a relation i ◁ j is increasing, draw a (red) arrow from i to j under the integers i, i + 1, …, j. If there is a decreasing relation j ◁ i draw a (blue) arrow from j to i over the integers j, j − 1, …, i. See Figure 1 for an example.

5 3 1 2 4 8 6 7

1 2 3 4 5 6 7 8

Figure 1. On the left, an example of the labeling of the vertices of a binary tree by calling the ‘in-order’ algorithm. On the right, the poset induced by the tree.

We have a useful characterization due to Châtel, Pilaud and Pons [CPP17] of the partial order of the Tamari lattice in terms of increasing or decreasing relations.

Proposition 2.1. Let T_{1} and T_{2} be two binary trees. The following are equivalent. (1) T_{1} ⩽ T_{2} in the Tamari lattice.

(2) Dec(T_{1}) ⊆ Dec(T_{2}).

(3) Inc(T_{2}) ⊆ Inc(T_{1}).

Proof. See [CPP17, Proposition 40 and Remark 52]. □

Definition 2.2. An interval-poset (P, ◁) is a poset over the integers 1, 2, …, n such that

(1) If a ◁ c and a < c, then, for all integers b such that a < b < c, we have b ◁ c.

(2) If c ◁ a and a < c, then, for all integers b such that a < b < c, we have b ◁ a.

The conditions (1) and (2) of this definition will be referred to as the interval-poset condition. The integer n in the definition is called the size of the interval-poset.

Remark 2.3. Let (P, ◁) be an interval-poset. If x ◁ y is an increasing relation (respectively a decreasing relation), then by the interval-poset condition there is a relation y − 1 ◁ y (respectively x + 1 ◁ x). The existence of such ‘small’ relations will be crucial in most of our proofs on modern interval-posets.

Theorem 2.4 (Châtel, Pons). Let n ∈ ℕ. There is a bijection between the set of intervals in Tam_{n} and the set of interval-posets of size n.

Proof. This is Theorem 2.8 of [CP15].

Since we need to use the explicit version of the theorem, let us recall the two inverse bijections. if [S, T] is an interval in Tam_{n}, we construct an interval-poset as follows. The trees S and T can be seen as binary search trees and they induce two partial order relations ◁_{S} and ◁_{T}. Let P = {1, 2, …, n}. There is a binary relation ◁ on P given by the disjoint union of the decreasing relations of S and the increasing relations of T. Then it is proved in [CP15] that (P, ◁) is an interval-poset.

Conversely, we assume that (P, ◁) is an interval-poset of size n. Let D be the poset obtained by only keeping the decreasing relations of P. Similarly, let I be the poset obtained by only keeping the increasing relations. By [CP15, Lemma 2.5], the Hasse diagrams of these two posets are two forests. By adding a common root to the trees of each of these forests, we obtained two planar trees. Now, we produce binary trees starting from these planar trees.

For I we recursively produce a binary tree T by using the rule: right sibling becomes right child and child becomes left child.

For D we recursively produce a binary tree S by using the rule: left sibling becomes left child and child becomes right child.

The tree S is smaller than T for the order of the Tamari lattice, so we have an interval [S, T].

These two correspondences are sometimes called the Knuth correspondences or the natural correspondences (see [dBM67] or [HPT64] for more details).

It was proved in [CP15, Theorem 2.8] that these two constructions give two bijections inverse of each other. □

Finally, we need a useful translation in the world of interval-posets of the usual left/right symmetry of trees.

Lemma 2.5. Let [S, T] be an interval in Tam_{n} and P be its corresponding intervalposet. The interval-poset corresponding to the interval obtained by taking the left/right symmetry of S and T is the interval-poset Q of size n defined by a ◁_{Q} b ⇔ n + 1 − a ◁_{P} n + 1 − b.

3. Exceptional intervals of the Tamari lattice

In [Cha07], Chapoton introduced an operad NCP of non-crossing plants. A noncrossing plant is a generalization of a non-crossing tree. Since we will not work with them, we refer the reader to the original article for a precise definition. We will only use the fact that non-crossing trees are particular examples of non-crossing plants. It was proved that this operad (in the category of sets) is a sub-operad of Dend, the Dendriform operad. Then it was proved in [CHNT08] that the image of a non-crossing tree in Dend is of the form ∑_{t∈I} t where I is an interval in the Tamari lattice. An interval that appears as such an image of a non-crossing tree is called exceptional. In this section, we reprove and make precise this result by giving an explicit description of the exceptional intervals in terms of the interval-posets. Since they are in bijection with the non-crossing trees, the number of exceptional intervals in the Tamari lattice of size n is \frac{1}{2n+1} \binom{3n}{n}.

There is another well known family of intervals of the Tamari lattice counted by these numbers: it is classical that the Tamari order is a refinement of the usual partial ordering of the non-crossing partitions (see [BB09, Section 2] for more details). This implies that an interval in the poset of non-crossing partitions can naturally be seen as an interval in the Tamari lattice. By a result of Kreweras [Kre72] or a bijection of Edelman [Ede82], the number of intervals of non-crossing partitions of size n is \frac{1}{2n+1} \binom{3n}{n}. At the end of this section, we show that this family coincides with the family of exceptional intervals.

3.1. Exceptional intervals and non-crossing trees. A non-crossing tree in the regular n+1-gon is a set of edges between the vertices of the polygon with the following properties

• edges do not cross pairwise,

• any two vertices are connected by a sequence of edges,

• There is no loop made of edges.

The boundary edges are allowed in the set. It is classical that the number of non-crossing trees in the regular n + 1-gon is \frac{1}{2n+1} \binom{3n}{n} (see e.g. [DP93, Theorem 3.10]).

Given two non-crossing trees f and g in regular polygons and a side i of the regular polygon containing f, one can define the composition f ∘_{i} g in the grafting of the polygons containing f and g. This is defined as the union of the two trees, with some modifications along the grafting diagonal. If the diagonal is present in both f and g, then it is kept in f ∘_{i} g. If it is present in exactly one of the two trees, then it is not kept in f ∘_{i} g. Otherwise, the result is not a non-crossing tree. One ‘denominator’ diagonal is added and the result is a non-crossing plant. We refer to [Cha07, Section 5.2] for more details.

It was shown in [CHNT08, Section 5.1] that one can construct a poset from a noncrossing tree. Let us recall this construction.

Let T be a non-crossing tree in a based regular n + 1-gon. Here by based, we mean that we choose one side of the polygon and call it the base. We can label the edges of the n + 1-gon by assigning the number 0 to the base, and then successively assigning the numbers 1 to n to the edges in clockwise order. If an edge of T is a boundary edge we assign to it the number of the boundary edge. Otherwise, the label of the edge of the non-crossing tree is the number of the unique open boundary edge that it separates from the base. Then we set i ◁_{T} j if the edge i is separated from the base by the edge j. An example is given in Figure 2.

11 10 2 1 8 7 6 5 4 3 9 0  3 9 6 4 5 2 10 11 1 8 7

1 3 10 2 6 8 5 7 9 4 11

Figure 2. On the left, an example of a non-crossing tree in a 12-gon and in the center the induced labeling of the non-crossing tree. On the right, the Hasse diagram of the corresponding poset where the maximal elements are 1 and 11.

Lemma 3.1. Let T be a non-crossing tree in a based regular n + 1-gon. Then the poset ([1, n], ◁_{T}) is an interval-poset that we denote by P_{T}.

Proof. We label the boundary edges of a based regular n + 1-gon as above. We use the notation [i_{1}, i_{2}] where i_{1} ⩽ i_{2} for the edge that goes from the left side of the boundary edge i_{1} to the right side of the boundary edge i_{2}. For example, in Figure 2, the edge with label 6 corresponds to [4, 6] and the edge labeled by 4 corresponds to [4, 4]. Note that, by construction of our labeling, the edge [i_{1}, i_{2}] labeled by i separates the boundary edge i of the regular n + 1-gon from the base. In particular this implies that 1 ⩽ i_{1} ⩽ i and i ⩽ i_{2} ⩽ n.

Let us check that the poset P_{T} = ([1, n], ◁_{T}) is an interval-poset. Let 0 < i < j < k ⩽ n be such that i ◁ k. This means that the edge [i_{1}, i_{2}] labeled by i is separated from the base by the edge [k_{1}, k_{2}] labeled by k. Since, k separates i from the base and T is a non-crossing tree, we see that the only possibility is to have:

k_{1} ⩽ i_{1} ⩽ i ⩽ i_{2} ⩽ k ⩽ k_{2}.

The boundary edge j is between i and k, so either it is before i_{2} or after. Since T is a non-crossing tree the edge j cannot cross the edges i and k. So, in the first case k and i separate j from the base, and in the second case k separates j from the base. In particular, we have j ◁ k. See Figure 3 for an illustration where the letter j is used for the first case and the letter J for the second. The case where k ◁ i is similar and is illustrated in the right part of Figure 3. □

\begin{matrix}0 \\ k_{1} \\ i \\ i_{1} \\ i_{2} \\ i \\ k \\ k_{2} \\ k \\ j \\ j \\ J \\ J \end{matrix}  \begin{matrix}0 \\ i \\ i_{1} \\ k \\ i_{2} \\ i \\ k_{2} \\ k_{1} \\ k \\ J \\ J \\ j \\ j \end{matrix}

Figure 3. On the left the case i < j < k and i ◁ k. On the right i < j < k and k ◁ i.

Lemma 3.2. Let T be a non-crossing tree in a based regular n+1-gon. Then the Hasse diagram^{1} of the interval-poset P_{T} = ([1, n], ◁_{T}) does not contain any configuration of the form y → z and y → x where x < y < z.

Proof. Let us assume that we have integers x < y < z such that y ◁ x and y ◁ z. This means that the edge x = [x_{1}, x_{2}] separates y = [y_{1}, y_{2}] from the base. As in the proof of Lemma 3.1, this implies that

x_{1} ⩽ y_{1} ⩽ y_{2} ⩽ x_{2}.

Similarly, the edge z = [z_{1}, z_{2}] separates y from the base, so we have

z_{1} ⩽ y_{1} ⩽ y_{2} ⩽ z_{2}.

Since T is a non-crossing tree, if x_{1} ⩽ z_{1}, then necessarily x_{2} ⩾ z_{2}. In this case the edge x separates the edge z from the base and we have z ◁ x. If z_{1} ⩽ x_{1}, then x_{2} ⩽ z_{2} and we have x ◁ z. In both cases, we see that one of two relations y ◁ x and y ◁ z is not a cover relation. In particular the configuration y → z and y → x does not appear in the Hasse diagram of the poset. □

Definition 3.3. An interval-poset whose Hasse diagram does not contain any configuration of the form y → z and y → x where x < y < z is called an exceptional interval-poset.

If (P, ◁) is an interval-poset over the integers [1, n], we can construct a graph G_{P} in a based regular n + 1-gon by using the following procedure which is nothing but a reformulation in terms of interval-posets of the construction explained in [CHNT08, Section 5.1]. Let us start by labeling the boundary edges of the polygon as above. Then, for an integer v, consider the poset {x ∈ [1, n] : x ◁ v}. It has a minimal element (for the usual order relation <) v_{1} and a maximal element v_{2}. We associate to v the edge in the polygon from the left side of v_{1} to the right side of v_{2}.

1We use the symbol y → z to indicate the presence of an arrow from y to z in the Hasse quiver of the poset P_{T}. This means that y ◁_{T} z is a cover relation.

Lemma 3.4. If (P, ◁) is an exceptional interval-poset of size n, then the graph G_{P} is a non-crossing tree. Proof. Let (P, ◁) be an exceptional interval-poset. If k is a maximal element of P (for the relation ◁), then the set I_{k} := {i ∈ P : i ◁ k} is an interval because P is an interval-poset. Moreover, if k and k′ are two maximal elements of P, then the intervals I_{k} and I_{k′} are disjoint. Indeed, let z ∈ P such that z ◁ k and z ◁ k′. We can assume that k ⩽ k′. If z ⩽ k ⩽ k′, then the interval-poset condition implies that k ◁ k′ and by maximality k = k′. Similarly, if k ⩽ k′ ⩽ z, the interval-poset condition implies that k′ ◁ k and by maximality, we have k = k′. Now, if k < z < k′, by maximality of k and k′, we have a configuration of the form z → k and z → k′ in the Hasse diagram. This is not possible since the interval-poset P is exceptional. In other words, the exceptional interval-posets are nothing but the non-interleaving forests introduced in [CHNT08, Section 5.1]. In particular, the result is a direct consequence of [CHNT08, Lemma 5.2]. We sketch it for the convenience of the reader.

It is easy to see that the poset P has a unique maximal element if and only if the base of the polygon is in the graph G_{P}. In this case, we say that G_{P} is based.

The interval-poset P is a disjoint union of s interval-posets I_{k_{1}}, …, I_{k_{n}} where k_{i} runs through the maximal elements of P. If there is more than one maximal element, by induction on the size of the poset we see that the graph G_{I_{k_{i}}} is a based non-crossing tree. Now, it is easy to see that the graph G_{P} is obtained by gluing the base of all the non-crossing trees G_{I_{k_{i}}} on the boundary of a regular s + 1-gon. More formally, in terms of NCP-operads, we have G_{p} = S ∘_{1} G_{I_{k_{1}}} ∘_{2} ⋯ ∘_{s} G_{I_{ks}}, where S is the non-crossing tree with s edges consisting of all boundary edges of the regular s + 1-gon, except for the base.

If there is only one maximal element m in P, then G_{P} is based. The case where P has only two elements is elementary and can be checked by listing all the possible cases. If |P | ⩾ 3, let P_{1} = {i ∈ P : i < m} and P_{2} = {i ∈ P : m < i}. Clearly P_{1} and P_{2} are two disjoint interval-posets of size smaller than |P |. By induction, the graphs I_{P_{1}} and I_{P_{2}} are non-crossing trees. Let U be the non-crossing tree in a based square consisting of the base and the two adjacent boundary edges. It is now easy to see that G_{P} = (U ∘_{1} I_{P_{1}}) ∘_{3} I_{P_{2}}. In particular, G_{P} is a non-crossing tree. □ Proposition 3.5. The map sending a non-crossing tree T to the interval-poset P_{T} and the map sending an exceptional interval-poset P to the non-crossing tree T_{P} are two bijections inverse of each other between the set of non-crossing trees in a based regular n + 1-gon and the set of exceptional interval-posets of size n. Proof. The result is proved by induction. The cases n = 0, 1 and 2 can be easily checked by hand. Let n ⩾ 3. If T is a non-crossing tree, we denote the exceptional intervalposet obtained in Lemma 3.1 by P_{T}. If P is an exceptional interval-poset, we denote the non-crossing tree obtained in Lemma 3.4 by T_{P}. Let S be the non-crossing tree with s edges consisting of all boundary edges of the regular s + 1-gon, except for the base. Let T_{1}, ⋯, T_{s} be s based non-crossing trees. Let T = S ∘_{1} T_{1} ∘_{2} ⋯ ∘_{s} T_{s}. The edges of T_{i} (viewed as edges in T) are separated from the base by the base of T_{i}, and the edges of T_{i} are not separated from the base by any edge of T_{j} for i ≠ j. This implies that P_{T} is the disjoint union of the posets P_{T_{i}} and all these posets have a unique maximal element.

If the poset P has more than one maximal element, we have P = P_{1} ⊔ ⋯ ⊔ P_{s} where P_{i} is the set of elements smaller than the i-th maximal element. By the proof of Lemma 3.4, the corresponding non-crossing tree T_{P} is of the form S ∘_{1} I_{P_{1}} ∘_{2} ⋯ ∘_{s} I_{P_{s}}. By the remark above, the poset corresponding to the tree T_{P} is P_{I_{P_{1}}} ⊔ ⋯ ⊔ P_{I_{Ps}}. Now, by induction we have that P_{T_{P}} = P.

Similarly, if the tree T is not based, it can be written as S ∘_{1} T_{1} ∘_{2} ⋯ ∘_{s} T_{s} where T_{i} are based non-crossing trees. So, we have P_{T} = P_{T_{1}} ⊔ ⋯ ⊔ P_{T_{s}}, and T_{P_{T}} = S ∘_{1} T_{P_{T_{1}}} ∘_{2} ⋯ ∘_{s} T_{P_{Ts}}. One more time, an induction gives the result.

Let U be the non-crossing tree in a based square consisting of the base and the two adjacent boundary edges. If T is a based non-crossing tree, there are two non-crossing trees T_{1} and T_{2} such that T = U ∘_{1} T_{1} ∘_{3} T_{2}. It is easy to see that the poset P_{T} is of the form P_{1} ⊔ {m} ⊔ P_{2}, where m is the labeling of the base of T, P_{1} is the subset consisting of the elements smaller (for <) than m and P_{2} is the set of elements larger than m. Since m is the label of the basis it is the unique maximal element of P_{T}. Using this decomposition of based non-crossing trees, and exceptional interval-posets with a unique maximal element, it is easy to prove by induction that T_{P_{T}} = T and P_{T_{P}} = P. □

By [Cha07, Theorem 5.3], there is an injective morphism of operads (in the category of sets) Θ from the operad of non-crossing plants NCP and the dendriform operad Dend. Using exceptional interval-posets we describe the image of a non-crossing tree by Θ.

Theorem 3.6. Let T be a non-crossing tree. Let the image of T in Dend be ∑_{t∈I} t. Then the set of trees I is the interval of the Tamari lattice corresponding to the exceptional interval-poset P_{T}.

Proof. Since exceptional interval-posets are the same as non-interleaving forests, the result follows from a reformulation of [CHNT08, Section 5.1] and a description of intervalposets in terms of linear extensions due to Châtel and Pons. We sketch the arguments.

Let ϕ : NCP → Mould be the injection defined in [Cha07, Section 5.2] or in [CHNT08, Section 5.2]. Let ψ : Dend → Mould be the injection defined in [Cha07, Theorem 3.1]. Since the maps Θ, ϕ and ψ are morphisms of operads and since the diagram is commutative on the elements of NCP(2), the following diagram is commutative:

\xymatrix{NCP \ar[dr]^{ϕ} \ar[rr]^{Θ} &  & Dend \ar[dl]_{ψ} \\  & Mould}

Moreover, all the morphisms are injective.

Let T be a non-crossing tree. By [CHNT08, Lemma 5.3], we have ϕ(T) = ∑_{σ∈L(P_{T})} f_{σ} where P_{T} is the exceptional interval-poset that corresponds to P and L(P_{T}) is the set of all linear extensions of P_{T} and if σ ∈ S_{n}, then f_{σ} is the fraction defined by

f_{σ}(u_{1}, …, u_{n}) = \frac{1}{u_{σ(1)} · (u_{σ(1)} + u_{σ(2)}) · · · · · (u_{σ(1)} + ⋯ + u_{σ(n)})}.

For σ, σ′ ∈ S_{n} the multi-residue ∮_{σ} (see [Cha07, Proposition 3.3]) has the property that ∮_{σ} f_{σ′} ≠ 0 if and only if σ = σ′. So, for σ ∈ S_{n}, we have ∮_{σ} ϕ(P_{T}) ≠ 0 if and only if σ is a linear extension of P_{T}.

On the other hand, by [Cha07, Proposition 3.3], if T is a binary tree, we have ∮_{σ} ψ(T) ≠ 0 if and only if σ is a linear extension of the poset induced by the tree T. As a consequence, I is the set of trees whose linear extensions are exactly the linear extensions of P_{T}. Now, by [CP15, Theorem 2.8], this implies that I is an interval of the Tamari lattice, and that P_{T} is the interval-poset corresponding to I. □

3.2. Non-crossing partitions. A partition (b_{1}, …, b_{m}) of {1, 2, …, n} is non-crossing if there do not exist 1 ⩽ i < j < k < l ⩽ n such that i, k ∈ b_{s} and j, l ∈ b_{t} for s ≠ t. Let NC_{n} be the set of all non-crossing partitions of {1, 2, …, n}. It is well-known that the cardinality of this set is the Catalan number c_{n}. The refinement of partitions induces a structure of partial order on NC_{n} which is known to be a lattice (see [Kre72] for more details).

It is also classical that the Tamari lattice is a refinement of the poset of non-crossing partitions. In general, it is convenient to realize these posets on the set of Dyck paths via well chosen bijections in order to compare them (see [BB09, Section 2] for more details). Here, in order to simplify the proofs, we realize the poset of non-crossing partitions on the Tamari lattice, using a bijection similar to a bijection introduced by Edelman [Ede82].

If T is a (planar) binary tree, we can view it as a binary search tree using the in-order algorithm (this is why our bijection is not the same as Edelman’s bijection: he labeled the trees with pre-order traversal). Then the partition π_{T} associated to the tree T is the finest partition of {1, 2, …, n} such that, if j is right child of i, then i and j are in the same block. For example, the partition corresponding to the binary tree of Figure 1 is {1, 3, 4}, {2}, {5, 8}, {6, 7}.

Lemma 3.7. Let T be a binary tree and π_{T} its corresponding partition. Then π_{T} is a non-crossing partition.

Proof. Let i < j < k < l such that i, k are in a block b_{1} and j, l are in a block b_{2}. The vertex of T labeled by k is a right descendant of the vertex labeled by i.

Since the in-order algorithm goes first through left subtrees, then it visits the root and finally goes through right subtrees, the vertex j is in the right subtree of i. Since l and i are in the same block, the vertex l is a right-descendant of i. Since k < l, the vertex k is in the right subtree of j. The only possibility is to have that j, k and l are right descendants of i. So, they are in the same block. □

Conversely, if π = (b_{1}, …, b_{m}) is a non-crossing partition of {1, 2, …, n} we will construct a binary search tree associated to this partition. We assume that the blocks of the partition are totally ordered in such a way that min(b_{1}) < min(b_{2}) < ⋯ < min(b_{n}) and the elements of the blocks are ordered by the natural ordering of the integers. The tree T_{π} is constructed in two steps:

(1) To each block b_{i} is associated a binary tree T_{i} with root min(b_{i}) and if y is the successor of x in the block b_{i}, then y is the right child of x.

(2) If T_{i} is a tree constructed in the first step, let m_{i} be the vertex with maximal labeling in the tree. We construct inductively a tree T_{π} by grafting the root of T_{i} as the left child of the vertex labeled by m_{i} + 1. For an example see Figure 4.

1 2 3 4 5 6 7 8  1 2 7 3 4 5 6 8  8 3 1 2 4 5 6 7

Figure 4. An example of the two steps of the construction of a binary tree associated to a non-crossing partition.

Lemma 3.8. Let π be a non-crossing partition of {1, 2, …, n} and T_{π} the corresponding binary tree. Then T_{π} is a binary search tree.

Proof. Let s be the label of a vertex. If x is a right descendant of s, then by construction s and x are in the same block and we have s < x. If y is the left child of x, then the maximal element of the block of y is x − 1. If z is in the block of y, then we have s < z < x because s and x are in the same block, y and x − 1 are in the same block, and the partitions are non-crossing. Using these remarks, it is easy to check that, if z is in the right subtree of s, then s < z. Similarly, it is easy to check that the elements of the left subtree of s are labeled by integers strictly smaller than s. □

Proposition 3.9. The map sending a binary tree T to the non-crossing partition π_{T} and the map sending a partition π to the binary tree T_{π} are two bijections inverse of each other.

Proof. By construction of the tree T, the minimal elements of the blocks are the vertices that are a left child of another vertex (i.e. they have a right parent) and their left descendants are the elements of their block. So, the partition π_{T_{π}}is equal to π. Since there is a unique way to turn a binary tree into a binary search tree of size n using exactly once each of the integers 1, 2, …, n, we have T_{π_{T}} = T. □

We can now be more precise about the fact that the Tamari lattice is a refinement of the lattice of non-crossing partitions.

Lemma 3.10. Let π_{1} and π_{2} be two non-crossing partitions of {1, 2, …, n}. If π_{1} ⩽ π_{2} in the poset of non-crossing partitions, then T_{π_{1}} ⩽ T_{π_{2}} in the Tamari lattice.

Proof. Using Proposition 2.1, it is enough to show that the decreasing relations of T_{π_{1}} are decreasing relations of T_{π_{2}}.

Let i < j such that j ◁_{T_{π_{1}}} i. In other words, the vertex j is in the subtree with root i. Since i < j, this implies that j is in the right subtree of i. Let x be the right descendant of i such that j is in its left subtree (if j is a right descendant of i, we have x = j). Since the tree T_{π_{1}} is a binary search tree, this implies that i < j < x. Moreover, by construction of T_{π_{1}}, the elements i and x are in the same block. Since the partial order relation for non-crossing partitions is given by merging blocks, in the partition π_{2} the elements i and x are also in the same block. In other words, the element x is in the right subtree of i in T_{π_{2}}. Since i < j < x, this implies that j is also in the right subtree of i, so we have j ◁_{T_{π_{2}}} i. □

We can now characterize the intervals of the Tamari lattice that come from intervals in the lattice of non-crossing partitions.

Theorem 3.11. Let n ∈ ℕ. Let I be an interval of the Tamari lattice Tam_{n}. Then there is an interval of non-crossing partitions [π_{1}, π_{2}] such that I = [T_{π_{1}}, T_{π_{2}}] if and only if the interval-poset corresponding to I is exceptional.

Proof. Let π_{1} ⩽ π_{2} in NC_{n}. Let I = [T_{π_{1}}, T_{π_{2}}] be the corresponding interval in Tam_{n} and P be the corresponding interval-poset. Let x < y < z such that we have a relation y ◁ x and y ◁ z.

First assume that y◁x is a cover relation. We will show that this implies the existence of a relation x ◁ z. This last relation implies that y ◁ z is not a cover relation. We can assume that y is the maximal element such that y ◁ x is a cover relation and y ◁ z. Let t◁x be a cover relation. If z ⩽ t, then by the interval-poset condition we have a relation z ◁ x and the relation y ◁ x becomes the composite of y ◁ z and z ◁ x contradicting the hypothesis. So, the maximal element t with a cover relation t ◁ x is an element of [y, z[. By the interval-poset condition, we have t ◁ x, so by maximality we have t = y.

In other terms, in the decreasing forest of P, the element y is the right-most child of x. So, using the bijection of Theorem 2.4 we see that y is the right child of x in the tree T_{π_{1}}. In terms of non-crossing partitions, this means that y is the successor of x in its block. Since the partial order relation for the non-crossing partitions is given by merging of blocks, we see that y is still in the block of x in π_{2}. This implies that y is also in the right subtree of x in T_{π_{2}}.

In the increasing forest of P we have the relation y ◁ z which means that y is in the left subtree of z. Since y is a right descendant of x, this implies that x is in the right subtree of z. Using one more time the bijection of Theorem 2.4, we have an increasing relation x ◁ z.

We only sketch the proof when y◁z is a cover relation. We can assume y to be minimal for this property. This implies that y is the left-most child of z in the increasing forest of P. So y is the left child of z in T_{π_{2}}. By the argument of Lemma 3.10, an increasing relation of T_{π_{2}} is also an increasing relation of T_{π_{1}}. In particular, y is in the left subtree of z in T_{π_{1}}. The relation y ◁ x in P implies that y is in the right subtree of x. Since it is also in the left subtree of z, this implies that z is in the right subtree of x. So we have the relation z ◁ x in P.

We have proved that the interval-posets of the intervals of the Tamari lattice coming from intervals of non-crossing partitions are exceptional. The result follows from the fact that the number of exceptional interval-posets is the number of intervals in the poset of non-crossing partitions. □

4. New intervals and modern interval-posets

In this section, we introduce the notion of modern interval-posets and we show that the modern interval-posets of size n are in bijection with the new intervals of Tam_{n+1}. Note that there is a shift of the size by 1.

4.1. New intervals of the Tamari lattice. From now on, we will always assume that the leaves of the binary trees of Tam_{n} are labeled from left to right by the integers 1, 2, …, n + 1. Let T ∈ Tam_{n} and S ∈ Tam_{k}. Let 1 ⩽ i ⩽ n + 1. The binary tree T ∘_{i} S is the tree of size k + n obtained by grafting the root of S on the i-th leaf of T. If [S_{1}, T_{1}] is an interval of Tam_{n} and [S_{2}, T_{2}] is an interval of Tam_{k}, and 1 ⩽ i ⩽ n + 1, then the tree S_{1} ∘_{i} S_{2} is smaller than T_{1} ∘_{i} T_{2}. We say that the interval [S_{1} ∘_{i} S_{2}, T_{1} ∘_{i} T_{2}] is the i-th grafting of [S_{2}, T_{2}] on [S_{1}, T_{1}], and we denote it by [S_{1}, T_{1}] ∘_{i} [S_{2}, T_{2}].

Definition 4.1. An interval of Tam_{n} is called new if it cannot be obtained as the grafting of two intervals.

The new intervals were introduced by Chapoton in [Cha17].

Lemma 4.2 (Chapoton). An interval [S, T] of Tam_{n} is new if and only if there is no pair of subtrees (A, B) of S and T whose leaves are labeled by the same interval [i, j] ≠ [1, n + 1].

Proof. If there is a subtree A of S whose leaves are labeled by [i, j] and a subtree B of T whose leaves are also labeled by [i, j], then S is of the form S_{1} ∘_{i} A and T is of the form T_{1} ∘_{i} B, so the interval is not new. Conversely, if the interval is not new, then [S, T] = [S_{1}, T_{1}] ∘_{i} [A, B]. So there is a pair of subtrees (A, B) of S and T whose leaves are labeled by the same interval [i, i + size(S)]. □

With this criterion, it is easy to see that the new intervals of Tam_{n} have a nice shape.

Lemma 4.3. Let n ∈ ℕ^{∗}. Let [S, T] be a new interval of Tam_{n}. Then there are two binary trees S_{1} and T_{1} in Tam_{n−1} such that S = Y ∘_{1} S_{1} and T = Y ∘_{2} T_{1} where Y is the unique binary tree of size 1.

Proof. The covering relation for the Tamari lattice is the left rotation. So, if there is a vertex on the right side of S, it will be fixed by any left rotation, so it will also appear at the same place in the tree T. Similarly, if there is a vertex on the left side of T it must also be at the same place in S. So the subtrees with root s have the same interval of leaves. Using Lemma 4.2, we see that the interval [S, T] is not new in both cases. □

However, it is easy to find intervals with this nice shape but which are not new. We will characterize the new intervals in this family in Theorem 4.18.

4.2. Raising and lowering of interval-posets.

Definition 4.4. Let n ∈ ℕ. An interval-poset of size n is modern if it does not contain any configuration of the form x ◁ y and z ◁ y with x < y < z.

Let us remark that, unlike Definition 3.3, the forbidden configuration here involves all the relations and not only the relations in the Hasse diagram of the poset.

Let us introduce the raise of a set with a reflexive binary relation^{2}. If P = {1, 2, …, n} is a set with a reflexive binary relation ◁, then (Ra(P), ◁_{R}) is the set {1, 2, …, n + 1} with the binary relation ◁_{R} defined by keeping all decreasing relations of P and shifting all the increasing relations of P by 1. More precisely, the relation ◁_{R} is reflexive and for x < y ⩽ n, we have y ◁_{R} x if and only if y ◁ x. For 1 < x < y ⩽ n + 1 we have x ◁_{R} y if and only if x − 1 ◁ y − 1. For an example, see Figure 5.

\begin{aligned}& 1 2 3 & \begin{matrix}• \\ • \\ • \end{matrix} & & \begin{matrix}• \\ • \\ • \end{matrix} \\ 1 2 3 4 & & & \begin{matrix}• \\ • \\ • \\ • \end{matrix} & & \begin{matrix}• \\ • \\ • \\ • \end{matrix} \end{aligned}

Figure 5. On the top an interval-poset of size 3 and its corresponding interval of Tam_{3}. On the bottom, its raise and the corresponding interval of Tam_{4}.

Lemma 4.5. Let (P, ◁) be an interval-poset of size n. Then the raise of P is an interval-poset if and only if P is modern.

Proof. Since the raise only shifts the increasing relations of P, it is clear that the relation ◁_{R} satisfies the two conditions of interval-poset.

If the interval-poset P is not modern, there is a configuration of the form x ◁ y and z ◁ y with x < y < z. The condition of interval-poset implies the existence of the two relations y − 1 ◁ y and y + 1 ◁ y. It is clear that the raise of P is not a poset since we have y ◁_{R} y + 1 and y + 1 ◁_{R} y.

If the interval-poset P is modern, we need to see that Ra(P) is a poset. If we have in Ra(P) two elements x < y such that x ◁_{R} y and y ◁_{R} x, then in P we have y ◁ x and x − 1 ◁ y − 1. Since x − 1 < x ⩽ y − 1, the condition of interval-poset of P implies that we have a relation x ◁ y − 1. Similarly, since x ⩽ y − 1 < y, the interval-poset condition implies that we have a relation y − 1 ◁ x. Since P is a poset, we have x = y − 1, and we see that the relations x ◁_{R} y and y ◁_{R} x come from the relations y − 2 ◁ y − 1 and y ◁ y − 1 in P. In other words, the interval-poset P is not modern.

Let us assume that Ra(P) contains two relations x◁_{R}y and y◁_{R}z but does not contain the relation x ◁_{R} z. Since increasing relations and decreasing relations come from P, it is clear that such a situation implies that one of the two relations is increasing, and the second one is decreasing. If the relation x ◁_{R} y is increasing, there are two possibilities: either z is before x, or z is between x and y. If z is before x the relation y ◁_{R} z and the interval-poset condition imply the existence of a relation x ◁_{R} z. Otherwise, the interval-poset condition implies the existence of a relation z ◁_{R} y, which by the argument above implies that P is not modern. The case where x ◁_{R} y is decreasing is similar. □

2The raise of an interval-poset needs not to be an interval-poset, so in order to be able to take successive raises we need a more general setting.

Definition 4.6. An interval-poset P of size n is called new if it has no increasing relation starting at 1, no decreasing relation starting at n, and no relations of the form i + 1 ◁_{P} j + 1 and j ◁_{P} i for i < j.

Let us define the lowering of an interval-poset (P, ◁) of size n with no increasing relation starting at 1 and no decreasing relation starting at n. This is the poset (Low(P), ◁_{L}) where Low(P) is the set {1, 2, …, n − 1} and the relation ◁_{L} is the relation obtained by keeping the decreasing relations and shifting the increasing relations by −1. More precisely, ◁_{L} is reflexive and for x < y, we have y ◁_{L} x if and only if y ◁ x and x ◁_{L} y if and only if x + 1 ◁ y + 1.

Lemma 4.7. Let P be an interval-poset of size n with no increasing relation starting at 1 and no decreasing relation starting at n. Then the lowering of P is an interval-poset if and only if P is new.

Proof. This is a straightforward checking. □

Lemma 4.8. The raising/lowering operations induce two inverse bijections between the set of modern interval-posets of size n and the set of new interval-posets of size n + 1.

Proof. The only way to have two relations i + 1 ◁_{R} j + 1 and j ◁_{R} i for i < j in Ra(P) is to have i ◁ j and j ◁ i in P, so the raise of a modern interval-poset is new. Similarly, the lowering of a new interval-poset P is modern since the forbidden pattern leads to the existence of relations y − 1 ◁_{L} y and y + 1 ◁_{L} y that must come from y + 1 ◁ y and y ◁ y + 1 in P.

Moreover, it is obvious that the raising and lowering operations are inverse of each other. □

Proposition 4.9. Let [S, T] be an interval of Tam_{n+1}. Let P be its corresponding interval-poset. Then P is new if and only if there is an interval [S_{1}, T_{1}] of Tam_{n} such that S = Y ∘_{1} S_{1} and T = Y ∘_{2} T_{1}.

Proof. First we show that there is no increasing relation starting at 1 in P if and only if there is a tree T_{1} such that T = Y ∘_{2} T_{1}. Using the left/right symmetry and Lemma 2.5 we can deduce that there is no decreasing relation starting at n + 1 in P if and only if there is a tree S_{1} such that S = Y ∘_{1} S_{1}. If there is an increasing relation starting at 1, let x be the maximal element such that we have 1 ◁ x. Then in the forest of increasing relations the first tree has root x and 1 is in this tree. So it is sent by the bijection of Theorem 2.4 to the binary tree T which has a root x and 1 is in its left subtree. This implies that the root of T has a left child and T is not of the form Y ∘_{2} T_{1}. Conversely, if the root of T has a left child, then the vertex labeled by 1 is in the left subtree of T. Let x be the label of the root of T. Then we have an increasing relation 1 ◁ x in P.

If P is new, then by the previous argument S = Y ∘_{1} S_{1} and T = Y ∘_{2} T_{1}. Since P is new, the lowering of P is defined. We will show that the interval corresponding to Low(P) is [S_{1}, T_{1}]. Using the left/right symmetry and Lemma 2.5, it is enough to show that the binary tree corresponding to the decreasing relations of Low(P) is S_{1}. If F denotes the forest of decreasing relations of Low(P), then the decreasing forest of P is F ⊔ {n + 1} where n + 1 is the tree with only one vertex n + 1. So, the tree corresponding to the decreasing relations of Low(P) is the left subtree of the tree of P. In other words, it is the tree S_{1}.

Since Low(P) is an interval-poset, the trees S_{1} and T_{1} obtained by considering the decreasing relations and the increasing relations satisfy S_{1} ⩽ T_{1} in Tam_{n}.

Conversely, we assume that [S_{1}, T_{1}] is an interval of Tam_{n} such that [S, T] is an interval of Tam_{n+1} for S = Y ∘_{1} S_{1} and T = Y ∘_{2} T_{1}. If we turn T into a binary search tree by using the in-order algorithm, it is easy to see that the root of T is labeled by 1 and, if x is the label of a vertex of T_{1}, then this vertex is labeled by 1 + x in T. In other words, the increasing relations of T are the increasing relations of T_{1} shifted by 1. By symmetry, the interval-poset corresponding to [S, T] is the raise of the interval-poset corresponding to [S_{1}, T_{1}]. By Lemma 4.8, the interval-poset corresponding to [S, T] is new. □

4.3. Characterization of the new intervals. This section is devoted to the proof of the following theorem.

Theorem 4.10. An interval of the Tamari lattice is new if and only if the corresponding interval-poset is new.

We are going to prove that the intervals that are not new are exactly the intervals whose interval-poset is not new. As first easy case, we consider intervals that do not have the nice shape of Lemma 4.3.

Lemma 4.11. Let n ∈ ℕ^{∗}. Let [T, S] be an interval of Tam_{n} that is not of the form [Y ∘_{1} S_{1}, Y ∘_{2} T_{1}] for two trees S_{1} and T_{1} of Tam_{n−1}. Then the corresponding intervalposet is not new.

Proof. Assume that the root of the tree S has a right child. Let x be the right-most vertex of S. This is the last right descendant of the root of S. This vertex is the last vertex visited by the in-order algorithm described in Section 2. So it is labeled by n. Let r be the label of the root of S. Then in P we have a relation n ◁ r and the poset is not new. Similarly, if the root of T has a left child, there is an increasing relation in P starting at 1, so the poset is not new. □

Conversely, we have the following assertion.

Lemma 4.12. Let P be an interval-poset. If there is an increasing relation starting at 1 or a decreasing relation starting at n, then the corresponding interval is not new.

Proof. If there is a decreasing relation starting at n in P, then, in the decreasing forest of P, the integer n is not the root of its tree. Using the bijection of Theorem 2.4, this implies that there is a vertex on the right side of the tree S. Similarly, if there is an increasing relation starting by 1 in P, there is a vertex on the left side of the tree T. By Lemma 4.3, this implies that the interval [S, T] is not new. □

With the in-order algorithm, there is a simple relation between the labeling of the vertices and the labeling of the leaves.

Lemma 4.13. Let S be a binary search tree. Let T be a subtree of S. Then the vertices of T are labeled by the interval [i, j −1] if and only if the leaves of T are labeled by [i, j].

Proof. The result follows from an easy induction. □

We can deduce the following lemma.

Lemma 4.14. Let [S, T] be an interval of Tam_{n} such that S = Y ∘_{1} S_{1} and T = Y ∘_{2} T_{1} for two trees S_{1} and T_{1} of Tam_{n−1}. If [S, T] is not new, the corresponding interval-poset is not new.

Proof. By Lemma 4.2, there are integers 1 < i < j < n + 1, a subtree A of S whose leaves are labeled by [i, j] and a subtree B of T whose leaves are also labeled by [i, j]. This implies that the root of A and B are not on the left or right sides of S and T.

By Lemma 4.13, the vertices of the two subtrees are labeled by [i, j − 1]. Let x be the label of the root B. The left-most vertex of B is labeled by i. So, in the poset of increasing relations of T we have i ◁ x. The vertex labeled by j (there is such a vertex since j < n + 1) is the vertex visited by the in-order traversal after j − 1. Since j − 1 is the right-most vertex of the tree B, the vertex x is in the subtree with root j. So, we have x ◁ j and, by transitivity, we have i ◁ j.

Similarly, if y is the label of the root of A, then we have a decreasing relation j −1◁y. The vertex labeled by i − 1 (there is such a vertex since 1 < i) is the vertex visited by the in-order algorithm before the vertex labeled by i which is nothing but the left-most vertex of the tree S_{1}. In particular, y is in the subtree with root i − 1. So, we have y ◁ i − 1 and by transitivity j − 1 ◁ i − 1.

In conclusion, the interval-poset corresponding to [S, T] is not new. □

Conversely, we need to understand how the forbidden configuration of Definition 4.6 leads to the existence of a grafting decomposition of the corresponding interval. For this we need to carefully follow the bijection of Châtel and Pons.

Let P be an interval-poset with no increasing relation starting at 1 and no decreasing relation starting at n. If P is not new, then it has a configuration of the form i+1◁_{R}j+1 and j ◁_{R} i for i < j. Let x be the maximal element in [i + 1, j] such that i + 1 ◁ x. Note that the interval-poset condition implies that there is a decreasing relation x ◁ i. Similarly, let y be the minimal element such that i < y ⩽ j and such that j ◁ y.

Lemma 4.15. Let T be the upper bound of the interval of Tam_{n} corresponding to P by the bijection of Theorem 2.4. Then the subtree of T with root the vertex labeled by x has leaves labeled by the interval [i + 1, j + 1].

Proof. Let h ⩽ i. If there is a relation h ◁ x, by the interval-poset condition we have a relation i ◁ x. This contradicts the decreasing relation x ◁ i.

Moreover, the maximality of x implies that the relation x ◁ j + 1 is a cover relation in the increasing forest of P. Together with the previous argument, this shows that x is the left-most child of j + 1 in the increasing forest of P.

The relation i + 1 ◁ j + 1 and the interval-poset condition imply the existence of the relation j ◁ j + 1. Clearly, j is the right-most child of j + 1 in the increasing forest of P.

So, in the tree T, the vertex j is the right-most descendant of x and x is the left child of j + 1. In other words, j is the largest vertex of the subtree with root x. Since we have i + 1 ◁ x, there is a vertex labeled by i + 1 in the subtree with root x. The first argument of the proof implies that this is the smallest vertex of this subtree. So it has its vertices labeled by the interval [i + 1, j]. Finally, by Lemma 4.13 its leaves are labeled by [i + 1, j + 1]. □

Dually, we have a similar result for the decreasing relations. Lemma 4.16. Let S be the lower bound of the interval of Tam_{n} corresponding to P by the bijection of Theorem 2.4. Then the subtree of S with root the vertex labeled by y has leaves labeled by the interval [i + 1, j + 1]. Proof. This is a straightforward application of Lemma 2.5 to Lemma 4.15. □

Proof of Theorem 4.10. By Lemmas 4.11 and 4.14, if an interval is not new, then its corresponding interval-poset is not new. Conversely, using Lemma 4.12, we may assume that P does not have an increasing relation starting at 1 nor a decreasing relation starting at n. Let [S, T] be the corresponding interval. Then, by Lemmas 4.15 and 4.16 and the discussion before them, in S and T there are two subtrees whose leaves are labeled by the same interval. Lemma 4.2 implies that [S, T] is not new. □

As a corollary, we also have a characterization in terms of modern interval-posets. Corollary 4.17. Let n ∈ ℕ. There is a bijection between the set of new intervals of Tam_{n+1} and the set of modern interval-posets of size n. Proof. By Theorem 4.10, an interval of Tam_{n+1} is new if and only if its corresponding interval-poset is new. By Lemma 4.8, these interval-posets are in bijection with the modern interval-posets of size n. □

As explained in Lemma 4.3, it is easy to see that, if an interval [S, T] is new, then S = Y ∘_{1} S_{1} and T = Y ∘_{2} T_{1} where Y is the unique binary tree of size 1. However, this is not a sufficient condition. Using our characterization of new intervals in terms of interval-posets, we can find a characterization of the new intervals of the Tamari lattice. Theorem 4.18. Let [S, T] be an interval of Tam_{n+1}. Then [S, T] is a new interval if and only if there is an interval [S_{1}, T_{1}] in Tam_{n} such that S = Y ∘_{1} S_{1} and T = T ∘_{2} T_{1}. Proof. By Theorem 4.10, the new intervals of Tam_{n+1} are exactly the intervals such that the corresponding interval-poset is new. The result follows from Proposition 4.9. □

5. Infinitely modern interval-posets

For an integer k and an interval-poset P of size n, we let Ra^{k}(P) the k-th raise of P.

Definition 5.1. An interval-poset is infinitely modern if Ra^{k}(P) is an interval-poset for every k ⩾ 1. Lemma 5.2. An interval-poset P is infinitely modern if and only if it does not contain any configuration of the form w ◁ x and z ◁ y for w < x < y < z. Proof. If we have such a configuration in P, then the interval-poset condition implies the existence of relations x − 1 ◁ x and y + 1 ◁ y. After raising our poset sufficiently many times, we will have two contradictory relations y ◁_{R^{k}} y + 1 and y + 1 ◁_{R^{k}} y.

Conversely, let k + 1 be the smallest integer such that Ra^{k+1}(P) is not a poset. Then Ra^{k}(P) is not modern and by Definition 4.4 there is a configuration of the form x ◁_{R^{k}} y and z ◁_{R^{k}} y for x < y < z in Ra^{k}(P). This leads to the result. □

For an interval-poset P of size n, we denote by ir(P) the smallest integer k such that there is an \underline{i}ncreasing \underline{r}elation k ◁ k + 1. If there is no increasing relation, we use the convention that ir(P) = n. Similarly, we denote by dr(P) the largest integer i such that there is a \underline{d}ecreasing \underline{r}elation i ◁ i − 1. If there is no decreasing relation, we use the convention that dr(P) = 1. We can associate to any interval-poset P of size n the double statistic (ir(P), dr(P)) which is a pair of elements of {1, 2, …, n}. Using this statistic, we have another description of the infinitely modern interval-posets.

Proposition 5.3. Let P be an interval-poset of size n. Then P is infinitely modern if and only if dr(P) ⩽ ir(P).

Proof. If ir(P) < dr(P), then the poset is not infinitely-modern because, after some raises, the relation k ◁ k + 1 will contradict the relation i ◁ i − 1. Conversely, if the poset is not infinitely modern, by Lemma 5.2, there are integers w < x < y < z such that w ◁ x and z ◁ y. By the interval-poset condition, we have relations x − 1 ◁ x and y + 1 ◁ y. In particular, we see that ir(P) < dr(P). □

We denote by IM(n, i, k) the set of infinitely modern interval-posets P of size n such that ir(P) = k and dr(P) = i.

Let 1 ⩽ i ⩽ k ⩽ n + 1 and P be an interval-poset of size n. Then we define a relation f_{i,k}(P) on the set with n + 1 elements by adding a new point to the set of P. For the increasing relations, the new point is inserted at k and we add a new increasing relation from k to k + 1. For the decreasing relations, we may think that the new point is inserted at the position i and we add a new relation i ◁ i − 1. The old relations of P are modified accordingly to the positions of the new point.

More formally, f_{i,k}(P) is defined as the set {1, 2, …, n + 1} with the relation ◁′:

• We have k ◁′ k +1 and i◁′ i+1 with the convention that there are no increasing relations when k = n + 1 and no decreasing relations when i = 1.

• Let us assume that we have an increasing relation x◁y in P. If x < y < k, then we have the relation x ◁′ y in f_{i,k}(P). If x < k ⩽ y, then we have the relation x ◁′ y + 1 in f_{i,k}(P). If k ⩽ x < y, then we have the relation x + 1 ◁′ y + 1.

• Let us assume that we have a decreasing relation y ◁ x in P. If i ⩽ x < y, then we have the relation y + 1 ◁′ x + 1. If x < i ⩽ y, then we have the relation y + 1 ◁ x. If x < y < i, then we have the relation y ◁ x.

• Take the transitive closure of the relation ◁′.

Lemma 5.4. Let 1 ⩽ i ⩽ k ⩽ n + 1. Let i′ ⩽ i and k − 1 ⩽ k′. Let P ∈ IM(n, i′, k′). Then f_{i,k}(P) is an interval-poset of size n + 1 in IM(n + 1, i, k).

Proof. If we have a decreasing relation y ◁ x in P, by the interval-poset condition, we also have a relation x + 1 ◁ x. This implies that, in P, all the decreasing relations are of the form y ◁ x where x < y and x < i′. Since i′ ⩽ i, in f_{i,k}(P) all the decreasing relations are of the form y′ ◁ x′ where x′ < i. Moreover, we have a decreasing relation i ◁ i − 1 in f_{i,k}(P). In other terms, we have dr(f_{i,k}(P)) = i.

Similarly, in P all the increasing relations are of the form x ◁ y with x < y and k′ + 1 ⩽ y. Since k ⩽ k′ + 1, all the increasing relations in f_{i,k}(P) are of the form x′ ◁ y′ where k < y′. By construction in f_{i,k}(P), we have the relation k ◁ k + 1. So, ir(f_{i,k}(P)) = k.

1 2 3 4 5  1 2 3 4 5 6

Figure 6. On the left, an interval-poset P of size 5. On the right, the construction f_{2,4}(P). The vertex in red represents the position of the new point for the increasing relations. The vertex in blue represents the position of the new point for the decreasing relations. The new arrows are displayed in thick red and blue. The black dashed arrows correspond to the old relations of P. The long red arrow is obtained by transitivity.

It remains to check that under the hypothesis f_{i,k}(P) is an interval-poset. Let x < y such that x ◁ y and y ◁ x in f_{i,k}(P). Since the increasing relations land after k and the decreasing before i, the only possibility is to have x < i < k < y. This means that in P, we have a relation x ◁ y − 1 and y ◁ y − 1. This is not possible since P is a poset. Since the relation ◁′ is transitive by construction, this shows that f_{i,k}(P) is a poset.

We need to check the interval-poset condition. It is an easy case by case checking: let x < y < z and x ◁ z in f_{i,k}(P). If x < k < y, then in P we have the relation x ◁ y − 1. If k ≠ z, since P is an interval-poset, we have the relation z′ ◁ y − 1 for z′ = z if z′ < k and z′ = z − 1 otherwise. So, in f_{i,k}(P), we have z ◁ y. If z = k, then in f_{i,k}(P) we have the relation k ◁ k + 1. By the interval-poset condition of P, we have k ◁ y − 1. It becomes k + 1 ◁ y in f_{i,k}(P). By transitivity, we have k ◁ y. Similarly, we can check the case where k ⩽ x ⩽ y. For the decreasing relations, the proof is similar. □

On the other hand, if P is an interval-poset in IM(n+1, i, k) let us construct ρ(P) an interval-poset of size n. Informally, for the increasing relations, we remove the vertex k and the relation k◁k+1. We shift the other relations accordingly to their position. For the decreasing relations, we remove the vertex i and the relation i◁i−1. Furthermore, we shift the relations accordingly to their position. More formally, ρ(P) is the relation on the set {1, 2, …, n} defined by:

• Let x < y. Then we have a relation x ◁ y in the following two cases: if x < k < y + 1 and there is a relation x ◁ y + 1 in P, or if k < x + 1 < y + 1 and there is a relation x + 1 ◁ y + 1 in P.

• Let x < y. Then we have a relation y ◁x in the following two cases: if x < y < i and there is a relation y ◁ x in P or if x < i < y + 1 and there is a relation y + 1 ◁ x in P.

Lemma 5.5. Let P ∈ IM(n + 1, i, k). Then ρ(P) is an infinitely modern interval-poset such that dr(P) ⩽ i and k − 1 ⩽ ir(P).

Proof. In P the increasing relations are of the form y ◁ x where k < x. If we have the relation k − 1 ◁ k + 1 in P, then we have the relation k − 1 ◁ k in ρ(P). Otherwise the second increasing relation x ◁ x + 1 of length 1 in P (the one after k ◁ k + 1) appears for k + 1 ⩽ k. Here we use one more time the convention that there is an increasing relation starting at n + 1 if there is no such relation. So, in ρ(P) the first increasing relation is x − 1 ◁ x and we have k − 1 ⩽ ir(P). Moreover, we have ir(P) = k − 1 if and only if we have the relation k − 1 ◁ k + 1 in P.

Similarly, we have dr(P) ⩽ i and dr(P) = i if and only if we have the relation i − 1 ◁ i + 1 in P.

Now, we check that ρ(P) is an interval-poset. By the description of ir(ρ(P)) and dr(ρ(P)), we deduce that, if x ◁ y is an increasing relation in ρ(P), we have k ⩽ y. Similarly, if y ◁ x is a decreasing relation we have x < i.

Let x < y such that x ◁ y and y ◁ x in ρ(P). Then we must have x < i and k ⩽ y. So, the relation x ◁ y comes from the relation x ◁ y + 1 in P and the relation y ◁ x comes from the relation y +1◁x in P. Since P is an interval-poset, this is not possible. In P there are no increasing relations of the form x ◁ k and no decreasing relations of the form y ◁ i, so removal of the relations k ◁ k + 1 and i ◁ i − 1 will not break the transitivity of the relation. Checking the interval-poset condition is straightforward and similar to the proof of Lemma 5.4.

If i < k, as a direct consequence of Proposition 5.3, the interval-poset ρ(P) is infinitely-modern. If i = k, we have to check that it is not possible to have ir(ρ(P)) = k − 1 and dr(ρ(P)) = i. But this is a direct consequence of the description of these two particular cases obtained above. □

Proposition 5.6. Let n ∈ ℕ. Let 1 ⩽ i ⩽ k ⩽ n + 1. Then we have a bijection

f_{i,k} : ⋃_{\begin{matrix}1⩽i′⩽i \\ k−1⩽k′⩽n \end{matrix}} IM(n, i′, k′) → IM(n + 1, i, k).

Proof. By Lemma 5.4, f_{i,k} maps the left-hand side to the right-hand side, and by Lemma 5.5, the map ρ goes from the right-hand side to the left-hand side. It is clear that ρ and f_{i,k} are two bijections inverse of each other. □

Theorem 5.7. Let n ∈ ℕ. Then the number of infinitely modern interval-posets of size n is \frac{1}{2n+1} \binom{3n}{n}.

Proof. Let k, l ∈ {0, 1, …, n − 1}. We set B(n, k, l) = | IM(n, k + 1, n − l)|. With the change of variables x − 1 = k and n − y = l, this is the number of infinitely modern interval-posets of size n with ir = y and dr = x. It is easy to check that we have B(1, 0, 0) = 1. By Lemma 5.3, if P is an interval-poset such that ir(P) < dr(P), then P is not infinitely-modern. So, if k + l ⩾ n, we have B(n, k, l) = 0. Finally, if k + l < n, then 1 ⩽ x ⩽ y ⩽ n and Proposition 5.6 implies

B(n, k, l) = ∑_{0⩽i⩽k,0⩽j⩽k} B(n − 1, i, j).

We recognize the sequence of [Ava08, Definition 2.1]. The result follows from [Ava08, Proposition 2.1]. □

References

[Ara13] T. Araya. Exceptional sequences over path algebras of type A_{n} and non-crossing spanning trees. Algebr. Represent. Theory, 16(1):239–250, 2013.

[Ava08] J.-C. Aval. Multivariate Fuss–Catalan numbers. Discrete Math., 308(20):4660–4669, 2008.

[BB09] O. Bernardi and N. Bonichon. Intervals in Catalan lattices and realizers of triangulations. J. Combin. Theory Ser. A, 116(1):55–75, 2009.

[BK04] A. B. Buan and H. Krause. Tilting and cotilting for quivers and type Ã_{n}. J. Pure Appl. Algebra, 190(1-3):1–21, 2004.

[Cha07] F. Chapoton. The anticyclic operad of moulds. Int. Math. Res. Notices, (20):Art. ID rnm078, 36, 2007.

[Cha12] F. Chapoton. On the categories of modules over the Tamari posets. In Associahedra, Tamari lattices and related structures, volume 299 of Prog. Math. Phys., pages 269–280. Birkhäuser/Springer, Basel, 2012.

[Cha16] F. Chapoton. Stokes posets and serpent nests. Discrete Math. Theor. Comput. Sci., 18(3):1365–8050, 2016.

[Cha17] F. Chapoton. Une note sur les intervalles de Tamari. Ann. Math. Blaise Pascal, 25(2):299– 314, 2018.

[CHNT08] F. Chapoton, F. Hivert, J.-C. Novelli, and J.-Y. Thibon. An operational calculus for the mould operad. Int. Math. Res. Notices, (9):Art. ID rnn018, 22, 2008.

[CP15] G. Châtel and V. Pons. Counting smaller elements in the Tamari and m-Tamari lattices. J. Combin. Theory Ser. A, 134:58–97, 2015.

[CPP17] G. Châtel, V. Pilaud, and V. Pons. The weak order on integer posets. Algebr. Combin., 2(1):1–48, 2019.

[dBM67] N. G. de Bruijn and B. J. M. Morselt. A note on plane trees. J. Combin. Theory, 2(1):27–34, 1967.

[DP93] S. Dulucq and J.-G. Penaud. Cordes, arbres et permutations. Discrete Math., 117(1-3):89– 105, 1993.

[Ede82] P. H. Edelman. Multichains, noncrossing partitions and trees. Discrete Math., 40(2-3):171– 179, 1982.

[Gab81] P. Gabriel. Un jeu? Les nombres de Catalan. Zürich uni, Mitteilungsblatt des Rektorats, 12. Jahrgang, Heft 6:4–5, 1981.

[HPT64] F. Harary, G. Prins, and W. T. Tutte. The number of plane trees. Nederl. Akad. Wetensch. Proc. Ser. A 67=Indag. Math., 26:319–329, 1964.

[HU05] D. Happel and L. Unger. On a partial order of tilting modules. Algebr. Represent. Theory, 8(2):147–156, 2005.

[Kre72] G. Kreweras. Sur les partitions non croisées d’un cycle. Discrete Math., 1(4):333–350, 1972.

[Rea06] N. Reading. Cambrian lattices. Adv. Math., 205(2):313–353, 2006.

[Rog18] B. Rognerud. The bounded derived categories of the Tamari lattices are fractionally Calabi–

          Yau. preprint; arXiv:1807.08503.

[Tam62] D. Tamari. The algebra of bracketings and their enumeration. Nieuw Arch. Wisk. (3), 10:131–146, 1962.