Baptiste Priez

Aladin Virmaux

Thibault Manneville

Joël Gay

Mathias Lep- Outre

Justine Falque

Julian Ritter

Camille Combe

Doriann Albertin

Noémie Cartier

Balthazar Charles

Monica Garcia

Germain Poullot

Éva Philippe

Chiara Mantovani

Clément Aram Chenevière

Dermenjian

François Bergeron

Christophe Hohlweg

Olivier Lafitte

Sakina Benhima

Claire Guerrier

Keywords: positivity

a aussi été un de ces étudiants et c'est ainsi qu'il est devenu un de mes amis les plus chers, merci à lui pour sa présence.

Lors de mon année à Montréal, j'ai été accueillie très chaleureusement par les équipes du LACIM et de L'IRL ce qui m'a permis de passer une année très riche aussi bien sur le plan personnel que scientifique. Je remercie plus particulièrement

Abstract

I present an overview of the research I have conducted for the past ten years in algebraic, bijective, enumerative, and geometric combinatorics. The two main objects I have studied are the permutahedron and the associahedron as well as the two partial orders they are related to: the weak order on permutations and the Tamari lattice. This document contains a general introduction (Chapters 1 and 2) on those objects which requires very little previous knowledge and should be accessible to non-specialist such as master students. Chapters 3 to 8 present the research I have conducted and its general context. You will find:

• a presentation of the current knowledge on Tamari interval and a precise description of the family of Tamari interval-posets which I have introduced along with the rise-contact involution to prove the symmetry of the rises and the contacts in Tamari intervals;

• my most recent results concerning q, t-enumeration of Catalan objects and Tamari intervals in relation with triangular partitions;

• the descriptions of the integer poset lattice and integer poset Hopf algebra and their relations to well known structures in algebraic combinatorics;

• the construction of the permutree lattice, the permutree Hopf algebra and permutreehedron;

• the construction of the s-weak order and s-permutahedron along with the s-Tamari lattice and s-associahedron.

Chapter 9 is dedicated to the experimental method in combinatorics research especially related to the SageMath software. Chapter 10 describes the outreach efforts I have participated in and some of my approach towards mathematical knowledge and inclusion.

Pour mon fils Octave Monnier Pons et mon "demi-fils" Ilane Bullet

Remerciements

For most of history, Anonymous was a woman.

-Virginia Woolf Tout d'abord, je souhaite remercier ma rapportrice Sylvie Corteel et mes deux rapporteurs Nathan Reading et Vic Reiner. Merci pour le temps que vous avez consacré à mon travail et pour vos rapports qui me rendent fière de ce que j'ai accompli. J'étends mes remerciements à l'ensemble de mon jury, c'est-à-dire à Mireille-Bousquet Mélou, Florent Hivert, Lionel Pournin et Maria Ronco. C'est un honneur pour moi d'avoir un jury d'une telle qualité, rassemblant des chercheurs et chercheuses de renommées mondiales et dont j'admire le travail. Je remercie aussi François Bergeron et Frédéric Chapoton qui, après avoir été mes rapporteurs de thèse il y a 10 ans, m'ont écrit les lettres de recommandations pour l'HDR. Merci aussi à Nicole Bidoit et Christine Paulin pour m'avoir accompagnée tout au long du processus.

Depuis que j'ai soutenu ma thèse en 2013 et obtenu mon poste actuel en 2014, j'ai bénéficié d'un environnement de travail d'une grande qualité grâce aux collègues, collaborateurs et collaboratrices qui m'ont entourée et soutenue. Ce sont des personnes avec qui j'ai partagé non seulement le plaisir de faire de la science mais aussi des valeurs telles que la science ouverte et inclusive, l'intégrité scientifique, la démocratisation des connaissances, etc. Je remercie ainsi chaleureusement Vincent Pilaud, mon coauteur et collaborateur de longue date avec qui j'ai aussi co-dirigé la thèse de Daniel Tamayo, Nicolas Thiéry avec qui j'ai collaboré sur le projet OpenDreamKit et les enseignements de ProgImpérative, Florent Hivert avec qui j'ai co-dirigé la thèse de Hugo Mlodecki et qui parraine mon habilitation, et Cesar Ceballos, mon coauteur et qui mène avec moi le projet PAGCAP. J'étends ces remerciements à l'ensemble de l'équipe GALaC du LISN ainsi qu'à l'équipe Combi du LIX que j'ai pu croisée en particulier lors de notre séminaire commun et enfin aux membres du projet PAGCAP. J'en profite aussi pour remercier mon tout premier coauteur, Grégory Châtel, qui sera content de voir que nos intervallesposets vivent toujours ! Enfin, je remercie toutes les personnes avec qui j'ai eu des échanges professionnels et scientifiques au cours de ces 10 ans et en particulier les équipes de l'IRIF et de Marne-la-Vallée.

Comme je m'apprête à être habilitée à diriger des thèses, je voudrais remercier les 3 (ex-)doctorants qui ont déjà choisi de me faire confiance : Hugo Mlodecki qui a soutenu en 2022, Daniel Tamayo qui soutient sa thèse la même semaine que mon habilitation et Loïc Le Mogne qui entre dans sa deuxième année de doctorat. C ¸a a été (et c'est toujours) un grand plaisir de travailler avec vous et je vous souhaite beaucoup de réussite dans vos projets futurs.

CONTENTS

7.8

The permutreehedra, for all decorations δ ∈ • { , , , } 2 • . 7.9 The Schröder permutree lattices for 3 , 3 , 3 . . . . . . . . . . 7.10 Grafting two permutrees (left) and cutting a permutree (right). . .6 s-decreasing trees and s-Tamari trees for s = (0, 2, 3). On the left picture, the non s-Tamari trees are in black. . . . . . . . . . . . . 8.7 The s-permutahedron complex for s = (0, 2, 2). . . . . . . . . . . . 8.8 Example of a pure interval. On the left, the minimal tree with colored tree-ascents and on the right the corresponding interval. . 8.9 The s-associahedron complex for s = (0, 2, 2). . . . . . . . . . . . 8.10 Some realizations for s-permutahedra and s-associahedra. . . . . . 8.11 A pure interval and its corresponding ascentope . . . . . . . . . . 8.12 A pure interval of dimension 9 with the f vector of its ascentope. 9.1 Pictures of early drafts of triangular partitions and Dyck paths . . 9.2 A manual computation of q, t symmetry on intervals of ν-Tamari .

INTRODUCTION

It is impossible to be a mathematician without being a poet in soul.

-Sofia Kovalevskaya, Sónya Kovalévsky: Her Recollections of Childhood

Ten years ago, I defended my PhD thesis on "orders on permutations". I studied especially the relation between the weak order and the Tamari lattice. My approach was mostly combinatorial. The weak order is a partial order on permutations known as the "bubble sort order". The minimal element is the identity permutation 1 . . . n while the maximal element is n(n-1) . . . 1. Each cover relation switches two values in consecutive positions. In particular, any descending path from the maximal element to the identity defines a sorting network corresponding to a specific implementation of the bubble sort algorithm (see Section 1.2 for more details).

The Tamari lattice [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF] is a partial order that can be defined especially on binary trees or on any objects counted by the Catalan numbers. The cover relation is the well known binary tree rotation used in particular in sorting algorithms to balance binary trees [START_REF] Adelson-Velsky | An algorithm for the organization of information[END_REF]. As I explain in Chapter 2, it is a quotient lattice of the weak order. The construction uses the binary search tree insertion: each binary tree is associated with an interval of permutations which corresponds to a lattice congruence class.

The combinatorial relation between the weak order and the Tamari lattice extends to geometry and algebra. The Hasse diagram of the weak order is the skeleton of a polytope, the permutahedron, which can be constructed as the convex hull of the permutations of size n seen as points in N n . Similarly, the Tamari lattice corresponds to the associahedron. This polytope was described originally by Tamari himself in his thesis [START_REF] Tamari | Monoides Préordonnés et Chaînes de Malcev[END_REF] and later independently by Stasheff [START_REF] Stasheff | Homotopy associativity of H-spaces. I, II[END_REF]. Nowadays, many realizations are known [START_REF] Loday | Realization of the Stasheff polytope[END_REF][START_REF] Hohlweg | Permutahedra and generalized associahedra[END_REF] and it has become a major object in discrete geometry and combinatorics [START_REF] Pilaud | Celebrating Loday's Associahedron[END_REF].

In Section 2.5, I explain how the combinatorial construction of the congruence classes also translate into a geometrical one by "removing" faces of permutahedron to obtain the associahedron. Besides, in Sections 1.5 and 2.7, I show the connection between the combinatorial aspects and some Hopf algebraic structures on permutations and binary trees [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF][START_REF] Duchamp | Noncommutative symmetric functions. VI. Free quasi-symmetric functions and related algebras[END_REF][START_REF] Loday | Hopf algebra of the planar binary trees[END_REF][START_REF] Hivert | The algebra of binary search trees[END_REF].

This combinatorial, algorithmic, geometric, and algebraic correspondence has motivated my work for the past years. I have formed collaborations to deepen my understanding especially of the geometrical aspects and get a broader view of the questions at stake. Indeed, even if we can explain the correspondence in many different cases, it still amazes us and leaves many open questions. For example, partial orders structures appear when looking at the skeletons of polytopes. In some cases, this partial orders are lattices. Then, they often also correspond to algebraic structures such as Hopf algebras. But we do not yet understand what the lattice property brings to the geometric or the algebraic aspects. I do not think these questions have easy answers. They are part of the general pursuit of mathematicians and computer scientists to create connections between distant topics, a pursuit where I believe combinatorics has an essential role to play. In my work, I have tried to create some of these connections using a combinatorial and algorithmic approach. I have introduced new objects and structures to allow for new points of view: the Tamari interval-posets [CP15,[START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF], the lattice and Hopf algebra of integer posets [START_REF] Chatel | The weak order on integer posets[END_REF][START_REF] Pilaud | The Hopf algebra of integer binary relations[END_REF], the permutrees [PP18,[START_REF] Pilaud | Permutree sorting[END_REF], the s-weak order [CP19] [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF][START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF]. In this document, I present an overview of this work and I attempt to explain the context and mathematical journey that led to each of these constructions and results. I have tried to avoid technical details to keep a broader view and show the ideas behind the objects, especially through examples. Each chapter ends with some open questions and perspectives. Besides, some chapters are completed by SageMath worksheets with computed examples [START_REF] Pons | HDR-notebooks[END_REF].

Part I: Permutahedra and Associahedra

This part is here is to introduce the two main characters of this story and give the notions needed to understand my work. I have tried to make it easy to follow even for non-specialist.

Chapter 1: Permutahedra I present the permutahedron and the weak order and especially the different points of view (geometrical, combinatorial, and more) through which I have studied them.

Chapter 2: Associahedra I present the associahedron and the Tamari lattice in their aspects more relevant to my work: mostly through their relations with the permutahedron and the weak order.

Part II: Bijections on Tamari Intervals and More

This part presents the work I have conducted in relations to intervals of the Tamari lattice in a bijective combinatorial approach.

Chapter 3: Intervals of the Tamari Lattice I give a general overview of the state of knowledge in enumerative and bijective combinatorics on Tamari intervals, especially by listing the different families I know to be in bijection with intervals of the Tamari lattice. I present the functional equations satisfied by those families giving a general explanation on its combinatorial meaning. I then define three families of combinatorial objects, in bijection with Tamari intervals, that were introduced in my work: Tamari intervalposets [CP15], closed flows [START_REF] Chapoton | Two bijections on tamari intervals[END_REF], and grafting trees [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF]. The main result is given in Theorem 1: Tamari interval-posets are in bijection with intervals of the Tamari lattice.

Chapter 4: Statistics and Bijections on Tamari Intervals

I present the results of [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF] where I define the rise-contact involution on Tamari intervals, answering a conjecture of [START_REF] Preville-Ratelle | Combinatoire Des Espaces Coinvariants Trivariés Du Groupe Symétrique[END_REF] and [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF]. I explain how to read certain interesting statistics on Tamari intervals and show how natural involutions of Catalan objects extend in this context. The main results are given in Theorems 4 and 5 which express the properties of the rise-contact involution and its generalization to m-Tamari intervals.

Chapter 5: q, t-Catalan I present the results of [START_REF] Pons | A description of the Zeta map on Dyck paths area sequences[END_REF] and [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF] in relations to q, t-Catalan numbers. I start by giving the general background on this topic, in relation with representation theory and symmetric functions, especially its link to the enumeration of intervals of the Tamari lattice. I explain the interpretation of the ζ-function I obtained in [START_REF] Pons | A description of the Zeta map on Dyck paths area sequences[END_REF]. The main results of this chapter have been obtained in collaboration with my student Loïc Le Mogne on the q, t enumeration of triangular Dyck paths in [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF]. We have especially Theorem 7 and Conjecture 8 which express the relations between triangular q, t enumerations and certain intervals of the ν-Tamari lattices.

Part III: Quotients and Sublattices

This part explores a certain framework to understand the weak order and Tamari lattice as part of bigger structures, in particular using the technologies of subposets, sublattices and lattice quotients.

Chapter 6: Integer Posets I present the work of [START_REF] Chatel | The weak order on integer posets[END_REF] and [START_REF] Pilaud | The Hopf algebra of integer binary relations[END_REF] where we introduce a new family of objects called the integer posets. I explain how many combinatorial objects can be understood as integer posets: permutations, binary trees, binary sequences, intervals of the weak order, faces of the permutahedron and associahedron and more. Our main result is then given in Theorem 9: we can define a weak order on integer poset and it is a lattice. The classical weak order as well as the Tamari lattice are sublattices of this lattice. We also find many lattice structures like a lattice of weak order intervals or the facial order as subposets. Besides, integer posets can also be endowed with a Hopf algebraic structure and we construct new Hopf algebras using this technology as in Theorem 10.

Chapter 7: Permutrees I present the results of [PP18] and [START_REF] Pilaud | Permutree sorting[END_REF]. We study certain lattice quotients of the weak order which we call the permutree lattices. The permutrees interpolate between permutations, binary trees and binary sequences. We give their combinatorial description and many properties. In particular, we build polytopes called the permutreehedra in Theorem 11 and Hopf algebras in Theorem 12. Theorem 13 is a first step towards the characterization of permutrees in all Coxeter groups using an automaton on reduced words of the symmetric group.

Part IV: Generalizations

Chapter 8: The s-Weak Order and s-Permutahedra I present results which were initially published in [CP19] and are being fully written in [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF] and [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF]. We define the s-weak order, which is a generalization of the weak order on certain decreasing trees. This is motivated by the definition of the ν-Tamari lattices. Our main results are expressed in Theorem 14: the s-weak order is a lattice, and Theorem 15: the ν-Tamari lattice is a sublattice of the s-weak order. Besides, we obtain a certain complex, the s-permutahedron, which we believe to be a polyhedral complex. Conjecture 17 expresses that a realization as a polyhedral subdivision of the permutahedron should exists in all dimensions.

Part V: Experimental Approach

This part explores some attendant aspects of my research which I consider to be essential, especially the experimental approach of my research methodology and the general philosophy in which I conduct my work.

Chapter 9: Epistemology of the Experimental Approach I give a general overview of my research methodology using computer exploration and experimentation. This is nourished especially by the collaboration I have started with the mathematician historian and philosopher Emmylou Haffner. I explain what code I have written, why, and how I make it available for further research.

Chapter 10: Outreach I give an overview of the outreach activities I have conducted these past ten years in particular regarding experimental mathematics and support of free software and I explain what this commitment has meant for me as a scientist.

Part I Permutahedra and Associahedra

CHAPTER 1 PERMUTAHEDRA It is a narrow mind which cannot look at a subject from various points of view.

-George Eliot, Middlemarch Geometrically, the permutations of 1, . . . , n form a set of n! points in N n . This set actually lies in a hyperplane of dimension n -1 as the sum of coordinates is always n 1 i = n(n+1)

2

. Moreover, the points are in convex position and the convex hull is a polytope called the permutahedron. As an example, the images of Figure 1.1 can be obtained with SageMath using the following code. The permutahedron is a central object in my work. It has various properties connecting combinatorics, geometry and algebra. In this chapter, we recall some of these properties, highlighting the different point of views that will arise in the rest of the manuscript.

As a reflection group

The group of permutations of size n is called the Symmetric group. It is a reflection group: it is generated by a set of of geometric reflections. The permutahedron is actually the convex hull of the orbit of the identity through the reflections. The reflections are defined by the hyperplanes x i = x j for all i ̸ = j. Figure 1.2 illustrates the case of dimension 2 (n = 3). We can see that the 3 reflections corresponding to the 3 hyperplanes x 1 = x 2 , x 1 = x 3 and x 2 = x 3 . In green, we write the coordinates of the vertices of the permutahedron. In red, we write the inverse permutation of the green permutation. We will see that it is useful to keep both representations in mind. Each reflection x i = x j corresponds to a transposition (i, j) applied either on the positions of the green permutation, or on the values of the red permutation.

x1 = x3 x1 = x2 x2 = x3 (1,2,3) (1,3,2) (2,3,1) (2,1,3) (3,1,2) (3,

As a partial order and sorting networks

The skeleton of a polytope is the graph structure given by the vertices and edges of the polytope. By choosing a starting point (the identity) and orienting the edges away from the starting point, one defines a partial order, or poset, on the vertices. In the case of the permutahedron, the skeleton of the polytope actually corresponds to the Hasse diagram of the partial order, i.e., the graph of the cover relations of the poset. Recall that a cover relation in a poset is a relation x ≺ z

AS A PARTIAL ORDER AND SORTING NETWORKS

such that there is no y with x ≺ y ≺ z. The cover relations are the minimal set of relations which generate the poset through transitivity.

As there are two usual ways of labeling the vertices of the permutahedron (either using the coordinates or the inverse permutation), this defines two isomorphic partial orders on permutations known as the left and right weak order. The cover relations correspond to simple transpositions s i = (i, i+1). On the left weak order, these transpositions are applied to the left of the permutation i.e., exchanging the values i and i + 1. On the right weak order, the transpositions are applied to the right exchanging the values at positions i and i + 1. Figure 1.3 shows the left and right weak order on S 3 with s 1 in red and s 2 in blue. Figure 1.4 shows the left and right weak order on S 4 with s 1 in blue, s 2 in red, and s 3 in green. Each cover relation adds an inversion to the permutation, i.e., two values which appear in reverse order. The weak order is graded by the number of inversions, with the maximal number of inversions being n(n-1) 2 and attained in the maximal permutation n n -1 . . . 1. Moreover, we can give an alternative definition of the weak order using inclusion of inversions. For two permutations σ and τ , we define that σ ≼ τ if and only if inv(σ) ⊆ inv(τ ). The definition of inv depends on the version of the weak order we consider. In the left weak order, we use position inversions inv pos (σ) := {(i, j); i < j and σ(i) > σ(j)}. In the right weak order, which is the one we will mostly use in this manuscript, we consider value inversions inv val (σ) := {(a, b); a < b; σ -1 (b) < σ -1 (a)} (in other words, σ(b) appears before σ(a) in σ). Note that value inversions are sometimes called coinversions in the literature. We find the names position and value inversions less ambiguous especially because we work mostly with the right weak order and the value inversions.

For example, the position inversions of σ = 2314 are (1, 3) and (2, 3). It is smaller than 3412 in the left weak order as the position inversions of 3412 are (1, 3), (1, 4), (2, 3), and (2, 4). On the other hand, the value inversions of 2314 are (1, 2) and (1, 3). It is smaller in the right weak order than 2431 whose value inversions are (1, 2), (1, 3), (1, 4) and (3, 4). It is an easy exercise to show that the cover relations of the order defined by inclusion of the inversions are indeed the simple transpositions.

This also allows for an interpretation of the weak order as a sorting network. A sorting network is a series of comparisons and exchange to apply on a list of entries to sort the list. Each descending path from the maximal permutation to the identity "sorts" the permutation so each of these paths corresponds to a sorting network. They are actually sorting networks corresponding to different possible implementations of the well known (inefficient) bubble sort algorithm. The complexity O(n 2 ) of the algorithm corresponds to the height of the weak order, i.e., the maximal number of inversions n(n-1) 2 .

As a lattice

The weak order admits an extra algebraic structure: it is a lattice. A lattice can be defined as a partial order which admits two binary operations:

• the meet, written ∧, which computes the greatest lower bound of two elements x and y;

• the join, written ∨, which computes the lowest upper bound of two elements x and y.

The best way to understand this condition is to look at a counter example. Figure 1.5 shows the Hasse diagram of a poset which is not a lattice. Look for example at elements 4 and 5. We take the intersection of the ideals generated by the two

AS A LATTICE

elements, i.e., the elements of the poset which are at the same time smaller than or equal to 4 and 5. This set is {1, 2, 3} and does not have a maximal element. This poset is actually isomorphic to the Bruhat order on S 3 (or strong order) which is another well known partial order on permutations. On the contrary, the meet and join of any two elements of the weak order is well defined. This was proved in [START_REF] Th | Analyse Algébrique D'un Scrutin[END_REF] in the context of analyzing voting systems (this is also where the name permutahedron was introduced). The first step in the proof is to characterize inversion sets. This is done in [GR70, Theorem 2, page 26]: a set I of tuples (i, j) with 1 ≤ i < j ≤ n is the inversion set of a permutation if and only if I is transitive ((i, j) ∈ I and (j, k) ∈ I with i < j < k implies (i, k) ∈ I) and the complementary of I is transitive. The complementary of I is the set of tuples (i, j) with 1 ≤ i < j ≤ n which are not in I, they correspond to the non-inversions of the permutation. Inversion sets can then be used to explicitly compute the join of two permutations σ and µ. Let I σ and I µ be the respective inversion sets, then I σ ∪ I µ is not necessary transitive and so it is not an inversion set. Nevertheless, we can prove that the transitive closure of I σ ∪ I µ is an inversion set and it gives the permutation σ ∨ µ. We have not specified here if we were working with values or positions for the inversion sets: it is not necessary as the characterization and proof are the same.

As an example, in the right weak order the meet of 3214 and 3142 is 3124 and the join is 3421. Looking at values inversions, we have inv val (3214) = {(1, 2), (1, 3), (2, 3)} and inv val (3142) = {(1, 3), (2, 3), (2, 4)}. Their union {(1, 2), (1, 3), (2, 3), (2, 4)} is not a inversion set because it is not transitive. The transitive closure adds the inversion (1, 4) and is the inversion set of 3421. The left and right weak orders are implemented in SageMath and we show examples in [START_REF] Pons | HDR-notebooks[END_REF].

As a Coxeter group

Reflection groups are also part of a larger family of groups, the Coxeter groups. A Coxeter group is a group which admits a certain presentation through a finite set of generators s 1 , . . . , s n with relations (s i s j ) m i,j = 1 where m i,i = 1 and 2 ≤ m i,j ≤ ∞. Finite Coxeter Groups have been classified. The symmetric group S n corresponds to the type A n-1 . Its generators are the simple transpositions and satisfy the braid relations

s 2 i = 1; (1.1) (s i s j ) 2 = 1 if i + 1 < j; (1.2) (s i s i+1 ) 3 = 1. (1.3)
Each element of the group corresponds to an infinite set of words on the generators s i . A word is said to be reduced if it is of minimal length. For example, in S 3 , s 1 , s 3 1 , and s 1 s 2 s 1 s 1 s 2 are three words corresponding to the permutation 213 with respective lengths 1, 3, and 5, but only s 1 is reduced. We say that 213 is of length 1. The weak order can be seen as an oriented version of the Cayley graph of the Symmetric group using the Coxeter presentation. A path in the permutahedron skeleton graph corresponds to a word of generators in the group. If the path is following the weak order orientation, i.e., if it is only going up in the poset, it is a reduced word. In particular, for each element, the set of reduced words corresponds to the set of oriented paths from the identity to the element. Depending on the version of the weak order we are working with (left of right), the correspondence between paths and words changes slightly. In the right weak order, generators are added to the right of the word while going along the path, while they are added to the left in the left weak order.

For example, in Figure 1.3, we can see that on the left weak order, the permutation 312 is obtained by a path starting at 123 and going through a red edge first (s 1 ) and then a blue edge (s 2 ). As we are on the left weak order, the reduced word corresponding to 312 is s 2 s 1 . On the right weak order, the path s 1 then s 2 goes to 231. Indeed, the reduced word of 231 is s 1 s 2 , it is the inverse of 312 = s 2 s 1 . Similarly, we can read that, in both the right and left weak orders, the maximal permutation 321 has 2 reduced words: s 1 s 2 s 1 and s 2 s 1 s 2 .

The symmetric group is just one example of a finite Coxeter group. These have been classified [START_REF] Coxeter | The Complete Enumeration of Finite Groups of the Form Ri2=(RiRj)kij=1[END_REF] into 4 infinite families (A n , B n , D n , I n ) and 6 exceptional groups (E 6 , E 7 , E 8 , F 3 , H 3 , H 4 ). Other finite Coxeter groups are products of these classified families. We represent Coxeter groups through their Dynkin diagrams as in Figure 1.6. The generators s i are the vertices of the diagram. If there is no edge between two vertices i and j, then their corresponding generators s i and s j commute (m i,j = 2). Otherwise, m i,j is equal to 3 by default or to the edge label. If the diagram is disconnected, then the group is a product of the connected components. Figure 1.6 represents the possible connected diagrams of finite Coxeter groups corresponding to the classified families. In particular, as explained in [START_REF] Hohlweg | Permutahedra and Associahedra[END_REF], you can construct a group permutahedron by taking the convex hull of the orbit of a generic point. Besides, you can also define a weak order as in type A by interpreting the skeleton of the polytope as the Hasse diagram of a partial order. This order can be defined without any reference to geometry: we say that µ ≼ σ in the right (resp. left) weak order if and only if there exist a reduced word of µ which is prefix (resp. suffix) of a reduced word of σ. For example, we have 2314 ≼ 2431 (in the right weak order of type A) and indeed 2314 = s 1 s 2 is a prefix of s 1 s 2 s 3 s 2 = 2431. This order has been proved to be a lattice by Björner [Bjo84] for all finite Coxeter groups.

The work I present here mostly concerns the Symmetric group, otherwise called "type A case" in reference to the Coxeter classification. Nevertheless, to study the weak order lattice and the permutahedron, it is important to keep in mind all the aforementioned point of views, and especially this interpretation as a Coxeter group. Besides, the Coxeter approach is a strong motivation of my work. Indeed, the combinatorial work in type A often lays the ground to a more general approach through Coxeter groups. Type A offers many combinatorial tools that are only partially available in other types . Many proofs can be done in a simple elementary way relying on intuition and exploration. They open the door to what might be true for other Coxeter groups and sometimes to more generic proofs.

As a Hopf algebra

Hopf algebras are algebraic structures that have raised the interest of the combinatorial community for the past decades. They can be seen as a generalization of the classical notion of generating functions studied by Flajolet and Sedgewick [START_REF] Flajolet | Analytic Combinatorics[END_REF] in the context of algorithmic analysis. A generating function can be understood as a formal sum over an infinite combinatorial set where each object of size n is represented by a single monomial z n . The result is a power series where the coef-ficient of z n is the number of objects of size n. In that sense, generating functions are a way to encode recurrences of integer sequences into an algebraic object. Hopf algebras encode a larger class of structural inductions on combinatorial objects.

Formally, a combinatorial Hopf algebra is defined as a vector space over a set of combinatorial objects. So instead of working with polynomials or power series, we directly sum the objects themselves and work with formal linear combinations of combinatorial objects. A Hopf algebra H is a special case of a bialgebra. It is endowed with two operations: a product • : H H → H and a coproduct ∆ : H → H H. These two operations are respectively associative and coassociative and admits respectively a unit and a co-unit. Besides, the coproduct needs to be an algebra morphism. In other words, for any two elements x and y in H, then ∆(x • y) = ∆(x) • ∆(y). We don't go into details into the axioms satisfied by bialgebras and Hopf algebras as they are not completely relevant to our work. We refer the reader to [START_REF] Hivert | An Introduction to Combinatorial Hopf Algebras --Examples and realizations[END_REF] for a more comprehensive presentation.

The initial motivation for the study of Hopf algebras in combinatorics comes from the study of symmetric functions and can be traced back to MacMahon [START_REF] Alexander | Combinatory Analysis[END_REF] and later to Rota [START_REF] Joni | Coalgebras and Bialgebras in Combinatorics[END_REF]. The connection with the permutahedron comes from the Malvenuto-Reutenauer Hopf algebra on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF] which we call FQSym after [START_REF] Duchamp | Noncommutative symmetric functions. VI. Free quasi-symmetric functions and related algebras[END_REF] who redefine the algebra using the notion of polynomial realization with words. We write F σ the elements of FQSym using the basis F. The product is defined by the shifted shuffle product on permutation. We show an example below:

F 231 • F 12 = F 23145 + F 2341 + F 24315 + F 23451 + F 42315 (1.4) + F 24351 + F 42351 + F 24531 + F 42531 + F 45231 = 23145≼ R µ≼ R 45231 F µ .
(1.5)

The letters of the second permutation are shifted then the sum runs over all permutations such that the order of the small letters (here 1, 2, and 3 in red) corresponds to the first permutation and the order of the big letters (here 4 and 5) corresponds to the second permutation as in the shuffle of two decks of cards. This is actually a sum over an interval of the right weak order between the element where the letters of the second permutation are in the rightmost positions (here 23145) and the element where they are in the leftmost positions (here 45231). So, in some sense, the weak order encodes the structure of the Hopf algebra.

As FQSym is a Hopf algebra, the basis F also admits a coproduct. It actually corresponds to a product in the dual basis G. The product in G is called the convolution product on permutations and corresponds to a sum in the left weak order.

FACES OF THE PERMUTAHEDRON

G 312 • G 12 = G 31245 + G 41235 + G 41325 + G 51234 + G 42315 (1.6) + G 51324 + G 52314 + G 51423 + G 52413 + G 53412 = 31245≼ L µ≼ L 53412 G µ .
(1.7)

In the convolution product, the role of the values and positions are switched: here the orders of the letters placed in the first 3 positions is given by the first permutation 312 whereas the order of the letters in the last 2 positions is given by the second permutation 12. The basis G is isomorphic to F using the inversion of permutation just like between the right and left weak orders. This makes FQSym an auto-dual Hopf algebra whose structure is given by the weak order. Besides, the weak order can be used to define multiplicative basis hence proving that FQSym is free.

Faces of the permutahedron

The permutahedron can be defined by its vertices, the permutations, as we have seen. As a polytope, it can also be defined through a list of inequalities. For example, on the left of Figure 1.7, we cut the plane defined by x 1 + x 2 + x 3 = 6 (where the permutahedron of dimension 2 lives) into two half planes using the value of x 1 + x 2 . Looking again at Figure 1.2, it is clear that permutahedron of dimension 2 is defined by 6 such inequalities. In dimension 2, this is an easy exercise to find those inequalities. For example, we always have x 1 + x 2 = 6 -x 3 and as 1 ≤ x 3 ≤ 3, we find 3 ≤ x 1 + x 2 ≤ 5 which corresponds to the right image of Figure 1.7. In general, for the permutahedron of dimension n -1 we find 2 n -2 inequalities. They correspond to all nonempty proper subsets of [n] := {1, 2, . . . , n}. For each subset J, the corresponding inequality is given by j∈J x j ≥ |J|+1 2 [START_REF] Rado | An Inequality[END_REF]. The extremal points of the polytope are the points where some inequalities are equalities. They correspond to the faces of the polytope and are polytopes themselves. For example, in dimension 2, the permutahedron has 13 faces : 1 face of dimension 2 (the full polytope), 6 faces of dimension 1 (the 6 edges corresponding to the 6 inequalities), and 6 faces of dimension 0 (the 6 vertices, a.k.a the permutations). They are counted by the Fubini numbers [A670] and have a nice combinatorial interpretation as ordered partitions. The general idea is the following: when you are on the edge between permutation 123 and permutation 213, the order between 1 and 2 is not defined but they are both before 3, this is the ordered partition {1, 2}, {3} which we write 12|3. The dimension of the face is given by n -ℓ where ℓ is the number of parts in the ordered partitions. We illustrate this in Figure 1 This combinatorial interpretation allows for extra structures that extend the ones on permutations. For example, one can define a lattice structure, the facial weak order such that the weak order is a sublattice. It was shown in [KLN + 01] for type A and in [START_REF] Dermenjian | The facial weak order and its lattice quotients[END_REF] for all Coxeter groups. A Hopf algebra structure can also be defined on faces that extend the Malvenuto-Reutenauer one on permutations [START_REF] Chapoton | Algèbres de Hopf des permutahèdres, associahèdres et hypercubes[END_REF].

CHAPTER 2 ASSOCIAHEDRA L'algèbre n'est qu'une géométrie écrite, la géométrie n'est qu'une algèbre figurée.

-Sophie Germain, Oeuvres philosophiques.

In his thesis [START_REF] Tamari | Monoides Préordonnés et Chaînes de Malcev[END_REF] and later on in [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF], Dov Tamari introduces a certain partial order, the "associativity posets", on the different ways to parenthesize a word of a given length n. He is studying how to replace the usual associativity of a binary operation (ab)c = a(bc) by a substitution rule setting some early foundations for what is known nowadays as term rewriting systems. For example, there are 5 ways to parenthesize a word of length 4: ((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd)). In general, the number of configurations is counted by the famous Catalan numbers [A108]

C n = 1 n + 1 n 2n . (2.1)
By orienting the rewriting such that (ab)c ≺ a(bc) as shown in Figure 2.1, we obtain the partial order known as the Tamari lattice. Indeed, it was conjectured by Tamari in his thesis to be a lattice and he later gave several proofs [START_REF] Friedman | Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative[END_REF][START_REF] Huang | Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law[END_REF] with his students Friedman and Huang. According to Stasheff [Sta12], in his thesis, Tamari also describes the geometry of the lattice and gives the first known depiction of the associahedra. Just like the weak order, the Tamari lattice Hasse diagram corresponds to the oriented skeleton of a polyotpe. This polytope is the associahedron. It was also introduced independently by Stasheff [START_REF] Stasheff | Homotopy associativity of H-spaces. I, II[END_REF] about 10 years after Tamari's thesis and is sometimes known as the Stasheff polytope.

The Tamari lattice and associahedron are now major objects of interest in the combinatorics community. See for example the the collection of papers gathered in [START_REF] Müller-Hoissen | Associahedra, Tamari Lattices and Related Structures: Tamari Memorial Festschrift[END_REF] to honor the memory of Tamari and the recent survey on Loday's realization of the associahedron [START_REF] Pilaud | Celebrating Loday's Associahedron[END_REF]. The relations between the Tamari lattice and the weak order has been nourishing many of the questions I considered these last 10 years. In this chapter, I present an overview of the combinatorial,

As a sublattice

We say that a permutation σ of size n contains a pattern µ of size k ≤ n if there is a subword w of σ with |w| = k such that the relative order between the letters of w is given by µ. In other words, the standardized permutation of w is µ. For example, the permutation 4213 contains the pattern 312 because the subword 413 is such that the highest value appears first (4), then the smallest one (1), then the intermediate one (3), which corresponds to the permutation 312. In [START_REF] Knuth | The Art of Computer Programming: Volume 3: Sorting and Searching[END_REF], Knuth shows that the so-called stack sortable permutations are the permutations avoiding the pattern 231 if we read the values from left to right and 312 if we read the values from right to left. Both families are counted by the Catalan numbers. Actually, the set of permutations avoiding any pattern of size 3 is always counted by the Catalan numbers (see [START_REF] Alexander | Combinatory Analysis[END_REF] for the permutations avoiding 123 and the introduction of [START_REF] Simion | Restricted Permutations[END_REF] for a more general explanation). Now, if we select right-stack sortable permutations in the right weak order, i.e., the permutations avoiding 312, the induced partial order is actually a sublattice of the weak order.

If L is a lattice, then I ⊂ L is a sublattice if for any two elements x and y in I, then x ∧ L y and x ∨ L y are also in I. In particular, note that even if I is a lattice (using the order induced by L), it might not be a sublattice of L. See for example the subposet on Figure 2.2: it is indeed a lattice but not a sublattice of the lattice on the left because c ∧ d = b is not part of the subposet. In the case of 312-avoiding permutations, we can show that they form a sublattice of the right weak order using inversion sets as in Section 1.3. A permutation avoids 312 if for all a < c where (a, c) is a (value) inversion, then (a, b) is also a value inversion for all b with a < b < c. This property is actually stable when taking the transitive closure of the union of two inversion sets. This shows that the join of two 312 avoiding permutations is also a 312 avoiding permutation. A similar proof can be done for the meet. We thus obtain a lattice where the number of elements is given by the Catalan numbers: this is actually the Tamari lattice as we explain in Section 2.2. See the example on Figure 2

As a quotient lattice

The classical algorithm of binary search tree insertion gives another connection between the weak order and the Tamari lattice. We consider here planar rooted binary trees, which are counted by the Catalan numbers. Recursively, a binary tree is either a leaf (an empty tree) or a non-empty binary tree with a left and a right subtree. We usually do not draw the empty children and the size is given by the number of non-empty nodes. A binary tree whose non-empty nodes are labeled with numbers is said to be a binary search tree if for all nodes λ labeled by x, the nodes in the left subtree of λ are labeled with values smaller than or equal to x while the nodes on the right subtree of λ are labeled with values greater than x. This structure is used for sorting algorithms through binary search tree insertion: a number is inserted through the root and "falls down" following branches depending on its value and the label of the node (left if it is smaller, right if it is bigger) until it reaches a leaf, i.e., an empty spot. In Figure 2.4, we show the step by step binary search tree insertion of the values of a permutation (from right to left). This algorithm is used in conjunction with binary tree rotation (see Figure 2.5) in [START_REF] Adelson-Velsky | An algorithm for the organization of information[END_REF] to obtain efficient sorting algorithms. Besides, it actually defines a surjection between permutations and binary trees: the image of a permutation is the tree obtained by inserting the values from right to left. Technically, what we obtain is a labeled tree but there is only one way to label a given tree with 1, . . . , n such that it is a binary search tree. It consists of labeling the nodes in in-order, we call it a standard binary search tree.

It was shown in [START_REF] Björner | Permutation statistics and linear extensions of posets[END_REF] that the pre-image of a given binary tree is an interval in the right weak order which corresponds to the linear extensions of the standard binary search tree: all possible ways to "read" a permutation such that a node label is read before its parent. For example, the permutation 12354 is not a linear extension of the tree of Figure 2.4 because 3 appears after its parent 2. In [START_REF] Hivert | The algebra of binary search trees[END_REF], the authors call this pre-image the sylvester class of the tree (from the french word "sylvestre"), it is the transitive closure of the following rewriting rule on permutations:

. . . ac . . . b . . . ≡ . . . ca . . . b . . .

(2.2) with a < b < c.

A congruence relation on a lattice is said to be a lattice congruence if x ≡ x ′ and y ≡ y ′ implies that x ∧ y ≡ x ′ ∧ y ′ and x ∨ y ≡ x ′ ∨ y ′ . This induces a lattice structure on the congruence classes which is called a lattice quotient of L. Lattice quotients have been studied in a combinatorial context by Reading [START_REF] Reading | Lattice Congruences of the Weak Order[END_REF]. In particular, if the congruence classes are intervals and satisfy some extra orderpreserving conditions, then they form a lattice quotient. The sylvester classes satisfy the conditions and the quotient lattice we obtain is actually the Tamari lattice as illustrated on Figures 2.6 and 2.7. Classes are represented by binary trees and the cover relation is the binary tree rotation depicted on Figure 2.5. This description of the lattice is actually very close to the original one from Tamari depicted on Figure 2.1. Indeed the binary tree is just the symbolic expression tree following the associative rule of the parenthesis. In particular, the substitution rule (ab)c → a(bc) is exactly the binary tree rotation of Figure 2.5.

To connect with the previous section, note that the 312-avoiding permutations are the minimal elements of the sylvester classes (the maximal elements are the 132-avoiding permtuations). The construction by quotient means in particular that the subposet of 312 avoiding permutations is indeed the Tamari lattice. Note that it does not imply that it forms a sublattice. To conclude, a similar construction can be made on the left weak order using the bijection between permutations and decreasing binary trees (labeled binary trees where labels are strictly decreasing from root to leaves) as a surjective map between permutations and binary trees defining a lattice congruence.

Other lattice descriptions

The Tamari lattice is defined on Catalan objects. As such, there are at least as many descriptions of the lattice as there are objects counted by the Catalan numbers, which is to say a lot. For example, it is very common to see the lattice described on triangulations of a regular polygon where the cover relations is a flip of the triangulation. In my work, I often use the description in terms of Dyck paths. A Dyck path is a path formed by two types of steps, "up" and "down", such that the path starts and finishes on the x axis but never goes below. The cover relation that gives the Tamari lattice is the Dyck path Tamari rotation which consist of lifting the portion of the path following a down step (the portion is taken until the path reaches again the level of the down step). We show an example on Figure 2.8 where we also represent the Dyck path as a binary word where 1 means "up" and 0 "down". The Tamari lattices for n = 3 and 4 on Dyck paths are shown on Figure 2.9.

-→ 1101 0 11100100 1001100 -→ 1101 11100100 0 1001100

Loday's associahedron

Loday gave the first explicit realization of the associahedron such that every vertex of the Tamari lattice has integer coordinates and corresponds to an extrema of the polytope [START_REF] Loday | Realization of the Stasheff polytope[END_REF][START_REF] Pilaud | Celebrating Loday's Associahedron[END_REF]. Each tree of size n corresponds to a point (v 1 , . . . v n ) in N n where v i is equal to the product of the number of leaves in the left subtree times the number of leaves in the right subtree of the node labeled by i in the standard binary search tree labeling. We give an example on Figure 2.10 where we have made the leaves (empty trees) explicit. (1, 2, 3)

3 1 2 (2, 1, 3) 1 3 2 (3, 1, 2) 2 1 3
(1, 4, 1)

1 2 3 (3, 2, 1)
(1, 4, 1, 4, 5, 18, 1, 2)

Figure 2.10: Coordinates of binary trees in Loday's associahedron.

On the right of Figure 2.10, we show all the coordinates for the Tamari lattice on size 3. You can check that the sum of the coordinates for each point is equal to 6 like in the permutahedron. Actually, the four points on the left have permutation coordinates: the inverse permutation of their unique linear extension. They are vertices of both the associahedron and the permutahedron. This is true for all singletons: binary trees with a single linear extension. Figure 2.11 presents the associahedra of dimensions 2 and 3 drawn with SageMath, the code is available here [START_REF] Pons | HDR-notebooks[END_REF].

As a removahedron

As we have seen, certain vertices of the associahedron correspond to vertices of the permutahedron. As we show on Figure 2.12, we can actually embed the permutahedron inside the associahedron. Geometrically, this means that the list of inequalities defining the associahedron are a subset of the inequalities of the permutahedron we saw in Section 1.6. The associahedron is then a special case of removahedron as defined by Pilaud [START_REF] Pilaud | Which nestohedra are removahedra? Revista Colombiana de Matematicas[END_REF]. In dimension 2, the inequality which is "removed" is x 1 + x 3 ≥ 3 corresponding to the ordered partition 13|2. In general, all inequalities corresponding to faces where no vertex is a singleton binary tree are removed [START_REF] Hohlweg | Permutahedra and generalized associahedra[END_REF]. So faces of the associahedron are a subset of faces of the permutahedron. They also admit a combinatorial interpretation in terms of Schröder trees. A Schröder tree is a rooted planar tree such that each node has at least two children. We label the "valleys" of the tree, i.e., the gap between two subtrees, with increasing labels from left to right. This way, labeled binary Schröder trees actually correspond to binary search tree (the label of the node is the label of the unique valley underneath). They correspond to the vertices of the associahedron, i.e., faces of dimension 0. The other (non binary) trees are the faces of dimensions greater than 0. More precisely, the dimension is the number of valleys minus the number of internal nodes. Just like ordered partitions are "in between" permutations in the weak order, Schröder trees are "in between" binary trees. They correspond to partial rotations where a node is merged with its parent and not yet rotated to its right. We illustrate this on Figure 2.13.

The inequalities defining the associahedron are given by the Schröder trees with exactly two internal nodes. They correspond to certain two-parts ordered partitions (in red on Figure 2.13). Recall that any non-empty proper subset J of [n] defines a permutahedron inequality corresponding to a two-parts ordered partition. For the associahedron, we only keep the subsets that are intervals. Indeed, in dimension 2, the only subset that is not kept is {1, 3} (ordered partition 13|2). In Schröder trees, the subset J correspond to the part that is bellow the second internal node. There is no way to get a two-nodes Schroder tree with the bellow part being {1, 3}. Indeed, it would have to be bellow the label 2 but could not be to its left (because 3 > 2) nor to its right (because 1 < 2).

As a Cambrian lattice

We have seen in Section 1.4 that the weak order and the permutahedron can be defined for any Coxeter group. This is also true for the Tamari lattice, which then becomes a special case of the Cambrian lattices defined by Reading [Rea06]. There are different ways to define and understand Cambrian lattices. We can see them as a special class of quotient lattices of the weak order. Indeed, the sylvester congruence, which defines the Tamari lattice, is characterized by two initial merge as we illustrate on Figure 2.14.

A lattice congruence can be described by a list of merged edges in the Hasse diagram: two elements are in the same class if they are connected by a path of merged edges. For example, in Figure 2.14, 1342, 3142, and 3412 are in the same class. On the other hand, 3214 is alone in its class. You can check that these are the same classes as in Figure 2 These are the right sides of the two initial hexagons of the lattice. In type A, the weak order of size n always starts with n-2 hexagons which correspond to the braid relations s i s i+1 s i = s i+1 s i s i+1 . The sylvester congruence is then generated by n -2 merges: s i+1 -s i+1 s i for 1 ≤ i < n -1. For n = 4, this gives indeed the edge between s 2 = 1324 and s 2 s 1 = 3124, and the edge between s 3 = 1243 and s 3 s 2 = 1423. This easily generalizes to all finite Coxeter groups and can be encoded by an orientation of the Dynkin diagram. Indeed, each edge between i and j of the diagram is labeled with k ≥ 3 and corresponds to the relation (s i s j ) k = 1. In the weak order, it then corresponds to a polygon with 2k edges. If k is odd, one side is given by

s i -s i s j -• • • -(s i s j ) k-1 2 -(s i s j ) k-1 2 s i ,
where -represents an edge in the weak order. The other side is

s j -s j s i -• • • -(s j s i ) k-1 2 -(s j s i ) k-1 2 s j .
Then an orientation of the Dynkin diagram defines a lattice congruence by deciding which side of the polygon to merge. If the orientation is i → j, then all edges between s j s i and (s i s j ) k-1 2

(for k odd) are merged. If the orientation is i ← j, then all edges between s i s j and (s i s j )

k-1 2 are merged. For type A, the polygon is always an hexagon and there is only one edge to merge. The orientation corresponding to the sylvester congruence is written on the right of Figure 2.14. We present another Cambrian congruence for type A 3 on Figure 2 The lattices corresponding to Cambrian congruences are called the Cambrian lattices. Not only do they define some "Tamari" lattices for all Coxeter groups, they also define generalizations of the classical Tamari lattice in type A with different orientations of the Dynkin diagram. They share some of its properties. For example, their elements are always counted by the Catalan numbers: you can check that there are 14 classes on Figure 2.15. The unoriented graphs of the lattice Hasse diagram are isomorphic and they give different realizations of the associahedron [START_REF] Hohlweg | Permutahedra and generalized associahedra[END_REF].

The orientation of the Dynkin diagram somehow indicates in which order s i and s j much appear in the reduced word to avoid certain patterns. This is formalized through the system of c-sorted words described by Reading [Rea06]. Each orientation defines a Coxeter element by reading a linear extension of the oriented Dynkin diagram. For example, for the Tamari orientation of Figure 2.14, this would be c = s 1 s 2 s 3 . For the orientation of Figure 2.15, this would be c ′ = s 1 s 3 s 2 = s 3 s 1 s 2 . By taking an infinite concatenation of the Coxeter element, you get the c ∞ word, for respective previous examples,

c ∞ = s 1 s 2 s 3 |s 1 s 2 s 3 |s 1 s 2 s 3 | . . . c ′∞ = s 1 s 3 s 2 |s 1 s 3 s 2 |s 1 s 3 s 2 | . . . .
Now each reduced word can be read as a subword of c ∞ . Let us call I 1 the subset of letters used from the first copy of c, I 2 from the second copy and so on. A reduced word is said to be c-sortable if it exists as a subword of c ∞ with I 1 ⊂ I 2 ⊂ I 3 . . . . For example, s 1 s 2 s 1 = 3214 is both c-sortable and c ′ -sortable as we have (for both c and c ′ ) I 1 = {s 1 , s 2 } and I 2 = {s 1 } ⊂ I 1 . On the other hand, s 2 s 3 = 1342 is c-sortable but not c ′ -sortable. Indeed, for c ′ , we have I 1 = {s 2 } and I 2 = {s 3 }. Elements of the group which have at least one c-sortable reduced word generalize the 312-avoiding permutations for Cambrian lattices: they correspond to the minimal elements of the Cambrian congruence classes.

As a sub and quotient Hopf algebra

In [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF], Loday and Ronco describe a Hopf algebra on binary trees as a quotient Hopf algebra of the Malvenuto-Reutenauer Hopf algebra on permutations that we described in 1.5. They also note the correspondence between the Hopf algebraic relations and the geometrical relations between the permutahedron and associahedron. The Loday-Ronco Hopf algebra is studied in [START_REF] Hivert | The algebra of binary search trees[END_REF] where it is called PBT: they show how it can be constructed using sylvester classes and binary search tree insertions. Indeed, we can define a basis P indexed by binary trees as a sum over elements from the basis F of FQSym: the sum is over all linear extension of the standard binary search tree. See the example below.

P = F 2143 + F 2413 + F 4213 . (2.3)
You can check that the binary search tree insertion of Section 2.2 gives the binary tree for all three permutations. The basis P forms a sub Hopf algebra of FQSym.

As the product between two elements of F is an interval in the weak order, the product of two elements of P gives a sum over sylvester classes which is an interval of the Tamari lattice, see the example on Figure 2.16. Besides, the basis P admits a dual basis Q which forms a quotient Hopf algebra of FQSym. This is the original Loday-Ronco algebra which can be described through decreasing binary trees mimicking the relation between the left weak order and the Tamari lattice.

The cube

The associahedron can be seen as an intermediate step between the permutahedron and the cube. Indeed, the cube corresponds to the boolean lattice which is also a sublattice and a quotient lattice of both the weak order and the Tamari lattice. The cube appears as a sublattice if you take permutations avoiding both patterns 312 and 213, see Figure 2.17 for an example. In terms of quotient, the cube is given by the minimal lattice congruence obtained by merging both sides of all initial hexagons of the weak order. This congruence is actually a surjective map between permutations and binary sequences based on the recoils of the permutation. To a permutation of size n, we associate a binary sequence v 1 . . . v n-1 with v i = + if i + 1 appears after i in the permutation and v i = -otherwise (i and i + 1 form a recoil). A compatible map also exists on binary trees using the canopy of the binary tree. The congruence classes of the recoils map are then unions of sylvester classes. Besides, the cube is also a removahedron which can be constructed from the associahedron by removing more inequalities. And finally, it also corresponds to the Hopf algebra of recoils [GKL + 95] which is a sub hopf algebra of FQSym and PBT.

m-Tamari and ν-Tamari

We finish this chapter with two generalization of the Tamari lattice that we study in our work. The m-Tamari lattice appears in [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF]. It is best described on m-ballot paths: they are paths between (0, 0) and (mn, n) made of vertical and horizontal steps and which stay above the line y = x m . In particular, an m-ballot path of size n has n vertical steps and n × m horizontal steps. For m = 1, they are exactly Dyck paths (where "up" is vertical and "down" is horizontal). A rotation operation can be defined for all m which is very similar to the Dyck path rotation and also gives a lattice. See the example for m = 3 and n = 3 on Figure 2.18. Actually, by replacing every vertical step by a series of m up steps, we obtain an upper ideal of the classical Tamari lattice of size n × m.

Another way to understand m-ballot paths is to say that they are all the paths above the path represented by (10 m ) n (where 1 means vertical and 0 horizontal). In [START_REF] Préville-Ratelle | The enumeration of generalized Tamari intervals[END_REF], Préville-Ratelle and Viennot show that you can define a lattice on paths above any initial down path. This is what we call the ν-Tamari lattice (where ν represents the initial down path). The rotation is a generalization of the Dyck path rotation. At each point, we compute the number of horizontal

+ + + -+ + + -+ + + - -+ - --+ + -- --- Figure 2
.17: The boolean lattice as a sub and quotient lattice of the weak order.

steps that can be taken to the right until crossing the initial down path. This is the distance between the point and the original path. A rotation switches an horizontal step with the portion of path directly following the step, where the path is taken up to next point at a similar distance. We show an example on Figure 2.18. Just like the m-Tamari lattices, the ν-Tamari lattices can also be seen as a "piece" of a larger Tamari lattice. They also have interesting properties.

INTERVALS OF THE TAMARI LATTICE

There are times when I feel like I'm in a big forest and don't know where I'm going. But then somehow I come to the top of a hill and can see everything more clearly.

-Maryam Mirzakhani, Brillant 10, 2005.

In [START_REF] Chapoton | Sur le nombre d'intervalles dans les treillis de Tamari[END_REF], Chapoton proves that the number of intervals in the Tamari lattice satisfies a surprisingly nice formula:

I n = 2 n(n + 1) 4n + 1 n -1 = 2(4n + 1)! (n + 1)!(3n + 2)! (3.1)
where I n is the number of couples of elements x, y, in the Tamari lattice on size n, with x ≼ y. I write "nice formula" because not only is it a closed product formula, but it is almost a rather simple binomial coefficient. It suggests that a bijective proof is within reach. I write "surprisingly" because it is not at all common for combinatorial lattices to admit such a formula. For example, there is no such formula (and no hope for a product formula) for the intervals of the weak order. Similarly, other weak order lattice quotients, especially other type A Cambrian lattices do not have such a formula. We write below the first numbers of the sequence [A260],

1, 1, 3, 13, 68, 399, 2530, 16965, 118668.

(3.2)

As referenced in the OEIS, these numbers also count the number of simple, rooted, planar, triangular maps. The formula can indeed be found in [Tut62, formula 1.5]. Again, this is a surprising link between two structures that come from very different backgrounds. It turns out that these numbers are found in many different contexts. Along with my co-authors, I have introduced some objects in bijection with Tamari intervals: Tamari interval-posets [CP15], closed flows [START_REF] Chapoton | Two bijections on tamari intervals[END_REF] and grafting trees [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF]. In this chapter, I give a general overview of the current knowledge on objects counted by the Tamari interval numbers and thus place my own contributions in the global context to extract some interesting questions to explore.

Generating functions, Catalan numbers and Tamari intervals

As we have seen in Chapter 2, the number of elements in the Tamari lattice is counted by the Catalan numbers (7.3). This is probably one of the most famous sequences in combinatorics. In his book [START_REF] Stanley | Catalan Numbers[END_REF], Stanley gives 214 objects counted by the Catalan numbers. One reason to find the Catalan numbers "everywhere" is that they encode the simplest possible binary structure. Indeed, let F (z) be the generating functions of Catalan numbers,

F (z) := n≥0 C n z n , (3.3)
Where C n is equal to (7.3). Then, F satisfies the following functional equation

F (z) = 1 + zF (z) 2 . (3.4)
From there, it is immediate to find a recursive formula for C n . To find the closed product formula, one needs to solve the quadratic equation and expand the solution using Newton binomial theorem. I have actually used this several times in talks for high schoolers and general audience as it is a very nice and understandable proof mixing combinatorics and analysis. In particular, this means that all Catalan objects can be decomposed into two smaller objects just like a binary tree can be decomposed into a left and a right subtree.

The formula (3.1) looks very much like the Catalan formula. It is actually the solution of another functional equation which requires an extra parameter x. Let

ϕ(z) := n≥0 I n z n , (3.5)
where I n is (3.1). Then, ϕ(z) = Φ(z, 1) where

Φ(z, x) = 1 + zxΦ(z, x) xΦ(z, x) -Φ(z, 1) x -1 . (3.6)
We give this exact functional equation in [CP15, Theorem 3.2] and this was already proven by Chapoton in [START_REF] Chapoton | Sur le nombre d'intervalles dans les treillis de Tamari[END_REF] where he also solves it to obtain (3.1). The extra parameter is called the catalytic parameter: it is necessary to keep this extra parameter to express the functional equation. Just like the Catalan functional equation (3.4), this is quadratic, but the right part of the product is now transformed through a divided difference using the catalytic parameter.

To understand what it means in terms of combinatorics, we can compare a simple example on both Catalan objects and Tamari intervals. In the generating function of Catalan, an object of size k corresponds to a monomial z k . The product in the functional equations means that it can be combined to an object of size

n -1 -k to form a new object corresponding to a monomial z × z k × z n-1-k = z n .
In the case of Tamari intervals, two objects of respective size k and n -1 -k are represented by two monomials

x v 1 z k and x v 2 z n-1-k . But the right monomial is transformed through the divided difference into a sum z n-1-k (1+x+x 2 +• • •+x v 2 ).
It means that the combinations of two smaller objects now gives a set of v 2 + 1 objects of size n which all carry an extra parameter. One way to prove that a combinatorial family is counted by I n is then to exhibit the underlying Catalan binary decomposition and the extra catalytic parameter.

A map of maps using maps and trees

On Figure 3.1, I present an non-exhaustive landscape of objects counted by I n with their bijections. I have written in blue the objects whose definitions are directly related to the Tamari lattice itself and in red the ones coming from planar maps. The study of planar maps, i.e. graphs embed in the plane, is a field by itself which is connected to the study of the Tamari lattice through this surprising connection between Tamari intervals and triangulations (simple, rooted, planar, triangular maps). Coming from the Tamari side, my knowledge of the map aspect is limited and the landscape concentrates more on the Tamari related aspects. Besides, this landscape is restricted for now to families counted by I n thus excluding bijections on subsets of intervals or generalizations which are also numerous.

couples of Binary trees couples of Dyck paths

[Def20] [DH23] [DH23] [Pon19] [CCP14] [Com19] [Zei19] [CP15] [Tut62] [Sch90] [BB09] [PS03] [FFN23] [Pon19]
sticky trees bridgeless maps A first comment on this landscape is the great variety of objects that appear. On top of the red (maps) and blue (Tamari) ones, we see sequent calculus from the work of Noam Zeilberger [START_REF] Zeilberger | A sequent calculus for a semi-associative law[END_REF] and extended fighting fish [START_REF] Duchi | A bijection between Tamari intervals and extended fighting fish[END_REF], which represent certain branching surfaces or, equivalently, walks in the quarter plane. In Chapter 4, we explore some specific interesting statistics on intervals and see how they relate to some of these objects. Besides, this landscape concentrates on combinatorics: the I n numbers also appear in some algebraic settings which we explore in Chapter 5.

[Fan18] [Fan18] [Wor80, Fus10]
As we have said, Chapoton is the first to count Tamari intervals [START_REF] Chapoton | Sur le nombre d'intervalles dans les treillis de Tamari[END_REF]. He proves that they satisfy the functional equation (3.6) and notes the connection with maps but does not provide a direct bijection. The proof of Chapoton is based on binary trees and the catalytic parameter is the number of nodes on the left branch of the maximal tree in the interval. A bijection between triangulations and intervals is later given by Bernardi and Bonichon [BB09] using Schnyder woods or realizers: this is a way to encode a triangulation with three intertwined planar trees. The bijection uses Dyck paths. A triangulation can be represented by multiple set of realizers: Tamari intervals then correspond to minimal realizers while general realizers correspond to couples of Dyck paths (P, Q) where P is below Q.

The functional equation can also be expressed in terms of Dyck paths. The catalytic parameter then corresponds to some statistic of the lower Dyck path called the number of contacts. This is what is done in [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] where the authors solve a more a general functional equation corresponding to intervals in the m-Tamari lattices. We discuss it in Section 3.6. In this paper, they also notice that another statistic called the initial rise could serve as a catalytic parameter. We have explored this question in [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF] and discuss it in Chapter 4.

My main contribution to the landscape of Figure 3.1 is the introduction of Tamari interval posets. At the end of my thesis, I started a collaboration on Tamari intervals with Grégory Châtel, who was also a PhD student in my institution. We introduced Tamari interval-posets in a conference paper [START_REF] Chatel | Counting smaller trees in the Tamari order[END_REF]. In the full version [CP15], we extend this definition to m-Tamari intervals. In [START_REF] Chapoton | Two bijections on tamari intervals[END_REF] and [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF], I present other useful objects in bijection with Tamari interval-posets. Nevertheless, even though they give interesting insights about intervals, these objects did not permit to obtain a direct bijective proof of Chapoton's formula (3.6). This could be done indirectly through the bijection with maps and their interpretation with blossoming trees but was not completely satisfactory. This is now solved by a very recent work of Fang, Fusy and Nadeau [START_REF] Fang | Tamari intervals and blossoming trees[END_REF] which is actually still in writing: this is a direct bijection between blossoming trees (which can be counted directly by (3.1)) and Tamari interval posets.

Tamari interval-posets

Tamari interval-posets of size n are partial orders on [n] satisfying certain conditions. We write a ◁ b to say that a is smaller than b in the poset (to differentiate from the symbol ≺ used for the Tamari lattice and the weak order) and a < c if a is smaller than c as integers. The definition stated in [CP15, Definition 2.7] says that a partial order on

[n] is a Tamari interval-poset if for all a < b < c, a ◁ c ⇒ b ◁ c; (3.7) c ◁ a ⇒ b ◁ a.
(3.8)

We give an example on the right of Figure 3.2. We see that we have 1 ◁ 5 which implies b ◁ 5 for 1 < b < 5. Similarly, we have 10 ◁ 5 which implies b ◁ 5 for 5 < b < 10. Besides, Tamari interval-posets have been integrated into SageMath. The examples of this Section can be found in [START_REF] Pons | HDR-notebooks[END_REF]. The main result of [CP15] is

Theorem 1 (Theorem 2.8 from [CP15]). Tamari interval-posets are in bijection with intervals of the Tamari lattice.

The bijection is built from binary trees using the connection between the Tamari lattice and the weak order. Recall that each binary tree can be seen itself as a poset whose linear extensions are the permutations of the sylvester class (see Figures 2.4, 2.6, and 2.7). Let [T, T ′ ] be a Tamari interval expressed as a couple of binary trees. We construct a new poset called the decreasing forest of T , F ≥ (T ), by keeping all decreasing relations (c ◁ a with a < c) of the binary tree seen as a poset. For example, on Figure 3.2, you see that 6, 7, 8, 9, and 10 are below 5 in the binary tree: they are decreasing relations and are kept in F ≥ (T ). On the other hand, the increasing relation 2 ◁ T 5 is not part of F ≥ (T ). Similarly, we construct the increasing forest, F ≤ (T ′ ), of the maximal tree in the interval T ′ by keeping its increasing relations. The interval-poset is constructed by taking relations from both the decreasing forest of T and the increasing forest of T ′ .

We usually draw it as in Figure 3.2 as the union of the Hasse diagrams of increasing relations (in blue, oriented from left to right) and decreasing relations (in red, oriented from bottom to top). For example, 9 ◁ 10 is drawn on Figure 3.2 even though it is not a cover relation as we have 9 ◁ 8 ◁ 10, because it is a cover relation of the increasing forest. This representation is very useful for many constructions on interval-posets.

The linear extensions of a Tamari interval-poset correspond to an interval of the weak order. More precisely, the linear extensions of the decreasing forest of a binary tree T correspond to the interval between the minimal permutation of its sylvester class and the maximal permutation of the weak order. For example, for the tree T of Figure 3.2, the linear extensions of F ≥ (T ) are the interval [1 3 4 2 6 7 9 8 10 5, 10 9 8 7 6 5 4 3 2 1]. Similarly, the linear extensions of the increasing forest of a binary tree T ′ correspond to the interval between the identity and the maximal permutation of the sylvester class of T ′ . For T ′ as in Figure 3.2, we get the interval [1 2 3 4 5 6 7 8 9 10, 9 8 10 6 7 3 4 2 5 1]. The linear extensions of the Tamari interval-poset are then the intersections between the two intervals, here [1 3 4 2 6 7 9 8 10 5, 9 8 10 6 7 3 4 2 5 1].

In particular, if you take two trees T and T ′ which are not comparable in the Tamari lattice, then F ≥ (T ) and F ≤ (T ′ ) have no linear extensions in common:

T → F ≥ (T ) T ′ → F ≤ (T ′ ) [T, T ′ ]
T = 3 1 2 F ≥ (T ) = 1 2 3
Linear extensions: 213, 231, 321.

T ′ = 2 1 3 F ≤ (T ′ ) = 1 2 3
Linear extensions: 123, 132, 312. the intersection of the intervals is empty. In this case, you cannot construct the interval-poset because the relations of F ≥ (T ) and F ≤ (T ′ ) are incompatible. For example, on Figure 3.3, we see that 2 ◁ 1 in F ≥ (T ) while 1 ◁ 2 in F ≤ (T ′ ): we cannot construct a poset with both relations. The interval-poset conditions (3.7) and (3.8) directly come from the increasing and decreasing forests construction. In particular, if an increasing forest is compatible with a decreasing forest (i.e., they share a common linear extension), then the result of their union is always an interval-poset. Besides, the construction of the forests is actually a very classical bijection between binary trees and planar forests. The decreasing forest is the "left sibling -right child" while the increasing forest is the symmetric "right sibling -left child": for each node, its left (resp. right) subtree becomes its left (resp. right) sibling while its right (resp. left) subtree becomes its child. In particular, the nodes on the left (resp. right) branch become the roots of the trees in the forest. This bijection easily translates to Dyck paths as illustrated on Figure 3.4.

To recover the functional equation (3.6), we describe a composition of Tamari interval-posets that translates into the product and divided difference. This is illustrated on Figure 3.5. The catalytic parameter is the number of connected Step 1: label the up-steps and their corresponding down-steps from left to right. Step 2: transform nestings into poset relations. Step 1: label all up-steps from left to right. Step 2: Connect each up-step to the first-up step following its down-step. . Following the bijection with binary trees, this corresponds to the number of nodes on the left branch of the minimal tree. On the example of Figure 3.5, it is equal to 2 for the interval on the left and to 3 for the interval on the right. The composition adds an extra node (the node 4) and creates a set of interval-posets where nodes 1 to 3 correspond to the left interval while nodes 5 to 8 correspond to the right one. Increasing relations have been added between all nodes from the left interval to the node 4. The set is over all possible ways to add decreasing relations between the right interval and the new node 4. In the generating function, the left interval would be the monomial x 2 z 3 while the right is x 3 z 4 . The composition gives the polynomial

x 2 z 3 xz x 4 z 4 -z 4 x -1 = x 3 z 8 (1 + x + x 2 + x 3 ) (3.9) = x 3 z 8 + x 4 z 8 + x 5 z 8 + x 6 z 8 . (3.10)
This composition (and associated decomposition) allows us to recover the functional equation (3.6). It also gives a natural way to write the generating function Φ(z, x) of Tamari intervals as a sum over binary trees

Φ(z, x) = T z size(T ) B T (x) (3.11)
where the sum is over binary trees and B T (x) is a polynomial defined recursively such that B T (1) is the number of trees smaller than or equal to T in the Tamari lattice. The recursive definition (Definition 1.1 of [CP15]) is given by B T (x) = 1 if T is empty and otherwise

B T (x) = x B L (x) x B R (x) -B R (1) x -1 . (3.12)
As we see on Figure 3.1, Tamari interval-posets have allowed us and others to create new bijective connections between Tamari intervals and other combinatorial families. They also give a nice characterization of some special families of intervals: exceptional intervals and modern intervals which have appeared in the work of Rognerud [START_REF] Rognerud | Exceptional and modern intervals of the Tamari lattice[END_REF][START_REF] Rognerud | The bounded derived categories of the Tamari lattices are fractionally Calabi-Yau[END_REF].

Closed flows

In [START_REF] Chapoton | Flows on Rooted Trees and the Menous-Novelli-Thibon Idempotents[END_REF], Chapoton studies certain polynomials appearing in the context of the Pre-Lie operad. They can be interpreted using flows on planar forests. It appeared that some of these polynomials were related to the Tamari lattice and actually to the Tamari polynomials that we defined in [CP15]. This lead us to define a simple bijection between closed flows and Tamari interval-posets [START_REF] Chapoton | Two bijections on tamari intervals[END_REF].

A flow can be seen as some fluid going up a tree. Each node of the tree can be a source or a leak by respectively adding or subtracting to its incoming flow. On each edge, the flow must be weakly positive. We show an example on Figure 3.6. The value added /removed to the incoming flow is written on each vertex. By definition, we state that the only possible value for a leak is -1 but sources do not have an upper limit. The exit rate is the sum of the out flow for all trees. We say that a flow on a forest is closed if the exit rate is 0. In [START_REF] Chapoton | Two bijections on tamari intervals[END_REF], we present a bijection between closed flows and Tamari interval-posets and obtain the following as a consequence.

Theorem 2 (Theorem 4.1 from [START_REF] Chapoton | Two bijections on tamari intervals[END_REF]). The number of closed flows on a given forest is the number of trees smaller than or equal to a certain tree in the Tamari lattice.

We illustrate the bijection on Figure 3.6. The general idea is the following: the flow forest gives the increasing forest of the interval-poset through a classical bijection. Then each vertex of the flow corresponds to a vertex of the Tamari interval-posets. We add the decreasing relations by reading the leaks in decreasing order. Each leak i is connected to the closest possible source k and all relations j ◁ i for i < j ≤ k are added to the interval-poset.

Grafting trees

The composition of Tamari interval-posets of Figure 3.5 can be seen as a bijection between interval-posets of size n and triples (I, J, r) such that I and J are Tamari interval-posets with size(I) + size(J) = n and r is an extra parameter between 0 and the so-called contacts of J. The contacts are the catalytic parameter, they correspond to the number of nodes on the left branch of the lower binary tree, or equivalently to the number of non-initial contacts between the lower Dyck path and the origin, or the number of connected components in the decreasing forest of J. This gives a recursive decomposition of Tamari interval-posets which can be encoded in a labeled binary tree where the label is the parameter r. We show this on Figure 3.7.

In [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF], I call these trees grafting trees. They are a direct combinatorial interpretation of the functional equation (3.6). The tree itself is the upper tree of the interval. The label of a node i is the number of children of i in the decreasing forest of the interval-poset. They can be interpreted as a list of rotations to apply to the minimal tree of the Tamari lattice to reach the lower binary tree of the interval. In particular, if all the labels are 0, then the lower binary tree of the interval is the minimal element of the Tamari lattice.

Grafting trees are all labeled binary trees such that for each node v, the label As they directly translate the functional equation, grafting trees are very natural objects to consider when working with Tamari intervals. I use them in [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF] to describe certain involutions as I explain in Chapter 4. They also make a connection to maps as there is an easy bijection between grafting trees and (1, 1)description trees found in [START_REF] Cori | Description trees and Tutte formulas[END_REF].

ℓ(v) satisfies 0 ≤ ℓ(v) ≤ size(T R (v)) -w∈T R (v) ℓ(w) where T R (v) is the right -1 -1 1 1 1 0 0 1 1 -1 -1 2 2 1 0 0 -1 0 0 1 1 0 -1 -1 1 1 1 0 0 1 1 -1 -1 2 2 1 0 0 -1 0 0 1 1 0 -1 -1 1 1 -1 -1 2

Interval-posets in m-Tamari

In [BP12], Bergeron and Préville-Ratelle conjecture that the number of intervals of the m-Tamari lattices of Section 2.9 is given by

I m,n := m + 1 n(mn + 1) (m + 1) 2 n + m n -1 . (3.13)
This is proved in [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] using an m-generalization of the functional equation (3.6) where B (m) is an (m + 1) linear form defined by

Φ (m) (z, x) = 1 + B (m) (Φ, Φ, . . . , Φ) (3.14) T L T R 1 T R 2 . . . T Rm (picture from [CP15])
B (m) (f, g 1 , . . . , g m ) = zxf ∆(g 1 ∆(. . . ∆(g m )) . . . ), (3.15) and ∆(g) = xg(x) -g(1) x -1 . (3.16)
In other words, the product and divided difference are applied m times. The authors of [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] prove that the intervals of the m-Tamari lattices satisfy the functional equation using m-Dyck paths and the contact statistic as a catalytic parameter. Then they solve the equation with a guess-and-check approach to obtain (3.13). Note that unlike the classical case, this is not a simple equation and requires advanced techniques.

As the m-Tamari lattices can be seen as a special interval of the Tamari lattice, we can express intervals of the m-Tamari lattice as some subfamily of Tamari interval-posets. This is what we do in [CP15]. This requires to characterize the binary trees which appear in the m-Tamari lattice and see how they are in bijection with (m + 1)-ary trees. We introduce the notion of m-binary trees and show how each tree can be decomposed into a set of m "roots" and m + 1 subtrees as we illustrate on Figure 3.8. This gives the following bijection.

Theorem 3 (Theorem 4.6 of [CP15]). Intervals of the m-Tamari lattice in size n are in bijection with Tamari interval-posets of size n × m such that, for all 1 ≤ i ≤ n, we have

im ◁ im -1 ◁ . . . ◁ im -(m -1).
(3.17)

See an example on Figure 3.9 for m = 2 and n = 11: you can check that we have 2i ◁ 2i -1 for all i. Using this, we recover the functional equation (3.14) and, for each element of the lattice, find a recursive formula generalizing (3.12).

In [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF], we also explain how this translates to grafting trees. An m-Tamari interval poset corresponds to a grafting tree such that ℓ(v i ) ≥ 1 if i ̸ ≡ 0 mod m. See the example on Figure 3.9 for m = 2: the labels of all odd value nodes are greater than or equal to 1. In particular, this implies that the grafting tree is an m-binary tree. We call these trees the m-grafting trees.

Open questions

On Figure 3.10, we present the bijection of Bernadi and Bonichon [START_REF] Bernardi | Intervals in Catalan lattices and realizers of triangulations[END_REF] directly between Tamari interval-posets and triangulations. We show the 13 intervals for size 3 and one example in size 4. There seems to be a direct link between the decreasing and increasing forests of Tamari interval-posets on one side and two of the trees of the realizers of the triangulation on the other side. On the last example, we see that the red tree of the triangulation (rooted on the bottom left) is exactly the decreasing forest of the interval-poset. The blue tree (rooted on the bottom right) is a bit different from the increasing forest but each node v has the same number of children in both the realizer and the interval-poset. I never had to time to fully formalize and prove this description and to explore it. This leaves some questions open. Triangulations have a clear symmetry of order 3, what is this symmetry on Tamari interval-posets? Basically, what is the "third tree" (in green, rooted at the top) on the Tamari interval-posets? What is the connection between this bijection and the new bijection of [START_REF] Fang | Tamari intervals and blossoming trees[END_REF]? Beside, neither [START_REF] Bernardi | Intervals in Catalan lattices and realizers of triangulations[END_REF] nor [START_REF] Fang | Tamari intervals and blossoming trees[END_REF] (to our knowledge) generalize to m-Tamari. The main open question then remains: is there a "map" interpretation of the intervals of the m-Tamari lattices and a bijective proof of (3.13)?

STATISTICS AND BIJECTIONS ON TAMARI INTERVALS

I counted everything. I counted the steps to the road, the steps up to church, the number of dishes and silverware I washed . . . anything that could be counted, I did.

-Katherine Johnson

Having multiple combinatorial families to represent Tamari intervals is useful when we try to understand their inner structure. Indeed, each family has natural statistics and symmetries. By combining them, we sometimes reveal more properties. When solving the functional equation (3.14), the authors of [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] noticed that there was a symmetry between the contacts of the lower path and the initial rises of the upper path. This was the result of an analytic proof (on intervals of m-Tamari) and they did not have a combinatorial explanation, even for m = 1. As the contacts are the catalytic parameter of the functional equation, this suggests that another decomposition of Tamari intervals is possible based on the initial rises. In [START_REF] Chapoton | Two bijections on tamari intervals[END_REF], we provide this decomposition and note that it actually gives an involution on Tamari intervals. But it is only in [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF] that I provide a "natural way" to see this involution using grafting trees. This also led me to define a very interesting transformation on grafting trees related to m-Tamari intervals. It is the key element to prove combinatorially the symmetry of the two statistics in the m-Tamari case as it was stated in [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] and to solve a more general conjecture of Préville-Ratelle [PR12, Conjecture 17].

In this chapter, I give an overview of my results in [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF]. I show the two natural involutions on Tamari intervals that led to the rise-contact involution. I explain their effects on different interesting statistics and then show how to generalize the involution to m-Tamari intervals. Note that the rise-contact involution has been implemented into SageMath. The computations originally provided with the paper [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF] are here [START_REF] Pons | Public open-source SageMath research code and notebooks[END_REF], the specific examples of this Chapter are available here [START_REF] Pons | HDR-notebooks[END_REF].

Contacts, descents, and complement involution

We have mentioned many times that the functional equation of the Tamari intervals requires a catalytic parameter. Different choices are possible for the statistic it refers to. In [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] and [CP15], the number of non initial contacts of the lower path is taken, i.e., the number of time the path comes back to the x axis.

For short, we call it the contact value of the interval. On binary trees, this is the number of nodes on the left branch of the lower tree. On Tamari interval-posets, this is the number of components in the decreasing forest (in red).

We can actually do more and construct a contact vector c 0 , c 1 , . . . c n-1 , that completely characterizes the lower path of the interval. The first value of the vector is the contact value. Then note that each up step of the path defines a smaller Dyck path by taking the portion of the path following the up step until it reaches its corresponding down step. For example, on the first interval of Figure 4.1, the subpath following the first up step of the lower Dyck path is given by 101100. It has two non-initial contacts which gives c 1 = 2. The second up step precedes a peak, so it defines an empty subpath and we have c 2 = 0 and so on. Contact vector: 4, 2, 0, 1, 0, 0, 1, 0 Descent vector: 1, 2, 0, 3, 2, 0, 0, 0 (reversed)

↓ Ψ 1 2 3 4 5 6 7 8
Contact vector: 1, 2, 0, 3, 2, 0, 0, 0 Descent vector: 4, 2, 0, 1, 0, 0, 1, 0 (reversed)

Figure 4.1: The complement involution on Tamari intervals This is even easier to read on the Tamari interval-poset. As we said, c 0 is the number of connected components of the decreasing forest (the graph in red). In the first interval of Figure 4.1, it is indeed 4, with the components being {1, 2, 3, 4}, {5}, {6, 7} and {8}. Then c i is the number of children in the decreasing forest of the vertex i. We can see in the example, that 1 has two children (2 and 3), giving c 1 = 2, while 2 has no children, giving c 2 = 0, and so on.

The Tamari lattice is trivially isomorphic to its revered order. Indeed , if two binary trees are such that T ≼ Q, it is immediate that their mirror images T ′ and Q ′ where the left and right subtrees have been recursively exchanged are such that Q ′ ≼ T ′ . This is a trivial involution on binary trees but not so natural on Dyck paths. On the other hand, it is easy to define on Tamari interval-posets. Sending the interval [T, Q] to [Q ′ , T ′ ] corresponds to relabeling the poset such that i becomes n + 1 -i. This "switches" the increasing and decreasing relations of the poset. We show the involution on Figure 4.1: see that we had 7 ◁ 8 and 6 ◁ 8 on the the first interval, which corresponds to the relations 2 ◁ 1 and 3 ◁ 1 on its image. We call this involution the complement of the interval-poset and write it Ψ.

As the involution transforms the decreasing forest in red into the increasing forest in blue on the second interval, it is clear what the image of the contact vector is. Where we looked at components and children in decreasing forest, we now look at the increasing forest, reading the vertices in decreasing order. This gives another obvious choice for the catalytic parameter: the number of components of the increasing forest, which is the number of nodes on the right branch of the upper tree in the interval. A little observation indicates that this is the length of the final descent in the upper path. More precisely, the complement involution exchanges the contact vector of the lower path with the reversed descent vector of the upper path (the number of down steps following each up step from right to left). See for example that in the second interval of Figure 4.1, the final up-step of the upper path is followed by 4 down steps, the previous one by 2 down steps and so on.

Rises, descents, and left-branch involution

The surprising result of [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] is that the initial rise of the upper path could serve as a catalytic parameter (and not only the final descent). The initial rise is the number of initial up steps. Of course, reversing the path gives a natural involution on Dyck paths which sends the final descent to the initial rise but it is not compatible with the Tamari order. In other words, if D ≼ D ′ in the Tamari lattice, it is not the case in general for their reversed version. Nevertheless, using the representation of Tamari intervals as grafting trees, we find that the equivalent of "reversing the path" is actually easy to define and exchanges the descent vector with the rise vector. The general idea is to reverse the upper Dyck path and let the lower Dyck path naturally "follow". Contact vector: 4, 0, 1, 0, 2, 0, 0, 1 Rise vector: 1, 2, 0, 3, 2, 0, 0, 0 Descent vector: 4, 0, 1, 0, 0, 2, 0, 1 (reversed)

↓ Φ (reverse dashed edges) Contact vector: 4, 2, 0, 1, 0, 0, 1, 0 Rise vector: 4, 0, 1, 0, 0, 2, 0, 1 Descent vector: 1, 2, 0, 3, 2, 0, 0, 0 (reversed) Remember that the shape of the grafting tree corresponds to the upper binary tree while the labels give the lower element of the interval. Dyck pack reversal easily translates to binary trees through an involution known as the "left-branch involution" which consists of reversing all nodes of every "left" branch of the tree. We illustrate this on Figure 4.2: we have written the left branches with dashed lines to make it easier to follow. The labels move along with their nodes and the result is again a grafting tree corresponding to a Tamari interval where the descent and rise vectors have been exchanged. We call this the left-branch involution on Tamari intervals and write it Φ.

The natural question is: what happens to the contact vector? To answer, we need to understand how the contact vector can be read directly on the grafting tree. This is actually quite easy. The contact value is given by the size of the tree minus the sum of the labels. On the example of Figure 4.2, this is 8 -4 = 4. Then, the value c i is the label on the node i. Reading the nodes from left to right on the first tree of Figure 4.2, we obtain indeed 0, 1, 0, 2, 0, 0, 1. You can check that it corresponds to the contact vector of the lower Dyck path. Following the involution Φ, it is clear that the contact value c 0 stays the same. The rest of the contact vector is permuted as the nodes have changed their positions but the values themselves stay the same.

Distance and Tamari inversions

Another interesting statistic appears in the work of Préville-Ratelle [PR12]: the distance. In Chapter 5, we discuss in more details the algebraic context in which the statistic appears, in relations with qt-Catalan numbers. For now, we only give its combinatorial definition and how it can be computed on different objects. The distance of a Tamari interval is the length of the maximal chain in the lattice between its lower element and upper element. For example, if the interval is reduced to a single element, then the distance is 0, if it corresponds to an edge, the distance is 1. If the interval is a pentagon (with one size of length 3 and another of length 2), then the distance is 3. On a Tamari interval, seen as a couple of Dyck paths or binary trees, this statistic is not so easy to compute as one need to find this maximal chain and prove that it is indeed maximal. It turns out that it has a very simple interpretation on Tamari interval-posets as well as on grafting trees. Besides, it also appear in the study of extended fighting fish where the distance is the area of the final surface [START_REF] Duchi | A bijection between Tamari intervals and extended fighting fish[END_REF].

We call a Tamari inversion on an interval-poset, a couple (a, c) with 1 ≤ a < c ≤ n such that: there is no b with a ≤ b < c and c ◁ b, and no b with a < b ≤ c with a ◁ b. We show an example on Figure 4.3. In particular, (i, i + 1) is always a Tamari inversion if you do not have i ◁ i + 1 nor i + 1 ◁ i. We prove in [Pon19, Proposition 28] that the number of Tamari inversions give the distance of the interval. The intuition is that Tamari inversions correspond to rotations that can be applied one by one from the lower element to the upper element. The distance can also easily be read on the grafting tree. It somehow computes a certain deficit between the labels and the maximum value they could take. Remember that a label on a node needs to be smaller than or equal to the size of its right subtree minus the sum of the labels. For example, on the root node v 4 of the grafting tree of Figure 4.3, we need ℓ(v 4 ) ≤ 4 -1. The actual label is 2, so there is a "deficit" of 1. The deficit d i is then the size of the right subtree of v i minus the sum of its labels minus the label ℓ(v i ). The only other non-zero value besides d 4 on Figure 4.3 is d 5 = 3 -1 -0 = 2. Then the distance is the sum of all deficits. Actually each value d i gives the number of Tamari inversions (i, * ).

Using this characterization, it is easy to see that the two previous involutions Ψ and Φ preserve the distance statistic. For the complement Ψ: the definition of Tamari inversions is symmetric towards the increasing and decreasing relations. Each Tamari inversion (a, c) in I corresponds to a Tamari inversion (n + 1 -c, n + 1 -a) on Ψ(I). For the left-branch involution Φ, we see that even though the shape of tree is changed, the size of the right subtrees and their labels are not.

The Rise-contact involution

Using Φ and Ψ, we obtain the following result.

Theorem 4 (Theorem 54 of [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF]). Let β be the rise-contact involution defined by β := Φ • Ψ • Φ. Then β is an involution on Tamari intervals which exchanges the contact value and the initial rise (these are the first values of the contact and rise vectors) and the values of the contact vector and rise vector (the order is not kept) while keeping the distance.

The rise-contact β is the conjugate of the Ψ involution by Φ and so is trivially an involution. This proves [PR12, Conjecture 17] for the case m = 1. We show an example of the complete involution on Figure 4.4.

The expand-contract operation on m-Tamari intervals

It is possible to define generalizations of the contact and rise vectors on intervals of the m-Tamari lattice. In [PR12, Conjecture 17], Préville-Ratelle conjectures that they are equi-distributed and symmetric (when forgetting the order of the values in the vector). This generalizes the symmetry found in [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF]. This suggests that a rise-contact involution also exists on m-Tamari intervals. But the generalization is not direct. Indeed, even though m-Tamari intervals can be trivially interpreted as intervals of a Tamari lattice on size n × m, this set is not stable by the rise-contact involution we defined previously. The idea behind the generalization is to find another interpretation of the m-Tamari intervals as a subset of intervals in n × m stable through the rise-contact involution.

To do that, we use the characterization of m-grafting trees of Section 3.6. We have the following issue: the rise vector of an m-grafting tree is m-divisible (all values are multiples of m) but not the contact vector. This dissymmetry comes This actually changes the rise vector but not the contact vector. To solve this, we apply a simple transformation on the labels of mgrafting tree:

C(I) = [4, 0, 1, 0, 2, 0, 0, 1] R(I) = [1, 2, 0, 3, 2, 0, 0, 0] C(I, X) = x 4 0 x 2 1 x 2 x 4 R(I, Y ) = y 4 0 y 1 y 2 2 y 3 J = 1 2 3 4 5 6 7 8 =   C(J) = [1, 2, 3, 2, 0, 0, 0, 0] R(J) = [4, 2, 0, 1, 0, 0, 1, 0] C(J, X) = x 4 0 x 1 x 2 2 x 3 R(J, Y ) = y 4 0 y 2 1 y 2 y 4 (picture from [Pon19])
ℓ ′ (v i ) = mℓ(v i ) if i ≡ 0 mod m, and ℓ ′ (v i ) = m(ℓ(vi) -1) otherwise.
This is the expand operation. The inverse operation is called the contract. We illustrate this on Figure 4.5. In [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF], we prove that the expand / contract operations define a bijection between m-grafting trees and grafting trees of size n×m whose contact and rise vectors are m-divisible. In particular, this new set of intervals is now stable through the classical rise-contact involution β which gives the following result.

Theorem 5 (Theorem 74 of [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF]). The m-rise-contact β m := expand •β • contract is an involution on m-Tamari intervals exchanging the m-contacts and the m-rises and proving Conjecture 17 of [START_REF] Preville-Ratelle | Combinatoire Des Espaces Coinvariants Trivariés Du Groupe Symétrique[END_REF].

Open questions

In [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF], the ideas are more important than the proofs. The definition of the expand operation especially is very simple. The proof that it is a bijection (especially that the result is a grafting tree) is only a slightly technical proof by induction. But somehow, we miss some combinatorial insight. What "are" the expanded m-grafting trees? Can they be used for other purposes? (For example, to obtain a bijective proof of the formula counting intervals). I would also like to study and understand the meaning of these different involutions in the ν-Tamari lattices. It seems possible to define an expand operation there too and some sort of rise-contact involution.

CHAPTER 5

Q, T -CATALAN

You must give me leave to judge for myself, and pay me the compliment of believing what I say.

-Jane Austen, Pride and Prejudice

The enumeration of Tamari intervals is related to diagonal harmonic polynomials. This algebraic background may give us a hint on why we find such nice formulas as they also appear as the dimensions of certain spaces and can be obtained through symmetric functions. In particular, the study of those polynomials motivated the definition of the m-Tamari lattices in [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF]. In his thesis [START_REF] Preville-Ratelle | Combinatoire Des Espaces Coinvariants Trivariés Du Groupe Symétrique[END_REF], Préville-Ratelle gives a good introduction to the algebraic questions and their relations to combinatorics, stating many problems and conjectures.

The combinatorial aspects of these questions have been an important motivation for my work. In the year 2021-2022, I obtained a délégation CNRS (sabbatical) to work in Montreal with François Bergeron in particular. He introduced me to his recent work on triangular partitions [START_REF] Bergeron | Combinatorics of triangular partitions[END_REF] which gives an interesting generalization of Dyck paths with many open questions. I spent most of the year working on these questions. In this chapter I present the general background of q, t-Catalan combinatorics and their relation to Tamari intervals and triangular partitions. I give an overview of two papers [START_REF] Pons | A description of the Zeta map on Dyck paths area sequences[END_REF] and [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF]. The first one is a short note on a description of the Zeta function (from [START_REF] Haglund | The Q, T-catalan Numbers and the Space of Diagonal Harmonics: With an Appendix on the Combinatorics of Macdonald Polynomials[END_REF]) which I had known for some years and put in writing recently. The second is the result of my collaboration on triangular partitions with Loïc Le Mogne who joined me in Montreal for his Master internship and is now doing a PhD under my supervision.

Background on diagonal harmonic polynomials

5.1.1 The q, t-Catalan and the Tamari intervals

Let us work on a ring of multivariate polynomials in multiple set of variables. This ring is naturally graded by the degrees of the polynomials in the different sets of variables. The action of the symmetric group S n which permutes simultaneously all sets of variable is called the diagonal action and is compatible with the degree graduation. Invariant polynomials under this action are called diagonal polynomials. The coinvariant spaces are the graded quotient of the ring by the ideal of invariant polynomials. They can be realized as diagonal harmonic polynomials.

We are interested in the computation of the dimensions of those spaces.

When working with a single set of variables, this is the classical theory of harmonic polynomials. This was studied in the 1950 by Shephard-Todd, Weyl, and Chevalley in connection with invariant theory and reflection groups [START_REF] Humphreys | Reflection Groups and Coxeter Groups[END_REF][START_REF] Broué | Introduction to Complex Reflection Groups and Their Braid Groups[END_REF]. The extension of the theory to multi sets of variables has been studied in the past years in different fields: combinatorics, but also quantum mechanic, representation theory, algebraic geometry.

In two sets of variables, the dimensions of the coinvariant spaces are given by (n + 1) (n-1) which is the number of parking functions. They can be understood as some Dyck paths with increasing labels on up steps. The connection with combinatorics is explained in [START_REF] Haglund | The Q, T-catalan Numbers and the Space of Diagonal Harmonics: With an Appendix on the Combinatorics of Macdonald Polynomials[END_REF][START_REF] Haglund | Combinatorial Aspects of Macdonald and Related Polynomials[END_REF]. It comes from the work of Bergeron, Garsia and Haiman using advanced algebraic tools such as representation theory. The symmetric functions are often used to express the characters of the symmetric groups through the Schur functions. In the study of coinvariant spaces also, symmetric functions play an essential role through a basis of modified Macdonald polynomials. This allows to compute the dimensions of the spaces in the form of polynomials in q and t such that the values for q = t = 1 are the Catalan numbers. These are symmetric, Schur-positive polynomials.

This last sentence has many repercussions for combinatorics. The q, t-Catalan enumeration means that the polynomials could be obtained by sending each combinatorial object of a Catalan family to a monomial q i t j where i and j are specific statistics on the object. These statistics have been proved to be the area and dinv. The area of a Dyck path is a very natural statistic counting the number of squares below the path. The dinv (and its equivalent the bounce) is a more mysterious statistic: we give different interpretations in Section 5.2. The representation theory behind the definition tells us that the two statistics are symmetric but there is, to this day, no direct combinatorial proof.

A simple proof would not only be satisfactory for the mind, it could also lead to a better understanding of those polynomials and give better computation techniques. Indeed, as we explain in Section 5.1.2, there are generalizations of the q, t symmetry and the polynomials are very difficult to compute. This is where the "Schur positivity" comes into play and gives interesting combinatorial questions. It tells us that the q i t j monomials can be "put together" to form Schur polynomials. Each Catalan object belongs to a certain subset corresponding to a specific Schur monomial but we do not know how to partition the objects into such sets and which Schur monomials appear in the q, t enumeration of a Catalan number. Obtaining a combinatorial interpretation (or an algorithm) to compute those monomials would be a huge progress.

In [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF], Bergeron and Préville-Ratelle work with 3 sets of variables instead of 2 and connect the theory of coinvariant spaces with the Tamari lattice. Indeed, now the dimensions of the spaces are given by polynomials in 3 symmetric variables q, t, and r. The values of the polynomials when q = t = r = 1 are the number of intervals of the Tamari lattice (and m-Tamari lattice for a certain m generalization of the coinvariant spaces). The 3 variables then correspond to 3 statistics on Tamari intervals. One of them is the distance of the interval which we studied in Chapter 4, it somehow generalizes the notion of area of a Dyck path: the distance of the interval between the minimal element of the lattice and a Dyck path P is the area of P . The second statistic is the dinv of the maximal element of the interval. The third statistic has no interpretation so far.

Besides, the polynomials are also Schur positive. Moreover, they correspond to "the same" Schur functions as the 2 variables case. Indeed, Schur functions are formal objects that form a basis of symmetric functions in an infinite number of variables. They are indexed by integer partitions and can be expanded into any number of variables. If the integer partition has k parts, expanding the Schur function in less than k variables gives 0. The Schur polynomials appearing in the q, t-Catalan enumeration are then the expansion in 2 variables of certain Schur functions s λ where λ has, at most, two parts. The Schur polynomials in the q, t, r enumeration of Tamari intervals are these same Schur functions expanded in 3 variables plus some extra terms s λ where λ has 3 parts.

Triangular partitions and Dyck paths

An integer partition λ of size n is a list of positive integers

λ 1 ≥ λ 2 ≥ • • • ≥ λ k with i λ i = n
where k is called the length of the partition. For convenience, we often consider partitions ending with an infinite number of 0 parts (λ j := 0 for j > k). A sub-partition µ of λ is a partition such that µ i ≤ λ i for all i ≥ 0. Dyck paths of size n are trivially in bijection with sub-partitions of the staircase integer partition (n, n-1, . . . , 1). Indeed, we often represent partitions using their Ferrers diagram as on Figure 5.1 : each line of the diagram contains λ i boxes. The top partition of Figure 5.1 is then (2, 1). If µ is a sub-partition of λ, its Ferrers diagram is contained in the Ferrers diagram of λ. The frontier between the two partitions draws a path below the initial partition (in red on Figure 5.1). When λ is the staircase partition, we obtain a Dyck path by a simple rotation. See for example the 5 sub-partitions of (2, 1) corresponding to the 5 Dyck paths of size 3.

The Dyck paths of size 4 are the sub-partitions of (3, 2, 1). (5.1)

These are called the rational Catalan numbers. Indeed, for a = n and b = n + 1, we recover the Catalan numbers. In our settings, this is counting the partitions whose Ferrers diagrams fit below the line between (0, b) and (a, 0). They are all sub-partitions of the maximal fitting partition which we call a rational partition. Combinatorial properties of rational Dyck paths are known for being related to representation theory and coinvariant spaces (See for example [ALW16, ALW15, TW18]). In particular, there exists a q, t enumeration that generalizes the q, t-Catalan case with similar open questions. In [START_REF] Bergeron | Open questions for operators related to rectangular Catalan combinatorics[END_REF], Bergeron summarizes some of these questions (both algebraic and combinatorial) in the rectangular case (where the co-prime condition for a and b is dropped). The work of [BHM + 23] suggests that the connection between combinatorial enumeration, representation theory and symmetric functions exists beyond the rectangular and rational cases: by taking paths below any line. This motivated the work of Bergeron and Mazin on triangular partitions [START_REF] Bergeron | Combinatorics of triangular partitions[END_REF]. A integer partition is said to be triangular if it is the maximal partition fitting below the line joining (r, 0) and (0, s) for r and s non-negative real numbers. In particular, r and s are not required to be integers. We show an example on Figure 5.2 next to a partition which is not triangular.

In [START_REF] Gorsky | Generalized q, t-Catalan numbers[END_REF], the authors use a formula from Gorsky and Negut [GN15] to obtain a q, t-enumeration of the sub-partitions of any partition λ, thus generalizing the q, t-Catalan numbers. But the signification of each q, t monomial is not clear and coefficients are not always positive. Conjecture 7.1.1 from [BHM + 23] states that the coefficients might be positive if the partition lies under a certain convex curve. In the case where the partition is triangular, the authors obtain an explicit formula using symmetric functions and prove a combinatorial interpretation of the statistics corresponding to q and t (generalizing the area and dinv ). In [BM22, Conjecture 1], Bergeron and Mazin further conjecture that this q, t-enumeration is Schur-positive.

Understanding the "dinv"

Zeta function and area sequences

In the q, t-Catalan enumeration, the combinatorial interpretation for the q exponent comes naturally: it is the area of the Dyck path. If we see Dyck paths as a sub-partition µ of a partition λ, this is the number of boxes which are part of λ but not of µ: the red boxes on Figure 5.1 and 5.3. Even in the classical case, the interpretation of the second statistic is more difficult. In [START_REF] Haglund | Conjectured statistics for the q,t-Catalan numbers[END_REF], Haglund gives a first conjectural interpretation of the exponent of t as the bounce statistic. At the same period, Haiman finds another interpretation that we now call the dinv. This leads Haglund to come up with a bijection from Dyck paths of size n to themselves sending the area and bounce to the dinv and area respectively. This is the zeta map ζ [Hag08, page 50]. In particular, it proves that the area, the dinv, and the bounce are equi-distributed (but not the q, t-symmetry). As q, t-enumerations arose in more general settings, some generalization of the ζ map also appeared. In [START_REF] Armstrong | Sweep maps: A continuous family of sorting algorithms[END_REF], the author describe a general ζ map for all rational Dyck paths. They conjecture that it is bijective but it appears a difficult question. It was eventually solved in [START_REF] Thomas | Sweeping up zeta[END_REF].

I discovered the q, t-enumeration of Catalan number at some time during my thesis. I found the problem of finding a combinatorial proof of the symmetry fascinating and tried to solve it. I did not succeed but I came up with a bijective map that I soon discovered was the ζ map (more precisely ζ -1 ). As it was not a major result, I did not care to write it at the time. I finally did last year in [START_REF] Pons | A description of the Zeta map on Dyck paths area sequences[END_REF] after discussing it with Hugh Thomas as he had actually never seen this description anywhere. As I explain below, it is based on the area sequence of Dyck paths. We read the sequence value by value and make an insertion in a new area sequence that we build iteratively. The process is very simple and can be easily implemented. I actually provide the full implementation with the paper in [START_REF] Pons | An implementation of the Zeta map on Dyck paths area sequences[END_REF].

The area sequence of a Dyck path is a very common way to represent Dyck paths and to compute the area. It consists of "counting the boxes": when represented as in 5.3, we read the number of red boxes, line by line, from top to bottom. This gives a bijection between Dyck paths of size n and sequences of integers a 1 , . . . , a n where a 1 = 0 and 0 ≤ a i+1 ≤ a i + 1. The area is of course the sum of the a i . The dinv is also easy to compute from the area sequence: it is the number of couples (a i , a j ) with i < j and a j = a i or a j = a i -1. On Figure 5.3, the dinv is 65.

I define an operation called the insertion on the area sequence. If a 1 . . . a n is an area sequence, then inserting in position i gives the new sequence a 1 . . . a i (a i + 1)a i+1 . . . a n . By convention, inserting in position 0 adds a 0 at the beginning of the sequence. I then explain how we can control the increase of the dinv through the insertion and I define specific insertion points such that if the last inserted value increased the dinv by v i , then the new sequence has v i +1 insertion points corresponding to potential increases of the dinv of 0, 1, . . . v i + 1. From an area sequence a 1 . . . a n , we can then construct a new sequence by inserting at the insertion point in the image which increases the dinv by exactly a i .

Theorem 6 (Theorem 6 of [START_REF] Pons | A description of the Zeta map on Dyck paths area sequences[END_REF]). The insertion process described previously defines a bijection on area sequences such that the dinv of the image is the area of the sequence. We show an an example on Figure 5.4 where insertion points are made visible. We prove that this map is actually ζ -1 . In particular, we give a direct proof that the area of the new sequence is the bounce of the original one. 0

• 1 0• 0 01 • 2 0 • 1 0• 0 012 • 3 0 • 2 0 • 1 0• 0 0121 0 0 • 2 1 • 0 0• 1 01211 0 0 1 • 1 0 • 2 1• 0 012111 0 0 1 • 2 2 • 0 0 1• 1 0121112 0 0 1 • 3 2 • 1 2 • 0 0 1• 2 01211123 0 0 1 • 4 2 • 2 2 • 1 2 • 0 0 1• 3 012111233 0 0 1 2 • 3 2 • 2 2 • 1 0 1 • 4 2• 0 0121112330 0 0 1 2 2 2 0 1 2 • 1 3• 0 01211123301 0 0 1 2 2 2 0 1 2 • 2 3 • 1 3• 0 012111233011 0 0 1 2 2 2 0 1 2 3 • 2 4 • 0 3• 1 0121112330110 0 0 1 2 2 2 0 1 2 3 4 • 1 5 • 0 3 01211123301101 0 0 1 2 2 2 0 1 2 3 4 • 2 5 • 1 5 • 0 3 012111233011012 0 0 1 2 2 2 0 1 2 3 4 • 3 5 • 2 5 • 1 5 • 0 3 0121112330110122 0 0 1 2 2 2 0 1 2 3 4 5 • 3 6 • 0 5 • 2 5 • 1 3 01211123301101221 0 0 1 2 2 2 0 1 2 3 4 5 6 • 1 5 5 • 2 6 • 0 3

The deficit in triangular Dyck paths

In [BHM + 23], the authors generalize the dinv statistic to all triangular Dyck paths by counting the p-balanced hooks in the Ferrers diagram of the sub-partition. This is reformulated in [BM22, Section 4.1] and given a new name: the sim statistic. Remember that a triangular partition is the maximal partition lying under a given line. Actually, for any given triangular partition, there is an infinite number of lines to choose from. The authors of [START_REF] Bergeron | Combinatorics of triangular partitions[END_REF] provide a very simple criteria for deciding if a a given partition is triangular using the hooks of the different cells. They also define a certain notion of mean slope as an explicit line choice. A cell of a sub-partition is said to be similar if its hook is "compatible" in a certain sens with the mean slope of the triangular partition. The number of similar cells is called the sim. It corresponds to the known dinv statistic on regular and rational Dyck paths. We show an example on the left of Figure 5.5: the similar cells are colored in green while the non similar cells are in yellow with dotted pattern.

In [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF], we present a new combinatorial interpretation of the similar cells using a new statistic called the deficit. The cells of the Ferrers diagram of a partition λ can be filled with numbers to form a tableau. It is called a standard Young tableau if it contains exactly the numbers 1, . . . , n such that the numbers are increasing on each line and each column. Let θ be a standard Young tableau of shape λ where λ is a triangular partition. We say that there is a θ-inversion in a sub-partition µ of λ if there is a cell c inside µ with a higher value in θ than another cell c ′ outside of µ. For example, on the right of Figure 5.5, we see that 15 is inside the sub-partition while 14 is outside. Then the cell which lies at the "hook" of c and c ′ is said to be a deficit cell. The number of deficit cells gives the deficit of the triangular Dyck path with tableau θ.

In the example of Figure 5.5, we see two deficit cells: the cell number 2 which is at the hook of 15 and 14, and the cell number 10 which is at the hook of 16 and 14. These are the two cells which were identified as non similar cells on the left. Indeed, we prove that on a certain tableau that we call the triangular tableau, the deficit cells are exactly the non similar cells. This tableau is constructed using the mean slope defined by Bergeron and Mazin (or more precisely, a slight irrational deformation): we move the slope towards the origin and number the cells in decreasing order as we touch them. Using an irrational slope ensures that slope touches the cells one by one. We show an example on Figure 5 This interpretation has been very useful and it also opens new horizons. Indeed, we might wonder what are the q, t-enumerations of other standard Young tableau of shape λ, using the tableau deficit to compute the power of t. Most of the time, it is not symmetric but it actually defines a certain family of tableaux, which we call the similar-symmmetric tableaux, or sim-sym, on which we recover the original q, t-enumeration. Characterizing those tableaux seems to be a difficult question: we find some of them as "slope tableaux" using a similar construction as for the mean slope, but not all of them. We were nevertheless able to characterize them in the case of triangular partitions of length 2.

Lattice interval enumeration and Schur-positivity

We have briefly explained the relations between the q, t-enumeration of Dyck paths, the symmetric functions and representation theory. In the case of triangular partitions, these relations are still conjectural (especially concerning representation theory). When I met him in Montreal, François Bergeron was working on this question. In particular, he was able to compute, or partially compute, a certain Schur-positive symmetric function for each triangular partition. The expansion in two variables of those functions are the q, t enumeration of triangular Dyck paths. The question he asked me was: what happens in 3 variables? For classical Dyck paths and m-Dyck paths, we know we obtain an enumeration on Tamari and m-Tamari intervals but what happen on the other cases?

The most natural choice is to look at the intervals of the ν-Tamari lattice that we mentioned in Section 2.9. In certain cases, it gives the wanted enumeration but not in all cases. For some partitions, we have the right number of intervals but loose the q, t-symmetry or the Schur-positivity. In other cases, the number of intervals does not correspond to the expansion of the symmetric function. I spent lots of time trying to find a lattice structure that would give the proper q, t-interval enumeration. Even though I was able to compute some examples (I actually explain that in Chapter 9), I could not find a proper general definition.

Around this time, I was joined by Loïc Le Mogne who started his internship and was interested in working on these questions. I asked him to look at the case of triangular partitions of length 2. Indeed, this case is much easier than the general case but still largely non-trivial. As we came up with the definition of sim-sym tableaux, it appeared to us that a certain maximal chain in the ν-Tamari lattice defines a Young tableau, which we call the top-down tableau, which sometimes is sim-sym. In particular, in the length 2 case, the top-down tableau is always sim-sym but does not necessarily corresponds to the triangular tableau. We then state the following theorem.

Theorem 7 (Theorem 5 of [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF]). The q, t-enumeration of intervals of the ν-Tamari lattice on triangular 2-partitions is symmetric and Schur-positive.

The statistic corresponding to q is the distance while the statistic corresponding to t is the number of similar cells using the top-down tableau. The proof of the theorem has been obtained by Loïc Le Mogne based on case-by-case analysis using the structure of the lattice. It will appear in the long version of the paper.

Using this result and some extra computation, we express a new conjecture on q, t-enumerations of intervals.

Conjecture 8 (Conjecture 4 of [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF]). Let λ be a triangular partition such that the top-down tableau of λ is sim-sym, then the q, t-enumeration of ν-Tamari intervals is symmetric and Schur-positive.

Open questions

We have seen already that the general field of q, t-Catalan combinatorics has many open questions as we can read in [START_REF] Preville-Ratelle | Combinatoire Des Espaces Coinvariants Trivariés Du Groupe Symétrique[END_REF] and [START_REF] Bergeron | Open questions for operators related to rectangular Catalan combinatorics[END_REF]. Some of these questions are very difficult but they often leave a trace of more approachable problems. The study of triangular partitions and our own results are still very new and we have many leads to investigate:

• We would like to better understand sim-sym tableaux. In particular, there should be a bijection between elements of similar area and sim using different tableaux.

• The question of finding the "good" lattice structure is still open. Even if the general case is difficult, we have had new ideas on how to approach it. One would be to further study the length 2 case. Indeed, we might be able to define a different lattice for each sim-sym tableau and prove that they give a similar enumeration of intervals.

• I did not have the time yet to investigate the ζ function on triangular partitions. I do not know if the general definition of sweep maps from [START_REF] Armstrong | Sweep maps: A continuous family of sorting algorithms[END_REF] which was later proven to be bijective in [START_REF] Thomas | Sweeping up zeta[END_REF] works for triangular partitions (it is said to work on the rectangular and rational cases). In any case, it needs specific investigation to understand how it is or could be defined and what it tells us on the combinatorics of the triangular case.

• There are some notions of contacts and rises on triangular Dyck paths, in relation in particular with triangular parking functions. We need to further investigate the expressions that arise in the symmetric functions related to triangular partitions and look for proper combinatorial interpretation. In particular, we need to look at classical bijections and correspondences of the classical case and see how they generalize.

• Similarly, we need to investigate how to get "triangular versions" of some classical Catalan objects, in particular objects that are in relations with Tamari intervals as in Figure 3.1.

Part III

Quotients and Sublattices

CHAPTER 6

INTEGER POSETS

Definitions belong to the definers, not the defined.

-Toni Morrison, Beloved.

As I presented in the previous chapters, Tamari interval-posets were the result of a collaboration with Grégory Châtel. This started around 2012 while I was finishing my thesis and Gréory Châtel was a fellow student. Around 2013, we started working with Vincent Pilaud to understand the connection between our work on Tamari intervals and Cambrian lattices [Rea06]. We wanted to answer the following questions: can the intervals of the Cambrian lattices be seen as intervalposets? Can we use this characterization to count the intervals? Is it possible to define other algebraic structures, such as Hopf algebras, on intervals? The short answers are: yes, no, yes. In particular, there is a specificity of the Tamari lattice for counting intervals. Nevertheless, as we started exploring those questions, it appeared that many combinatorial objects that were considered very different in nature could be seen as integer poset. It became interesting to study this specific family and how it related to previously known algebraic structures, especially lattices and Hopf algebras. This collaboration resulted in 3 papers [PP18, CPP19], and [START_REF] Pilaud | The Hopf algebra of integer binary relations[END_REF]. This chapter is dedicated to [START_REF] Chatel | The weak order on integer posets[END_REF] where we explore the lattice structure of integer posets, and [START_REF] Pilaud | The Hopf algebra of integer binary relations[END_REF] which is about Hopf algebraic aspects. The results from both papers were originally presented in a FPSAC conference poster [START_REF] Pilaud | Algebraic structures on integer posets[END_REF]. The paper [PP18] describes some family of objects called the permutrees, we present it in details in Chapter 7. Even though it was written before the two other papers, the original motivation came from the study of integer posets. We start here by explaining how many objects can be described in terms of integer posets. We then give the main ideas to construct the lattice and Hopf algebra of integer posets through the notion of integer relations.

Generalizing the Tamari interval-posets

We have defined Tamari interval-posets as posets on integers satisfying certain relations. Besides, the linear extensions of a Tamari interval-poset give a certain interval of the weak order. Actually, any interval of the weak order can be encoded as the linear extensions of a certain poset on integer. Tamari interval-posets are just a special case.

Indeed, let us consider permutations as a linear order on integers: they correspond to a special case of partial orders on integers where the order is total. Similarly, standard binary search trees define a poset by orienting all edges towards the root. The linear extensions are the sylvester class of the tree. This is also the case of binary sequences: we interpret any -sign by an increasing relation and any + sign by a decreasing relation. In this case, linear extensions also give a certain interval of the weak order corresponding to the recoil class we mentioned in Section 2.8. We show examples of these constructions on Figure 6.1. In this chapter, we always represent integer posets by writing the integers in their natural order on a line and writing all relations (not just cover relations) by dividing them intro increasing relations (in blue, from left to right, on top) and decreasing relations (in red, from right to left, on bottom). Now we can construct interval-posets of the corresponding lattices (the weak order, the Tamari lattice, and the boolean lattice). For each interval e ≼ f , we take the decreasing relations of the smaller element e and the increasing relations of the larger element f as illustrated on Figure 6.2 for permutations. This always give a certain poset on integers and we characterize the obtained families depending on the considered lattice. The conditions that need to be satisfied are always local conditions on triplets a < b < c. Basically, the increasing (resp. decreasing) We then obtain three families of integer posets representing three families of intervals in the weak order, the Tamari lattice and the boolean lattice respectively. In [START_REF] Chatel | The weak order on integer posets[END_REF], we call them WOIP for weak order interval-posets, TOIP for Tamari order interval-posets and BOIP for boolean order interval-poset. The elements of those latices (permutations, binary trees, and boolean sequences) are the maximal posets (posets with the maximal number of relations) that we can construct satisfying the interval conditions (we call them WOEP, TOEP, and BOEP where the E stands for element). In particular, you can always recover the element from the increasing (resp. decreasing) relations. For a permutation, this means recovering the permutation from the inversions. For a binary tree, this corresponds to the bijection between the tree and its decreasing / increasing forest. Besides, we can also characterize faces of the corresponding polytopes as special kind of intervals:

the WOFP [CPP19, Proposition 2.10] are the interval-posets corresponding to the faces of the permutahedron, the TOFP [CPP19, Proposition 2.10] correspond to faces of the associahedron, while all BOIP are actually faces of the cube.

The nice enumeration of Tamari intervals come from the fact that the increasing and decreasing relations form a forest of rooted trees. It is not the case for the weak order especially and the characterization does not lead to interesting decompositions in terms of enumeration. Nevertheless, all this objects are known to appear in different algebraic structures: lattices and Hopf algebras. This is what motivates the following sections which proposes a general framework to define these structures.

Integer Relations

As a lattice

Let S be a set of size n and R a binary relation on S, i.e., a set of couples (x, y) with x ∈ S and y ∈ S. We write x R y if x is in relation with y and x ̸ R y if not. We consider only reflexive relations, i.e., x R x for all x ∈ S. But R is in general not symmetric so x R y does not imply y R x. The boolean lattice is a well known structure on binary relations where the order is given by inclusion of the relations. The minimal element is the empty relation, while the maximal is the relation R where x R y for all x and y in S. The meet and join are given by taking respectively the intersection and union of relations.

We now consider the case where S = 1, . . . , n and we say that R is an integer relation. In this case, the set S is actually endowed with 2 relations: the relation R and the natural order relation between integers. This allows for a new lattice definition which we call the weak order on integer relations as it is indeed a generalization of the weak order on permutations as we explain in Section 6.4.

We see the integer relation R as the union of two subrelations : the increasing relation R Inc , i.e., the couples a R b with a < b and decreasing relation R Dec , i.e., the couples b R a with a < b. We say that a relation R is smaller than or equal to a relation S, R ≼ S, if and only if R Dec ⊆ S Dec and S Inc ⊆ R Inc (Definition 1.1 of [START_REF] Chatel | The weak order on integer posets[END_REF]).

We present the example for relations of size 2 on Figure 6.4. We show both the classical boolean lattice on the left and the weak order on the right. On the boolean lattice, the minimal element is the empty relation and at each step, one relation is added. On the weak order, the minimal element is the relation containing all possible increasing relations and at each step, either one increasing relation is removed or one decreasing is added. In particular, the weak order on integer relations is isomorphic to the classical boolean lattice. Indeed, it is a product of the reversed boolean lattice on increasing relations by the boolean lattice on decreasing relations. It then forms a cube of dimension n(n -1).

Note that we always represent relations as in Figure 6. As it is isomorphic to the boolean lattice, the weak order on integer relation is a lattice. We can easily compute the join in the meet as shown on Figure 6.4: the meet is obtained by taking the union of increasing relations and intersection of decreasing relations. The join is the symmetric operation.

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
Figure 6.5: Join and meet on integer relations

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 F R 1 2 • F R 1 = F R 1 2 3 + F R 1 2 3 + F R 1 2 3 + • • • + F R 1 2 3
.

(picture from [PP20])

Figure 6.6: Product in the Hopf algebra of integer relations as an interval

As a Hopf algebra

Let R be the set of all integer relations, R n the set of integer relations of size n, and k a field. Then we can define a Hopf algebra on the vector space kR := n≥0 kR n . The product (on the fundamental basis F R) is given by what we call the shifted shuffle of two relations R of size n and S of size m [PP20, Definition 3]. This is a set containing all relations T such that the subrelation of T on 1, . . . , n is R and the subrelation on n + 1, . . . , n + m is the shifted version of S, written S. In other words, an relation T of the shifted shuffle is obtained by concatenating R and S and adding some increasing relations from R to S and some decreasing relations from S to R. In particular, the shifted shuffle has cardinality 2 2mn .

The product between R and S is the sum over all the elements of the shifted shuffle. This actually gives a sum over an interval of the weak order on integer relations. The minimal element is given by R\S, the relation where all increasing relations have been added between R and S and no decreasing relations. While the maximal element is R/S, the relation where all decreasing relations have been added between S and R and no increasing relations. See an example on Figure 6.6.

The coproduct on kR is defined using the notion of total cuts of a relation (Definition 10 of [START_REF] Pilaud | The Hopf algebra of integer binary relations[END_REF]). A total cut on relation R of size n is a partition of 1, . . . , n into two sets X and Y such that for all x ∈ X and y ∈ Y , we have x R y and y ̸ R x. In particular, there are always two trivial total cuts: the case where either X or Y is the empty set. The coproduct is the sum over all the total cuts, where the relation R is divided into the two (standardized) subrelations given by the total cut. For example, we have

△ F R 1 2 3 = F R 1 2 3 ⊗ F R ∅ + F R 1 ⊗ F R 1 2 + F R 1 2 ⊗ F R 1 + F R ∅ ⊗ F R 1 2 3
where the total cuts are ({1, 2, 3}, ∅), ({1}, {2, 3}), ({1, 3}, {2}), and (∅, {1, 2, 3}).

We prove in [PP20, Proposition 15] that the product and coproduct indeed define a graded Hopf algebra on kR. The correspondence with the weak order allows us to define multiplicative bases and obtain that the Hopf algebra is freely generated by certain elements indexed by under-indecomposable relations (relations T which cannot be written as T = R\S).

Integer Posets

As a lattice

A poset is a binary relation which is reflexive, antisymmetric and transitive. As we only consider reflexive integer relations, we are interested in studying the induced subposets of the lattice of integer relations on antisymmetric and transitive integer relations.

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
Figure 6.7: Meet of two transitive relations.

We write A n the set of antisymmetric integer relations of size n. It is easy to prove that it forms a sublattice of the weak order on integer relations [CPP19, Proposition 1.4]. Indeed, suppose that T = R∧S is not an antisymmetric relation. This means that we have x and y with x T y and y T x. We suppose x < y. The decreasing relations of T are the intersection of the decreasing relations of R and S,

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 (picture from [CPP19])
Figure 6.8: The weak order lattice on integer posets so we have y R x and y S x. As the increasing relations of T are the union of the increasing relations of R and S, we have the relation (x, y) in at least one of R or S. So one of R or S is also not antisymmetric.

On the other hand, transitive relations T n do not form a sublattice of the lattice of integer relations. Indeed, it is well known that the union of two transitive relations is not itself transitive. Nevertheless, the weak order on transitive integer relations is still a lattice. We explain a process to construct the meet of two transitive relations as illustrated in 6.7. Let R and S be two transitive relations. Their meet as integer relations is not transitive. We first apply a transitive closure on the increasing relations. The result is still not transitive as there might be a chain involving a decreasing relation. In this case, we remove the problematic decreasing relations.

This operation is called the transitive decreasing deletion and we prove in [CPP19, Proposition 1.14] that it indeed gives the meet of the two relations in the poset of transitive relations. Beside, this is compatible with the antisymmetry condition: the antisymmetic (transitive) relations form a sublattice of the transitive relations. This gives the main theorem of [START_REF] Chatel | The weak order on integer posets[END_REF].

Theorem 9 (Theorem 1 from [START_REF] Chatel | The weak order on integer posets[END_REF]). The weak order on integer posets is a lattice.

See Figure 6.8 for an example in size 3. Note that this was later generalized to other finite Coxeter groups in [START_REF] Gay | The weak order on Weyl posets[END_REF].

As a Hopf algebra

Looking at integer posets in the Hopf algebra of integer relations, we obtain the two following properties [PP20, Proposition 30]:

• if at least one integer poset appears in the product of two relations R and S, then both R and S are integer posets;

• the coproduct of an integer poset only contains integer posets.

This allows us to define a Hopf algebra on integer posets as a quotient of the Hopf algebra of binary relations by the ideal generated by relations which are not posets. In other words, we just "remove" the non-posets from the result of the product. For example, the result of the product of Figure 6.6 in the Hopf algebra of integer-posets is now given by a sum over the interval of Figure 6.9.

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 (picture from [PP20])
Figure 6.9: Interval corresponding to the product of integer posets.

General audience paper

The lattice aspects of this work concerning binary integer relations and integer posets have been turned into a general audience paper published in the magazine Interstices [START_REF] Pons | Ordonner les ordres : un treillis sur les ordres partiels[END_REF]. This was an occasion to present the notion of poset using the illustration of the closet-poset of Figure 6.10.

Figure 6.10: The Closet-Poset

Induced structures on permutations, binary trees and more

Permutations seen as WOEP (see Section 6.1) form a sublattice of the lattice of integer posets [CPP19, Proposition 2.3]. This is the weak order. Indeed the order is given by the inclusion of the inversions. Moreover, the WOIP and TOIP induce some subposets. They are both lattices but only TOIP forms a sublattice. This led us to study more precisely in which cases we obtain a sublattice and to describe processes to compute the meet (and the join) when the induced poset is a lattice but not a sublattice. This motivated the definition of permutrees which we describe precisely in Chapter 7. Recall by looking at Figure 6.3 that, in a weak order interval, for each increasing relation a ◁ c we need to have a ◁ b or b ◁ c for a < b < c (with symmetrical conditions on decreasing relations). In the case of Tamari intervalposets, we "force" to always have b ◁ c. We could also force to always have a ◁ b.

INDUCED STRUCTURES ON PERMUTATIONS, BINARY TREES AND MORE81

In the boolean lattices, we force to have both. It is quite natural to "mix" the forcing conditions of the different objects. For example, in size 4, we can decide that each increasing relation a ◁ c with a < 2 < c forces the relation 2 ◁ c, whereas each increasing relation a ◁ c, with a < 3 < c forces the relation a ◁ 3.

We encode the rules into a decoration. Each decoration gives a certain family of intervals and elements: the permutrees. In particular, this includes and generalizes the Cambrian trees defined by Reading in [Rea06]. In [CPP19, Theorems 2.77, 2.82, 2.85, and 2.88], we study the relations between the lattices on intervals and elements and the lattice of integer posets. We find in particular a sufficient condition on the decoration to obtain sublattices of the lattice of integer posets: it needs to be covering: for each b, with 1 < b < n, either a ◁ b or b ◁ c should be explicitly forced (or both). We obtain like this that the Tamari lattice, the Cambrian lattice, and the boolean lattice as well as their lattices of intervals are sublattices of the lattice of integer posets.

Besides, using the characterization of the faces of the permutahedron as WOFP, of the associahedron as TOFP, we obtain induced subposets of the integer posets which are lattices. For the permutahedron, this is the facial order defined in [KLN + 01] and more generally in [START_REF] Dermenjian | The facial weak order and its lattice quotients[END_REF]. The facial order on the faces of the associahedron is found in [START_REF] Dermenjian | The facial weak order and its lattice quotients[END_REF][START_REF] Novelli | Polynomial realizations of some trialgebras[END_REF][START_REF] Palacios | Weak Bruhat order on the set of faces of the permutohedron and the associahedron[END_REF]. This construction also generalizes to the faces of the permutreehedron (we define this polytope in the next Chapter).

In [START_REF] Pilaud | The Hopf algebra of integer binary relations[END_REF], we study the induced Hopf algebraic structures and obtain the following.

Theorem 10 (from [START_REF] Pilaud | The Hopf algebra of integer binary relations[END_REF]). The intervals of weak order, Tamari lattice, boolean lattice and more, can be endowed with Hopf algebraic structures.

For the intervals of the weak order, we are able to quotient the Hopf algebra of integer posets to obtain a Hopf algebra of weak order intervals (WOIP). The process is very similar to the quotient from integer relations to integer posets: we "remove" the non-weak order intervals from the product of two weak order intervals in the Hopf algebra of integer posets. Besides, the WOIP Hopf algebra can also be obtained as a subalgebra of the integer-posets algebra by constructing certain fibers of a deletion process defined in [START_REF] Chatel | The weak order on integer posets[END_REF]. Using similar processes, we reconstruct the Malvenuto-Reutenauer Hopf algebra on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF] and the Chapoton Hopf algebra on faces of the permutahedron [START_REF] Chapoton | Algèbres de Hopf des permutahèdres, associahèdres et hypercubes[END_REF].

We then prove in [PP20, Proposition 84] that the TOIP (intervals of the Tamari lattice) form a sub Hopf algebra of the Hopf algebra of weak order intervals. Similarly, we recover the Loday-Ronco Hopf algebra [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF] and a Hopf algebra on the faces of the associahedron [START_REF] Chapoton | Algèbres de Hopf des permutahèdres, associahèdres et hypercubes[END_REF]. All these constructions generalize to permutrees.

Open questions

In [START_REF] Foissy | Algebraic structures on double and plane posets[END_REF], Foissy describes a Hopf algebra of double posets and a specific case where one of the poset is actually linear. By looking at the product, it is clear that it is not the same as the one we define. It still raises questions on these structures. Indeed, there are different ways to define products and co-products on double relations (and more generally on k-tuples of binary relations). One choice gives our Hopf algebra, another gives Foissy Hopf algebra. It would be interesting to classify these different possibilities: which ones are self dual? In case they are not, what is the dual? In which case can we obtain Hopf algebras on posets, on permutations or permutations intervals? What are the structures that we recover or define this way? CHAPTER 7

PERMUTREES

Mathematical science shows what is. It is the language of unseen relations between things. But to use and apply that language, we must be able to fully to appreciate, to feel, to seize the unseen, the unconscious.

-Ada Lovelace

In [START_REF] Chatel | Cambrian Hopf algebras[END_REF], Châtel and Pilaud present a Hopf algebra on Cambrian trees. Cambrian trees are certain non rooted binary trees which can be used to represent the elements of the Cambrian lattices of Reading [Rea06]. The Cambrian lattices are lattice quotients of the weak order and each Cambrian tree represent a class. In particular, Cambrian trees can be represented as integer posets (see Chapter 6). While working on integer posets, it appeared that we could define a more general family: the permutrees. The name "permutree" comes from "permutation" and "tree". Indeed, permutrees are a family that regroups permutations, rooted binary trees, Cambrian trees, binary sequences, and interpolations between these objects. A permutree comes with a certain decoration. Each decoration defines a specific family of permutrees, a lattice quotient of the weak order and a polytope. Besides, we are able to define a Hopf algebra of permutrees (using all decorations) which is a subalgebra of a certain decorated version of the Malvenuto-Reutenauer Hopf algebra on permutations [START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF].

In this chapter, we present the results of two papers: first [PP18] (also presented at EUROCOMB in [START_REF] Pilaud | Permutrees[END_REF]) in collaboration with Vincent Pilaud, then [START_REF] Pilaud | Permutree sorting[END_REF] (also presented at FPSAC in [START_REF] Pilaud | Permutree sorting[END_REF]) in collaboration with Vincent Pilaud and Daniel Tamayo Jiménez. I consider this second paper as a first step towards defining permutrees for all finite Coxeter groups.

Lattice quotients and decorations

In Section 2.6, we explain how Cambrian lattices can be constructed as quotients of the weak order defined by a certain orientation of the Dynkin diagram of the group. In type A, this means choosing an orientation i → i+1 or i ← i+1 for each 1 ≤ i < n-1. If we have i → i+1, we contract the edge between the permutations s i+1 = 1 . . . i(i + 2)(i + 1) . . . n and s i+1 s i = 1 . . . (i + 2)i(i + 1) . . . n. This is the "right" side of the initial hexagon formed by s i and s i+1 . Symmetrically, if we have i ← i + 1, we contract the edge between the permutations s i = 1 . . . (i + 1)i(i + 2) . . . n and s i s i+1 = 1 . . . (i + 1)(i + 2)i . . . n, the "left" side of the hexagon. We then take the lattice congruence generated by these contractions.

For Cambrian congruences, each edge needs to to be oriented in exactly one direction. The permutree congruences are the generalizations where we now allow an edge to not be oriented or to be oriented in both directions. See on These congruences form a subfamily with interesting properties of the set of all lattice congruences of the weak order studied by Reading in [START_REF] Reading | Lattice Congruences of the Weak Order[END_REF]. We show all possible permutree congruences for size 4 on Figure 7.2. We see that they are ordered by refinement: orienting an edge in the Dynkin diagram corresponds to contracting a side of a polygon and to merge some congruence classes. The most refined congruence corresponds to the case where no edge is contracted: this is the trivial congruence where each permutation is its own class and we have n! classes. If all edges are contracted, we obtain the cube congruence we described in Section 2.8 with 2 n-1 classes. If exactly one edge is contracted for each hexagon, this is a Cambrian congruence. If we contract always the same size, this is the sylvester congruence. In both cases, the number of classes is given by the Catalan numbers. In Section 7.2, we explain how in general we can associate each class with a tree satisfying certain properties called a permutree.

To each orientation of the Dynkin diagram, we associate a certain word δ ∈ { , , , } n called the decoration using the following rules i

--i + 1 δ i+1 = ; i → i + 1 δ i+1 = ; i ← i + 1 δ i+1 = ; i ↔ i + 1 δ i+1 = .
These symbols correspond to certain type of nodes in the permutrees as we explain in Section 7.2. The first and last symbols δ 1 and δ n are set to by convention. We could actually use any symbols: the first and last symbol of the word only play a role for the combinatorial definition but do not change the corresponding Dynkin diagram orientation nor the congruence of the weak order. Using this convention, the orientations 1 ← 2 --3 and 1 ↔ 2 --3 of Figure 7.1 correspond to the words and respectively. We can use the decorations to interpret the minimal elements of the congruence classes in terms of pattern avoidance. Recall that the minimal elements of the sylvester classes are the 312-avoiding permutation. In case of permutrees, we need to specify the value of the middle element of the pattern. Minimal permutations in the permutree classes are the ones avoiding cab subwords with a < b < c and δ b ∈ { , } and bca with a < b < c and δ b ∈ { , }. For example, 2413 is not minimal in its class for δ = because it contains 241 and δ 2 = . This characterization is given in [PP18, Corollary 2.14]. We use it in [START_REF] Pilaud | Permutree sorting[END_REF] to characterize the reduced words of the minimal class elements as explained in Section 7.7. Permutrees are directed (from bottom to top) planar non rooted trees, labeled by exactly the numbers 1, . . . , n and such that each node is of certain type defined by a symbol in { , , , }. The image of the symbol represents the incoming / outgoing edges and implies certain rules illustrated on Figure 7.3. A node has one incoming edge and one outgoing edge. A node has two incoming edges and one outgoing edge. A node has one incoming edge and two outgoing edges. And a node has two incoming edges and two outgoing edges. The nodes coming from or going to the left of a given node i must be labeled with values smaller than i. Symmetrically, the nodes coming from or going to the right of a given node i must be labeled with values bigger than i. The decoration is the words of node symbols read from 1 to n (from left to right). We say that the symbols and are down symbols as they have two incoming edges. Similarly, we write that and are up symbols. In particular is both an up and a down symbol while is neither. Permutrees are actually better understood as the result of a certain insertion algorithm from permutations that we illustrate on Figure 7.4. The algorithm takes a permutation σ of size n and a decoration δ ∈ { , , , } n and constructs a permutree with decoration δ. We often write the decoration directly on the values of the permutation for convenience. A value v is underlined if δ v is a down symbol and overlined if δ v is an up symbol. For example the decorated permutation 2751346 corresponds to the decoration . The algorithm is as follows. For all 1 ≤ i ≤ n, we place the symbol δ i at position (σ i , i). The values 1, . . . , n on the y-axis are called the levels of the nodes. We trace a red line below any down symbol and above any up symbol. The label of the node is the value σ i in the permutation and is written below (or above) the red line. These lines correspond to certain "walls" that cannot be crossed by the edges of the permutree. They enforce the labeling rules attached to the nodes. We start an edge at every interstice between the red lines at the bottom of the picture including the borders. We then "grow" the tree by attaching edges to the first available entry point they see without crossing a red line.

Permutree insertion and permutree lattice

The result is a leveled permutree. Decorated permutations are in bijection with leveled permutrees. The permutree itself is the graph in black oriented from bottom to top. By "forgetting" the levels, we obtain a surjection between decorated permutations and permutrees. The fiber of a permutree is the set of the linear extensions of the graph. These fibers correspond to the permutree congruence defined in Section 7.1. Indeed, if δ = n , then there is no red line and the permutree is a linear graph labeled by the permutation (see the first example of Figure 7.5). If δ = n , the algorithm is the binary search tree insertion described in Section 2.2 (see the second example of Figure 7.5). If δ ∈ { , } n , this is the Cambrian tree insertion that can be found in [START_REF] Chatel | Cambrian Hopf algebras[END_REF]. If δ = n , each node is directly attached to the previous one and is either above or below: this gives a binary sequence as described in Section 2.8. The description of the permutree congruence classes as the linear extensions of permutrees gives the characterization of the minimal (and also maximal) elements which we explained in Section 7.1. Actually, it describes the possible local moves on any decorated permutation within a congruence class. Indeed, the permutree congruence is the transitive closure of two local rules . . . ac . . . b . . . ≡ . . . ca . . . b . . . ,

. . . b . . . ac . . . ≡ . . . b . . . ca . . . ,

where a < b < c and the written decoration on b are the necessary requirements (there an be extra decorations on a, b and c). See the example given on Figure 7.6. We have that 7251346 ≡ 2751346 as we are able to exchange 7 and 2 because they have a witness on the right (either 4 or 6) with a down decoration. You can check indeed that the two levels permutrees are different but that the underlying permutrees are similar. Similarly, we have 2751346 ≡ 2715346 because 5 and 1 can be exchanged thanks to the witness 2 to the left with an up decoration. Each decoration δ defines a lattice congruence [PP18, Proposition 2.13]. We thus obtain δ-permutree lattices (see Figure 7.7). The rotation on permutrees is natural generalization of the rotation on binary trees.

Numerology

There is a very natural question: given a certain decoration δ, how many δpermutrees are there? This also corresponds to counting the equivalence classes. It is known for some decorations giving specific subfamilies: the factorial numbers for permutations, the Catalan numbers for binary and Cambrian trees, and the powers of 2 for the binary sequences. In general, we call this the factorial-Catalan number C(δ) and provide a recursive formula which interpolates between the factorial and Catalan numbers. Indeed, the Catalan numbers satisfy a well known recursion

C n = n-1 k=0 C k C n-1-k (7.3)
with C 0 = 1. On the other hand, the factorial numbers satisfy

n! = n(n -1)! = n i=1 (n -1)!. (7.4)
The idea is then to mix those two summations depending on the actual symbols of δ. The first essential property is given in [PP18, Corollary 2.21]: only the positions of the and matter. In particular a symbol can be changed into a without changing the value of C(δ). Besides, the case of the symbol is actually trivial. If δ i = , we have that C(δ) = C(δ 1 . . . δ i-1 )C( δ i+1 . . . δ n ). For example, for δ = , we indeed get

C(δ) = C( )C( )C( ) = 2 3 . (7.5)
Then for δ ∈ { , , } n , we get a recursive formula summing over all possibilities to remove one symbol,

C(δ) = δ i = C(δ 1 . . . δ i-1 δ i+1 . . . δ n ) + δ i ∈{ , } C(δ 1 . . . δ i-1 )C(δ i+1 . . . δ n ). (7.6)
When the removed symbol is , we simply sum on the decoration of size n -1 as in (7.4). When the removed symbol is or , the word is split into two parts as in (7.3). Using these rules, we can compute the number of permutrees for the examples of Figure 7.7.

C(

) = 2C( ) + C( )C( ) + C( ) (7.7) = 2 × 5 + 2 + 6 = 18 (7.8) C( ) = C( )C( ) ( 7
.9) = 2 × 5 = 10 (7.10)

Permutreehedra

The weak order, the Tamari lattice, the Cambrian lattices, the boolean lattice: the Hasse diagrams of these lattices all correspond to the skeletons of certain polytopes which are all generalized permutahedra [START_REF] Postnikov | Permutohedra, Associahedra, and Beyond[END_REF]. A generalized permutahedron is a polytope where every edge follows the direction of a permutahedron edge e i -e j . When we drew our first permutree lattices, they "looked nice" in the sense that it felt like it was the graph of a polytope. For example, in size n, any element is adjacent to n -1 elements: this is a characteristic of vertices in a simple polytope. Indeed, we realized that we could generalize Loday's construction of the associahedron (See Section 2.4) and obtain a geometrical realization of the permutree lattices. More precisely, for every decoration δ, we define a polytope PT(δ) called the permutreehedron as the convex hull of the vertices a(T) for T a δ-permutree. Each coordinate of a(T) is computed as follows:

a(T) i =          1 + d if δ i = , 1 + d + ℓr if δ i = , 1 + d -ℓr if δ i = , 1 + d + ℓr -ℓr if δ i = ,
where d is the number of descendants of i , ℓ and r are the number of left and right descendants of i, and ℓ and r are the number of left and right ascendants of i. For example, the coordinates of the permutree of Figure 7.4 are [7, -4, 3, 8, 1, 12, 1].

Theorem 11 (Theorem 3.4 of [PP18]). For each decoration δ, The permutreehedron PT(δ) is the polytope corresponding to the δ-permutree congruence.

The word "corresponding" here refers to the polyhedral fan of the polytope. In [Rea05], Reading gives the explicit fan corresponding to any lattice quotient of the weak order of a Coxeter group. In particular, this describes the δ-permutree fan of which the permutahedron fan is a refinement. Our theorem states that the permutreehedron indeed realizes the permutree fan. This includes in particular that the Hasse diagram of the lattice is the skeleton of the polytope.

Beside, we can also construct the permutreehedron as a removahedron as in Section 2.5. Recall that the faces of the permutahedron can be represented by ordered partitions (see Section 1.6). The facets correspond to partitions of 1, . . . , n into two sets I and J. For the permutreehedron, we only keep the facets that correspond to an edge cut of a permutree. For each oriented edge between two vertices of a permutree, the edge cut partitions 1, . . . , n into two sets I and J. I contains all the vertices connected to the source of the edge and J all other vertices. For example, on the tree of Figure 7.4, the different values for I are {2, 3, 4, 5, 6, 7}, {1, 2}, {1, 2, 3}, {5}, {1, 2, 3, 4, 5}, and {7}. These are all the facets containing the tree.

Figure 7.8 shows all permutreehedra for decorations of size 4. You can see the correspondence with Figure 7.6. When we add an orientation to an edge of the Dynkin diagram, this corresponds combinatorially to coarse the lattice congruence, i.e., to merge some congruence classes together. Geometrically, this corresponds to removing some facets so that the polytopes can be seen inside one another.

In [START_REF] Pilaud | Quotientopes[END_REF], Pilaud and Santos proved that all lattice congruence of the weak order can be realized a generalized permutahedra. But their realization is not the same as the one of permutreehedra. In particular, the quotientopes are not removahedra. Actually, it was proven in [START_REF] Albertin | Removahedral congruences versus permutree congruences[END_REF] that the permutree congruences are exactly the congruences that can be realized as removahedra.

Schröder permutrees

We define a concept of Schröder permutree which are the equivalent of Schröder trees for the permutrees (see Section 2.5). They correspond to permutrees where some nodes have been merged together. It gives a combinatorial description to the faces of the permutreehedra. Most properties and operations on permutrees easily generalize to Schröder permutrees. We have an insertion algorithm (from ordered partitions), a congruence relation, and a counting formula. The congruence is a lattice congruence from the facial weak order and thus we obtain a facial order on Schröder permutrees as illustrated on Figure 7.9.

(picture from [PP18]) Figure 7.9: The Schröder permutree lattices for 3 , 3 , 3

Hopf algebras

We have seen in Section 1.5 the definition of the Malvenuto-Reutenauer Hopf algebra (FQSym) and how it relates to the weak order. In particular, the sylvester congruence not only define a lattice congruence but also the Loday-Ronco Hopf algebra on binary trees as a subalgebra of FQSym (or, dually, a quotient Hopf algebra). The same construction extends to permutrees. For this, we use a decorated version of FQSym. Basically, the product is now defined on decorated permutations and the decoration moves along with the value it is attached to as in the following example.

F 231 • F 12 = F 23145 + F 2341 + F 24315 + F 23451 + F 42315 (7.11) + F 24351 + F 42351 + F 24531 + F 42531 + F 45231 .
Conversely, on the co-product (or the product in the dual Hopf algebra), the decoration is attached to its position as in

G 312 • G 12 = G 31245 + G 41235 + G 41325 + G 51234 + G 42315 (7.12) + G 51324 + G 52314 + G 51423 + G 52413 + G 53412 .
We define a basis indexed by permutrees. The element indexed by a permutree T is a sum over all decorated permutations σ whose insertion algorithm results in T : these are the linear extensions of the tree or, equivalently, all the elements of the permutree class. See the example below for the tree of Figure 7.4.

P = F 2135476 + F 2135746 + F 2137546 + • • • + F 7523146 + F 7523416 + F 7523461 .
Theorem 12 (Theorem 4.5 of [PP18]). The elements (P T ) where T is a permutree form a Hopf subalgebra of the decorated version of FQSym.

On Figure 7.10, we show two operations on permutrees (grafting and cutting) which give a direct combinatorial descriptions of the product and coproduct. Besides, by duality, the dual Hopf algebra is a quotient of the decorated dual of FQSym and we also obtain direct descriptions of the operations. A similar construction can be made on Schröder permutrees using a decorated version of the Chapoton Hopf algebra on the faces of the permutahedra [START_REF] Chapoton | Algèbres de Hopf des permutahèdres, associahèdres et hypercubes[END_REF].

Reduced words and other groups

Cambrian lattices are defined for all finite Coxeter groups. In particular, the minimal elements of each class are proved to be the c-sortable elements as we explain in Section 2.6. The concept of permutree congruence can also easily be extended to other finite Coxeter groups but the identification of minimal class elements turns out to be more difficult than for the the Cambrian case.

Indeed, the c-sorting algorithm can be seen as a generalization of classical stack sorting (which would correspond to the choice of s 1 . . . s n-1 as a Coxeter element in type A). From an algorithmic point of view, the c ∞ word is a sorting network. At each step, we try to apply a certain operation if possible. The list of operations to "try" is decided in advance and does not depend of the success / failure of the previous operations. The list of operations actually applied give us a subword of c ∞ which identifies if an element is minimal in its Cambrian class or not. The most natural question would then be: is there such a sorting network for all permutree congruences? We give a negative answer in [PPTJ23, Remark 5.9] which indicates that the characterization of the permutree classes in general is a difficult problem.

Our approach in [START_REF] Pilaud | Permutree sorting[END_REF] is to study the reduced words of minimal permutations in the permutree classes in type A. The basic case corresponds to orienting exactly one edge of the Dynkin diagram, i.e., to contract the side of exactly one hexagon. We can then construct the U(j) automaton of Figure 7.11 which corresponds to orienting the edge (j -1) ← j. Even though we have not explicitly drawn the looping transitions, this is a complete automaton: at each state, any transposition s i can be read. Only the transitions that result in a change of state are written explicitly. The states of the first and second line are accepting states whereas the states in the third line are rejecting states.

Theorem 13 (Theorem 1.1 of [START_REF] Pilaud | Permutree sorting[END_REF]). A permutation is minimal in its permutree class if and only if it admits a reduced word accepted by the automaton.

For example, in size 4, for U 2 , corresponding to the orientation 1 ← 2 --3 of Figure 7.1 (left), the reduced word s 2 s 1 s 3 is accepted which means that the permutation 3142 is minimal in its class. On the other hand, s 1 s 2 (permutation 2314) and s 2 s 1 s 2 s 3 (permutation 3241) are rejected by the automaton. You can check that it is the case of all their reduced words and they are not minimal in their classes.

We actually provide an algorithm so that, given a permutation, only one reduced word needs to be tested in the automaton. This offers a new characterization of minimal permutree classes elements besides the pattern avoidance, just like stack sortable permutations correspond to 231-avoiding permutations. By taking products of automata, we generalize our algorithm to all permutree congruences in type A.

Open questions

We believe that similar automata can be found for other types of finite Coxeter groups. Daniel Tamayo worked on this subject during his thesis under the supervision of Vincent Pilaud and myself. We were able to find a general rule for type B. For type D, we could find some automata that worked in small sizes but we do not have a general rule at this date. From our observations, the general case automata (if they exist) in types different than A and B are much more elaborate. In type A especially, many simplifications arise, giving very simple automata.

More generally, there are still many areas to explore for permutrees in other Coxeter groups. For example, can we obtain the permutreehedron as Coxeter removahedra and do the results of [START_REF] Albertin | Removahedral congruences versus permutree congruences[END_REF] can be extended? We would also like to consider permutrees as subsets of root systems like in the work of Gay and Pilaud [START_REF] Gay | The weak order on Weyl posets[END_REF].

CHAPTER 8

THE S-WEAK ORDER AND S-PERMUTAHEDRA I just knew there were stories I wanted to tell.

-Octavia E. Butler

As I was working on the m-Tamari lattices by the end of my thesis, I wondered what was the equivalent of the weak order in the m-Tamari case. This is indeed a very natural question considering the many links between the weak order and the Tamari lattice in combinatorics, geometry and algebra. I studied the mpermutations, i.e., the permutations with m copies of each letter. I was interested in the lattice properties and at the same time, Novelli and Thibon were working on m versions of the Hopf algebraic structures. In this context, the notion of metasylvester congruence was introduced in [START_REF] Novelli | Hopf algebras of mpermutations, (m + 1)-ary trees, and m-parking functions[END_REF]. This lead me to define the metasylvester lattice in [START_REF] Pons | A lattice on decreasing trees : The metasylvester lattice[END_REF].

Even though I am very interested in all the geometric aspects related to my work, my own background and approach is very much on the combinatorial side. In 2014, I could "see" that this new lattice of mine was "nice" and looked like a permutahedron that had been cut into smaller pieces, but I had no idea how to formalize that property. Around this time, I attended a talk by Cesar Ceballos at Séminaire Lotharingien de Combinatoire where he presented the results he obtained with Padrol and Sarmiento on the realization the ν-Tamari lattices [START_REF] Ceballos | Geometry of $\nu$-Tamari lattices in types A and B[END_REF]. I went to talk to him right after to show him my own work and see if we could work on a geometric realization together. This resulted in a fruitful collaboration which is still going on with many fascinating results and open questions. We presented a first version of our work at FPSAC 2019 [CP19]. In 2022, we released the first paper [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF] of a series of at least two. It covers the combinatorial aspects of [CP19] and is a generalization of [START_REF] Pons | A lattice on decreasing trees : The metasylvester lattice[END_REF]. We are working at the moment on the second paper [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF] where we cover the combinatorial definition of the s-permutahedra complex. In this Chapter, I present an overview of all these results as well as the many different leads for future work. Computations and examples are available here [START_REF] Pons | SageMath code and demo for s-weak order and spermutahedra[END_REF].

The metasylvester lattice

As the m-Tamari lattice is an upper ideal of the Tamari lattice of size n × m, it is a sublattice and a quotient lattice of a certain upper ideal in the weak order. It is actually more natural to look at the reversed m-Tamari which is a sublattice of the weak order on permutations where every letter is repeated m times as in Figure 8.1. where a < b < c. As an example, the classes on Figure 8.1 are the red shapes. As both local moves require to have a letter repeated, when m = 1, on the classical weak order, each permutation is its own class. Besides, a sylvester class as defined by (2.2) in Section 2.2 is a union of metasylvester classes. The metasylvester congruence is not a lattice congruence. Indeed, it is not compatible with the meet operation. For example, take σ = 121332 and µ = 131223. We have that σ ≡ 332112 and µ ≡ 311223. But σ ∧ µ = 112323 is not equivalent to 332112 ∧ 311223 = 311223. Nevertheless, the join operation is compatible and actually the maximal elements of the class have a nice characterization. They are Stirling permutations, i.e., permutations avoiding the pattern 121. They form a sublattice of the weak order and are in bijections with m-decreasing trees. In [START_REF] Pons | A lattice on decreasing trees : The metasylvester lattice[END_REF] I call this lattice the metasylvester lattice. This is actually a special case of the s-weak order which I defined with Ceballos in [CP19] and [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF].

The s-weak order

Let s be a sequence of s non negative integers. We define the s-decreasing trees. They are ordered rooted trees on n nodes labeled 1 to n such that the node i has s(i) + 1 children and so that the labels are decreasing from the root to the leaves. In particular, there are (1 + s

(n))(1 + s(n) + s(n -1)) • • • (1 + s(n) + • • • + s(2))
s-decreasing trees for a given sequence s. When s does not contain any zeros, then s-decreasing trees are in bijection with s-permutations: permutations where each letter i appears s(i) times and avoiding the pattern 121. The bijection is illustrated on Figure 8.2. When s = (m, m . . . , m), the s-permutations are the maximal elements of the metasylvester classes and so we have a lattice structure. This generalizes easily for all s without zeros: the s-permutations form a sublattice of the weak order. This is not the case when s contains zero but we can still extend the definition. We generalize the notion of tree inversion which was already introduced in [START_REF] Pons | A lattice on decreasing trees : The metasylvester lattice[END_REF]. Basically, the tree-inversions are a multiset where each inversion (b, a) appears with a certain cardinality #(b, a). The cardinality of (b, a) expresses where is a regarding b in the tree. If it is to the left or in the first subtree of b, then #(b, a) = 0. If it is to the right of b or in the last subtree, we have #(b, a) = s(b). The intermediate values correspond to the case where a belongs to a middle child of b. We show an example on Figure 8.3.

In particular, when s = (1, 1, . . . , 1), then s-decreasing trees are decreasing binary trees, in bijection with permutations. In this case, the tree-inversions are the classical value inversions of permutations: each cardinality #(b, a) can either be 0 (no inversion, a is before b) or 1 (b is before a). Another interesting case is when s contains some zeros: if s(b) = 0, then the node b has one child and #(b, a) = 0 for all a < b, independently of the position of a.

The tree-inversions form a multiset and we can generalize the notion of inclusion of classical sets. For two multisets T and S, we have T ⊆ S if, for all a < b, # T (b, a) ≤ # S (b, a). This gives a partial order on s-decreasing trees which we call s = (0, 0, 2, 1, 3) is also an inversion. A multiset of inversions is an s-tree inversion set if it is transitive and co-transitive (the non-inversions are also transitive). We actually call this second property the planarity of the set, it translates to: for all c > b > a such that #(c, a) = i, either #(b, a) = s(b) or #(c, b) ≥ i. It is easy to see that the tree-inversions of an s-decreasing tree satisfy these properties as illustrated on Figure 8.5. We prove that they are sufficient properties and give an explicit construction to recover the tree from the tree-inversions.

To prove that the s-weak order is a lattice, we then generalize the notions of union and transitive closure to multisets of inversions. The join of two sdecreasing trees is obtained by taking the transitive closure of the union of their tree-inversions. We also characterize the tree-ascents, i.e., the cover relations of the poset. Basically, a cover relation corresponds to moving a node i to the right. There are some technicalities in when and how we can do this move: nodes move by taking along their middle children but leave behind their left child. The nodes are not allowed to move if they have a strict right child. For example, on the tree of Figure 8.3, 1 and 2 are allowed to move to the right of 5 but not 3 because 2 is a strict right child of 3 (while 1 is not a strict right child of 2 because s(2) = 0). Furthermore, we prove that the s-weak order is polygonal, semidistributive and congruence uniform. These are all interesting lattice properties that are defined in particular in [START_REF] Reading | Lattice Theory of the Poset of Regions[END_REF]. It implies some properties on the the lattice congruences of the s-weak order. Our proof is based on the notion of HH lattices found in [START_REF] Caspard | Cayley lattices of finite Coxeter groups are bounded[END_REF]. It also uses some useful properties of the intervals of the s-weak order found in [START_REF] Lacina | Poset topology of $s$ weak order via SB-labelings[END_REF] who studies some topological properties of the lattice based on our initial extended abstract [CP19].

Link with the ν-Tamari lattice

In [START_REF] Pons | A lattice on decreasing trees : The metasylvester lattice[END_REF], I claimed that the m-Tamari lattice was both a sublattice and a quotient lattice of the metasylvester lattice. In [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF], we generalize and prove this result on the s-weak order. We define the s-Tamari trees: there are the trees such that #(c, a) ≤ #(c, b) for all a < b < c. This means that a node a cannot move faster to the right than a node b of greater value.

Theorem 15 (Theorem 2.2 of [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF]). The set of s-Tamari trees form a sublattice of the s-weak order. This is illustrated on Figure 8.6. We give explicit descriptions of the cover relations and prove that this is isomorphic to a certain ν-Tamari lattice as defined in Section 2.9 where ν is simply the reversed sequence s.

Besides, when s does not contain any zeros, then the s-Tamari lattice is a quotient lattice of the s-weak order and we give direct characterization of the congruence classes. In particular, the minimal elements of the classes are the s-decreasing trees. intervals. The s-permutahedra is the set of pure intervals on which we can define notions of containment, intersection and dimension.

The "dimension" of a pure interval is the number of selected tree-ascents. At this stage, this is a formal notion which should later correspond to the actual dimension of the polytope.

Not all intervals are pure intervals (just like not all intervals of the weak order are faces of the permutahedron). The first question we ask is then: if T ≼ S, how can we tell if this corresponds to a pure interval? We prove that there is a simple characterization using the variations of the interval, i.e., the inversions (b, a) such that # T (b, a) < # S (b, a). We define a notion of essential variation and show in particular that the selected tree-ascents of the pure interval are the minimal essential variations of the interval. This characterization leads to our main result in this paper.

Theorem 16 (from [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF]). The intersection of two pure intervals is a pure interval.

Besides, the dimension of the intersection is always smaller than or equal to the dimensions of the initial pure intervals. We reach equality only if one pure interval is already included in the other. You can check this property on Figure 8.7: the 2-dimensional faces can intersect only in an edge (pure interval of dimension 1) or in a tree (pure interval of dimension 0). To prove that the s-permutahedra is indeed a polytopal complex, we need to prove further that each pure interval can be realized as a polytope. We have serious leads for this result which I explain in Section 8.5. We hope to develop them in a sequel paper.

We can extend the definitions of pure intervals to the s-Tamari lattice and thus define the s-associahedron (see Figure 8.9). In this case, we can actually prove that it is a polytopal complex through a direct bijection with the ν-associahedron of Ceballos, Padrol and Sarmiento [START_REF] Ceballos | Geometry of $\nu$-Tamari lattices in types A and B[END_REF]. solution of our conjecture. I present here the current state of our (and other's) research and the perspectives we would like to explore.

Ascentopes

We do not prove yet in [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF] that the s-permutahedra is a polytopal complex. Nevertheless, we actually have a polytopal construction for each pure interval which we call the ascentope. An ascentope is a certain removahedron defined using an s-decreasing tree T and a set of selected tree-ascents. Experimentally, our construction gives a geometrical realization of the pure intervals. See Figure 8.11 for an example in 3 dimensions. We can compute the skeleton of the polytope and check that it corresponds to the Hasse diagram of the interval. We also computed f -vectors for big examples such as the one of Figure 8.12. The f vector gives the number of faces in each dimension. As we understand the faces combinatorially, we can check that the geometric results are consistent with our combinatorial construction: it is the case on all the examples we have computed. The next step is obviously to prove that this construction is indeed a realization of the pure intervals and to study the properties of this family of polytopes. Note that the ascentope realization does not solve the more general conjecture which requires to construct the polytopal complex as a polytopal subdivision. Indeed, there is no indication that the ascentopes can be "glued" together. Nevertheless, it would prove that the s-permutahedra is indeed a polytopal complex for all s.

Solving the conjecture

Since 2019 and [CP19], I have been mentioning the conjecture of the polytopal subdivision realization a few times. In particular, I had started discussing this Following this, Rafael González suggested that we look at the problem through the lens of flow polytopes. These are certain polytopes defined by flows on a graph which can be used to obtain triangulations and polytopal subdivisions [START_REF] Mészáros | Volumes and Ehrhart polynomials of flow polytopes[END_REF]. This looked very promising and I invited Éva Philippe and my PhD student Daniel Tamayo to join the research discussions. Together with an extended group of researchers, they came up with a certain flow polytope which gave a dual realization of the s-permutahedra. Even though the proof is not finalized yet, they were able to show me explicit bijections and coordinates to construct the polytopal subdivision. Their paper is in writing [GDMP + 23] and would partially solve the conjecture.

The construction of [GDMP + 23] only works for an s which do not contain zeros. The next natural step would then be to see if the result can be extended to the zero case. Besides, we also conjectured that the realization should give a realization of the s-associahedron. Is it the case? Can it be proved using flows? What is the link with the current realization of Ceballos, Padrol and Sarmiento [CPS16]? In both cases, Tropical geometry seem to be necessary to compute the vertices coordinates. Is there a realization which does not rely on this?

Besides, what are the polytopes we obtain for each pure interval? Are they removahedron or even generalized permutahedron? Are they related to the ascentopes that we have been defining with Cesar Ceballos?

Finally, the dual of the s-permutahedron seems to have interesting properties. It looks like a certain Shi-arrangement where some walls have been removed. We would like to study this construction to better understand its properties.

Lattice quotients and geometric realizations

We have proved that the s-Tamari lattice is a lattice quotient of the s-weak order when s does not contain any zeros. What are the other lattice quotients? In particular, Tamayo, Philippe and Pilaud have been working on some s-Permutrees with interesting combinatorial and geometrical properties. When s contains some zeros, the Tamari case defines another lattice which is not isomorphic to ν-Tamari: what is it? What are the elements counted by? Does it have an interpretation in terms of paths?

Other groups and other lattices

An natural question is also to look at other Coxeter groups. For this, the perspective of the generalized Shi-arrangement would be a good starting point. Do we also find polytopal subdivision? This is the case in type B for the Ceballos, Padrol and Sarmiento realization of the ν-Tamari lattices [START_REF] Ceballos | Geometry of $\nu$-Tamari lattices in types A and B[END_REF]. More generally, our approach through pure intervals works in many other combinatorial lattices with nice geometric realization. Is there a way we can extend our proof and characterizations to these other cases? Part V Experimental Approach approach of my own methods and to discuss it with historians and philosophers. In this context I was invited by Emmylou Haffner to give a talk at a seminar of mathematical history and philosophy in SPHERE [START_REF] Pons | Expérimentation manuelle et par ordinateur dans la recherche en combinatoire[END_REF]. Emmylou Haffner studies ancient mathematican's drafts to understand the creative process [START_REF] Haffner | Going to the source(s) of sources in mathematicians' drafts[END_REF] like in this post where she looks at Elie Cartan's drafts [START_REF] Haffner | Des calculs dans l'atelier de fabrication d' Élie Cartan[END_REF]. The seminar was coordinated by Arilès Remaki whose thesis focuses on Leibnitz [START_REF] Remaki | L'art combinatoire en tant qu'art d'inventer chez Leibniz, sur la période 1672-1680[END_REF] and especially on the combinatorial explorations that led to his work. Looking at Leibnitz's drafts with combinatorial pictures and computational tables makes an interesting connection with our own exploratory methods now enhanced by computer.

In this chapter, I use the research example that I presented in [START_REF] Pons | Expérimentation manuelle et par ordinateur dans la recherche en combinatoire[END_REF] to explain my research approach and unfold the early stages of research creation through experimentation using both the computer and "pen and paper". Then I give an overview of the research code that I have written for the past ten years and of the good practices that I have put in place to share, reuse and valorize this work.

The experimental process

When I gave this talk at the SPHERE seminar, I was in the middle of a research project that led to what I presented in Chapter 5. In particular, I was looking at a certain lattice structure on triangular Dyck paths which would give a combinatorial interpretation to some Schur expansions computed by François Bergeron. I decided to present this problem as a typical example of research investigation.

To understand objects

Looking at my drafts, it became apparent that my first task had been to "understand" the paper [START_REF] Bergeron | Combinatorics of triangular partitions[END_REF] that Bergeron presented to me when I arrived in Canada. On Figure 9.1, I show some initial drafts kept in my written notes. We see that I am recomputing some of the examples of [START_REF] Bergeron | Combinatorics of triangular partitions[END_REF] to familiarize myself with the material. I also started to code at this stage. I implemented several classes to represent triangular partitions and triangular Dyck paths along with methods to compute the properties described in the paper. For example, below is a piece of code which is part of the triangular partition class to test if another partition is similar in the sense of [START_REF] Bergeron | Combinatorics of triangular partitions[END_REF] d e f i s s i m c e l l ( s e l f , i , j , tau ) : r e t u r n s e l f . c e l l m i n s l o p e ( i , j ) < tau . m ea n s l o p e ( ) \ and tau . m e a n s l o p e ( ) <= s e l f . c e l l m a x s l o p e ( i , j ) d e f s i m c e l l s ( s e l f , tau ) : f o r i , j i n s e l f . c e l l s ( ) : i f s e l f . i s s i m c e l l ( i , j , tau ) : y i e l d ( i , j ) d e f i s s i m i l a r ( s e l f , tau ) : r e t u r n a l l ( s e l f . i s s i m c e l l ( i , j , tau ) \ f o r i , j i n s e l f . c e l l s ( ) )

The constant back and forth between my manual computations and examples and the automated ones is what ensures me that I am progressing on solid grounds. The manual computation and often manual enumeration of objects gives me the time to understand the processes to the point where I can code and automate the task. Doing so assures me that I have not overlooked a crucial detail or misunderstood a definition. Besides, sometimes the error is not mine. In the early paper draft printed to me by Bergeron, a typo had replaced a "≤" sign by a "<" sign: I was able to spot it when I tested the definition.

To eliminate false statements and generate counter example

Once I had read the paper, I wanted to study lattice structures on triangular Dyck paths to see if I could find a q, t enumeration of intervals that would be symmetric and Schur positive (as in the classical and m-Tamari cases). As there was a general definition of Tamari in [START_REF] Préville-Ratelle | The enumeration of generalized Tamari intervals[END_REF], my first attempt was to look at it and see if it "worked". I manually computed the first non-trivial example (see Figure 9.2) and noticed that, in this case, I had a q, t symmetry.

Here, the manual computation helps me understand how the ν-Tamari lattice translates into triangular partitions and gives me some initial insights on how the q, t symmetry could work. Of course, the immediate next step is to implement this. Below are the methods I used to generate the ν-Tamari lattice of triangular Dyck paths. d e f p a t h t a m a r i r o t a t e ( s e l f , l i n e ) : L = s e l f . s k e w p a r t i t i o n ( ) . r o w l e n g t h s ( ) p = l i s t ( s e l f . path (

) ) v = L [ l i n e ] p [ l i n e ]-=1 i = l i n e -1 w h i l e i >= 0 and L [ i ] > v : p [ i ]-=1 i -=1 r
e t u r n TriangularDyckPath ( s e l f . p a r t i t i o n ( ) , p ) d e f p a t h t a m a r i u p ( s e l f ) :

f o r l , c i n s e l f . path ( ) . c o r n e r s ( ) : y i e l d s e l f . p a t h t a m a r i r o t a t e ( l ) Figure 9.2: A manual computation of q, t symmetry on intervals of ν-Tamari

Once I had this, it quickly appeared that the ν-Tamari lattice did not give the desired q, t interval enumeration. It is actually very common that the computer exploration is here to save us time by rejecting false hypothesis early on. Not only does it tell us that some ideas are just wrong but it also exhibits interesting counter examples. In this case, the partition (3, 2, 2, 1) was the first truly interesting example where ν-Tamari would fail to provide a symmetric q, t enumeration of intervals. I could then concentrate my efforts on this particular partition.

The partition (3, 2, 2, 1) has 23 subpartitions and we expect to find 161 intervals in the "good" lattice: 161 is the result of a certain expansion of a Schur functions in 3 variables q, t, r and computing the polynomial for q = t = r = 1. This is exactly a case which is "in between" manual and automatic exploration. Indeed, 23 elements is rather small and manageable by hand while 161 starts to be a bit too big. My research at this point illustrates that. I was literally looking for the right lattice by manually guessing what the correct cover relations might be using my intuition and some indication from the Schur computation (see Figure 9.3). I would then hard code the lattice inside my program and compute the q, t enumeration of intervals.

Doing so, I was actually able to find a working structure for (3, 2, 2, 1) but could not deduce a general rule. But the multiple attempts has left me with a better knowledge of what works and what does not. This was proved to be true by Loïc Le Mogne in our paper [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF] (this is an extended abstract, the complete proof will actually appear in our future complete paper).

To find ideas and emit conjectures

Similarly, the final conjecture of [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF] which I explain in Section 5.3 has also been made possible by computer exploration. For example, the following function tests that the ν-Tamari enumeration of intervals is Schur positive for all triangular partitions whose top-down tableau is sim-sym.

# t e s t e d 3 . . 2 1 d e f t e s t s c h u r p o s i t i v e P R V s i m s y m ( n , q , t ) : f o r t r i n T r i a n g u l a r P a r t i t i o n s ( n ) : The interesting anecdote is that this function did not give a positive answer. Indeed, two of the Schur functions did not correspond. But it actually appeared that those Schur functions are very difficult to compute on the algebraic side. The functions I had received from Bergeron were actually missing some terms that he could not get at the time using his computational methods. I was able to guess the missing terms using my conjecture. This not only strengthened my belief that the conjecture was true but also gave indications that the combinatorial computation (as inefficient as it is) would actually turn out to be more efficient than the algebraic computation which requires extensive computational power to reduce very big matrices.

d = P R V q t d i s t r i b u t i o n ( t

To solve and to prove

As we saw, computer exploration helps us sort out positive and negative results before we even try to prove anything. This is of course useful at the investigation 9.2. WHAT TO DO WITH THE CODE? 123 stage but not only. Indeed, once we have a result that seems to be right and we are trying to prove it, we need to polish our statement as much as possible. Can we reduce the hypothesis? This other statement seems to just be a rephrasing, is this the case? I believe my statement A implies B, does the computer confirm that B is true? Finding the route to the final proof, we might extract lemmas or other statements and the computer tests will be of great assistance. I consider that I have a certain pool of objects on which I can experiment to observe the results and guide me through my understanding1 .

What to do with the code?

My current file for research code on triangular partitions has more than 2500 lines, not including the code written by my student Loïc Le Mogne. The code related to [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF] and [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF] is about 4500 lines. This contains implementations of the objects at stake and many test functions, failed attempts, leads, and so on. Very much like a draft paper, it is often badly written, with few comments and explanations. What is the value of this code? Does it have any and how can we use it?

Contributions to open-source

Computer exploration and experimental mathematics has developed with the general access to computer systems. As many mathematicians started to code, attempts to share the produced code has arisen. I have been using the SageMath computer system since the beginning of my thesis. I believe in the open-source philosophy that the code we produce should be made accessible to all. Some objects are wildly used in combinatorics: permutations, Dyck paths, binary trees, and so on. They can be used in SageMath as the result of previous developments by other researchers. SageMath actually contains the basic grounds for most mathematical topics as can be read in [ZFM + 13].

I have myself contributed to SageMath whenever I felt that the code I had developed could be useful to others. My larger contribution is the implementation of Tamari interval-posets [START_REF] Pons | SageMath ticket: Interval-posets of tamari[END_REF] following my paper [CP15]. Providing a direct implementation into SageMath was very useful in a research perspective: it helped Tamari interval-posets to become a major objects in the study of Tamari intervals as it could be used directly for computations. The initial class has been enriched by others, especially Frédéric Chapoton who works on this subject. Following my second paper [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF], we added together the rise-contact involution which I had implemented during my investigations [START_REF] Chapoton | SageMath ticket: Some new methods for Tamari interval-posets[END_REF]. Previously, I had also contributed to several methods on binary trees [START_REF] Pons | SageMath ticket: Adding new combinatorial maps to binary trees[END_REF]. These are just some examples, I have authored about 15 contributions and participated in about 50.

Other good practices

The road from writing research code for oneself and contributing to an opensource software (or develop a full independent software) is not easy. For one thing, much of the code we write for research does not belong to a general software like SageMath. A big portion of the code corresponds to failed attempts, or constructions that would eventually emerge in a different form in the final product. At this stage, it is not always easy to identify what part of our code should belong the common shared knowledge of a software like SageMath. Besides, the code we write for research almost never follows the coding standard of a final SageMath contribution or of a software that could be distributed. There is often a long road of cleaning and documenting and testing. This takes a very long time that we, realistically, might not have. The result is that some useful, imperfect, code might never get shared.

Even if the quality is low, I believe that research code is worth sharing, especially when it leads to a published paper. Indeed, if I used this code for my own investigation, it could be useful for others. The objects used in the paper might turn out to be reused in another paper. Somebody else might decide to turn them into a proper software contribution. Or maybe, another researcher just needs to compute extra examples for their own purpose. This is why I have taken the habit to publish the research code along with the paper even if it is not a proper contribution to an existing software or a finished product. I first started a single GitHub repo where I would just post my research scripts organized by thematics along with some examples and presentations written with Jupyter notebooks [START_REF] Pons | Public open-source SageMath research code and notebooks[END_REF].

I provided an open license directly on the GitHub repo making it explicit that the code can be reused and, for example, integrated into another open-source software. To be fully efficient, one also needs to provide some environment information about how to run the code . I thus chose to include a Docker file which contains for example what SageMath version has been used to write the code.

It became apparent that having only one repo for everything was not practical: I would often upgrade SageMath but not fix all my previous codes and the environment information would then be out of date. For my latest papers, I chose to create one repo per paper: this is what I did for [START_REF] Pons | An implementation of the Zeta map on Dyck paths area sequences[END_REF] as an annex to [START_REF] Pons | A description of the Zeta map on Dyck paths area sequences[END_REF]. I also have a specific code repo for this document [START_REF] Pons | HDR-notebooks[END_REF]. Finally, when I published the code related to [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF], I decided to create a specific archive of the code at the time of publication [START_REF] Pons | SageMath code and demo for s-weak order and spermutahedra[END_REF] using Zenodo. Indeed, as this code is still prone to be changed, it provides a link to a specific state of the software.

As a summary, here is a list of codes related to my different papers:

• Code related to Tamari interval-posets ([CP15] and [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF]) is available on my general repo [START_REF] Pons | Public open-source SageMath research code and notebooks[END_REF] with multiple demo notebooks. Some of it has been turned into SageMath contributions especially in [START_REF] Pons | SageMath ticket: Interval-posets of tamari[END_REF] and [START_REF] Chapoton | SageMath ticket: Some new methods for Tamari interval-posets[END_REF]).

• Code related to [PP18, CPP19, PP20] with a demo notebook is available on my general repo [START_REF] Chapoton | SageMath ticket: Some new methods for Tamari interval-posets[END_REF].

• Code related to [START_REF] Pons | A description of the Zeta map on Dyck paths area sequences[END_REF] with a demo notebook is available on a specific repo [START_REF] Pons | An implementation of the Zeta map on Dyck paths area sequences[END_REF].

• Code related to [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF][START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF] with multiple demos is available on a specific repo and as a Zenodo archive [START_REF] Pons | SageMath code and demo for s-weak order and spermutahedra[END_REF].

Note that the code related to [START_REF] Le | Deficit and (q,t)-symmetry in triangular Dyck paths[END_REF] that I mention in Section 9.1 is not yet published. Indeed, only an extended abstract has been published and the final paper is still in the making. Besides, Loïc Le Mogne also wrote some code and I would like to merge our contributions.

One reason for sharing this code is re-usability which is why I make the effort of providing a running environment and often some demo notebooks that I edit as I write the corresponding papers. Speaking with historians and philosophers of mathematics, I also see another purpose. This "unclean" code is an equivalent of an early draft. It contains mistakes, failed attempts, ideas that sometimes were never fully developed. In other words, it contains some information about the process itself. Wether we share those codes or not, they hold an epistemic value and should at least be kept.

CHAPTER 10

OUTREACH Se vouloir libre, c'est aussi vouloir les autres libres.

-Simone de Beauvoir, Pour une morale de l'ambiguïté.

In the past 10 years, I have been a promoter of the software SageMath and more generally of open-source development and free software. This has also led me to think more of my role as a scientist and the science community we build. In 2018, I gave the opening keynote at the programming event PyCon Fr. I developed the idea that scientists and open source developers share a common ethic and motivation: we want to create knowledge and share it, we want contribute and to collaborate, we want our work to last to be re-used and improved.

Following this idea, it is important for me to take an active part in science communication and outreach at different levels. Within the math community, I work at promoting open-source software and programming knowledge in general. Within the scientific community at large, I have made presentations to explain the process of experimental mathematics. I also talk to general audiences and especially to middle and high schools to explain and share what research in mathematics and computer science mean. In this chapter, I give a general overview of this work.

Advocate for open science

Open science is the general idea that science productions should be made accessible to all: papers, data, software, etc. In mathematics and computer science, it concerns especially open-source software. Between 2015 and 2019, I have been part of the OpenDreamKit project which was coordinated in my university Paris-Saclay and included 18 institutions and about 50 participants. We received significant funding that was used mostly for two things: hiring full paid developers to work on open-source software and organizing events within the different communities to foster collaboration and development.

I was the local coordinator for Paris-Saclay as well as the work package leader for "Community Building, Training, Dissemination, Exploitation, and Outreach".

In the 4 years of the project, we were part of 110 events: either organized by members of the project or where they participated in a significant way. I was myself part of 23 events. For example, I co-organized the event "Free Computational Mathematics at CIRM" in 2019. The project also included 3 reviews in front of a European commission in which I took an active part presenting the activities of the project.

My implication as a promoter of open science goes beyond my role in the project. I have organized several Sage Days workshop, even before the begining of OpenDreamKit. In 2015, I organized a joint event at PyCon US to help build relations between the SageMath community and the open-source community at large. At this occasion, I gave a presentation at the main conference to explain the concept of experimental mathematics [START_REF] Pons | Experimental pure mathematics using Sage[END_REF] to many non-mathematicians.

I also participate in the effort to build a better scientific ecosystem, especially concerning scientific publications. I was an editor for the Journal of Open Source Software between 2019 and 2022 to help better recognize the role of open-source development in scientific progress. I have also accepted a role as backend editor for the new journal Combinatorial Theory which is owned directly by its editorial board and charge no fees neither for readers nor writers.

Building a more inclusive community

An open-source software is often free in the sense of "free of charge" (French word: "gratuit") and always free in the sense "free to be reused and shared" (French word: "libre"). But this is not enough to make it equally accessible to all. This is also true for mathematics and computer science in general. Technical and societal barriers exist which affect certain demographics more than others.

Women especially suffer from negative stereotypes early on in relations to science and mathematics. This affects their own confidence and ability to solve problems [START_REF] Désert | La menace du stéréotype : une interaction entre situation et identité[END_REF], the way they are perceived by others [MDB + 12], and their career choices [START_REF] Nils | Chapitre 4. Genre et orientation scolaire et vocationnelle[END_REF]. Danica Savonick and Cathy N. Davidson have collected several studies on gender bias in academia and its combinations with other bias such as racism [START_REF] Savonick | Gender Bias in Academe: An Annotated Bibliography OTHER BIBLIOGRAPHIC REFERENCES of Important Recent Studies[END_REF]. As a result, women are largely underrepresented in mathematics and computer science [START_REF] Brisbin | Women's Representation in Mathematics Subfields: Evidence from the arXiv[END_REF]. I have myself expressed the burden of being the only woman in a blog post [START_REF] Pons | Being the only woman -OpenPyViv[END_REF]. This has led me to take different actions. I have participated in many events such as the exhibition organized by Femmes et mathématiques [FetM22] to help make women in science more visible, especially to young girls. But I am also interested in building a better environment for current women scientists. For example, I run the PyLadies parisian chapter between 2016 and 2020 where I organized weekly meetup with many women developers. I noticed that even at a very high level, women lack confidence in their ability to code and would be reluctant to join coding events such as Sage Days which often show a worst gender disparity than classical mathematics events. As part of the OpenDreamKit project, I organized in 2017 and 2019 Women in Sage events which were Sage Days workshops targeted at women. They were a great success. You can see some pictures on Figure 10.2 and read the reports I published online [START_REF] Pons | Report on WomenInSage • OpenDreamKit[END_REF][START_REF] Pons | Report on second Women In Sage • OpenDreamKit[END_REF].

Actual borders are physical barriers that stop people from doing research. Indeed, most resources are concentrated in "western" countries. In many parts of the world, students and researchers lack funding, basic infrastructure or even access to advanced education. This is visible in open-source software: see the big African gap on the SageMath developer map on Figure 10.3. In 2019, two Nigerian women were supposed to join us at our Women in Sage event organized in Archanes, Greece. Their trip was fully paid by the OpenDreamKit project but they could not get their Visa in time. Nevertheless, the same year we had 3 Nigerian researchers coming to our other event "Free Computational Mathematics at CIRM". They enjoyed the event very much and we decided to co-organize Sage Days in Nigeria the following summer. I did not attend myself as I was literally having a baby the same week. The project funded the trip of some SageMath instructors and relied on Ibadan university for local organization. It was a great success (see [START_REF] Bray | Report on Sage Days 102[END_REF]) and also an indicator for the need of such events in West Africa as well as a lesson for us SageMath developers on how we can improve our software to allow an easier access. In 2021, I co-organized and participated remotely to a Women in Sage event in Senegal organized by Eliza Lorenzo. She was a participant to the Women in Sage event I held in Paris in 2017. I had advertised the event to my contacts in Nigeria and some researchers from Ibadan were able to attend. This shows that these events create a good dynamic that can help West African researchers to reinforce their scientific network. Thanks to these events, I formed connections with two researchers: Ini Adinya from Nigeria and Olivia Nabawanda from Uganda with whom I try to build a scientific collaboration despite the systemic difficulties.

Thanks to OpenDreamKit, I was also able to attend the event ECCO (Colombia) in 2016 and 2018 as a SageMath instructor. These were extremely reward-ing experiences (see [START_REF] Pons | An Inclusive Maths Conference: ECCO 2016[END_REF][START_REF] Pons | I want to do science the Colombian way[END_REF]). The Colombian community in combinatorics has made great work in building an inclusive space and bringing Colombian and international students together. Following these events, I became a co-organiser for ECCO 2022, especially in charge of the CIMPA application and funding. I am now part of the ECCO Steering committee whose role is to organize future events. Besides, ECCO 2018 is where I met Daniel Tamayo Jiménez who is now finishing his PhD under my supervision and joined supervision of Vincent Pilaud.

Political mathematics

There is a general belief that mathematics is politically neutral. Indeed, a theorem expresses a certain truth under some hypothesis, can it be racist or sexist? I do not believe this is the right question. Theorems are written by people in a certain context. Us, mathematicians, are part of a society which is, by nature, political. In [START_REF] Godement | Analyse mathématique I : Convergence, fonctions élémentaires[END_REF][START_REF] Godement | Analyse mathématique II : Calcul différentiel et intégral, séries de Fourier, fonctions holomorphes[END_REF], Roger Godement writes extensive preambles and notes to its books on Mathematical analysis. He questions the scientific responsibility of scientists in the creation of deadly weapons such as nuclear bombs. He also shows how political contexts and decisions impact what kind of science is considered good or interesting and thus developed.

In algebraic combinatorics, the long term applications of what we do, if they exist, may seem too far in the future to raise our concern. But this should not blind us in the illusion that what we do has no political implication. Defending fundamental science and the pursuit of knowledge for its own sake is already a political statement. Defending open-source software and open science is a political statement. Besides, there is the question of how we do mathematics, who do we teach it to, how do we teach it, etc. Federico Ardila develops this idea in [START_REF] Ardila-Mantilla | CAT(0) Geometry, Robots, and Society[END_REF] and asks important questions about power.

Without any advanced statistical examination, I can say that I teach computer science mostly to young men and thus I am participating in a system which deprives young women of a useful knowledge in our society (I have chosen the gender disparity but, of course, many other inequalities are just as problematic).

The academic system we are part of has some positive values and qualities and also some important setbacks. Of course, we cannot solve it all by ourselves. But we can choose to place our scientific activity in the general context of society and not see it as neutral. We can think about what we do and improve when we can. This is the choice I am always trying to make. This is also why I chose to include this last chapter. Not only does it relay some important activities I have run for the last 10 years but I consider these activities to be part of my scientific commitment just as much as my mathematical results.

CLOSING REMARKS

Truth is a matter of the imagination.

-Ursula K. Le Guin, The Left Hand of Darkness.

I consider algebraic combinatorics to lie at the intersection of algorithmics and mathematics. My goal is to understand the inner structure of objects to exhibit the connection between topics that seem distant in nature. This is the case with the Tamari lattice and the Tamari intervals especially which I present in Chapters 3, 4, and 5. They appear in the context of planar maps as well as in representation theory. If I sometimes answer questions as in [START_REF] Pons | The Rise-Contact involution on Tamari intervals[END_REF], most of my papers actually create new structures, like permutrees [PP18], or the s-weak order [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF]. My hope is that those new objects deepen our understanding of the permutahedron and associahedron and create new points of views to explore.

My motivation comes from difficult open questions. I have mentioned the q, tsymmetry of Catalan numbers in Chapter 5. To finish this document, I present two other open problems which have caught my attention recently. The Tamari lattice and its generalization the ν-Tamari lattice can be understood in the more general framework of pipe dreams and subword complexes [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multiassociahedra[END_REF]. More precisely, pipe dreams are certain objects associated to permutations (each permutation gives a collection of pipe dreams). All pipe dreams of a given permutation are related through flips and we can define a poset of increasing flips. For specific permutations, this gives the Tamari and ν-Tamari lattices. In general, this is not a lattice but, in [START_REF] Rubey | Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs[END_REF], Rubey conjectures that it is indeed a lattice when flips are restricted to chute moves. Beside, interesting geometrical structures appear which look like polyhedral complexes based on pure intervals like in our work on s-permutahedra [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF].

The second problem is related to the flip distance of triangulations. In [START_REF] Daniel | Rotation distance, triangulations, and hyperbolic geometry[END_REF], Sleator, Tarjan, and Thurston prove a fundamental result on the associahedron. The diameter, i.e., the maximal rotation distance between two binary trees, is linear in the dimension n. The exact value was computed by Pournin in [START_REF] Pournin | The diameter of associahedra[END_REF].

But it leaves open the following: what is the complexity of computing the minimal rotation distance between two given trees? This is the same as computing the minimal flip distance between two triangulations of a convex polygon. When the polygon is not convex, it is NP-complete [START_REF] Aichholzer | Flip Distance Between Triangulations of a Simple Polygon is NP-Complete[END_REF] but the proof cannot be extended to the convex case. Besides, remember that the associahedron is in between the permutahedron and the cube. In the permutahedron, the diameter is the maximal number of inversions, n(n-1) 2 . In the cube, it is n. The minimal distance is also easy to compute in both those polytopes. Indeed, the distance between two permutations σ and µ is the number of inversions of µσ -1 , and can be computed in O(n 2 ). In the cube, the distance between two binary sequences is just the number of bits which are different. So it is computed in O(n) where n is the size of the sequence. It is interesting to notice these questions are easy in those two polytopes but difficult for the associahedron. What about permutreehedra and other generalized permutahedra? Can we use what we understand from the relations of these polytopes with the permutahedron and the cube to study those questions?

Solving such problems is a long term goal that fuels my current research. With each attempt, come new ideas that will flourish in unexpected manners, adding to the general understanding of the underlying structures. Besides, in addition to working on these questions myself, I believe that my role is to foster the scientific environment that makes progress possible. Encourage seminars, collaborations, workshops, open discussions, and freedom of investigation. This is the role I take especially as PhD advisor. With each of my students, I have tried to find the right balance between providing problems and questions and giving them the opportunity to express their own ideas and build their own research path. When I ask an open question, I do not always expect a final answer. I expect attempts and ideas. Then I am here to guide them through it, in a collaborative manner, to see where it could lead us. Sometimes, it eventually answers the original question, sometimes it opens new routes that we had not seen beforehand.

Someone told me an anecdote that they were once asked "In your field, what do you think the next breakthrough is going to be?". I do not believe this is an interesting question. Breakthroughs do not happen because we chase after them (and their very nature makes them impossible to predict). They happen because we let our mind open to new ideas and keep inventing new truths.

Glossary

PyLadies is an international mentorship program to support women who code in python. 129

Sage Days are workshop dedicated to the software SageMath.

7 .

 7 11 The automaton U(j) to. . . . . . . . . . . . . . . . . . . . . . . . 8.1 The lattice of 2-permutations (left) with metasylvester classes and the corresponding s-weak order. . . . . . . . . . . . . . . . . . . . 8.2 An s-decreasing tree and the corresponding s-permutation. . . . . 8.3 An s-decreasing tree and its tree-inversions. . . . . . . . . . . . . 8.4 Examples of s-weak lattices. . . . . . . . . . . . . . . . . . . . . . 8.5 Illustration of the transitivity and planarity conditions on s-tree inversion sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

9. 3

 3 Manual attempt to obtain the desired lattice structure on partition (3, 2, 2, 1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4 Manual enumeration of triangular Dyck paths to define the tableau deficit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Figure 1.1: The permutahedra of dimensions 2 and 3 drawn by SageMath

Figure 1

 1 Figure 1.2: The permutahedron as a reflection group.

Figure 1 . 3 :Figure 1

 131 Figure 1.3: The left and right weak orders on S 3 .

Figure 1 . 5 :

 15 Figure 1.5: An example of a non-lattice

Figure 1 . 6 :

 16 Figure 1.6: The possible connected Dynkin diagrams of finite Coxeter groups Image under CC BY-SA 3.0 from Wikimedia Commons

Figure 1 . 7 :

 17 Figure 1.7: Inequalities in the plane defined by x 1 + x 2 + x 3 = 6.

Figure 1 . 8 :

 18 Figure 1.8: Ordered partitions as faces of the permutahedron.

(

  Figure 2.1: The Tamari lattice on parenthesized words

Figure 2

 2 Figure 2.2: Example of a lattice which is not a sublattice.

Figure 2

 2 Figure 2.4: Binary search tree insertion and linear extensions

Figure 2 Figure 2 . 7 :

 227 Figure 2.6: The Tamari lattice as a quotient of the right weak order (n = 3)

Figure 2 . 8 :

 28 Figure 2.8: Tamari rotation on Dyck paths

Figure 2 .

 2 Figure 2.11: The associahedra of dimensions 2 and 3 drawn by SageMath

Figure 2 .

 2 Figure 2.12: Permutahedra inside of associahedra

Figure 2 .

 2 Figure 2.13: Faces of the associahedron as Schröder trees.

Figure 2

 2 Figure 2.16: Product of PBT as an interval of the Tamari lattice

  Figure 2.18: The m-Tamari lattice and a ν-Tamari lattice

Figure 3 . 1 :

 31 Figure 3.1: Landscape of bijections between objects counted by Tamari intervals

Figure 3

 3 Figure 3.2: Construction of Tamari interval-posets from binary trees

Figure 3 . 3 :

 33 Figure 3.3: Decreasing and increasing forests of two incompatible trees.

  final forest of the Dyck path.

  Figure 3.4: Bijection between Dyck paths and decreasing and increasing forests

Figure 3

 3 Figure 3.5: Composition of interval-posets

Figure 3 Figure 3 . 7 :

 337 Figure 3.6: Bijection between closed flows and Tamari interval-posets

Figure 3

 3 Figure 3.8: Decomposition of m-binary trees and example for m = 2.

Figure 3

 3 Figure3.9: An m-Tamari interval-poset and its corresponding grafting tree.

Figure 3

 3 Figure 3.10: Bijection between interval-posets and triangulations

Figure 4 . 2 :

 42 Figure 4.2: The left-branch involution on Tamari intervals

Figure 4 . 3 :

 43 Figure 4.3: Tamari inversions on an interval-poset and grafting tree

4. 5 .

 5 THE EXPAND-CONTRACT OPERATION ON M -TAMARI INTERVALS57 I J = β(I)

Figure 4 . 4 :

 44 Figure 4.4: The rise-contact involution on Tamari intervals

Figure 4 . 5 :

 45 Figure 4.5: The expand operation on m-grafting trees

Figure 5 . 1 :

 51 Figure 5.1: Dyck paths of size 3 as sub-partitions of (2, 1)

Figure 5 . 2 :

 52 Figure 5.2: The triangular partition (4, 3, 1) and the non-triangular partition (4, 4).

Figure 5

 5 Figure 5.3: A Dyck path (as a sub-partition) with its area and area sequence.

Figure 5 . 4 :

 54 Figure 5.4: An example of the inverse zeta map bijection

Figure 5 . 5 :

 55 Figure 5.5: Similar cells, Triangular young tableau and deficit

Figure 5 . 6 :

 56 Figure 5.6: Construction of the triangular tableau

Figure 6

 6 Figure 6.1: Permutations, binary trees, and binary sequences as integer posets

Figure 6 . 3 :

 63 Figure 6.2: Construction of a weak order interval-poset

Figure 6

 6 Figure 6.4: The boolean lattice (on the left) and the weak order (on the right) on integer relations.

Figure 7 . 1 :

 71 Figure 7.1: Two examples of permutree congruences.

Figure 7 . 3 :

 73 Figure 7.3: The labeling rules on permutrees.

Figure 7 . 4 :

 74 Figure 7.4: The insertion algorithm on the decorated permutation 2751346.

Figure 7 . 5 :

 75 Figure 7.5: Leveled permutrees corresponding to a permutation (left), a leveled binary tree (middle left), a leveled Cambrian tree (middle right), and a leveled binary sequence (right).

Figure 7 . 6 :

 76 Figure 7.6: The permutree congruence on decorated permutations.

Figure 7 . 7 :

 77 Figure 7.7: The δ-permutree lattices, for the decorations δ = (left) and δ = (right)

Figure 7

 7 Figure 7.8: The permutreehedra, for all decorations δ ∈ • { , , , } 2 • .

Figure 7 .

 7 Figure 7.10: Grafting two permutrees (left) and cutting a permutree (right).

Figure 7 .

 7 Figure 7.11: The automaton U(j) to.

Figure 8 . 1 :

 81 Figure 8.1: The lattice of 2-permutations (left) with metasylvester classes and the corresponding s-weak order.

Figure 8 . 2 :

 82 Figure 8.2: An s-decreasing tree and the corresponding s-permutation.

Figure 8

 8 Figure 8.3: An s-decreasing tree and its tree-inversions.

Figure 8

 8 Figure 8.5: Illustration of the transitivity and planarity conditions on s-tree inversion sets.

Figure 8

 8 Figure 8.11: A pure interval and its corresponding ascentope

f

  Figure8.12: A pure interval of dimension 9 with the f vector of its ascentope.

Figure 9 . 1 :

 91 Figure 9.1: Pictures of early drafts of triangular partitions and Dyck paths

120CHAPTER 9 .

 9 Figure 9.3: Manual attempt to obtain the desired lattice structure on partition (3, 2, 2, 1).

  Figure 9.4: Manual enumeration of triangular Dyck paths to define the tableau deficit.

10. 2

 2 Talking about research to non researchers I also invest myself in promoting and explaining research to non researchers, especially in schools. I took part several times to the MATh.en.JEANS project either by giving research talks to the schools, or by proposing research projects to pupils and meeting them throughout the year. Besides, I gave several general audience presentations and was invited to create an educational video with a professional team for the YouTube channel Le Myriogon[START_REF] Barcelo | Des cartes bien à leur place -Viviane Pons -Le Myriogon[END_REF]. I presented a simple bijection on permutations that I explained using playing cards as you can see on Figure10.1.

Figure 10

 10 Figure 10.1: Des Cartes bien à leur place for Le Myriogon youtube channel

Figure 10

 10 Figure 10.2: Pictures taken at Women in Sage in 2017 and 2019

  Generating functions, Catalan numbers and Tamari intervals . . . 3.2 A map of maps using maps and trees . . . . . . . . . . . . . . . .

	Introduction
	I Permutahedra and Associahedra
	II Bijections on Tamari Intervals and More
	3 Intervals of the Tamari Lattice
	3.1

1 Permutahedra 1.1 As a reflection group . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 As a partial order and sorting networks . . . . . . . . . . . . . . . 1.3 As a lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 As a Coxeter group . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 As a Hopf algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Faces of the permutahedron . . . . . . . . . . . . . . . . . . . . . 2 Associahedra 2.1 As a sublattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 As a quotient lattice . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Other lattice descriptions . . . . . . . . . . . . . . . . . . . . . . . 2.4 Loday's associahedron . . . . . . . . . . . . . . . . . . . . . . . . 2.5 As a removahedron . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 As a Cambrian lattice . . . . . . . . . . . . . . . . . . . . . . . . 2.7 As a sub and quotient Hopf algebra . . . . . . . . . . . . . . . . . 2.8 The cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 m-Tamari and ν-Tamari . . . . . . . . . . . . . . . . . . . . . . . 3.3 Tamari interval-posets . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Closed flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Grafting trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  The upper line is a comment which indicates which sizes have been tested. My research code is often full of testing functions with comments to keep track of positive / negative results. I also wrote the following function which tested that the Schur expansion I had corresponded to the actual Schur functions that had been sent to me by Bergeron.

	122CHAPTER 9. EPISTEMOLOGY OF THE EXPERIMENTAL APPROACH
	i f t e s t s y m m e t r y d i s t r i b u t i o n ( d ) :
	p r i n t ( t r )
	P = t r . p a t h t a m a r i l a t t i c e ( )
	d2 = P R V p o s e t d i s t r i b u t i o n ( t r , P)
	p o l = sum ( d2 [ k ] * q * * k [ 0 ] * t * * k [ 1 ] f o r k i n d2 )
	S = s c h u r . f r o m p o l y n o m i a l ( p o l )
	i f not a l l ( c>0 f o r p , c i n S i f l e n (P) <= 2 ) :
	r e t u r n t r
	r e t u r n True
	d e f t e s t P R V p o l y n o m i a l s ( p o l s , q , t ) :
	wrong = [ ]
	f o r key i n p o l s :
	t r = T r i a n g u l a r P a r t i t i o n ( key )
	d = P R V q t d i s t r i b u t i o n ( t r )
	i f t e s t s y m m e t r y d i s t r i b u t i o n ( d ) :
	p r i n t ( t r )
	P = t r . p a t h t a m a r i l a t t i c e ( )
	d2 = P R V p o s e t d i s t r i b u t i o n ( t r , P)
	p o l 1 = sum ( d2 [ k ] * q * * k [ 0 ] * t * * k [ 1 ] f o r k i n d2 )
	p o l 2 = p o l s [ key ] . expand ( 3 ) ( q , t , 1 )
	i f not p o l 1 == p o l 2 :
	wrong . append ( t r )
	r e t u r n wrong
	r )

  They often include introduction talks and also development time around specific topics.. 128, 129 SageMath is a free open source mathematical software created in 2005 and mostly written in python. It includes a wide range of mathematics and is built on top of many other open-source packages. Its stated mission is to "create a viable free open source alternative to Magma, Maple, Mathematica and Matlab". It has been developed mostly by researchers, based on free contributions evaluated through code-reviews. 2, 9, 13, 26, 27, 41, 51, 115, 123, 124, 127-130 Zenodo is a general-pupose open repository which allows researcher to deposit research data. It provides a version number and a DOI. 124, 125

https://www.lri.fr/˜pons/static/spermutahedron/

Note that I am not talking about formal proof assistants. This is another area altogether which I have not had time to explore.

Thierry Dumont. Calcul mathématique avec Sage. CreateSpace Independent Publishing Platform, s.l, May 2013.

Part IV

Pure intervals and s-permutahedra

Looking at the examples of Figure 8.4, a geometrical structure seems to appear. Indeed, the lattices can be drawn in a way that "cuts" the plane into smaller polygonal areas. These polygons are glued together in a "nice" way and form a bigger polygon. All examples of Figure 8.4 are for n = 3. For bigger n, we notice the same phenomenons of cutting a polytope of dimension n -1 into smaller polytopal cells. This is what we call a polytopal complex. The road from seeing to proving turned out to be a much longer path than we initially thought and at this date, we still have no final proof that the s-weak order defines a polytopal complex. Nevertheless, in [CP19] and [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF] we define what we call a combinatorial complex: the s-permutahedron as shown on Figure 8.7.

In [START_REF] Ceballos | The s-weak order and spermutahedra I: combinatorics and lattice structure[END_REF], we proved that the s-weak order is a polygonal lattice. This means that if a tree T is covered by two trees S and S ′ , then the interval between T and S ∨ S ′ is a polygon: it is formed by two chains that meet only in their extremities. The polygons that appear have been characterized by Lacina [START_REF] Lacina | Poset topology of $s$ weak order via SB-labelings[END_REF]: there are either squares, hexagons or pentagons. We believe that that this generalizes to other dimensions: if a tree T is covered by k trees S 1 , . . . , S k , then the interval between T and ∨ k i=1 S i is the skeleton of a k dimensional polytope which is a This is what we call a pure interval of the s-weak order. More precisely, a pure interval is defined by an s-decreasing tree T with a set of selected tree-ascents. Each tree-ascent gives a covering element S and the pure interval is the interval between T and the join of the covering elements S. We show an example on Figure 8.8. Our paper [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF] studies the combinatorial properties of the pure We express a conjecture at the end of [CP19] which should also appear in [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF].

Conjecture 17 (from [CP19] and [START_REF] Ceballos | The s-weak order and spermutahedra II: The combinatorial complex of pure intervals[END_REF]). A geometric realization of the spermutahedron as a polytopal subdivision of permutahedron exists in all dimensions.

By removing some facets, one should obtain a realization of the s-associahedron. We have such a realization for dimensions 2 and 3 as we show on Figure 8.10. More can be found on this webpage 1 .

Perspectives

Our work on the s-weak order and s-permutahedra is still in progress. We are finishing our second paper at the moment and hope to have at least 2 more. Besides, our initial extended abstract [CP19] has raised the interest of the scientific community. For example, Lacina [START_REF] Lacina | Poset topology of $s$ weak order via SB-labelings[END_REF] explored some topological properties of the lattice. At the moment, the group of [GDMP + 23] is working on a positive CHAPTER 9

EPISTEMOLOGY OF THE EXPERIMENTAL APPROACH

To me programming is more than an important practical art. It is also a gigantic undertaking in the foundations of knowledge.

-Grace Hopper

In 2010, I started a research internship at the end of my master degree that would eventually lead to my PhD. My first assignment was to attend a workshop on the open source mathematical software SageMath. At the time, I had no experience with SageMath nor even with the python language (on which SageMath is based). Nevertheless, with a strong background in computer science, I had no difficulties to learn the system. By the end of my internship, I had actually developed the first draft of what is now an external package on bases for multivariate polynomials [START_REF] Pons | SageMath external package implementing the abstract ring of multivariate polynomials with several bases[END_REF].

Already, at this early stage of my research career, it felt natural to me to approach mathematical knowledge and research through experimentation and code. Indeed, it has since become an essential part of my research methodology. In other words: I have written some code related to all my research and all my papers. Computer exploration and experimentation is as essential to me as having a pen and paper. Moreover, I believe that, to a certain degree, experimentation is part of any mathematical research, whether a computer is used or not. On the other hand, as it is used on early stages of the research, it can often be absent of the final result. This creates a difficult problem for historians and philosophers who try to understand how mathematical knowledge is created. For us mathematicians, and especially mathematicians who use computers, this creates another challenge: how do we value this work? In particular, how do we value the necessary technical work to create the tools that are needed? A first step, in my opinion, is to make this work visible and to explain the experimental process in mathematics. Indeed, it has appeared to me that many people do not associate experimentation with mathematics and do not really understand what we mean by that. And probably, different mathematicians have different practices and mean different things. This has led me to have an introspective PyCon is a the name given to general conferences about the Python programming language. The main even is the yearly event PyCon US which often welcomes a few thousand participants. PyCon Fr is also organized every year with a few hundred participants. 127, 128