The monomial basis and the $Q$-basis of the Hopf algebra of parking functions.

Li, Teresa Xueshan

Journal of Algebraic Combinatorics, Tome 42 (2015) no. 2, pp. 473-496.

Résumé

Consider the vector space $\mathbb {K}\mathcal{P}$ spanned by parking functions. By representing parking functions as labeled digraphs, Hivert, Novelli and Thibon constructed a cocommutative Hopf algebra $\mathrm{PQSym}^{*}$ on $\mathbb {K}\mathcal{P}$. The product and coproduct of $\mathrm{PQSym}^{*}$ are analogous to the product and coproduct of the Hopf algebra NCSym of symmetric functions in noncommuting variables defined in terms of the power sum basis. In this paper, we view a parking function as a word. We shall construct a Hopf algebra PFSym on $\mathbb {K}\mathcal{P}$ with a formal basis $\{M_a\}$ analogous to the monomial basis of NCSym. By introducing a partial order on parking functions, we transform the basis $\{M_a\}$ to another basis $\{Q_a\}$ via the Möbius inversion. We prove the freeness of PFSym by finding two free generating sets in terms of the $M$-basis and the $Q$-basis, and we show that PFSym is isomorphic to the Hopf algebra $\mathrm{PQSym}^{*}$. It turns out that our construction, when restricted to permutations and nonincreasing parking functions, leads to a new way to approach the Grossman-Larson Hopf algebras of ordered trees and heap-ordered trees.

Détail

Classification : 16T30, 16T05, 05E05
Keywords: Hopf algebras, parking functions, partitions, noncommutative symmetric functions