Combinatoire algébrique des arbres

Abstract : This thesis comes within the scope of algebraic combinatorics and deals with the construction of several combinatorial and algebraic structures on different tree species. After defining an analogue of the plactic monoid whose equivalence classes are indexed by pairs of twin binary trees, we propose in this context an analogue of the Robinson-Schensted correspondence. From this monoid, we construct a Hopf subalgebra of the Hopf algebra of free quasi-symmetric functions whose bases are indexed by pairs of twin binary trees.Then, we propose a combinatorial functor from the category of monoids to the category of set-operads. Using this functor, we construct several operads that involve various combinatorial objects. Through a construction that brings a noncommutative Hopf algebra from an operad, we obtain from one of the operads obtained by our construction, a Hopf algebra based on ordered forests of planar rooted trees. We propose a polynomial realization of the latter.Finally, we establish some properties satisfied by balanced binary trees in the Tamari lattice. We show that the set of balanced binary trees is closed by interval and that the intervals of balanced binary trees have the shape of hypercubes. To enumerate these intervals, we introduce a new kind of tree grammars, namely the synchronous grammars. They allow to obtain a fixed-point functional equation for the generating series of the generated trees
Document type :
Complete list of metadatas

Cited literature [63 references]  Display  Hide  Download
Contributor : Abes Star <>
Submitted on : Monday, February 27, 2012 - 5:07:40 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Friday, November 23, 2012 - 3:10:49 PM


Version validated by the jury (STAR)


  • HAL Id : pastel-00674619, version 1


Samuele Giraudo. Combinatoire algébrique des arbres. Autre [cs.OH]. Université Paris-Est, 2011. Français. ⟨NNT : 2011PEST1023⟩. ⟨pastel-00674619⟩



Record views


Files downloads