Combinatoire algébrique des arbres

Résumé : 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
Type de document :
Thèse
Autre [cs.OH]. Université Paris-Est, 2011. Français. <NNT : 2011PEST1023>
Liste complète des métadonnées


https://pastel.archives-ouvertes.fr/pastel-00674619
Contributeur : Abes Star <>
Soumis le : lundi 27 février 2012 - 17:07:40
Dernière modification le : jeudi 22 juin 2017 - 14:21:52
Document(s) archivé(s) le : vendredi 23 novembre 2012 - 15:10:49

Fichier

TH2011PEST1023_complete.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : pastel-00674619, version 1

Citation

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

Partager

Métriques

Consultations de
la notice

695

Téléchargements du document

806