Algebraic combinatorics on trees
Combinatoire algébrique des arbres
Résumé
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
Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur la construction de plusieurs structures combinatoires et algébriques sur différentes espèces d'arbres. Après avoir défini un analogue du monoïde plaxique dont les classes d'équivalence sont indexées par les couples d'arbres binaires jumeaux, nous proposons un analogue de la correspondance de Robinson-Schensted dans ce contexte. À partir de ce monoïde, nous construisons une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les couples d'arbres binaires jumeaux. Ensuite, nous proposons un foncteur combinatoire de la catégorie des monoïdes vers la catégorie des opérades ensemblistes. En utilisant ce foncteur, nous construisons plusieurs opérades qui mettent en jeu divers objets combinatoires. Par le biais d'une construction qui à une opérade associe une algèbre de Hopf non commutative, nous obtenons à partir de l'une des opérades obtenue par notre construction, une algèbre de Hopf basée sur les forêts ordonnées d'arbres plans enracinés. Nous proposons une réalisation polynomiale de cette dernière. Finalement, nous établissons certaines propriétés vérifiées par les arbres binaires équilibrés dans le treillis de Tamari. Nous montrons que l'ensemble des arbres binaires équilibrés y est clos par intervalle et que les intervalles d'arbres binaires équilibrés ont la forme d'hypercubes. Dans l'objectif de dénombrer ces intervalles, nous introduisons une nouvelle sorte de grammaires d'arbres, les grammaires synchrones. Celles-ci permettent d'obtenir une équation fonctionnelle de point fixe pour la série génératrice des arbres qu'elles engendrent
Origine : Version validée par le jury (STAR)
Loading...