# The s-weak order and s-permutahedra II: the combinatorial complex of pure intervals

Cesar Ceballos, Viviane Pons

► To cite this version:

Cesar Ceballos, Viviane Pons. The s-weak order and s-permutahedra II: the combinatorial complex of pure intervals. The Electronic Journal of Combinatorics, 2024, 31 (3), pp.P3.12. 10.37236/12438 . hal-04390514

HAL Id: hal-04390514

https://hal.science/hal-04390514v1

Submitted on 12 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
THE *s*-WEAK ORDER AND *s*-PERMUTAHEDRA II:
THE COMBINATORIAL COMPLEX OF PURE INTERVALS

CESAR CEBALLOS* AND VIVIANE PONS*

ABSTRACT. 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 *v*-associahedron. Finally, we present three polytopality conjectures, evidence supporting them, and some hints about potential generalizations to other finite Coxeter groups.

CONTENTS

Introduction 2

Part 1. The *s*-permutahedron 6

1.1. The *s*-weak order (background) 6

1.1.1. Lattice definition through *s*-decreasing trees and tree-inversions 6

1.1.2. Tree-ascents and cover relations 8

1.2. The *s*-permutahedron 10

1.2.1. Pure intervals of the *s*-weak order 10

1.2.2. The combinatorial complex of pure intervals 12

1.3. Characterization of pure intervals 16

1.3.1. Variations and essential variations of an interval 16

1.3.2. The Characterization Theorem 17

1.3.3. Proof Part 1: Pure-candidate intervals are pure intervals 19

1.3.4. Proof Part 2: Pure intervals are pure-candidate intervals 22

1.3.5. Properties of variations of pure intervals 25

1.4. Intersection of pure intervals 25

1.4.1. The Intersection Theorem 25

1.4.2. Variations of the intersection 26

1.4.3. Essential variations of the intersection 28

1.4.4. Proof of the Intersection Theorem 29

Part 2. The *s*-associahedron 30

2.1. The *s*-Tamari lattice (background) 30

Date: September 27, 2023.

2020 Mathematics Subject Classification. Primary 20F55 and 52B05; Secondary 06B05 and 06B10.

Key words and phrases. Weak order, Permutahedron, Tamari Lattice, Associahedron.

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.
<table><tbody><tr><td>2.1.1.</td><td>The s-Tamari lattice</td><td>30</td></tr><tr><td>2.1.2.</td><td>The v-Tamari lattice</td><td>31</td></tr><tr><td>2.1.3.</td><td>The s-Tamari lattice and the v-Tamari lattice are isomorphic</td><td>31</td></tr><tr><td><b>2.2.</b></td><td><b>The s-associahedron</b></td><td><b>32</b></td></tr><tr><td>2.2.1.</td><td>The s-associahedron</td><td>32</td></tr><tr><td>2.2.2.</td><td>The v-associahedron</td><td>34</td></tr><tr><td>2.2.3.</td><td>The s-associahedron and the v-associahedron are isomorphic</td><td>37</td></tr><tr><td><b>Part 3.</b></td><td><b>Polytopal conjectures</b></td><td><b>38</b></td></tr><tr><td><b>3.1.</b></td><td><b>Polytopal complex and polytopal subdivision realizations</b></td><td><b>38</b></td></tr><tr><td><b>3.2.</b></td><td><b>Generalizations for finite Coxeter groups</b></td><td><b>41</b></td></tr><tr><td><b>3.3.</b></td><td><b>Geometric realizations in dimensions 2 and 3</b></td><td><b>42</b></td></tr><tr><td><b>3.4.</b></td><td><b>Realization via flow polytopes</b></td><td><b>43</b></td></tr><tr><td></td><td><b>References</b></td><td><b>44</b></td></tr></tbody></table>

## INTRODUCTION

This paper is the second contribution (after [CP22]) to a series of articles related to the s-weak order and the s-permutahedron. We originally introduced these objects in an extended abstract [CP19], which is now developed into two long versions: the prequel [CP22] and this present paper.

<figure><img src="image_2.png" /><figcaption>FIGURE 1. The s-weak order as the edge graph of the s-permutahedron for s = (0, 2, 2).</figcaption></figure>
<figure><img src="image_3.png" /><figcaption>FIGURE 2. The *s*-weak order as the edge graph of the *s*-permutahedron for *s* = (0, 0, 2).</figcaption></figure>

The purpose of the first paper [CP22] 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 and 3. 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 [Tam51, MHPS12]), 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 [AL62], Hopf algebras [LR02, LR98, AS06, HNT05], Cambrian lattices [Rea06], Permutrees [PP18], cluster algebras [FZ02, FZ03], representation theory [Hai94, BP12], 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 [BP12] and the more general *v*-Tamari lattice of Préville-Ratelle and Viennot [PRV17], whose study is motivated by conjectural connections with the theory of (multivariate higher) diagonal harmonics in representation theory, see e.g. [BP12, BMCPR13, BMFPR11, BCP22].

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 [GR70] 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 [Bjö84, Hoh12]. The weak order has well known connections with the classical Tamari lattice, which can be obtained from it both as a sublatttice [BW97] and as a lattice quotient [Rea06]. These properties have interesting geometric and algebraic counterparts. Geometrically, the associahedron can be obtained by removing certain facets of the permutahedron [HL07, HLT11], and this translates into algebraic properties between certain related Hopf algebras [LR02, LR98].
<figure><img src="image_4.png" /><figcaption>FIGURE 3. The s-Tamari lattice as the edge graph of the s-associahedron for s = (0, 2, 2)</figcaption></figure>

The recent extensions of the Tamari lattice and the lack of (type A)<fnref n="1" /> generalizations of the weak order lead to the question: what is the equivalent of the weak order for the *v*-Tamari lattice? The *s*-weak order introduced in [CP22] 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 *v*-Tamari lattice.

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

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 and 3, 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.

<footnote n="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.</footnote>
<figure><img src="image_6.png" /></figure>

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 [CPS19] (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 [CPS19]. 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 [CP19], 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 [Lac22], where he shows that they are the only intervals of the *s*-weak order which are homotopy equivalent to a sphere.

These recent advances motivate 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 [The22] code used to reach the results as well as a demo SageMath worksheet with computations of all examples in this paper [Pon23b].
<figure><img src="image_7.png" /><figcaption>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).</figcaption></figure>

# 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 [CP22] needed for Part 1 of this paper. We call a sequence *s* = (*s*₁, *s*₂), . . ., *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*₀<sup>*y*</sup>, . . ., *T*<sup>*y*</sup>*m* the *m* + 1 children of *y*. Then *T*₀<sup>*y*</sup> is the *left child* of *y*, while *T*₁<sup>*y*</sup>, . . ., *T*<sup>*y*</sup>*m*−₁ are the *middle children* of *y* and *T*<sup>*y*</sup>*m* is the *right child* of *y*. Besides, if *m* > 0, we say that *T*₀<sup>*y*</sup> (*resp.* *T*<sup>*y*</sup>*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 *#*<sub>*T*</sub>(*c*, *a*), is given
<figure><img src="image_8.png" /><figcaption>FIGURE 5. an s-decreasing tree and its tree-inversions (Figure 4 of [CP22])</figcaption></figure>

by the relative position of a towards c. If a is left of c or belongs to $T_0^c$, then $\#_T(c, a) = 0$. If a belongs to a middle child $T_i^c$ (with $0 < i < m$), then $\#_T(c, a) = i$. Finally, if a belongs to $T_m^c$ or is right of c, then $\#_T(c, a) = m$. We give many examples on Figure 5.

As we explain in [CP22], 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 multi-permutations. In particular, if $s = (1, 1, \dots)$, 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 [CP22]). 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) \notin 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 \subseteq J$ (resp. $I \subset J$) if $\#_I(c, a) \le \#_J(c, a)$ (resp. $\#_I(c, a) < \#_J(c, a)$) for all $(c, a) \in I$.

Given a weak composition $s$ with $\ell(s) = n$, we write $\Sigma_s$ the *maximal s-inversion set* defined by $\#_{\Sigma_s}(c, a) = s(c)$ for all $1 \le a < c \le 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) \ge \#_I(c, b)$.

Given a weak composition $s$ with $\ell(s) = n$ and $I \subseteq \Sigma_s$, then $I$ is *planar* if for all triplets $1 \le a < b < c \le n$, either $\#_I(b, a) = s(b)$ or $\#_I(c, b) \ge \#_I(b, a)$.

We prove the following.

**Proposition 1.1.2** (Proposition 1.6 of [CP22]). 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 $\Sigma_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
<figure><img src="image_9.png" /><figcaption>FIGURE 6. Illustration of the transitivity and planarity conditions on s-tree inversion sets. (Figure 5 of [CP22])</figcaption></figure>

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 [CP22] that it is a lattice using the following two operations on multi-sets.

**Definition 1.1.3** (Definition 1.12 of [CP22]). The union of two multi-sets of inversions *I* and *J* is given by

$$ (1) \qquad \#_{I \cup 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 \ge 2$ values $c = b_1 > b_2 > \cdots > b_k = a$ such that $\#_I(b_i, b_{i+1}) > 0$ for all $1 \le i < k$. Note that if $\#_I(c, a) > 0$, then $(c, a)$ itself is a transitivity path. We write $I^{\text{tc}}$ for the *transitive closure* of *I*, which is defined as follows. For all $a < c$, $\#_{I^{\text{tc}}}(c, a) = v$ with $v$ the maximal value of $\#_I(b_1, b_2)$ for $c = b_1 > \cdots > b_k = a$ a transitivity path between $c$ and $a$.

**Definition 1.1.5** ([CP22, Definition 1.9]). Let *R* and *T* be two s-decreasing trees of a same weak composition *s* with $\ell(s) = n$. We say that $R \prec T$ if $\mathrm{inv}(R) \subseteq \mathrm{inv}(T)$ using the inclusion of multi-sets. We call the relation $\prec$ the *s-weak order*.

**Theorem 1.1.6** (Theorem 1.21 of [CP22]). 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) \qquad \mathrm{inv}(T \lor R) = (\mathrm{inv}(T) \cup \mathrm{inv}(R))^{\mathrm{tc}}. $$

We show an example of the computation of the join on Figure 7, please see [CP22] 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 [CP22].

**Definition 1.1.7** (Definition 1.24 from [CP22]). 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.
<figure><img src="image_10.png" /><figcaption>FIGURE 7. The computation of $T \lor R$ in the s-weak lattice (Figure 7 of [CP22])</figcaption></figure>

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.

<figure><img src="image_11.png" /><figcaption>FIGURE 8. Schematic illustration of two s-trees containing an ascent $(a, c)$. (Figure 8 from [CP22])</figcaption></figure>

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 [CP22], we prove the following result, which basically translates all the conditions of Definition 1.1.7 in terms of tree-inversions.
**Proposition 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 \le 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)$;

(iv) if $s(a) > 0$, for all $a' < a$, then $\#(a, a') = s(a)$ implies that $\#(c, a') > \#(c, a)$.

## 1.2. THE s-PERMUTAHEDRON

The key idea of this paper is that even if the *s*-week order is just a poset, it actually possesses 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) \in A$ by one and then taking the transitive closure.<fnref n="2" />

**Definition 1.2.1.** Let $T_1 \prec 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, and 11.

<figure><img src="image_12.png" /><figcaption>FIGURE 9. Example of a pure interval. On the left, the minimal tree with colored tree-ascents and on the right the corresponding interval.</figcaption></figure>

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 [CP22], 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 $\#_{T_1}(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

<footnote n="2">²We use this notation for simplicity but it is not entirely consistent with [CP22]. Indeed, we used the notation $(c, a)$ in [CP22] 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)$.</footnote>
<figure><img src="image_13.png" /><figcaption>FIGURE 10. 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.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>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.</figcaption></figure>

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 tree-ascents of $T_1$. Then $T_2$ can be obtained as the join $T_2 = \bigcup_{a \in A} (T_1 + a)$ over all trees $T_1 + a$ obtained from $T_1$ by rotating a tree-ascent $a \in 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) = \#_{T_1}(c, a) + 1$
while all other values are unchanged. Similarly, we write $M_A := \cup_{(a,c) \in A} M_{(a,c)}$, i.e., all cardinalities
$(c, a)$ with $(a, c) \in 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_{(a,c)}^{\text{tc}}$, i.e., the transitive closure of $M_{(a,c)}$.
Similarly, the tree-inversions of $T+A$ are given by $M_A^{\text{tc}}$.

By definition, we have $M_{(a,c)} \subseteq M_A$ for all $(a,c) \in 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_{(a,c)}^{\text{tc}} \subseteq M_A^{\text{tc}}$. In other words, $T_1 + (a, c) \preceq T_1 + A$. By taking the lattice join, we obtain $T_2 \preceq T_1 + A$.

Now by definition of the join, the inversions of $T_2$ are given by $\text{inv}(T_2) = M_2^{\text{tc}}$ where $M_2 = \cup_{(a,c) \in A} M_{(a,c)}^{\text{tc}}$. In particular, $M_2 \neq 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) \in A$ we know that $\#M_2(c, a) \ge \#M_{(a,c)}(c, a) = \#T_1(c, a) + 1 = \#M_A(c, a)$. Besides, for each couple $a' < c'$ such that $(a', c') \notin A$, we have $\#M_2(c', a') \ge \#T_1(c', a') = \#M_A(c', a')$. We obtain $M_A \subseteq M_2$. By taking the transitive closure, we have $\text{inv}(T_1 + A) \subseteq \text{inv}(T_2)$ and so $T_1 + A \preceq T_2$. $\square$

**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 $\text{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 $\text{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 $\text{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 $\text{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) \qquad f_s(t) := \sum_{F \in \text{Perm}(s)} t^{\dim(F)} $$

The f-polynomial for our example in Figure 1 is

$$ (4) \qquad 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 $\text{Perm}(s)$ is given by

$$ \sum_{T} (1 + t)^{\text{asc}(T)}, $$

where the sum runs over all s-decreasing trees $T$ and $\text{asc}(T)$ denotes the number of ascents of $T$.

*Proof.* Let

$$ f_s(t) = \sum_{T} (1 + t)^{\text{asc}(T)} = c_0 + c_1 t + c_2 t^2 + \dots $$

We need to show that $c_k$ counts the number of k-dimensional faces of $\text{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)^{\text{asc}(T)}$. $\square$

The polynomial $\sum_{T} t^{\text{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 \ge 2$, then we write $s = (\tilde{s}, u, v)$ where $\tilde{s}$ is the sequence obtained by removing the last two values in $s$, $u = s(n-1)$ and $v = s(n)$. Then

$$ (1) \text{ if } n > 2 \text{ and } u = 0, \text{ then } f_s = f_{(\tilde{s},v)}f_{(0,v)}; $$

$$ (2) \text{ if } n = 2 \text{ or } u > 0, \text{ then } f_s(t) = (v+1)f_{(\tilde{s},u+v)}(t) + vtf_{(\tilde{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 $\text{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 $\text{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** worksheet [Pon23b].

*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 and 13 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 = (\tilde{s}, 0, v)$. We prove that the pure intervals of $s$ are in bijection with products of pure intervals of $(\tilde{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' = (\tilde{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 \neq 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) \in A; a < c < n-1\} \cup \{(a, n-1); (a, n) \in A \text{ and } a \neq 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'' = \emptyset$. 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 \in 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 = (\tilde{s}, u, v)$ and $u \neq 0$. In this case, we prove that there is a bijection between pure intervals of $s$ and some marked pure intervals of $(\tilde{s}, u+v)$ and $(\tilde{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) \notin A$.
<figure><img src="image_15.png" /><figcaption>FIGURE 12. Bijective illustration of Case (1) of the recursive *f*-polynomial computation.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>FIGURE 13. Bijective illustration of Case (2) of the recursive *f*-polynomial computation.</figcaption></figure>

In this case, $(T, A)$ is sent to a marked pure interval of $s' = (\tilde{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><caption>TABLE 1. Some values of $f_s(t)$</caption><tbody><tr><td>f<sub>(0,0,1)</sub>(t) = t<sup>2</sup> + 4t + 4</td><td>f<sub>(0,0,0,1)</sub>(t) = t<sup>3</sup> + 6t<sup>2</sup> + 12t + 8</td><td>f<sub>(0,2,0,1)</sub>(t) = 2t<sup>3</sup> + 13t<sup>2</sup> + 26t + 16</td></tr><tr><td>f<sub>(0,0,2)</sub>(t) = 4t<sup>2</sup> + 12t + 9</td><td>f<sub>(0,0,0,2)</sub>(t) = 8t<sup>3</sup> + 36t<sup>2</sup> + 54t + 27</td><td>f<sub>(0,2,0,2)</sub>(t) = 12t<sup>3</sup> + 58t<sup>2</sup> + 90t + 45</td></tr><tr><td>f<sub>(0,0,3)</sub>(t) = 9t<sup>2</sup> + 24t + 16</td><td>f<sub>(0,0,0,3)</sub>(t) = 27t<sup>3</sup> + 108t<sup>2</sup> + 144t + 64</td><td>f<sub>(0,2,0,3)</sub>(t) = 36t<sup>3</sup> + 153t<sup>2</sup> + 212t + 96</td></tr><tr><td>f<sub>(0,1,1)</sub>(t) = t<sup>2</sup> + 6t + 6</td><td>f<sub>(0,0,1,1)</sub>(t) = t<sup>3</sup> + 12t<sup>2</sup> + 28t + 18</td><td>f<sub>(0,2,1,1)</sub>(t) = 2t<sup>3</sup> + 21t<sup>2</sup> + 48t + 30</td></tr><tr><td>f<sub>(0,1,2)</sub>(t) = 4t<sup>2</sup> + 15t + 12</td><td>f<sub>(0,0,1,2)</sub>(t) = 8t<sup>3</sup> + 51t<sup>2</sup> + 90t + 48</td><td>f<sub>(0,2,1,2)</sub>(t) = 12t<sup>3</sup> + 76t<sup>2</sup> + 135t + 72</td></tr><tr><td>f<sub>(0,1,3)</sub>(t) = 9t<sup>2</sup> + 28t + 20</td><td>f<sub>(0,0,1,3)</sub>(t) = 27t<sup>3</sup> + 136t<sup>2</sup> + 208t + 100</td><td>f<sub>(0,2,1,3)</sub>(t) = 36t<sup>3</sup> + 185t<sup>2</sup> + 288t + 140</td></tr><tr><td>f<sub>(0,2,1)</sub>(t) = 2t<sup>2</sup> + 9t + 8</td><td>f<sub>(0,0,2,1)</sub>(t) = 4t<sup>3</sup> + 30t<sup>2</sup> + 57t + 32</td><td>f<sub>(0,2,2,1)</sub>(t) = 6t<sup>3</sup> + 44t<sup>2</sup> + 85t + 48</td></tr><tr><td>f<sub>(0,2,2)</sub>(t) = 6t<sup>2</sup> + 20t + 15</td><td>f<sub>(0,0,2,2)</sub>(t) = 18t<sup>3</sup> + 96t<sup>2</sup> + 152t + 75</td><td>f<sub>(0,2,2,2)</sub>(t) = 24t<sup>3</sup> + 130t<sup>2</sup> + 210t + 105</td></tr><tr><td>f<sub>(0,2,3)</sub>(t) = 12t<sup>2</sup> + 35t + 24</td><td>f<sub>(0,0,2,3)</sub>(t) = 48t<sup>3</sup> + 220t<sup>2</sup> + 315t + 144</td><td>f<sub>(0,2,2,3)</sub>(t) = 60t<sup>3</sup> + 282t<sup>2</sup> + 413t + 192</td></tr><tr><td>f<sub>(0,3,1)</sub>(t) = 3t<sup>2</sup> + 12t + 10</td><td>f<sub>(0,0,3,1)</sub>(t) = 9t<sup>3</sup> + 56t<sup>2</sup> + 96t + 50</td><td>f<sub>(0,2,3,1)</sub>(t) = 12t<sup>3</sup> + 75t<sup>2</sup> + 132t + 70</td></tr><tr><td>f<sub>(0,3,2)</sub>(t) = 8t<sup>2</sup> + 25t + 18</td><td>f<sub>(0,0,3,2)</sub>(t) = 32t<sup>3</sup> + 155t<sup>2</sup> + 230t + 108</td><td>f<sub>(0,2,3,2)</sub>(t) = 40t<sup>3</sup> + 198t<sup>2</sup> + 301t + 144</td></tr><tr><td>f<sub>(0,3,3)</sub>(t) = 15t<sup>2</sup> + 42t + 28</td><td>f<sub>(0,0,3,3)</sub>(t) = 75t<sup>3</sup> + 324t<sup>2</sup> + 444t + 196</td><td>f<sub>(0,2,3,3)</sub>(t) = 90t<sup>3</sup> + 399t<sup>2</sup> + 560t + 252</td></tr><tr><td></td><td>f<sub>(0,1,0,1)</sub>(t) = t<sup>3</sup> + 8t<sup>2</sup> + 18t + 12</td><td>f<sub>(0,3,0,1)</sub>(t) = 3t<sup>3</sup> + 18t<sup>2</sup> + 34t + 20</td></tr><tr><td></td><td>f<sub>(0,1,0,2)</sub>(t) = 8t<sup>3</sup> + 42t<sup>2</sup> + 69t + 36</td><td>f<sub>(0,3,0,2)</sub>(t) = 16t<sup>3</sup> + 74t<sup>2</sup> + 111t + 54</td></tr><tr><td></td><td>f<sub>(0,1,0,3)</sub>(t) = 27t<sup>3</sup> + 120t<sup>2</sup> + 172t + 80</td><td>f<sub>(0,3,0,3)</sub>(t) = 45t<sup>3</sup> + 186t<sup>2</sup> + 252t + 112</td></tr><tr><td></td><td>f<sub>(0,1,1,1)</sub>(t) = t<sup>3</sup> + 14t<sup>2</sup> + 36t + 24</td><td>f<sub>(0,3,1,1)</sub>(t) = 3t<sup>3</sup> + 28t<sup>2</sup> + 60t + 36</td></tr><tr><td></td><td>f<sub>(0,1,1,2)</sub>(t) = 8t<sup>3</sup> + 57t<sup>2</sup> + 108t + 60</td><td>f<sub>(0,3,1,2)</sub>(t) = 16t<sup>3</sup> + 95t<sup>2</sup> + 162t + 84</td></tr><tr><td></td><td>f<sub>(0,1,1,3)</sub>(t) = 27t<sup>3</sup> + 148t<sup>2</sup> + 240t + 120</td><td>f<sub>(0,3,1,3)</sub>(t) = 45t<sup>3</sup> + 222t<sup>2</sup> + 336t + 160</td></tr><tr><td></td><td>f<sub>(0,1,2,1)</sub>(t) = 4t<sup>3</sup> + 33t<sup>2</sup> + 68t + 40</td><td>f<sub>(0,3,2,1)</sub>(t) = 8t<sup>3</sup> + 55t<sup>2</sup> + 102t + 56</td></tr><tr><td></td><td>f<sub>(0,1,2,2)</sub>(t) = 18t<sup>3</sup> + 104t<sup>2</sup> + 175t + 90</td><td>f<sub>(0,3,2,2)</sub>(t) = 30t<sup>3</sup> + 156t<sup>2</sup> + 245t + 120</td></tr><tr><td></td><td>f<sub>(0,1,2,3)</sub>(t) = 48t<sup>3</sup> + 235t<sup>2</sup> + 354t + 168</td><td>f<sub>(0,3,2,3)</sub>(t) = 72t<sup>3</sup> + 329t<sup>2</sup> + 472t + 216</td></tr><tr><td></td><td>f<sub>(0,1,3,1)</sub>(t) = 9t<sup>3</sup> + 60t<sup>2</sup> + 110t + 60</td><td>f<sub>(0,3,3,1)</sub>(t) = 15t<sup>3</sup> + 90t<sup>2</sup> + 154t + 80</td></tr><tr><td></td><td>f<sub>(0,1,3,2)</sub>(t) = 32t<sup>3</sup> + 165t<sup>2</sup> + 258t + 126</td><td>f<sub>(0,3,3,2)</sub>(t) = 48t<sup>3</sup> + 231t<sup>2</sup> + 344t + 162</td></tr><tr><td></td><td>f<sub>(0,1,3,3)</sub>(t) = 75t<sup>3</sup> + 342t<sup>2</sup> + 490t + 224</td><td>f<sub>(0,3,3,3)</sub>(t) = 105t<sup>3</sup> + 456t<sup>2</sup> + 630t + 280</td></tr></tbody></table><table><tbody><tr><td>f<sub>(0,4,4,4)</sub>(t) = 280t<sup>3</sup> + 1100t<sup>2</sup> + 1404t + 585</td></tr><tr><td>f<sub>(0,5,5,5)</sub>(t) = 585t<sup>3</sup> + 2170t<sup>2</sup> + 2640t + 1056</td></tr><tr><td>f<sub>(0,6,6,6)</sub>(t) = 1056t<sup>3</sup> + 3774t<sup>2</sup> + 4446t + 1729</td></tr><tr><td>f<sub>(0,2,2,2,2)</sub>(t) = 120t<sup>4</sup> + 924t<sup>3</sup> + 2380t<sup>2</sup> + 2520t + 945</td></tr><tr><td>f<sub>(0,3,3,3,3)</sub>(t) = 945t<sup>4</sup> + 5610t<sup>3</sup> + 11946t<sup>2</sup> + 10920t + 3640</td></tr><tr><td>f<sub>(0,2,1,0,2)</sub>(t) = 24t<sup>4</sup> + 188t<sup>3</sup> + 498t<sup>2</sup> + 549t + 216</td></tr><tr><td>f<sub>(0,2,0,1,3,2)</sub>(t) = 640t<sup>5</sup> + 6278t<sup>4</sup> + 21941t<sup>3</sup> + 35474t<sup>2</sup> + 27108t + 7938</td></tr><tr><td>f<sub>(0,1,1,2,0,3,3)</sub>(t) = 16200t<sup>6</sup> + 166377t<sup>5</sup> + 665262t<sup>4</sup> + 1349600t<sup>3</sup> + 1481796t<sup>2</sup> + 841320t + 194040</td></tr></tbody></table>

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 \neq 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) \notin A$, we can keep the selected tree-ascents of $T$ in $T'$. We get $A' = \{(a, c) \in A; a < c \le n-1\} \cup \{(a, n-1); (a, n) \in 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) \notin A$. As there is $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) \in A$, we send $(T, A)$ to a pure interval of $s'' = (\tilde{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 \neq 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) \in A; a < c \le n-1\} \cup \{(a, n-1); (a, n) \in A \text{ and } a \neq 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. $\square$

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 $\text{Perm}(s)$ is a combinatorial complex in the following sense.

(1) *The face of a face is also a face:* If $I \in \text{Perm}(s)$ is a face (a pure interval) and $J \subseteq I$ is a face (a pure interval) then $J \in \text{Perm}(s)$.

(2) *The intersection of any two faces is also a face:* If $I, J \in \text{Perm}(s)$ are two faces (pure intervals) then $I \cap J \in \text{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).

## 1.3. 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).

### 1.3.1. Variations and essential variations of an interval.

**Definition 1.3.1 (Variations).** Let $T_1 \preceq 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 $\#_{T_2}(c, a) > \#_{T_1}(c, a)$. In this case, we say that $(c, a)_v$ where $v = \#_{T_1}(c, a)$ is a variation of $[T_1, T_2]$. We call $v$ the value of the variation. The difference $\#_{T_2}(c, a) - \#_{T_1}(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 $\text{Var}([T_1, T_2])$ the set of variations of the interval, and $\text{EVar}(T_1, T_2)$ the set of essential variations.

We present below two examples based on Figures 9 and 10. This can be computed using SageMath as we show in [Pon23b].

**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) \in 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 $\#_{T_1}(c, b) = \#_{T_1}(c, a) = v$. As $b$ is maximal, there is no $b' > b$ such that $(c, b')$ 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$. Therefore, $(c, b_2)$ is not an essential variation. This proves the uniqueness part. $\square$

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$.

**Lemma 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 $\#_{T_1}(b, a) < s(b)$, we obtain by planarity (Definition 1.1.1) that $\#_{T_1}(c, a) \le \#_{T_1}(c, b)$. As both $(c, b)$ and $(b, a)$ vary, we obtain $\#_{T_2}(c, b) > \#_{T_1}(c, b)$ and $\#_{T_2}(b, a) > \#_{T_1}(b, a) \ge 0$ which gives $\#_{T_2}(c, a) \ge \#_{T_2}(c, b) > \#_{T_1}(c, b) \ge \#_{T_1}(c, a)$ by transitivity. $\square$

**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) \qquad \#_{T_1}(b, a) \le \#_{T_2}(b, a) \le \#_{T_1}(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) \in A$ and otherwise $\#_S(c, a) = \#_T(c, a)$. In particular, $S^{\text{tc}}$ is the tree-inversion set of $T+A$. There is a transitivity path in $S$

$$ b = b_1 > b_2 > \dots > 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 $\text{inv}(T)$ because $\text{inv}(T)$ is transitive and $\#_T(b, a) = v$. Besides, by definition of $S$, we have $\#_T(b_i, b_{i+1}) \le \#_S(b_i, b_{i+1}) \le \#_T(b_i, b_{i+1}) + 1$. This gives us in particular

$$ (6) \qquad \#_T(b_1, b_2) \ge 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) \ge v + k - 1 > v$. 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_{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} > \dots > b_k = a$$

is a transitive path in $\mathrm{inv}(T)$, which implies that $\#_T(b, a) > v$ and leads to a contradiction. $\square$

**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 \in \mathrm{Var}([T_1, T_2])$ and $(b, a)_w \in \mathrm{Var}([T_1, T_2])$ then $(c, b)_v \in \mathrm{Var}([T_1, T_2])$;

(2) if $(c, a)_v \in \mathrm{EVar}([T_1, T_2])$ and $(c, b)_v \in \mathrm{EVar}([T_1, T_2])$ and $s(b) \neq 0$ then $(b, a)_0 \in \mathrm{Var}([T_1, T_2])$.

Note that for Condition (2), we require that $\#_{T_1}(c, a) = \#_{T_1}(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 \preceq 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.

<figure><img src="image_17.png" /><figcaption>FIGURE 14. A +1-interval that is not a pure interval.</figcaption></figure>

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 pure-candidate.
### 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] = [T_1, T_1 + A]$ where $(a, c) \in 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 $\#_{T_1}(c, a) = 0$ or $\#_{T_1}(c, a) = s(c)$. The second option is not possible because $(c, a)$ varies. So $\#_{T_1}(c, a) = 0$ and there exists $d > c$ such that $\#_{T_1}(d, a) < \#_{T_1}(d, c)$. In $T_2$, we have $\#_{T_2}(c, a) = \#_{T_1}(c, a) + 1 = 1$, which gives by transitivity that $\#_{T_2}(d, a) \ge \#_{T_2}(d, c) \ge \#_{T_1}(d, c) > \#_{T_1}(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 $\#_{T_2}(d, c) > \#_{T_1}(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. $\square$

**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. $\square$

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.

**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.

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, $\#_{T_1}(c, a) \le v$ and $\#_{T_2}(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'$ with $c > b' > a$ such that $(c, b')_v$ is an essential variation and $a$ belongs to a middle child of $b'$. We have $\#_{T_1}(b, a) = 0$ so $a$ does not belong to a middle child of $b$ and $b \ne b'$. Suppose that $c > b > b'$. We have $(c, b)_v$ and $(c, b')_v$ essential variations and $s(b) \ne 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') \ne 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 $\#_{T_1}(b, a) = s(b)$ which contradicts the fact that $(b, a)$ varies. $\square$
**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 $\#_{T_1}(c, b) = v$ and $\#_{T_1}(b, a) < s(b)$, then $(c, b)_v$ varies.

*Proof.* Suppose that $(c, b)$ does not vary. As $(c, a)$ varies, we have $\#_{T_2}(c, a) > \#_{T_1}(c, a)$. And because $(c, b)$ does not vary, we have $\#_{T_2}(c, b) = \#_{T_1}(c, b)$. We obtain that $\#_{T_2}(c, a) > \#_{T_2}(c, b)$ which implies by planarity (Definition 1.1.1) that $\#_{T_2}(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. $\square$

**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 $\#_{T_1}(c, b) = \#_{T_1}(c, a) = v$ and $\#_{T_1}(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. $\square$

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.

**Proposition 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 $\#_{T_1}(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 $\#_{T_1}(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 $\#_{T_1}(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.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 $\#_{T_2}(c, a') \ge \#_{T_2}(c, a) > \#_{T_1}(c, a) = \#_{T_1}(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 $\#_{T_1}(a, a') = 0$ which contradicts our initial statement. $\square$

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.

**Definition 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 by

$$c > c_1 > \cdots > c_k$$

where the set $\{c_i\}_{i=1}^k$ consists of all values $c_i \ge a$ such that $(c, c_i)_v$ is an essential variation and either $c_i = a$ or $\#_{T_1}(c_i, a) < s(c_i)$.

**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 \le \#_{T_1}(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 \ne 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, $\#_{T_1}(b, a) < s(b)$ so $b \in \{c_i\}_{i=1}^k$. Now, if $b \ne c_k$, then $b = c_i$ with $i < k$. By Property (i), we have $\#_{T_1}(c_i, c_k) = 0$, which implies $\#_{T_1}(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 $\#_{T_1}(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 $\#_{T_1}(c_1, a) = s(c_1)$ which is impossible by definition of the variation path, or $\#_{T_1}(b, c_1) \ge \#_{T_1}(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 \ne 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 $\#_{T_1}(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. $\square$

**Proposition 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 $\#_{T_2}(c, a) = \#_{T_1+A}(c, a)$. It is clear that $T_1+A \le T_2$. Indeed, let $S$ be the multi-set of inversions such that $\#_S(c, a) = \#_{T_1}(c, a)+1$ if $(c, a)$ is a minimal essential variation of $[T_1, T_2]$ and $\#_S(c, a) = \#_{T_1}(c, a)$ otherwise ($S^{\text{tc}} = \text{inv}(T+A)$). Clearly, as the minimal essential variations are a subset of the variations of $[T_1, T_2]$, we have $S \subseteq \text{inv}(T_2)$ which implies that it is also the case for the transitive closure. In particular, if $(c, a)$ is not a variation, $\#_{T_2}(c, a) = \#_{T_1}(c, a) = \#_{T_1+A}(c, a)$. Let us assume that $(c, a)_v$ is a variation in $[T_1, T_2]$ and take $c > c_1 > \cdots > c_k \ge 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 \ne a$, then $a$ is a middle
descendant of $c_k$ and $\#_{T_1}(c_k, a) > 0$. By taking the transitive closure of the multi-set of inversions $S$, we obtain indeed $\#_{T_1+A}(c, a) \ge v+1$. $\square$

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. $\square$

### 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 useful 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 > \dots > c_k \ge a$ if

(i) $(c_1, c)_v \in A$;

(ii) $(c_i, c_{i-1})_0 \in A$ for all $1 < i \le 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 > \dots 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 > \dots > 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 > \dots > c_k \ge a$ is also an ascent-path, in particular $a$ is a descendant of $c_i$ with $\#_T(c_i, a) = 0$.

**Lemma 1.3.27.** Let $c > b > a$ such that there is an ascent-path $c > c_1 > \dots c_k \ge 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 \ne 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 \le 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) \ne \#_T(c_i, c_{i+1})$, then $c_i \ne 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 \le 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$. $\square$

**Example 1.3.28.** Look again at Figure 10. 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 $\#_{T_1}(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 $\#_{T_1}(7,1) = 1 = s(7)$.

**Lemma 1.3.29.** If $c > c_1 > \dots > c_k \ge a$ is an ascent path in a pure interval $[T, T+A]$, with $\#_T(c,a) = v$, then $(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 > \dots > 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 \ne c_k$, then it is a middle descendant of $c_k$ meaning $\#_{T+A}(c_k, a) \ge \#_T(c_k, a) > 0$. By transitivity, $\#_{T+A}(c, a) \ge v+1$.

If $a \ne 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 $\#_{T_1}(c, b) \ne v$, then $c_k$ cannot be a middle descendant of $b$. We assume $\#_{T_1}(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$. $\square$

**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 > \dots > c_k \ge 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) \in A$ and $\#_S(c, a) = \#_T(c, a)$ otherwise, so $S^{\text{te}}$ is the tree-inversion set of $T+A$. By definition, there is a transitivity path in $S$, $c = c_0 > c_1 > \dots > c_k > c_{k+1} = a$ such that $\#_S(c, c_1) = v+1$ and $\#_S(c_i, c_{i-1}) > 1$. We choose the path so that $k$ is minimal and we prove that this is an ascent-path. In the following, we suppose that $k \ge 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) \ge v+1$ and $c > c_2 > \dots > 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 > \dots \ge c_k$ is a shorter transitivity path. This means that $\#_T(c, c_1) = v$ and that $(c_1, c) \in A$.

A similar reasoning can be made for $(c_{i-1}, c_i)$ for all $1 < i \le 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, 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_1 > \dots > 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 > \dots > 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$. $\square$

**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 \neq c_k$, then the choice for $c_k$ is unique by Lemma 1.3.5 and then for $1 \le i \le 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. $\square$

1.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-path $c > c_1 > \cdots > c_k \ge 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 (1) and (2) of Theorem 1.3.9.

We first prove that $[T, T + A]$ satisfies Condition (1). 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 $\#_{T_1}(c, b) = \#_{T_1}(c, a) = v$. We now use Lemma 1.3.27 on $c > b > a$ and the ascent-path $c > c_1 > \cdots > c_k \ge 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 > \cdots > 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 > \cdots > 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 > \cdots > 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 tree-ascent. 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. $\square$

1.3.4.3. *Proof of Theorems 1.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. $\square$

*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) \in A$ if and only if $(c, a)$ is a minimal essential variation. $\square$
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$.

**Proposition 1.3.33 (Middle variation properties).** Let $[T, T+A]$ be a pure interval and $c > b > a$. The following properties hold.

(1) If $(c, a)_v$ is a variation, and $\#_T(c, b) = v$ and $\#_T(b, a) < s(b)$, then $(c, b)_v$ is a variation.

(2) If $(c, a)_v$ is a variation and $a$ is a middle descendant of $b$, then $(c, b)_v$ is a variation.

(3) If $(c, a)_v$ is an essential variation, then $a$ is not a middle descendant of $b$.

(4) If $(c, a)_v$ is an essential variation and $(b, a)_w$ is a variation, then $(b, a)_w$ and $(c, b)_v$ are essential variations.

(5) If $(c, b)_v$ is a variation with $s(b) > 0$ and $\#_T(b, a) = s(b)$ and $\#_T(c, a) = v$, then there exists $b'$ with $c > b' > b$ and $a$ is a middle descendant of $b'$ and $(c, b')$ a variation.

(6) If $(c, a)_v$ is an essential variation and $(c, b)_v$ is a variation, then $\#_T(b, a) = 0$.

(7) If $(c, a)_v$ is a variation and $\#_T(c, b) = v$ and $\#_T(b, a) = 0$ and $s(b) > 0$, then either $(b, a)$ is a variation or there is $b'$ with $c > b' > b$ with $b$ a middle descendant of $b'$ and $(c, b')_v$ a variation.

(8) If $(c, a)_v$ is a variation and $(c, b)_v$ is an essential variation with $s(b) > 0$ and $\#_T(b, a) = 0$ then $(b, a)$ is a variation.

*Proof.* Property (1) is Lemma 1.3.16. It is also a consequence of Lemma 1.3.27. This implies Property (2): if $a$ is a middle descendant of $b$, then $\#_T(c, b) = v$ and $\#_T(b, a) < s(b)$. Then Property (3) is a consequence of (2): if $(c, b)$ varies and $a$ is a middle descendant of $b$, then $(c, a)$ is not an essential variation. Property 4 is Lemma 1.3.14 with the addition that $(b, a)$ is also an essential variation which is a consequence in particular of 1.

We prove Property (5). Suppose that we have $(c, b)_v$ a variation, $s(b) > 0$, $\#_T(b, a) = s(b)$ and $a$ is never a middle descendant of any $b'$ with $c > b' > b$ such that $(c, b')$ varies. We prove that it implies $\#_T(c, a) > v$. We look at the ascent-path $c = c_0 > c_1 > \cdots > c_k \ge b$ between $c$ and $b$. Either $c_k = b$ and by hypothesis $\#_T(c_k, a) = s(c_k) > 0$. Or $b$ is middle descendant of $c_k$ and as we have $\#_T(b, a) = s(b) > 0$, we get by transitivity $\#_T(c_k, a) \ge \#_T(c_k, b) > 0$. As $(c, c_k)$ varies, by hypothesis $a$ cannot be a middle descendant of $c_k$, so this gives again $\#_T(c_k, a) = s(c_k) > 0$. As we have an ascent-path, $(c_k, c_{k-1})$ is a tree-ascent. Using Statement (iv) of Proposition 1.1.8, we obtain $\#_T(c_{k-1}, a) > \#_T(c_{k-1}, c_k)$. Either $c_{k-1} = c$ and we are done, or as $a$ cannot be a middle descendant of $c_{k-1}$, we get $\#_T(c_{k-1}, a) = s(c_{k-1})$. And $s(c_{k-1}) > 0$ because $(c_{k-1}, c_k)$ varies. Besides, $(c_{k-1}, c_{k-2})$ is a tree-ascent so we apply the same reasoning until we reach $c_0 = c$. This implies Property (6). Indeed, $(c, a)_v$ is an essential variation so $a$ cannot be a middle descendant of $b$ (Property (3)) so either $\#_T(b, a) = s(0)$ or $\#_T(b, a) = s(b)$. But in this last case, Property (5) tells us that $a$ is a middle descendant of $b'$ which is forbidden.

Property (7) is a direct consequence of Lemma 1.3.27. As $s(b) > 0$ and $\#_T(b, a) = 0$, only cases (i) and (ii) are possible. In case (i), $b = c_i$ for $c_i$ an element of the variation path. If $i < k$, then $(b, a)$ varies as in Remark 1.3.26. If $i = k$, then $a$ is a middle descendant of $b$ and so $\#_T(b, a) > 0$. In case (ii), we have that $b$ is a middle descendant of some other node as described in the property. This implies Property (8): as $(c, b)$ is an essential variation, $b$ cannot be a middle descendant of any $b'$ and then we have that $(b, a)$ is a variation. $\square$

## 1.4. INTERSECTION OF PURE INTERVALS

1.4.1. **The Intersection Theorem.** The goal is to prove the following theorem.

**Theorem 1.4.1.** The intersection of two pure intervals is a pure interval.

**Example 1.4.2.** Figure 1 shows all the pure intervals for the s-weak lattice with $s = (0, 2, 2)$. The lattice is drawn such that each pure interval corresponds to a cell. The dimension of the cell is the number of
<figure><img src="image_18.png" /><figcaption>FIGURE 15. Example of intersections of pure intervals for $s = (0, 2, 2)$</figcaption></figure>

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 \cap I_2 \neq \emptyset$ if and only if $x_1 \vee x_2 \leq y_1 \wedge y_2$, and in this case we have $I_1 \cap I_2 = [x_1 \vee x_2, y_1 \wedge y_2]$.

*Proof.* Suppose that $I_1 \cap I_2 \neq \emptyset$, then there is $x \in I_1 \cap I_2$. We have $x_1 \leq x$ and $x_2 \leq x$, which implies $x_1 \vee x_2 \leq x$. Similarly, $x \leq y_1 \wedge y_2$. We obtain $x_1 \vee x_2 \leq x \leq y_1 \wedge y_2$, i.e., $I_1 \cap I_2 \subseteq [x_1 \vee x_2, y_1 \wedge y_2]$.

Now suppose $x_1 \vee x_2 \leq y_1 \wedge y_2$ and take $x \in [x_1 \vee x_2, y_1 \wedge y_2]$. By definition, we have $x_1 \leq x_1 \vee x_2 \leq x \leq y_1 \wedge y_2 \leq y_1$, so $x \in I_1$. Similarly, $x \in I_2$. This gives $I_1 \cap I_2 \neq \emptyset$ and $[x_1 \vee x_2, y_1 \wedge y_2] \subseteq I_1 \cap I_2$. $\square$

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.

**Lemma 1.4.4 (intersection stability).** Let $[T, T+A]$ and $[T', T' + A]$ be two pure intervals with a non-empty intersection. Let $X = T \vee 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 \in [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) = v + 1$. Let $S = \text{inv}(T) \cup \text{inv}(T')$ such that $\text{inv}(X) = S^{\text{tc}}$. There is a transitivity path in $S$

$$b = b_1 > \dots > 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 \neq a$. If either $\#_T(b_1, b_3) = v + 1$ or $\#_{T'}(b_1, b_3) = v + 1$, 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|$.
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

$$ (7) \qquad \#_T(b, b_2) = v + 1 $$

$$ (8) \qquad \#_T(b_2, a) = 0 $$

$$ (9) \qquad \#_{T'}(b, b_2) = v $$

$$ (10) \qquad \#_{T'}(b_2, a) = 1. $$

We have $X \in [T, T + A]$ and $\#_X(b_2, a) = 1 > \#_T(b_2, 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. $\square$

**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 \lor T'$ and $Y = (T + A) \land (T' + A')$, then

$$ (11) \qquad \mathrm{Var}([X, Y]) = \mathrm{Var}([T, T + A]) \cap \mathrm{Var}([T', T' + A']) $$

Note that the intersection is taken considering variations with their values, i.e., $(b, a)_v \in \mathrm{Var}([T, T + A]) \cap \mathrm{Var}([T', T' + A'])$ if and only if $(b, a)_v \in \mathrm{Var}([T, T + A])$ and $(b, a)_v \in \mathrm{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 $\mathrm{inv}(T)$. By definition, $\mathrm{inv}(T) \subseteq \mathrm{inv}(T+A)$. Besides, as the intersection is non-empty, $T \preceq T' + A'$ which means $\mathrm{inv}(T) \subseteq \mathrm{inv}(T' + A')$. We also have $\#_{T+A}(b, a) = \#_{T'+A'}(b, a) = v + 1 = \#_S(b, a)$ and this gives us $S \subseteq \mathrm{inv}(T + A)$ and $S \subseteq \mathrm{inv}(T' + A')$. As $Y = (T + A) \land (T' + A')$, this gives that $S \subseteq \mathrm{inv}(Y)$ and so $\#_Y(b, a) \ge 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 \le X \le Y \le T + A$, this implies that $\#_X(b, a) = \#_Y(b, a) = v$ and $(b, a)$ is not a variation of $[X, Y]$. $\square$

**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.

We present two examples also computed in our SageMath demo worksheet [Pon23b].

**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).
<figure><img src="image_19.png" /><figcaption>FIGURE 16. Example of an intersection of pure intervals in size 10</figcaption></figure>

**1.4.3. Essential variations of the intersection.** 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.

**Definition 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.

**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.
**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) \ge \#_{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 compat-
ible 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)_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) \le \#_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 \le \#_T(b, a) \le 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)$. $\square$

**Remark 1.4.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 $[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 \neq 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 $\#_{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') \le \#_T(b, a)$. 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')$. $\square$

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.
We start with Condition (1). We take $c > b > a$ such that $(c, a)_v$ and $(b, a)_w$ are variations of $[X, Y]$. By Proposition 1.4.5, the variations of $[X, Y]$ are the intersection of the variations of $[T, T + A]$ and $[T', T' + A']$. So $(c, a)_v$ and $(b, a)_w$ are variations in both $[T, T + A]$ and $[T', T + A']$. These are pure intervals which implies that $(c, b)_v$ is a variation in both. By Proposition 1.4.5, $(c, b)_v$ is a variation of $[X, Y]$.

We now prove Condition (2). We take $c > b > a$ such that $(c, a)_v$ and $(c, b)_v$ are essential variations of $[X, Y]$ and suppose $s(b) \neq 0$. By Proposition 1.4.9, $(c, a)_v$ and $(c, b)_v$ are compatible variations of $[T, T + A]$ and $[T', T' + A']$. We need to show that $(b, a)_0$ is a variation of $[X, Y]$, i.e., that it is a variation in both $[T, T + A]$ and $[T', T' + A']$.

Let us first prove that $\#_T(b, a) = \#_{T'}(b, a) = 0$. We have proved in Proposition 1.4.12 that $(c, a)_v$ is an essential variation of at least one of the intervals. Without loss of generality, we suppose that $(c, a)_v$ is an essential variation of $[T, T + A]$. Using Statement (6) of Proposition 1.3.33, we obtain that $\#_T(b, a) = 0$. Suppose that $\#_{T'}(b, a) > 0$. If $a$ is a middle descendant of $b$, then as $(c, a)_v$ is compatible, this means $\#_T(b, a) = s(b)$ which contradicts our previous conclusion that $\#_T(b, a) = 0 < s(b)$. So $\#_{T'}(b, a) = s(b)$. We use Statement (5) of Proposition 1.3.33: $a$ is a middle descendant of some $b'$ in $T'$ with $c > b' > b$. We choose $b'$ to be minimal so that $a$ is not a middle descendant of any other node of value between $b$ and $b'$. As $\#_{T'}(b, a) = s(b)$, we have $\#_{T'}(b', b) \leq \#_{T'}(b', a) < s(b')$. As $(c, a)$ is a compatible variation, in $T$ we have $\#_T(b', a) = s(b')$ and as $\#_T(b, a) = 0$ this gives $\#_T(b', b) \geq \#_T(b', a) = s(b')$. So $(b', b)$ is a variation of $[T', T' + A']$ as well as $(b', a)$. We can apply again Statement (5) on $b' > b > a$ which contradicts the minimality of $b'$.

We prove now that $(b, a)$ varies in $[T, T + A]$. If $(c, b)_v$ is an essential variation, then it is the case by Statement (8) of Proposition 1.3.33. If not, then there exists $b'$ with $c > b' > b$ and $b$ is a middle descendant of $b'$ in $T$. We choose $b'$ to be minimal, so $b$ is not a middle descendant of any other node of value between $b$ and $b'$. Because $(c, a)$ is a compatible variation, this implies that $\#_{T'}(b', b) = s(b')$ and, moreover, by Proposition 1.4.12 $(c, b)_v$ is an essential variation of $[T', T' + A']$. Using Statement (8), we obtain that $(b, a)$ varies in $T'$. In particular, $a$ is a descendant of $b$ in $T'$ and $\#_{T'}(b', a) = s(b')$. In $T$, we have $\#_T(b, a) = 0$, and so $\#_T(b', a) \leq \#_T(b', b) < s(b')$. These cardinalities are higher in $T'$ so it implies that both $(b', a)$ and $(b', b)$ are variations of $[T, T + A]$ and by the +1 property, we have $\#_T(b', b) = \#_T(b', a) = s(b') - 1$. Besides, the minimality of $b'$ gives that $(b', b)$ is an essential variation and by Statement (8) of the middle variations Proposition 1.3.33 on $b' > b > a$, we obtain that $(b, a)$ varies.

In this last proof, we have not made any assumptions on the variations of $[T, T + A]$ beside being compatible, especially we have not assumed that $(c, a)$ was an essential variation. So the proof applies in the same way to $[T', T' + A']$ and $(b, a)_0$ is also a variation of $[T', T' + A']$. This gives that $(b, a)_0$ is indeed a variation of $[X, Y]$. $\square$

**Corollary 1.4.13.** Let $[T, T + A]$ and $[T', T' + A']$ be two pure intervals with non-empty intersection. Then their intersection is the pure interval $[T'', T'' + A'']$ where $T'' = T \lor T'$ and $A''$ is the set of couples $(a, c)$ such that $(c, a)$ is a minimal compatible variation of the two intervals, i.e., there is no $b$ with $a < b < c$ such that $(b, a)$ is a compatible variation.

*Proof.* This is a consequence of Proposition 1.3.12 and Proposition 1.4.9. $\square$

# Part 2. The s-associahedron

## 2.1. THE s-TAMARI LATTICE (BACKGROUND)

We recall the definition of the s-Tamari lattice and its connection with the $\nu$-Tamari lattice of Préville-Ratelle and Viennot, as shown in [CP22]. We refer to [CP22] for more detailed explanations.

### 2.1.1. The s-Tamari lattice.

**Definition 2.1.1.** An s-decreasing tree $T$ is called an *s-Tamari tree* if for any $a < b < c$ the number of $(c, a)$ inversions is less than or equal to the number of $(c, b)$ inversions:

$$ \#_T(c, a) \leq \#_T(c, b). $$
In terms of the tree this means that the node labels in $T_i^c$ are smaller than all the labels in $T_j^c$ for $i < j$. The multi set of inversions of an s-Tamari tree is called an *s-Tamari inversion set*.

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 [CP22, Lemma 2.23] that if $(a, c)$ is a Tamari-ascent of $T$ then by increasing the cardinality of $(c, a)$ by one in $\text{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 $\nu$-Tamari lattice.** The $\nu$-Tamari lattice is another lattice structure introduced in [PRV17], which can be defined in terms of a family of combinatorial object called $\nu$-trees [CPS20].

Let $\nu$ 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_\nu$ the set of lattice points weakly above $\nu$ inside the smallest rectangle containing $\nu$. We say that two points $p, q \in A_\nu$ are $\nu$-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 $\nu$. Otherwise, we say that $p$ and $q$ are $\nu$-compatible.

**Definition 2.1.6.** A $\nu$-tree is a maximal collection of pairwise $\nu$-compatible elements in $A_\nu$.

Although $\nu$-trees are just sets of lattice points above $\nu$, 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 [CPS20]. The result is a planar binary tree with a root at the top left corner of $A_\nu$.

Let $\mathcal{T}$ be a $\nu$-tree and $p, r \in \mathcal{T}$ be two elements which do not lie in the same row or same column. We denote by $p\square r$ the smallest rectangle containing $p$ and $r$, and write $p\llcorner r$ (resp. $p\lceil r$) for the lower left corner (resp. upper right corner) of $p\square r$.

Let $p, q, r \in \mathcal{T}$ be such that $q = p\llcorner r$ and no other elements in $\mathcal{T}$ besides $p, q, r$ lie in $p\square r$. The node $q$ is called a $\nu$-ascent of $T$, and the $\nu$-tree rotation of $\mathcal{T}$ at $q$ is defined as the set $\mathcal{T}' = (\mathcal{T} \setminus \{q\}) \cup \{q'\}$, where $q' = p\lceil r$. As shown in [CPS20, Lemma 2.10], the rotation of a $\nu$-tree is also a $\nu$-tree.

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

An example of this lattice for $\nu = \text{NEENEEN}$ is shown on the right of Figure 17.

2.1.3. **The *s*-Tamari lattice and the *$\nu$*-Tamari lattice are isomorphic.** Let $s = (s(1), \dots, s(n))$ be a weak composition and $\nu(s)$ be the lattice path $\nu(s) := NE^{s(1)} \dots NE^{s(n)}$. We denote by $\leftarrow_S^s$ the reversed sequence $(s(n), \dots, s(2), s(1))$. In [CP22], we showed that the *s*-Tamari lattice and the $\nu(\leftarrow_S^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, \dots, n$, such that a node $x$ has label $i$ if the number of internal nodes traversed strikty before $x$ is equal to $i$. We denote by $\phi(T)$ the unique $\nu$-tree containing as many nodes at height $i$ as there are nodes in $T$ with label $i$. Such $\nu$-tree can be uniquely constructed using the right flushing algorithm
from [CPS20]: 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.

<figure><img src="image_20.png" /><figcaption>FIGURE 17. Bijection between the $s$-Tamari lattice and the $\nu(\overleftarrow{s})$-Tamari lattice for $s = (0, 2, 2)$. (Figure 16 of [CP22])</figcaption></figure>

**Proposition 2.1.8 ([CP22, Corollary 2.34]).** The map $\varphi$ is an isomorphism between the $s$-Tamari lattice and the $\nu(\overleftarrow{s})$-Tamari lattice.

## 2.2. THE $s$-ASSOCIAHEDRON

In this section we extend the $s$-Tamari lattice to a full polyhedral complex that we call the $s$-associahedron, and show that it coincides with the $\nu$-associahedron introduced by Ceballos, Padrol, and Sarmiento in [CPS19].

**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) \in A$ by one and then taking the transitive closure.

**Definition 2.2.1.** Let $T_1 \subsetneq 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 and 19.

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 Tamari-ascents of $T_1$. Then $T_2$ can be obtained as the join $T_2 = \bigcup_{a \in A} (T_1 + a)$ over all $s$-Tamari trees $T_1 + a$ obtained from $T_1$ by rotating a Tamari-ascent $a \in 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
<figure><img src="image_21.png" /><figcaption>FIGURE 18. Examples of 2-dimensional pure s-Tamari intervals.</figcaption></figure>

inversion and take the transitive closure. Besides, as s-Tamari is a sublattice of the s-weak order, the definition of the join is the same as in the s-weak order (by union and transitive closure of tree-inversions). Then all the arguments for proving Lemma 1.2.2 still work. □

**Definition 2.2.3** (The s-associahedron). The s-associahedron Asso(s) is the collection of pure s-Tamari intervals $[T, T + A]$. Here, T denotes an s-Tamari tree and A a subset of Tamari-ascents of T. The dimension of $[T, T + A]$ is said to be equal to $|A|$. In particular,

(1) the vertices of Asso(s) are s-Tamari trees T, and

(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

$$\sum_{T} (1 + t)^{\mathrm{tasc}(T)},$$

where the sum ranges over all s-Tamari trees T and tasc(T) denotes the number of s-Tamari ascents of T.
<figure><img src="image_22.png" /><figcaption>FIGURE 19. Example of a 3-dimensional pure s-Tamari interval.</figcaption></figure>

*Proof.* The proof is exactly the same as the proof of Proposition 1.2.4. Let

$$ \sum_{T} (1+t)^{\tanh(T)} = f_0 + f_1 t + f_2 t^2 + \dots $$

where the sum runs over all s-Tamari trees T. We need to show that $f_k$ counts the number of k-dimensional faces of $\text{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)^{\tanh(T)}$. $\square$

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 $\sum_{T} t^{\tanh(T)}$ may be regarded as s-generalizations of the Narayana numbers. The *s-Narayana number* $\text{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 [CGD19] in this general set up, and in [ARW13] for the special case of signatures arising in rational Catalan combinatorics.

2.2.2. **The $\nu$-associahedron.** In [CPS19], Ceballos, Padrol and Sarmiento proved that the Hasse diagram of the $\nu$-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 $\nu$-associahedron and gave
a complete characterization of its faces in terms of certain combinatorial objects called “covering $(I, \bar{J})$-forrests”, see [CPS19, Definition 5.1 and Theorem 5.2]. We present here an equivalent description of their $\nu$-associahedron phrased in terms of $\nu$-trees, which is more convenient for our purposes.

Let $\nu$ be a lattice path consisting of north an east unit steps. Recall that a $\nu$-tree is a maximal $\nu$-compatible collection of elements in $A_\nu$ (lattice points weakly above $\nu$), and that the $\nu$-Tamari lattice is the lattice of $\nu$-trees whose covering relation is given by $\nu$-Tamari rotations. This lattice was extended to a full simplicial complex in [CPS19] called the *$\nu$-Tamari complex*. Its faces, which we call *$\nu$-faces*, are $\nu$-compatible collections of elements in $A_\nu$ ordered by inclusion [CPS20]. A $\nu$-face $\mathcal{F}$ is said to be *covering* if it contains the root (top left corner in $A_\nu$) and at least one point in each row and each column. The covering $\nu$-faces are exactly the interior faces of the $\nu$-Tamari complex, see [CPS19, Lemma 4.3].

**Definition 2.2.5.** The *$\nu$-associahedron* Asso($\nu$) is the polyhedral complex of interior faces of the $\nu$-Tamari complex, ordered by reversed inclusion. Equivalently, Asso($\nu$) is the polyhedral complex of covering $\nu$-faces, ordered by reversed inclusion. The *dimension of a covering $\nu$-face* $\mathcal{F}$ is $\ell(\nu) + 1 - |\mathcal{F}|$, where $\ell(\nu)$ is the length of $\nu$. In particular,

(1) the vertices of Asso($\nu$) are $\nu$-trees, and

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

An example of the $\nu$-associahedron for $\nu = \text{NEENEEN}$ 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.

<figure><img src="image_23.png" /><figcaption>FIGURE 20. The $\nu$-associahedron for $\nu = \text{NEENEEN}$.</figcaption></figure>

Before matching the definitions of $s$-associahedra and $\nu$-associahedra we need the following results.

**Lemma 2.2.6.** Covering $\nu$-faces $\mathcal{F}$ are in bijection with pairs $(\mathcal{T}, \mathcal{A})$ such that $\mathcal{T}$ is a $\nu$-tree and $\mathcal{A}$ is a (possibly empty) subset of $\nu$-ascents of $\mathcal{T}$. The bijection is determined by $\mathcal{F} = \mathcal{T} \setminus \mathcal{A}$ and $\dim(\mathcal{F}) = |\mathcal{A}|$.

*Proof.* If $\mathcal{T}$ is a $\nu$-tree and $a$ is a $\nu$-ascent of $\mathcal{T}$, then the $\nu$-face $\mathcal{T} \setminus \{a\}$ is contained in two facets ($\mathcal{T}$ and the rotation of $\mathcal{T}$ at $a$). Therefore, $\mathcal{T} \setminus \{a\}$ is an interior face of the $\nu$-Tamari complex. Similarly, if $\mathcal{A}$
is a subset of $\nu$-ascents of $T$, the $\nu$-face $T \setminus A$ is also an interior face. Thus, $\mathcal{F} = T \setminus A$ is a covering $\nu$-face. By definition, its dimension is equal to $\dim(\mathcal{F}) = \ell(\nu) + 1 - |T \setminus A| = \ell(\nu) + 1 - |T| + |A| = |A|$.

It remains to show that every covering $\nu$-face $\mathcal{F}$ can be written uniquely as $\mathcal{F} = T \setminus A$ for some $\nu$-tree $T$ and a subset $A$ of $\nu$-ascents of $T$. We prove this using the connection between $\nu$-Tamari lattices and subword complexes presented in [CPS20].

Let $\mathcal{F}$ be a covering $\nu$-face. By [CPS20, Theorem 5.5], the $\nu$-Tamari lattice is the increasing flip graph of a suitably chosen subword complex $\mathcal{SC}(Q_{\nu}, \pi_{\nu})$. It is not required to understand subword complexes in this proof, but to know that under this correspondence, $\nu$-trees correspond to facets of the subword complex and $\nu$-rotations to increasing flips. The link of a face in a subword complex is also a subword complex itself, see e.g. [KM04]. Therefore, the restriction of the $\nu$-Tamari lattice to the set of $\nu$-trees containing $\mathcal{F}$ is the increasing flip graph of another suitable subword complex $\mathcal{SC}(Q_{\mathcal{F},\nu}, \pi_{\nu})$. 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 $\nu$-tree $\mathcal{T}_{\mathcal{F}}^{\min}$ (resp. $\mathcal{T}_{\mathcal{F}}^{\max}$) containing $\mathcal{F}$ such that every “flippable” element of $\mathcal{T}_{\mathcal{F}}^{\min}$ (resp. $\mathcal{T}_{\mathcal{F}}^{\max}$) that is not in $\mathcal{F}$ is “increasingly flippable” (resp. “decreasingly flippable”), that is a $\nu$-ascent (resp. “$\nu$-descent”). Moreover, since $\mathcal{F}$ is an interior face, then every element of $A = \mathcal{T}_{\mathcal{F}}^{\min} \setminus \mathcal{F}$ is flippable. Thus, $A$ is a subset of $\nu$-ascents of $\mathcal{T}_{\mathcal{F}}^{\min}$. Since $\mathcal{F} = \mathcal{T}_{\mathcal{F}}^{\min} \setminus A$, this finishes our proof. $\square$

For $a \in A$ we denote by $T_a$ the $\nu$-tree obtained from $T$ by applying a $\nu$-Tamari rotation at the $\nu$-ascent $a$, and by $T + A$ the join of the set $\{T_a : a \in A\}$. The interval $[T, T + A]$ of the $\nu$-Tamari lattice is called a *pure $\nu$-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 $\nu = \nu(\frac{1}{s})$, we know by Proposition 2.1.8 and Lemma 2.2.2 that pure $s$-Tamari intervals are mapped to pure $\nu$-Tamari intervals under the bijection $\varphi$ from Section 2.1.3. For instance, the pure $s$-Tamari interval in Figure 19 is mapped to the pure $\nu$-Tamari interval in Figure 21. Moreover, the following proposition gives a nice and simple classification of pure $\nu$-Tamari intervals, as the sets of $\nu$-trees containing covering $\nu$-faces.

**Proposition 2.2.7.** Let $T$ is a $\nu$-tree and $A$ is a (possibly empty) subset of $\nu$-ascents of $T$. If $\mathcal{F} = T \setminus A$ is the corresponding covering $\nu$-face, then

$$ (12) \qquad [T, T + A] = \{\nu\text{-trees } T' : \mathcal{F} \subseteq T'\}. $$

*Proof.* Using the same subword complex techniques from the proof of Lemma 2.2.6, the set of $\nu$-trees containing $\mathcal{F}$ is in correspondence with the set of facets of the subword complex $\mathcal{SC}(Q_{\mathcal{F},\nu}, \pi_{\nu})$, and $\nu$-rotations correspond to increasing flips. As argued above, this set of facets has a unique minimal element $\mathcal{T}_{\mathcal{F}}^{\min}$ and a unique maximal element $\mathcal{T}_{\mathcal{F}}^{\max}$. Therefore,

$$ (13) \qquad [\mathcal{T}_{\mathcal{F}}^{\min}, \mathcal{T}_{\mathcal{F}}^{\max}] = \{\nu\text{-trees } T' : \mathcal{F} \subseteq T'\}. $$

By construction, we have that $T = \mathcal{T}_{\mathcal{F}}^{\min}$ and $A = T \setminus \mathcal{F}$. It remains to show that $T + A = \mathcal{T}_{\mathcal{F}}^{\max}$.

By [CPS19, Lemma 4.4 or Proposition 5.16], the interval in Equation (13) is a product of classical Tamari lattices. Its minimal element is $T$, and it contains the $\nu$-Tamari trees $T + a$ for $a \in A$ (because we rotate an element $a$ that is not in $\mathcal{F}$). Since the dimension $\dim(\mathcal{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, $\mathcal{T}_{\mathcal{F}}^{\max}$ is the join of the set $\{T_a : a \in A\}$, which is equal to $T + A$ by definition. $\square$

Figure 21 shows an example of a pure $\nu$-Tamari interval. The $\nu$-ascents $A$ of the $\nu$-tree $T$ are the circled nodes in the figure, and the covering $\nu$-face $\mathcal{F} = T \setminus A$ is the set of filled red nodes. The $\nu$-trees in the interval $[T, T + A]$ are exactly the $\nu$-trees containing these filled red nodes.

**Corollary 2.2.8.** Let $[T, T + A]$ and $[T', T' + A']$ be two pure $\nu$-Tamari intervals, and $\mathcal{F} = T \setminus A$ and $\mathcal{F}' = T' \setminus A'$ be their corresponding covering $\nu$-faces. Then $[T, T + A] \subseteq [T', T' + A']$ if and only if $\mathcal{F} \supseteq \mathcal{F}'$.
<figure><img src="image_24.png" /><figcaption>FIGURE 21. Example of a pure $\nu$-Tamari interval</figcaption></figure>

*Proof.* Assume $\mathcal{F} \supseteq \mathcal{F}'$. Since every $\nu$-tree containing $\mathcal{F}$ contains $\mathcal{F}'$, then by Equation 12 we have $[\mathcal{T}, \mathcal{T} + \mathcal{A}] \subseteq [\mathcal{T}', \mathcal{T}' + \mathcal{A}']$. This proves the backward direction.

For the forward direction, assume that $\mathcal{F} \not\supseteq \mathcal{F}'$. We aim to show that $[\mathcal{T}, \mathcal{T} + \mathcal{A}] \not\subseteq [\mathcal{T}', \mathcal{T}' + \mathcal{A}']$. Let $f' \in \mathcal{F}' \setminus \mathcal{F}$, and $\tilde{\mathcal{T}}$ be a $\nu$-tree containing $\mathcal{F}$. We consider two cases.

Case 1: $f' \notin \tilde{\mathcal{T}}$. In this case, $\tilde{\mathcal{T}}$ does not contain $\mathcal{F}'$, and so $\tilde{\mathcal{T}} \in [\mathcal{T}, \mathcal{T} + \mathcal{A}]$ but $\tilde{\mathcal{T}} \notin [\mathcal{T}', \mathcal{T}' + \mathcal{A}']$ as we wanted to show.

Case 2: $f' \in \tilde{\mathcal{T}}$. Since $\mathcal{F} \subseteq \tilde{\mathcal{T}}$ is an interior face and $f' \notin \mathcal{F}$, then $f'$ is flippable in $\tilde{\mathcal{T}}$. Flipping it, we obtain a new $\nu$-tree $\mathcal{T}^* = \tilde{\mathcal{T}} \setminus \{f'\} \cup \{f^*\}$. This new tree satisfies $\mathcal{F} \subseteq \mathcal{T}^*$ but $\mathcal{F}' \not\subseteq \mathcal{T}^*$. Thus, $\mathcal{T}^* \in [\mathcal{T}, \mathcal{T} + \mathcal{A}]$ but $\mathcal{T}^* \notin [\mathcal{T}', \mathcal{T}' + \mathcal{A}']$ as we wanted. $\square$

2.2.3. **The s-associahedron and the $\nu$-associahedron are isomorphic.** The bijection $\varphi$ between s-Tamari trees and $\nu(\overleftarrow{s})$-trees described in Section 2.1.3 extends naturally to a bijection $\bar{\varphi}$ between the faces of the s-associahedron and the faces of the $\nu(\overleftarrow{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 $(\mathcal{T}, \mathcal{A})$ of a $\nu$-tree $\mathcal{T} = \varphi(T)$ and a subsets $\mathcal{A}$ of $\nu$-assents of $\mathcal{T}$ corresponding to $A$. We denote by $\bar{\varphi}$ the map that sends the pure s-Tamari interval $[T, T + A]$ to the covering $\nu$-face $\mathcal{F} = \mathcal{T} \setminus \mathcal{A}$.

**Theorem 2.2.9.** The map $\bar{\varphi}$ is an isomorphism between Asso$(s)$ and Asso$(\nu(\overleftarrow{s}))$.
*Proof.* By Lemma 2.2.6, the map $\bar{\varphi}$ is a bijection between pure s-Tamari intervals and covering $\nu(\leftarrow s)$-faces. So, $\bar{\varphi}$ is a bijection between the faces of the s-associahedron and the faces of the $\nu(\leftarrow s)$-associahedron. We need to show that this map preserves their order relation.

Let $[T, T + A]$ and $[T', T' + A']$ be two pure s-Tamari intervals. Consider the corresponding pure $\nu$-Tamari intervals $[T, T + A]$ and $[T', T' + A']$ determined by the bijection $\varphi$, and let $\mathcal{F} = T \setminus A$ and $\mathcal{F}' = T' \setminus A'$ be the corresponding covering $\nu$-faces. Since $\varphi$ is order preserving, $[T, T + A] \subseteq [T', T' + A']$ if and only if $[T, T + A] \subseteq [T', T' + A']$. Combining this with Corollary 2.2.8, we get that $[T, T + A] \subseteq [T', T' + A']$ if and only if $\mathcal{F} \supseteq \mathcal{F}'$ as we wanted. $\square$

# Part 3. Polytopal conjectures

## 3.1. POLYTOPAL COMPLEX AND POLYTOPAL SUBDIVISION REALIZATIONS

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 [Pon23b]. 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) \qquad Z(s) = \sum_{1 \le i < j \le n} s(j) \Delta_{ij}, $$

where $\Delta_{ij} = \text{conv}\{e_i, e_j\} \subset \mathbb{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
<figure><img src="image_25.png" /><figcaption>FIGURE 22. Some geometric realizations of *s*-permutahedra in dimension 2.</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>FIGURE 23. Some geometric realizations of *s*-permutahedra in dimension 3.</figcaption></figure>
in Figures 22 and 23. You can find 3-dimensional animations of these polyhedral subdivisions and more
in this webpage [Pon23a]. Besides, all examples in dimensions 2 and 3 can be computed with **SageMath**
as shown in our demo worksheet [Pon23b].

One remarkable property of the classical permutahedron is that the classical associahedron can be
obtained from it by removing certain facets [HL07, HLT11]. We believe that if *s* contains no zeros, this
property also holds for the *s*-permutahedron and the *s*-associahedron.

**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 and 4. The 3d examples are also available on the webpage [Pon23a]. All these examples
were computed with **SageMath** and can be obtained from our demo worksheet [Pon23b].

<figure><img src="image_27.png" /><figcaption>FIGURE 24. Realizations of *s*-associahedra from *s*-permutahedra</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>FIGURE 25. The *s*-permutahedron and *s*-associahedron for *s* = (0, 0, 2). In this case, the *s*-associahedron is not convex because *s*(2) = 0.</figcaption></figure>

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 *v*-associahedra in [CPS19, Cor. 5.13], which states that
the *v*-associahedron is convex if and only if *v* does not have two non-initial consecutive north steps. In
such a case, the *v*-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 [HL07].
## 3.2. 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><img src="image_29.png" /><figcaption>FIGURE 26. A tantalizing option for s-permutahedra and s-associahedra of Coxeter type $B_2$.</figcaption></figure>

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

$$ (15) \qquad \prod_{i=1}^{n} \frac{e_i + mh + 1}{e_i + 1}, $$
<figure><img src="image_30.png" /><figcaption>FIGURE 27. The s-braid arrangement for $s = (0, 2, 3)$.</figcaption></figure>

where $h$ denotes the Coxeter number and $e_1, \dots, e_n$ are the exponents of the Coxeter group. In type $B_2$, we have $h = 4$, $e_1 = 1$ and $e_2 = 3$, so the previous formula reduces to $(2m+1)(m+1)$, which can be easily checked to count the number of vertices of the subdivided cyclohedra on the right of Figure 26. For instance, varying $m$ gives the desired sequence 6, 15, 28, 45, 66, ...

As far as we know, there are no *m-generalizations* of the $n!$ number (or equivalently, $|W|$) for other finite Coxeter groups $W$. In type $A$, if we set $s = (m, m, \dots, m)$ to be a sequence consisting of $n$ copies of $n$, then the number of elements of the $s$-weak order is the $s!$ number [CP22]

$$ (16) \qquad s! = \prod_{i=0}^{n-1} (1 + im). $$

In particular, if $m = 1$, this recovers the $n!$ number, and so may be regarded as the *m-generalization* of $n!$ in type $A$. On the other hand, the number of elements of a finite Coxeter group $W$ of rank $n$ can be computed by the uniform formula

$$ (17) \qquad |W| = \prod_{i=1}^{n} (1 + e_i). $$

The $n!$ number is recovered for type $A_{n-1}$, in which case the exponents are $e_1, \dots, e_{n-1} = 1, \dots, n-1$. It seems plausible for us, that a natural *m-generalization of $|W|$* is

$$ (18) \qquad \prod_{i=1}^{n} (1 + me_i). $$

In type $A_{n-1}$, this recovers the number of elements of the $s$-week order for $s = (m, m, \dots, m)$, expressed in Equation (16). For type $B_2$, we get the sequence $(1+m)(1+3m)$, which counts exactly the number of vertices of the Fuss-Catalan $s$-permutahedron of type $B_2$ that we are suggesting on the left of Figure 26. The first terms of this sequence are 8, 21, 40, 65, 96, ... These numbers are called octagonal numbers in [SI20, Sequence A000567]. It would be interesting to investigate if the *m-generalization of $|W|$* is the dimension of certain $W$-module in representation theory. Remarkable $S_n$-modules whose dimensions are given by $n!$ appear in [GH93, GH96, Hai01].

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.

### 3.3. 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, \dots, e_n \in \mathbb{R}^n$ are the standard basis vectors in $\mathbb{R}^n$. Let $s = (s(1), s(2), \dots, 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 = \sum_{i<j} \#_T(j, i)e_{ij} \quad \text{and} \quad F_{(T,A)} = \text{conv}\{v_{T'} : T' \in [T, T+A]\}.$$

For $n = 3$ and $s(3) \neq 0$, this gives a 2-dimensional realization of the $s$-permutahedron in the subspace $\{(x_1, x_2, x_3) \in \mathbb{R}^3 : x_1 + x_2 + x_3 = 0\} \subset \mathbb{R}^3$, see Figure 22. This realization “cuts” a polygon (a hexagon if $s_2 \neq 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 \ge 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) \neq 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 $\bar{v}_T = \sum_{i<j} (3\#_T(j, i) + f_T(j, i))e_{ij}$ where $f_T(j, i) = 0$ for $j \neq 3$ and

$$f_T(3, i) = \begin{cases} 0 & \text{if } \#_T(3, i) = 0, \\ s_3 + (\#_T(4, 1) - \#_T(4, 3)) + (\#_T(4, 2) - \#_T(4, 3)) & \text{if } 0 < \#_T(3, i) < s_3, \\ 2s_3 & \text{if } \#_T(3, i) = s_3. \end{cases}$$

See Figure 4 for examples, the demo webpage [Pon23a], or the SageMath demo worksheet [Pon23b]. We conjecture that such a construction also exists for higher dimensions.

<figure><img src="image_31.png" /><figcaption>FIGURE 28. Construction of a 3 dimensional realization.</figcaption></figure>

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 $s$-permutahedron. This works for both our 2D and 3D realizations, and is an analogue of a construction in [HL07] giving rise to Loday's realization of the associahedron. The process is illustrated in Figure 24 in 2D, see Figure 4 for 3D examples.

### 3.4. REALIZATION VIA FLOW POLYTOPES

As mentioned before, the conjectures of this paper were announced in an extended abstract of our work back in 2019 [CP19], and this is the first time where we include all the details of our constructions. 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$.

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 literally an intersection as sets, and therefore, it is very simple to compute. Exactly the same situation happens for the *v*-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.

## REFERENCES

[AL62] G.M. Adelson-Velsky and E. M. Landis. An algorithm for the organization of information. *Soviet Mathematics Doklady*, 3:1259-1263, 1962.

[ARW13] Drew Armstrong, Brendon Rhoades, and Nathan Williams. Rational associahedra and noncrossing partitions. *Electron. J. Combin.*, 20(3):Paper 54, 27, 2013.

[AS06] Marcelo Aguiar and Frank Sottile. Structure of the Loday-Ronco Hopf algebra of trees. *J. Algebra*, 295(2):473-511, 2006. doi:10.1016/j.jalgebra.2005.06.021.

[BCP22] Nantel Bergeron, Cesar Ceballos, and Vincent Pilaud. Hopf dreams and diagonal harmonics. *J. Lond. Math. Soc. (2)*, 105(3):1546-1600, 2022. doi:10.1112/jlms.12541.

[Bjö84] Anders Björner. Orderings of Coxeter groups. In *Combinatorics and Algebra*, volume 34 of *Contemporary Mathematics*, pages 175-195. American Mathematical Society, 1984.

[BMCPR13] Mireille Bousquet-Mélou, Guillaume Chapuy, and Louis-François Préville-Ratelle. The representation of the symmetric group on *m*-Tamari intervals. *Adv. Math.*, 247:309-342, 2013. doi:10.1016/j.aim.2013.07.014.

[BMFPR11] Mireille Bousquet-Mélou, Éric Fusy, and Louis-François Préville-Ratelle. The number of intervals in the *m*-Tamari lattices. *Electron. J. Combin.*, 18(2):Paper 31, 26, 2011. doi:10.37236/2027.

[BP12] F. Bergeron and L.-F. Préville-Ratelle. Higher trivariate diagonal harmonics via generalized Tamari posets. *J. Comb.*, 3(3):317-341, 2012. doi:10.4310/JOC.2012.v3.n3.a4.

[BW97] Anders Björner and Michelle L. Wachs. Shellable nonpure complexes and posets. II. *Trans. Amer. Math. Soc.*, 349(10):3945-3975, 1997. doi:10.1090/S0002-9947-97-01838-2.

[CGD19] Cesar Ceballos and Rafael S. González D'León. Signature Catalan combinatorics. *Journal of Combinatorics*, 10(4):725-773, 2019. doi:https://doi.org/10.4310/JOC.2019.v10.n4.a6.

[CP19] C. Ceballos and V. Pons. The *s*-weak order and *s*-permutahedra. In *31th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2019)*, volume 82B, page Art. 76. Séminaire Lotharingien de Combinatoire, 2019.

[CP22] Cesar Ceballos and Viviane Pons. The *s*-weak order and *s*-permutahedra I: combinatorics and lattice structure. Preprint, arXiv:2212.11556, 2022.

[CPS19] Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento. Geometry of *v*-Tamari lattices in types *A* and *B*. *Trans. Amer. Math. Soc.*, 371(4):2575-2622, 2019. doi:10.1090/tran/7405.

[CPS20] Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento. The *v*-Tamari lattice via *v*-trees, *v*-bracket vectors, and subword complexes. *Electron. J. Combin.*, 27(1):Paper No. 1.14, 31, 2020. doi:https://doi.org/10.37236/8000.

[FZ02] Sergey Fomin and Andrei Zelevinsky. Cluster algebras. I. Foundations. *J. Amer. Math. Soc.*, 15(2):497-529 (electronic), 2002.

[FZ03] Sergey Fomin and Andrei Zelevinsky. Cluster algebras. II. Finite type classification. *Invent. Math.*, 154(1):63-121, 2003.

[GDMP$^+$23] Rafael González D'León, Alejandro H. Morales, Eva Philippe, Daniel Tamayo Jiménez, and Martha Yip. Realizing the *s*-permutahedron via flow polytopes. Preprint, arXiv:2307.03474, 2023. arXiv:2307.03474.
[GH93] Adriano M. Garsia and Mark Haiman. A graded representation model for Macdonald's polynomials. *Proceedings of the National Academy of Sciences of the United States of America*, 90(8):3607-3610, 1993. URL: http://www.ams.org/mathscinet-getitem?mr=1214091, doi:10.1073/pnas.90.8.3607.

[GH96] Adriano M. Garsia and Mark Haiman. Some natural bigraded $S_n$-Modules. *The Electronic Journal of Combinatorics*, 3(2):R24, January 1996. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r24.

[GR70] G. Th. Guilbaud and P. Rosenstiehl. Analyse Algébrique D'un Scrutin. In *Ordres. Totaux finis*, pages 71-100. De Gruyter, December 1970. doi:10.1515/9783110565911-008.

[Hai94] Mark D. Haiman. Conjectures on the quotient ring by diagonal invariants. *J. Algebraic Combin.*, 3(1):17-76, 1994. doi:10.1023/A:1022450120589.

[Hai01] Mark Haiman. Hilbert schemes, polygraphs and the Macdonald positivity conjecture. *Journal of the American Mathematical Society*, 14(4):941-1006, 2001. URL: http://www.ams.org/jams/2001-14-04/S0894-0347-01-00373-3/, doi:10.1090/S0894-0347-01-00373-3.

[HL07] Christophe Hohlweg and Carsten E. M. C. Lange. Realizations of the associahedron and cyclohedron. *Discrete Comput. Geom.*, 37(4):517-543, 2007. doi:10.1007/s00454-007-1319-6.

[HLT11] Christophe Hohlweg, Carsten E. M. C. Lange, and Hugh Thomas. Permutahedra and generalized associahedra. *Advances in Mathematics*, 226(1):608-640, January 2011. doi:10.1016/j.aim.2010.07.005.

[HNT05] F. Hivert, J.-C. Novelli, and J.-Y. Thibon. The algebra of binary search trees. *Theoret. Comput. Sci.*, 339(1):129-165, 2005. doi:10.1016/j.tcs.2005.01.012.

[Hoh12] Christophe Hohlweg. Permutahedra and Associahedra. In Folkert Müller-Hoissen, Jean Marcel Pallo, and Jim Stasheff, editors, *Associahedra, Tamari Lattices and Related Structures: Tamari Memorial Festschrift*, Progress in Mathematics, pages 129-159. Springer, Basel, 2012. doi:10.1007/978-3-0348-0405-9_8.

[KM04] Allen Knutson and Ezra Miller. Subword complexes in Coxeter groups. *Adv. Math.*, 184(1):161-176, May 2004.

[Lac22] S. Lacina. Poset Topology of s-Weak Order via SB-Labelings. *Journal of Combinatorics*, 13(3):357-395, 2022. doi:10.4310/JOC.2022.v13.n3.a3.

[LR98] Jean-Louis Loday and María O. Ronco. Hopf algebra of the planar binary trees. *Adv. Math.*, 139(2):293-309, 1998. doi:10.1006/aima.1998.1759.

[LR02] Jean-Louis Loday and María O. Ronco. Order structure on the algebra of permutations and of planar binary trees. *J. Algebraic Combin.*, 15(3):253-270, 2002. doi:10.1023/A:1015064508594.

[MHPS12] Folkert Müller-Hoissen, Jean Marcel Pallo, and Jim Stasheff, editors. *Associahedra, Tamari lattices and related structures*, volume 299 of *Progress in Mathematics*. Birkhäuser/Springer, Basel, 2012. Tamari memorial Festschrift. doi:10.1007/978-3-0348-0405-9-9.

[Pon23a] V. Pons. Many example of 3d s-permutahedra, 2023. personnal webpage. URL: https://www.lri.fr/~pons/static/spermutahedron/.

[Pon23b] V. Pons. Sagemath code and demo for s-weak order and s-permutahedra, 2023. doi:10.5281/zenodo.8380308.

[PP18] V. Pilaud and V. Pons. Permutrees. *Algebraic Combinatorics*, 1(2):173-224, 2018. doi:10.5802/alco.1.

[PRV17] Louis-François Préville-Ratelle and Xavier Viennot. The enumeration of generalized Tamari intervals. *Trans. Amer. Math. Soc.*, 369(7):5219-5239, 2017. doi:10.1090/tran/7004.

[PS13] Vincent Pilaud and Christian Stump. El-labelings and canonical spanning trees for subword complexes. In Karoly Bezdek, Antoine Deza, and Yinyu Ye, editors, *Discrete Geometry and Optimization*, volume 69 of *Fields Institute Communications Series*, pages 213-248. Springer, 2013.

[Rea06] Nathan Reading. Cambrian lattices. *Adv. Math.*, 205(2):313-353, 2006. doi:10.1016/j.aim.2005.07.010.

[SI20] Neil J. A. Sloane and The OEIS Foundation Inc. The on-line encyclopedia of integer sequences, 2020. URL: http://oeis.org/?language=english.

[Tam51] Dov Tamari. *Monoides Préordonnés et Chaînes de Malcev*. Doctorat ès-Sciences Mathématiques Thèse de Mathématique, Paris, 1951.

[The22] The Sage Developers. *SageMath, the Sage Mathematics Software System (Version 9.5)*, 2022.

(C. Ceballos) INSTITUTE OF GEOMETRY, TU GRAZ, GRAZ, AUSTRIA

Email address: cesar.ceballos@tugraz.at

URL: http://www.geometrie.tugraz.at/ceballos/

(V. Pons) CNRS, IRL CRM MONTRÉAL, CANADA – UNIVERSITÉ PARIS-SACLAY, CNRS, LABORATOIRE INTERDISCIPLINAIRE DES SCIENCES DU NUMÉRIQUE, ORSAY, FRANCE.

Email address: viviane.pons@lisl.upsaclay.fr

URL: https://www.lri.fr/~pons/