Camille Combe

Samuele Giraudo

THREE FUSS-CATALAN POSETS IN INTERACTION AND THEIR ASSOCIATIVE ALGEBRAS

Keywords: 2020 Mathematics Subject Classification. 05E99, 06A07, 06A11, 16T30 Poset, Tamari lattice, Fuss-Catalan objets, Malvenuto-Reutenauer algebra, Loday-Ronco algebra

We introduce δ-cliffs, a generalization of permutations and increasing trees depending on a range map δ. We define a first lattice structure on these objects and we establish general results about its subposets. Among them, we describe sufficient conditions to have EL-shellable posets, lattices with algorithms to compute the meet and the join of two elements, and lattices constructible by interval doubling. Some of these subposets admit natural geometric realizations. Then, we introduce three families of subposets which, for some maps δ, have underlying sets enumerated by the Fuss-Catalan numbers. Among these, one is a generalization of Stanley lattices and another one is a generalization of Tamari lattices. These three families of posets fit into a chain for the order extension relation and they share some properties. Finally, in the same way as the product of the Malvenuto-Reutenauer algebra forms intervals of the right weak Bruhat order of permutations, we construct algebras whose products form intervals of the lattices of δ-cliff. We provide necessary and sufficient conditions on δ to have associative, finitely presented, or free algebras. We end this work by using the previous Fuss-Catalan posets to define quotients of our algebras of δ-cliffs. In particular, one is a generalization of the Loday-Ronco algebra.

INTRODUCTION

The theory of combinatorial Hopf algebras takes a prominent place in algebraic combinatorics. The Malvenuto-Reutenauer algebra FQSym [MR95, DHT02] is a central object in this theory. This structure is defined on the linear span of all permutations and the product of two permutations has the notable property to form an interval of the right weak Bruhat order. Moreover, FQSym admits a lot of substructures, like the Loday-Ronco algebra of binary trees PBT [START_REF] Loday | Hopf Algebra of the Planar Binary Trees[END_REF][START_REF] Hivert | The algebra of binary search trees[END_REF] and the algebra of noncommutative symmetric functions Sym [GKL + 95]. Each of these structures brings out in a beautiful and somewhat unexpected way the combinatorics of some partial orders, respectively the Tamari order [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF] and the Boolean lattice, playing the same role as the one played by the right weak Bruhat order for FQSym. To be slightly more precise, all these algebraic structures have, as common point, a product • which expresses, on their so-called fundamental bases {F x } x , as

F x • F y = x y≼z≼x y F z , (0.0.1)
where ≼ is a partial order on basis elements, and and are some binary operations on basis elements (in most cases, some sorts of concatenation operations).

The point of departure of this work consists in considering a different partial order relation on permutations and ask to what extent analogues of FQSym and a similar hierarchy of algebras arise in this context. We consider here first a very natural order on permutations: the componentwise ordering ≼ on Lehmer codes of permutations [Leh60]. A study of these posets Cl 1 (n) appears in [Den13]. Each poset Cl 1 (n) is an order extension of the right weak Bruhat order of order n. To give a concrete point of comparison, the Hasse diagrams of the right weak Bruhat order of order 3 and of Cl 1 (3) are respectively

In the same way as the Tamari order can be defined by restricting the right weak Bruhat order to some permutations, one builds three subposets of Cl δ by restricting ≼ to particular δ-cliffs. This leads to three families Av δ , Hi δ , and Ca δ of posets. When δ is the particular map m defined above with m ⩾ 0, the underlying sets of all these posets of order n ⩾ 0 are enumerated by the n-th m-Fuss-Catalan number [START_REF] Dvoretzky | A problem of arrangements[END_REF] cat m (n) := 1 mn + 1 mn + n n . (0.0.4)

These posets have some close interactions: when δ is an increasing map, Hi δ is an order extension of Ca δ , which is itself an order extension of Av δ . Besides, Hi m (resp. Ca m ) generalizes for any m ⩾ 0 the Stanley lattice [Sta75, Knu04] (resp. Tamari lattice), which occurs when m = 1. Our generalization of Tamari lattices is different from the classical one introduced in [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF]. Besides, from these posets Hi m and Ca m , one defines respectively two quotient algebras Hi m and Ca m of Cl m . Notably, The algebra Ca 1 is isomorphic to PBT, and the other ones Ca m , m ⩾ 2, are not free as associative algebras. This paper is organized as follows.

Section 1 is intended to introduce δ-cliffs and to set some notations and recalls about poset theory. As a by-product in the process of establishing links between the posets Cl δ (n) and the weak Bruhat order, we introduce an alternative poset (Cl δ (n), ≼ ′

) when δ satisfies some particular conditions. We prove that when δ = 1, the obtained poset is the weak Bruhat order and we conjecture that for all authorized range maps δ, the posets (Cl δ (n), ≼ ′

) are semi-distributive lattices. Besides, even if the posets Cl δ (n) have a very simple structure, they contain interesting subposets S(n). To study these substructures, we establish a series of sufficient conditions on S(n) for the fact that these posets are EL-shellable [START_REF] Björner | Shellable nonpure complexes and posets[END_REF][START_REF] Björner | Shellable nonpure complexes and posets[END_REF], are lattices (and give algorithms to compute the meet and the join of two elements), and are constructible by interval doubling [Day79]. Moreover, under some precise conditions, each subposet S(n) can be seen as a geometric object in R n . We call this the geometric realization of S(n). We introduce here the notion of cell and expose a way to compute the volume of the geometrical object.

Next, in Section 2, we study the posets Av δ , Hi δ , and Ca δ . For each of these, we provide some general properties (EL-shellability, lattice property, constructibility by interval doubling), and describe its input-wings, output-wings, and butterflies elements, that are elements having respectively a maximal number of covered elements, covering elements, or both properties at the same time. We observe a surprising phenomenon: some posets Av δ , Hi δ , or Ca δ are isomorphic to their subposets restrained on input-wings, output-wings, or butterflies elements. Moreover, a notable link among other ones is that the subposet of Ca m (n) is isomorphic to the subposet of Hi m-1 (n) restrained to its input-wings. We also study further interactions between our three families of Fuss-Catalan posets: there are for instance bijective posets morphisms (but not poset isomorphisms) between Av δ and Ca δ , and between Ca δ and Hi δ , when δ is increasing.

Finally, Section 3 presents a study of the algebra Cl δ . We start by introducing a natural coproduct on Cl δ in order to obtain by duality a product, associative in some cases. Three alternative bases of Cl δ are introduced, including two that are multiplicative and are defined from the order on δ-cliffs. We then rely on these bases to give a presentation by generators and relations of Cl δ . When δ is valley-free and is 1-dominated (that is a certain condition on range maps), Cl δ admits a finite presentation (a finite number of generators and a finite number of nontrivial relations between the generators). When δ is weakly increasing, Cl δ is free as an associative algebra. We end this work by constructing, given a subfamilly S of Cl δ , a quotient space Cl S of Cl δ isomorphic to the linear span of S. A sufficient condition on S to have moreover a quotient algebra of Cl δ is introduced. We also describe a sufficient condition on S for the fact that the product of two basis elements of Cl S is an interval of a poset S(n). These results are applied to construct and study the two quotients Hi m := Cl Hi m and Ca m := Cl Ca m of Cl m . The algebra Ca 1 is isomorphic to the Loday-Ronco algebra and the other algebras Ca m , m ⩾ 2, provide generalizations of this later which are not free. On the other hand, for any m ⩾ 1, all Hi m are other associative algebras whose dimensions are also Fuss-Catalan numbers and are not free.

This paper is an extended version of [START_REF] Combe | Three interacting families of Fuss-Catalan posets[END_REF] containing the proofs of the presented results and presenting new ones as the geometrical aspects of the studied posets.

General notations and conventions. For any integers i and j, [i, j] denotes the set {i, i + 1, . . . , j}. For any integer i, [i] denotes the set [1, i] and i] denotes the set [0, i]. Graded sets are sets decomposing as a disjoint union S = n⩾0 S(n). For any x ∈ S, the unique n ⩾ 0 such that x ∈ S(n) is the degree |x| of x. A graded subset of S is a graded set S ′ such that for all n ⩾ 0, S ′ (n) ⊆ S(n). The generating series of S is the series G S (t) := x∈S t |x| . The empty word is denoted by ε. If P is a statement, we denote by ↿ P the indicator function (equals to 1 if P holds and 0 otherwise).

δ-CLIFF POSETS AND GENERAL PROPERTIES

This section is devoted to introduce the lattices of δ-cliffs and to set some notations and definitions about posets and lattices. Then, we will review some properties of its subposets, like EL-shellability, constructibility by interval doubling, and geometric realizations.

1.1. δ-cliffs. We introduce here δ-cliffs, their links with Lehmer codes, permutations, and particular increasing trees.

1.1.1. First definitions. A range map is a map δ : N \ {0} → N. We shall specify range maps as infinite words δ = δ(1)δ(2) . . . . For this purpose, for any a ∈ N, we shall denote by a ω the infinite word having all its letters equal to a. We say that δ ⋆ is rooted if δ(1) = 0; ⋆ is weakly increasing if for all i ⩾ 1, δ(i) ⩽ δ(i + 1); ⋆ is increasing if for all i ⩾ 1, δ(i) < δ(i + 1)); ⋆ has an ascent if there are 1 ⩽ i 1 < i 2 such that δ(i 1 ) < δ(i 2 ); ⋆ has an descent if there are 1 ⩽ i 1 < i 2 such that δ(i 1 ) > δ(i 2 ); ⋆ has a valley if there are 1 ⩽ i

1 < i 2 < i 3 such that δ(i 1 ) > δ(i 2 ) < δ(i 3 ); ⋆ is valley-free (or unimodal) if δ has no valley; ⋆ is j-dominated for a j ⩾ 1 if there is k ⩾ 1 such that for all k ′ ⩾ k, δ(j) ⩾ δ(k ′
).

For any n ⩾ 0, the n-th dimension of δ is the integer dim n (δ

) := #{i ∈ [n] : δ(i) ̸ = 0}.
Given a range map δ, a word u of nonnegative integers of length n is a δ-cliff if for any i ∈ [n], u i ∈ δ(i)]. The size |u| of a δ-cliff u is its length as a word, and the weight ω(u) of u is the sum of its letters. The graded set of all δ-cliffs where the degree of a δ-cliff is its size, is denoted by Cl δ . In the sequel, for any m ⩾ 0, we shall denote by m the range map satisfying m(i) = (i -1)m for any i ∈ N \ {0}. For instance, Cl 1 (3) = {000, 001, 002, 010, 011, 012},

(1.1.1a)

Cl 2 (3) = {000, 001, 002, 003, 004, 010, 011, 012, 013, 014, 020, 021, 022, 023, 024}.

(1.1.1b)

Let us denote respectively by 0δ (n) and by 1δ (n) the δ-cliffs 0 n and δ(1) . . . δ(n).

It follows immediately from the definition of δ-cliffs that the cardinality of Cl δ (n) satisfies

#Cl δ (n) = i∈[n] (δ(i) + 1). (1.1.2)
The first numbers of m-cliffs are

1, 1, 1, 1, 1, 1, 1, 1, m = 0, (1.1.3a) 1, 1, 2, 6, 24, 120, 720, 5040, m = 1, (1.1.3b) 1, 1, 3, 15, 105, 945, 10395, 135135, m = 2. (1.1.3c) Last sequence is Sequence A001147 of [Slo].

Lehmer codes and permutations.

There is a classical correspondence between permutations and Lehmer codes [Leh60], that are certain words of integers. Here, we consider a slight variation of Lehmer codes, establishing a bijection between the set of 1-cliffs of size n and the set of permutations of the same size. Given a permutation σ of size n, let the 1-cliff u such that for any j ∈ [n], u j is the number of values i such that i < j while σ -1 (i) > σ -1 (j). We denote by leh(σ) the 1-cliff thus associated with the permutation σ. For instance, leh(436512) = 002323. 1.1.3. Weakly increasing range maps and increasing trees. Given a rooted weakly increasing range map δ, let ∆ δ : N \ {0} → N be the map defined by ∆ δ (i) := δ(i + 1) -δ(i). For instance, for any a ⩾ 0, ∆ a ω = 0 ω , and for any m ⩾ 0, ∆ m = m ω . A δ-increasing tree is a planar rooted tree where internal nodes are bijectively labeled from 1 to n, any internal node labeled by i ∈ [n] has arity ∆ δ (i) + 1, and every children of any node labeled by i ∈ [n] are leaves or are internal nodes labeled by j ∈ [n] such that j > i. The size of such a tree is its number of internal nodes. The leaves of a δ-increasing tree are implicitly numbered from 1 to its total number of leaves from left to right.

Observe that, regardless of any particular condition on δ, any δ-cliff u of size n ⩾ 1 recursively decomposes as u = u ′ a where a ∈ δ(n)] and u ′ is a δ-cliff of size n -1. Relying on this observation, when δ is rooted and weakly increasing, let tree δ be the map sending any δ-cliff u of size n to the δ-increasing tree of size n recursively defined as follows. If n = 0, tree δ (u) is the leaf. Otherwise, by using the above decomposition of u, tree δ (u) is the tree obtained by grafting on the (a + 1)-st leaf of the tree tree(u ′ ) a node of arity ∆ δ (n) + 1 labeled by n. For instance, tree 2 (0230228) = (1.1.5) Proposition 1.1.1. For any rooted weakly increasing range map δ, tree δ is a one-to-one correspondence from the set of all δ-cliffs of size n ⩾ 0 and the set of all δ-increasing trees of size n.

Proof. Let us first prove that tree δ is a well-defined map. This can be done by induction on n and arises from the fact that, for any u ∈ Cl δ (n), the total number of leaves of tree δ (u) is 1 + δ(n + 1). This is a consequence of the fact that

1 + δ(n) -1 + ∆ δ (n) + 1 = 1 + δ(n + 1). (1.1.6)
Therefore, there is in tree δ (u) a leaf of index a+1 for any value a ∈ δ(n + 1)]. Hence, and due to the fact that by construction, tree δ (u) is a δ-increasing tree, the map tree δ is well-defined. Now, let φ be the map from the set of all δ-increasing trees of size n to Cl δ (n) defined recursively as follows. If t is the leaf, set φ(t) := ε. Otherwise, consider the node with the maximal label in t. Since t is increasing, this node has no children. Set t ′ as the δ-increasing tree obtained by replacing this node by a leaf in t, and set a as the index of the leaf of t ′ on which this maximal node of t is attached (this index is 1 if t ′ is the leaf). Then, set φ(t) := φ(t ′ )(a -1). The statement of the proposition follows by showing by induction on n that φ is the inverse of the map tree δ .

□

In [START_REF] Ceballos | The s-weak order and s-permutahedra[END_REF], s-decreasing trees are considered, where s is a sequence of length n ⩾ 0 of nonnegative integers. These trees are labeled decreasingly and any internal node labeled by i ∈ [n] has arity s i . As a consequence of Proposition 1.1.1, any s-decreasing tree can be encoded by a δ-increasing tree where δ is a rooted weakly increasing range map satisfying

δ(i) = 1⩽j⩽i-1 s n-j+1 for all i ∈ [n + 1].
The correspondence between such s-decreasing trees and δ-increasing trees consists in relabeling by n + 1 -i each internal node labeled by i ∈ [n]. A consequence of all this is that δ-cliffs can be seen as generalizations of s-decreasing trees by relaxing the considered conditions on δ.

1.2. δ-cliff posets. We endow now the set of all δ-cliffs of a given size with an order relation, give some recalls about poset and lattice theory, and establish a link between the poset of 1-cliffs and the weak Bruhat order of permutations. 1.2.1. First definitions. Let δ be a range map and ≼ be the partial order relation on Cl δ defined by u ≼ v for any u, v ∈ Cl δ such that |u| = |v| and u i ⩽ v i for all i ∈ [|u|]. For any n ⩾ 0, the poset (Cl δ (n), ≼) is the δ-cliff poset of order n. Figure 1 shows the Hasse diagrams of some δ-cliff posets. Let us introduce some notation about δ-cliffs. For any u ∈ Cl δ (n) and i ∈ [n], let ↓ i (u) (resp. ↑ i (u)) be the word on Z of length n obtained by decrementing (resp. incrementing) by 1 the i-th letter of u. Let also, for any u, v ∈ Cl δ (n), D(u, v) := {i ∈ [n] : u i ̸ = v i } be the set of all indices of different letters between u and v. For any u, v ∈ Cl δ (n), let u ∧ v be the δ-cliff of size n defined for any i ∈ [n] by (u ∧ v) i := min{u i , v i }. We also define u ∨ v similarly by replacing the min operation by max in the previous definition. For any u, v ∈ Cl δ (n), the difference between v and u is the word v -u on Z of length n defined for any i ∈ [n] by

(v -u) i := v i -u i . Observe that when u ≼ v, v -u is a δ-cliff. The δ-complementary c δ (u) of u ∈ Cl δ (n) is the δ-cliff 1δ (n) -u.
For instance, by setting u := 0010, if u is seen as a 1-cliff, then c 1 (u) = 0113, and if u is seen as a 2-cliff, then c 2 (u) = 0236. This map c δ is an involution.

First properties and recalls.

A study of the 1-cliff posets appears in [Den13]. Our definition stated here depending on δ is therefore a generalization of these posets. The structure of the δ-cliff posets is very simple since each of these posets of order n is isomorphic to the Cartesian product δ

(1)] × • • • × δ(n)],
where k] is the total order on k + 1 elements. It follows from this observation that each δ-cliff poset is a lattice admitting respectively ∧ and ∨ as meet and join operations. Recall that a lattice (L, ∧, ∨) is distributive if for all x, y, z ∈ L, x ∧(y ∨ z) = (x ∧ y) ∨(x ∧ z). Recall also that all distributive lattices are modular and graded [START_REF] Stanley | Enumerative Combinatorics[END_REF]. Since total orders are distributive and the distributivity is preserved by the Cartesian product of posets, Cl δ (n) is a distributive lattice.

Recall that the covering relation of a poset P is the set of all pairs (x, y) ∈ P 2 such that the interval [x, y] has cardinality 2. It follows immediately from the definition of ≼ that the covering relation ⋖ of Cl δ (n) satisfies u ⋖ v if and only if there is an index i ∈ [n] such that v = ↑ i (u). Moreover, these posets Cl δ (n) are graded, and the rank of a δ-cliff u is ω(u). The least element of the poset is 0δ (n) while the greatest element 1δ (n).

Let us make some reminders about poset morphisms used thereafter. If 1.2.3. Links with the weak Bruhat order. Let S be the graded set of all permutations where the degree of a permutation is its length as a word. A coinversion of a permutation σ is a pair σ j , σ i such that σ j < σ i and i < j. For any n ⩾ 0, the weak Bruhat order of order n is a partial order (S(n), ≼ S ) wherein for any σ, ν ∈ S(n), σ ≼ S ν if the set of all coinversions of σ is contained in the set of all coinversions of ν. By denoting by s i , i ∈ [n-1], the i-th elementary transposition, the covering relation ⋖ S of this poset satisfies σ ⋖ S σs i for any σ ∈ S(n) and

any i ∈ [n -1] such that σ i < σ i+1 .
When δ is a rooted weakly increasing range map, let us consider the binary relation ⋖ ′ on Cl δ (n) defined as follows. Let u, v ∈ Cl δ and t := tree δ (u). We have we observe that all the children of the nodes labeled by 2, 3, 5 and 6 are leaves, except possibly the first ones. For this reason, u is covered by ↑ 3 (u) = 022042 and by ↑ 6 (u) = 021043, but not by ↑ 2 (u) = 031042 since this word is not a δ-cliff.

u ⋖ ′ v if there is an index i ∈ [n] such that v = ↑ i (u)
The reflexive and transitive closure ≼ ′ of this relation is an order relation. By Proposition 1.1.1, this endows the set of all δ-increasing trees with a poset structure. It follows immediately from the description of the covering relation ⋖ of Cl δ (n) provided in Section 1.2.2 that ⋖ ′ is a refinement of ⋖. For this reason (Cl δ (n), ≼) is an order extension of (Cl δ (n), ≼ ′ ). Figure 2 shows an example of a Hasse diagram of such a poset. ).

Proposition 1.2.1. For any n ⩾ 0, the poset (Cl 1 (n), ≼ ′ ) is isomorphic to the weak Bruhat order on permutations of size n.

Proof. Let φ be the map from the set of all words u of size n of integers without repeated letters to the set of increasing binary trees of size n where internal nodes are bijectively labeled by the letters of u, defined recursively as follows. If σ is the empty word, then φ(σ) is the leaf. Otherwise, σ decomposes as σ = waw ′ where a is the least letter of σ, and w and w ′ are words of integers. In this case, φ(σ) is the binary tree consisting in a root labeled by a and having as left subtree φ(w ′

) and as right subtree φ(w) -observe the reversal of the order between w and w ′

. Now, by induction on n, one can prove that for any permutation σ of size n, the binary trees φ(σ) and tree 1 (leh(σ)) are the same.

Assume that σ and ν are two permutations such that σ ⋖ S ν. Thus, by definition of ⋖ S , σ decomposes as σ = wabw ′ and ν as ν = wbaw ′ where a and b are letters such that a < b, and w and w ′ are words of integers. By definition of φ, since a and b are adjacent in σ, the right subtree of the node labeled by b of φ(σ) is empty. Therefore, due to the property stated in the first part of the proof, and by definition of the map tree 1 and of the covering relation ⋖ ′

, one has leh(σ) ⋖ ′ leh(ν). Conversely, assume that u and v are two 1-cliffs such that u ⋖ ′ v. Thus, by definition of ⋖ ′ , v is obtained by changing a letter u i , i ⩾ 2, in u by u i + 1, and in tree 1 (u), the right subtree of the node labeled by i is empty. Let σ := leh -1 (u) and ν := leh -1 (v). Since φ(σ) and tree 1 (u) are the same increasing binary trees, we have, from the definition of the map φ, that u i-1 < u i . Finally, by definition of ⋖ S , one obtains σ ⋖ S ν.

We have shown that the bijection leh between S(n) and Cl 1 (n) is such that, for any σ, ν ∈ S(n), σ ⋖ S ν if and only if leh(σ) ⋖ ′ leh(ν) . For this reason, leh is a poset isomorphism. □ Therefore, Proposition 1.2.1 says in particular that the 1-cliff poset is an extension of the weak Bruhat order. Besides, for all rooted weakly increasing range maps δ, one can see (Cl δ (n), ≼ ′

) as generalizations of the weak Bruhat order. Supported by some computer experiments, we state the following conjecture.

Conjecture 1.2.2. For any rooted weakly increasing range map δ and any n ⩾ 0, the poset

(Cl δ (n), ≼ ′
) is a semi-distributive lattice. Observe that when S is spread, each poset S(n), n ⩾ 0, is bounded, that is it admits a least and a greatest element. Observe also that if S is both minimally and maximally extendable, then S is spread.

Lemma 1.3.1. Let δ be a range map and S be a coated graded subset of Cl δ . Then, S is straight.

Proof. Let n ⩾ 0 and u, v ∈ S(n) such that u ≼ v and #D(u, v) ⩾ 2. Set j := max D(u, v) and w := u 1 . . . u j-1 v j v j+1 . . . v n . Since S is coated, w belongs to S, and moreover, since j is maximal, w := u 1 . . . u j-1 v j u j+1 . . . u n . Therefore, #D(u, w) = 1. This proves that there exists a w ′ ∈ S(n) such that u ⋖ S w ′ ≼ w and #D(u, w ′ ) = 1. Thus, S is straight. □

We use here the notion of n-th dimension of range maps, defined in Section 1.1.1. In the case where S is straight, we define the graded set of ⋆ input-wings as the set I(S) containing any u ∈ S which covers exactly dim |u| (δ) elements; ⋆ output-wings as the set O(S) containing any u ∈ S which is covered by exactly dim |u| (δ)

elements; ⋆ butterflies as the set B(S) being the intersection I(S) ∩ O(S).

Equivalently, u ∈ S is an input-wing (resp. output-wing) if it is possible to decrement (resp. increment) all values at all positions i ∈ [|u|] such that δ(i) ̸ = 0. Observe also that if there is an i ⩾ 1 such that δ(i) = 1, there are no butterfly in S(n) for all n ⩾ i.

We present now general results about subposets S(n), n ⩾ 0, of δ-cliff posets.

1.3.1. EL-shellability. Let (P, ≼ P ) and (Λ, ≼ Λ ) be two posets, and λ : ⋖ P → Λ be a map (here ⋖ P is seen as the set of all pairs (u, v) such that v covers u in P). For any saturated chain x (1) , . . . , x (k) of P, by a slight abuse of notation, we set λ x (1) , . . . , x (k) := λ x (1) , x (2) , . . . , λ x (k-1) , x (k) .

(1.3.1)

We say that a saturated chain of P is λ-increasing (resp. λ-weakly decreasing) if its image by λ is an increasing (resp. weakly decreasing) word w.r.t. the partial order relation ≼ Λ . We say also that a saturated chain x (1) , . . . , x (k) of P is λ-smaller than a saturated chain y (1) , . . . , y (ℓ) of P if the image by λ of x (1) , . . . , x (k) is smaller than the image by λ of y (1) , . . . , y (ℓ) for the lexicographic order induced by ≼ Λ . The map λ is an EL-labeling of P if there exist such a poset Λ and a map λ such that for any x, y ∈ P satisfying x ≼ P y, there is exactly one λincreasing saturated chain from x to y which is minimal among all saturated chains from x to y w.r.t. the order on saturated chains just described. The poset P is EL-shellable [START_REF] Björner | Shellable nonpure complexes and posets[END_REF][START_REF] Björner | Shellable nonpure complexes and posets[END_REF] if P is bounded and admits an EL-labeling.

The EL-shellability of a poset P implies several topological and order theoretical properties of the associated order complex ∆(P) made of all the chains of P. For instance, one of the consequences for P for having at most one λ-weakly decreasing chain between any pair of its elements is that the Möbius function of P takes values in {-1, 0, 1}. In an equivalent way, the simplicial complex associated with each open interval of P is either contractile or has the homotopy type of a sphere [START_REF] Björner | Shellable nonpure complexes and posets[END_REF].

For the sequel, we set Λ as the poset Z 2 wherein elements are ordered lexicographically. For any straight graded subset S of Cl δ , let us introduce the map λ S :

⋖ S → Z 2 defined for any (u, v) ∈ ⋖ S by λ S (u, v) := (-i, u i ) where i is the unique index i ∈ [|u|] such that D(u, v) = {i}.
Observe that the fact that S is straight ensures that λ S is well-defined.

Theorem 1.3.2. Let δ be a range map and S be a coated graded subset of Cl δ . For any n ⩾ 0, the map λ S is an EL-labeling of S(n). Moreover, there is at most one λ S -weakly decreasing chain between any pair of elements of S(n).

Proof. By Lemma 1.3.1, the fact that S is coated implies that S is also straight. Let u, v ∈ S(n) such that u ≼ v. Since S is straight, the image by λ S of any saturated chain from u to v is well-defined. Now, let u = w (0) , w (1) , . . . , w (k) = v be the sequence of elements of S(n) defined in the following way. For any i ∈ k -1], the word w (i+1) is obtained from w (i) by increasing by the minimal possible value a ⩾ 1 the letter w (i) j such that j is the greatest index satisfying w

(i) j < v j .

By construction, for any

i ∈ k -1], each w (i+1)
writes as

w (i+1) = u 1 . . . u j-1 u j + a v j+1 . . . v n
, where a is some positive integer. There is at least one value a such that w (i) belongs to S(n) since by hypothesis, S is coated. For this reason, the considered sequence is a well-defined saturated chain in S(n). This saturated chain is also λ S -increasing by construction. Moreover, since S is straight, if one consider another saturated chain from u to v, this chain passes through a word obtained by incrementing a letter which has not a greatest index, and one has to choose later in the chain the letter of the smallest index to increment it. For this reason, this saturated chain would not be λ S -increasing.

Assume now that there exists in S a λ S -weakly decreasing saturated chain of the form u = w (0) , w (1) , . . . , w (k) = v . By definition of λ S and of the poset Λ, for any i ∈ k -1], the word w (i+1) is obtained from w (i) by increasing by the minimal possible value the letter w (i) j such that j is the smallest index satisfying w (i) j < v j . If it exists, this saturated chain is by construction the unique λ S -weakly decreasing saturated chain from u to v. □

Meet and join operations, sublattices, and lattices.

Here we give some sufficient conditions on S for the fact that each S(n), n ⩾ 0, is a lattice.

First, when S is spread and, for any n ⩾ 0 and any

u, v ∈ S(n), u ∧ v ∈ S (resp. u ∨ v ∈ S), by [Sta11], each S(n) is a lattice. Moreover, when both u ∧ v ∈ S and u ∨ v ∈ S, each S(n) is a sublattice of Cl δ (n).
Again by [START_REF] Stanley | Enumerative Combinatorics[END_REF], S(n) is in this case distributive and graded.

Second, assume instead that S is minimally extendable. For any n ⩾ 0, the S-decrementation map is the map ⇓ S : Cl δ (n) → S(n) defined recursively by ⇓ S (ε) := ε and, for any (1.3.2)

Observe that the fact that S is minimally extendable ensures that ⇓ S is a well-defined map. Let also, for any n ⩾ 0 and

u, v ∈ S(n), u ∧ S v := ⇓ S (u ∧ v).
When S is maximally extendable, we denote by ⇑ S the S-incrementation map defined in the same way as the S-decrementation map with the difference that in the previous definitions, the operation max is replaced by the operation min and the relation ⩽ is replaced by the relation ⩾. Here, the fact that S is maximally extendable ensure that ⇑ S is well-defined. We also define the operation ∨ S in the same way as ∧ S with the difference that in the previous definitions, the map ⇓ S is replaced by ⇑ S and the operation ∧ is replaced by the operation ∨.

Theorem 1.3.3. Let δ be a range map and S be a closed by prefix and minimally (resp. maximally) extendable graded subset of Cl δ . The operation ∧ S (resp. ∨ S ) is, for any n ⩾ 0, the meet (resp. join) operation of the poset S(n).

Proof. Let us show the property of the statement of the theorem in the case where S is minimally extendable. The other case is symmetric. We proceed by induction on n ⩾ 0. When n = 0, the property is trivially satisfied.

Let n ⩾ 1 and u, v ∈ S(n). Since S is closed by prefix, one has u = u ′ a and v = v ′ b with u ′ , v ′ ∈ S(n -1) and a, b ∈ N. Since S is minimally extendable, u ∧ S v = u ′ a ∧ S v ′ b = ⇓ S u ′ ∧ v ′ min{a, b} = ⇓ S u ′ ∧ v ′ c (1.3.3) where c := max{c ⩽ min{a, b} : ⇓ S (u ′ ∧ v ′ ) c ∈ S}. Now, by induction hypothesis, we obtain ⇓ S u ′ ∧ v ′ c = u ′ ∧ S v ′ c (1.3.4)
where ∧ S is the meet operation of the poset S(n -1). First, we deduce from the above computation that for any i ∈ [n], the i-th letter of u ∧ S v is nongreater than min{u i , v i }, and that u ∧ S v belongs to S(n). Therefore, u ∧ S v is a lower bound of {u, v}. Second, by induction hypothesis, w ′ := u ′ ∧ S v ′ is the greatest lower bound of {u ′ , v ′ }. By construction, since c is the greatest letter such that c ⩽ a, c ⩽ b, and w ′ c ∈ S holds, any other lower bound of {u, v} is smaller than w ′ c. This prove that w ′ c is the greatest lower bound of {u, v} and implies the statement of the theorem. □ 1.3.3. Join-irreducible elements. Recall that an element x of a lattice L is join-irreducible (resp. meet-irreducible) if x covers (resp. is covered by) exactly one element in L. We denote by J(L) (resp. M(L)) the set of join-irreducible (resp. meet-irreducible) elements of L. These notions are usually considered specially for lattices but we can take the same definitions even when L is just a poset.

Proposition 1.3.4. Let δ be a range map and S be a straight graded subset of Cl δ . For any

n ⩾ 0, u ∈ S(n) is a join-irreducible (resp. meet-irreducible) element of S(n) if and only if there is a k ⩾ 1 and a unique i ∈ [n] such that ↓ k i (u) ∈ S(n) (resp. ↑ k i (u) ∈ S(n)).
Proof. Assume first that u is a join-irreducible element of S(n). Then, there is exactly one

element u ′ of S such that u ′ ⋖ S u. Since S is straight, #D(u ′ , u) = 1, implying that u satisfies the stated condition.
Conversely, assume that u satisfies the stated condition. Assume that there are u ′ , u ′′

∈ S(n) such that u ′ ⋖ S u and u ′′ ⋖ S u. Since S is straight, there exist i ′ , i ′′ ∈ [n] and k ′ , k ′′ ⩾ 1 such that u ′ = ↓ k ′ i ′ (u) and u ′′ = ↓ k ′′ i ′′ (u). Due to the property satisfied by u, i ′ = i ′′ , so that u ′ = u ′′ since u ′
and u ′′ are both covered by u. Therefore, u is join-irreducible.

The part of the statement of the proposition concerning the meet-irreducible elements is symmetric. □ 1.3.4. Constructibility by interval doubling. We denote by 2 the poset {0, 1} endowed with the natural order relation on integers. Let (P, ≼) be a poset and I one of its intervals. The interval doubling of I in P is the poset P[I] := (P \ I) ⊔ (I × 2), having ≼ ′ as order relation, which is defined as follows. For any x, y ∈ P[I], one has x ≼ ′ y if one of the following assertions is satisfied: This operation has been introduced in [START_REF] Day | Doubling constructions in lattice theory[END_REF] as an operation on posets preserving the property to being a lattice. On the other way round, we say that P is obtained by an interval contraction from a poset P ′ if there is an interval

(i) x ∈ P \ I,
I of P such that P[I] is isomorphic as a poset to P ′ [CLCdPBM04].
A lattice L is constructible by interval doubling (spelled as "bounded" in the original article) if L is isomorphic as a poset to a poset obtained by performing a sequence of interval doubling from the singleton lattice. It is known from [Day79] that such lattices are semi-distributive. Recall that a finite lattice L is constructible by interval doubling if and only if it is congruence uniform, and then in particular, the number of join-irreducible elements of L determines the number of interval doubling steps needed to create L (see [Day79] and [Müh19]).

The aim of this section is to introduce a sufficient condition on a graded subset S of Cl δ for the fact that each S(n), n ⩾ 0, is constructible by interval doubling. We shall moreover describe explicitly the sequence of interval doubling operations involved in the construction of S(n) from the trivial lattice.

Let P be a nonempty subposet of Cl δ (n) for a given fixed size n ⩾ 1. Let us denote by m(P) the letter max{u n : u ∈ P}. For any a, b ∈ δ(n)], let P a := {u ∈ P : u n = a} and P a,b := {ub : ua ∈ P a }. Observe that P a is a subposet of P while P a,b may contain δ-cliffs that do not belong to P. The derivation of P is the set

D(P) := P 0 ∪ P 1 ∪ • • • ∪ P m(P)-1 ∪ P m(P),m(P)-1 . (1.3.5)
In other words, D(P) is the set of all the cliffs obtained from P by decrementing their last letters if they are equal to m(P) or by keeping them as they are otherwise. Observe that D(P) is not necessarily a subposet of P. Nevertheless, D(P) is still a subposet of Cl δ (n). Observe also that m(D(P)) ⩽ m(P) -1. For instance, by considering the subposet P := {0000, 0111, 0002, 0112, 0103, 0104, 0004} (1.3.6) of Cl 2 (4), we have P 2,m(P) = {0004, 0114} and D(P) = {0000, 0111, 0002, 0112, 0103, 0003}.

The subposet P is nested if it is nonempty and (N1) for any a ∈ m(P)], the δ-cliff 0 n-1 a belongs to P; (N2) for any a ∈ m(P)], P a,m(P) is both a subset and an interval of P.

This definition still holds when m(P) = 0. Observe that any δ-cliff 0 n-1 a, a ⩾ 1, of P covers exactly the single element 0 n-1 (a -1) of P. This element exists by (N1). Therefore, when P is a lattice, these δ-cliffs are join-irreducible.

Lemma 1.3.5. Let δ be a range map and P be a nonempty subposet of Cl δ (n) for an n ⩾ 1. If P is nested, then for any a ∈ m(P)], P a is an interval of P.

Proof. First, by (N1), P a admits 0 n-1 a as unique least element. It remains to prove that P a has at most one greatest element. By contradiction, assume that there are in P a two different greatest elements ua and va, where u, v ∈ Cl δ (n -1). Then, by setting b := m(P), in P a,b the δ-cliffs ub and vb are still incomparable. Since these two elements are also greatest elements of P a,b , this implies that P a,b is not an interval in P. This contradicts (N2). □

I = P b ′ is an interval of P ′ . Let u, v ∈ P b ′ such that u ≼ v. Assume that there exists w ∈ P ′ b ′ such that u ≼ w ≼ v. Let us denote by u ′ (resp. v ′ , w ′ ) the prefix of size n -1 of u (resp. v, w). By (N2), u ′ b and v ′ b belong to P b . Moreover, by Lemma 1.3.6, since P ′ b ′ = P b,b ′ , w ∈ P b,b ′ . Therefore, w ′ b
:= ub, if ub ′ ∈ P ′ \ P b ′ , (1.3.7b) φ ub ′ , 1 := ub ′ , if ub ′ , 1 ∈ P b ′ × 2, (1.3.7c) φ ub ′ , 2 := ub, if ub ′ , 2 ∈ P b ′ × 2. (1.3.7d)
This map φ is well-defined because, respectively, one has P ′ a = P a for any a ∈ b ′ -1],

Lemma 1.3.6 holds, I is in particular a subset of P, and P satisfies (N2). Let now ψ : P → P ′ [I] be the map satisfying

ψ(ua) = ua, if ua ∈ P and a ∈ b ′ -1 , (1.3.8a) ψ(ub) = ub ′ , if ub ′ ∈ P ′ \ P b ′ , (1.3.8b) ψ(ub) = ub ′ , 2 , if ub ′ ∈ P b ′ , (1.3.8c) ψ ub ′ = ub ′ , 1 , if ub ′ ∈ P b ′ . (1.3.8d)
By similar arguments as before, this map ψ is well-defined. Moreover, by construction, ψ is the inverse of φ. Therefore, φ is a bijection. The fact that φ is a poset embedding comes by definition of φ and from the fact that, due to the property of P to be nested, for any ub ′ ∈ P ′ \ P b ′ , all elements greater than ub ′ in P ′ do not belong to P b ′ . Thus, P ′ [I] is isomorphic as a poset to P. □ By assuming that P is nested, the sequence of derivations from P is the sequence P, D(P), D 2 (P), . . . , D m(P) (P) (1.3.9) of subsets of Cl δ (n). Observe that due to (N1), for any k ∈ [m(P) -1], m D k (P) ⩾ 1, so that D k+1

(P) is well-defined.

Given a graded subset S of Cl δ , we say by extension that S is nested if for all n ⩾ 0, the posets S(n) are nested.

Theorem 1.3.9. Let δ be a rooted range map and S be a nested and closed by prefix graded subset of Cl δ . For any n ⩾ 1, S(n) is constructible by interval doubling. Moreover,

S(n) → D(S(n)) → • • • → D m(S(n)) (S(n)) ≃ S(n -1) → D(S(n -1)) → • • • → D m(S(n-1)) (S(n -1)) ≃ S(n -2) → • • • → S(0) ≃ {ε} (1.3.10)
is a sequence of interval contractions from S(n) to the trivial lattice {ε}.

Proof. We proceed by induction on n ⩾ 0. If n = 0, since δ is rooted, we necessarily have S(0) ≃ {ε}, and this poset is by constructible by interval doubling. Assume now that n ⩾ 1 and set P := S(n). Since S is nested, the sequence of reductions from P is well-defined. By Lemmas 1.3.7 and 1.3.8, by setting P ′ := D m(P) (P), P is obtained by performing a sequence of interval doubling from the poset P ′

. Now, due to the definition of the derivation algorithm D, P ′ is made of the δ-cliffs of P wherein the last letters have been replaced by 0. This poset P ′ is therefore isomorphic to the poset P ′′ formed by the prefixes of length n -1 of P. Since S is closed by prefix, P ′′ is thus the poset S(n -1). By induction hypothesis, this last poset is constructible by interval doubling. Therefore, S(n) also is. All this produces the sequence (1.3.10) of interval contractions. □ 1.3.5. Elevation maps. We introduce here a combinatorial tool intervening in the study of the three Fuss-Catalan posets introduced in the sequel.

Let S be a closed by prefix graded subset of Cl δ . For any u ∈ S, let F S (u) := {a ∈ δ(|u| + 1)] : ua ∈ S}.

(1.3.11)

By definition, F S (u) is the set of all the letters a that can follow u to form an element of S.

For any n ⩾ 0, the S-elevation map is the map e S : S(n) → Cl δ (n) defined, for any u ∈ S(n) and i ∈ [n], by e S (u

) i := #(F S (u 1 . . . u i-1 ) ∩ u i -1]) (1.3.12)
for any i ∈ [n]. From an intuitive point of view, the value of the i-th letter of e S (u) is the number of cliffs of S obtained by considering the prefix of u ending at the letter u i and by replacing this letter by a smaller one. Remark in particular that e Cl δ is the identity map. Besides, we say that any u ∈ S is an exuviae if e S (u) = u.

Let E S be the graded set wherein for any n ⩾ 0, E S (n) is the image of S(n) by the S-elevation map. We call this set the S-elevation image. Observe that E S is a graded subset of Cl δ . Note also that for any u ∈ S, e S (u) ≼ u.

Proposition 1.3.10. Let δ be a range map and S be a closed by prefix graded subset of Cl δ . For any n ⩾ 0, the S-elevation map is injective on the domain S(n). Proof. We proceed by induction on n. When n = 0, the property is trivially satisfied. Let u, v ∈ S(n) such that n ⩾ 1 and e S (u) = e S (v). Proof. Let n ⩾ 0 and v ∈ E S (n). Then, there exists u ∈ S(n) such that e S (u

) = v. Let v ′ be a prefix of v. Since S is closed by prefix, the prefix u ′ of u of length n ′ := |v ′ | belongs to S(n ′
). Moreover, by definition of e S , we have e S (u ′ ) = v ′ . Therefore, v ′ ∈ E S , implying the statement of the lemma. □ Proposition 1.3.12. Let δ be a range map and S be a closed by prefix graded subset of Cl δ such that for any u, v ∈ S, u ≼ v implies F S (v) ⊆ F S (u). For any n ⩾ 0, the map e -1 S is a poset morphism from E S (n) to S(n). Proposition 1.3.12 says that when S is closed by prefix, for any n ⩾ 0, the poset S(n) is an order extension of E S (n).

1.3.6. Geometric cubic realizations. Let S be a graded subset of Cl δ . For any n ⩾ 0, the realization of S(n) is the geometric object C(S(n)) defined in the space R n and obtained by placing for each u ∈ S(n) a vertex of coordinates (u 1 , . . . , u n ), and by forming for each u, v ∈ S(n) such that u ⋖ S v an edge between u and v. Remark that the posets of Figure 1 represent actually the realizations of δ-cliff posets. We will follow this drawing convention for all the next figures of posets in all the sequel. When S is straight, every edge of C(S(n)) is parallel to a line passing by the origin and a point of the form (0, . . . , 0, 1, 0, . . . , 0). In this case, we say that C(S(n)) is cubic.

As a side remark, we would like to stress that the present notion of geometric realization of a poset differs from the usual one saying that it consists in the geometric realization of the simplicial complex of the chain of the poset.

Let us assume from now that S is straight. Let u, v ∈ S(n) such that u ≼ v. The word u is cell-compatible with v if for any word w of length n such that for any i ∈ [n], w i ∈ {u i , v i }, then w ∈ S. In this case, we call cell the set of points ⟨u, v⟩

:= {x ∈ R n : u i ⩽ x i ⩽ v i for all i ∈ [n]}. (1.3.13)
By definition, a cell is an orthotope, that is a parallelotope whose edges are all mutually orthogonal or parallel. A point x of R n is inside a cell ⟨u, v⟩ if for any i ∈ [n], u i ̸ = v i implies u i < x i < v i . A cell ⟨u, v⟩ is pure if there is no point of S(n) inside ⟨u, v⟩. In other terms, this says that for all w ∈ [u, v], there exists i ∈ [n] such that u i ̸ = v i and w i ∈ {u i , v i }. Two cells ⟨u, v⟩ and ⟨u ′ , v ′ ⟩ of C(S(n)) are disjoint if there is no point of R n which is both inside ⟨u, v⟩ and ⟨u ′ , v ′ ⟩. The dimension dim ⟨u, v⟩ of a cell ⟨u, v⟩ is its dimension as an orthotope and it satisfies dim ⟨u, v⟩ = #D(u, v). The volume vol ⟨u, v⟩ of ⟨u, v⟩ is its volume as an orthotope and its satisfies

vol ⟨u, v⟩ = i∈D(u,v) v i -u i .
(1.3.14)

For any k ⩾ 0, the k-volume vol k (C(S(n))) of C(S(n))
is the volume obtained by summing the volumes of all its all its cells of dimension k, computed by not counting several times potential intersecting orthotopes. The volume

vol(C(S(n))) of C(S(n)) is defined as vol k (C(S(n)))
where k is the largest integer such that C(S(n)) has at least one cell of dimension k.

Figure 3 shows examples of these notions. Figure 3a shows a cubic realization wherein 00 is cell-compatible with 12. Hence, ⟨00, 12⟩ is a cell. The point 1 2 , 3 2 ∈ R 2 is inside ⟨00, 12⟩, and since there are no elements of the poset inside the cell, this cell is pure. Figure 3b shows a cubic realization wherein 00 is not cell-compatible with 22 because 02 does not belong to the poset. Nevertheless, ⟨00, 11⟩, ⟨10, 21⟩, and ⟨11, 22⟩ are pure cells of dimension 2. Figure 3c shows a cubic realization wherein ⟨00, 22⟩ is a non-pure cell. Indeed, the δ-cliff 11 is an element of the poset and is inside this cell. Finally, Figure 3d shows a cubic realization having 1 as volume since there is exactly one cell ⟨000, 111⟩ of maximal dimension (which is 3) and of volume 1. Its 2-volume is 8 since this cubic realization decomposes as the seven disjoint cells ⟨000, 011⟩, ⟨000, 101⟩, ⟨000, 110⟩, ⟨001, 111⟩, ⟨010, 111⟩, ⟨100, 111⟩, and ⟨101, 113⟩ of respective volumes 1, 1, 1, 1, 1, 1, and 2.

There is a close connection between output-wings (resp. input-wings) of S(n), n ⩾ 0, and the computation of the volume of C(S(n)): if ⟨u, v⟩ is a cell of maximal dimension of C(S(n)), then due to the fact that S is straight, u (resp. v) is an output-wing (resp. input-wing) of S(n). When for any n ⩾ 0, (i) there is a map ρ :

O(S)(n) → I(S)(n); (ii) all cells of maximal dimension of C(S(n)) express as ⟨u, ρ(u)⟩ with u ∈ O(S)(n); (iii) all cells of {⟨u, ρ(u)⟩ : u ∈ O(S)(n)} are pairwise disjoint; then the volume of C(S(n)), n ⩾ 0, writes as vol(C(S(n))) = u∈O(S)(n) vol ⟨u, ρ(u)⟩ .
(1.3.15)

When some cells of {⟨u, ρ(u)⟩ : u ∈ O(S)(n)} intersect each other, the expression for the volume would not be at as simple as (1.3.15) and can be written instead as an inclusion-exclusion formula. Of course, the same property holds when ρ is instead a map from I(S)(n) to O(S)(n) by changing accordingly the previous text.

Recall that the order dimension [Tro92] of a poset P is the smallest nonnegative integer k such that there exists a poset embedding of P into N k , ≼ where ≼ is the componentwise partial order. Recall that the hypercube of dimension n ⩾ 0 is the poset H n on the set of the subsets of [n] ordered by set inclusion. It can be shown that the order dimension of H n is n.

Proposition 1.3.13. Let δ be a range map and S be a straight graded subset of Cl δ . If, for an n ⩾ 0, C(S(n)) has a cell of dimension dim n (δ), then the order dimension of the poset S(n) is dim n (δ).

Proof. First, since S(n) is a subposet of Cl δ (n), S(n) is a subposet of the Cartesian product N k
where k := #{i ∈ [n] : δ(i) ̸ = 0}. This poset has order dimension dim n (δ), so that the order dimension of S(n) is at most dim n (δ). Besides, since S is straight, the notion of cell is welldefined in the cubic realization of S(n). By hypothesis, S(n) contains a cell ⟨u, v⟩ of dimension dim n (δ). Thus, there is a poset embedding of H dim n (δ) into the interval [u, v] of S(n). Therefore, the order dimension of S(n) is at least dim n (δ). □

As a particular case of Proposition 1.3.13, the order dimension of Cl δ (n) is dim n (δ). This explains the terminology of "n-th dimension of δ" for the notation dim n (δ) introduced in Section 1.1.1.

SOME FUSS-CATALAN POSETS

We present here some examples of subposets of δ-cliff posets. We focus in this work on three posets whose elements are enumerated by m-Fuss-Catalan numbers for the case δ = m, m ⩾ 0. We provide some combinatorial properties of these posets like among others, a description of their input-wings, output-wings, and butterflies, a study of their order theoretic properties, and a study of their cubic realizations. We end this section by establishing links between these three families of posets in terms of poset morphisms, poset embeddings, and poset isomorphisms. We shall omit some straightforward proofs (for instance, in the case of the descriptions of input-wings, output-wings, butterflies, meet-irreducible and join-irreducible elements of the posets -the descriptions of these two families use Proposition 1.3.4).

We use the following notation conventions. Poset morphisms are denoted through arrows , poset embeddings through arrows , and poset isomorphisms through arrows .

2.1. δ-avalanche posets. We begin by introducing a first Fuss-Catalan family of posets. As we shall see, these posets are not lattices but they form an important tool to study the next two families of Fuss-Catalan posets.

2.1.1. Objects. For any range map δ, let Av δ be the graded subset of Cl δ containing all δ-cliffs u such that for all nonempty prefixes u ′ of u, then ω(u ′ ) ⩽ δ(|u ′ |). Any element of Av δ is a δ-avalanche. For instance, Av 2 (3) = {000, 001, 002, 003, 004, 010, 011, 012, 013, 020, 021, 022}.

(2.1.1) Proposition 2.1.1. For any weakly increasing range map δ, the graded set Av δ is

(i) closed by prefix; (ii) is minimally extendable; (iii) is maximally extendable if and only if δ

= 0 ω .
Proof. Point (i) is an immediate consequence of the definition of δ-avalanches. Let n ⩾ 0 and u ∈ Av δ (n). Since δ(n + 1) ⩾ δ(n), u0 is a δ-avalanche. This establishes (ii). Finally, we have immediately that Av 0 ω is maximally extendable. Moreover, when δ ̸ = 0 ω , there is an n ⩾ 1 such that δ(n) ⩾ 1 and δ(n ′ ) = 0 for all 1 ⩽ n ′ < n. Therefore, 0 n-1 δ(n) is a δ-avalanche but 0 n-1 δ(n) δ(n + 1) is not. Therefore, (iii) holds. □ Proposition 2.1.2. For any m ⩾ 0 and n ⩾ 0, #Av m (n) = cat m (n).

Proof. This is a consequence of Proposition 2. Let δ be a weakly increasing range map. Notice that in general, Av

δ (n) is not bounded. Since for all u ∈ Av δ (n), ω(u) ⩽ δ(n), we have u ∈ max ≼ Av δ (n) if and only if ω(u) = δ(n).
Moreover, due to the fact that any δ-cliff obtained by decreasing a letter in a δ-avalanche is also a δ-avalanche, the poset Av δ (n) is the order ideal of Cl δ (n) generated by max ≼ Av δ (n). Finally, as a particular case, we shall show as a consequence of upcoming Proposition 2.2.7 that for any m ⩾ 0 and n ⩾ 1, # max ≼ Av m (n) = cat m (n -1).

Proposition 2.1.3. For any weakly increasing range map δ and n ⩾ 0, the poset Av δ (n) The four posets of avalanches, input-wings, output-wings, and butterflies are linked in the following way.

(i) is straight, where u ∈ Av δ (n) is covered by v ∈ Av δ (n) if and only if there is an i ∈ [n] such that ↑ i (u) = v; (ii) is coated; (iii)

is graded, where the rank of an avalanche is its weight; (iv) admits an EL-labeling; (v) is a meet semi-sublattice of

Theorem 2.1.5. For any m ⩾ 1 and n ⩾ 0,

Av m-1 (n) I(Av m )(n) O(Av m )(n) B(Av m+1 )(n) φ 1 φ 2 φ 1 (2.1.

3) is a diagram of poset embeddings or isomorphisms, where the maps φ

1 and φ 2 are defined, for any u ∈ N n and i ∈ [n], by φ 1 (u) i :=↿ i̸ =1 (u i + 1) and φ 2 (u) i :=↿ i̸ =1 (u i -1). Proof. This follows from the descriptions of the input-wings, output-wings, and butterflies of Av m (n) provided by Proposition 2.1.4. □ Figure 5 gives an example of the poset isomorphisms or embeddings described by the statement of Theorem 2.1.5. As a consequence of Theorem 2.1.5, for any m ⩾ 1 and n ⩾ 0, (t) has no constant term. Since any m-Dyck path decomposes in a unique way as a concatenation of indecomposable m-Dyck paths, one has G(t) = (1 -G ′ (t)) -1 . Now, by using the fact that G(t) satisfies G(t) = 1 + tG(t) m+1 , we have

G ′ (t) = G(t) -1 G(t) = tG(t) m = t 1 1 -G ′ (t) m (2.1.5)
This relation satisfied by G ′ (t) between the first and last members of (2.1.5) is known to be the one of the generating series of twisted m-Fuss-Catalan numbers (see [Slo]

v i ∈ {φ 2 (u) i , u i } for all i ∈ [n]. By definition of φ 2 , v 1 = 0 and v i ∈ {u i -1, u i } for all i ∈ [2, n].
Since u is an input-wing of Av m , φ 2 (u) is an m-avalanche, and due to the definition of m-avalanches, any m-cliff obtained by decrementing some letters of u is still an m-avalanche. Thus, v ∈ Av m and (i) holds. Points (ii) and (iii) are consequences of the fact that there is no element of Av m (n) inside a cell ⟨φ 2 (u), u⟩. Indeed, since for any i ∈

[n], |φ 2 (u) i -u i | ⩽ 1, we have v i ∈ {φ 2 (u) i , u i } for all v ∈ ⟨φ 2 (u), u⟩ ∩ Av m (n). □
As shown by Proposition 2.1.8, the cells of maximal dimension of the cubic realization of Av m (n) are all of the form ⟨φ 2 (u), u⟩ where the u are input-wings of Av m (n).

Proposition 2.1.9. For any m ⩾ 1 and n ⩾ 0, vol(C(Av

m (n))) = cat m-1 (n).
Proof. Proposition 2.1.8 describes all the cells of maximal dimension of C(Av m (n)) as cells ⟨φ 2 (u), u⟩ where u is an input-wing of Av m (n). Since all these cells are pairwise disjoint, the volume of C(Av m (n)) expresses as (1.3.15). Moreover, observe that the volume of each cell ⟨φ 2 (u), u⟩ where u in an input-wing is by definition of φ 2 equal to 1. Therefore, vol(C(Av m (n))) is equal to the number of input-wings of Av m (n). The statement of the proposition follows now from Theorem 2.1.5. □ 2.2. δ-hill posets. We now introduce δ-hills and δ-hill posets as subposets of δ-cliff posets. As we shall see, some of these posets are sublattices of m-cliff lattices.

2.2.1. Objects. For any range map δ, let Hi δ be the graded subset of Cl δ containing all δ-cliffs such that that for any i ∈ Proof. Point (i) is an immediate consequence of the definition of δ-hills. We have immediately that Hi 0 ω is minimally extendable. Moreover, when δ ̸ = 0 ω , there is an n ⩾ 1 such that δ(n) ⩾ 1. Therefore, 1δ (n) is a δ-hill but 1δ (n) 0 is not. This establishes (ii). Finally, since for any n ⩾ 0, δ(n + 1) ⩾ δ(n), one has δ(n + 1) ⩾ u n for any u ∈ Hi δ (n). This shows that u δ(n + 1) is a δ-hill.

[|u| -1], u i ⩽ u i+1

Therefore, (iii) holds. □

For any m ⩾ 0, an m-Dyck path of size n is a path in from (0, 0) to ((m +1)n, 0) in N 2 staying above the x-axis, and consisting only in steps of the form (1, -1), called down steps, or steps of the form (1, m), called up steps. We denote by Dy m the graded set of all m-Dyck paths. There is a one-to-one correspondence between Hi m (n) and Dy m (n) wherein an m-Dyck path w of size n is sent to the m-hill u of size n such that for any i ∈ [n], u i is the number of down steps to the left of the i-th up step of w. For instance, the 2-Dyck path (2.2.2) is sent to the 2-hill 02366. Since m-Dyck paths of size n are known to be enumerated by m-Fuss-Catalan numbers, one has #Hi m (n) = cat m (n).

Proposition 2.2.2. For any range map δ and any n ⩾ 0, E

Hi δ (n) = Av δ (n). Proof. First, since Hi δ is by Proposition 2.2.1 closed by prefix, the Hi δ -elevation map and the Hi δ -elevation image are well-defined. Let u ∈ Hi δ (n) and v := e Hi δ (u). By definition of δ-hills and of the Hi δ -elevation map, we have v 1 = u 1 and, for any Proposition 2.2.3. For any weakly increasing range map δ and n ⩾ 0, the poset Hi δ (n) is

i ∈ [2, n], v i = u i -u i-1 . Therefore, for any prefix v ′ := v 1 . . . v j , j ∈ [n], of v, we have ω v ′ = u 1 + (u 2 -u 1 ) + (u 3 -u 2 ) + • • • + u j -u j-1 = u j . (2.2.3) Since u is in particular a δ-cliff of size n, then u j ⩽ δ(j), so that v ∈ Av δ (n). This shows that E Hi δ (n) is a subset of Av δ (n).
(u ′ ) = v ′ n-1 . Since ω(u ′ ) + a = ω(u) ⩽ δ(n), we have that b ⩽ δ(n). Therefore, since moreover b ⩾ v ′ n-1 , v is a δ-hill
(i) straight, where u ∈ Hi δ (n) is covered by v ∈ Hi δ (n) if
< • • • < u |u| ; (ii) the graded set O(Hi m ) contains all the m-cliffs u satisfying u 1 ⩽ u 2 < • • • < u |u|

and for all i ∈ [2, |u|], u i < m(i); (iii) the graded set B(Hi m ) contains all the m-cliffs u satisfying u 1 < • • • < u |u| and for all i ∈ [2, |u|], u i < m(i).

The four posets of hills, input-wings, output-wings, and butterflies are linked in the following way.

Theorem 2.2.5. For any m ⩾ 1 and n ⩾ 0,

Hi m-1 (n) I(Hi m )(n) O(Hi m )(n) B(Hi m+1 )(n) φ 3 I φ 2 (2.2.4)
is a diagram of poset embeddings or isomorphisms, where the map φ 3 is defined for any u ∈ N n and i ∈ [n] by φ 3 (u) i := u i + i -1, I is the identity map, and φ 2 is the map defined in the statement of Theorem 2.1.5.

Proof. This follows from the descriptions of the input-wings, output-wings, and butterflies of Hi m (n) provided by Proposition 2.2.4. □ Figure 7 gives an example of the poset isomorphisms or embeddings described by the statement of Theorem 2.2.5. As a consequence of Theorem 2.2.5, for any m ⩾ 1 and n ⩾ 0, the number of input-wings in Hi m (n) is cat m-1 (n). -cliffs v of size n satisfying v i-1 ⩽ v i < m ′ (i). A possible bijection between these two sets sends any u ∈ B(Hi m )(n) to the m ′ -cliff v of the same size such that for any i ∈ [n], v i = u i -i + 1. We have already seen in the proof of Proposition 2.1.6 that these sets are in one-to-one correspondence with (m -1)-Dyck paths which cannot be written as a nontrivial concatenation of two (m -1)-Dyck paths. Therefore, the statement of the proposition follows. □ Proposition 2.2.7. For any m ⩾ 0 and n ⩾ 1, the map ρ

: max ≼ Av m (n) → Hi m (n -1) such that any u ∈ max ≼ Av m (n), ρ(u) is the prefix of size n -1 of e -1
Hi m (u), is a bijection. Proof. First, since Hi m is by Proposition 2.2.1 closed by prefix, by Proposition 1.3.10, e

Hi m is an injective map. This implies that the map ρ, defined by considering the inverse of e

Hi m is a well-defined map. Let ρ ′ : Hi m (n-1) → max ≼ Av m (n) be the map defined for any v ∈ Hi m (n-1) by ρ ′ (v) := e Hi m (va) where a := m(n -1). As pointed out before, u ∈ max ≼ Av m (n) if and only if ω(u) = m(n -1). This implies that ρ ′ (v) belongs to max ≼ Av m (n). Moreover, due to the respective definitions of ρ and ρ ′ , both ρ • ρ ′ and ρ ′ • ρ are identity maps. Therefore, ρ is a bijection. □ Proposition 2.2.8. For any m ⩾ 1 and n ⩾ 1, the set J(Hi m (n)) contains all m-hills u such that u = 0 k a n-k such that k ∈ [n -1] and a ∈ [km].

Proposition 2.2.9. For any m ⩾ 0 and n ⩾ 0, the map e Hi m is a bijection between J(Hi m (n)) and J(Av m (n)).

Proof. This is a straightforward verification using the descriptions of join-irreducible elements of Hi m (n) and Av m (n) brought by Propositions 2.2.8 and 2.1.7. □ By Proposition 2.2.8 (or also by Propositions 2.1.7 and 2.2.9), the number of join-irreducibles elements of Hi m (n) satisfies, for any m ⩾ 1 and n ⩾ 1, #J(Hi m (n)) = m n 2 . Since by Proposition 2.2.3, Hi m (n) is constructible by interval doubling, this is also the number of its meetirreducible elements [START_REF] Grätzer | Lattice Theory: Special Topics and Applications[END_REF].

Cubic realization. The map φ

2 introduced in Theorem 2.2.5 is used here to describe the cells of maximal dimension of the cubic realization of Hi m (n), m ⩾ 1, n ⩾ 0. Proposition 2.2.10. For any m ⩾ 1, n ⩾ 0, and u ∈ I(Hi m )(n),

(i) the m-hill φ 2 (u) is cell-compatible with the m-hill u; (ii) the cell ⟨φ 2 (u), u⟩ is pure; (iii) all cells of {⟨φ 2 (u), u⟩ : u ∈ I(Hi m )(n)} are pairwise disjoint. Proof.
Due to the similarity between the maps φ 2 and the map φ 1 introduced in the statement of Theorem 2.1.5, the proof here is very similar to the one of Proposition 2.1.8. □

As shown by Proposition 2.2.10, the cells of maximal dimension of the cubic realization of Hi m (n) are all of the form ⟨φ 2 (u), u⟩ where the u are input-wings of Hi m (n).

Proposition 2.2.11. For any m ⩾ 1 and n ⩾ 0, vol(C(Hi m (n))) = cat m-1 (n).

Proof. Proposition 2.2.10 describes all the cells of maximal dimension of C(Hi m (n)) as cells ⟨φ 2 (u)⟩ , u where u is an input-wing of Hi m (n). Since all these cells are pairwise disjoint, the volume of C(Hi m (n)) expresses as (1.3.15). Moreover, observe that the volume of each cell ⟨φ 2 (u), u⟩ where u in an input-wing, is by definition of φ 2 equal to 1. Therefore, vol(C(Hi m (n))) is equal to the number of input-wings of Hi m (n). The statement of the proposition follows now from Theorem 2.2.5. □

δ-canyon posets.

We introduce here our last family of posets. They are defined on particular δ-cliffs called δ-canyons. As we shall see, under some conditions these posets are lattices but not sublattices of δ-cliff lattices.

2.3.1. Objects. For any range map δ, let Ca δ be the graded subset of Cl δ containing all δ-cliffs such that u i-j ⩽ u i -j, for all i ∈ [|u|] and j ∈ [u i ] satisfying i -j ⩾ 1. Any element of Ca δ is a δ-canyon. For instance Ca 2 (3) = {000, 010, 020, 001, 002, 012, 003, 013, 023, 004, 014, 024}.

(2.3.1)

As a larger example, the 2-cliff u := 020100459002301 is a 2-canyon. Indeed, by picturing an m-canyon u by drawing for each position i ∈ [|u|] a segment from the point (i -1, 0) to the point (i -1, u i ) in the Cartesian plane, the previous condition says that one can draw lines of slope 1 passing through the x-axis and the top of each segment without crossing any segment. For instance, the previous u is drawn as

(2.3.2)
and one can observe that none of its diagonals, drawn as dotted lines, crosses a segment. Besides, if u is a δ-cliff of size n and i, j ∈ [n] are two indices such that i < j, one has the three following possible configurations depending on the value α := u j -(j -i): ⋆ If α < 0, then we say that i and j are independent in u (graphically, the diagonal of u j falls under the x-axis before reaching the segment of u i ); ⋆ If α ∈ u i -1], then we say that j is hindered by i in u (graphically, the diagonal of u j hits the segment of u i ); ⋆ If α ⩾ u i , then we say that j dominates i in u (graphically, the segment of u i is below or on the diagonal of u j ).

By definition, a δ-cliff u is a δ-canyon if no index of u is hindered by another one.

Proposition 2.3.1. For any range map δ, the graded set Ca δ is (i) closed by prefix; (ii) is minimally extendable; (iii) is maximally extendable if δ is increasing.

Proof. Let u be a δ-canyon of size n ⩾ 0. Immediately from the definition of the δ-canyons, it follows that u 0 is a δ-canyon of size n + 1, and that for any prefix u ′ of u, u ′ is a δ-canyon. Therefore, Points (i) and (ii) check out. Let us now consider the δ-cliff u ′ := u δ(n + 1). If δ is increasing, for all j ∈ [n], u n+1-j ⩽ u n+1 -j. Therefore, u ′ is a δ-canyon. Therefore, (iii) holds. □

Let us now introduce a series of definitions and lemmas in order to show that the sets Ca δ (n) and Hi δ (n) are in one-to-one correspondence when δ is an increasing range map.

For any δ-canyon u of size n, let d(u) be the δ-canyon obtained by changing for each index

i ∈ [n] the letter u i into 0 if i is dominated by another index j ∈ [i + 1, n]. For instance, when δ = m with m = 2, d(020050012) = 000050002. Observe that u ∈ Ca δ is an exuviae (see Section 1.3.5) if and only if d(u) = u.

Lemma 2.3.2. For any range map δ and any δ-canyon u, F

Ca δ (u) = F Ca δ (d(u)). Proof. Assume that u is of size n and set w := d(u). Assume that ua is a δ-canyon for a letter a ∈ N. Then, the index n + 1 is hindered by no other index in ua. Since w is obtained by changing to 0 some letters of u, the index n + 1 remains hindered by no other index in wa. Therefore, wa is also a δ-canyon. Conversely, assume that wa is a δ-canyon for a letter a ∈ N. Then, the index n + 1 is hindered by no other index in wa. By contradiction, assume that ua is not a δ-canyon. This implies that the index n + 1 is hindered by an index i in ua. Let us take i maximal among all indices satisfying this property. Due to the maximality of i, i is dominated by no other index in u so that we have u i = w i . This implies that n + 1 is hindered by i in wa, which contradicts our hypothesis. Therefore, ua is a δ-canyon. □ Lemma 2.3.3. Let δ be a range map a u be a δ-canyon of size n ⩾ 0. Then,

F Ca δ (u) = δ(n + 1)] \ i∈[n] d(u) i ̸ =0 [n + 1 -i, n + d(u) i -i].
(2.3.3)

Proof. Let w be a δ-canyon of size n and let w := d(u). For any letter a ∈ δ(n + 1)], the δ-cliff wa is a δ-canyon if and only if the index n + 1 is hindered by no index in wa. Now, for any i ∈ [n] such that w i ̸ = 0, the index i hinds the index n + 1 in wa if and only if

a ∈ [n + 1 -i, n + w i -i].
By definition of d, all indices of w are pairwise independent. Therefore, for any

i, i ′ ∈ [n] such that i ̸ = i ′ and w i ̸ = 0 ̸ = w i ′ , the sets [n + 1 -i, n + w i -i] and [n + 1 -i ′ , n + w i ′ -i ′
] are disjoint. Lemma 2.3.2 and the fact that d is an idempotent map imply the stated formula. □ Lemma 2.3.4. Let δ be a range map and u be a δ-canyon. Then, ω(e Ca δ (u)) = ω(d(u)). Proof. This follows by induction on the size of u, by using the relation d(u) = e

Ca δ (d(u)), and by using Lemma 2.3.2. □ Proposition 2.3.5. For any increasing range map δ and any n ⩾ 0, E Ca δ (n) = Av δ (n). Proof. First, since Ca δ is by Proposition 2.3.1 closed by prefix, the Ca δ -elevation map and so the Ca δ -elevation image are well-defined. By Lemmas 2.3.3 and 2.3.4, and since δ is increasing, for any δ-canyon u of size n ⩾ 0, one has #F Ca δ (u) = 1 + δ(n + 1) -ω(e Ca δ (u)).

(2.3.4)

Let us proceed by induction on n to prove that for any u ∈ Ca δ (n), e Ca δ (u) is a δ-avalanche. If n = 0, the property holds immediately. Let u = u ′ a be a δ-canyon of size n + 1 where u ′ ∈ Ca δ (n) and a ∈ N. By induction hypothesis, e

Ca δ (u ′ ) is a δ-avalanche. Therefore, in particular, ω(e Ca δ (u ′ )) ⩽ δ(n). Moreover, by (2.3.4), we have

ω e Ca δ u ′ a = ω e Ca δ u ′ + # F Ca δ u ′ ∩ a -1] ⩽ ω e Ca δ u ′ + 1 + δ(n + 1) -ω e Ca δ u ′ -1 = δ(n + 1), (2.3.5)
showing that u ′ a is a δ-canyon.

Conversely, let us prove by induction on n that for any v ∈ Av δ (n), there exists a δ-canyon u such that e Ca δ (u) = v. If n = 0, the property holds immediately. Let v = v ′ b be a δ-avalanche of size n + 1 where v ′ ∈ Av δ (n) and b ∈ N. By induction hypothesis, there is

u ′ ∈ Ca δ (n) such that e Ca δ (u ′ ) = v ′ . Since v is a δ-avalanche, b ⩽ δ(n + 1) -ω(v ′
). Now, by (2.3.4), since there are 1 + δ(n + 1) -ω(v ′

) different letters a such that u ′ a is a δ-canyon, there is in particular a δ-canyon u = u ′ a such that e Ca δ (u) = v. □ Proposition 2.3.6. For any increasing range map δ and any n ⩾ 0, the map e -1 Hi δ • e Ca δ is a bijection between Ca δ (n) and Hi δ (n).

Proof. First, since δ is increasing, by Propositions 2.2.1 and 2.3.1, both Hi δ and Ca δ are closed by prefix. Therefore, the maps e Hi δ and e Ca δ are well-defined. By Proposition 1.3.10, the maps e

Ca m and e Hi m are injective, and by Propositions 2.2.2 and 2.3.5, they both share the same image Av m (n). This implies that e

Ca m is a bijection from Ca m to Av m (n), and that e -1 Hi m is a well-defined map and is a bijection from Av m (n) to Hi m (n). Therefore, the statement of the proposition follows. □

As a consequence of Proposition 2.3.6, for any m ⩾ 0, m-canyons are enumerated by m-Fuss-Catalan numbers.

2.3.2. Posets. For any n ⩾ 0, the subposet Ca δ (n) is the δ-canyon poset of order n. Figure 8 shows the Hasse diagrams of some m-canyon posets. The 1-canyons are also known as Tamari diagrams and have been introduced in [START_REF] Pallo | Enumerating, ranking and unranking binary trees[END_REF]. The set of these objects of size n is in one-to-one correspondence with the set of binary trees with n internal nodes. It is also known that the componentwise comparison of Tamari diagrams is the Tamari order [START_REF] Pallo | Enumerating, ranking and unranking binary trees[END_REF].

Recall that the Tamari order admits, as covering relation, the right rotation operation in binary trees. It has also the nice property to endow the set of binary trees of a given size with a lattice structure [START_REF] Huang | Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law[END_REF]. Besides, a study of the posets of the intervals of the Tamari order, based upon a generalization of Tamari diagrams, has been performed in [Com19]. The Tamari posets admit a lot of generalizations, for instance through the so-called m-Tamari posets [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF] where m ⩾ 0, and through the ν-Tamari posets [START_REF] Préville-Ratelle | The enumeration of generalized Tamari intervals[END_REF] where ν is a binary word. Our δ-canyon posets can be seen as different generalizations of Tamari posets. For any m ⩾ 2, the m-canyon posets are not isomorphic to the m-Tamari posets. Moreover, we shall prove in the sequel that for any increasing map δ, Ca δ is a lattice. As already mentioned, Tamari posets have the nice property to be lattices [START_REF] Huang | Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law[END_REF], are also EL-shellable [START_REF] Björner | Shellable nonpure complexes and posets[END_REF], and constructible by interval doubling [Gey94]. The same properties hold for m-Tamari lattices, see respectively [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] and [START_REF] Mühle | The topology of the m-Tamari lattices[END_REF] for the first two ones. The last one is a consequence of the fact that m-Tamari lattices are intervals of 1-Tamari lattices [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] and the fact that the property to be constructible by interval doubling is preserved for all sublattices of a lattice [Day79]. As we shall see here, the δ-canyon posets have the same three properties.

i ∈ [k], w i = u i ⩽ v i ,
and for any i ∈ [k + 1, n], w i = v i ⩾ u i , the fact that u and v are δ-caynons implies that for any i ∈ [n] and j ∈ [w i ] such that i -j ⩾ 1, the inequality w j ⩾ w i-j + j holds. Thus, w is an δ-canyon, so that (ii) holds. Now, by Lemma 1.3.1, (i) checks out, and by Theorem 1.3.2, (iv) also. Let u and v be two δ-canyons of size n and set w as the δ-cliff u ∧ v. For all j ∈ [w i ] such that i -j ⩾ 1, w i-j ⩽ w i -j. Indeed, either w i-j = u i-j or w i-j = v i-j , and in the two cases w i-j ⩽ (u ∧ v) i -j. For this reason, w is a δ-canyon. This shows (v). Besides, due to the fact that by Proposition 2.3.1, Ca δ is closed by prefix and is maximally extendable, Theorem 1.3.3 implies (vi). Point (vii) is a consequence of Theorem 1.3.9 since (iii) holds and Ca δ is closed by prefix. □

One can observe that Ca m (n) is not a join semi-sublattice of the lattice of δ-cliffs. Indeed, by setting u := 0124 and v := 0205, even if u and v are 2-canyons, u ∨ v = 0225 is not. By Proposition 2.3.7, the posets Ca m (n) are lattices and Theorem 1.3.3 provides a way to compute the join of two of their elements. For instance, in Ca 1 , one has 00120 ∨

Ca 1 00201 = ⇑ Ca 1 (00120 ∨ 00201) = ⇑ These computations of the join of two elements are similar to the ones described in [Mar92] (see also [Gey94]) for Tamari lattices.

Besides, as pointed out by Proposition 2.3.7, when δ is an increasing range map, each Ca δ (n) is constructible by interval doubling. Figure 9 shows a sequence of interval contractions performed from Ca 2 (4) in order to obtain Ca 2 (3). Proof. Let us first prove that ρ is a well-defined map. By Proposition 2.3.8, since for all i ∈ [2, n], u i < m(i), the word u ′ obtained by incrementing by 1 all its letters except the first one is an m-cliff. Moreover, since by Proposition 2.3.1, Ca m is maximally extendable, v := ⇑ Ca m (u ′ ) is a well-defined m-canyon. Since by construction, for all i ∈ [2, n], v i ̸ = 0, each word obtained by replacing by 0 a letter v i in v is an m-canyon. Therefore, v covers n -1 elements of Ca m (n). These elements are obtained by decreasing v i by some value, due to the fact that by Proposition 2.3.7, Ca m is straight. For this reason, v is an input-wing, showing that ρ is a well-defined map from O(Ca m )(n) to I(Ca m )(n). Let us now define the map ρ ′

:

I(Ca m )(n) → O(Ca m )(n) as follows. For any v ∈ I(Ca m )(n), u := ρ ′ (v) is the m-cliff satisfying u i =↿ i̸ =1 ↿ u i-1 ⩽u i -2 (u i -1) for any i ∈ [n]. It is straightforward to prove that ρ ′
is a well-defined map. Moreover, by induction on n ⩾ 0, one can prove that both ρ • ρ ′ and ρ ′ • ρ are identity maps. This establishes (i).

Let v be an m-cliff satisfying v i ∈ {u i , ρ(u) i } for any i ∈

[n]. Since ρ ′
is the inverse map of ρ, this is equivalent to the fact that v i ∈ {ρ ′ (w) i , w i } for all i ∈ [n], where w is the input-wing ρ(u) of Ca m (n). Therefore, by definition of ρ ′

, v 1 = 0 and v i ∈ w i -1] for any i ∈ [2, n]. The fact that w is an input-wing implies, by Proposition 2.3.8, that u i < u i+1 for all i ∈ [n -1]. This implies that v is an m-canyon, so that (ii) checks out.

Point (iii) follows directly from the definition of ρ: since ρ(u) is obtained by incrementing all the letters of u, except the first, in a minimal way so that the obtained m-cliff is an m-canyon, there cannot be any m-canyon inside the cell ⟨u, ρ(u)⟩.

Finally, assume that there are two input-wings v and w of Ca m (n) such that there is a point x := (x 1 , . . . , x n ) ∈ R n such that x is inside both the cells ⟨ρ ′ (v), v⟩ and ⟨ρ ′ (w), w⟩. By contradiction, let us assume that v ̸ = w and let us set i ∈ [2, n] as the smallest position such that v i ̸ = w i . Therefore, we have in particular ρ ′ (v) i < x i < v i and ρ ′ (w) < x i < w i .

(2.3.8)

Without loss of generality, we assume that

v i < w i . Now, if v i -2 ⩾ v i-1 , then ρ ′ (v) i = v i -1 and ρ ′ (w) i = w i -1. It follows from (2.3.8) that v i = w i . Otherwise, when v i -2 < v i-1 , we have ρ ′
(v) i = 0 and ρ ′ (w) i = w i -1. It follows again, from (2.3.8), that v i = w i . This contradicts our hypothesis and shows that v = w. Therefore, (iv) holds. □

This algorithm ρ brought by Proposition 2.3.10 describes the cells of maximal dimension of the cubic realization of Ca m (n). The definition of ρ is inspired by an analogous algorithm introduced by the first author in [Com19] to describe the cells of a geometric realization of the lattices of Tamari intervals. Figure 10 shows some examples of images of output-wings of Ca m (n) by ρ.

The three posets of the input-wings, output-wings, and butterflies of canyon posets are linked in the following way.

Theorem 2.3.11. For any m ⩾ 1 and n ⩾ 0, (n -1)!.

I(Ca m )(n) O(Ca m )(n) B(Ca m+1 )(n) φ
(2.3.10) Proof. Directly from the definition of m-canyons, one has that the m-canyon 0m (n) is cellcompatible with 1m (n). Therefore, 0m (n), 1m (n) is a cell of C(Ca m (n)). Since all others cells of this cubic realization are contained in this one, one obtains that C(Ca m (n)) is an orthotope. This leads to the stated expression for the volume of the cubic realization of Ca m (n). □ 2.4. Poset morphisms and other interactions. The purpose of this part is to state the main links between the three posets Av δ , Hi δ , and Ca δ when δ is an increasing range map. We shall also consider their subposets formed by their input-wings, output-wings, and butterflies elements in the particular case where δ = m for an m ⩾ 0.

= u ′ a and v = v ′ b are two δ-canyons of size n + 1 such that ω(d(u ′ a)) > ω(d(v ′ b)) where u ′ and v ′ are δ-canyons of size n and a, b ∈ N. If ω(d(u ′ )) > ω(d(v ′ )), then by induction hypothesis, there is i ∈ [n] such that u ′ i > v ′ i . Since u i = u ′ i and v i = v ′ i , the property holds. Otherwise, ω(d(u ′ )) ⩽ ω(d(v ′ )). Since ω(d(u)) > ω(d(v))
(n) → Hi δ (n) is
a bijection, this map is not a poset isomorphism. This is the case since there does not exist for instance a poset isomorphism between Ca 1 (3) and Hi 1 (3) -their Hasse diagrams are not superimposable. Moreover, as a consequence of Theorem 2.4.2, for any n ⩾ 0, Hi δ (n) is an order extension of Ca δ (n). Furthermore, it is possible to show by induction on the length of the δ-canyons and by using Lemma 2.3.3 that Ca δ satisfies the prerequisites of Proposition 1.3.12. Therefore, Ca δ (n) is an order extension of Av δ (n).

To summarize the situation, when δ is an increasing range map, the three families of Fuss-Catalan posets fit into the chain

Av δ (n) Ca δ (n) Hi δ (n) e -1 Ca δ e -1 Hi δ • e Ca δ (2.4.1)
of posets for the order extension relation. This phenomenon is analogous to the one stating that Stanley lattices are order extensions of Tamari lattices, which in turn are order extension of Kreweras lattices [START_REF] Kreweras | Sur les partitions non croisées d'un cycle[END_REF] (see for instance [START_REF] Bernardi | Intervals in Catalan lattices and realizers of triangulations[END_REF]). In the present case, avalanche posets play the role of the Kreweras lattices, canyon posets play the role of the Tamari posets, and hill posets play the role of Stanley posets. The difference is that for δ = 1, even if canyon lattices coincide with Tamari lattices and hill lattices coincide with Stanley lattices, the avalanche posets are not isomorphic to Kreweras lattices. Figure 12 gives an example of an instance of (2.4.1).

Isomorphisms between subposets.

There is a link between the hill and the canyon posets, as stated by the following result.

Theorem 2.4.3. For any m ⩾ 1 and n ⩾ 0,

Hi m-1 (n) I(Ca m )(n) φ 3 (2.4.2)
is a poset isomorphism, where φ 3 is the map defined in the statement of Theorem 2.2.5.

Proof. This follows from the description of the input-wings of Ca m (n) provided by Proposition 2.3.8. □ Figure 13 gives an example of the poset isomorphism described by the statement of Theorem 2.4.3. A consequence of Theorem 2.4.3 is that, for any m ⩾ 2 and n ⩾ 0, the image by φ -1

3 of Ca m-1 (n) ∩ I(Ca m )(n) is Hi m-2 (n). Indeed, the set Ca m-1 (n) ∩ I(Ca m )(n) is nothing but the set I(Ca m-1 )(n).
To summarize the whole situation of the links between the three studied Fuss-Catalan posets stated by Theorems 2.1.5, 2.2.5, 2.3.11, 2.4.2, 2.4.3, and Proposition 1.3.12, one has for

m-1 (n) I(Av m )(n) O(Av m )(n) B(Av m+1 )(n) Ca m-1 (n) O(Ca m )(n) I(Ca m )(n) B(Ca m+1 )(n) Hi m-1 (n) I(Hi m )(n) O(Hi m )(n) B(Hi m+1 )(n) e -1 Ca m-1 e -1 Hi m-1 • e Ca m-1 ρ φ 2 I φ 1 φ 1 φ 3 φ 4 φ 3 φ 2 (2.4.3)
of poset morphisms, embeddings, or isomorphisms.

ASSOCIATIVE ALGEBRAS OF δ-CLIFFS

This part of the work is devoted to endow the sets of δ-cliffs with algebraic structures. We describe a graded associative algebra on δ-cliffs motivated by a connection with the δ-cliff posets. Indeed, the product of two δ-cliffs is a sum of δ-cliffs forming an interval of a δ-cliff poset. This property is shared by a lot of combinatorial and algebraic structures. For instance, the algebra FQSym of permutations is related to the weak Bruhat order [DHT02, AS05], the algebra PBT of binary trees is related to the Tamari order [LR02, HNT05], and the algebra Sym of integer compositions is related to the hypercube [GKL + 95].

3.1. Coalgebras and algebras. We introduce here a cograded coalgebra structure on the linear span of all δ-cliffs and then, by considering the dual structure, we obtain a graded algebra. When δ satisfies some properties, this gives an associative algebra.

From now, K is the ground field (of characteristic zero) of all algebraic structures to be defined next. For any graded vector space V, we denote by H V (t) the Hilbert series of V.

We use here the notions of valleys in range maps and of valley-free range maps, defined in Section 1.1.1.

3.1.1. Coalgebras of δ-cliffs. For any range map δ, let Cl δ be the linear span of all δ-cliffs. This space is graded and decomposes as Cl δ = n⩾0 Cl δ (n), where Cl δ (n), n ⩾ 0, is the linear span of all δ-cliffs of size n. By definition, the set {F u : u ∈ Cl δ } is a basis of Cl δ , and we shall refer to it as the fundamental basis or as the F-basis. Let also c : Cl δ → K be the linear map defined by c(F ε ) := 1 and by c(F u ) := 0 for any u ∈ Cl δ \ {ε}.

For any n ⩾ 0, the δ-reduction map is the map r δ : N n → Cl δ (n) defined for any word u ∈ N n and any i ∈ [n] by (r δ (u)) i := min{u i , δ(i)}. For instance, r 1 (212066) = 012045 and r 2 (212066) = 012066.

Let ∆ : Cl δ → Cl δ ⊗ Cl δ be the cobinary coproduct defined, for any w ∈ Cl δ , by

∆(F w ) := u,v∈N * w=uv F u ⊗ F r δ (v) , (3.1.1)
where N * denotes the set of all words on N. This coproduct is well-defined since any prefix of a δ-cliff is a δ-cliff and the image of a word on N by the δ-reduction map is by definition a δ-cliff. Proof. The first part of the statement is a direct consequence of the definition of ∆.

To establish the second part, let us compute the two ways to apply twice the coproduct ∆ on a basis element of Cl δ . For any w ∈ Cl δ , we have We now establish a link between this product • on the F-basis of Cl δ and the posets Cl δ (n), n ⩾ 0, introduced and studied in the previous sections. For this, let for any n 1 , n 2 ⩾ 0 the two binary operations , : Cl δ (n 1 ) × Cl δ (n 2 ) → N n Proof. Assume that δ is weakly increasing and let w := u v where u, v ∈ Cl δ . Hence, since v is a δ-cliff, for any i ∈ [|v|], w |u|+i = v i ⩽ δ(i). Since δ is weakly increasing, we have δ(i) ⩽ δ(|u| + i). This implies that w |u|+i ⩽ δ(|u| + i). Moreover, the fact that u is δ-cliff implies that, for any i ∈ [|u|], w i = u i ⩽ δ(i). Therefore, u v is a δ-cliff.

Conversely, assume that all w := u v are δ-cliffs for all u, v ∈ Cl δ . In particular, this holds for u := 0 and v := 1δ (n) for any n ⩾ 0. We have δ(i -1) = v i-1 = w i ⩽ δ(i) for any i ∈ [2, n + 1]. Therefore, δ is weakly increasing. □

Let χ δ : N * → K be the map defined for any u ∈ N * by χ δ (u) :=↿ u v∈Cl δ .

Theorem 3.1.4. For any range map δ, the product • of Cl δ satisfies, for any u, v ∈ Cl δ , such that w |u|+i > δ(|u| + i). Since w |u|+i = v i , this implies that v i > δ(|u| + i). Observe that by definition of the δ-reduction map, for all v ′ ∈ r -1 δ (v) and j ∈ [|v|], v ′ j ⩾ v j . Therefore, no uv ′ can be a δ-cliff. By inspecting Formula (3.1.8) for the product •, we obtain that the sum is empty, so that F u • F v = 0. □ Lemma 3.2.1. For any weakly increasing range map δ and any u, v ∈ Cl δ , u ⊣ v = c δ (c δ (u) c δ (v)), and u ⊢ v = c δ (c δ (u) c δ (v)).

F u • F v = χ δ (u v) w∈[u v,u v]
Proof. These identities follow by straightforward computations based upon the definitions of the operations , , ⊣, ⊢, and c δ . □

Notice that, by Lemmas 3.2.1, 3.1.2, and 3.1.3, if δ is weakly increasing and u and v are δ-cliffs, both u ⊣ v and u ⊢ v are δ-cliffs. Proposition 3.2.2. For any weakly increasing range map δ, the product • of Cl δ satisfies, for any u, v ∈ Cl δ ,

G u • G v = w∈[u ⊣ v,u ⊢ v] G w .
(3.2.4)

where [u ⊣ v, u ⊢ v] is an interval of the poset Cl δ (|u| + |v|).

Proof. By Lemma 3.2.1, we have A consequence of the freeness of Cl 1 is that Cl 1 is isomorphic as a unital associative algebra to FQSym [MR95, DHT02], an associative algebra on the linear span of all permutations. This follows from the fact that FQSym is also free as a unital associative algebra and that its Hilbert series is the same as the one of Cl 1 . Moreover, in [NT20], the authors construct some associative algebras m FQSym as generalizations of FQSym whose bases are indexed by objects being generalizations of permutations. The algebras Cl m , m ⩾ 0, can therefore be seen as other generalizations of FQSym, not isomorphic to m FQSym when m ⩾ 2.

G u • G v = F c δ (u) • F c δ (v) =
Type

Introduction 1 .

 1 δ-cliff posets and general properties 1.1. δ-cliffs 1.2. δ-cliff posets 1.3. Subposets of δ-cliff posets 2. Some Fuss-Catalan posets 2.1. δ-avalanche posets 2.2. δ-hill posets 2.3. δ-canyon posets 2.4. Poset morphisms and other interactions 3. Associative algebras of δ-cliffs 3.1. Coalgebras and algebras 3.2. Bases and algebraic study 3.3. Quotient algebras Conclusion and open questions References Date: March 1, 2022.

  Cl 1 (4).

FIGURE 1 .

 1 FIGURE 1. Hasse diagrams of some δ-cliff posets.

  and all the children of the node labeled by i of t are leaves, except possibly the first of its brotherhood. For instance, for δ := 0233579 ω and the δ-cliff u := 021042, since tree δ (u)

FIGURE 2 .

 2 FIGURE 2. The Hasse diagram of the poset (Cl0112ω (4), ≼ ′

  ua ∈ Cl δ (n) where u ∈ Cl δ and a ∈ N, by ⇓ S (ua) := ⇓ S (u) b where b := max{b ⩽ a : ⇓ S (u) b ∈ S}.

  y ∈ P \ I, and x ≼ y; (ii) x ∈ P \ I, y = (y ′ , b) ∈ I × 2, and x ≼ y ′ ; (iii) x = (x ′ , a) ∈ I × 2, y ∈ P \ I, and x ′ ≼ y; (iv) x = (x ′ , a) ∈ I × 2, y = (y ′ , b) ∈ I × 2, and x ′ ≼ y ′ and a ⩽ b.

  Lemma 1.3.6. Let δ be a range map and P be a nonempty subposet of Cl δ (n) for an n ⩾ 1. If m(P) ⩾ 1 and P is nested, then D(P) m(D(P)) = P m(P),m(P)-1 . Proof. Let b := m(P), P ′ := D(P), and b ′ := m(P ′ ). First, since P satisfies (N1), b ′ = b -1. Moreover, directly from the definition of the derivation operation D, we have P ′ b ′ = P b,b ′ ∪P b ′ . By (N2), P b ′ ,b is a subset of P b , so that P b ′ is a subset of P b,b ′ . Therefore, P ′ b ′ = P b,b ′ . □ Lemma 1.3.7. Let δ be a range map and P be a nonempty subposet of Cl δ (n) for an n ⩾ 1. If m(P) ⩾ 1 and P is nested, then D(P) is nested. Proof. Let b := m(P), P ′ := D(P), and b ′ := m(P ′ ). First, since P satisfies (N1), b ′ = b -1. Moreover, in particular, for any a ∈ b ′ ], 0 n-1 a ∈ P. Hence, 0 n-1 a ∈ P ′ , so that P ′ satisfies (N1). Let a ∈ b ′ -1]. By (N2), P a,b is an interval of P b . Due to the fact a ⩽ b ′ -1, one has P a = P ′ a , so that P ′ a,b is an interval of P b . This is equivalent to the fact that P ′ a,b ′ is an interval of P b,b ′ . By Lemma 1.3.6, the relation P ′ b ′ = P b,b ′ holds and leads to the fact that P ′ a,b ′ is an interval of P ′ b ′ . Therefore, P ′ satisfies (N2). □ Lemma 1.3.8. Let δ be a range map and P be a nonempty subposet of Cl δ (n) for an n ⩾ 1. If m(P) ⩾ 1 and P is nested, then P is isomorphic as a poset to D(P)[I] where I is the interval P m(P)-1 of D(P). Proof. Let b := m(P), P ′ := D(P), and b ′ := m(P ′ ). By (N1), b ′ = b -1. Let us first prove that

  Since S is closed by prefix, we have u = u ′ a and v = v ′ b where u ′ , v ′ ∈ S(n -1) and a, b ∈ N. By definition of e S , we have e S (u ′ a) = e S (u ′ )c and e S (v ′ b) = e S (v ′ )c where c ∈ N. Hence, e S (u ′ ) = e S (v ′ ) which leads, by induction hypothesis, to the fact that u ′ = v ′ . Moreover, we deduce from this and from the definition of the S-elevation map that there are exactly c letters a ′ smaller than a such that u ′ a ′ ∈ S and that there are exactly c letters b ′ smaller than b such that v ′ b ′ ∈ S. Therefore, we have a = b and thus u = v, establishing the injectivity of e S . □ Lemma 1.3.11. Let δ be a range map and S be a closed by prefix graded subset of Cl δ . The S-elevation image is closed by prefix.

  Proof. First, by Proposition 1.3.10, the map e -1 S is well-defined. We now proceed by induction on n. When n = 0, the property is trivially satisfied. Let u and v be elements of E S (n) such that n ⩾ 1 and u ≼ v. By Lemma 1.3.11, we have u = u ′ a and v = v ′ b where u ′ , v ′ ∈ E S (n -1) and a, b ∈ N. By definition of e -1 S , we have e -1 S (u ′ a) = e -1 S (u ′ )c and e -1 S (v ′ b) = e -1 S (v ′ )d where c, d ∈ N. Since u ≼ v, one has u ′ ≼ v ′ so that, by induction hypothesis, e -1 S (u ′ ) ≼ e -1 S (v ′ ). Moreover, u ≼ v implies that a ⩽ b. Due to the fact that F S (v ′ ) ⊆ F S (u ′ ), one has by definition of e -1 S that c ⩽ d. Therefore, e -1 S (u ′ )c ⩽ e -1 S (v ′ )d, which implies the statement of the proposition. □

  A cubic realization of a subposet of the 113 ω -cliffs of order 3.

FIGURE 3 .

 3 FIGURE 3. Some cubic realizations of straight subposets of posets of δ-cliffs for certain range maps δ.

  Figure4shows the Hasse diagrams of some m-avalanche posets.

FIGURE 4 .

 4 FIGURE 4. Hasse diagrams of some δ-avalanche posets.

FIGURE 5 .

 5 FIGURE 5. From the top to bottom and left to right, here are the posets Av 2 (3), Av 3 (3), Av 3 (3), and Av 4 (3). All these posets contain Av 2 (3) as subposet by restricting on input-wings, output-wings, or butterflies.

  (i) the set M(Av m (n)) contains all m-avalanches u such that u = u ′ a where u ′ ∈ max ≼ Av m (n -1) and a ∈ m -1]; (ii) the set J(Av m (n)) contains all m-avalanches having exactly one letter different from 0. By Proposition 2.1.7 and by upcoming Proposition 2.2.7, the number of meet-irreducible elements of Av m (n) satisfies, for any m ⩾ 1 and n ⩾ 2, #M(Av m (n)) = mcat m (n -2) and the number of join-irreducibles elements of Av m (n) satisfies, for any m ⩾ 1 and n ⩾ 1, #J(Av m (n)) = m n 2 . 2.1.3. Cubic realization. The map φ 2 introduced in Theorem 2.1.5 is used here to describe the cells of maximal dimension of the cubic realization of Av m (n), m ⩾ 1, n ⩾ 0. Proposition 2.1.8. For any m ⩾ 1, n ⩾ 0, and u ∈ I(Av m )(n), (i) the m-avalanche φ 2 (u) is cell-compatible with the m-avalanche u; (ii) the cell ⟨φ 2 (u), u⟩ is pure; (iii) all cells of {⟨φ 2 (u), u⟩ : u ∈ I(Av m )(n)} are pairwise disjoint. Proof. Let v be an m-cliff of size n satisfying

  Now, let u be an δ-avalanche of size n. Let us show by induction on n ⩾ 0 that there exists v ∈ Hi δ (n) such that e Hi δ (v) = u. When n = 0, the property is trivially satisfied. When n ⩾ 1, since Av δ is, by Proposition 2.1.1, closed by prefix, one has u = u ′ a for a u ′ ∈ Av δ (n -1) and an a ∈ N. By induction hypothesis, there exists v ′ ∈ Hi δ (n -1) such that e Hi δ (v ′ ) = u ′ . Now, let b := a + v ′ n-1 and set v := v ′ b. By using what we have proven in the first paragraph, ω

  and it satisfies e Hi δ (v) = u. □ 2.2.2. Posets. For any n ⩾ 0, the subposet Hi δ (n) of Cl δ (n) is the δ-hill poset of order n.Figure6shows the Hasse diagrams of some m-hill posets. The 1-hill posets are sometimes

FIGURE 6 .

 6 FIGURE 6. Hasse diagrams of some δ-hill posets.

FIGURE 7 .

 7 FIGURE 7. From the top to bottom and left to right, here are the posets Hi 2 (3), Hi 3 (3), Hi 3 (3), and Hi 4 (3). All these posets contain Hi 2 (3) as subposet by restricting on input-wings, output-wings, or butterflies. Proposition 2.2.6. For any m ⩾ 1 and n ⩾ 1, #B(Hi m )(0) = 1 and #B(Hi m )(n) = cat ′ m-1 (n). Proof. By Proposition 2.2.4, the set B(Hi m )(n) contains all m-cliffs u of size n satisfying u 1 < • • • < u n and for any i ∈ [2, n], u i < m(i). By setting m ′ := m -1, this set is in one-to-one correspondence with the set of all m ′-cliffs v of size n satisfying v i-1 ⩽ v i < m ′ (i). A possible bijection between these two sets sends any u ∈ B(Hi m )(n) to the m ′ -cliff v of the same size such that for any i ∈ [n], v i = u i -i + 1. We have already seen in the proof of Proposition 2.1.6 that these sets are in one-to-one correspondence with (m -1)-Dyck paths which cannot be written as a nontrivial concatenation of two (m -1)-Dyck paths. Therefore, the statement of the proposition follows.□

FIGURE 8 .

 8 FIGURE 8. Hasse diagrams of some δ-canyon posets.

Proposition 2.3. 8 .

 8 For any m ⩾ 0, (i) the graded set I(Ca m ) contains all the m-cliffs u satisfying u i < u i+1 for all i ∈ [|u| -1]; (ii) the graded set O(Ca m ) contains all the m-cliffs u satisfying, for all i ∈ [2, |u|], u i < m(i), and, for all i ∈ [|u|], if u i ̸ = 0, then for all j ∈ [i -2], u i-j < u i -j; (iii) the graded set B(Ca m ) contains all the m-cliffs u satisfying 1 ⩽ u i < m(i) for all i ∈ [2, |u|], and u i -u i-1 ⩾ 2 for all i ∈ [3, |u|].(iv) all cells of {⟨u, ρ(u)⟩ : u ∈ O(Ca m )(n)} are pairwise disjoint.

FIGURE 10 .FIGURE 11 .

 1011 FIGURE 10. The poset Ca 3 (3) wherein output-wings are marked. The arrows connect these elements to their images by the bijection ρ.

FIGURE 12 .

 12 FIGURE 12. From the left to the right, here are the posets Av 3 (3), Ca 3 (3), and Hi 3 (3). The poset on the right is an order extension of the one at middle, which is itself an order extension of the one at the left.

FIGURE 13 .

 13 FIGURE 13. The subposet of Ca 2 (4) formed by its input-wings is isomorphic to Hi 1 (4).

Av

(

  ∆)∆(F w ) = u,v∈N * w=uv y ′ ,z ′ ∈N * r δ (v)=y ′ z ′ F u ⊗ F y ′ ⊗ F r δ (z ′ ) =x,y,z∈N * w=xyzF x ⊗ F r δ (y) ⊗ F r δ |y|(z) , (3.1.5)

  any u, v ∈ Cl δ , by u v := uv and u v := uv′ where v ′ is the word on N of length |v| satisfying, for any i ∈ [|v|],v ′ i = δ(|u| + i) if v i = δ(i),for δ = 112334 ω , 010 1021 = 0101021 and 010 1021 = 0103041. For δ = 210 ω , 21 11 = 2110. Observe that this last word is not a δ-cliff. Lemma 3.1.2. Let δ be a range map and u, v ∈ Cl δ . If the word u v is a δ-cliff, then u v also is. Proof. Assume that w := u v ∈ Cl δ . Hence, for any i ∈ [|w|], w i ⩽ δ(i). In particular, this implies that for any i ∈ [|v|], v i = w |u|+i ⩽ δ(|u| + i). By definition of the operation , the word w ′ := u v satisfies w |u|+i ∈ {v i , δ(|u| + i)}. Moreover, the fact that u is a δ-cliff implies that for any i ∈ [|u|], u i = w ′ i ⩽ δ(i). Therefore, w ′ is a δ-cliff. □ Lemma 3.1.3. A range map δ is weakly increasing if and only if for any u, v ∈ Cl δ , u v is a δ-cliff.

  where [u v, u v] is an interval of the poset Cl δ (|u| + |v|).Proof. Assume first that w := u v ∈ Cl δ . By Lemma 3.1.2, u v ∈ Cl δ . By (3.1.8), for anyw ′ ∈ Cl δ , F w ′ appears in F u • F v if and only if there is v ′ ∈ r -1 δ (v) such that uv ′ = w ′ . This implies that r δ (v ′ ) = v and, by definition of the δ-reduction map, for any i ∈ [|v|], v ′ i ⩾ v i . Moreover, since w ′ is a δ-cliff, we have for any i ∈ [|v|], v ′ i = w ′ |u|+i ⩽ δ(|u| + i). Therefore, for all i ∈ [|v|], v i ⩽ v ′ i ⩽ δ(|u| + i).This is equivalent to the fact that u v ≼ w ′ ≼ u v and leads to the expression of the statement of theorem.Assume finally that w := u v / ∈ Cl δ . Since u and v are δ-cliffs, there exists an index i ∈[|v|]

  w∈[c δ (u) c δ (v),c δ (u) c δ (v)] F w = w∈[c δ (cδ (u) c δ (v)),c δ (cδ (u) c δ (v))] G w .(3.2.5)Now, again by Lemma 3.2.1, we obtain the stated expression. □For instance, in Cl 1 , G 01

  belongs to P b . Again by (N2), this leads to the fact that w ∈ P b ′

	that the set P b ′	is closed by interval in P ′ b ′ . Since finally, by Lemma 1.3.5, P b ′	. This shows is an interval of
	P, P b ′ of P ′ .	has a unique least and a unique greatest element. This implies that P b ′	is an interval
	Since I is an interval of P ′ doubling operation, P ′ [I] = (P ′ \ P b ′ , we can now consider the poset P ′ ) ⊔ (P b	[I]. By definition of the interval

′ × 2). Let φ : P ′ [I] → P be the map defined by φ(ua) := ua, if ua ∈ P ′ \ P b ′ and a ̸ = b ′ , (1.3.7a) φ ub ′

  2.2 coming next. Indeed, by this result, Av m (n) is the image by the elevation map of a graded set of objects enumerated by m-Fuss-Catalan numbers. Since this set of objects satisfies all the requirements of Proposition 1.3.10, the elevation map is injective, implying that it is a bijection. □

	Therefore, by Proposition 2.1.2, the first numbers of m-avalanches by sizes are
	1, 1, 1, 1, 1, 1, 1, 1,	m = 0,	(2.1.2a)
	1, 1, 2, 5, 14, 42, 132, 429,		m = 1,	(2.1.2b)
	1, 1, 3, 12, 55, 273, 1428, 7752,	m = 2.	(2.1.2c)

The second and third sequences are respectively Sequences A000108 and A001764 of [Slo].

2.1.2. Posets. For any n ⩾ 0, the subposet Av δ (n) of Cl δ (n) is the δ-avalanche poset of order n.

  for instance). □

	By Proposition 2.1.6, the first numbers of output-wings of Av m (n) by sizes are
	1, 1, 1, 1, 1, 1, 1, 1,	m = 0,	(2.1.6a)
	1, 1, 1, 2, 5, 14, 42, 132,	m = 1,	(2.1.6b)
	1, 1, 2, 7, 30, 143, 728, 3876,	m = 2.	(2.1.6c)

The fourth sequence is Sequence A006013 of

[Slo]

. As a side remark, for any m ⩾ 1, the generating series of the graded set O(Av m ) is 1 plus the inverse, for the functional composition of series, of the polynomial t(1 -t) m .

Proposition 2.1.7. For any m ⩾ 1 and n ⩾ 1,

  . Any element of Hi δ is a δ-hill. For instance,

	Hi 2 (3) = {000, 001, 011, 002, 012, 022, 003, 013, 023, 004, 014, 024}.	(2.2.1)
	Proposition 2.2.1. For any weakly increasing range map δ, the graded set Hi δ is
	(i) closed by prefix;
	(ii) is minimally extendable if and only if δ = 0 ω ;
	(iii) is maximally extendable.

  Points (i), (ii), (iii), (iv), and (vi) are immediate. Point (v) follows from (ii) and Theorem 1.3.2. Point (vii) is a consequence of Theorem 1.3.9 since (iii) holds and, from Proposition 2.2.1, of the fact that Hi δ is closed by prefix. Alternatively, (vii) is implied by (vi) and the fact that any sublattice of a lattice constructible by interval doubling is constructible by interval doubling [Day79], which is indeed the case for Cl δ (n).

	and only if there is an i ∈ [n]
	such that ↑ i (u) = v;
	(ii) coated;
	(iii) nested;
	(iv) graded, where the rank of a hill is its weight;
	(v) EL-shellable;
	(vi) a sublattice of Cl δ (n);
	(vii) constructible by interval doubling.
	Proof.

□ Proposition 2.2.4. For any m ⩾ 0, (i) the graded set I(Hi m ) contains all the m-cliffs u satisfying u 1

  For any increasing range map δ and n ⩾ 0, the poset Ca δ (n) is Point (iii) is immediate. Assume that u and v are two δ-canyons of size n such that u ≼ v. Let k ∈ [n -1] and consider the δ-cliff w := u 1 . . . u k v k+1 . . . v n . Now, since for any

	Proposition 2.3.7. (i) straight;
	(ii) coated;
	(iii) nested;
	(iv) EL-shellable;
	(v) a meet semi-sublattice of Cl δ (n);
	(vi) a lattice;
	(vii) constructible by interval doubling.
	Proof.

  2.4.1. Order extensions. Observe that the map e Ca δ is not a poset morphism. Indeed, for instance in Ca 1 one has 002 ≼ 012 but eCa 1 (002) = 002 ≼ 011 = e Ca 1 (012). Nevertheless, by composing this map on the left with the inverse of the Hi δ -elevation map, we obtain a poset morphism, as stated by the next theorem. First, since by Proposition 2.3.1, Ca δ is closed by prefix, eCa δ is well-defined. By considering the contrapositive of the statement of the lemma and by Lemma 2.3.4, we have to show that for any δ-canyons u and v of size n, ω(d(u)) > ω(d(v)) implies that there exists i ∈ [n] such that u i > v i . We proceed by induction on n. If n = 0, the property holds immediately. Assume now that u

	Lemma 2.4.1. Let δ be a range map, and u and v be two δ-canyons of size n. If u ≼ v,
	then ω(e Ca δ (u)) ⩽ ω(e Ca δ (v)).
	Proof.

  and by definition of the map d, we necessarily have a > b. Therefore one has u n+1 > v n+1 , showing that the property holds. □ Theorem 2.4.2. For any increasing range map δ and any n ⩾ 0, the map e -1Hi δ • e Ca δ from Ca δ (n) to Hi δ (n) is a poset morphism. Proof. First of all, by Proposition 2.3.6, the map φ := e -1Hi δ •e Ca δ is well-defined. By definition of the maps eHi δ and e Ca

	Ca δ (u 1 . . . u i )) ⩽ ω(e Ca δ (v	1 . . . v i )).
	Moreover, by the above remark, this implies φ(u) i ⩽ φ(v) i . Therefore, we have φ(u) ≼ φ(v),
	establishing the statement of the theorem.	□
	Even if, by Proposition 2.3.6, e -1 Hi δ •e Ca

δ , for any δ-canyon w of size n and any i ∈ [n], φ(w) i = ω(e Ca δ (w 1 . . . w i )). Assume now that u and v are two δ-canyons of size n such that u ≼ v. Then, for any i ∈ [n], u 1 . . . u i ≼ v 1 . . . v i . By Lemma 2.4.1, this implies ω(e δ : Ca δ

  For instance, for δ := 1221013 ω , we have in Cl δ , Let δ be a range map. The space Cl δ endowed with the coproduct ∆ and the counit c is a counital cograded coalgebra. Moreover, ∆ is coassociative if and only if δ is valley-free.

	∆(F 1021 ) = F ε ⊗ F 1021 + F 1 ⊗ F	021 + F 10 ⊗ F 11 + F 102 ⊗ F 1 + F 1021 ⊗ F ε ,	(3.1.2)
	and
	∆(F 1211010 ) = F ε ⊗ F 1211010 + F 1 ⊗ F 111000 + F 12 ⊗ F 11010 + F 121 ⊗ F 1010
	+ F 1211 ⊗ F 010 + F 12110 ⊗ F 10 + F 121101 ⊗ F 0 + F 1211010 ⊗ F ε .	(3.1.3)
	Theorem 3.1.1.

  and H-bases. By mimicking the construction of bases of several combinatorial spaces by using a particular partial order on their basis element (see for instance[START_REF] Duchamp | Noncommutative Symmetric Functions VI: Free Quasi-Symmetric Functions and Related Algebras[END_REF][START_REF] Hivert | The algebra of binary search trees[END_REF]), let for any u ∈ Cl δ , E u := By triangularity, the sets {E u : u ∈ Cl δ } and {H u : u ∈ Cl δ } are bases of Cl δ , called respectively elementary basis and homogeneous basis, or respectively E-basis and H-basis. For instance, For any m ⩾ 1, m is of type B. Each Cl m is free as a unital algebra and its minimal generating sets are infinite.Proof. Since Cl m is a free unital associative algebra, its Hilbert series and the generating series of its minimal generating set satisfies the relation H Cl m (t) = (1 -G P m (t)) -1 . This leads to the stated expression for G P m (t). □

	Type B. Proposition 3.2.12. For any m ⩾ 0, the generating series of the minimal generating set of
	Cl m satisfies
										G P m (t) = 1 -	1 H Cl m (t)	.	(3.2.20)
	The first generators of Cl 1 are
	a	0 , a 01 , a 002 , a 011 , a 012 ,
				a	0003 , a 0013 , a 0021 , a 0022 , a 0023 , a 0102 , a 0103 , a 0111 , a 0112 , a 0113 , a 0121 , a 0122 , a 0123 , (3.2.21)
	and the first generators of Cl 2 are
							a	0 , a 01 , a 02 , a 003 , a 004 , a 011 , a 012 , a 013 , a 014 , a 021 , a 022 , a 023 , a 024 .	(3.2.22)
		• G 010 = G	01030 + G	01031 + G	01032 + G	01130 + G 01131 + G	01132 + G	01230 + G	01231 + G	01232 , (3.2.6)
	and in Cl 2 ,
		G	01 • G	010 = G 01050 + G 01051 + G	01052 + G	01053 + G	01054 + G 01150 + G 01151 + G	01152 + G	01153
						+ G	01154 + G	01250 + G	01251 + G 01252 + G 01253 + G	01254 + G	01350 + G	01351 + G 01352
						+ G	01353 + G	01354 + G	01450 + G	01451 + G 01452 + G	01453 + G	01454 .
										(3.2.7)
	u≼v 3.2.2. E v∈Cl δ	F v ,	(3.2.8)	H u :=	v∈Cl δ v≼u	F v .	(3.2.9)
	for δ := 1021 ω	,
									E 10010 = F 10010 + F 10011 + F 10110 + F 10111 + F 10210 + F 10211 ,	(3.2.10)
	and
										H 10010 = F	10010 + F 10000 + F 00010 + F 00000 .	(3.2.11)

  C. Let the range map δ := 010 ω of type C. The unital associative algebra Cl δ admits the presentation Cl δ ≃ K ⟨a 0 , a 01 ⟩ / R δ where R δ is minimally generated by the elements a Let the range map δ := 0110 ω of type C. The unital associative algebra Cl δ admits the presentation Cl δ ≃ K ⟨a 0 , a 01 , a 011 ⟩ / R δ where R δ is minimally generated by the elements a Let the range map δ := 210 ω of type C. The unital associative algebra Cl δ admits the presentation Cl δ ≃ K ⟨a Let the range map δ := 021 ω of type D. The unital associative algebra Cl δ admits the presentation Cl δ ≃ K ⟨a

														0 a	01 , a 01 a	01 .	(3.2.23)
		0 a	0 a	01 , a 01 a	01 , a 01 a	0 a	01 , a 011 a 01 , a 011 a	0 a	01 , a 0 a 011 , a 01 a	011 , a 011 a	011 .	(3.2.24)
									0 , a 1 , a 2 ⟩ / R δ where R δ is minimally generated
				a 0 a	0 a	1 , a 0 a	1 a	1 , a 1 a 0 a 1 , a 1 a	1 a	1 , a 2 a	0 a	1 , a 2 a 1 a 1 , a 0 a	2 , a 1 a	2 , a 2 a	2 .	(3.2.25)
	Type D. 0 , a 01 , a 02 , a 011 , a 021 , a 0111 , a 0211 , a 01111 , a 02111 , . . . ⟩ / R δ where R δ is
	generated by the relations
	a	0 a	02 , a 01 a	02 , a 02 a	02 , a 011 a	02 , a 021 a 02 , a 0 a	021 , a 01 a	021 , a 02 a 021 , a 0 a 0211 , . . . .	(3.2.26)

Remark that, from the definition of m-canyons and the description of I(Ca m ) brought by Proposition 2.3.8, for any u ∈ I(Ca m ), all m-canyons v such that u ≼ v are also input-wings of Ca m . For this reason, for any n ⩾ 0, I(Ca m )(n) is an order filter of Ca m (n).

Proposition 2.3.9. For any m ⩾ 1 and n ⩾ 1, the set J(Ca m (n)) contains all m-canyons having exactly one letter different from 0. By Proposition 2.3.9, the number of join-irreducibles elements of Ca m (n) satisfies, for any m ⩾ 1 and n ⩾ 1, #J(Ca m (n)) = m n 2 . Since by Proposition 2.3.7, Ca m (n) is constructible by interval doubling, this is also the number of its meet-irreducible elements [START_REF] Grätzer | Lattice Theory: Special Topics and Applications[END_REF].

Cubic realization.

Let m ⩾ 1 and n ⩾ 0. For any output-wing u of Ca m (n), we define ρ(u) as the m-canyon ⇑ Ca m (u ′ ), where u ′ is the m-cliff obtained by incrementing by 1 all letters of u except the first one. For instance, the output-wing 01007 of Ca 2 (5) is sent by ρ to the 2-canyon ⇑ Ca 2 (02118) = 02348. We call ρ(u) the left-to-right increasing of u. This map is not a poset embedding because, for m := 2 and n := 3, ρ(010) = 023 ≼ 013 = ρ(002) but 010 ≼002. where for any k ⩾ 0, δ k is the range map satisfying δ k (i) = min{δ(i), δ(k + i)} for any i ⩾ 1. The second equality of (3.1.5) comes from the two following facts. First, for any i ∈ [|y ′ |], y ′ i = r δ (v) i = r δ (y) i where y is the factor w |u|+1 . . . w |u|+|y ′ | of w. Second, we have for any j ∈ Let us now prove that (3.1.4) and (3.1.5) are different if and only if δ has a valley. These two elements are different if and only if there exists a factorization w = xyz with x, y, z ∈ N * such that r δ (z) ̸ = r δ |y| (z). This is equivalent to the fact there exists an index i ∈

To have this difference, we necessarily have δ(|y| + i) < z i and δ(|y| + i) < δ(i). Now, since w is in particular a δ-cliff, we have z i = w j+i-1 ⩽ δ(j + i -1). Therefore, we obtain δ(i) > δ(|y| + i) < δ(j + i -1).

where, for any (3.1.12) By Theorem 3.1.1, the product • admits the linear map 1 : K → Cl δ satisfying 1(1) = F ε as unit, and is graded. Moreover, again by this last theorem, • is associative if and only if δ is valley-free. For instance, for δ := 101 ω , δ has a valley and since

the product • of Cl δ is not associative.

For instance, for δ := 01120 ω ,

and, since 01 011 = 01011 / ∈ Cl δ ,

In particular when δ is weakly increasing, Lemma 3.1.3 and Theorem 3.1.4 state that any product of two elements of the F-basis of Cl δ is a sum of elements of the F-basis ranging in an interval of a δ-cliff poset.

3.2.

Bases and algebraic study. We construct alternative bases for Cl δ and establish several properties of this structure w.r.t. properties of the range map δ. The main results are summarized in Table 1. We also provide a classification of all associative algebras Cl δ in four classes, depending on properties of the valley-free range map δ.

We use here the notion of j-dominated range maps, defined in Section 1.1.1.

G-basis. For any

where c(u) is the complementary of u as defined in Section 1.2.1. Due to the fact that c is an involution, the set {G u : u ∈ Cl δ } is a basis of Cl δ , called G-basis.

We now consider that δ is a weakly increasing range map. We need, to state the next result, to introduce for any n 1 , n 2 ⩾ 0 the two binary operations ⊣, ⊢ :

and by u ⊢ v := uv ′ where v ′ is the word on N of length |v| satisfying, for any i ∈

For instance, for δ = 112334 ω , 010 1021 = 0103042 and 010 1021 = 0103242. Observe that in the case where δ = m for an m ⩾ 0, u ⊣ v is the word obtained by concatenating u and v and by incrementing by m|u| the letters coming from v that are different from 0, and u ⊢ v is the word obtained by concatenating u and v and by incrementing by m|u| all the letters coming from v. Proposition 3.2.3. For any range map δ, the product • of Cl δ satisfies, for any u, v ∈ Cl δ ,

(3.2.12)

Proof. By (3.1.8), we have

(3.2.13)

The equality between the third and the last member of (3.

Proof. By (3.1.8), we have

(3.2.15)

The equality between the third and the last member of (3.2.15) is a consequence of the fact that for any

By definition of the H-basis provided by (3.2.9), and since F r δ (u v) is the element with the greatest index appearing in the last member of (3.2.15), this expression is equal to the stated formula. □

Presentation by generators and relations

The graded collection of all these elements is denoted by P δ . For instance, for δ := 021 ω , among others, the δ-cliffs 0, 01, and 021111 are δ-prime, and 0210 = 021 0 and 011101 = 0111 01 are not. Proposition 3.2.5. For any range map δ, the set {E u : u ∈ P δ } is a minimal generating family of the unital magmatic algebra (Cl δ , •, 1).

Proof. Let us call G the set of the elements of Cl δ appearing in the statement of the proposition.

We proceed by proving that any E u , u ∈ Cl δ , can be expressed as a product of elements of G by induction on the size n of u. Since for any λ ∈ K,

Since moreover E ε is generated by the empty product of elements of G, the property is true for n = 0. Assume now that u is a nonempty δ-cliff

where k ⩾ 1 is maximal and the u (i) , i ∈ [k], are some nonempty δ-cliffs.

, we have u = u ′ u (k) where u ′ and u (k) are both nonempty δ-cliffs. Then, by Proposition 3.2.3,

and of u (k) are both smaller than n, by induction hypothesis, E u ′ and E u (k) are generated by G. Therefore, E u also is.

It remains to prove that G is minimal w.r.t. set inclusion. For this, let any u ∈ P δ and set

Since by definition of δ-prime elements, and due to the product rule on the E-basis provided by Proposition 3.2.3, E u cannot be expressed as a product of elements of G ′ , E u is not generated by G ′

. Therefore, G is minimal. □ Lemma 3.2.6. Let δ be a range map. If u is a nonempty δ-cliff, then u admits as suffix a unique δ-prime δ-cliff.

Proof. Assume by contradiction that there are two different suffixes w and w ′ of u which are δ-prime. Therefore, |w| ̸ = |w ′ |, and the shortest word among w and w ′ is the suffix of the other. Assume without loss of generality that w ′ is shorter than w. This implies that there is a nonempty word v ∈ N * such that w = vw ′ . Now, since by hypothesis w is a δ-cliff, and since any prefix of a δ-cliff is a δ-cliff, we obtain that v is a δ-cliff. Therefore, w = v w ′ where v and w ′ are both nonempty δ-cliffs. This implies that w is not δ-prime, which is in contradiction with our assumptions. □

Let A P δ be the alphabet {a u : u ∈ P δ }. We denote by K ⟨A P δ ⟩ the free associative algebra generated by A P δ . By definition, the elements of this algebra are noncommutative polynomials on A P δ . For any u ∈ Cl δ , we denote by a u the monomial a u (1) . . . a u (k) where u (1) , . . . , u (k) , k ⩾ 0, is the unique sequence of δ-prime δ-cliffs such that u = u (1) • • • u (k) . By Lemma 3.2.6, this definition is consistent since any δ-cliff admits exactly one factorization on δ-prime δ-cliffs. Proposition 3.2.7. For any valley-free range map δ, the unital associative algebra (Cl δ , •, 1) is isomorphic to K ⟨A P δ ⟩ / R δ where R δ is the subspace of K ⟨A P δ ⟩ defined as the linear span of the set a u (1) . . . a u (k) : k ⩾ 1, for all i ∈ [k], u (i) ∈ P δ , and u (1) . . . u (k) / ∈ Cl δ .

(3.2.16)

Proof. Let us prove that R δ is an ideal of K ⟨A P δ ⟩. Let u := u (1) . . . u (k) such that for all i ∈ [k], u (i) ∈ P δ , and u / ∈ Cl δ . Let also v := v (1) . . . v (ℓ) such that for all i ∈ [ℓ], v (i) ∈ P δ , and v ∈ Cl δ . Therefore, we have a u (1) . . . a u (k) ∈ R δ and a v (1) . . . a v (ℓ) ∈ K ⟨A P δ ⟩. Since u / ∈ Cl δ , there is an index j ∈ [|u|] such that u j > δ(j). This implies that (uv) j = u j > δ(j), so that uv / ∈ Cl δ . Hence, a u (1) . . . a u (k) a v (1) . . . a v (ℓ) ∈ R δ . Now, assume by contradiction that vu ∈ Cl δ . Since u / ∈ Cl δ , there is an index j ∈ [|u|] such that u j > δ(j). This letter u j appears at a certain position j ′ of a factor

). Besides, since vu ∈ Cl δ , we have u j = (vu) |v|+j ⩽ δ(|v| + j). Therefore, we obtain δ(j ′

) > δ(j) < δ(|v| + j), and since j ′ < j < |v| + j, this leads to the fact that δ has a valley, which is in contradiction with our hypothesis. Hence,

Let the linear map φ :

for any u ∈ Cl δ . Recall that Lemma 3.2.6 implies that a u is a well-defined monomial of K ⟨A P δ ⟩ / R δ . Recall also that since δ is valley-free, by Theorem 3.1.1, Cl δ is a unital associative algebra. Hence, it remains to prove that φ is a unital associative algebra isomorphism. First, φ is an isomorphism of spaces since it establishes a one-to-one correspondence between basis elements E u , u ∈ Cl δ , of Cl δ and basis elements φ

since a u a v ∈ R δ . Finally, we have φ(E ε ) = a ε = 1. This shows that φ is a unital associative algebra morphism. □ Let ⩽ s be the partial order relation on the monomials of K ⟨A P δ ⟩ wherein for any monomials a u (1) . . . a u (k) and a v (1) . . . a v (ℓ) of K ⟨A P δ ⟩, one has a u (1) . . . a u (k) ⩽ s a v (1) . . . a v (ℓ) if the word u (1) . . . u (k) is a suffix of v (1) . . . v (ℓ) . Given a set M of monomials of For this reason, the ideal generated by G is a subspace of R δ . Now, let x := a u (1) . . . a u (k) be a basis element of R δ . Since u (1) . . .

, we have x = a u ′ a v ′ u (ℓ+2) . . . u (k) . Therefore, x belongs to the ideal generated by G. This shows that G generates R δ as an ideal. It remains to show that G is minimal w.r.t. set inclusion. For this, assume that G is nonempty. Let any x := a u a v ∈ G and set G ′ := G \ {x}. Since x is a minimal element in G w.r.t. the order relation ⩽ s , there is no a u ′ a v ∈ G such that a u ′ a v ⩽ s a u a v . For this reason, x cannot be expressed as a product yx ′ where x ′ ∈ G ′ and y ∈ K ⟨A P δ ⟩. Moreover, since u is a δ-cliff and all its prefixes still are, x cannot by expressed as a product x ′ y where x ′ ∈ G ′ and y ∈ K ⟨A P δ ⟩. Therefore, G ′ does not generates R δ . This shows the minimality of G. □ Lemma 3.2.9. Let δ be a valley-free range map. The unital associative algebra (Cl δ , •, 1) is free if and only if δ is weakly increasing.

Proof. We use here the fact that, by Proposition 3.2.7, Cl δ is isomorphic as a unital associative algebra to the quotient K ⟨A P δ ⟩ / R δ and the description of the generating familly of R δ provided by Proposition 3.2.8.

When δ is weakly increasing, for all u, v ∈ Cl δ , uv ∈ Cl δ . Therefore, R δ is the null space so that Cl δ is free as a unital associative algebra. Conversely, when δ is not weakly increasing, there is an i ⩾ 1 such that δ(i) > δ(i + 1). In this case, there are u, v ∈ Cl δ such that uv / ∈ Cl δ .

By expressing u and v respectively as products of δ-prime δ-cliffs, this leads to the existence of a relation in R δ . □ Lemma 3.2.10. Let δ be a valley-free range map. The unital associative algebra (Cl δ , •, 1) admits a finite number of generators and a finite number of nontrivial relations between the generators if and only if δ is 1-dominated.

Proof. We use here the fact that, by Proposition 3.2.7, Cl δ is isomorphic as a unital associative algebra to the quotient K ⟨A P δ ⟩ / R δ and the description of the generating familly of R δ provided by Proposition 3.2.8.

Assume that δ is 1-dominated. The δ-cliffs 0, 1, . . . , δ(1) are δ-prime. Moreover, since δ is 1-dominated, there is an ℓ ⩾ 0 such that any δ-cliff u of size ℓ or more decomposes as u = v w such that v ∈ Cl δ (ℓ) and w is a δ-cliff having only letters nongreater than δ(1). This implies that all δ-prime δ-cliffs have ℓ as maximal size. Therefore, Cl δ is finitely generated. Moreover, the finite number of nontrivial relations in Cl δ is the consequence of the finiteness of the generating set of Cl δ and the description of the relations of R δ . Indeed, there is a finite number of monomials a u a v with u ∈ Cl δ , v ∈ P δ , and uv / ∈ Cl δ that are not suffixes of any other one satisfying the same description. Conversely, assume that δ is not 1-dominated. Thus, since δ is valley-free, there is an index j ⩾ 1 such that δ(1) = • • • = δ(j) and for all i ⩾ j + 1, δ(i) > δ(1). For any k ⩾ j + 1, set u as the δ-cliff of size k defined by u i := δ(i) for all i ∈ [k]. By Lemma 3.2.6, there is a unique δ-prime δ-cliff u ′ being a suffix of u. Since u ′ is in particular a δ-cliff, one must have u ′ 1 ⩽ δ(1). Due to the previous description of δ, we necessarily have u = u ′ . Therefore, u is δ-prime. This shows that there are infinitely many δ-prime δ-cliffs and thus, that Cl δ admits an infinite number of generators. □

The set of all valley-free range maps can be partitioned into the following four classes: ⋆ The class of type A range maps, containing all constant range maps; ⋆ The class of type B range maps, containing all weakly increasing range maps having at least one ascent; ⋆ The class of type C range maps, containing all 1-dominated range maps having at least one descent; ⋆ The class of type D range maps, containing all range maps that are not 1-dominated and having at least one descent.

Theorem 3.2.11. Let δ be a valley-free range map. Each unital associative algebra (Cl δ , •, 1) admits the presentation K ⟨A P δ ⟩ / R δ which fits into one of the following four classes: (i) If δ is of type A, then A P δ is finite and R δ is the zero space; (ii) If δ is of type B, then A P δ is infinite and R δ is the zero space; (iii) If δ is of type C, then A P δ is finite and R δ is finitely generated and nonzero; (iv) If δ is of type D, then A P δ is infinite and R δ is infinitely generated.

Proof. This is a consequence of the presentation by generators and relations of Cl δ provided by Propositions 3.2.7 and 3.2.8, and of the properties of the generating sets and relations spaces of Cl δ raised by Lemmas 3.2.9 and 3.2.10. □

Examples.

We provide here some examples of unital associative algebras Cl δ for particular range maps δ and describe their structure thanks to the classification provided by Theorem 3.2.11.

Type A. Let δ by a range map of type A. Thus, there is a value c ∈ N such that δ(i) = c for all i ∈ N. Thus, Cl δ is the free unital associative algebra generated by a 0 , a 1 , . . . , a c . Let us introduce here an important combinatorial condition for the sequel on S. We say thatS is closed by suffix reduction if for any u ∈ S, for all suffixes u ′ of u, r δ (u ′ ) ∈ S.

Proposition 3.3.1. Let δ be a valley-free range map and S be a graded subset of Cl δ . If S is closed by prefix and is closed by suffix reduction, then Cl S is a quotient algebra of the unital associative algebra (Cl δ , •, 1).

Proof. Notice first that, since δ is valley-free, Cl δ is by Theorem 3.1.1 a well-defined unital associative algebra. We have to prove that V S is an associative algebra ideal of Cl S . For this, let F u ∈ V S and F v ∈ Cl S . Let us look at Expression (3.1.8) for computing the product of Cl δ . Assume that there is a cliff uv ′ ∈ S such that F uv ′ appears in F u • F v . Then, since S is closed by prefix, u ∈ S, which contradicts our hypothesis. For this reason, F u • F v belongs to V S . Moreover, let F u ∈ Cl S and F v ∈ V S . Assume that there is a cliff uv ′ ∈ S such that F uv ′ appears in F u • F v . Then, since S is closed by suffix reduction, one has r δ (v ′ ) ∈ S. By (3.1.8), r δ (v ′ ) = v, leading to the fact that v ∈ S holds, and which contradicts our hypothesis. Therefore, F u • F v belongs to V S . This establishes the statement of the proposition. □

Notice that the graded subset Av δ is not closed by suffix reduction. For instance, even if 00112 is an 1-avalanche, the 1-reduction of its suffix 112 is 012, which is not an 1-avalanche.

Let us denote by θ S : Cl δ → Cl S the canonical projection map. By definition, this map satisfies, for any u ∈ Cl δ , θ S (F u ) =↿ u∈S F u .

Product.

We show here that under some conditions of S, the product in Cl S can be described by using the poset structure of S. More precisely, we say that Cl S has the interval condition if the support of any product F u • F v , u, v ∈ S, is empty or is an interval of a poset S(n), n ⩾ 0. Lemma 3.3.2. Let δ be a range map and S be a graded subset of Cl δ such that for any n ⩾ 0, S(n) is a meet (resp. join) semi-sublattice of Cl δ (n). For any u, v ∈ S, if u v is a δ-cliff, then the set [u v, u v] ∩ S admits at most one minimal (resp. maximal) element.

Proof. Assume that S(n) is a meet semi-sublattice of Cl δ (n) and that u v ∈ Cl δ . By Lemma 3.1.2, u v ∈ Cl δ so that I := [u v, u v] is a well-defined interval of Cl δ (n). Assume that there exist two δ-cliffs w and w ′ belonging to I ∩ S. Since S(n) is a meet semi-sublattice of Cl δ (n), by setting w ′′ := w ∧ w ′ , one has w ′′ ∈ S. Since u v is a lower bound of both w and w ′ , we necessarily have u v ≼ w ′′ and w ′′ ∈ I. This shows that when I ∩ S is nonempty, this set admits exactly one minimal element. The proof is analogous for the respective part of the statement of the proposition. □

When for any n ⩾ 0, S(n) is a lattice, we denote by ∧ S (resp. ∨ S ) its meet (resp. join) operation. In this case, S is meet-stable (resp. join-stable) if, for any n ⩾ 0 and any u, v ∈ S(n), the relation

Lemma 3.3.3. Let δ be a range map and S be a closed by prefix, maximally extendable, and join-stable graded subset of Cl δ . For any u, v ∈ S such u v is a δ-cliff, the set [u v, u v]∩S admits at most one maximal element.

Assume that there exist two δ-cliffs w and w ′ belonging to I ∩S. It follows from the hypotheses on S of the statement that, by Theorem 1.3.3, the operation ∨ S is the join operation of the posets S(n), n ⩾ 0 (see Section 1.3.2). First, since w ≼ u v and w ′ ≼ u v, we have w ∨ w ′ ≼ u v. Moreover, by definition of the ∨ S operation, w ′′ := w ∨ S w ′ is obtained by incrementing by some values some letters of w ∨ w ′ . Now, observe that due to the definitions of the operations and , w and w ′ write respectively as w = ur and w ′ = ur ′ where r and r ′ are some words on N. Moreover, if there is an index i ∈ [|r|] such that r i ̸ = r ′ i , then v i = δ(i) and (u v) |u|+i = δ(|u| + i). This, the definition of the ∨ S operation, and the fact that S is join-stable imply that w ′′ ≼ u v. Therefore, w ′′ ∈ I ∩ S. This shows that when I ∩ S is nonempty, this set admits exactly one maximal element. We can observe that for any m ⩾ 1, Hi m is not free as unital associative algebra. Indeed, the quasi-inverse of the respective generating series of these elements is not the Hilbert series of Hi m , which is expected when this algebra is free.

Canyon associative algebras. For any m ⩾ 0, let Ca m be the quotient Cl Ca m . This quotient is well-defined due to the fact that Ca m satisfies the conditions of Proposition 3. The associative algebra Ca 1 is the Loday-Ronco algebra [START_REF] Loday | Hopf Algebra of the Planar Binary Trees[END_REF], also known as PBT [START_REF] Hivert | The algebra of binary search trees[END_REF]. It is known that this associative algebra is free and that the dimension of its generators are a shifted version of Catalan numbers: 0, 1, 1, 2, 5, 14, 42, 132, 429.

(3.3.11)

The sequence for the numbers of generators of Ca 2 degree by degree begins by 0, 1, 2, 7, 30, 149, 788, 4332.

(3.3.12)

We can observe that for any m ⩾ 2, Ca m is not free as unital associative algebra. It follows, from the same argument as the previous section, that Ca m is not free.

CONCLUSION AND OPEN QUESTIONS

This work presents three new families of posets on Fuss-Catalan objects and associative algebras on their linear spans. All this are based upon δ-cliffs, a combinatorial family of words of integers satisfying some conditions. Some general properties about subposets of the posets of δ-cliffs have been presented, as well as general properties about quotients of the associative algebras defined on the linear span of δ-cliffs.

Here is a list of open questions raised by this research:

(1) (Generalization of the weak Bruhat order) -The first open question concerns the alternative order relation on δ-cliffs introduced in Section 1.2.3. This consists in considering Conjecture 1.2.2 and in proving that the posets (Cl δ (n), ≼ ′

) are semi-distributive lattices, or at least lattices.

(2) (Coproducts and Hopf bialgebras) -As explained above, the associative algebras Cl 1 and Ca 1 are already known algebraic structures which are in fact Hopf bialgebras. They are endowed with a coproduct satisfying some compatibility relations with the product. The question here consists in endowing Cl δ with a coproduct where δ is a unimodal range map. We can ask also for a general definition of such a coproduct for the quotients Cl S of Cl δ for some subfamilies S of δ-cliffs.

(3) (Other subposets and quotient algebras) -There are other subfamilies of δ-cliffs than δhills and δ-canyons which seem to lead to interesting posets and associative algebras. Among these, there are δ-dunes, which are δ-cliffs u such that Email address: samuele.giraudo@u-pem.fr