L’algèbre de Hopf des couples d’arbres binaires jumeaux

Construction de sous-algèbres de Hopf de FQSym

La construction

Nous rappelons ici la construction formalisée par Hivert et Nzeutchap [HN07] (voir également [DHT02], [Hiv04] et [Nze08]) qui établit un lien entre bons monoïdes et algèbres de Hopf combinatoires, en donnant un moyen de construire des algèbres de Hopf à partir de bons monoïdes. Soit M := A∗/≡ un bon monoïde au sens de la définition 4.1.4 du chapitre 4. Nous noterons ub la classe d’équivalence du mot u pour la relation ≡. L’algèbre de Hopf MFQSym On peut associer à M une algèbre de Hopf combinatoire dont les bases sont indexées par les classes d’équivalences de ≡ composées de permutations. Cette algèbre de Hopf est une sous- § 5.1 — Construction de sous-algèbres de Hopf de FQSym 97 algèbre de Hopf de FQSym, et ses éléments de base Pbσ sont définis par Pbσ := X σ ∈ bσ Fσ. (5.1.1) La base des P est la base fondamentale de MFQSym, l’algèbre de Hopf combinatoire ainsi définie. Afin d’être exhaustif et en but de référence future, énonçons le théorème suivant de [HN07] ainsi que sa démonstration. Théorème 5.1.1. Les éléments Pbσ définis en (5.1.1) engendrent une sous-algèbre de Hopf de FQSym. Démonstration. Montrons que le produit de deux éléments Pbσ et Pbν exprimé dans FQSym peut se réécrire dans la base des P. Nous avons Pbσ · Pbν =   X σ ∈ bσ Fσ   ·   X ν ∈ bν Fν   (5.1.2) = X σ ∈ bσ ν ∈ bν Fσ · Fν (5.1.3) = X σ ∈ bσ ν ∈ bν X π ∈ σ✂ν Fπ. (5.1.4) Soit π une permutation et supposons que l’élément Fπ apparaît dans (5.1.4). Pour réécrire cette expression dans la base des P, il est nécessaire que pour toute permutation π ′ ≡ π, l’élément Fπ′ y apparaisse également. Soit (σ, ν) l’unique couple de permutations tel que π ∈ σ ✂ ν. Notons n la taille de σ et m la taille de ν. Comme ≡ est compatible aux restrictions aux intervalles d’alphabet, σ = π|[1,n] ≡ π ′ |[1,n] =: σ ′ , (5.1.5) et π|[n+1,n+m] ≡ π ′ |[n+1,n+m] . (5.1.6) De plus, comme ≡ est compatible avec la déstandardisation, ν = std 

Quelques propriétés générales des sous-algèbres de Hopf de FQSym

Dans ce paragraphe, ≡ désigne une relation d’équivalence sur A∗ qui est également une congruence de monoïde et compatible avec la déstandardisation et aux restrictions aux intervalles d’alphabet. Soit M := A∗/≡ le bon monoïde associé à ≡ et MFQSym la sous-algèbre de Hopf de FQSym associée à M obtenue selon la construction décrite dans le paragraphe 5.1.1. 102 Chapitre 5 — L’algèbre de Hopf des couples d’arbres binaires jumeaux 

Produits et intervalles

Rappelons que dans le cas où ≡ est une congruence du permutoèdre, la structure Sn/≡ est pour tout n > 0 un treillis, et à plus forte raison, un poset. Cette construction est détaillée dans le paragraphe 4.4.1 du chapitre 4. Nous notons 6 la relation d’ordre partiel ainsi obtenue sur les classes de permutations de taille n pour la relation ≡. Lorsque ≡ est une congruence du permutoèdre, il se passe un phénomène particulier au niveau du produit de MFQSym. En effet, les éléments de la base des P qui apparaissent dans un produit de deux éléments de la base des P de MFQSym forment un intervalle du treillis quotient Sn/≡. Avant de montrer cette propriété, nous avons besoin du lemme suivant. Lemme 5.2.1. Soient σ (1) , σ (2) , ν (1) et ν (2) des permutations qui vérifient σ (1) 6P σ (2) et ν (1) 6P ν (2). Nous avons alors dans FQSym,   X σ(1) 6P σ 6P σ(2) Fσ   ·   X ν(1) 6P ν 6P ν(2) Fν   = X σ(1)  ν(1) 6P π 6P σ(2)  ν(2) Fπ. (5.2.1) Démonstration. Il est tout d’abord clair que tout élément Fπ qui apparaît dans le membre droit de (5.2.1) possède une multiplicité de 1. De plus, on déduit directement à partir de la définition du produit de mélange décalé sur les permutations qu’il en est de même pour le membre gauche de (5.2.1). Supposons maintenant qu’un élément Fπ apparaît dans le membre gauche de (5.2.1). Il existe alors un unique couple (σ, ν) de permutations tel que π ∈ σ ✂ ν, σ (1) 6P σ 6P σ (2) et ν (1) 6P ν 6P ν (2). Par définition du produit de mélange décalé, on a σ  ν 6P π 6P σ  ν. Ceci implique σ (1)  ν (1) 6P π 6P σ (2)  ν (2), et par conséquent, Fπ apparaît dans le membre droit de (5.2.1). Supposons qu’un élément Fπ apparaît dans le membre droit de (5.2.1). Nous avons alors σ (1)  ν (1) 6P π 6P σ (2)  ν (2). Posons n := |σ (1)| = |σ (2)|, m := |ν (1)| = |ν (2)|, σ := π|[1,n] et ν := std.