# Combinatorics of the Permutahedra, Associahedra, and Friends

Viviane Pons

► To cite this version:

Viviane Pons. Combinatorics of the Permutahedra, Associahedra, and Friends. Combinatorics [math.CO]. Université Paris-Saclay, 2023. tel-04390473

HAL Id: tel-04390473

https://hal.science/tel-04390473

Submitted on 12 Jan 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Combinatorics of the
Permutahedra, Associahedra, and
Friends

Habilitation à diriger des recherches
Présentée et soutenue à l'Université Paris-Saclay le
20/10/2023, par

Viviane Pons

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

Composition du jury

**Sylvie CORTEEL**
Directrice de recherche, CNRS & Université Paris-Cité

Rapportrice

**Nathan READING**
Professor, North Carolina State University

Rapporteur

**Victor REINER**
Professor, University of Minnesota

Rapporteur

**Mireille BOUSQUET-MÉLOU**
Directrice de recherche, CNRS & Université de Bordeaux

Examinatrice

**Florent HIVERT**
Professeur, Université Paris-Saclay

Examineur

**Lionel POURNIN**
Professeur, Université Sorbonne Paris Nord

Examineur

**Maria RONCO**
Profesora, Universidad de Talca

Examinatrice
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 intervalles- posets 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. Ç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.
Au cours de ces années, j’ai aussi croisé de très nombreux étudiants et étudiants qui ont fait vivre nos équipes de recherche par leurs idées, leur vivacité, leurs exposés, leurs initiatives et leurs visions. Au risque d’en oublier, je pense à Jean-Baptiste Priez, Aladin Virmaux, Thibault Manneville, Joël Gay, Mathias Lepoutre, Justine Falque, Julian Ritter, Camille Combe, Doriann Albertin, Noémie Cartier, Balthazar Charles, Monica Garcia, Germain Poullot, Éva Philippe, Chiara Mantovani, Clément Chenevière. Aram Dermenjian 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 François Bergeron, Christophe Hohlweg, Olivier Lafitte, Sakina Benhima et Claire Guerrier, ainsi que Srecko Belek pour son chalet sous la neige, toute l’équipe du LACIM pour son accueil et tous les membres de l’IRL et du CRM qui m’ont aidée à naviguer à travers l’administration et l’immigration.

Je souhaite aussi rendre hommage à trois personnes qui ont, chacun à leur façon, contribué à ma construction en tant qu’enseignante-chercheuse et qui nous manquent : Alain Lascoux, Yanis Manoussakis et Marc Zipstein.

Enfin je souhaite remercier mes proches, ma famille qui est un soutien sans faille : ma mère Sylvie, Rébecca, Alice, et tous les enfants. Merci à Elyah pour son intelligence et sa vivacité, à Maël de nous faire rire avec ses premiers pas, à Ilane pour sa sensibilité et ses pensées si riches, à Octave pour sa tendresse, ses câlins et ses interprétations musicales. Et enfin, merci à mon compagnon Sébastien avec qui je partage toute cette vie. Merci d’être là et de m’épauler, de me comprendre, de comprendre ma vocation et mes engagements. *Ca fait 20 ans et des poussières, qu’on fait face au vent d’hiver, ensemble on a peur de rien.*
CONTENTS

Introduction 1

I Permutahedra and Associahedra 7

1 Permutahedra 9

1.1 As a reflection group 10

1.2 As a partial order and sorting networks 10

1.3 As a lattice 12

1.4 As a Coxeter group 14

1.5 As a Hopf algebra 15

1.6 Faces of the permutahedron 17

2 Associahedra 19

2.1 As a sublattice 20

2.2 As a quotient lattice 22

2.3 Other lattice descriptions 25

2.4 Loday's associahedron 26

2.5 As a removalhedron 26

2.6 As a Cambrian lattice 28

2.7 As a sub and quotient Hopf algebra 31

2.8 The cube 32

2.9 *m*-Tamari and *ν*-Tamari 32

II Bijections on Tamari Intervals and More 35

3 Intervals of the Tamari Lattice 37

3.1 Generating functions, Catalan numbers and Tamari intervals 38

3.2 A map of maps using maps and trees 39

3.3 Tamari interval-posets 40

3.4 Closed flows 44

3.5 Grafting trees 45
<table><tr><td>3.6</td><td>Interval-posets in <i>m</i>-Tamari</td><td>47</td></tr><tr><td>3.7</td><td>Open questions</td><td>49</td></tr></table>

<table><tr><td>4</td><td>Statistics and Bijections on Tamari Intervals</td><td>51</td></tr><tr><td>4.1</td><td>Contacts, descents, and complement involution</td><td>52</td></tr><tr><td>4.2</td><td>Rises, descents, and left-branch involution</td><td>53</td></tr><tr><td>4.3</td><td>Distance and Tamari inversions</td><td>55</td></tr><tr><td>4.4</td><td>The Rise-contact involution</td><td>56</td></tr><tr><td>4.5</td><td>The expand-contract operation on <i>m</i>-Tamari intervals</td><td>56</td></tr><tr><td>4.6</td><td>Open questions</td><td>58</td></tr></table>

<table><tr><td>5</td><td><i>q</i>, <i>t</i>-Catalan</td><td>59</td></tr><tr><td>5.1</td><td>Background on diagonal harmonic polynomials</td><td>60</td></tr><tr><td>5.1.1</td><td>The <i>q</i>, <i>t</i>-Catalan and the Tamari intervals</td><td>60</td></tr><tr><td>5.1.2</td><td>Triangular partitions and Dyck paths</td><td>61</td></tr><tr><td>5.2</td><td>Understanding the “dinv”</td><td>63</td></tr><tr><td>5.2.1</td><td>Zeta function and area sequences</td><td>63</td></tr><tr><td>5.2.2</td><td>The deficit in triangular Dyck paths</td><td>65</td></tr><tr><td>5.3</td><td>Lattice interval enumeration and Schur-positivity</td><td>67</td></tr><tr><td>5.4</td><td>Open questions</td><td>68</td></tr></table>

### III Quotients and Sublattices 69

<table><tr><td>6</td><td>Integer Posets</td><td>71</td></tr><tr><td>6.1</td><td>Generalizing the Tamari interval-posets</td><td>71</td></tr><tr><td>6.2</td><td>Integer Relations</td><td>74</td></tr><tr><td>6.2.1</td><td>As a lattice</td><td>74</td></tr><tr><td>6.2.2</td><td>As a Hopf algebra</td><td>75</td></tr><tr><td>6.3</td><td>Integer Posets</td><td>77</td></tr><tr><td>6.3.1</td><td>As a lattice</td><td>77</td></tr><tr><td>6.3.2</td><td>As a Hopf algebra</td><td>79</td></tr><tr><td>6.3.3</td><td>General audience paper</td><td>79</td></tr><tr><td>6.4</td><td>Induced structures on permutations, binary trees and more</td><td>80</td></tr><tr><td>6.5</td><td>Open questions</td><td>81</td></tr></table>

<table><tr><td>7</td><td>Permutrees</td><td>83</td></tr><tr><td>7.1</td><td>Lattice quotients and decorations</td><td>83</td></tr><tr><td>7.2</td><td>Permutree insertion and permutree lattice</td><td>86</td></tr><tr><td>7.3</td><td>Numerology</td><td>89</td></tr><tr><td>7.4</td><td>Permutreehedra</td><td>91</td></tr><tr><td>7.5</td><td>Schröder permutrees</td><td>93</td></tr><tr><td>7.6</td><td>Hopf algebras</td><td>93</td></tr><tr><td>7.7</td><td>Reduced words and other groups</td><td>95</td></tr></table>
<table><tr><td>7.8 Open questions</td><td>96</td></tr></table>

IV Generalizations 97

8 The s-Weak Order and s-Permutahedra 99

8.1 The metasylvester lattice 100

8.2 The s-weak order 101

8.3 Link with the $\nu$-Tamari lattice 104

8.4 Pure intervals and s-permutahedra 105

8.5 Perspectives 108

8.5.1 Ascentopes 109

8.5.2 Solving the conjecture 110

8.5.3 Lattice quotients and geometric realizations 110

8.5.4 Other groups and other lattices 111

V Experimental Approach 113

9 Epistemology of the Experimental Approach 115

9.1 The experimental process 116

9.1.1 To understand objects 116

9.1.2 To eliminate false statements and generate counter example 118

9.1.3 To find ideas and emit conjectures 120

9.1.4 To solve and to prove 122

9.2 What to do with the code? 123

9.2.1 Contributions to open-source 123

9.2.2 Other good practices 124

10 Outreach 127

10.1 Advocate for open science 127

10.2 Talking about research to non researchers 128

10.3 Building a more inclusive community 129

10.4 Political mathematics 131

Closing remarks 133

Glossary 136

Selected list of publications 137

Other bibliographic references 141
LIST OF FIGURES

<table>
  <tbody>
    <tr>
      <td>1.1</td>
      <td>The permutahedra of dimensions 2 and 3 drawn by SageMath</td>
      <td>9</td>
    </tr>
    <tr>
      <td>1.2</td>
      <td>The permutahedron as a reflection group.</td>
      <td>10</td>
    </tr>
    <tr>
      <td>1.3</td>
      <td>The left and right weak orders on S<sub>3</sub>.</td>
      <td>11</td>
    </tr>
    <tr>
      <td>1.4</td>
      <td>The left and right weak orders on S<sub>4</sub>.</td>
      <td>11</td>
    </tr>
    <tr>
      <td>1.5</td>
      <td>An example of a non-lattice</td>
      <td>13</td>
    </tr>
    <tr>
      <td>1.6</td>
      <td>The possible connected Dynkin diagrams of finite Coxeter groups</td>
      <td>15</td>
    </tr>
    <tr>
      <td>1.7</td>
      <td>Inequalities in the plane defined by x<sub>1</sub> + x<sub>2</sub> + x<sub>3</sub> = 6.</td>
      <td>17</td>
    </tr>
    <tr>
      <td>1.8</td>
      <td>Ordered partitions as faces of the permutahedron.</td>
      <td>18</td>
    </tr>
    <tr>
      <td>2.1</td>
      <td>The Tamari lattice on parenthesized words</td>
      <td>20</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>Example of a lattice which is not a sublattice.</td>
      <td>21</td>
    </tr>
    <tr>
      <td>2.3</td>
      <td>The Tamari lattice as a sublattice of the right weak order.</td>
      <td>21</td>
    </tr>
    <tr>
      <td>2.4</td>
      <td>Binary search tree insertion and linear extensions</td>
      <td>22</td>
    </tr>
    <tr>
      <td>2.5</td>
      <td>Binary tree rotation.</td>
      <td>22</td>
    </tr>
    <tr>
      <td>2.6</td>
      <td>The Tamari lattice as a quotient of the right weak order (n = 3).</td>
      <td>24</td>
    </tr>
    <tr>
      <td>2.7</td>
      <td>The Tamari lattice as a quotient of the right weak order (n = 4).</td>
      <td>24</td>
    </tr>
    <tr>
      <td>2.8</td>
      <td>Tamari rotation on Dyck paths</td>
      <td>25</td>
    </tr>
    <tr>
      <td>2.9</td>
      <td>The Tamari lattice on Dyck paths.</td>
      <td>25</td>
    </tr>
    <tr>
      <td>2.10</td>
      <td>Coordinates of binary trees in Loday's associahedron.</td>
      <td>26</td>
    </tr>
    <tr>
      <td>2.11</td>
      <td>The associahedra of dimensions 2 and 3 drawn by SageMath</td>
      <td>27</td>
    </tr>
    <tr>
      <td>2.12</td>
      <td>Permutahedra inside of associahedra</td>
      <td>27</td>
    </tr>
    <tr>
      <td>2.13</td>
      <td>Faces of the associahedron as Schröder trees.</td>
      <td>28</td>
    </tr>
    <tr>
      <td>2.14</td>
      <td>Initial merges (in bold red) generating the sylvester congruence (in bold red and blue) and corresponding orientation of the Dynkin diagram.</td>
      <td>29</td>
    </tr>
    <tr>
      <td>2.15</td>
      <td>Another Cambrian congruence on A<sub>3</sub> with corresponding orientation</td>
      <td>30</td>
    </tr>
    <tr>
      <td>2.16</td>
      <td>Product of PBT as an interval of the Tamari lattice</td>
      <td>31</td>
    </tr>
    <tr>
      <td>2.17</td>
      <td>The boolean lattice as a sub and quotient lattice of the weak order.</td>
      <td>33</td>
    </tr>
    <tr>
      <td>2.18</td>
      <td>The m-Tamari lattice and a v-Tamari lattice</td>
      <td>34</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Landscape of bijections between objects counted by Tamari intervals</td>
      <td>39</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Construction of Tamari interval-posets from binary trees</td>
      <td>42</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>Decreasing and increasing forests of two incompatible trees.</td>
      <td>42</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>3.4</td>
      <td>Bijection between Dyck paths and decreasing and increasing forests</td>
      <td>43</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>Composition of interval-posets</td>
      <td>44</td>
    </tr>
    <tr>
      <td>3.6</td>
      <td>Bijection between closed flows and Tamari interval-posets</td>
      <td>46</td>
    </tr>
    <tr>
      <td>3.7</td>
      <td>Example of grafting tree with corresponding interval-poset decomposition.</td>
      <td>47</td>
    </tr>
    <tr>
      <td>3.8</td>
      <td>Decomposition of m-binary trees and example for m = 2.</td>
      <td>48</td>
    </tr>
    <tr>
      <td>3.9</td>
      <td>An m-Tamari interval-poset and its corresponding grafting tree.</td>
      <td>49</td>
    </tr>
    <tr>
      <td>3.10</td>
      <td>Bijection between interval-posets and triangulations</td>
      <td>50</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>The complement involution on Tamari intervals</td>
      <td>52</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>The left-branch involution on Tamari intervals</td>
      <td>54</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Tamari inversions on an interval-poset and grafting tree</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>The rise-contact involution on Tamari intervals</td>
      <td>57</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>The expand operation on m-grafting trees</td>
      <td>58</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Dyck paths of size 3 as sub-partitions of (2, 1)</td>
      <td>62</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>The triangular partition (4, 3, 1) and the non-triangular partition (4, 4).</td>
      <td>63</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>A Dyck path (as a sub-partition) with its area and area sequence.</td>
      <td>64</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>An example of the inverse zeta map bijection.</td>
      <td>65</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Similar cells, Triangular young tableau and deficit</td>
      <td>66</td>
    </tr>
    <tr>
      <td>5.6</td>
      <td>Construction of the triangular tableau</td>
      <td>66</td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>Permutations, binary trees, and binary sequences as integer posets</td>
      <td>72</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Construction of a weak order interval-poset.</td>
      <td>73</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Conditions on interval-posets</td>
      <td>73</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>The boolean lattice (on the left) and the weak order (on the right) on integer relations.</td>
      <td>75</td>
    </tr>
    <tr>
      <td>6.5</td>
      <td>Join and meet on integer relations.</td>
      <td>75</td>
    </tr>
    <tr>
      <td>6.6</td>
      <td>Product in the Hopf algebra of integer relations as an interval</td>
      <td>76</td>
    </tr>
    <tr>
      <td>6.7</td>
      <td>Meet of two transitive relations.</td>
      <td>77</td>
    </tr>
    <tr>
      <td>6.8</td>
      <td>The weak order lattice on integer posets</td>
      <td>78</td>
    </tr>
    <tr>
      <td>6.9</td>
      <td>Interval corresponding to the product of integer posets.</td>
      <td>79</td>
    </tr>
    <tr>
      <td>6.10</td>
      <td>The Closet-Poset</td>
      <td>80</td>
    </tr>
    <tr>
      <td>7.1</td>
      <td>Two examples of permutree congruences.</td>
      <td>84</td>
    </tr>
    <tr>
      <td>7.2</td>
      <td>The permutree congruences, for all decorations δ ∈ Φ·{Φ, Θ, Υ, ⊗}².</td>
      <td>85</td>
    </tr>
    <tr>
      <td>7.3</td>
      <td>The labeling rules on permutrees.</td>
      <td>86</td>
    </tr>
    <tr>
      <td>7.4</td>
      <td>The insertion algorithm on the decorated permutation 2751346.</td>
      <td>87</td>
    </tr>
    <tr>
      <td>7.5</td>
      <td>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).</td>
      <td>88</td>
    </tr>
    <tr>
      <td>7.6</td>
      <td>The permutree congruence on decorated permutations.</td>
      <td>89</td>
    </tr>
    <tr>
      <td>7.7</td>
      <td>The δ-permutree lattices, for the decorations δ = ΦΦΘΘ (left) and δ = Φ⊗ΥΘ (right)</td>
      <td>90</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>7.8</td>
      <td>The permutreehedra, for all decorations δ ∈ Θ · {Θ, Θ, Θ, Θ}² · Θ.</td>
      <td>92</td>
    </tr>
    <tr>
      <td>7.9</td>
      <td>The Schröder permutree lattices for Θ³, Θ³, Θ³</td>
      <td>93</td>
    </tr>
    <tr>
      <td>7.10</td>
      <td>Grafting two permutrees (left) and cutting a permutree (right).</td>
      <td>94</td>
    </tr>
    <tr>
      <td>7.11</td>
      <td>The automaton U(j) to.</td>
      <td>95</td>
    </tr>
    <tr>
      <td>8.1</td>
      <td>The lattice of 2-permutations (left) with metasylvester classes and the corresponding s-weak order.</td>
      <td>100</td>
    </tr>
    <tr>
      <td>8.2</td>
      <td>An s-decreasing tree and the corresponding s-permutation.</td>
      <td>101</td>
    </tr>
    <tr>
      <td>8.3</td>
      <td>An s-decreasing tree and its tree-inversions.</td>
      <td>102</td>
    </tr>
    <tr>
      <td>8.4</td>
      <td>Examples of s-weak lattices.</td>
      <td>103</td>
    </tr>
    <tr>
      <td>8.5</td>
      <td>Illustration of the transitivity and planarity conditions on s-tree inversion sets.</td>
      <td>104</td>
    </tr>
    <tr>
      <td>8.6</td>
      <td>s-decreasing trees and s-Tamari trees for s = (0, 2, 3). On the left picture, the non s-Tamari trees are in black.</td>
      <td>105</td>
    </tr>
    <tr>
      <td>8.7</td>
      <td>The s-permutahedron complex for s = (0, 2, 2).</td>
      <td>106</td>
    </tr>
    <tr>
      <td>8.8</td>
      <td>Example of a pure interval. On the left, the minimal tree with colored tree-ascents and on the right the corresponding interval.</td>
      <td>106</td>
    </tr>
    <tr>
      <td>8.9</td>
      <td>The s-associahedron complex for s = (0, 2, 2).</td>
      <td>107</td>
    </tr>
    <tr>
      <td>8.10</td>
      <td>Some realizations for s-permutahedra and s-associahedra.</td>
      <td>108</td>
    </tr>
    <tr>
      <td>8.11</td>
      <td>A pure interval and its corresponding ascentope</td>
      <td>109</td>
    </tr>
    <tr>
      <td>8.12</td>
      <td>A pure interval of dimension 9 with the f vector of its ascentope.</td>
      <td>109</td>
    </tr>
    <tr>
      <td>9.1</td>
      <td>Pictures of early drafts of triangular partitions and Dyck paths</td>
      <td>117</td>
    </tr>
    <tr>
      <td>9.2</td>
      <td>A manual computation of q, t symmetry on intervals of ν-Tamari.</td>
      <td>118</td>
    </tr>
    <tr>
      <td>9.3</td>
      <td>Manual attempt to obtain the desired lattice structure on partition (3, 2, 2, 1).</td>
      <td>120</td>
    </tr>
    <tr>
      <td>9.4</td>
      <td>Manual enumeration of triangular Dyck paths to define the tableau deficit.</td>
      <td>121</td>
    </tr>
    <tr>
      <td>10.1</td>
      <td>Des Cartes bien à leur place for Le Myriogon youtube channel</td>
      <td>128</td>
    </tr>
    <tr>
      <td>10.2</td>
      <td>Pictures taken at Women in Sage in 2017 and 2019</td>
      <td>130</td>
    </tr>
    <tr>
      <td>10.3</td>
      <td>The SageMath developer map taken from https://www.sagemath.org/ in June 2023.</td>
      <td>130</td>
    </tr>
  </tbody>
</table>
# 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 [Tam62] 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 [AL62]. 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 [Tam51] and later independently by Stasheff [Sta63]. Nowadays, many realizations are known [Lod04, HLT11] and it has become a major object in discrete geometry and combinatorics [PSZ23].

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 [MR95, DHT02, LR98, HNT05].

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, Pon19], the lattice and Hopf algebra of integer posets [CPP19, PP20], the permutrees [PP18, PPTJ23], the *-weak order [CP19] [CP22, CP23]. 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 [PonSage23].

# 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 interval-posets [CP15], closed flows [CCP14], and grafting trees [Pon19]. 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 [Pon19] where I define the *rise-contact* involution on Tamari intervals, answering a conjecture of [PR12] and [BFP11]. 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 [Pon22] and [LMP23] 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 [Pon22]. 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 [LMP23]. We have especially Theorem 7 and Conjecture 8 which express the relations between triangular *q*, *t* enumerations and certain intervals of the *v*-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 [CPP19] and [PP20] 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 [PPTJ23]. 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 [CP22] and [CP23]. 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 $\nu$-Tamari lattices. Our main results are expressed in Theorem 14: the *s*-weak order is a lattice, and Theorem 15: the $\nu$-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
<figure><img src="image_3.png" /></figure>
# 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ⁿ. This set actually lies in a hyperplane of dimension *n* − 1 as the sum of coordinates is always ∑¹ⁿ *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.

P3 = Polyhedron(list(Permutations(3)))
P3.plot()

P4 = Polyhedron(list(Permutations(4)))
P4.plot()

<figure><img src="image_4.png" /><figcaption>Figure 1.1: The permutahedra of dimensions 2 and 3 drawn by **SageMath**</figcaption></figure>

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.
## 1.1 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 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 \neq 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.

<figure><img src="image_5.png" /><figcaption>Figure 1.2: The permutahedron as a reflection group.</figcaption></figure>

## 1.2 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 \prec z$
such that there is no $y$ with $x \prec y \prec 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 $\mathcal{S}_3$ with $s_1$ in red and $s_2$ in blue. Figure 1.4 shows the left and right weak order on $\mathcal{S}_4$ with $s_1$ in blue, $s_2$ in red, and $s_3$ in green.

<figure><img src="image_6.png" /><figcaption>Figure 1.3: The left and right weak orders on $\mathcal{S}_3$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 1.4: The left and right weak orders on $\mathcal{S}_4$.</figcaption></figure>
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 $\frac{n(n-1)}{2}$ and attained in the maximal permutation $n! - 1... 1$. Moreover, we can give an alternative definition of the weak order using inclusion of inversions. For two permutations $\sigma$ and $\tau$, we define that $\sigma \prec \tau$ if and only if $\mathrm{inv}(\sigma) \subseteq \mathrm{inv}(\tau)$. The definition of inv depends on the version of the weak order we consider. In the left weak order, we use *position inversions* $\mathrm{inv}_{\mathrm{pos}}(\sigma) := \{(i, j); i < j \text{ and } \sigma(i) > \sigma(j)\}$. In the right weak order, which is the one we will mostly use in this manuscript, we consider *value inversions* $\mathrm{inv}_{\mathrm{val}}(\sigma) := \{(a, b); a < b; \sigma^{-1}(b) < \sigma^{-1}(a)\}$ (in other words, $\sigma(b)$ appears before $\sigma(a)$ in $\sigma$). 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 $\sigma = 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 $\frac{n(n-1)}{2}$.

## 1.3 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 $\wedge$, which computes the *greatest lower bound* of two elements $x$ and $y$;

* the *join*, written $\vee$, 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
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.

<figure><img src="image_8.png" /><figcaption>Figure 1.5: An example of a non-lattice</figcaption></figure>

On the contrary, the meet and join of any two elements of the weak order is well defined. This was proved in [GR70] 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 \le i < j \le 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 \le i < j \le 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 $\sigma$ and $\mu$. Let $I_\sigma$ and $I_\mu$ be the respective inversion sets, then $I_\sigma \cup I_\mu$ is not necessary transitive and so it is not an inversion set. Nevertheless, we can prove that the *transitive closure* of $I_\sigma \cup I_\mu$ is an inversion set and it gives the permutation $\sigma \vee \mu$. 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 an 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 [PonSage23].
## 1.4 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, \dots, s_n$ with relations $(s_i s_j)^{m_{i,j}} = 1$ where $m_{i,i} = 1$ and $2 \le m_{i,j} \le \infty$. Finite Coxeter Groups have been classified. The symmetric group $\mathfrak{S}_n$ corresponds to the type $A_{n-1}$. Its generators are the simple transpositions and satisfy the *braid relations*

$$s_i^2 = 1; \tag{1.1}$$

$$(s_i s_j)^2 = 1 \qquad \text{if } i + 1 < j; \tag{1.2}$$

$$(s_i s_{i+1})^3 = 1. \tag{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 $\mathfrak{S}_3$, $s_1$, $s_1^3$, and $s_1 s_2 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_2s_1$. On the right weak order, the path $s_1$ then $s_2$ goes to 231. Indeed, the reduced word of 231 is $s_1s_2$, it is the inverse of 312 = $s_2s_1$. Similarly, we can read that, in both the right and left weak orders, the maximal permutation 321 has 2 reduced words: $s_1s_2s_1$ and $s_2s_1s_2$.

The symmetric group is just one example of a finite Coxeter group. These have been classified [Cox35] 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.

<figure><img src="image_9.png" /><figcaption>Figure 1.6: The possible connected Dynkin diagrams of finite Coxeter groups</figcaption></figure>

Image under CC BY-SA 3.0 from Wikimedia Commons

All finite Coxeter groups admit a faithful representation as a reflection group. In particular, as explained in [Hoh12], 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 $\mu \prec \sigma$ in the right (resp. left) weak order if and only if there exist a reduced word of $\mu$ which is prefix (resp. suffix) of a reduced word of $\sigma$. For example, we have 2314 $\prec$ 2431 (in the right weak order of type *A*) and indeed 2314 = $s_1s_2$ is a prefix of $s_1s_2s_3s_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.

1.5 As a Hopf algebra

Hopf algebras are algebraic structures that have raised the interest of the combina-
torial community for the past decades. They can be seen as a generalization of the
classical notion of *generating functions* studied by Flajolet and Sedgewick [FS09]
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*<sup>*n*</sup>. 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 $\mathcal{H}$ is a special case of a bialgebra. It is endowed with two operations: a product $\cdot: \mathcal{H} \otimes \mathcal{H} \to \mathcal{H}$ and a coproduct $\Delta: \mathcal{H} \to \mathcal{H} \otimes \mathcal{H}$. These two operations are respectively *associative* and *co-associative* 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 $\mathcal{H}$, then $\Delta(x \cdot y) = \Delta(x) \cdot \Delta(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 [Hiv06] 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 MacMachon [Mac15] and later to Rota [JR79]. The connection with the permutahedron comes from the Malvenuto-Reutenauer Hopf algebra on permutations [MR95] which we call **FQSym** after [DHT02] who redefine the algebra using the notion of *polynomial realization* with words. We write $\mathbb{F}_{\sigma}$ the elements of **FQSym** using the basis $\mathbb{F}$. The product is defined by the *shifted shuffle product* on permutation. We show an example below:

$$ \mathbb{F}_{\mathbf{231}} \cdot \mathbb{F}_{\mathbf{12}} = \mathbb{F}_{\mathbf{231}45} + \mathbb{F}_{\mathbf{2341}} + \mathbb{F}_{\mathbf{24315}} + \mathbb{F}_{\mathbf{23451}} + \mathbb{F}_{\mathbf{42315}} + \mathbb{F}_{\mathbf{24351}} + \mathbb{F}_{\mathbf{42351}} + \mathbb{F}_{\mathbf{24531}} + \mathbb{F}_{\mathbf{42531}} + \mathbb{F}_{\mathbf{45231}} \quad (1.4) $$

$$ = \sum_{\mathbf{23145} \prec_R \mu \prec_R \mathbf{45231}} \mathbb{F}_{\mu}. \quad (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 $\mathbb{F}$ also admits a coproduct. It actually corresponds to a product in the *dual basis* $\mathbb{G}$. The product in $\mathbb{G}$ is called the *convolution product* on permutations and corresponds to a sum in the left weak order.
$$ \mathbb{G}_{312} \cdot \mathbb{G}_{12} = \mathbb{G}_{31245} + \mathbb{G}_{41235} + \mathbb{G}_{41325} + \mathbb{G}_{51234} + \mathbb{G}_{42315} + \mathbb{G}_{51324} + \mathbb{G}_{52314} + \mathbb{G}_{51423} + \mathbb{G}_{52413} + \mathbb{G}_{53412} \quad (1.6) $$

$$ = \sum_{31245 \le L \mu \le L 53412} \mathbb{G}_{\mu}. \quad (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 $\mathbb{G}$ is isomorphic to $\mathbb{F}$ using the inversion of permutation just like between the right and left weak orders. This makes $\mathbf{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 $\mathbf{FQSym}$ is free.

## 1.6 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.

<figure><img src="image_10.png" /><figcaption>Figure 1.7: Inequalities in the plane defined by $x_1 + x_2 + x_3 = 6$.</figcaption></figure>

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 \le x_3 \le 3$, we find $3 \le x_1 + x_2 \le 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 non-empty proper subsets of $[n] := \{1, 2, \dots, n\}$. For each subset $J$, the corresponding inequality is given by $\sum_{j \in J} x_j \ge \binom{|J|+1}{2}$ [Rad52].

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-\ell$ where $\ell$ is the number of parts in the ordered partitions. We illustrate this in Figure 1.8.

<figure><img src="image_11.png" /><figcaption>Figure 1.8: Ordered partitions as faces of the permutahedron.</figcaption></figure>

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 [DHP16] for all Coxeter groups. A Hopf algebra structure can also be defined on faces that extend the Malvenuto-Reutenauer one on permutations [Cha00].
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 [Tam51] and later on in [Tam62], 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 \quad (a(bc))d \quad (ab)(cd) \quad a((bc)d) \quad a(b(cd)).$$

In general, the number of configurations is counted by the famous Catalan
numbers [A108]

$$C_n = \frac{1}{n+1} \binom{n}{2n} \qquad (2.1)$$

By orienting the rewriting such that $(ab)c \prec 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 [FT67, HT72]
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 polytope. This polytope is the associahedron. It was also introduced
independently by Stasheff [Sta63] 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 [MPS12] to honor the memory of Tamari and the recent survey on Loday's
realization of the associahedron [PSZ23]. The relations between the Tamari lat-
tice 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*,
<figure><img src="image_12.png" /><figcaption>Figure 2.1: The Tamari lattice on parenthesized words</figcaption></figure>

geometrical, and algebraical links between these two structures. This gives the ground motivation of the work I present afterwards.

## 2.1 As a sublattice

We say that a permutation $\sigma$ of size $n$ contains a pattern $\mu$ of size $k \le n$ if there is a subword $w$ of $\sigma$ with $|w| = k$ such that the relative order between the letters of $w$ is given by $\mu$. In other words, the *standardized permutation* of $w$ is $\mu$. 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 [Knu98], 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 [Mac15] for the permutations avoiding 123 and the introduction of [SS85] 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 \subset L$ is a sublattice if for any two elements $x$ and $y$ in $I$, then $x \wedge_L y$ and $x \vee_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 \wedge d = b$ is not part of the subposet.

<figure><img src="image_13.png" /><figcaption>Figure 2.2: Example of a lattice which is not a sublattice.</figcaption></figure>

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

<figure><img src="image_14.png" /><figcaption>Figure 2.3: The Tamari lattice as a sublattice of the right weak order.</figcaption></figure>
## 2.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 $\lambda$ labeled by $x$, the nodes in the left subtree of $\lambda$ are labeled with values smaller than or equal to $x$ while the nodes on the right subtree of $\lambda$ 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).

<figure><img src="image_15.png" /><figcaption>Figure 2.4: Binary search tree insertion and linear extensions</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Figure 2.5: Binary tree rotation</figcaption></figure>
This algorithm is used in conjunction with binary tree rotation (see Figure 2.5) in [AL62] 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 [BW91] 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 [HNT05], 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:

$$ \dots ac \dots b \dots \equiv \dots ca \dots b \dots \qquad (2.2) $$

with $a < b < c$.

A congruence relation on a lattice is said to be a *lattice congruence* if $x \equiv x'$ and $y \equiv y'$ implies that $x \wedge y \equiv x' \wedge y'$ and $x \vee y \equiv x' \vee 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 [Rea04]. In particular, if the congruence classes are intervals and satisfy some extra order-preserving 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 \rightarrow 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 permutations). 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.
<figure><img src="image_17.png" /><figcaption>Figure 2.6: The Tamari lattice as a quotient of the right weak order ($n = 3$)</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Figure 2.7: The Tamari lattice as a quotient of the right weak order ($n = 4$)</figcaption></figure>
## 2.3 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.

<figure><img src="image_19.png" /><figcaption>Figure 2.8: Tamari rotation on Dyck paths</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Figure 2.9: The Tamari lattice on Dyck paths</figcaption></figure>
## 2.4 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 [Lod04, PSZ23]. Each tree of size $n$ corresponds to a point $(v_1, \dots, v_n)$ in $\mathbb{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.

<figure><img src="image_21.png" /><figcaption>Figure 2.10: Coordinates of binary trees in Loday’s associahedron.</figcaption></figure>

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 [PonSage23].

## 2.5 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 [Pil17].
<figure><img src="image_22.png" /><figcaption>Figure 2.11: The associahedra of dimensions 2 and 3 drawn by SageMath</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 2.12: Permutahedra inside of associahedra</figcaption></figure>

In dimension 2, the inequality which is “removed” is $x_1+x_3 \ge 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 [HLT11]. 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
<figure><img src="image_24.png" /><figcaption>Figure 2.13: Faces of the associahedron as Schröder trees.</figcaption></figure>

In Schröder trees, the subset *J* correspond to the part that is below the second internal node. There is no way to get a two-nodes Schröder tree with the below part being {1, 3}. Indeed, it would have to be below the label 2 but could not be to its left (because 3 > 2) nor to its right (because 1 < 2).

## 2.6 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.7. This representation is possible because
<figure><img src="image_25.png" /><figcaption>Figure 2.14: Initial merges (in bold red) generating the sylvester congruence (in bold red and blue) and corresponding orientation of the Dynkin diagram.</figcaption></figure>

all congruence classes form intervals of the lattice. A natural question is then: if I merge a single edge, what other edges need to be merged so that the final congruence is a lattice congruence? We say that the other necessary edges are *forced* by the original one. This has been answered in general by Reading for the weak order using *arc diagrams* [Rea04]. The sylvester congruence is then the smallest lattice congruence containing the two initial edges in red on Figure 2.14: 1324 – 3124, and 1243 – 1423.

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 \le 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 \ge 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 - \cdots - (s_i s_j)^{\frac{k-1}{2}} - (s_i s_j)^{\frac{k-1}{2}} s_i,$$

where $-$ represents an edge in the weak order. The other side is

$$s_j - s_j s_i - \cdots - (s_j s_i)^{\frac{k-1}{2}} - (s_j s_i)^{\frac{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 \to j$, then all edges between $s_j s_i$ and $(s_i s_j)^{\frac{k-1}{2}}$ (for $k$ odd) are merged. If the orientation
is $i \leftarrow j$, then all edges between $s_i s_j$ and $(s_i s_j)^{\frac{k-1}{2}}$ are merged. For type $A$, the polygon is always a 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.15.

<figure><img src="image_26.png" /><figcaption>Figure 2.15: Another Cambrian congruence on $A_3$ with corresponding orientation</figcaption></figure>

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 [HLT11].

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^\infty$ word, for respective previous examples,

$$c^\infty = s_1 s_2 s_3 | s_1 s_2 s_3 | s_1 s_2 s_3 | \dots$$

$$c'^\infty = s_1 s_3 s_2 | s_1 s_3 s_2 | s_1 s_3 s_2 | \dots$$

Now each reduced word can be read as a subword of $c^\infty$. 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^\infty$ with $I_1 \subset I_2 \subset I_3 \dots$. For example, $s_1s_2s_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\} \subset I_1$. On the other hand, $s_2s_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.

## 2.7 As a sub and quotient Hopf algebra

In [LR98], 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 associa- hedron. The Loday-Ronco Hopf algebra is studied in [HNT05] 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 $\mathbb{P}$ indexed by binary trees as a sum over elements from the basis $\mathbb{F}$ of **FQSym**: the sum is over all linear extension of the standard binary search tree. See the example below.

$$ \mathbb{P} \mathrel{\begin{smallmatrix} \vdots \\ \mathbb{P} \end{smallmatrix}} = \mathbb{F}_{2143} + \mathbb{F}_{2413} + \mathbb{F}_{4213}. \qquad (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 $\mathbb{P}$ forms a sub Hopf algebra of **FQSym**. As the product between two elements of $\mathbb{F}$ is an interval in the weak order, the product of two elements of $\mathbb{P}$ gives a sum over sylvester classes which is an interval of the Tamari lattice, see the example on Figure 2.16.

<figure><img src="image_27.png" /><figcaption>Figure 2.16: Product of **PBT** as an interval of the Tamari lattice</figcaption></figure>
Besides, the basis $\mathbb{P}$ admits a dual basis $\mathbb{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.

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

## 2.9 *m*-Tamari and *v*-Tamari

We finish this chapter with two generalization of the Tamari lattice that we study in our work. The *m*-Tamari lattice appears in [BP12]. 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 \times 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 \times 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 [PV17], 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 *v*-Tamari lattice (where *v* 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><img src="image_28.png" /><figcaption>Figure 2.17: The boolean lattice as a sub and quotient lattice of the weak order.</figcaption></figure>

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. For example, Ceballos, Padrol, and Sarminento provide a geometric realization of the *ν*-Associahedron [CPS16].
<figure><img src="image_29.png" /><figcaption>Figure 2.18: The *m*-Tamari lattice and a *v*-Tamari lattice</figcaption></figure>
# Part II

## Bijections on Tamari Intervals
and More
<figure><img src="image_30.png" /></figure>
# CHAPTER 3

## 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 [Cha05], Chapoton proves that the number of *intervals* in the Tamari lattice satisfies a surprisingly nice formula:

$$I_n = \frac{2}{n(n+1)} \binom{4n+1}{n-1} = \frac{2(4n+1)!}{(n+1)!(3n+2)!} \quad (3.1)$$

where $I_n$ is the number of couples of elements $x, y$, in the Tamari lattice on size $n$, with $x \preceq 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 *bijjective 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. \quad (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 [CCP14] and grafting trees [Pon19]. 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.
## 3.1 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 [Sta15], 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) := \sum_{n \ge 0} C_n z^n, \qquad (3.3)$$

Where $C_n$ is equal to (7.3). Then, $F$ satisfies the following functional equation

$$F(z) = 1 + zF(z)^2. \qquad (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

$$\phi(z) := \sum_{n \ge 0} I_n z^n, \qquad (3.5)$$

where $I_n$ is (3.1). Then, $\phi(z) = \Phi(z, 1)$ where

$$\Phi(z, x) = 1 + zx\Phi(z, x) \frac{x\Phi(z, x) - \Phi(z, 1)}{x - 1}. \qquad (3.6)$$

We give this exact functional equation in [CP15, Theorem 3.2] and this was already proven by Chapoton in [Cha05] 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 \times z^k \times 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+\cdots+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.

## 3.2 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.

<figure><img src="image_31.png" /><figcaption>Figure 3.1: Landscape of bijections between objects counted by Tamari intervals</figcaption></figure>

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 [Zei19] and extended fighting fish [DH23], 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.

As we have said, Chapoton is the first to count Tamari intervals [Cha05]. 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 [BFP11] where the authors solve a more 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 [Pon19] 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 [CP13]. In the full version [CP15], we extend this definition to *m*-Tamari intervals. In [CCP14] and [Pon19], 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 [FFN23] 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.

## 3.3 Tamari interval-posets

Tamari interval-posets of size $n$ are partial orders on $[n]$ satisfying certain conditions. We write $a \prec b$ to say that $a$ is smaller than $b$ in the poset (to differentiate from the symbol $\prec$ 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 \triangleleft c \Rightarrow b \triangleleft c; \qquad (3.7)$$

$$c \triangleleft a \Rightarrow b \triangleleft a. \qquad (3.8)$$

We give an example on the right of Figure 3.2. We see that we have $1 \triangleleft 5$ which implies $b \triangleleft 5$ for $1 < b < 5$. Similarly, we have $10 \triangleleft 5$ which implies $b \triangleleft 5$ for $5 < b < 10$. Besides, Tamari interval-posets have been integrated into SageMath. The examples of this Section can be found in [PonSage23]. 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_{\ge}(T)$, by keeping all *decreasing relations* ($c \triangleleft 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_{\ge}(T)$. On the other hand, the increasing relation $2 \triangleleft T$ 5 is not part of $F_{\ge}(T)$. Similarly, we construct the *increasing forest*, $F_{\le}(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 \triangleleft 10$ is drawn on Figure 3.2 even though it is not a cover relation as we have $9 \triangleleft 8 \triangleleft 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_{\ge}(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_{\ge}(T)$ and $F_{\le}(T')$ have no linear extensions in common:
<figure><img src="image_32.png" /></figure>

(picture from [CP15])

<figure><img src="image_33.png" /><figcaption>Figure 3.3: Decreasing and increasing forests of two incompatible trees.</figcaption></figure>

the intersection of the intervals is empty. In this case, you cannot construct the interval-poset because the relations of $F_{\ge}(T)$ and $F_{\le}(T')$ are incompatible. For example, on Figure 3.3, we see that $2 \not\triangleleft 1$ in $F_{\ge}(T)$ while $1 \not\triangleleft 2$ in $F_{\le}(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
<figure><img src="image_34.png" /><figcaption>Figure 3.4: Bijection between Dyck paths and decreasing and increasing forests</figcaption></figure>

components in the decreasing forest: *i.e.* the poset where you keep only the decreasing relations (in red). 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^2z^3$ while the right is $x^3z^4$. The composition gives the polynomial
$$
\mathbb{B} \left( \begin{smallmatrix} 1 & 2 & 1 \\ | & & | \\ 3 & & 4 \end{smallmatrix}, \begin{smallmatrix} 2 & 3 & 1 \\ | & & | \\ 4 & & 2 \end{smallmatrix} \right) =
\begin{aligned}[t]
& \begin{smallmatrix} 1 & 2 & 4 \\ | & & | \\ 3 & 5 & 6-7 \end{smallmatrix} +
\begin{smallmatrix} 1 & 2 & 4 \\ | & & | \\ 3 & 5 & 6-7 \end{smallmatrix} \\
& +
\begin{smallmatrix} 1 & 2 & 4 \\ | & & | \\ 3 & 5 & 6-7 \end{smallmatrix} +
\begin{smallmatrix} 1 & 2 & 4 \\ | & & | \\ 3 & 5 & 6-7 \end{smallmatrix}
\end{aligned}
$$

(picture from [CP15])

<caption>Figure 3.5: Composition of interval-posets</caption>

$$
x^2 z^3 x z \frac{x^4 z^4 - z^4}{x-1} = x^3 z^8 (1 + x + x^2 + x^3) \quad (3.9)
$$

$$
= x^3 z^8 + x^4 z^8 + x^5 z^8 + x^6 z^8. \tag{3.10}
$$

This composition (and associated decomposition) allows us to recover the func-
tional equation (3.6). It also gives a natural way to write the generating function
$\Phi(z, x)$ of Tamari intervals as a sum over binary trees

$$
\Phi(z, x) = \sum_{T} z^{\text{size}(T)} \mathcal{B}_{T}(x) \qquad (3.11)
$$

where the sum is over binary trees and $\mathcal{B}_T(x)$ is a polynomial defined recursively
such that $\mathcal{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 $\mathcal{B}_T(x) = 1$
if $T$ is empty and otherwise

$$
\mathcal{B}_T(x) = x \mathcal{B}_L(x) \frac{x \mathcal{B}_R(x) - \mathcal{B}_R(1)}{x-1}. \quad (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 [Rog20, Rog21].

**3.4 Closed flows**

In [Cha14], 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 [CCP14].

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 [CCP14], we present a bijection between closed flows and Tamari interval-posets and obtain the following as a consequence.

**Theorem 2** (Theorem 4.1 from [CCP14]). *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.

## 3.5 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 [Pon19], 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 $\ell(v)$ satisfies $0 \le \ell(v) \le \text{size}(T_R(v)) - \sum_{w \in T_R(v)} \ell(w)$ where $T_R(v)$ is the right
<figure><img src="image_35.png" /></figure>

(picture from [CCP14])

<caption>Figure 3.6: Bijection between closed flows and Tamari interval-posets</caption>
<figure><img src="image_36.png" /><figcaption>Figure 3.7: Example of grafting tree with corresponding interval-poset decomposition.</figcaption></figure>

subtree of $v$. For example, on Figure 3.7, the label of the root must be comprised between 0 and 3 because the right subtree has 4 nodes and labels summing to 1. If labels all have maximal values, then it corresponds to the interval $[T, T]$ made of a single tree.

As they directly translate the functional equation, grafting trees are very natural objects to consider when working with Tamari intervals. I use them in [Pon19] 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 [CS03].

## 3.6 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} := \frac{m+1}{n(mn+1)} \binom{(m+1)^2n+m}{n-1}. \qquad (3.13) $$

This is proved in [BFP11] using an $m$-generalization of the functional equation (3.6)

$$ \Phi^{(m)}(z, x) = 1 + B^{(m)}(\Phi, \Phi, \dots, \Phi) \qquad (3.14) $$
<figure><img src="image_37.png" /><figcaption>Figure 3.8: Decomposition of *m*-binary trees and example for *m* = 2.</figcaption></figure>

where $B^{(m)}$ is an ($m+1$) linear form defined by

$$ B^{(m)}(f, g_1, \dots, g_m) = zxf\Delta(g_1\Delta(\dots\Delta(g_m)))\dots, \quad (3.15) $$

and

$$ \Delta(g) = \frac{xg(x) - g(1)}{x - 1}. \quad (3.16) $$

In other words, the product and divided difference are applied *m* times. The authors of [BFP11] 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 \triangleleft im - 1 \triangleleft \dots \triangleleft im - (m - 1). \quad (3.17) $$

See an example on Figure 3.9 for *m* = 2 and *n* = 11: you can check that we have $2i \triangleleft 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 [Pon19], we also explain how this translates to grafting trees. An *m*-Tamari interval poset corresponds to a grafting tree such that $\ell(v_i) \ge 1$ if $i \ne 0 \bmod 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.

<figure><img src="image_38.png" /><figcaption>Figure 3.9: An *m*-Tamari interval-poset and its corresponding grafting tree.</figcaption></figure>

## 3.7 Open questions

On Figure 3.10, we present the bijection of Bernadi and Bonichon [BB09] 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 [FFN23]? Beside, neither [BB09] nor [FFN23] (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)?
<figure><img src="image_39.png" /><figcaption>Figure 3.10: Bijection between interval-posets and triangulations</figcaption></figure>
# CHAPTER 4

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 [BFP11] 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 [CCP14], we provide this decomposition and note that it actually gives an involution on Tamari intervals. But it is only in [Pon19] 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 [BFP11] 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 [Pon19]. 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 gen-
eralize the involution to *m*-Tamari intervals. Note that the rise-contact involution
has been implemented into **SageMath**. The computations originally provided with
the paper [Pon19] are here [PonSage18], the specific examples of this Chapter are
available here [PonSage23].
## 4.1 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 [BFP11] 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, \dots, 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.

<figure><img src="image_40.png" /><figcaption>Figure 4.1: The complement involution on Tamari intervals</figcaption></figure>
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 \prec 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' \prec 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 \prec 8$ and $6 \prec 8$ on the first interval, which corresponds to the relations $2 \prec 1$ and $3 \prec 1$ on its image. We call this involution the *complement* of the interval-poset and write it $\Psi$.

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.

## 4.2 Rises, descents, and left-branch involution

The surprising result of [BFP11] 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 \prec 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”.
<figure><img src="image_41.png" /><figcaption>Figure 4.2: The left-branch involution on Tamari intervals</figcaption></figure>

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

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 $\Phi$, 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.

**4.3 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 [DH23].

We call a *Tamari inversion* on an interval-poset, a couple (a, c) with $1 \le a < c \le n$ such that: there is no b with $a \le b < c$ and $c \triangleleft b$, and no b with $a < b \le c$ with $a \triangleleft 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 \triangleleft i+1$ nor $i+1 \triangleleft 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.

<figure><img src="image_42.png" /><figcaption>Tamari inversions: (4, 7), (5, 6), (5, 7).</figcaption></figure>

<caption>Figure 4.3: Tamari inversions on an interval-poset and grafting tree</caption>

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 $\ell(v_4) \le 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 $\ell(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 $\Psi$ and $\Phi$ preserve the distance statistic. For the complement $\Psi$: 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 $\Psi(I)$. For the left-branch involution $\Phi$, we see that even though the shape of tree is changed, the size of the right subtrees and their labels are not.

## 4.4 The Rise-contact involution

Using $\Phi$ and $\Psi$, we obtain the following result.

**Theorem 4** (Theorem 54 of [Pon19]). Let $\beta$ be the rise-contact involution defined by $\beta := \Phi \circ \Psi \circ \Phi$. Then $\beta$ 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 $\beta$ is the conjugate of the $\Psi$ involution by $\Phi$ 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.

## 4.5 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 [BFP11]. 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 \times 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 \times 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
4.5. THE EXPAND-CONTRACT OPERATION ON M-TAMARI INTERVALS 57

<figure><img src="image_43.png" /><figcaption>Figure 4.4: The rise-contact involution on Tamari intervals</figcaption></figure>

from the interpretation of *m*-ballot paths as Dyck path of size *n* × *m* by replacing
each up step by *m* up-steps. This actually changes the rise vector but not the
contact vector. To solve this, we apply a simple transformation on the labels of *m*-
grafting tree: *ℓ*(vᵢ) = *mℓ*(vᵢ) if *i* ≡ 0 mod *m*, and *ℓ'(vᵢ)* = *mℓ(vᵢ) - 1*) otherwise.
This is the *expand* operation. The inverse operation is called the *contract*. We
illustrate this on Figure 4.5. In [Pon19], 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 [Pon19]). The *m*-rise-contact $\beta_m := \text{expand} \circ \beta \circ$ contract is an involution on *m*-Tamari intervals exchanging the *m*-contacts and the *m*-rises and proving Conjecture 17 of [PR12].
<figure><img src="image_44.png" /><figcaption>Figure 4.5: The expand operation on *m*-grafting trees</figcaption></figure>

**4.6 Open questions**

In [Pon19], 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 *v*-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 [BP12]. In his thesis [PR12], 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* (sabréatical) to work in Montreal with François Bergeron in particular. He introduced me to his recent work on *triangular partitions* [BM22] 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 [Pon22] and [LMP23]. The first one is a short note on a description of the Zeta function (from [Hag08]) 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.
# 5.1 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 [Hum90, Bro10]. 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 [Hag08, Hag20]. 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^j t^i$ 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 [BP12], 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_\lambda$ where $\lambda$ 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_\lambda$ where $\lambda$ has 3 parts.

### 5.1.2 Triangular partitions and Dyck paths

An *integer partition* $\lambda$ of size $n$ is a list of positive integers $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_k$ with $\sum_i \lambda_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 ($\lambda_j := 0$ for $j > k$). A *sub-partition* $\mu$ of $\lambda$ is a partition such that $\mu_i \le \lambda_i$ for all $i \ge 0$. Dyck paths of size $n$ are trivially in bijection with sub-partitions of the *staircase* integer partition $(n, n-1, \dots, 1)$. Indeed, we often represent partitions using their *Ferrers diagram* as on Figure 5.1: each line of the diagram contains $\lambda_i$ boxes. The top partition of Figure 5.1 is then $(2, 1)$. If $\mu$ is a sub-partition of $\lambda$, its Ferrers diagram is *contained* in the Ferrers diagram of $\lambda$. The frontier between the two partitions draws a *path* below the initial partition (in red on Figure 5.1). When $\lambda$ 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).

<figure><img src="image_45.png" /><figcaption>Figure 5.1: Dyck paths of size 3 as sub-partitions of (2, 1)</figcaption></figure>

This suggests a natural generalization of Dyck paths: changing the partition $\lambda$. This includes in particular the case of *rational Dyck paths*. Let $a$ and $b$ be two co-prime integers. Bizley [Biz54] gives a nice enumeration for paths made of north and east steps, above the line $y = \frac{a}{b}x$ and ending in $(a, b)$,

$$ \frac{1}{a+b} \binom{a+b}{a,b}. \qquad (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 [Ber17], 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* [BM22]. 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 [GHSR20], the authors use a formula from Gorsky and Negut [GN15] to obtain a $q, t$-enumeration of the sub-partitions of any partition $\lambda$, 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
<figure><img src="image_46.png" /><figcaption>Figure 5.2: The triangular partition (4, 3, 1) and the non-triangular partition (4, 4).</figcaption></figure>

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.

5.2 Understanding the “dinv”

5.2.1 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 [Hag03], 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 [ALW15], 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 [TW18].

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 ζ⁻¹). As it was not
a major result, I did not care to write it at the time. I finally did last year
in [Pon22] 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*
<figure><img src="image_47.png" /><figcaption>Figure 5.3: A Dyck path (as a sub-partition) with its area and area sequence.</figcaption></figure>

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 [PonSage22].

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*₁, ..., *a*ₙ where *a*₁ = 0 and 0 ≤ *a*ᵢ₊₁ ≤ *a*ᵢ + 1. The *area* is of course the sum of the *a*ᵢ. The *dinv* is also easy to compute from the area sequence: it is the number of couples (*a*ᵢ, *a*ⱼ) with *i* < *j* and *a*ⱼ = *a*ᵢ or *a*ⱼ = *a*ᵢ − 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 [Pon22]). *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 example on Figure 5.4 where insertion points are made visible. We prove that this map is actually $\zeta^{-1}$. In particular, we give a direct proof that the *area* of the new sequence is the *bounce* of the original one.

<table><caption>Figure 5.4: An example of the inverse zeta map bijection</caption><tr><td>0</td><td>·<sub>1</sub>0·<sub>0</sub></td></tr><tr><td>01</td><td>·<sub>2</sub>0·<sub>1</sub>0·<sub>0</sub></td></tr><tr><td>012</td><td>·<sub>3</sub>0·<sub>2</sub>0·<sub>1</sub>0·<sub>0</sub></td></tr><tr><td>0121</td><td>00·<sub>2</sub>1·<sub>0</sub>0·<sub>1</sub></td></tr><tr><td>01211</td><td>001·<sub>1</sub>0·<sub>2</sub>1·<sub>0</sub></td></tr><tr><td>012111</td><td>001·<sub>2</sub>2·<sub>0</sub>01·<sub>1</sub></td></tr><tr><td>0121112</td><td>001·<sub>3</sub>2·<sub>1</sub>2·<sub>0</sub>01·<sub>2</sub></td></tr><tr><td>01211123</td><td>001·<sub>4</sub>2·<sub>2</sub>2·<sub>1</sub>2·<sub>0</sub>01·<sub>3</sub></td></tr><tr><td>012111233</td><td>0012·<sub>3</sub>2·<sub>2</sub>2·<sub>1</sub>01·<sub>4</sub>2·<sub>0</sub></td></tr><tr><td>0121112330</td><td>001222012·<sub>1</sub>3·<sub>0</sub></td></tr><tr><td>01211123301</td><td>001222012·<sub>2</sub>3·<sub>1</sub>3·<sub>0</sub></td></tr><tr><td>012111233011</td><td>0012220123·<sub>2</sub>4·<sub>0</sub>3·<sub>1</sub></td></tr><tr><td>0121112330110</td><td>00122201234·<sub>1</sub>5·<sub>0</sub>3</td></tr><tr><td>01211123301101</td><td>00122201234·<sub>2</sub>5·<sub>1</sub>5·<sub>0</sub>3</td></tr><tr><td>01211123301102</td><td>00122201234·<sub>3</sub>5·<sub>2</sub>5·<sub>1</sub>5·<sub>0</sub>3</td></tr><tr><td>0121112330110122</td><td>001222012345·<sub>3</sub>6·<sub>0</sub>5·<sub>2</sub>5·<sub>1</sub>3</td></tr><tr><td>01211123301101221</td><td>0012220123456·<sub>1</sub>55·<sub>2</sub>6·<sub>0</sub>3</td></tr></table>

### 5.2.2 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 [BM22] provide a very simple criteria for deciding if 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 sense 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 [LMP23], 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 $\lambda$ can be filled with numbers to form a *tableau*. It is called a *standard*
<figure><img src="image_48.png" /><figcaption>Figure 5.5: Similar cells, Triangular young tableau and deficit</figcaption></figure>

Young tableau if it contains exactly the numbers 1, ..., n such that the numbers are increasing on each line and each column. Let $\theta$ be a standard Young tableau of shape $\lambda$ where $\lambda$ is a triangular partition. We say that there is a $\theta$-inversion in a sub-partition $\mu$ of $\lambda$ if there is a cell $c$ inside $\mu$ with a higher value in $\theta$ than another cell $c'$ outside of $\mu$. 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 $\theta$.

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

<figure><img src="image_49.png" /><figcaption>Figure 5.6: Construction of the triangular tableau</figcaption></figure>

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 $\lambda$, 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-symmetric* 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.

## 5.3 Lattice interval enumeration and Schur-po-sitivity

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 representa-tion 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 $\nu$-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 $\nu$-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 [LMP23])**. The *q*, *t*-enumeration of intervals of the $\nu$-Tamari lattice on triangular 2-partitions is symmetric and Schur-positive.

The statistic corresponding to *q* is the distance while the statistic correspond-ing 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 [LMP23]). Let $\lambda$ be a triangular partition such that the top-down tableau of $\lambda$ is sim-sym, then the $q, t$-enumeration of $\nu$-Tamari intervals is symmetric and Schur-positive.

## 5.4 Open questions

We have seen already that the general field of $q, t$-Catalan combinatorics has many open questions as we can read in [PR12] and [Ber17]. 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 $\zeta$ function on triangular partitions. I do not know if the general definition of sweep maps from [ALW15] which was later proven to be bijective in [TW18] 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
<figure><img src="image_50.png" /></figure>
# 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 interval-posets? 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 [PP20].

This chapter is dedicated to [CPP19] where we explore the lattice structure of integer posets, and [PP20] which is about Hopf algebraic aspects. The results from both papers were originally presented in a FPSAC conference poster [PP18b]. 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.
## 6.1 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 into *increasing relations* (in blue, from left to right, on top) and *decreasing relations* (in red, from right to left, on bottom).

<figure><img src="image_51.png" /><figcaption>Figure 6.1: Permutations, binary trees, and binary sequences as integer posets</figcaption></figure>

Now we can construct interval-posets of the corresponding lattices (the weak order, the Tamari lattice, and the boolean lattice). For each interval $e \preceq 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 gives 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)
relation $a \triangleleft c$ (resp. $c \triangleleft a$) implies something on the increasing (resp. decreasing) relations $a \triangleleft b$ and $b \triangleleft c$ (resp. $c \triangleleft b$ and $b \triangleleft a$). We illustrate the different conditions in Figure 6.3.

<figure><img src="image_52.png" /><figcaption>Figure 6.2: Construction of a weak order interval-poset</figcaption></figure>

<table><caption>Figure 6.3: Conditions on interval-posets</caption><thead><tr><th></th><th>intervals of permutations (weak order)</th><th>intervals of binary trees (Tamari lattice)</th><th>intervals of binary sequence (boolean lattice)</th></tr></thead><tbody><tr><td>a b c &rarr;</td><td>a b c or<br>a b c</td><td>a b c</td><td>a b c</td></tr><tr><td>a b c &rarr;</td><td>a b c or<br>a b c</td><td>a b c</td><td>a b c</td></tr></tbody></table>

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 [CPP19], 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 increas-
ing 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 de-
compositions 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.

6.2 Integer Relations

6.2.1 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 \in S$ and $y \in S$. We write $x R y$ if $x$ is in relation with $y$ and $x \nparallel y$ if not. We consider only *reflexive* relations, i.e., $x R x$ for all $x \in 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, \dots, 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^{\text{inc}}$, i.e., the couples $a R b$ with $a < b$ and decreasing relation $R^{\text{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 \prec_S S$, if and only if $R^{\text{Dec}} \subseteq S^{\text{Dec}}$ and $S^{\text{inc}} \subseteq R^{\text{inc}}$ (Definition 1.1 of [CPP19]).

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.4. Integers 1 to *n* are
<figure><img src="image_53.png" /><figcaption>Figure 6.4: The boolean lattice (on the left) and the weak order (on the right) on integer relations.</figcaption></figure>

written on a single line. Each increasing relation $a \mathbf{R} b$ is shown as a blue arc (from left to right) over the vertices while each decreasing relation $b \mathbf{R} a$ is a red arc (from right to left) under the vertices.

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.

<figure><img src="image_54.png" /><figcaption>Figure 6.5: Join and meet on integer relations</figcaption></figure>
<figure><img src="image_55.png" /></figure>

$$ \mathbb{F}\mathcal{R}_{1 \sim 2} \cdot \mathbb{F}\mathcal{R}_1 = \mathbb{F}\mathcal{R}_{1 \sim 2 \sim 3} + \mathbb{F}\mathcal{R}_{1 \sim 2 \sim 3} + \mathbb{F}\mathcal{R}_{1 \sim 2 \sim 3} + \dots + \mathbb{F}\mathcal{R}_{1 \sim 2 \sim 3 \sim 4} $$

(picture from [PP20])

<caption>Figure 6.6: Product in the Hopf algebra of integer relations as an interval</caption>

### 6.2.2 As a Hopf algebra

Let $\mathcal{R}$ be the set of all integer relations, $\mathcal{R}_n$ the set of integer relations of size $n$, and $\mathbf{k}$ a field. Then we can define a Hopf algebra on the vector space $\mathbf{k}\mathcal{R} := \bigoplus_{n \ge 0} \mathbf{k}\mathcal{R}_n$.

The product (on the fundamental basis $\mathbb{F}\mathcal{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, \dots, n$ is R and the subrelation on $n+1, \dots, n+m$ is the shifted version of S, written $\bar{S}$. In other words, an relation $T$ of the shifted shuffle is obtained by concatenating R and $\bar{S}$ and adding some increasing relations from R to $\bar{S}$ and some decreasing relations from $\bar{S}$ to R. In particular, the shifted shuffle has cardinality $2^{2^{mn}}$.

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 \setminus S$, the relation where all increasing relations have been added between R and $\bar{S}$ and no decreasing relations. While the maximal element is $R/S$, the relation where all decreasing relations have been added between $\bar{S}$ and R and no increasing relations. See an example on Figure 6.6.
The coproduct on $k\mathcal{R}$ is defined using the notion of *total cuts* of a relation (Definition 10 of [PP20]). A total cut on relation $R$ of size $n$ is a partition of $1, \dots, n$ into two sets $X$ and $Y$ such that for all $x \in X$ and $y \in Y$, we have $x R y$ and $y \nleq 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

$$ \Delta(F\mathcal{R}_{\underset{1}{\uparrow} \underset{2}{\downarrow} \underset{3}{\uparrow}}) = F\mathcal{R}_{\underset{1}{\uparrow} \underset{2}{\downarrow} \underset{3}{\uparrow}} \otimes F\mathcal{R}_{\emptyset} + F\mathcal{R}_{1} \otimes F\mathcal{R}_{\underset{1}{\uparrow} \underset{2}{\downarrow} \underset{3}{\uparrow}} + F\mathcal{R}_{\underset{1}{\uparrow} \underset{2}{\downarrow} \underset{3}{\uparrow}} \otimes F\mathcal{R}_{1} + F\mathcal{R}_{\emptyset} \otimes F\mathcal{R}_{\underset{1}{\uparrow} \underset{2}{\downarrow} \underset{3}{\uparrow}} $$

where the total cuts are $(\{1, 2, 3\}, \emptyset), (\{1\}, \{2, 3\}), (\{1, 3\}, \{2\}),$ and $(\emptyset, \{1, 2, 3\})$.

We prove in [PP20, Proposition 15] that the product and coproduct indeed define a graded Hopf algebra on $k\mathcal{R}$. 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\backslash S$).

# 6.3 Integer Posets

## 6.3.1 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.

<figure><img src="image_56.png" /><figcaption>Figure 6.7: Meet of two transitive relations.</figcaption></figure>

We write $\mathcal{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 \wedge S$ is *not* an antisymmetric relation. This means that we have $x$ and $y$ with $x \leq y$ and $y \leq x$. We suppose $x < y$. The decreasing relations of $T$ are the intersection of the decreasing relations of $R$ and $S$,
<figure><img src="image_57.png" /><figcaption>Figure 6.8: The weak order lattice on integer posets</figcaption></figure>

so we have $y \in R \ x$ and $y \in 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 antisymmetric (transitive) relations form a sublattice of the transitive relations. This gives the main theorem of [CPP19].
**Theorem 9** (Theorem 1 from [CPP19]). *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 [GP20].

### 6.3.2 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.

<figure><img src="image_58.png" /><figcaption>(picture from [PP20])</figcaption></figure>

**Figure 6.9:** Interval corresponding to the product of integer posets.
### 6.3.3 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* [PonMisc17]. This was an occasion to present the notion of *poset* using the illustration of the *closet-poset* of Figure 6.10.

<figure><img src="image_59.png" /><figcaption>Figure 6.10: The Closet-Poset</figcaption></figure>

## 6.4 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 \prec c$ we need to have $a \prec b$ or $b \prec c$ for $a < b < c$ (with symmetrical conditions on decreasing relations). In the case of Tamari interval-posets, we “force” to always have $b \prec c$. We could also force to always have $a \prec b$.
6.4. INDUCED STRUCTURES ON PERMUTATIONS, BINARY TREES AND MORE 81

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 \prec c$ with $a < 2 < c$ forces the relation $2 \prec c$, whereas each increasing relation $a \prec c$, with $a < 3 < c$ forces the relation $a \prec 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 \prec b$ or $b \prec 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 $[\text{KLN}^+01]$ and more generally in [DHP16]. The facial order on the faces of the associahedron is found in [DHP16, NT06, PR06]. This construction also generalizes to the faces of the permutreehedron (we define this polytope in the next Chapter).

In [PP20], we study the induced Hopf algebraic structures and obtain the following.

**Theorem 10** (from [PP20]). *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 [CPP19]. Using similar processes, we reconstruct the Malvenuto-Reutenauer Hopf algebra on permutations [MR95] and the Chapoton Hopf algebra on faces of the permutahedron [Cha00].

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 [LR98] and a Hopf algebra on the faces of the associahedron [Cha00]. All these constructions generalize to permutrees.
## 6.5 Open questions

In [Foi13], 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?
*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 [CP17], 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 [MR95].

In this chapter, we present the results of two papers: first [PP18] (also presented at EUROCOMB in [PP17]) in collaboration with Vincent Pilaud, then [PPTJ23] (also presented at FPSAC in [PPTJ21]) 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.

### 7.1 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 \to i+1$ or $i \leftarrow i+1$ for each $1 \le i < n-1$. If we have $i \to i+1$, we contract the edge between the permutations
$s_{i+1} = 1 \dots i(i+2)(i+1) \dots n$ and $s_{i+1}s_i = 1 \dots (i+2)i(i+1) \dots n$. This is the "right" side of the initial hexagon formed by $s_i$ and $s_{i+1}$. Symmetrically, if we have $i \leftarrow i+1$, we contract the edge between the permutations $s_i = 1 \dots (i+1)i(i+2)\dots n$ and $s_i s_{i+1} = 1 \dots (i+1)(i+2)i \dots n$, the "left" side of the hexagon. We then take the lattice congruence generated by these contractions.

For Cambrian congruences, each edge needs 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 Figure 7.1 the examples on size 4 for the orientations $1 \leftarrow 2 \rightarrow 3$ and $1 \leftrightarrow 2 \rightarrow 3$. The initial contracted edges are in red. Other contracted edges are in blue. Two permutations are in the same class if there is a path of contracted edges between them.

<figure><img src="image_60.png" /><figcaption>Figure 7.1: Two examples of permutree congruences.</figcaption></figure>

These congruences form a subfamily with interesting properties of the set of all lattice congruences of the weak order studied by Reading in [Rea04]. 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 $\delta \in$
<figure><img src="image_61.png" /><figcaption>Figure 7.2: The permutree congruences, for all decorations $\delta \in \Theta$. $\{\Theta, \mathcal{Y}, \mathcal{Y}, \mathcal{X}\}^2 \cdot \Theta$.</figcaption></figure>
`{1, 2, 3, 4}^n` called the *decoration* using the following rules

$$i \to i + 1 \quad \delta_{i+1} = 1;$$

$$i \to i + 1 \quad \delta_{i+1} = 2;$$

$$i \leftrightarrow i + 1 \quad \delta_{i+1} = 3;$$

$$i \leftrightarrow i + 1 \quad \delta_{i+1} = 4.$$

These symbols correspond to certain type of nodes in the permutrees as we explain in Section 7.2. The first and last symbols $\delta_1$ and $\delta_n$ are set to $1$ 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 \leftarrow 2 \leftarrow 3$ and $1 \leftrightarrow 2 \leftarrow 3$ of Figure 7.1 correspond to the words $123$ and $143$ 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 $\delta_b \in \{\textcircled{1}, \textcircled{2}\}$ and *bca* with $a < b < c$ and $\delta_b \in \{\textcircled{3}, \textcircled{4}\}$. For example, 2413 is not minimal in its class for $\delta = \textcircled{1}\textcircled{2}\textcircled{1}$ because it contains 241 and $\delta_2 = \textcircled{3}$. This characterization is given in [PP18, Corollary 2.14]. We use it in [PPTJ23] to characterize the reduced words of the minimal class elements as explained in Section 7.7.

## 7.2 Permutree insertion and permutree lattice

<figure><img src="image_62.png" /><figcaption>Figure 7.3: The labeling rules on permutrees.</figcaption></figure>

Permutrees are directed (from bottom to top) planar non rooted trees, labeled by exactly the numbers $1, \dots, n$ and such that each node is of certain type defined by a symbol in `{1, 2, 3, 4}`. The image of the symbol represents the incoming / outgoing edges and implies certain rules illustrated on Figure 7.3. A node `1` has one incoming edge and one outgoing edge. A node `2` has two incoming edges and one outgoing edge. A node `3` has one incoming edge and two outgoing edges. And a node `4` 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 $\mathcal{Y}$ and $\mathcal{X}$ are *down symbols* as they have two incoming edges. Similarly, we write that $\mathcal{Y}$ and $\mathcal{X}$ are *up symbols*. In particular $\mathcal{X}$ is both an up and a down symbol while $\mathcal{Y}$ 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 $\sigma$ of size $n$ and a decoration $\delta \in \{\text{Θ}, \text{Λ}, \text{Υ}, \text{⊗}\}^n$ and constructs a permutree with decoration $\delta$. We often write the decoration directly on the values of the permutation for convenience. A value $v$ is underlined if $\delta_v$ is a down symbol and overlined if $\delta_v$ is an up symbol. For example the decorated permutation $\overline{2751346}$ corresponds to the decoration $\text{ΘΥ}\text{Θ}\text{Θ}\text{Θ}\text{Θ}\text{Υ}$.

<figure><img src="image_63.png" /><figcaption>Figure 7.4: The insertion algorithm on the decorated permutation $\overline{2751346}$.</figcaption></figure>

The algorithm is as follows. For all $1 \le i \le n$, we place the symbol $\delta_i$ at position $(\sigma_i, i)$. The values $1, \dots, 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 $\sigma_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.

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 $\delta = \mathbf{1}^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 $\delta = \mathbf{2}^n$, the algorithm is the binary search tree insertion described in Section 2.2 (see the second example of Figure 7.5). If $\delta \in \{\mathbf{2}, \mathbf{3}\}^n$, this is the Cambrian tree insertion that can be found in [CP17]. If $\delta = \mathbf{3}^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.

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

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

$$ \dots ac \dots \underline{b} \dots \equiv \dots ca \dots \underline{b} \dots, \qquad (7.1) $$

$$ \dots \bar{b} \dots ac \dots \equiv \dots \bar{b} \dots ca \dots, \qquad (7.2) $$

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 $\overline{2751346} = \overline{2751346}$ as we are able to exchange $\overline{7}$ and $\overline{2}$ because they have a witness on the right (either $\overline{4}$ or $\overline{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 $\overline{2751346} = \overline{2715346}$ because 5 and 1 can be exchanged thanks to the witness $\overline{2}$ to the left with an up decoration.

Each decoration $\delta$ defines a lattice congruence [PP18, Proposition 2.13]. We thus obtain $\delta$-permutree lattices (see Figure 7.7). The rotation on permutrees is natural generalization of the rotation on binary trees.
<figure><img src="image_65.png" /><figcaption>Figure 7.6: The permuto tree congruence on decorated permutations.</figcaption></figure>

## 7.3 Numerology

There is a very natural question: given a certain decoration $\delta$, how many $\delta$-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($\delta$)* and provide a recursive formula which interpolates between the factorial and Catalan numbers.

Indeed, the Catalan numbers satisfy a well known recursion

$$C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k} \qquad (7.3)$$

with $C_0 = 1$. On the other hand, the factorial numbers satisfy

$$n! = n(n-1)! = \sum_{i=1}^{n} (n-1)! \qquad (7.4)$$

The idea is then to *mix* those two summations depending on the actual symbols of $\delta$. The first essential property is given in [PP18, Corollary 2.21]: only the positions of the $\otimes$ and $\oplus$ matter. In particular a $\otimes$ symbol can be changed into a $\oplus$ without changing the value of $C(\delta)$.

Besides, the case of the $\otimes$ symbol is actually trivial. If $\delta_i = \otimes$, we have that $C(\delta) = C(\delta_1 \dots \delta_{i-1} \otimes) C(\otimes \delta_{i+1} \dots \delta_n)$. For example, for $\delta = \otimes \otimes \otimes \otimes$, we indeed get

$$C(\delta) = C(\otimes \otimes) C(\otimes \otimes) C(\otimes \otimes) = 2^3 \qquad (7.5)$$

Then for $\delta \in \{\otimes, \oplus, \otimes\}^n$, we get a recursive formula summing over all possibilities to remove one symbol,
<figure><img src="image_66.png" /><figcaption>Figure 7.7: The $\delta$-permutree lattices, for the decorations $\delta = \textcircled{1}\textcircled{1}\textcircled{1}\textcircled{1}$ (left) and $\delta = \textcircled{1}\textcircled{1}\textcircled{1}\textcircled{1}$ (right)</figcaption></figure>

$$ C(\delta) = \sum_{\delta_i=\textcircled{1}} C(\delta_1 \dots \delta_{i-1} \delta_{i+1} \dots \delta_n) + \sum_{\delta_i \in \{\textcircled{1}, \textcircled{2}\}} C(\delta_1 \dots \delta_{i-1}) C(\delta_{i+1} \dots \delta_n). \quad (7.6) $$

When the removed symbol is $\textcircled{1}$, we simply sum on the decoration of size $n-1$ as in (7.4). When the removed symbol is $\textcircled{1}$ or $\textcircled{2}$, 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(\textcircled{1}\textcircled{1}\textcircled{1}) = 2C(\textcircled{1}\textcircled{1}\textcircled{1}) + C(\textcircled{1}\textcircled{1})C(\textcircled{1}) + C(\textcircled{1}\textcircled{1}\textcircled{1}) \quad (7.7) $$

$$ = 2 \times 5 + 2 + 6 = 18 \qquad (7.8) $$

$$ C(\textcircled{1}\textcircled{1}\textcircled{1}) = C(\textcircled{1}\textcircled{1})C(\textcircled{1}\textcircled{1}\textcircled{1}) \quad (7.9) $$

$$ = 2 \times 5 = 10 \qquad (7.10) $$
## 7.4 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 [Pos09]. 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 associated permutahedron (See Section 2.4) and obtain a geometrical realization of the permutree lattices. More precisely, for every decoration $\delta$, we define a polytope $\text{PT}(\delta)$ called the *permutreehedron* as the convex hull of the vertices $\mathbf{a}(\text{PT})$ for $T$ a $\delta$-permutree. Each coordinate of $\mathbf{a}(\text{PT})$ is computed as follows:

$$ \mathbf{a}(\text{PT})_i = \begin{cases} 1+d & \text{if } \delta_i = \mathbf{\emptyset}, \\ 1+d+\frac{\ell r}{\bar{l}\bar{r}} & \text{if } \delta_i = \mathbf{\emptyset}, \\ 1+d-\frac{\bar{l}\bar{r}}{\ell r} & \text{if } \delta_i = \mathbf{\emptyset}, \\ 1+d+\frac{\ell r}{\bar{l}\bar{r}}-\frac{\bar{l}\bar{r}}{\ell r} & \text{if } \delta_i = \mathbf{\emptyset}, \end{cases} $$

where $d$ is the number of descendants of $i$, $\ell$ and $\bar{\ell}$ are the number of left and right descendants of $i$, and $\bar{r}$ and $\ell$ 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 $\delta$, The permutreehedron $\text{PT}(\delta)$ is the polytope corresponding to the $\delta$-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 $\delta$-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, \dots, 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, \dots, 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
<figure><img src="image_67.png" /><figcaption>Figure 7.8: The permutreehedra, for all decorations $\delta \in \mathcal{D}$. $\{\mathbf{\Theta}, \mathbf{\Theta}, \mathbf{\Theta}, \mathbf{\Theta}\}^2 \cdot \mathcal{D}$.</figcaption></figure>
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 [PS19], 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 [APR21] that the permutree congruences are exactly the congruences that can be realized as removahedra.

## 7.5 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.

<figure><img src="image_68.png" /><figcaption>Figure 7.9: The Schröder permutree lattices for $\mathbf{1}^3$, $\mathbf{2}^3$, $\mathbf{3}^3$</figcaption></figure>

## 7.6 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.

$$ \begin{aligned} \mathbb{F}_{\overline{231}} \cdot \mathbb{F}_{\overline{12}} = & \mathbb{F}_{\overline{231}\overline{45}} + \mathbb{F}_{\overline{23}\overline{41}} + \mathbb{F}_{\overline{2}\overline{43}\overline{15}} + \mathbb{F}_{\overline{23}\overline{45}\overline{1}} + \mathbb{F}_{\overline{4}\overline{23}\overline{15}} \\ & + \mathbb{F}_{\overline{2}\overline{4}\overline{35}\overline{1}} + \mathbb{F}_{\overline{4}\overline{2}\overline{35}\overline{1}} + \mathbb{F}_{\overline{2}\overline{4}\overline{5}\overline{3}\overline{1}} + \mathbb{F}_{\overline{4}\overline{2}\overline{5}\overline{3}\overline{1}} + \mathbb{F}_{\overline{4}\overline{5}\overline{2}\overline{3}\overline{1}}. \end{aligned} \quad (7.11) $$

Conversely, on the co-product (or the product in the dual Hopf algebra), the decoration is attached to its position as in

$$ \begin{aligned} \mathbb{G}_{\overline{312}} \cdot \mathbb{G}_{\overline{12}} = & \mathbb{G}_{\overline{312}\overline{45}} + \mathbb{G}_{\overline{412}\overline{35}} + \mathbb{G}_{\overline{413}\overline{25}} + \mathbb{G}_{\overline{512}\overline{34}} + \mathbb{G}_{\overline{423}\overline{15}} \\ & + \mathbb{G}_{\overline{513}\overline{24}} + \mathbb{G}_{\overline{523}\overline{14}} + \mathbb{G}_{\overline{514}\overline{23}} + \mathbb{G}_{\overline{524}\overline{13}} + \mathbb{G}_{\overline{534}\overline{12}}. \end{aligned} \quad (7.12) $$

We define a basis indexed by permutrees. The element indexed by a permutree $T$ is a sum over all decorated permutations $\sigma$ 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.

$$ \mathbb{P} = \mathbb{F}_{\overline{21354}\overline{76}} + \mathbb{F}_{\overline{21357}\overline{46}} + \mathbb{F}_{\overline{21375}\overline{46}} + \cdots + \mathbb{F}_{\overline{75231}\overline{46}} + \mathbb{F}_{\overline{75234}\overline{16}} + \mathbb{F}_{\overline{752346}\overline{1}}. $$

**Theorem 12 (Theorem 4.5 of [PP18]).** The elements $(\mathbb{P}_T)$ where $T$ is a permutree form a Hopf subalgebra of the decorated version of $\mathbf{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 $\mathbf{FQSym}$ and we also obtain direct descriptions of the operations.

<figure><img src="image_69.png" /><figcaption>Figure 7.10: Grafting two permutrees (left) and cutting a permutree (right).</figcaption></figure>

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 [Cha00].
## 7.7 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 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^\infty$ 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^\infty$ 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 [PPTJ23] 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) \leftarrow j$.

<figure><img src="image_70.png" /><figcaption>Figure 7.11: The automaton $U(j)$ to.</figcaption></figure>

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 [PPTJ23]). *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 \leftarrow 2 - 3$ of Figure 7.1 (left), the reduced word $s_2s_1s_3$ is accepted which means that the
permutation 3142 is minimal in its class. On the other hand, $s_1s_2$ (permutation 2314) and $s_2s_1s_2s_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.

## 7.8 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 [APR21] can be extended? We would also like to consider permutrees as subsets of root systems like in the work of Gay and Pilaud [GP20].
# Part IV

## Generalizations
<figure><img src="image_71.png" /></figure>