Cesar Ceballos

Viviane Pons

THE s-WEAK ORDER AND s-PERMUTAHEDRA II: THE COMBINATORIAL COMPLEX OF PURE INTERVALS

Keywords: . 2020 Mathematics Subject Classification. Primary 20F55 and 52B05 ; Secondary 06B05 and 06B10 Weak order, Permutahedron, Tamari Lattice, Associahedron

This paper introduces the geometric foundations for the study of the s-permutahedron and the s-associahedron, two objects that encode the underlying geometric structure of the s-weak order and the s-Tamari lattice. We introduce the s-permutahedron as the complex of pure intervals of the s-weak order, present enumerative results about its number of faces, and prove that it is a combinatorial complex. This leads, in particular, to an explicit combinatorial description of the intersection of two faces. We also introduce the s-associahedron as the complex of pure s-Tamari intervals of the s-Tamari lattice, show some enumerative results, and prove that it is isomorphic to a well chosen ν-associahedron. Finally, we present three polytopality conjectures, evidence supporting them, and some hints about potential generalizations to other finite Coxeter groups.

Contents

Part 2. The s-associahedron 2.1. The s-Tamari lattice (background)

Introduction

This paper is the second contribution (after [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF]) to a series of articles related to the s-weak order and the s-permutahedron. We originally introduced these objects in an extended abstract [START_REF] Ceballos | The s-weak order and s-permutahedra[END_REF], which is now developed into two long versions: the prequel [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF] and this present paper.

Figure 2. The s-weak order as the edge graph of the s-permutahedron for s = (0, 0, 2).

The purpose of the first paper [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF] was to develop the combinatorial foundations for the study of the s-weak order and the s-Tamari lattice, two partially ordered structures defined on certain families of decreasing trees, see examples in Figures 1-2 and3. Our motivation for introducing those objects was to fill the gap between recent developments on generalizations of the classical Tamari lattice on one side, and its connections to the classical weak order of permutations on the other.

On one side, we have the classical Tamari lattice (see [START_REF] Tamari | Monoides Préordonnés et Chaînes de Malcev[END_REF][START_REF] Müller-Hoissen | Associahedra, Tamari lattices and related structures[END_REF]), a partial order on Catalan objects (such as binary trees) whose Hasse diagram is the edge graph of a polytope called the associahedron. It is a central object in algebraic combinatorics, related to many interesting structures such as AVL trees in efficient sorting algorithms [START_REF] Adelson-Velsky | An algorithm for the organization of information[END_REF], Hopf algebras [LR02, LR98, AS06, HNT05], Cambrian lattices [START_REF] Reading | Cambrian lattices[END_REF], Permutrees [START_REF] Pilaud | [END_REF], cluster algebras [START_REF] Fomin | Cluster algebras. I. Foundations[END_REF][START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF], representation theory [START_REF] Mark | Conjectures on the quotient ring by diagonal invariants[END_REF][START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF], and more. Two important generalizations of the Tamari lattice that are relevant for our work are the m-Tamari lattice of Bergeron and Préville-Ratelle [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF] and the more general ν-Tamari lattice of Préville-Ratelle and Viennot [START_REF] Préville-Ratelle | The enumeration of generalized Tamari intervals[END_REF], whose study is motivated by conjectural connections with the theory of (multivariate higher) diagonal harmonics in representation theory, see e.g. [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF][START_REF] Bousquet-Mélou | The representation of the symmetric group on m-Tamari intervals[END_REF][START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF][START_REF] Bergeron | Hopf dreams and diagonal harmonics[END_REF].

On the other side, we have the classical weak order on permutations, whose Hasse diagram is the edge graph of a polytope called the permutahedron. It is known to be a lattice [START_REF] Th | Analyse Algébrique D'un Scrutin[END_REF] obtained from an orientation of the Cayley graph of the symmetric group. Both the lattice construction and the associated polytope also exist for other finite Coxeter groups [START_REF] Björner | Orderings of Coxeter groups[END_REF][START_REF] Hohlweg | Permutahedra and Associahedra[END_REF]. The weak order has well known connections with the classical Tamari lattice, which can be obtained from it both as a sublatttice [START_REF] Björner | Shellable nonpure complexes and posets[END_REF] and as a lattice quotient [START_REF] Reading | Cambrian lattices[END_REF]. These properties have interesting geometric and algebraic counterparts. Geometrically, the associahedron can be obtained by removing certain facets of the permutahedron [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF][START_REF] Hohlweg | Permutahedra and generalized associahedra[END_REF], and this translates into algebraic properties between certain related Hopf algebras [START_REF] Loday | Order structure on the algebra of permutations and of planar binary trees[END_REF][START_REF] Loday | Hopf algebra of the planar binary trees[END_REF]. The recent extensions of the Tamari lattice and the lack of (type A) 1 generalizations of the weak order lead to the question: what is the equivalent of the weak order for the ν-Tamari lattice? The s-weak order introduced in [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF] gives an answer to this question. Given a sequence of non-negative integers s, the s-weak order is a lattice structure on a family of combinatorial objects called s-decreasing trees. We also introduced the s-Tamari lattice as a sublattice of the s-weak order and showed that it is isomorphic to a well chosen ν-Tamari lattice.

Tamari lattice

Weak order s-Tamari lattice ν-Tamari lattice s-Weak order The purpose of this second paper is to investigate the underlying geometric structure of the s-weak order and the s-Tamari lattice. As we can see from Figures 1 and3, the s-weak order and the s-Tamari lattice can be realized as the edge graph of a much richer geometric structure, whose faces can be explicitly described in terms of a special family of intervals which we call pure intervals and pure s-Tamari intervals. This leads to two main definitions: (1) the s-permutahedron is the complex of pure intervals of the s-weak order and (2) the s-associahedron is the complex of pure s-Tamari intervals of the s-Tamari lattice. In this second paper, we introduce these concepts and develop the geometric foundations for the study of s-permutahedra and s-associahedra. 1 There are further generalizations in the context of Coxeter groups. In this paper, we mainly focus on generalizations which are related to Coxeter groups of type A. Some discussions about other types are mentioned in Section 3.1.

Associahedron Permutahedron

s-Associahedron ν-Associahedron s-Permutahedron

The paper is subdivided into three parts. Part 1 is dedicated to the introduction and study of the s-permutahedron (Definition 1.2.3), whose faces are given by pure intervals of the s-weak order (Definition 1.2.1). We present enumerative results about the number of faces by giving an explicit formula for the f -polynomial (Proposition 1.2.4), and describe a more efficient recursive formula to compute it (Proposition 1.2.5). The main result of this part is to prove that the s-permutahedron is a combinatorial complex (Theorem 1.2.6) which, in particular, requires that the intersection of two faces is also a face of the complex (Theorem 1.4.1 and Corollary 1.4.13). Our proof is purely combinatorial and is based on an explicit characterization of pure intervals (Theorem 1.3.9) using the notions of variations and essential variations.

In Part 2, we introduce and study the s-associahedron (Definition 2.2.3), whose faces are given by pure s-Tamari intervals of the s-Tamari lattice (Definition 2.2.1). We present an explicit formula for its f -polynomial (Proposition 2.2.4), which provides natural definitions of the s-Catalan and the s-Narayana numbers. The main result of this part is to show that the s-associahedron coincides with the ν-associahedron introduced by Ceballos, Padrol, and Sarmiento in [START_REF] Ceballos | Geometry of ν-Tamari lattices in types A and B[END_REF] (Theorem 2.2.9). The ν-associahedron is a polytopal complex of bounded faces induced by certain arrangement of tropical hyperplanes, and its edge graph gives a geometric realization of the ν-Tamari lattice [START_REF] Ceballos | Geometry of ν-Tamari lattices in types A and B[END_REF]. This proves, in particular, that the s-associahedron is also a polytopal complex.

In Part 3, we present three conjectures about geometric realizations of the s-permutahedron and the s-associahedron (Section 3.1), as well as some hints about potential generalizations of our work in the context of finite Coxeter groups (Section 3.2). The first conjecture (Conjecture 3.1.1) states that pure intervals of the s-weak order can be realized as convex polytopes. The second conjecture (Conjecture 3.1.2) asserts that the s-permutahedron can be geometrically realized as a polytopal subdivision of a zonotope, and the third (Conjecture 3.1.3) that there is such a realization such that the s-associahedron can be obtained from it by removing some facet defining inequalities. All these conjectures are strongly supported by computer evidence. Several examples are illustrated in Figure 4. In particular, we show that they hold in full generality in dimensions 2 and 3 (Section 3.3).

We remark that these conjectures were already present in our initial extended abstract [START_REF] Ceballos | The s-weak order and s-permutahedra[END_REF], and have been partially solved since. Indeed, in [GDMP + 23], for a composition s without any 0, the authors provide a realization of the s-permutahedron as the dual of the complex of interior faces of a triangulation of a flow polytope. From this, using the Cayley trick and techniques from tropical geometry, they are able to construct the desired geometric realization of the s-permutahedron. The results in [GDMP + 23] solve Conjectures 3.1.1 and 3.1.2 for the special case where s contains no zeros. The case where s contains zeros is still open, and Conjecture 3. 1.3 remains open in general. We present a further discussion on these connections in Section 3.4. We remark that pure intervals also appear in the work of Lacina [START_REF] Lacina | Poset Topology of s-Weak Order via SB-Labelings[END_REF], where he shows that they are the only intervals of the s-weak order which are homotopy equivalent to a sphere.

These recent advances motive the further study of the s-weak order and the s-permutahedron, as well as a deeper understanding on the nice properties of the family of pure intervals. In comparison to [GDMP + 23], this paper develops the foundations for the study of s-permutahedra and s-associahedra and explores the combinatorial/geometric properties of the s-permutahedra for all s (with or without zeros).

Beside the paper, we provide the SageMath [START_REF]SageMath, the Sage Mathematics Software System (Version 9[END_REF] code used to reach the results as well as a demo SageMath worksheet with computations of all examples in this paper [START_REF] Pons | Sagemath code and demo for s-weak order and s-permutahedra[END_REF].

Figure 4. The s-permutahedron and the s-associahedron obtained from it by removing certain facets, for s = (0, 2, 2, 2), s = (0, 2, 3, 2), and s = (0, 3, 3, 3).

Part 1. The s-permutahedron 1.1. The s-weak order (background) 1.1.1. Lattice definition through s-decreasing trees and tree-inversions. In this Section, we recall the main definitions and results of [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF] needed for Part 1 of this paper. We call a sequence s = (s(1), s(2), . . . , s(n)) of non-negative integers a weak composition of length ℓ(s) = n. If for all i, s(i) > 0, this is simply a composition. An s-decreasing tree is a rooted planar tree with n internal nodes labeled bijectively by 1, . . . , n, such that node i has s(i) + 1 children and such that labels are decreasing from root to leaves. An example is given on Figure 5.

As each node is given a unique label, we usually write the node y instead of the node labeled by y for convenience. For an s-decreasing tree T and a node y such that s(y) = m, we write T y 0 , . . . , T y m the m + 1 children of y. Then T y 0 is the left child of y, while T y 1 , . . . , T y m-1 are the middle children of y and T y m is the right child of y. Besides, if m > 0, we say that T y 0 (resp. T y m ) is a strict left (resp. strict right) child of y. Note that the word child refers here to the whole subtree not just the child node.

An s-decreasing tree T is characterized by its multi-set of tree-inversions inv(T ). Let c < a be two nodes a of an s-decreasing tree T , the cardinality of the tree-inversion (c, a), written # T (c, a), is given As we explain in [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF], s-decreasing trees are a generalization of permutations. More precisely, if s does not contain any zeros, s-decreasing trees correspond to certain multi-permutations where the letter i is repeated s(i) times: they are in bijection with stirling permutations, i.e., 121-avoiding multipermutations. In particular, if s = (1, 1, . . . ), the s-decreasing trees are the decreasing binary trees, known to be in bijection with classical permutations. Thus, the tree-inversions are a generalization of the classical inversion sets of permutations. It can be understood as a multi-set where each inversion (c, a) appears #(c, a) times. Many classical notions and operations on sets can be generalized to multi-sets. Definition 1.1.1 (Definitions 1.4 and 1.5 of [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF]). Let I be a multi-set of inversions (c, a) with a < c. We write # I (c, a) the number of occurrences of (c, a) in I. If there is no occurrence of (c, a) in I we write (c, a) / ∈ I or equivalently # I (c, a) = 0. Given two multi-sets of inversions I and J, we say that I is included in J (resp. strictly included) and write I ⊆ J (resp.

s = (0, 0, 2, 1, 3) 5 4 3 2 1 T 5 0 = 4 (strict) left child T 5 1 = ∅ middle children T 5 2 = 3 2 1 T 5 3 = ∅ (strict) right child #(5, 4) = 0 #(5, 3) = 2 #(5, 2) = 2 #(5, 1) = 2 #(4, 3) = 1 #(4, 2) = 1 #(4, 1) = 1 #(3, 2) = 2 #(3, 1) = 2 #(2, 1) = 0
I ⊂ J) if # I (c, a) ≤ # J (c, a) (resp. # I (c, a) < # J (c, a)) for all (c, a) ∈ I.
Given a weak composition s with ℓ(s) = n, we write Σ s the maximal s-inversion set defined by # Σs (c, a) = s(c) for all 1 ≤ a < c ≤ n.

We say that a multi-set of inversions I is transitive if for all triplets a < b < c, either # I (b, a) = 0 or

# I (c, a) ≥ # I (c, b).
Given a weak composition s with ℓ(s) = n and

I ⊆ Σ s , then I is planar if for all triplets 1 ≤ a < b < c ≤ n, either # I (b, a) = s(b) or # I (c, b) ≥ # I (b, a).
We prove the following. Proposition 1.1.2 (Proposition 1.6 of [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF]). For s a given weak composition, a multi-set of inversions is the multi-set of tree-inversions of an s-decreasing tree T if and only if it is planar, transitive, and included in Σ s . We then call it an s-tree-inversion set.

Even though they might seem technical, the transitivity and planarity conditions can be naturally explained by picture, as in Figure 6. These conditions regard the possible positions for the triplet c > b > a inside the tree. By picture, it is then clear that the transitivity and planarity conditions are satisfied by any multi-set of inversions corresponding to an s-decreasing tree. The proof that they are sufficient conditions to obtain an s-decreasing tree is done using an explicit construction algorithm [CP22, Algorithm 1.8].

Tree-inversions and tree-inversion sets are fundamental notions to work on s-decreasing trees, and are specially useful in proofs. The methodology we often use is to first understand looking at the trees, and then prove using tree-inversions. In particular, we use tree-inversions to define a partial order on s-decreasing trees by inclusion of their tree-inversion sets. This is the s-weak order, generalizing the classical weak order which is also defined by inclusion of inversions. Furthermore, we proved in [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF] that it is a lattice using the following two operations on multi-sets.

Definition 1.1.3 (Definition 1.12 of [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF]). The union of two multi-sets of inversions I and J is given by ). Let R and T be two s-decreasing trees of a same weak composition s with ℓ(s) = n. We say that R ≼ T if inv(R) ⊆ inv(T ) using the inclusion of multi-sets. We call the relation ≼ the s-weak order.

Theorem 1.1.6 (Theorem 1.21 of [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF]). The s-weak order is a lattice for every weak composition s.

The join of two s-decreasing trees T and R is given by

(2) inv(T ∨ R) = (inv(T ) ∪ inv(R)) tc .
We show an example of the computation of the join on Figure 7, please see [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF] for more detailed examples and computations.

1.1.2. Tree-ascents and cover relations. The cover relations of the s-weak order can be combinatorially described in terms of a notion of tree ascents defined in [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF].

Definition 1.1.7 (Definition 1.24 from [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF]). Let T be an s-decreasing tree of some weak composition s of length n. We say that (a, c) with a < c is a tree-ascent of T if (i) a is a descendant of c;

(ii) a does not belong to the right child of c;

(iii) if a is a descendant of b with c > b > a, then a belongs to the right descendant of b;

(iv) if it exists, the strict right child of a is empty.

T 3 1 2 # T (3, 2) = 2 # T (3, 1) = 0 # T (2, 1) = 0 R 3 2 1 # R (3, 2) = 0 # R (3, 1) = 0 # R (2, 1) = 1 T ∨ R 3 2 1 # T ∨R (3, 2) = 2 # T ∨R (3, 1) = 2 # T ∨R (2, 1) = 1 Figure 7. The computation of T ∨ R in the s-weak lattice (Figure 7 of [CP22])
The above definition can be visually interpreted from the tree: basically, a is located at the right end of a non right subtree of c, with the exception s(a) = 0, when a is allowed to have more children on its unique leg. Figure 8 shows a schematic illustration of these two possible occurrences of an (a, c) ascent. We prove in [CP22, Theorem 1.32] that tree-ascents correspond to cover relations of the s-weak order. More precisely, to each tree ascent (a, c) of a tree T , one can associate an s-tree rotation by increasing the cardinality of # T (c, a) by one and performing the transitive closure of the resulting multi-set of inversions. In [CP22, Lemma 1.29], we show that it increases all cardinalities #(c, a ′ ) by one where a ′ is a or a non-left descendant of a. The obtained tree covers T in the s-weak order.

It is sometimes useful to characterize tree-ascents using solely properties on tree-inversions. In [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF], we prove the following result, which basically translates all the conditions of Definition 1.1.7 in terms of tree-inversions. (iv) if s(a) > 0, for all a ′ < a, then #(a, a ′ ) = s(a) implies that #(c, a ′ ) > #(c, a).

The s-permutahedron

The key idea of this paper is that even if the s-week order is just a poset, it actually posses a much richer underlying geometric structure, encoded in a combinatorial object which we will call the s-permutahedron. The "faces" of the s-permutahedron will be given by pure intervals of the s-weak order, which we now introduce.

1.2.1. Pure intervals of the s-weak order. Let T be an s-decreasing tree and A be a (possibly empty) subset of tree-ascents of T . We denote by T + A the s-decreasing tree whose inversion set is obtained by increasing the cardinality # T (c, a) for (a, c) ∈ A by one and then taking the transitive closure. 2 Definition 1.2.1. Let T 1 ≼ T 2 be two s-decreasing trees for a given weak composition s. We say that the interval [T 1 , T 2 ] is a pure interval if T 2 = T 1 + A with A a subset of tree-ascents of T 1 .

We present examples on Figures 9, 10 A pure interval [T 1 , T 1 + A] is represented by the tree T 1 where we color in red all nodes a such that there is a tree-ascent (a, c) in A. By Remark 1.25 of [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF], the smaller value a is enough to identify the tree-ascent (a, c): indeed c is the ascendant of a with minimal value such that # T1 (c, a) < s(c). It is the only possibility for a tree-ascent (a, * ) to exist (whereas there could be other tree-ascents ( * , c)).

On Figure 9, the nodes 2 and 3 are colored, representing respectively the tree-ascents (2, 3) and (3, 4). On the right, the corresponding interval is shown. The maximum is obtained by increasing the 2 We use this notation for simplicity but it is not entirely consistent with [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF]. Indeed, we used the notation +(c, a) in [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF] on multi-sets to increase the cardinality #(c, a) without taking the transitive closure. Besides, A is formally a set of tree-ascents (a, c) and not a set of tree-inversions (c, a). cardinalities of the tree-inversions (3, 2) and (4, 3) and taking the transitive closure. For example, we see that (4, 1) has been increased by transitivity because (4, 3) was increased and #(3, 1) > 0. This is also equivalent to taking the lattice join of the two trees obtained by applying the two s-tree-rotations of the two selected tree-ascents (see Lemma 1.2.2). We present a second example on Figure 10, showing the minimal element of the interval with selected tree-ascents and the maximal element of the interval. You can check that all tree-inversions corresponding to tree-ascents have been increased.

Lemma 1.2.2. Let T 1 and T 2 be two s-decreasing trees such that T 2 = T 1 + A with A a subset of treeascents of T 1 . Then T 2 can be obtained as the join T 2 = a∈A (T 1 + a) over all trees T 1 + a obtained from T 1 by rotating a tree-ascent a ∈ A.

Proof. We denote by T 2 the join of the rotated trees by the tree-ascents of A and prove that T 2 = T 1 + A.

For a tree-ascent (a, c), let M (a,c) be the multi-set of inversions such that # M (a,c) (c, a) = # T1 (c, a) + 1 while all other values are unchanged. Similarly, we write M A := ∪ (a,c)∈A M (a,c) , i.e., all cardinalities (c, a) with (a, c) ∈ A have been increased by one. In particular, the tree-inversions of the tree T 1 + (a, c) resulting from a single rotation (a, c) are given by M tc (a,c) , i.e., the transitive closure of M (a,c) . Similarly, the tree-inversions of T + A are given by M tc A . By definition, we have M (a,c) ⊆ M A for all (a, c) ∈ A where the inclusion is the multi-set inclusion defined in Definition 1.1.1. This is compatible with the multi-set transitive closure of Definition 1.1.4, and so we have M tc (a,c) ⊆ M tc A . In other words, T 1 + (a, c) ≼ T 1 + A. By taking the lattice join, we obtain

T 2 ≼ T 1 + A.
Now by definition of the join, the inversions of T 2 are given by inv(T 2 ) = M tc 2 where M 2 = ∪ (a,c)∈A M tc (a,c) . In particular, M 2 ̸ = M A as it is the union of the transitive closures of the M (a,c) multi-sets. But, as the transitive closure can only increase the cardinality of a tree-inversion, for each (a, c)

∈ A we know that # M2 (c, a) ≥ # M (a,c) (c, a) = # T1 (c, a) + 1 = # M A (c, a). Besides, for each couple a ′ < c ′ such that (a ′ , c ′ ) ̸ ∈ A, we have # M2 (c ′ , a ′ ) ≥ # T1 (c ′ , a ′ ) = # M A (c ′ , a ′ )
. We obtain M A ⊆ M 2 . By taking the transitive closure, we have inv(T 1 + A) ⊆ inv(T 2 ) and so

T 1 + A ≼ T 2 . □ 1.
2.2. The combinatorial complex of pure intervals. We are now ready to define one of the main objects of this paper, the s-permutahedron.

Definition 1.2.3 (The s-permutahedron). The s-permutahedron Perm(s) is the collection of pure intervals [T, T + A] of the s-weak order. Here, T denotes an s-decreasing tree and A a subset of tree-ascents of T . The dimension of [T, T + A] is said to be equal to |A|. In particular, (1) the vertices of Perm(s) are s-decreasing trees T , and

(2) two s-decreasing trees are connected by an edge if and only if they are related by an s-tree rotation. We often refer to pure intervals [T, T + A] as faces of Perm(s), and say that one face is contained in another if the containment holds as intervals in the s-weak order. Figure 1 illustrates an example of the s-permutahedron Perm(0, 2, 2). As we can see, it is a polytopal complex whose faces are labeled by pure intervals, and whose edge graph is the Hasse diagram of the s-weak order.

As we have a (combinatorial) notion of face and dimension, we can also define the f -polynomial associated to a weak composition s by

(3) f s (t) := F ∈Perm(s) t dim(F )
The f -polynomial for our example in Figure 1 is

(4) f (0,2,2) (t) = 15 + 20t + 6t 2 .
Indeed, there are 15 s-decreasing trees (faces of dimension 0), 20 edges (faces of dimension 1) and 6 pure intervals of dimension 2, which correspond to the 6 polygons that appear naturally on the lattice. The following proposition is straightforward from the definition. Proposition 1.2.4. The f -polynomial of the s-permutahedron Perm(s) is given by

T (1 + t) asc(T ) ,
where the sum runs over all s-decreasing trees T and asc(T ) denotes the number of ascents of T .

Proof. Let f s (t) = T (1 + t) asc(T ) = c 0 + c 1 t + c 2 t 2 + . . . .
We need to show that c k counts the number of k-dimensional faces of Perm(s). This follows from the fact that every subset of ascents A of T , of size k, contributes a t k to the term (1 + t) asc (T ) . □

The polynomial T t asc(T ) is a natural generalization of the Eulerian polynomial which we call the s-Eulerian polynomial. Its coefficients are called the s-Eulerian numbers.

There is actually a recursive way to compute f s which is much better in practice than enumerating all the s-decreasing trees. This is described in the following proposition. Proposition 1.2.5. If s is a weak composition of length 1, then f s (t) = 1. If s be a weak composition of length n ≥ 2, then we write s = (s, u, v) where s is the sequence obtained by removing the last two values in s, u = s(n -1) and v = s(n). Then

(1) if n > 2 and u = 0, then

f s = f (s,v) f (0,v) ; (2) if n = 2 or u > 0, then f s (t) = (v + 1)f (s,u+v) (t) + vtf (s,u+v-1) (t).
For example if s = (u, v) is a weak composition of length 2. The s-decreasing trees have two nodes labeled 1 and 2. The node 2 is the root and has v + 1 children. The s-weak order is the chain between the s-decreasing tree where 1 is at the extreme left and the s-decreasing tree where 1 is at the extreme right. There are v + 1 s-decreasing trees (corresponding to the possible positions of 1) and v edges. We get f (u,v) (t) = v + 1 + vt. By Proposition 1.2.4, we also obtain f (u,v) (t) = v(1 + t) + 1. Indeed all trees but the maximal one have one ascent. The recursive computation of Proposition 1.2.5 also gives

f (u,v) (t) = (v + 1)f (u+v) (t) + vtf (u+v-1) = v + 1 + vt.
We can also compute the f -polynomial of Perm(0, 2, 2) in Figure 1 using our recursive formula in Proposition 1.2.5. We obtain

f (0,2,2) (t) = 3f (0,4) (t) + 2tf (0,3) (t) = 3(5 + 4t) + 2t(4 + 3t) = 15 + 20t + 6t 2 .
For the Perm(0, 0, 2) (Figure 2), we get

f (0,0,2) (t) = f (0,2) (t)f (0,2) (t) = (3 + 2t) 2 = 9 + 12t + 4t 2 .
We present many computations in Table 1. You can also compute more example using our demo SageMath worsheet [START_REF] Pons | Sagemath code and demo for s-weak order and s-permutahedra[END_REF].

Proof. The proof can be done bijectively. The base case is trivial: if s is of length 1, whatever the value of s(1) is, there is a unique s-decreasing tree with no ascent giving f (s) = 1. We then define two different bijections corresponding to Cases (1) and (2) and illustrate them on examples in Figures 12 and13 respectively. For Case (2), the bijection is divided into two different cases, depending on whether or not (n -1, n) is a selected tree-ascent. This corresponds to the two summands of the recursion. Looking at the examples, we believe that the bijections are straightforward. We explain them in detail below.

Let us prove Case (1). We have s = (s, 0, v). We prove that the pure intervals of s are in bijection with products of pure intervals of (s, v) and (0, v). Let T be an s-decreasing tree and A a subset of tree-ascents of T . The root of T is necessarily n with v + 1 subtrees. The node n -1 is the root of one of the subtrees. As we have s(n -1) = 0, the node n -1 has a unique child which we write Q (it can be empty or has a root i < n -1). Let s ′ = (s, v), we construct an s ′ -decreasing tree T ′ by replacing the node n -1 by its unique child Q. All the other subtrees stay the same. We relabel the root to n -1 instead of n to keep a standard labeling. If (a, c) with a < c < n -1 is a tree-ascent in T , it is still a tree-ascent in T ′ : it is either in Q or in any of the other subtrees of n. As s(n -1) = 0, we cannot have a tree-ascent (a, n -1). Besides, if (a, n) is a tree-ascent in T with a ̸ = n -1, then (a, n -1) is a tree-ascent in T ′ . Indeed, all conditions of Definition 1.1.7 are still satisfied. We set

A ′ = {(a, c) ∈ A; a < c < n -1} ∪ {(a, n -1); (a, n) ∈ A and a ̸ = n -1}.
Now we define s ′′ = (0, v) and T ′′ the s ′′ -decreasing tree obtained by keeping only the nodes n and n -1, which we relabel into 2 and 1 respectively. If (n -1, n) is a tree-ascent of T , we set A ′′ = {(1, 2)}, otherwise A ′′ = ∅. In the end, we have |A ′ | + |A ′′ | = |A| so the monomial corresponding to the pure interval (T, A) is obtained by a product of monomials of (T ′ , A ′ ) and (T ′′ , A ′′ ). Besides, the reverse operation is easy: T ′′ gives the position where n -1 needs to be inserted. The selected tree-ascents stay the same up to relabeling. In particular, if (a, n -1) is a tree-ascent in T ′ , then (a, n) is a tree-ascent in T even if a ∈ Q because it is still at the right end of the subtree. We illustrate this bijection on Figure 12 with s = (0, 0, 2, 0, 3).

Let us prove Case (2). Note that if s is of length 2, we have shown earlier that the recursive computation gives the expected result. We then assume that s = (s, u, v) and u ̸ = 0. In this case, we prove that there is a bijection between pure intervals of s and some marked pure intervals of (s, u + v) and (s, u + v -1). Let T be an s-decreasing tree and A a subset of tree-ascents of T . Let us first suppose that (n-1, n) ̸ ∈ A. In this case, (T, A) is sent to a marked pure interval of s ′ = (s, u + v). We construct T ′ by merging the nodes n and n -1. In T , n -1 has u + 1 subtrees which become subtrees of the root in T ′ , at the former Table 1. Some values of f s (t)

t 3 = t 2 × t 5 4 1 3 2 → 4 3 1 2 2 1 t 2 = t 2 × 1
f (0,0,1) (t) = t 2 + 4t + 4 f (0,0,0,1) (t) = t 3 + 6t 2 + 12t + 8 f (0,2,0,1) (t) = 2t 3 + 13t 2 + 26t + 16 f (0,0,2) (t) = 4t 2 + 12t + 9 f (0,0,0,2) (t) = 8t 3 + 36t 2 + 54t + 27 f (0,2,0,2) (t) = 12t 3 + 58t 2 + 90t + 45 f (0,0,3) (t) = 9t 2 + 24t + 16 f (0,0,0,3) (t) = 27t 3 + 108t 2 + 144t + 64 f (0,2,0,3) (t) = 36t 3 + 153t 2 + 212t + 96 f (0,1,1) (t) = t 2 + 6t + 6 f (0,0,1,1) (t) = t 3 + 12t 2 + 28t + 18 f (0,2,1,1) (t) = 2t 3 + 21t 2 + 48t + 30 f (0,1,2) (t) = 4t 2 + 15t + 12 f (0,0,1,2) (t) = 8t 3 + 51t 2 + 90t + 48 f (0,2,1,2) (t) = 12t 3 + 76t 2 + 135t + 72 f (0,1,3) (t) = 9t 2 + 28t + 20 f (0,0,1,3) (t) = 27t 3 + 136t 2 + 208t + 100 f (0,2,1,3) (t) = 36t 3 + 185t 2 + 288t + 140 f (0,2,1) (t) = 2t 2 + 9t + 8 f (0,0,2,1) (t) = 4t 3 + 30t 2 + 57t + 32 f (0,2,2,1) (t) = 6t 3 + 44t 2 + 85t + 48 f (0,2,2) (t) = 6t 2 + 20t + 15 f (0,0,2,2) (t) = 18t 3 + 96t 2 + 152t + 75 f (0,2,2,2) (t) = 24t 3 + 130t 2 + 210t + 105 f (0,2,3) (t) = 12t 2 + 35t + 24 f (0,0,2,3) (t) = 48t 3 + 220t 2 + 315t + 144 f (0,2,2,3) (t) = 60t 3 + 282t 2 + 413t + 192 f (0,3,1) (t) = 3t 2 + 12t + 10 f (0,0,3,1) (t) = 9t 3 + 56t 2 + 96t + 50 f (0,2,3,1) (t) = 12t 3 + 75t 2 + 132t + 70 f (0,3,2) (t) = 8t 2 + 25t + 18 f (0,0,3,2) (t) = 32t 3 + 155t 2 + 230t + 108 f (0,2,3,2) (t) = 40t 3 + 198t 2 + 301t + 144 f (0,3,3) (t) = 15t 2 + 42t + 28 f (0,0,3,3) (t) = 75t 3 + 324t 2 + 444t + 196 f (0,2,3,3) (t) = 90t 3 + 399t 2 + 560t + 252 f (0,1,0,1) (t) = t 3 + 8t 2 + 18t + 12 f (0,3,0,1) (t) = 3t 3 + 18t 2 + 34t + 20 f (0,1,0,2) (t) = 8t 3 + 42t 2 + 69t + 36 f (0,3,0,2) (t) = 16t 3 + 74t 2 + 111t + 54 f (0,1,0,3) (t) = 27t 3 + 120t 2 + 172t + 80 f (0,3,0,3) (t) = 45t 3 + 186t 2 + 252t + 112 f (0,1,1,1) (t) = t 3 + 14t 2 + 36t + 24 f (0,3,1,1) (t) = 3t 3 + 28t 2 + 60t + 36 f (0,1,1,2) (t) = 8t 3 + 57t 2 + 108t + 60 f (0,3,1,2) (t) = 16t 3 + 95t 2 + 162t + 84 f (0,1,1,3) (t) = 27t 3 + 148t 2 + 240t + 120 f (0,3,1,3) (t) = 45t 3 + 222t 2 + 336t + 160 f (0,1,2,1) (t) = 4t 3 + 33t 2 + 68t + 40 f (0,3,2,1) (t) = 8t 3 + 55t 2 + 102t + 56 f (0,1,2,2) (t) = 18t 3 + 104t 2 + 175t + 90 f (0,3,2,2) (t) = 30t 3 + 156t 2 + 245t + 120 f (0,1,2,3) (t) = 48t 3 + 235t 2 + 354t + 168 f (0,3,2,3) (t) = 72t 3 + 329t 2 + 472t + 216 f (0,1,3,1) (t) = 9t 3 + 60t 2 + 110t + 60 f (0,3,3,1) (t) = 15t 3 + 90t 2 + 154t + 80 f (0,1,3,2) (t) = 32t 3 + 165t 2 + 258t + 126 f (0,3,3,2) (t) = 48t 3 + 231t 2 + 344t + 162 f (0,1,3,3) (t) = 75t 3 + 342t 2 + 490t + 224 f (0,3,3,3) (t) = 105t 3 + 456t 2 + 630t + 280 f (0,4,4,4) (t) = 280t 3 + 1100t 2 + 1404t + 585 f (0,5,5,5) (t) = 585t 3 + 2170t 2 + 2640t + 1056 f (0,6,6,6) (t) = 1056t 3 + 3774t 2 + 4446t + 1729 f (0,2,2,2,2) (t) = 120t 4 + 924t 3 + 2380t 2 + 2520t + 945 f (0,3,3,3,3) (t) = 945t 4 + 5610t 3 + 11946t 2 + 10920t + 3640 f (0,2,1,0,2) (t) = 24t 4 + 188t 3 + 498t 2 + 549t + 216 f (0,2,0,1,3,2) (t) = 640t 5 + 6278t 4 + 21941t 3 + 35474t 2 + 27108t + 7938 f (0,1,1,2,0,3,3) (t) = 16200t 6 + 166377t 5 + 665262t 4 + 1349600t 3 + 1481796t 2 + 841320t + 194040 position of n -1.
The root is relabeled n -1 in T ′ and has now u + v + 1 subtrees (it has lost one subtree and gained u + 1). Any tree-ascent of T , (a, c) with a < c < n -1 is still a tree-ascent in T ′ . Similarly, if (a, n -1) was a tree-ascent in T , it is also a tree-ascent in T ′ (except that now n -1 is the root). Finally, if (a, n) was a tree-ascent in T and a ̸ = n -1, then (a, n -1) is a tree-ascent in T ′ (whether a was a descendant of n -1 or not). As we have by hypothesis that (n -1, n) ̸ ∈ A, we can keep the selected tree-ascents of T in T ′ . We get

A ′ = {(a, c) ∈ A; a < c ≤ n -1} ∪ {(a, n -1); (a, n) ∈ A} with |A ′ | = |A|.
This operation is surjective. To obtain a bijection, we need to mark u + 1 consecutive edges from the root of T ′ : they give the subtrees and insertion position of the node n -1 in T . All tree-ascents of T ′ are still tree-ascents in T : a tree-ascent (a, n -1) in T ′ corresponds either to (a, n -1) in T if a belongs to first u marked edges, otherwise it transforms into a (a, n) tree-ascent. We thus obtain all pure intervals of s where (n -1, n) ̸ ∈ A. As there are v + 1 way to mark the edges of an s ′ -decreasing tree, we obtain that f s (t) = (v + 1)f s ′ (t) + f ′′ s where f ′′ s enumerates the pure intervals of s where (n -1, n) is in A. This bijection is illustrated for s = (0, 0, 0, 2, 3) in the first column of Figure 13: we show the 4 possible markings on a given pure interval of (0, 0, 0, 5) and their pre-images.

If (n -1, n) ∈ A, we send (T, A) to a pure interval of s ′′ = (s, u + v -1). As (n -1, n) is a tree-ascent, we know that the last subtree of n -1 in T is empty (this is true because u ̸ = 0). We then construct T ′′ by deleting this last subtree and then merging the nodes n -1 and n. The new root in T ′′ now has u + v subtrees. The same arguments as earlier work for tree-ascents different than (n -1, n) and we can define

A ′′ = {(a, c) ∈ A; a < c ≤ n -1} ∪ {(a, n -1); (a, n) ∈ A and a ̸ = n -1}. As we loose the tree-ascent (n -1, n), we have |A ′′ | = |A| -1.
Besides, to obtain a bijection we now need to mark u consecutive edges of the root but we cannot mark the last u edges. Indeed, we need (n -1, n) to be a tree-ascent of T which implies that n -1 can never be in the last subtree of n. There are v possible ways to mark the edges of an s ′′ -decreasing tree, we obtain f ′′ s = vtf s ′′ . We illustrate the bijection for s = (0, 0, 0, 2, 3) on the second column of Figure 13: we show the 3 possible markings on given pure interval of (0, 0, 0, 4) and their pre-images. □

Looking at many different examples, we believe that the s-permutahedron can be realized as a polytopal complex for any weak composition s (see Part 3). Two essential conditions for this to hold are listed in the following theorem, which is the main result of Part 1 of this paper. Theorem 1.2.6. For any weak composition s, the s-permutahedron Perm(s) is a combinatorial complex in the following sense.

(1) The face of a face is also a face: If I ∈ Perm(s) is a face (a pure interval) and J ⊆ I is a face (a pure interval) then J ∈ Perm(s).

(2) The intersection of any two faces is also a face:

If I, J ∈ Perm(s) are two faces (pure intervals) then I ∩ J ∈ Perm(s) is also a face (a pure interval).

Part (1) of this theorem follows by definition. The intersection property in Part ( 2) is more involved and we need to develop some tools in order to prove it. First, we will give a complete characterization of pure intervals in Section 1.3 (Theorem 1.3.9), which will then be used to prove the intersection property in Section 1.4 (Theorem 1.4.1).

Characterization of pure intervals

Although the definition of pure intervals is very simple and intuitive, we now aim to provide a characterization which is rather technical but conveniently useful for proofs (Theorem 1.3.9). In order to do this, we need to introduce the notions of variations, essential variations, and minimal essential variations of an interval. Roughly speaking, the variations are the inversions that increase in the interval, while the minimal essential variations of a pure interval [T 1 , T 1 + A] will characterize the tree-ascents A (Theorem 1.3.4).

Variations and essential variations of an interval.

Definition 1.3.1 (Variations). Let T 1 ≼ T 2 be two s-decreasing trees for a given weak composition s. We say that a tree-inversion (c, a) with c > a varies in the interval [T 1 , T 2 ] if # T2 (c, a) > # T1 (c, a). In this case, we say that (c, a) v where v = # T1 (c, a) is a variation of [T 1 , T 2 ]. We call v the value of the variation. The difference # T2 (c, a) -# T1 (c, a) is the amplitude. We sometimes omit the value v and write that (c, a) is a variation, meaning that there exists v for which (c, a) v is a variation.

We say that (c, a) v is an essential variation of [T 1 , T 2 ] if (c, a) v is a variation and there is no b with a < b < c such that a belongs to a middle child of b and (c, b) varies. Finally, we say that an essential variation (c, a) is minimal if there is no b with a < b < c with (b, a) an essential variation.

We write Var([T 1 , T 2 ]) the set of variations of the interval, and EVar(T 1 , T 2 ) the set of essential variations. 9 and10. This can be computed using SageMath as we show in [START_REF] Pons | Sagemath code and demo for s-weak order and s-permutahedra[END_REF].

We present below two examples based on Figures

Example 1.3.2. On the pure interval of Figure 9, the variations with their respective values are (3, 1) 1 , (3, 2) 1 , (4, 1) 0 , (4, 2) 0 , (4, 3) 0 . They are all of amplitude 1. Only (3, 2) 1 and (4, 3) 0 are essential variations. For example, (4, 2) 0 is not an essential variation because 2 belongs to the middle child of 3 and (4, 3) varies. In this case, both essential variations are minimal and correspond to the tree-ascents in A of the minimal tree.

Example 1.3.3. The pure interval of Figure 10 has 15 variations, 10 of which are essential variations: (4, 1) 0 , (6, 2) 1 , (9, 1) 0 , (9, 4) 0 , (9, 6) 1 , (10, 1) 2 , (10, 4) 2 , (10, 5) 0 , (10, 8) 0 , (10, 9) 2 . For example, (10, 2) 2 is a variation but not an essential variation. Besides, there are seven minimal essential variations: (4, 1) 0 , (6, 2) 1 , (9, 4) 0 , (9, 6) 1 , (10, 5) 0 , (10, 8) 0 , (10, 9) 2 . For example, (9, 1) 0 is not minimal because (4, 1) 0 is an essential variation. The seven minimal essential variations in this case also correspond to the tree-ascents in A of the minimal tree.

In Examples 1.3.2 and 1.3.3, the minimal essential variations of both pure intervals [T 1 , T 1 + A] correspond to the tree-ascents in A. This property holds in general and will be proved later on. Theorem 1.3.4 (Minimal essential variations of pure intervals). The set of minimal essential variations of a pure interval [T 1 , T 1 + A] is in correspondence with A. More precisely, (a, c) ∈ A if and only if there exists v for which (c, a) v is a minimal essential variation.

1.3.2. The Characterization Theorem. In order to characterize the variation sets of pure intervals we need some further properties.

Lemma 1.3.5. For all a < c such that (c, a) v is a variation but not an essential variation, there is a unique b > a such that (c, b) v is an essential variation and a belongs to a middle child of b.

Proof. Let us suppose that (c, a) v is a variation but not an essential variation. We know there is b such that a belongs to a middle child of b and (c, b) varies. We take such a b to be maximal. Note that as a is a descendant of b, then # Therefore, (c, b 2 ) is not an essential variation. This proves the uniqueness part. □

T1 (c, b) = # T1 (c, a) = v. As b is maximal, there is no b ′ > b such that (c, b ′
For example, there are three non-essential variations on the pure interval of Figure 9. For (3, 1) 1 the unique essential variation is (3, 2) 1 . For both (4, 2) 0 and (4, 1) 0 , the unique essential variation is (4, 3) 0 .

b = b 1 > b 2 > • • • > b k = a with # S (b 1 , b 2 ) = v + k and # S (b i , b i+1 ) > 0. This path does not exist as such in inv(T ) because inv(T ) is transitive and # T (b, a) = v. Besides, by definition of S, we have # T (b i , b i+1 ) ≤ # S (b i , b i+1 ) ≤ # T (b i , b i+1 ) + 1. This gives us in particular (6) # T (b 1 , b 2 ) ≥ v + k -1 > v
because k > 1 by hypothesis. This implies that there exist i such that # T (b i , b i+1 ) = 0. We take the minimal i that satisfies this property (b i is as close of b as possible). In particular, by transitivity,

# T (b, b i ) ≥ v + k -1 > v.
i+1 ) = # T (b, b i ) > v. Now, if j > i with # T (b j , b j+1 ) = 0
, by taking the minimal j satisfying this property, we prove in a similar way that # T (b, b j+1 ) > v. By induction, we obtain that for all i with # T (b i , b i+1 ) = 0, we have # T (b, b i+1 ) > v. Let i ′ be the maximal value satisfying the property. We have that

b = b 1 > b i ′ > b i ′ +1 > • • • > b k = a
is a transitive path in inv(T ), which implies that # T (b, a) > v and leads to a contradiction. □ Lemma 1.3.8 is not an equivalence; see Figure 14 for an example of a +1-interval that is not a pure interval. The main result of this section is the following characterization of pure intervals.

Theorem 1.3.9 (Characterization Theorem of pure intervals). Let T 1 and T 2 be two s-decreasing trees for a given weak composition s, then [T 1 , T 2 ] is a pure interval if and only if it is a +1-interval and for all a < b < c

(1

) if (c, a) v ∈ Var([T 1 , T 2 ]) and (b, a) w ∈ Var([T 1 , T 2 ]) then (c, b) v ∈ Var([T 1 , T 2 ]); (2) if (c, a) v ∈ EVar([T 1 , T 2 ]) and (c, b) v ∈ EVar([T 1 , T 2 ]) and s(b) ̸ = 0 then (b, a) 0 ∈ Var([T 1 , T 2 ]).
Note that for Condition (2), we require that # T1 (c, a) = # T1 (c, b).

Example 1.3.10. You can check that the two conditions of Theorem 1.3.9 are satisfied on the interval of Figure 10. For (1), you can see for example that both (10, 4) 2 and (9, 4) 0 are variations and indeed (10, 9) 2 is also a variation. Similarly, (9, 1) 0 and (4, 1) 0 are essential variations, and (9, 4) 0 is a variation. Besides (2) implies that as (10, 4) 0 and (10, 9) 0 are essential variations and s(9) > 0, then (9, 4) 0 is a variation. Similarly, as (9, 1) 0 and (9, 4) 0 are essential variations and s(4) > 0, this implies that (4, 1) 0 is a variation. Note that we also have that (10, 8) 0 and (10, 5) 0 are essential variations, but in this case (8, 5) 0 is not because s(8) = 0. Finally, you can see that (2) is not satisfied on variations: (10, 4) 2 and (10, 3) 2 are variations and s(4) > 0 but (4, 3) 0 is not a variation.

Example 1.3.11. On the other hand, Figure 14 shows an interval, i.e., two trees T 1 ≼ T 2 , such that [T 1 , T 2 ] is a +1-interval but not a pure interval. In other words, T 2 is not obtained by increasing the cardinality of a subset of the tree-ascents of T 1 . In this example, both conditions of Theorem 1.3.9 are not satisfied. Indeed, for (1), (4, 1) 0 and (3, 1) 1 are variations but (4, 3) 0 is not. For (2), (5, 4) 0 and (5, 3) 0 are essential variations and s(4) > 0 but (4, 3) 0 is not a variation. In the following two sections we will focus on the proof of the Characterization Theorem of pure intervals, Theorem 1.3.9. The techniques used to prove this result will also lead to a proof of Theorem 1.3.4, which characterizes the subset of tree-ascents of a pure interval in terms of its minimal essential variations.

For the sake of clarity, we are going to give a name to the +1-intervals satisfying both Conditions (1) and (2) of Theorem 1.3.9. We call them pure-candidate intervals. Our goal is to prove that pure-candidate intervals are the same as pure intervals. We separate this result into two parts: in Section 1.3.3 we show that pure-candidate intervals are pure, and in Section 1.3.4 we show that pure intervals are purecandidate.

] = [T 1 , T 1 + A] where (a, c) ∈ A if and only if (c, a) is a minimal essential variation of [T 1 , T 2 ].
We start by examining Condition (1) and show some useful properties.

Lemma 1.3.13. Let [T 1 , T 2 ] be +1-interval satisfying Condition (1). We have that for all a < c, if (c, a) varies then a is a descendant of c in T 1 .

Proof. Suppose that it is not the case, in particular, a cannot be a middle descendant of c and so either It is actually possible to prove that Condition (1) is equivalent to the one of Lemma 1.3.14, i.e., if the condition is true on essential variations then it is true for all variations. The proof is bit technical and not necessary at the moment.

We will prove Proposition 1.3.12 in two steps: first, we show that minimal essential variations are indeed tree-ascents of T 1 (Proposition 1.3.18), then that every variation of the interval is obtained by transitivity from the minimal essential variations (Proposition 1.3.23).

1.3.3.1. minimal essential variations are tree-ascents. The following lemmas explore some useful properties of variations and essential variations in pure-candidate intervals. This is a version of Lemma 1.3.6 now specific to essential variations. Note that Lemma 1.3.6 is not directly true for essential variations and that this version is not true in general: we need a pure-candidate interval. See for example the pure interval of Figure 10. We have that (10, 4) 2 and (4, 1) 0 are essential variations, the lemma implies that (10, 1) 0 is also an essential variation. On the other hand, (10, 9) 2 and (9, 6) 1 are essential variations but (10, 6) 2 is not. On the example of Figure 14 which is not a pure interval, we see that we have (5, 4) 0 an essential variation as well as (4, 1) 0 but (5, 1) 0 is not an essential variation (it is a variation but 1 is a middle child of 3 and (5, 3) varies).

Proof. By Lemma 1.3.6, we know that (c, a) varies in [T 1 , T 2 ]. More precisely, # T1 (c, a) ≤ v and # T2 (c, a) > v. Because [T 1 , T 2 ] is a pure-candidate interval, it is in particular a +1-interval and so (c, a) v is a variation of amplitude one. We need to prove that it is an essential variation. Suppose that it is not: there exists b In particular, Lemma 1.3.17 implies that the variation (b, a) 0 in Condition (2) is always an essential variation. We can now prove the following proposition. 3.17, it is necessarily an essential variation. This contradicts the fact that (c, a) is a minimal essential variation.

Let us prove Condition (iv), i.e., if it exists, the strict right child of a is empty. Suppose that it is not and that a ′ is the root of its right subtree. As s(a) > 0, we have # T2 (c, a ′ ) ≥ # T2 (c, a) > # T1 (c, a) = # T1 (c, a ′ ) and so (c, a ′ ) v is a variation. Moreover, it is an essential variation because if a ′ is a middle descendant of any node b, so is a. Condition (2) then states that (a, a ′ ) 0 is a variation and so # T1 (a, a ′ ) = 0 which contradicts our initial statement. □ 1.3.3.2. Transitive closure of minimal essential variations. To prove that every variation is obtained by transitivity from the minimal essential variations, we introduce the fundamental notion of variation path. Example 1.3.20. Here are all variation paths for the variations of Figure 9: • (3, 2) 1 : 3 > 2;

• (3, 1) 1 : 3 > 2;

• (4, 3) 0 : 4 > 3;

• (4, 2) 0 : 4 > 3;

• (4, 1) 0 : 4 > 3.

Example 1.3.21. Here are all variation paths for the variations of Figure 10: • (10, 8) 0 : 10 > 8;

• (10, 5) 0 : 10 > 5;

• (10, 9) 2 and (10, 6) 2 and (10, 2) 2 : 10 > 9;

• (10, 4) 2 and (10, 3) 2 : 10 > 9 > 4;

• (10, 1) 2 : 10 > 9 > 4 > 1;

• (9, 4) 0 and (9, 3) 0 : 9 > 4;

• (9, 1) 0 : 9 > 4 > 1;

• (9, 6) 1 and (9, 2) 1 : 9 > 6;

• (6, 2) 1 : 6 > 2;

• (4, 1) 0 : 4 > 1.

Lemma 1.3.22.

If I = [T 1 , T 2 ]
is a pure-candidate interval, then the variation path of any variation (c, a) v satisfies the following properties (i) for all j > i, then (c i , c j ) 0 is an essential variation;

(ii) either c k = a or a belongs to a middle child of c k ;

(iii) (c, c 1 ) is a minimal essential variation as well as (c i , c i+1 ) for all i < k.

Proof. Property (i) is a consequence of Condition (2) of pure-candidate intervals. Indeed, by definition of the variation path we have that (c, c i ) v and (c, c j ) v are essential variations and s(c i ) > 0 as 0 ≤ # T1 (c i , a) < s(c i ). This implies that (c i , c j ) 0 is an essential variation (using Condition (2) and Lemma 1.3.17). Property (ii) is a direct consequence of Lemma 1.3.5. Indeed, suppose that c k ̸ = a, i.e., (c, a) is not an essential variation. Then, there is a unique b > a such that (c, b) v is an essential variation with a a middle child of b. In particular, # T1 (b,

a) < s(b) so b ∈ {c i } k i=1 . Now, if b ̸ = c k , then b = c i with i < k. By Property (i), we have # T1 (c i , c k ) = 0, which implies # T1 (c k , a) = s(c k )
and contradicts the definition of the variation path.

We now prove Property (iii). We know by definition that (c, c 1 ) v is an essential variation. Let us suppose that it is not minimal, i.e., there is b with c > b > c 1 such that (b, c 1 ) is an essential variation. Using Lemma 1.3.14, we obtain that (c, b) v is an essential variation. As b does not belong to the variation path, we have by definition that # T1 (b, a) = s(b). We obtain a contradiction to the planarity condition on tree-inversions (see Definition 1.1.1) on b > c 1 > a. Indeed, we should have either # T1 (c 1 , a) = s(c 1 ) which is impossible by definition of the variation path, or # T1 (b, c 1 ) ≥ # T1 (b, a) = s(b) which is impossible as we have supposed (b, c 1 ) to be a variation.

This gives us that (c, c 1 ) is a minimal variation. Now, let us look at (c i , c i+1 ). First, see that if i ̸ = k, (c i , a) 0 is a variation. Indeed, (c i , c k ) 0 is an essential variation and either c k = a or a is a middle child of c k so (c i , a) varies by transitivity. Now if c i+1 is the first element of the variation path between c i and a, we are done by applying our previous argument on this new variation path. We need to prove that this is always the case, i.e., if b belongs to the variation path between c i and a, it also belongs to the variation path between c and a. Let b be such that c i > b > a with (c i , b) 0 an essential variation and # T1 (b, a) < s(b). We know that (c, c i ) v is an essential variation, then by weak transitivity of essential variations (see Lemma 1.3.15), we obtain that (c, b) v is also an essential variation and so b belongs to the variation path. □ Now we are ready to prove Proposition 1.3.12, which states that pure-candidate intervals are pure intervals.

Proof of Proposition 1.3.12. Let [T 1 , T 2 ] be a pure-candidate interval and let A be the set of couples (a, c) such that (c, a) is a minimal essential variation of [T 1 , T 2 ]. By Proposition 1.3.23, we have that T 2 = T 1 + A. Furthermore, we know that A is subset of tree-ascents of T 1 by Proposition 1.3.18. This proves that [T 1 , T 2 ] is a pure interval. □ 1.3.4. Proof Part 2: Pure intervals are pure-candidate intervals.

Proposition 1.3.24. Let [T, T + A] be a pure interval, then it is a pure-candidate interval.

In order to prove this proposition we need to show that the variations and essential variations of any interval [T, T + A] satisfy Conditions (1) and (2) of Theorem 1.3.9. For this, it is usefull to characterize the variations and essential variations of a pure interval in terms of its ascent-paths, a notion that we now define. 1.3.4.1. Ascent paths. In the following, we adopt a notation for tree-ascents that is similar to the one we use for variations: we write (a, c) v a tree-ascent (a, c) where #(c, a) = v. Definition 1.3.25 (Ascent paths). Let [T, T + A] be a pure interval and c > a with # T (c, a) = v. We say that there is an ascent

-path c > c 1 > • • • > c k ≥ a if (i) (c 1 , c) v ∈ A; (ii) (c i , c i-1 ) 0 ∈ A for all 1 < i ≤ k; (iii) either c k = a or a is a middle descendant of c k .
You can check on Examples 1.3.20 and 1.3.21 that all variation paths are actually ascent paths. We are indeed going to prove that they are the same.

Remark 1.3.26. As we have a series of tree-ascents, some properties of the ascent-paths are immediate (i) a is a descendant of c in T ; (ii) for all i, c > c 1 > . . . c i is also an ascent-path, in particular c i is a descendant of c with # T (c, c i ) = v; (iii) for all i < j, c i > • • • > c j is also an ascent-path, in particular c j is a descendant of c i with # T (c i , c j ) = 0; (iv) for all i, c i > • • • > c k ≥ a is also an ascent-path, in particular a is a descendant of c i with # T (c i , a) = 0. There is an ascent path between 10 > 9 > 4 > 1 using the tree-ascents (1, 4) 0 , (4, 9) 0 , and (9, 10) 2 . We look at all b with 10 > b > 1 and # T1 (10, b) = 2.

• 4 and 9 belong to the ascent-path and correspond to Case (i);

• 2, 3 et 6 are middle descendants of either 4 or 9, they correspond to Case (ii);

• 7 corresponds to Case (iii) as we have # T1 (7, 1) = 1 = s(7). We choose the path so that k is minimal and we prove that this is an ascent-path.

Lemma 1.3.29. If c > c 1 • • • > c k ≥ a is an ascent path in a pure interval [T, T + A], with # T (c, a) = v, then (
In the following, we suppose that k ≥ 1 as otherwise, (a, c) is a tree-ascent of A and there is nothing to prove.

Let us look first at (c, c 1 ). Suppose that we have # T (c, c 1 ) = v + 1 and look at the next step, (c 1 , c 2 ) (this always exists but sometimes c 2 = a).

If # T (c 1 , c 2 ) > 0, then # T (c, c 2 ) ≥ v + 1 and c > c 2 > • • • > a is a shorter transitivity path. This implies that # T (c 1 , c 2 ) = 0. As # S (c 1 , c 2 ) > 0, it means that (c 2 , c 1 ) is a tree-ascent of A. By Condition (i) of Proposition 1.1.8, we obtain # T (c, c 2 ) = # T (c, c 1 ) = v + 1 and again c > c 2 > • • • ≥ c k is a shorter transitivity path. This means that # T (c, c 1 ) = v and that (c 1 , c) ∈ A.
A similar reasoning can be made for again,c i could be skipped in the transitivity path. The only case left is (c k , a). We know that # S (c k , a) > 0. If # T (c k , a) = 0, this means that (a, c k ) 0 is a tree-ascent of A and c > c

(c i-1 , c i ) for all 1 < i ≤ k. We have c i-1 > c i > c i+1 . If # T (c i-1 , c i ) > 0, then # T (c i , c i+1 ) = 0 otherwise one can build a shorter transitivity path skipping c i . Then # T (c i-1 , c i ) > 0 implies that (c i+1 , c i ) is a tree-ascent of A and # T (c i-1 , c i ) = # T (c i-1 , c i ) = 0 otherwise,
1 > • • • > c k+1 = a is an ascent-path. If # T (c k , a) > 0, as (c k , c k-1
) is a tree-ascent, the strict right child of c k is empty, i.e. a is a middle child of c k .

We have proved that having a variation (c, a) implies to have an ascent-path between c and a, in particular, a has to be a descendant of c. There is left to prove that this ascent-path is indeed the variation path of (c, a) v . Note that for all i, c > c 1 > • • • > c i is an ascent-path as well and by Lemma 1.3.29 we obtain that (c, c i ) v is an essential variation. For all i < k, we have # T (c i , a) = 0 < s(c i ) (there is a variation (c i+1 , c i ) so s(c i ) > 0) and so c i belongs to the variation path. Now either (c k , a) 0 is a variation or a is a middle child of c k , so in both cases, # T (c k , a) < s(c k ) and c k also belongs to the variation path. We need to prove that the variation path consists only of those elements. Let (c, b) v be an essential variation such that c > b > a and # T (b, a) < s(b). We use Lemma 1.3.27. Case (iii) is forbidden by hypothesis. Case (ii) is not possible because (c, b) v is an essential variation. The only possibility left is Case (i): b is one of the c i . □ Proposition 1.3.31. Variation paths and ascent paths of a pure interval are the same.

Proof. This is a direct consequence of Lemma 1.3.30. The variation path is unique for each variation by definition. The ascent path (if it exists) between two values c and a is also unique: indeed if a ̸ = c k , then the choice for c k is unique by Lemma 1.3.5 and then for 1 ≤ i ≤ k, there is unique tree-ascent (c i , * ).

Each ascent path corresponds to a variation and we have proved in Lemma 1.3.30 that the variation path of this variation is the ascent path. □

1.
-path c > c 1 > • • • > c k ≥ a.
It is an essential variation if and only if c k = a.

Using this, we are now ready to prove that pure intervals are pure-candidate intervals.

Proof of Proposition 1.3.24. Let T be an s-decreasing tree and A a subset of the tree-ascents of T . We will prove that the pure interval [T, T + A] is a pure-candidate interval, meaning that it satisfies Conditions 3.9 and 1.3.4. We now have all the ingredients to prove Theorems 1.3.9 and 1.3.4.

Proof of Theorem 1.3.9. A pure candidate interval is by definition an interval satisfying the two conditions in Theorem 1.3.9. So, we need to show that pure intervals and pure candidate intervals are the same. This was shown in Proposition 1.3.12 and Proposition 1.3.24. □

Proof of Theorem 1.3.4. Let [T, T + A] be a pure interval. By Proposition 1.3.24, it is also a pure candidate interval. So, we can apply Proposition 1.3.12 to deduce that (a, c) ∈ A if and only if (c, a) is a minimal essential variation. □ 1.3.5. Properties of variations of pure intervals. Now that we have proved that pure-candidate intervals and pure intervals are the same: all the properties of variations / essential variations that we have shown to prove either Proposition 1.3.12 or Proposition 1.3.24 are satisfied in pure intervals. In particular each variation is given by a certain variation path (from Definition 1.3.19), which is also an ascent-path (Definition 1.3.25). The specific properties of variations in pure intervals are crucial in our next section. We regroup some of them in this proposition for clarity. We call them the middle variation properties as they all concern the variation of (c, b) depending on properties of (c, a) where c > b > a. selected tree-ascents in the pure interval. In this case, the intersection of two pure intervals correspond to the geometric intersection of the cells. In Figure 15, we show two cells of dimension two intersecting in a cell of dimension one and two cells with an empty intersection.

First, we prove that the intersection of two intervals is always an interval. This is actually a general result on lattices and the proof is immediate.

Lemma 1.4.3. Let L be a lattice and

I 1 = [x 1 , y 1 ], I 2 = [x 2 , y 2 ] two intervals of L. Then, I 1 ∩ I 2 ̸ = ∅ if and only if x 1 ∨ x 2 ≤ y 1 ∧ y 2 ,
and in this case we have

I 1 ∩ I 2 = [x 1 ∨ x 2 , y 1 ∧ y 2 ].
Proof. Suppose that I 1 ∩ I 2 ̸ = ∅, then there is x ∈ I 1 ∩ I 2 . We have x 1 ≤ x and x 2 ≤ x, which implies

x 1 ∨ x 2 ≤ x. Similarly, x ≤ y 1 ∧ y 2 . We obtain x 1 ∨ x 2 ≤ x ≤ y 1 ∧ y 2 , i.e., I 1 ∩ I 2 ⊆ [x 1 ∨ x 2 , y 1 ∧ y 2 ]. Now suppose x 1 ∨ x 2 ≤ y 1 ∧ y 2 and take x ∈ [x 1 ∨ x 2 , y 1 ∧ y 2 ]
. By definition, we have

x 1 ≤ x 1 ∨ x 2 ≤ x ≤ y 1 ∧ y 2 ≤ y 1 , so x ∈ I 1 . Similarly, x ∈ I 2 . This gives I 1 ∩ I 2 ̸ = ∅ and [x 1 ∨ x 2 , y 1 ∧ y 2 ] ⊆ I 1 ∩ I 2 . □
So we know that by intersecting two pure intervals, we always obtain an interval. We will prove that the variations of the intersection satisfy the conditions of Theorem 1.3.9. For this we need to understand what are the variations and essential variations of the intersection. 1.4.2. Variations of the intersection. As a first step, we prove the following lemma. We now have b > b 2 > a a transitivity path in S which does not exist either in T nor T ′ . Without loss of generality and using the +1 property, we can assume that

= v + 1. Let S = inv(T ) ∪ inv(T ′ ) such that inv(X) = S tc . There is a transitivity path in S b = b 1 > • • • > b k = a. with # S (b 1 , b 2 ) = v + 1 and # S (b i , b i+1 ) > 0. We choose the transitivity path such that k is minimal. Note that k > 2 because # T (b, a) = # T ′ (b, a) = v. Suppose that b 3 ̸ = a. If either # T (b 1 , b 3 ) = v + 1 or # T ′ (b 1 , b 3 ) = v + 1,
# T (b, b 2 ) = v + 1 (7) # T (b 2 , a) = 0 (8) # T ′ (b, b 2 ) = v (9) # T ′ (b 2 , a) = 1. (10) We have X ∈ [T, T + A] and # X (b 2 , a) = 1 > # T (b 2 ,
= (T + A) ∧ (T ′ + A ′ ), then (11) Var([X, Y ]) = Var([T, T + A]) ∩ Var([T ′ , T ′ + A ′ ]).
Note that the intersection is taken considering variations with their values, i.e., (b, a

) v ∈ Var([T, T + A]) ∩ Var([T ′ , T ′ + A ′ ]) if and only if (b, a) v ∈ Var([T, T + A]) and (b, a) v ∈ Var([T ′ , T ′ + A ′ ]). Proof. Let b > a, be such that (b, a) v is a variation of both [T, T + A] and [T ′ , T ′ + A ′ ]. In particular, # T (b, a) = # T ′ (b, a) = v and # T +A (b, a) = # T ′ +A ′ (b, a) = v + 1.
Using intersection stability of Lemma 1.4.4, we obtain # X (b, a) = v. Now, let S be the multi-set of inversions obtained by increasing by one the cardinality of (b, a) in inv(T ). By definition, inv(T ) ⊆ inv(T + A). Besides, as the intersection is non-empty, □ Proposition 1.4.5 can be summarized in a sentence: the variations of the intersection are the intersections of the variations. Note that this is true only if the intersection is non-empty. Besides, this does not extend to essential variations. Indeed, in this case, the intersection of essential variations is only included in the set of essential variations of the intersection.

T ≼ T ′ +A ′ which means inv(T ) ⊆ inv(T ′ +A ′ ). We also have # T +A (b, a) = # T ′ +A ′ (b, a) = v + 1 = # S (
We present two examples also computed in our SageMath demo worksheet [START_REF] Pons | Sagemath code and demo for s-weak order and s-permutahedra[END_REF].

Example 1.4.6. Figure 15 shows two examples of intersection of pure intervals for s = (0, 2, 2). On the first one, the intersection is not empty. The variations of the two pure intervals are respectively

{(3, 2) 1 , (3, 1) 1 , (2, 1) 0 } and {(3, 2) 1 , (3, 1) 1 , (2, 1) 1 }. The variations of the intersection are {(3, 2) 1 , (3, 1) 1 }.
In this case, the intersection has only one essential variation, (3, 2) 1 which is the only essential variation found in both pure intervals.

The second intersection of Figure 15 is an empty one but we see that it does not imply that the intersection of the variations is empty. Indeed, in this case (3, 1) 1 is a variation in both pure intervals.

Example 1.4.7. Figure 16 shows an intersection of pure intervals of size 10. For clarity, we have written the pure intervals along with their maximal trees. You can check that the minimal tree of the intersection is the join of the two minimal trees and it is smaller than the meet of the two maximal trees. The variations of the intersection are {(9, 4) 0 , (9, 3) 0 , (9, 1) 0 , (10, 6) 2 , (10, 2) 2 , (6, 2) 1 }. This is indeed the intersection of the variations in both intervals. However, the intersection has three essential variations: {(9, 4) 0 , (10, 6) 2 , (6, 2) 1 }. We see that (9, 4) 0 and (6, 2) 1 are essential variations in both pure intervals (they are the only ones present in both) but (10, 6) 2 is not (it is an essential variation only in the second one). To prove that the essential variations satisfy the conditions of Theorem 1.3.9, we need to characterize the variations of the two intervals that give essential variations in the intersection. We will do this using the following compatibility notion. Example 1.4.10. Let us call T and T ′ respectively the two minimal trees of the pure intervals shown in Figure 16. The variation (10, 6) 2 is the only compatible variation which is not an essential variation in both T and T ′ : in T ′ , (10, 6) 2 is an essential variation so 6 is never a middle descendant of any b with 10 > b > 6. In T , 6 is a middle descendant of 9 and we check that # T ′ (9, 6) = 2 = s(9). It is indeed an essential variation of the intersection.

On the other hand, (9, 1) 0 is an essential variation of T and a variation in T ′ . In T ′ , 1 is a middle descendant of 3 and 4 but we have # T (3, 1) = 0 < s(3) and # T (4, 1) = 0 < s(4) so it is not a compatible variation. Indeed, we see that (9, 1) 0 is a variation of the intersection but not an essential variation.

) v varies in [T ′ , T ′ + A ′ ].
Suppose first that a is still a middle descendant of b in X. We know that #

X (c, a) = v. As a is a descendant of b, this implies that # X (c, b) = v. We know # T (c, b) ≤ # X (c, b). If # T (c, b) < v, as # T (c, a) = v this implies in particular that # T (b, a) = s(b) which is not possible as we have # X (b, a) < s(b), so # T (c, b) = v. As # T (b, a) < s(b), we can apply Property (1) of Proposition 1.3.33 and we get that (c, b) v is a variation of [T, T +A]. As (c, b) v is also a variation of [T ′ , T ′ +A ′ ], using Proposition 1.4.5, we obtain that (c, b) v is a variation of [X, Y ] and then (c, a) v is not an essential variation of [X, Y ].
This means that a is no longer a middle descendant of b in X. As the cardinality of (b, a) can only increase, this means # X (b, a) = s(b). By the +1 property (Lemma

1.3.8), # T ′ (b, a) = s(b) -1 and s(b) -1 ≤ # T (b, a) ≤ s(b). But if # T (b, a) = s(b) -1, the intersection stability (Lemma 1.4.4) tells us that # X (b, a) = s(b) -1 which is not possible. We have proved that if a is a middle descendant of b in T ′ , then # T (b, a) = s(b). Symmetrically, we prove that if a is a middle descendant of b in T , then # T ′ (b, a) = s(b). □ Remark 1.4.
[X, Y ]. If (c, a) v is an essential variation of [X, Y ], then (c, a) v is an essential variation of either [T, T + A] or [T ′ , T ′ + A ′ ].
Proof. We need to prove that if (c, a) v is compatible, then it is an essential variation for one of the intervals. Suppose that it is not. We have b and b ′ such that a is a middle descendant of b in T and b

′ in T ′ . The compatibility implies that # T (b ′ , a) = s(b ′ ) and # T ′ (b, a) = s(b) so in particular b ̸ = b ′ .
Beside, we can chose b (resp. b ′ ) to be minimal, i.e., a is not a middle descendant in T (resp. T ′ ) of any node of value smaller than b (resp. b ′ ). Without loss of generality, we suppose b ′ < b. In T ′ , we have In terms of the tree this means that the node labels in T c i are smaller than all the labels in T c j for i < j. The multi set of inversions of an s-Tamari tree is called an s-Tamari inversion set.

# T ′ (b, a) = s(b) and a is a descendant of b ′ so # T ′ (b, b ′ ) = s(b). Using Remark 1.4.11, # T (b, a) = s(b)-1. Now the compatibility gives us # T (b ′ , a) = s(b ′ ) which implies that # T (b, b ′ ) ≤ # T (b, a).
The s-Tamari poset is the restriction of the s-weak order to the set of s-Tamari trees.

The s-Tamari trees play the role of 231-avoiding permutations of the s-weak order, and the number of s-Tamari trees may be regarded as the s-Catalan number.

An example of the s-Tamari lattice for s = (0, 2, 2) is illustrated on the left of Figure 17. The s-Catalan number in this case is 12 (a Fuss-Catalan number), which counts the number of elements of the lattice.

Theorem 2.1.2 ([CP22, Theorem 2.2]). The s-Tamari poset is a sublattice of the s-week order. In particular, it is a lattice.

Theorem 2.1.3 ([CP22, Theorem 2.20]). If s contains no zeros (except at the first position which is irrelevant), then the s-Tamari lattice is a quotient lattice of the s-weak order.

The cover relations of the s-Tamari lattice can be described as certain rotations on s-Tamari trees.

Definition 2.1.4. Let T be an s-Tamari tree of some weak composition s. We say that (a, c) with a < c is a Tamari-ascent of T if a is a non-right child of c. It was shown in [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF]Lemma 2.23] that if (a, c) is a Tamari-ascent of T then by increasing the cardinality of (c, a) by one in inv(T ) and taking the transitive closure, we obtain an s-Tamari inversion set. This operation is called an s-Tamari rotation of T .

Theorem 2.1.5 ([CP22, Theorem 2.25]). The cover relations of the s-Tamari lattice are in correspondence with s-Tamari rotations.

2.1.2. The ν-Tamari lattice. The ν-Tamari lattice is another lattice structure introduced in [PRV17], which can be defined in terms of a family of combinatorial object called ν-trees [START_REF] Ceballos | The ν-Tamari lattice via ν-trees, ν-bracket vectors, and subword complexes[END_REF].

Let ν be a lattice path on the plane consisting of a finite number of north and east unit steps, which are represented by the letters N and E. We denote by A ν the set of lattice points weakly above ν inside the smallest rectangle containing ν. We say that two points p, q ∈ A ν are ν-incompatible if and only if p is southwest or northeast to q and the south-east corner of the smallest rectangle containing p and q is weakly above ν. Otherwise, we say that p and q are ν-compatible. Definition 2.1.6. A ν-tree is a maximal collection of pairwise ν-compatible elements in A ν .

Although ν-trees are just sets of lattice points above ν, they can be regarded as planar binary trees in the classical sense, by connecting consecutive nodes (or lattice points) in the same row or column [START_REF] Ceballos | The ν-Tamari lattice via ν-trees, ν-bracket vectors, and subword complexes[END_REF]. The result is a planar binary tree with a root a the top left corner of A ν .

Let T be a ν-tree and p, r ∈ T be two elements which do not lie in the same row or same column. We denote by p□r the smallest rectangle containing p and r, and write p⌞r (resp. p⌝r) for the lower left corner (resp. upper right corner) of p□r.

Let p, q, r ∈ T be such that q = p⌞r and no other elements in T besides p, q, r lie in p□r. The node q is called a ν-ascent of T , and the ν-tree rotation of T at q is defined as the set T ′ = T \ {q}) ∪ {q ′ }, where q ′ = p⌝r. As shown in [CPS20, Lemma 2.10], the the rotation of a ν-tree is also a ν-tree.

Definition 2.1.7. The ν-Tamari lattice is the poset on ν-trees whose cover relations are given by ν-tree rotations.

An example of this lattice for ν = N EEN EEN is shown on the right of Figure 17. 2.1.3. The s-Tamari lattice and the ν-Tamari lattice are isomorphic. Let s = (s(1), . . . , s(n)) be a weak composition and ν(s) be the lattice path ν(s) := N E s (1) . . . N E s(n) . We denote by ←s the reversed sequence (s(n), . . . , s(2), s(1)). In [START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF], we showed that the s-Tamari lattice and the ν( ←s )-Tamari lattice are isomorphic. The bijection relating these two lattices is given as follows.

Let T be an s-Tamari tree. We use the reverse preorder transversal to label the nodes of T with the numbers 0, 1, . . . , n, such that a node x has label i if the number of internal nodes traversed striktly before x is equal to i. We denote by φ(T ) the unique ν-tree containing as many nodes at height i as there are nodes in T with label i. Such ν-tree can be uniquely constructed using the right flushing algorithm

The s-associahedron

In this section we extend the s-Tamari lattice to a full polyhedral complex that we call the sassociahedron, and show that it coincides with the ν-associahedron introduced by Ceballos, Padrol, and Sarmiento in [START_REF] Ceballos | Geometry of ν-Tamari lattices in types A and B[END_REF].

2.2.1. The s-associahedron. Let T be an s-Tamari tree and A be a (possibly empty) subset of Tamari ascents of T . Similarly as in the case of the s-weak order, we denote by T + A the s-Tamari tree whose inversion set is obtained by increasing all cardinality # T (c, a) where (a, c) ∈ A by one and then taking the transitive closure. Definition 2.2.1. Let T 1 ≼ T 2 be two s-Tamari trees for a given weak composition s. We say that the interval [T 1 , T 2 ] is a pure s-Tamari interval if T 2 = T 1 + A with A a subset of Tamari-ascents of T 1 .

Examples of pure s-Tamari intervals are shown in Figures 18 and19. The following lemma is the analog of Lemma 1.2.2 for the s-Tamari lattice.

Lemma 2.2.2. Let T 1 and T 2 be two s-Tamari trees such that T 2 = T 1 + A with A a subset of Tamariascents of T 1 . Then T 2 can be obtained as the join T 2 = a∈A (T 1 + a) over all s-Tamari trees T 1 + a obtained from T 1 by rotating a Tamari-ascent a ∈ A.

Proof. The proof is similar to the one of Lemma 1.2.2. Indeed even though the definition of tree-ascents differs from the definition of Tamari-ascents, the rotation is the same: increase the cardinality of the Proof. The proof is exactly the same as the proof of Proposition 1.2.4. Let

T (1 + t) tasc(T ) = f 0 + f 1 t + f 2 t 2 + . . . .
where the sum runs over all s-Tamari trees T . We need to show that f k counts the number of kdimensional faces of Perm(s). This follows from the fact that every subset of ascents A of T , of size k, contributes a t k to the term (1 + t) tasc (T ) . □

The constant term f 0 of this polynomial is the number of elements of the s-weak order, which is the s-Catalan number. Moreover, the coefficients of t k in the polynomial T t tasc(T ) may be regarded as s-generalizations of the Narayana numbers. The s-Narayana number Nar s (k) counts the number of s-Tamari trees with exactly k Tamari ascents. They have been already considered in [CPS19, Section 4] and [START_REF] Ceballos | Signature Catalan combinatorics[END_REF] in this general set up, and in [START_REF] Armstrong | Rational associahedra and noncrossing partitions[END_REF] for the special case of signatures arising in rational Catalan combinatorics. 2.2.2. The ν-associahedron. In [START_REF] Ceballos | Geometry of ν-Tamari lattices in types A and B[END_REF], Ceballos, Padrol and Sarmiento proved that the Hasse diagram of the ν-Tamari lattice can be realized as the edge graph of a polyhedral complex induced by an arrangement of tropical hyperplanes. They named this polyhedral complex the ν-associahedron and gave a complete characterization of its faces in terms of certain combinatorial objects called "covering (I, J)forrests", see [CPS19, Definition 5.1 and Theorem 5.2]. We present here an equivalent description of their ν-associahedron phrased in terms of ν-trees, which is more convenient for our purposes.

Let ν be a lattice path consisting of north an east unit steps. Recall that a ν-tree is a maximal ν-compatible collection of elements in A ν (lattice points weakly above ν), and that the ν-Tamari lattice is the lattice of ν-trees whose covering relation is given by ν-Tamari rotations. This lattice was extended to a full simplicial complex in [START_REF] Ceballos | Geometry of ν-Tamari lattices in types A and B[END_REF] called the ν-Tamari complex. Its faces, which we call ν-faces, are ν-compatible collections of elements in A ν ordered by inclusion [START_REF] Ceballos | The ν-Tamari lattice via ν-trees, ν-bracket vectors, and subword complexes[END_REF]. A ν-face F is said to be covering if it contains the root (top left corner in A ν ) and at least one point in each row and each column. The covering ν-faces are exactly the interior faces of the ν-Tamari complex, see [CPS19, Lemma 4.3].

Definition 2.2.5. The ν-associahedron Asso(ν) is the polyhedral complex of interior faces of the ν-Tamari complex, ordered by reversed inclusion. Equivalently, Asso(ν) is the polyhedral complex of covering ν-faces, ordered by reversed inclusion. The dimension of a covering ν-face F is ℓ(ν) + 1 -|F |, where ℓ(ν) is the length of ν. In particular,

(1) the vertices of Asso(ν) are ν-trees, and

(2) two ν-trees are connected by an edge if and only if they are related by a ν-Tamari rotation.

An example of the ν-associahedron for ν = N EEN EEN is shown in Figure 20. Note that in this case, it is isomorphic to the s-associahedron for s = (0, 2, 2) illustrated in Figure 3. Before matching the definitions of s-associahedra and ν-associahedra we need the following results.

Lemma 2.2.6. Covering ν-faces F are in bijection with pairs (T , A) such that T is a ν-tree and A is a (possibly empty) subset of ν-ascents of T . The bijection is determined by F = T ∖ A and dim(F) = |A|.

Proof. If T is a ν-tree and a is a ν-ascent of T , then the ν-face T ∖ {a} is contained in two facets (T and the rotation of T at a). Therefore, T ∖ {a} is an interior face of the ν-Tamari complex. Similarly, if A is a subset of ν-ascents of T , the ν-face T ∖ A is also an interior face. Thus, F = T ∖ A is a covering ν-face. By definition, its dimension is equal to dim

(F) = ℓ(ν) + 1 -|T ∖ A| = ℓ(ν) + 1 -|T | + |A| = |A|.
It remains to show that every covering ν-face F can be written uniquely as F = T ∖ A for some ν-tree T and a subset A of ν-ascents of T . We prove this using the connection between ν-Tamari lattices and subword complexes presented in [START_REF] Ceballos | The ν-Tamari lattice via ν-trees, ν-bracket vectors, and subword complexes[END_REF].

Let F be a covering ν-face. By [CPS20, Theorem 5.5], the ν-Tamari lattice is the increasing flip graph of a suitably chosen subword complex SC(Q ν , π ν ). It is not required to understand subword complexes in this proof, but to know that under this correspondence, ν-trees correspond to facets of the subword complex and ν-rotations to increasing flips. The link of a face in a subword complex is also a subword complex itself, see e.g. [START_REF] Knutson | Subword complexes in Coxeter groups[END_REF]. Therefore, the restriction of the ν-Tamari lattice to the set of ν-trees containing F is the increasing flip graph of another suitable subword complex SC(Q F ,ν, , π ν ). Furthermore, it is known that the increasing flip graph of a subword complex has a unique source and a unique sink [PS13, Proposition 4.8]. In our language, this means that there is a unique ν-tree T min F (resp. T max F ) containing F such that every "flippable" element of T min F (resp. T max F ) that is not in F is "increasingly flippable" (resp. "decreasingly flippable"), that is a ν-ascent (resp. "ν-descent"). Moreover, since F is an interior face, then every element of

A = T min F ∖ F is flippable. Thus, A is a subset of ν-ascents of T min F . Since F = T min F ∖ A, this finishes our proof. □
For a ∈ A we denote by T a the ν-tree obtained from T by applying a ν-Tamari rotation at the ν-ascent a, and by T + A the join of the set {T a : a ∈ A}. The interval [T , T + A] of the ν-Tamari lattice is called a pure ν-Tamari interval. An example is illustrated in Figure 21.

As we have seen in Section 1.3, the classification of pure intervals in the s-weak order is rather involved and technical, and one might expect a similar situation to happen for the classification of pure s-Tamari intervals in the s-Tamari lattice. However, if ν = ν( ←s ), we know by Proposition 2.1.8 and Lemma 2.2.2 that pure s-Tamari intervals are mapped to pure ν-Tamari intervals under the bijection φ from Section 2.1.3. For instance, the pure s-Tamari interval in Figure 19 Proof. Using the same subword complex techniques from the proof of Lemma 2.2.6, the set of ν-trees containing F is in correspondence with the set of facets of the subword complex SC(Q F ,ν, , π ν ), and ν-rotations correspond to increasing flips. As argued above, this set of facets has a unique minimal element T min 13) is a product of classical Tamari lattices. Its minimal element is T , and it contains the ν-Tamari trees T +a for a ∈ A (because we rotate an element a that is not in F). Since the dimension dim(F) = |A|, the interval in Equation ( 13) contains all the covers of the minimal element. Furthermore, the join of the covers of the minimal element in a classical Tamari lattice is the top element of the lattice, and this property is preserved by taking products of Tamari lattices. Therefore, T max F is the join of the set {T a : a ∈ A}, which is equal to T + A by definition. □ For the forward direction, assume that F ⊉ F ′ . We aim to show that [T , T

+ A] ⊈ [T ′ , T ′ + A ′ ]. Let f ′ ∈ F ′ ∖ F,
and T be a ν-tree containing F. We consider two cases.

Case 1: f ′ / ∈ T . In this case, T does not contain F ′ , and so

T ∈ [T , T + A] but T / ∈ [T ′ , T ′ + A ′ ] as we wanted to show. Case 2: f ′ ∈ T . Since F ⊆ T is an interior face and f ′ / ∈ F, then f ′ is flippable in T . Flipping it, we obtain a new ν-tree T * = T ∖ {f ′ } ∪ {f * }. This new tree satisfies F ⊆ T * but F ′ ⊈ T * . Thus, T * ∈ [T , T + A] but T * / ∈ [T ′ , T ′ + A ′
] as we wanted. □ 2.2.3. The s-associahedron and the ν-associahedron are isomorphic. The bijection φ between s-Tamari trees and ν( ←s )-trees described in Section 2.1.3 extends naturally to a bijection φ between the faces of the s-associahedron and the faces of the ν( ←s )-associahedron. For each pair (T, A) of an s-Tamari tree T and a subset A of Tamari-ascents of T , we can associate a pair (T , A) of a ν-tree T = φ(T ) and a subsets A of ν-assents of T corresponding to A. We denote by φ the map that sends the pure s-Tamari interval [T, T + A] to the covering ν-face F = T ∖ A.

Theorem 2.2.9. The map φ is an isomorphism between Asso(s) and Asso(ν( ←s )).

Proof. By Lemma 2.2.6, the map φ is a bijection between pure s-Tamari intervals and covering ν( ←s )faces. So, φ is a bijection between the faces of the s-associahedron and the faces of the ν( ←s )-associahedron. We need to show that this map preserves their order relation. We proved in Theorem 1.2.6 that the s-permutahedron is what we call a combinatorial complex, i.e. a collection of cells or faces (pure intervals) satisfying two properties: (1) it is closed under taking faces and (2) any two faces intersect properly. These two conditions are necessary conditions for being a polytopal complex. In order to be a polytopal complex, we need the further property that all the cells of the complex can be geometrically realized as (convex) polytopes. This condition is stated in the following conjecture.

Conjecture 3.1.1 (Polytopality of pure intervals). For any weak composition s, the pure intervals of the s-weak order are polytopal in the following sense:

(1) The inclusion poset of pure intervals contained in a pure interval [T, T + A] is the face lattice of some polytope P of dimension |A|.

(2) The Hasse diagram of the restriction of the s-weak order to [T, T + A] is the edge graph of P .

Item (2) in this conjecture is not really necessary because it follows from Item (1). However, we include it here because it is a nice property that we would like to highlight.

We have strong reasons to believe that this conjecture is true. On one side, it has been recently proven in the case where s does not contain any zeros [GDMP + 23], as we explain in Section 3.4. On the other side, we have an empirical polytopal construction of each pure interval as a generalized permutahedron which we call an ascentope. On Figure 11, you see on the right the ascentope corresponding to the pure interval. The code to compute the ascentopes is available on [START_REF] Pons | Sagemath code and demo for s-weak order and s-permutahedra[END_REF]. Computational experiments show that our ascentopes have the right properties with examples of dimensions up to 9. We plan to study these objects in future work.

Our next conjecture is even more general and was also proven when s does not contain any zeros [GDMP + 23], see Section 3.4. All of our figures seem to indicate that the Hasse diagram of the s-weak order seems to be realizable as the edge graph of a polytopal subdivision of a polytope, whose faces are in correspondence with pure intervals. This polytope should be combinatorially isomorphic to the zonotope

(14) Z(s) = 1≤i<j≤n s(j)∆ ij ,
where ∆ ij = conv{e i , e j } ⊂ R n . In particular, if s has no zeros (except possibly for s(1)) then Z(s) is combinatorially an (n -1)-dimensional permutahedron.

Conjecture 3.1.2 (Polytopal subdivision realization). For any weak composition s, the s-permutahedron can be geometrically realized as a polytopal subdivision of a polytope which is combinatorially isomorphic to Z(s). This means,

(1) The inclusion poset of pure intervals of the s-weak order is the face poset of the subdivision.

(2) The Hasse diagram of the s-weak order is the edge graph of the subdivision.

Again, Item (1) in this conjecture follows from Item (2), but we include it here because it is a nice property that we would like to highlight. As we will discuss in Section 3.3, this conjecture holds in full generality in dimensions 2 and 3. Examples of geometric realizations of s-permutahedra are illustrated s = (0, 0, 2) s = (0, 1, 2) s = (0, 2, 2) s = (0, 4, 3)

Figure 22. Some geometric realizations of s-permutahedra in dimension 2. s = (0, 0, 0, 2) s = (0, 0, 1, 2), s = (0, 1, 0, 2) s = (0, 1, 1, 2) s = (0, 2, 2, 2), s = (0, 2, 3, 2) s = (0, 3, 2, 3) s = (0, 3, 3, 3) s = (0, 5, 5, 5)

Figure 23. Some geometric realizations of s-permutahedra in dimension 3.

in Figures 22 and23. You can find 3-dimensional animations of these polyhedral subdivisions and more in this webpage [START_REF] Pons | Many example of 3d s-permutahedra[END_REF]. Besides, all examples in dimensions 2 and 3 can be computed with SageMath as shown in our demo worksheet [START_REF] Pons | Sagemath code and demo for s-weak order and s-permutahedra[END_REF].

One remarkable property of the classical permutahedron is that the classical associahedron can be obtained from it by removing certain facets [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF][START_REF] Hohlweg | Permutahedra and generalized associahedra[END_REF]. We believe that if s contains no zeros, this property also holds for the s-permutahedron and the s-assoociahedron.

Conjecture 3.1.3 (Removing facets of the s-permutahedron). If s has no zeros (except for s(1)), there exists a geometric realization of the s-permutahedron such that the s-associahedron can be obtained from it by removing certain facets.

Examples of s-associahedra obtained from s-permutahedra by removing certain facets are illustrated in Figures 24 and4 . The s-permutahedron and s-associahedron for s = (0, 0, 2). In this case, the s-associahedron is not convex because s(2) = 0.

We remark that if s contains zeros other than s(1), then Asso(s) is not convex, see an example in Figure 25. This follows from the analog result for ν-associahedra in [CPS19, Cor. 5.13], which states that the ν-associahedron is convex if and only if ν does not have two non-initial consecutive north steps. In such a case, the ν-associahedron is a polytopal subdivision of a classical associahedron [CPS19, Cor. 5.13]. Thus, Conjecture 3.1.3 may be thought as a generalization of Hohlweg and Lange's result in [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF].

Generalizations for finite Coxeter groups

Another natural related question is whether there are generalizations of our constructions for other Coxeter groups.

Question 3.2.1. Is there a natural definition of the s-permutahedron and the s-associahedron for other finite Coxeter groups? Figure 26 shows a tantalizing partial answer to this question in type B 2 . The left hand side of this figure shows what we believe could be Fuss-Catalan generalizations of the type B 2 permutahedron (subdivided octagons), while the right hand side shows the corresponding Fuss-Catalan type B 2 associahedra (subdivided cyclohedra) obtained by removing some facets. The number of vertices of these subdivided cyclohedra are 6, 15, 28, 45, 66, . . . , which are indeed the m-Catalan numbers of type B 2 (also called hexagonal numbers in [SI20, Sequence A000384]). This can be checked from the general formula of the Coxeter m-Catalan numbers, which is given by n i=1 e i + mh + 1 e i + 1 , (15) In forthcoming work, we will introduce and investigate the s-braid arrangement, an arrangement of hyperplanes which induces a cell decomposition that is dual to the s-permutahedron. This point of view will provide further insights on potential generalizations in the context of finite Coxeter groups. An example is illustrated on the right of Figure 27.

Geometric realizations in dimensions 2 and 3

In this section, we provide an explicit construction that shows that Conjectures 3.1.1, 3.1.2 and 3.1.3 hold in dimensions 2 and 3. There is a natural way of assigning coordinates to each s-decreasing tree.

Let e ij := e i -e j for i < j, where e 1 , . . . , e n ∈ R n are the standard basis vectors in R n . Let s = (s(1), s(2), . . . , s(n)) be a weak composition, T be an s-decreasing tree and A be a subset of tree-ascents of T . We define v T = i<j # T (j, i)e ij and F (T,A) = conv{v T ′ : T ′ ∈ [T, T + A]}.

For n = 3 and s(3) ̸ = 0, this gives a 2-dimensional realization of the s-permutahedron in the subspace {(x 1 , x 2 , x 3 ) ∈ R 3 : x 1 + x 2 + x 3 = 0} ⊂ R 3 , see Figure 22. This realization "cuts" a polygon (a hexagon if s 2 ̸ = 0 or a quadrilateral if s(2) = 0) into smaller polygons. Each polygon is convex and corresponds to one facet of the s-permutahedron.

One would hope that this construction directly extends to higher dimensions, but it is not the case. For n ≥ 4, the convex hull of all v T 's is the zonotope Z(s) from ( 14), which is still cut into identifiable pieces; however, those pieces do not form convex polytopes. We were able to fix this realization in dimension 3 (n = 4 and s(4) ̸ = 0), using a procedure illustrated in Figure 28. The first image shows the direct realization obtained by v T : we notice some bent edges and can identify what we call a "broken pattern" in trees related to those edges. The solution is to push the selected trees into a given direction by a parameter given by a broken pattern itself. In certain compositions s, this push leads to a "collision" (see middle of Figure 28) which again forces us to push certain trees further away. The process can be explicitly described for dimension 3. The new coordinates are given by v T = i<j (3 # T (j, i)+f T (j, i))e ij where f T (j, i) = 0 for j ̸ = 3 and See Figure 4 for examples, the demo webpage [START_REF] Pons | Many example of 3d s-permutahedra[END_REF], or the SageMath demo worksheet [START_REF] Pons | Sagemath code and demo for s-weak order and s-permutahedra[END_REF]. We conjecture that such a construction also exists for higher dimensions. Once we have a geometric realization of the s-permutahedron, we are able to identify what we call Tamari-valid faces and construct a realization of the s-associahedron by removing faces of the spermutahedron. This works for both our 2D and 3D realizations, and is an analogue of a construction in [START_REF] Hohlweg | Realizations of the associahedron and cyclohedron[END_REF] giving rise to Loday's realization of the associahedron. The process is illustrated in Figure 24 in 2D, see Figure 4 for 3D examples.

f T (3, i) =      0 if # T (3, i) = 0,

Realization via flow polytopes

As mentioned before, the conjectures of this paper were announced in an extended abstract of our work back in 2019 [START_REF] Ceballos | The s-weak order and s-permutahedra[END_REF], and this is the first time where we include all the details of our constructions. The construction in [GDMP + 23] is a beautiful work based on triangulations of flow polytopes. For each composition s (with no zeros), the authors introduce a graph called the s-oruga graph, and use a framing of it to triangulate its corresponding flow polytope. They show that the dual of the poset of interior faces of the resulting triangulation is isomorphic to the face poset of the s-permutahedron. Finally, they use the Cayley trick and techniques from tropical geometry to obtain the desired geometric realization.

The presentation in [GDMP + 23] has further important implications. One of them is a simpler and more convenient description of pure intervals of the s-weak order, when s has no zeros. They can be described as certain subsets of coherent routes of the s-oruga graph corresponding to interior faces of the triangulation. This has the advantage that intersecting two pure intervals corresponds to just intersecting the associated sets of coherent routes. This intersection is literarily an intersection as sets, and therefore, it is very simple to compute. Exactly the same situation happens for the ν-associahedron in Section 2.2.2, which makes the proofs much simpler in this case.

In contrast, the combinatorial description of the intersection of two pure intervals that we present in Section 1.4.1 uses the characterization of pure intervals in Section 1.3, which is rather involved. However, we believe that our deep combinatorial exploration of their combinatorial properties will be very useful. Combining this with the geometric/combinatorial techniques from [GDMP + 23] provides a powerful toolkit for future explorations.

Introduction Part 1 .

 1 The s-permutahedron 1.1. The s-weak order (background) 1.1.1. Lattice definition through s-decreasing trees and tree-inversions 1.1.2. Tree-ascents and cover relations 1.2. The s-permutahedron 1.2.1. Pure intervals of the s-weak order 1.2.2. The combinatorial complex of pure intervals 1.3. Characterization of pure intervals 1.3.1. Variations and essential variations of an interval 1.3.2. The Characterization Theorem 1.3.3. Proof Part 1: Pure-candidate intervals are pure intervals 1.3.4. Proof Part 2: Pure intervals are pure-candidate intervals 1.3.5. Properties of variations of pure intervals 1.4. Intersection of pure intervals 1.4.1. The Intersection Theorem 1.4.2. Variations of the intersection 1.4.3. Essential variations of the intersection 1.4.4. Proof of the Intersection Theorem

Figure 3 .

 3 Figure 3. The s-Tamari lattice as the edge graph of the s-associahedron for s = (0, 2, 2)

Figure 5 .

 5 Figure5. an s-decreasing tree and its tree-inversions (Figure4of[START_REF] Ceballos | The s-weak order and s-permutahedra I: combinatorics and lattice structure[END_REF])

Figure 6 .

 6 Figure 6. Illustration of the transitivity and planarity conditions on s-tree inversion sets. (Figure 5 of [CP22])

( 1 )

 1 # I∪J (c, a) = max (# I (c, a), # J (c, a)) for all a < c. Definition 1.1.4 (Definition 1.4 of [CP22]). Let I be a multi-set of inversions. A transitivity path between two values c > a is a list of k ≥ 2 values c = b 1 > b 2 > • • • > b k = a such that # I (b i , b i+1 ) > 0 for all 1 ≤ i < k. Note that if # I (c, a) > 0, then (c, a) itself is a transitivity path. We write I tc for the transitive closure of I, which is defined as follows. For all a < c, # I tc (c, a) = v with v the maximal value of # I (b 1 , b 2 ) for c = b 1 > • • • > b k = a a transitivity path between c and a. Definition 1.1.5 ([CP22, Defintion 1.9]

Figure 8 .

 8 Figure 8. Schematic illustration of two s-trees containing an ascent (a, c). (Figure 8 from [CP22])

Proposition 1 .

 1 1.8 (Proposition 1.27 of [CP22]). A couple (a, c) is a tree-ascent if and only if it satisfies the following statements (i) for all d such that c < d ≤ n, we have #(d, c) = #(d, a); (ii) #(c, a) < s(c); (iii) for all b such that a < b < c, then #(c, b) = #(c, a) implies that #(b, a) = s(b);

Figure 9 .

 9 Figure9. Example of a pure interval. On the left, the minimal tree with colored treeascents and on the right the corresponding interval.

Figure 10 .

 10 Figure10. Example of a pure interval. On the left, the minimal tree of the interval with selected tress-ascents and on the right, the maximal tree of the corresponding interval.

Figure 11 .

 11 Figure 11. Example of a pure interval. the minimal tree of the interval with selected tress-ascents and on the right, the interval drawn as the skeleton of a 3d polytope.

Figure 12 .Figure 13 .

 1213 Figure 12. Bijective illustration of Case (1) of the recursive f -polynomial computation.

  ) varies and a belongs to a middle child of b ′ . This means that there is no b ′ > b such that (c, b ′ ) varies and b belongs to a middle child of b ′ (because a is a descendant of b). Therefore, (c, b) is an essential variation. Now, let us suppose we have c > b 1 > b 2 > a such that (c, b 1 ) v is an essential variation and a belongs to a middle child of b 1 . If a is a descendant of b 2 , then b 2 belongs to the same middle child of b 1 as a.

Lemma 1 .

 1 3.6 (Transitivity). Let [T 1 , T 2 ] be an interval. Suppose that we have c > b > a with (c, b) and (b, a) variations. Then (c, a) also varies. Proof. This is immediate. Indeed, we have by hypothesis # T1 (b, a) < s(b), we obtain by planarity (Definition 1.1.1) that # T1 (c, a) ≤ # T1 (c, b). As both (c, b) and (b, a) vary, we obtain # T2 (c, b) > # T1 (c, b) and # T2 (b, a) > # T1 (b, a) ≥ 0 which gives # T2 (c, a) ≥ # T2 (c, b) > # T1 (c, b) ≥ # T1 (c, a) by transitivity. □ Definition 1.3.7 (+1-interval). An interval [T 1 , T 2 ] is said to be a +1-interval if all variations have amplitude one, i.e., for all a < b we have (5) # T1 (b, a) ≤ # T2 (b, a) ≤ # T1 (b, a) + 1. Lemma 1.3.8. Every pure interval is a +1-interval. Proof. Let [T, T +A] be a pure interval and take b > a. Suppose that # T (b, a) = v and # T +A (b, a) = v+k with k > 1. Let S be the multi-set of inversions such that # S (c, a) = # T (c, a) + 1 if (a, c) ∈ A and otherwise # S (c, a) = # T (c, a). In particular, S tc is the tree-inversion set of T + A. There is a transitivity path in S

  By definition of S, we have that (b i+1 , b i ) is a tree-ascent of T which belongs to A. By Condition (i) of Definition 1.1.7, it means that b i+1 is a descendant of b i . In particular, they belong to the same subtree of b and we have # T (b, b

Figure 14 .

 14 Figure14. A +1-interval that is not a pure interval.

  # T1 (c, a) = 0 or # T1 (c, a) = s(c). The second option is not possible because (c, a) varies. So # T1 (c, a) = 0 and there exists d > c such that # T1 (d, a) < # T1 (d, c). In T 2 , we have # T2 (c, a) = # T1 (c, a) + 1 = 1, which gives by transitivity that # T2 (d, a) ≥ # T2 (d, c) ≥ # T1 (d, c) > # T1 (d, a). In particular, (d, a) varies. We have d > c > a with variations (d, a) and (c, a), using Condition (1) of pure-candidate intervals, we obtain that (d, c) also varies. But if # T2 (d, c) > # T1 (d, c), the amplitude of the (d, a) variation is greater than 1 and we reach a contradiction as we work in a +1-interval by hypothesis. □ Lemma 1.3.14. Let [T 1 , T 2 ] be +1-interval satisfying Condition (1). If (c, a) v and (b, a) w are variations and (c, a) v is an essential variation then (c, b) v is an essential variation. Proof. By Condition (1), (c, b) v is a variation. Using Lemma 1.3.13, a is a descendant of b because (b, a) is a variation. So if b is a middle descendant of any b ′ with c > b ′ > b, so is a. As (c, a) is an essential variation, this implies that (c, b) is also an essential variation. □

  Lemma 1.3.15 (Weak transitivity of essential variations). Let [T 1 , T 2 ] be a pure-candidate interval. Suppose that we have c > b > a with (c, b) v and (b, a) 0 essential variations. Then (c, a) v is also an essential variation.

  ′ with c > b ′ > a such that (c, b ′ ) v is an essential variation and a belongs to a middle child of b ′ . We have # T1 (b, a) = 0 so a does not belong to a middle child of b and b ̸ = b ′ . Suppose that c > b > b ′ . We have (c, b) v and (c, b ′ ) v essential variations and s(b) ̸ = 0 (because (b, a) varies), by Condition (2) on pure-candidate intervals, we obtain that (b, b ′ ) 0 is a variation, which contradicts the fact that (b, a) is an essential variation. Now if c > b ′ > b, because s(b ′ ) ̸ = 0 (as a belongs to a middle child of b ′ ), we obtain that (b ′ , b) 0 is a variation. By planarity (Definition 1.1.1), this gives # T1 (b, a) = s(b) which contradicts the fact that (b, a) varies. □ Lemma 1.3.16. Let [T 1 , T 2 ] be a pure-candidate interval. Suppose that (c, a) v is an essential variation. If b is such that c > b > a with # T1 (c, b) = v and # T1 (b, a) < s(b), then (c, b) v varies. Proof. Suppose that (c, b) does not vary. As (c, a) varies, we have # T2 (c, a) > # T1 (c, a). And because (c, b) does not vary, we have # T2 (c, b) = # T1 (c, b). We obtain that # T2 (c, a) > # T2 (c, b) which implies by planarity (Definition 1.1.1) that # T2 (b, a) = s(b), i.e., (b, a) varies. As (c, a) and (b, a) vary, Condition (1) implies that (c, b) also varies which leads to a contradiction. □ Lemma 1.3.17. Let [T 1 , T 2 ] be a pure-candidate interval. Suppose that (c, a) is an essential variation. Then, there is no b such that c > b > a and a is a middle descendant of b. In particular, if b < c with (b, a) a variation, then (b, a) is an essential variation. Proof. This is a direct consequence of Lemma 1.3.16. If a is a middle descendant of b, then # T1 (c, b) = # T1 (c, a) = v and # T1 (b, a) < s(b) which implies that (c, b) varies and so (c, a) is not an essential variation. Now if (b, a) is a variation but not an essential variation, this means that a is a middle descendant of some b ′ with b > b ′ > a which contradicts the first part of the Lemma. □

Proposition 1 .

 1 3.18 (Minimal essential variations are tree-ascents). Let (c, a) v be a minimal essential variation of a pure-candidate interval [T 1 , T 2 ]. Then (a, c) is a tree-ascent of T 1 . Proof. We check the conditions of Definition 1.1.7. Condition (i) is satisfied by Lemma (1.3.13). As (c, a) varies, we have # T1 (c, a) < s(c) and so Condition (ii) is satisfied. Let us prove Condition (iii), i.e., if there is b with c > b > a and a a descendant of b, then a is a right descendant of b. Suppose that # T1 (b, a) < s(b), by Lemma 1.3.16, we have that (c, b) v is a variation. This is actually an essential variation because a is a descendant of b and (c, a) v is an essential variation. We then have essential variations (c, a) v and (c, b) v and we have supposed that # T1 (b, a) < s(b) which implies that s(b) > 0. By Condition (2) we have that (b, a) 0 is a variation. And by Lemma 1.

Definition 1 .

 1 3.19 (Variation path). Let I = [T 1 , T 2 ] be an interval and (c, a) v a variation. The variation path between c and a is given byc > c 1 > • • • > c k where the set {c i } ki=1 consists of all values c i ≥ a such that (c, c i ) v is an essential variation and either c i = a or # T1 (c i , a) < s(c i ).

Proposition 1 .

 1 3.23 (Transitive closure of minimal essential variations). Let [T 1 , T 2 ] be a pure-candidate interval and let A be the set of couples (a, c) such that (c, a) is a minimal essential variation of [T 1 , T 2 ]. Then T 2 = T 1 + A.

Proof.

  We want to prove that for all c > a, we have # T2 (c, a) = # T1+A (c, a). It is clear that T 1 + A ≤ T 2 . Indeed, let S be the multi-set of inversions such that # S (c, a) = # T1 (c, a)+1 if (c, a) is a minimal essential variation of [T 1 , T 2 ] and # S (c, a) = # T1 (c, a) otherwise (S tc = inv(T + A)). Clearly, as the minimal essential variations are a subset of the variations of [T 1 , T 2 ], we have S ⊆ inv(T 2 ) which implies that it is also the case for the transitive closure. In particular, if (c, a) is not a variation, # T2 (c, a) = # T1 (c, a) = # T1+A (c, a). Let us assume that (c, a) v is a variation in [T 1 , T 2 ] and take c > c 1 > • • • > c k ≥ a the variation path of (c, a). By Lemma 1.3.22, (c, c 1 ) v and (c i , c i+1 ) 0 are minimal essential variations for all i < k. This means that # S (c, c 1 ) = v + 1 and # S (c i , c i+1 ) = 1. Besides, if c k ̸ = a, then a is a middle descendant of c k and # T1 (c k , a) > 0. By taking the transitive closure of the multi-set of inversions S, we obtain indeed # T1+A (c, a) ≥ v + 1.□

Lemma 1 .

 1 3.27. Let c > b > a such that there is an ascent-path c > c 1 > . . . c k ≥ a between c and a with # T (c, a) = # T (c, b) = v (in particular, v < s(c)). Then, one of the following is true:(i) b = c i for a certain i; (ii) b is a middle descendant of c i for a certain i; (iii) # T (b, a) = s(b).Proof. Suppose that b ̸ = c i for all i. We first look at the case where b > c k . Let c 0 := c and (c i+1 , c i ) with 0 ≤ i < k be the tree-ascent surrounding b, i.e.,c i > b > c i+1 . Either c i = c and # T (c, b) = # T (c i , c i+1 ) by hypothesis or # T (c i , c i+1 ) = 0. If # T (c i , b) = # T (c i , c i+1 ), then Statement (iii) of Proposition 1.1.8 gives that # T (b, c i+1 ) = s(b) and we are in Case (iii). If # T (c i , b) ̸ = # T (c i , c i+1 ), then c i ̸ = c and # T (c i , b) > # T (c i , c i+1 ) = 0. As (c i , c i-1 )is a tree-ascent, either, # T (c i , b) < s(c i ) and we are in Case (ii) or Statement (iv) of Proposition 1.1.8 gives # T (c i-1 , b) > # T (c i-1 , c i ) (because the right child of c i is empty). This implies that i -1 > 0 and we can use the same reasoning until we reach an element c j with 0 < j ≤ i such that 0 < # T (c j , b) < s(c j ): i.e., b is a middle descendant of c j . In the case where b < c k , if (a, c k ) 0 is a tree-ascent, then the previous case still applies. If not, a is a middle child of c k and (c k , c k-1 ) is a tree-ascent. If # T (c k , b) = 0 < # T (c k , a), we are in Case (iii). If # T (c k , b) < s(c k ), then b is a middle descendant of c k . If # T (c k , b) = s(c k ), we have s(c k ) > 0 (it has a middle child). We get that # T (c k-1 , b) > # T (c k-1 , c k ) and we can apply the same reasoning as earlier to find c j such that b is a middle descendant of c j . □ Example 1.3.28. Look again at Figure 10.

  c, a) v is a variation of [T, T + A]. It is an essential variation if and only if c k = a. More specifically, for all b such that c > b > c k , then c k is never a middle descendant of b.Proof. It is quite clear that (c, a) varies. By hypothesis, # T (c, a) = v. As each step in c > c 1 > • • • > c k , (c i , c i-1) is a tree-ascent of A, the cardinality increases and you get # T +A (c, c 1 ) = v + 1 and# T +A (c i , c i+1 ) = 1. Besides, if a ̸ = c k , then it is a middle descendant of c k meaning # T +A (c k , a) ≥ # T (c k , a) > 0. By transitivity, # T +A (c, a) ≥ v + 1. If a ̸ = c k ,then (c, c k ) varies and (c, a) is not an essential variation. Reversely, assuming the second part of the lemma is true, we get that (c, c k ) is always an essential variation. Now let b be such that c > b > c k . If # T1 (c, b) ̸ = v, then c k cannot be a middle descendant of b. We assume # T1 (c, b) = v and look at the different possibilities of Lemma 1.3.27 on the ascent-path between c and c k . If b = c i for a certain i, then # T (b, c k ) = 0. If b is a middle descendant of a certain c i , then c k lies to the left of b and # T (b, c k ) = 0. The only case left is # T (b, c k ) = s(b). We get that c k is never middle descendant of b. □ Lemma 1.3.30. Let (c, a) v be a variation of a pure interval [T, T + A], then the variation path c > c 1 > • • • > c k ≥ a of (c, a) v as defined by Definition 1.3.19 is an ascent-path. Proof. Let (c, a) v be a variation of [T, T +A]. Let S be the multi-set of inversions set such that # S (c, a) = # T (c, a) + 1 if (a, c) ∈ A and # S (c, a) = # T (c, a) otherwise, so S tc is the tree-inversion set of T + A. By definition, there is a transitivity path in S, c = c 0 > c 1 > • • • > c k > c k+1 = a such that # S (c, c 1 ) = v + 1 and # S (c i , c i-1 ) > 1.

( 1 )

 1 and (2) of Theorem 1.3.9. We first prove that [T, T + A] satisfies Condition[START_REF]The s-Tamari lattice (background) We recall the definition of the s-Tamari lattice and its connection with the ν-Tamari lattice of Préville-Ratelle and Viennot[END_REF]. Let (c, a) v and (b, a) w be variations of [T, T + 1] with c > b > a. Lemma 1.3.30 states that there is an ascent-path between c and a and an ascent-path between b and a. In particular, a is a descendant of both c and b which implies # T1 (c, b) = # T1 (c, a) = v. We now use Lemma 1.3.27 on c > b > a and the ascent-path c > c 1 > • • • > c k ≥ a. The three possible cases give (i) b = c i for a certain i: then (c, b) v is a variation. (ii) b is a middle descendant of a certain c i : (c, b) v is variation by transitivity because (c, c i ) v is a variation. (iii) # T (b, a) = s(b): this is impossible because (b, a) varies. Now, let us prove Condition (2). Suppose that there exists c > b > a with (c, a) v and (c, b) v essential variations for some v and s(b) > 0 and (b, a) 0 is not a variation. We choose b such that the distance between c and b is minimal. In particular, if c > b 1 > • • • > b k ′ = b is the variation path between c and b, we have that (b i , a) 0 is a variation for i < k ′ . Indeed, c > b i > b > a and (c, b i ) v is an essential variation and s(b i ) > 0 (as (b i+1 , b i ) is a tree-ascent). We now look at the ascent-path c > c 1 > • • • > c k = a between c and a and again use Lemma 1.3.27 on c > b > a. If b = c i for some i, then there is an ascent-path b = c i > • • • > c k = a and by Lemma 1.3.29, we have an essential variation (b, a) 0 . As (c, b) is an essential variation, b cannot be a middle descendant of any c i . Only the last case remains where # T (b, a) = s(b) > 0. We write, c 0 := c. The ascent-path between c and b gives us that (b, b k ′ -1 ) is a treeascent. As s(b) > 0, then # T (b, a) = s(b) implies that # T (b k ′ -1 , a) > # T (b k ′ -1 , b) by Statement (iv) of Proposition 1.1.8. Either b k ′ -1 = c and this contradicts # T (c, a) = # T (b, a) or (b k ′ -1 , a) 0 is an essential variation by minimality of the distance c -b and again we reach a contradiction. □ 1.3.4.3. Proof of Theorems 1.

Proposition 1 .Figure 15 .

 115 Figure 15. Example of intersections of pure intervals for s = (0, 2, 2)

Lemma 1 .

 1 4.4 (intersection stability). Let [T, T + A] and [T′ , T ′ + A ′ ] be two pure intervals with a nonempty intersection. Let X = T ∨ T ′ . Suppose that there is b > a with # T (b, a) = # T ′ (b, a) = v. Then # X (b, a) = v.Proof. Let us suppose that there exist a < b with # T (b, a) = # T ′ (b, a) = v and # X (b, a) > v. We choose a such that |b -a| is minimal. As the intersection of [T, T + A] and [T ′ , T ′ + A ′ ] is non-empty, in particular, X ∈ [T, T + A]: the inversion (b, a) varies in [T, T + A] and using the +1 property of Lemma 1.3.8, we obtain # X (b, a)

  then k is not minimal. By transitivity, we have that # X (b 1 , b 3 ) = v + 1, and the +1 property gives us # T (b 1 , b 3 ) = # T ′ (b 1 , b 3 ) = v. This contradicts the minimality of |b -a|.

  a), which means that (b 2 , a) varies in [T, T + A]. We also have # X (b, a) > # T (b, a) by hypothesis, so (b, a) varies in [T, T + A]. Using Condition (1) of Theorem 1.3.9, we obtain that (b, b 2 ) also varies in [T, T + A] so # T +A (b, b 2 ) = v + 2. By transitivity, this gives # T +A (b, a) = v + 2 which contradicts the fact that # T (b, a) = v by the +1 property. □ Proposition 1.4.5 (Variation intersection). Let [T, T + A] and [T ′ , T ′ + A ′ ] be two pure intervals such that they have a non empty intersection [X, Y ] where X = T ∨ T ′ and Y

  b, a) and this gives us S ⊆ inv(T + A) and S ⊆ inv(T ′ + A ′ ). As Y = (T + A) ∧ (T ′ + A ′ ), this gives that S ⊆ inv(Y ) and so # Y (b, a) ≥ v + 1: (b, a) v is a variation of [X, Y ]. Conversely, if (b, a) does not vary in T . We have # T (b, a) = # T +A (b, a) = v and because T ≤ X ≤ Y ≤ T + A, this implies that # X (b, a) = # Y (b, a) = v and (b, a) is not a variation of [X, Y ].

Figure 16 .

 16 Figure 16. Example of an intersection of pure intervals in size 10

Definition 1 .

 1 4.8. Let [T, T + A] and [T ′ , T ′ + A ′ ] be two pure intervals with a non-empty intersection [X, Y ]. We say that (c, a) v is a compatible variation of the intersection if (c, a) v is a variation in both [T, T + A] and [T ′ , T ′ + A ′ ] and for all b with c > b > a such that a is a middle descendant of b in T ′ (resp. T ) then # T (b, a) = s(b) (resp. # T ′ (b, a) = s(b)). Note that if (c, a) v is an essential variation of both [T, T + A] and [T ′ , T ′ + A ′ ] then it is compatible because by Property (3) of Proposition 1.3.33, a is never a middle descendant of any b, c > b > a in neither T nor T ′ . Proposition 1.4.9. Let [T, T + A] and [T ′ , T ′ + A ′ ] be two pure intervals with a non-empty intersection [X, Y ]. Then (c, a) v is an essential variation of [X, Y ] if and only if, (c, a) v is a compatible variation of the intersection.

Proof.

  Let us first suppose that a variation (c, a) v is compatible for the intersection and show that it is an essential variation of the intersection [X, Y ]. By definition, it is a variation of both [T, T + A] and [T ′ , T ′ + A ′ ] so by Proposition 1.4.5, it is a variation of [X, Y ]. Now, take b with c > b > a. If # T (b, a) = # T ′ (b, a) = 0, then by intersection stability (Lemma 1.4.4), # X (b, a) = 0. Now if a is a middle descendant of b in T ′ , the compatibility implies that # T (b, a) = s(b) and so # X (b, a) = s(b). Similarly, if a is a middle descendant of b in T , the compatibility gives # X (b, a) ≥ # T ′ (b, a) = s(b). So a is never a middle descendant of b in X which implies that (c, a) v is an essential variation. We want to show the reverse implication, namely: the essential variations consists only of the compatible variations. Let us choose (c, a) v such that it is an essential variation of [X, Y ]. Proposition 1.4.5 tells us that (c, a) v is a variation for both [T, T + A] and [T ′ , T ′ + A ′ ]. Let us suppose that there exists b, with c > b > a and a is a middle descendant of b in T ′ . Remember that by Statement (2) of Proposition 1.3.33, this means that (c, b

  11. Suppose that (c, a) is an essential variation of an intersection [X, Y ] of two pure intervals [T, T + A] and [T ′ , T ′ + A ′ ], then for all b such that a is a middle descendant of b in T with c > b > a, we have # T ′ (b, a) = s(b) whereas # T (b, a) < s(b). This means in particular that # X (b, a) = s(b) and implies (1) by the +1 property #(b, a) can vary by at most 1 and so # T (b, a) = s(b) -1 (a is in the before last subtree of b); (2) (b, a) s(b)-1 is a variation of [T, T + A]. Proposition 1.4.12. Let [T, T + A] and [T ′ , T ′ + A ′ ] be two pure intervals with a non-empty intersection

  By the +1 property, we obtain # T (b, b ′ ) = s(b) -1. Moreover, both (b, a) and (b, b ′ ) vary as their cardinality increases in T ′ . They are essential variations because we have chosen b to be minimal. By Condition (2) of pure intervals on b > b ′ > a, as s(b ′ ) > 0, then # T (b ′ , a) = 0 which contradicts # T (b ′ , a) = s(b ′ ). □ 1.4.4. Proof of the Intersection Theorem. Now that we characterized the variations and the essential variations of the intersection, we are ready to prove the Intersection Theorem 1.4.1. Proof of Theorem 1.4.1. Let [T, T + A] and [T ′ , T ′ + A ′ ] be two pure intervals with a non-empty intersection [X, Y ]. We prove that the variations and essential variations of [X, Y ] satisfy the conditions of Theorem 1.3.9.

Figure 17 .

 17 Figure 17. Bijection between the s-Tamari lattice and the ν( ←s )-Tamari lattice for s = (0, 2, 2). (Figure 16 of [CP22])

Figure 19 .

 19 Figure 19. Example of a 3-dimensional pure s-Tamari interval.

Figure 20 .

 20 Figure 20. The ν-associahedron for ν = N EEN EEN .

  is mapped to the pure ν-Tamari interval in Figure 21. Moreover, the following proposition gives a nice and simple classification of pure ν-Tamari intervals, as the sets of ν-trees containing covering ν-faces. Proposition 2.2.7. Let T is a ν-tree and A is a (possibly empty) subset of ν-ascents of T . If F = T ∖A is the corresponding covering ν-face, then [T , T + A] = {ν-trees T ′ : F ⊆ T ′ } . (12)

FFF]

  and a unique maximal element T max = {ν-trees T ′ : F ⊆ T ′ } . (13) By construction, we have that T = T min F and A = T ∖ F. It remains to show that T + A = T max F . By [CPS19, Lemma 4.4 or Proposition 5.16], the interval in Equation (

Figure 21

 21 Figure 21 shows an example of a pure ν-Tamari interval. The ν-ascents A of the ν-tree T are the circled nodes in the figure, and the covering ν-face F = T ∖ A is the set of filled red nodes. The ν-trees in the interval [T , T + A] are exactly the ν-trees containing these filled red nodes. Corollary 2.2.8. Let [T , T + A] and [T ′ , T ′ + A ′ ] be two pure ν-Tamari intervals, and F = T ∖ A and F ′ = T ′ ∖ A ′ be their corresponding covering ν-faces. Then [T , T + A] ⊆ [T ′ , T ′ + A ′ ] if and only if F ⊇ F ′ .

Figure 21 .

 21 Figure 21. Example of a pure ν-Tamari interval

1 .

 1 Let [T, T + A] and [T ′ , T ′ + A ′ ] be two pure s-Tamari intervals. Consider the corresponding pure ν-Tamari intervals [T , T + A] and [T ′ , T ′ + A ′ ] determined by the bijection φ, and let F = T ∖ A and F ′ = T ′ ∖ A ′ be the corresponding covering ν-faces. Since φ is order preserving, [T, T + A] ⊆ [T ′ , T ′ + A ′ ] if and only if [T , T + A] ⊆ [T ′ , T ′ + A ′ ]. Combining this with Corollary 2.2.8, we get that [T, T + A] ⊆ [T ′ , T ′ + A ′ ] if and only if F ⊇ F ′ as we wanted. □ Part 3. Polytopal conjectures 3.Polytopal complex and polytopal subdivision realizations

Figure 24 .

 24 Figure 24. Realizations of s-associahedra from s-permutahedra

Figure 26 .

 26 Figure 26. A tantalizing option for s-permutahedra and s-associahedra of Coxeter type B 2 .

Figure 27 .( 1 +( 1 +

 2711 Figure 27. The s-braid arrangement for s = (0, 2, 3).

s

  3 + (# T (4, 1) -# T (4, 3)) + (# T (4, 2) -# T (4, 3)) if 0 < # T (3, i) < s 3 , 2s 3 if # T (3, i) = s 3 .

Figure 28 .

 28 Figure 28. Construction of a 3 dimensional realization.

  Meanwhile, Conjecture 3.1.2 (and consequently, Conjecture 3.1.1) have been proved in the particular case where s contains no zeros [GDMP + 23, Theorem 1.3]. The case when s contains zeros is still open. Besides dimensions 2 and 3, Conjecture 3.1.3 remains open for all s.

  1.3.3. Proof Part 1: Pure-candidate intervals are pure intervals. Proposition 1.3.12. If [T 1 , T 2 ] is a pure candidate interval, then it is a pure interval. More precisely, we have that [T 1 , T 2

  3.4.2. Variations and essential variations of pure intervals. As a straight forward consequence of Lemmas 1.3.29 and 1.3.30, we also obtain the following characterization of variations and essential variations of pure intervals.

Proposition 1.3.32. Let [T, T + A] be a pure interval. Then, (c, a) v is a variation if and only if there is an ascent

This project was supported by the ANR-FWF International Cooperation Project PAGCAP, funded by the ANR Project ANR-21-CE48-0020 and the FWF Project I 5788. Cesar Ceballos was also supported by the Austrian Science Fund FWF, Project P 33278.

C. CEBALLOS AND V. PONS

from [START_REF] Ceballos | The ν-Tamari lattice via ν-trees, ν-bracket vectors, and subword complexes[END_REF]: denote by h i the number of nodes that need to be added at height i. We add these nodes from bottom to top, from right to left, avoiding forbidden positions. The forbidden positions are those above a node that is not the left most node in a row. See Figure 17 for an illustration. (2) two s-Tamari trees are connected by an edge if and only if they are related by an s-Tamari rotation. We refer to pure s-Tamari intervals [T, T + A] as faces of Asso(s), and say that one face is contained in another if the containment holds as intervals in the s-Tamari lattice. Figure 3 illustrates an example of the s-associahedron Asso(0, 2, 2). As we can see, it is a polytopal complex whose faces are labeled by pure s-Tamari intervals, and whose edge graph is the Hasse diagram of the s-Tamari lattice. Its f -polynomial is 12 + 16t + 5t 2 . Indeed, there are 12 s-Tamari trees (faces of dimension 0), 16 edges (faces of dimension 1) and 5 pure s-Tamari intervals of dimension 2, which correspond to the 5 polygons.

The following proposition is straightforward from the definition.

Proposition 2.2.4. The f -polynomial of the s-associahedron Asso(s) is given by

where the sum ranges over all s-Tamari trees T and tasc(T ) denotes the number of s-Tamari ascents of T .