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

Abstract : 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
Document type :
Complete list of metadatas

Cited literature [62 references]  Display  Hide  Download
Contributor : Abes Star <>
Submitted on : Thursday, March 10, 2016 - 11:41:23 AM
Last modification on : Wednesday, December 19, 2018 - 10:47:33 AM
Long-term archiving on : Monday, June 13, 2016 - 9:14:11 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01286087, version 1


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⟩



Record views


Files downloads