Thèse

Titre. 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.

Mots clés : combinatoire ; algorithmique ; arbre ; algèbre de Hopf ; opérade ; fonction quasi-symétrique libre ; treillis de Tamari ; correspondance de Robinson-Schensted ; réalisation polynomiale.

Composition du jury : Le diaporama de la soutenance se trouve ici.

Le manuscrit de la thèse se trouve ici.

La soutenance a eu lieu le 8 décembre 2011 à l'université Paris-Est Marne-la-Vallée.