Hopf algebras and dendriform structures arising from parking functions.

*(English)*Zbl 1127.16033This paper introduces and studies the Hopf algebra PQSym of parking quasi-symmetric functions (which we shall define) as an extension of FQSym, the Hopf algebra of free quasi-symmetric functions introduced by G. Duchamp, F. Hivert and J.-Y. Thibon [Int. J. Algebra Comput. 12, No. 5, 671-717 (2002; Zbl 1027.05107)], which we shall recall. Also studied are certain subalgebras of PQSym and some quotients of them.

For words on the alphabet of positive integers, the shifted shuffle of two words \(u\) and \(v\) is the shuffle of \(u\) and \(v(k)\), where \(k\) is the length of \(u\), and \(v(k)\) is obtained from \(v\) by increasing each of its letters by \(k\), FQSym has a basis \(\{G_s\mid s\) a (finite) permutation}, where \(G_s\) is the sum of all words whose standardization is \(s\). Everything is over a field of characteristic zero. For \(F_s=-G_{s^{-1}}\), the product \(F_sF_t\) is the sum of all \(F_u\), \(u\) a term in the shifted shuffle product of \(s\) and \(t\). The coproduct of \(F_s\) is the sum of all \(F_{\text{Std}(t)}\otimes F_{\text{Std}(u)}\) over all \(t\) and \(u\) with \(s=tu\) (concatenation). Permutations are examples of parking functions. A parking function of length \(n\) is a word \(a=a_1a_2\dots a_n\), where each \(a_i\) is in \(\{1,2,\dots,n\}\), whose non-decreasing rearrangement \(a'= (a_1)'(a_2)' \dots(a_n)'\) satisfies \((a_i)'\) less than or equal to \(i\) for all \(i\).

PQSym has a basis of symbols \(F_a\), \(a\) a parking function. The multiplication is an extension of that of FQSym, i.e., \(F_aF_b\) is the sum of all \(F_c\), where \(c\) is a term in the shifted shuffle product of \(a\) and \(b\). To define the coproduct in PQSym, an algorithm is given which when applied to a word \(w\) produces a parking function \(\text{Park}(w)\) of the same length as \(w\). Then the coproduct of \(F_a\) is the sum of all \(F_{\text{Park}(u)}\otimes F_{\text{Park}(v)}\), where \(a=uv\). When \(w\) is a permutation, \(\text{Park}(w)\) coincides with \(\text{Std}(w)\), so that the coproduct in PQSym extends that of FQSym. Thus FQSym is a Hopf subalgebra of PQSym (there is also a description of the antipode in PQSym which involves the parking algorithm).

For the graded dual Hopf algebra PQSym*, dualizing the product and copoduct on PQSym gives the coproduct and product on the basis dual to the \(F_a\). It is shown that PQSym is a bidendriform dialgebra as defined by J.-L. Loday [Lect Notes Math. 1763, 7-66 (2001; Zbl 0999.17002)], in fact a bidendriform bialgebra. By results of L. Foissy [J. Pure Appl. Algebra 209, No. 2, 439-459 (2007; Zbl 1123.16030)], it follows that PQSym is a self-dual Hopf algebra whose primitive elements form a free Lie algebra. As a dendriform dialgebra, it is free on its totally primitive elements. A realization of PQSym is given in terms of certain \((0,1)\)-matrices. PQSym* is a dendriform trialgebra, as defined by J.-L. Loday and M. Ronco [Contemp. Math. 346, 369-398 (2004; Zbl 1065.18007)], and it is conjectured that PQSym* is free as a dendriform trialgebra.

Three subalgebras of PQSym are presented, with names SQSym, SCQSym and CQSym. SQSym has its Hilbert series given by little SchrĂ¶der numbers, and is isomorphic to the free dendriform trialgebra on one generator. CQSym has its Hilbert series given by Catalan numbers and is cocommutative. SCQSym is a Hopf quotient of SQSym, whose Hilbert series is given by powers of 3. Duals of these subalgebras are also studied.

For words on the alphabet of positive integers, the shifted shuffle of two words \(u\) and \(v\) is the shuffle of \(u\) and \(v(k)\), where \(k\) is the length of \(u\), and \(v(k)\) is obtained from \(v\) by increasing each of its letters by \(k\), FQSym has a basis \(\{G_s\mid s\) a (finite) permutation}, where \(G_s\) is the sum of all words whose standardization is \(s\). Everything is over a field of characteristic zero. For \(F_s=-G_{s^{-1}}\), the product \(F_sF_t\) is the sum of all \(F_u\), \(u\) a term in the shifted shuffle product of \(s\) and \(t\). The coproduct of \(F_s\) is the sum of all \(F_{\text{Std}(t)}\otimes F_{\text{Std}(u)}\) over all \(t\) and \(u\) with \(s=tu\) (concatenation). Permutations are examples of parking functions. A parking function of length \(n\) is a word \(a=a_1a_2\dots a_n\), where each \(a_i\) is in \(\{1,2,\dots,n\}\), whose non-decreasing rearrangement \(a'= (a_1)'(a_2)' \dots(a_n)'\) satisfies \((a_i)'\) less than or equal to \(i\) for all \(i\).

PQSym has a basis of symbols \(F_a\), \(a\) a parking function. The multiplication is an extension of that of FQSym, i.e., \(F_aF_b\) is the sum of all \(F_c\), where \(c\) is a term in the shifted shuffle product of \(a\) and \(b\). To define the coproduct in PQSym, an algorithm is given which when applied to a word \(w\) produces a parking function \(\text{Park}(w)\) of the same length as \(w\). Then the coproduct of \(F_a\) is the sum of all \(F_{\text{Park}(u)}\otimes F_{\text{Park}(v)}\), where \(a=uv\). When \(w\) is a permutation, \(\text{Park}(w)\) coincides with \(\text{Std}(w)\), so that the coproduct in PQSym extends that of FQSym. Thus FQSym is a Hopf subalgebra of PQSym (there is also a description of the antipode in PQSym which involves the parking algorithm).

For the graded dual Hopf algebra PQSym*, dualizing the product and copoduct on PQSym gives the coproduct and product on the basis dual to the \(F_a\). It is shown that PQSym is a bidendriform dialgebra as defined by J.-L. Loday [Lect Notes Math. 1763, 7-66 (2001; Zbl 0999.17002)], in fact a bidendriform bialgebra. By results of L. Foissy [J. Pure Appl. Algebra 209, No. 2, 439-459 (2007; Zbl 1123.16030)], it follows that PQSym is a self-dual Hopf algebra whose primitive elements form a free Lie algebra. As a dendriform dialgebra, it is free on its totally primitive elements. A realization of PQSym is given in terms of certain \((0,1)\)-matrices. PQSym* is a dendriform trialgebra, as defined by J.-L. Loday and M. Ronco [Contemp. Math. 346, 369-398 (2004; Zbl 1065.18007)], and it is conjectured that PQSym* is free as a dendriform trialgebra.

Three subalgebras of PQSym are presented, with names SQSym, SCQSym and CQSym. SQSym has its Hilbert series given by little SchrĂ¶der numbers, and is isomorphic to the free dendriform trialgebra on one generator. CQSym has its Hilbert series given by Catalan numbers and is cocommutative. SCQSym is a Hopf quotient of SQSym, whose Hilbert series is given by powers of 3. Duals of these subalgebras are also studied.

Reviewer: Earl J. Taft (New Brunswick)

##### MSC:

16W30 | Hopf algebras (associative rings and algebras) (MSC2000) |

05E05 | Symmetric functions and generalizations |