Algebraic combinatorics on order of trees

Combinatoire algébrique liée aux ordres sur les arbres

Grégory Chatel (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

This thesis comes within the scope of algebraic combinatorics and studies of order structures on multiple tree families. We first look at the Tamari lattice on binary trees. This structure is obtained as a quotient of the weak order on permutations : we associate with each tree the interval of the weak order composed of its linear extensions. Note that there exists a bijection between intervals of the Tamari lattice and a family of poset that we callinterval-posets. The set of linear extensions of these posets is the union of the sets of linear extensions of the trees of the corresponding interval. We give a characterization of the posets satisfying this property and then we use this new family of objet on a large variety of applications. We first build another proof of the fact that the generating function of the intervals of the Tamari lattice satisfies a functional equation described by F. Chapoton. Wethen give a formula to count the number of trees smaller than or equal to a given tree in the Tamari order and in the "m"-Tamari order. We then build a bijection between interval-posets and flows that are combinatorial objects that F. Chapoton introduced to study the Pre-Lieoperad. To conclude, we prove combinatorially symmetry in the two parameters generating function of the intervals of the Tamari lattice. In the next part, we give a Cambrian generalization of the classical Hopf algebra of Loday-Ronco on trees and we explain their connection with Cambrian lattices. We first introduce our generalization of the planar binary tree Hopf algebra in the Cambrian world. We call this new structure the Cambrian algebra. We build this algebra as a Hopf sub algebra of a permutation algebra. We then study multiple properties of this objet such as its dual, its multiplicative basis and its freeness. We then generalize the Baxter algebra of S. Giraudo to the Cambrian world. We call this structure the Baxter-Cambrian Hopf algebra. The Baxter numbers being well-studied, we then explored their Cambrian counter parts, the Baxter-Cambrian numbers. To conclude this part, we give a generalization of the Cambrian algebra using a packed word algebra instead of a permutation algebra as a base for our construction. We call this new structure the Schröder-Cambrian algebra

Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur l'étude et les applications de structures d'ordre sur plusieurs familles d'arbres. Dans un premier temps, nous étudions le treillis de Tamari sur les arbres binaires. Celui-ci s'obtient comme un quotient de l'ordre faible sur les permutations : à chaque arbre est associé un intervalle de l'ordre faible sur les permutations formé par ses extensions linéaires. Nous observons qu'il est possible de mettre en bijection les intervalles de l'ordre de Tamari avec une famille de posets particulière : les intervalles-posets. L'ensemble des extensions linéaires de ces posets est l'union des ensembles des extensions linéaires des arbres qui composent l'intervalle. Nous donnons une caractérisation des posets qui vérifient cette condition puis nous utilisons ce nouvel objet de plusieurs façons différentes. Nous fournissons tout d'abord une preuve alternative du fait que la fonction génératrice des intervalles de l'ordre de Tamari vérifie une équation fonctionnelle décrite par F. Chapoton. Nous donnons ensuite une formule qui permet de compter le nombre d'arbres inférieurs ou égaux à un arbre donné dans l'ordre de Tamari et dans l'ordre de m-Tamari. Nous construisons également une bijection entre les intervalles-posets et les flots, un objet que F. Chapoton a introduit lors de l'étude de l'opérade Pre-Lie. Pour finir, nous démontrons de façon combinatoire la répartition de deux statistiques dans la fonction génératrice des intervalles de l'ordre de Tamari. Dans la partie suivante, nous donnons une généralisation Cambrienne d'algèbres de Hopf classique et expliquons leurs liens avec les treillis Cambriens. Dans un premier temps, nous présentons une généralisation de l'algèbre de Hopf des arbres binaires planaires au monde Cambrien que nous appelons algèbre Cambrienne. Nous introduisons cette algèbre comme une sous-algèbre de Hopf d'une l'algèbre de permutations. Nous étudions diverses propriétés de cette structure comme par exemple son dual, ses bases multiplicatives et sa liberté. Nous étudions ensuite une généralisation de l'algèbre de Baxter définie par S. Giraudo que nous appelons algèbre Baxter-Cambrienne. Les nombres de Baxter ayant de nombreuses propriétés combinatoires, nous nous sommes intéressés par la suite à leur équivalent Cambrien, les nombres Baxter-Cambriens. Pour finir, nous donnons une généralisation de l'algèbre Cambrienne en utilisant une algèbre de mots tassés plutôt qu'une algèbre de permutations comme base de notre construction. Nous appelons cette nouvelle structure l'algèbre Schröder-Cambrienne

Mots clés: Combinatorics; Algebra; Lattice; Order; Tree; Tamari

Mots clés: Combinatoire; Algèbre; Treillis; Ordre; Arbre; Tamari

Domaines: Informatique et langage [cs.CL]

Grégory Chatel. Combinatoire algébrique liée aux ordres sur les arbres. Informatique et langage [cs.CL]. Université Paris-Est, 2015. Français. ⟨NNT : 2015PESC1136⟩. ⟨tel-01286087⟩