JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 28, No 1 (2008)

Florent Hivert , Jean-Christophe Novelli and Jean-Yves Thibon

Université Paris-Est Laboratoire d'Informatique de l'Institut Gaspard Monge UMR CNRS 7136 5 Boulevard Descartes Champs-sur-Marne 77454 Marne-la-Vallée cedex 2 France

We propose several constructions of commutative or cocommutative Hopf algebras based on various combinatorial structures and investigate the relations between them. A commutative Hopf algebra of permutations is obtained by a general construction based on graphs, and its noncommutative dual is realized in three different ways, in particular, as the Grossman-Larson algebra of heap-ordered trees. Extensions to endofunctions, parking functions, set compositions, set partitions, planar binary trees, and rooted forests are discussed. Finally, we introduce one-parameter families interpolating between different structures constructed on the same combinatorial objects.

1. Aguiar, M., & Sottile, F. (2005). Cocommutative Hopf algebras of permutations and trees. Journal of Algebraic Combinatorics, 22(4), 451-470.
2. Bergeron, F., Labelle, G., & Leroux, P. (1998). Combinatorial species and tree-like structures. Encyclopedia of mathematics and its applications, Vol.
67. Cambridge: Cambridge University Press.
3. Bergeron, N., Reutenauer, C., Rosas, M., & Zabrocki, M. (2005). Invariants and coinvariants of the symmetric group in noncommuting variables. Preprint .
4. Brouder, C., & Frabetti, A. (2001). Renormalization of QED with planar binary trees. European Journal of Physics C, 19, 715-741.
5. Brouder, C., & Oeckl, R. (2004). Quantum groups and quantum field theory: I. The free scalar field. In Mathematical physics research on the leading edge (pp. 63-90). Hauppauge: Nova Sci. Publ.
6. Connes, A., & Kreimer, D. (1998). Hopf algebras, renormalization and noncommutative geometry. Communications in Mathematical Physics, 199, 203-242.
7. Duchamp, G., Hivert, F., & Thibon, J.-Y. (2002). Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras. International Journal of Algebra and Computation, 12, 671-717.
8. Gelfand, I. M., Krob, D., Lascoux, A., Leclerc, B., Retakh, V. S., & Thibon, J.-Y. (1995). Noncommutative symmetric functions. Advances in Mathematics, 112, 218-348.
9. Grossman, R., & Larson, R. G. (1989). Hopf-algebraic structure of families of trees. J. Algebra, 126(1), 184-210.
10. Hivert, F. (2000). Hecke algebras, difference operators, and quasi-symmetric functions. Advances in Mathematics, 155, 181-238.
11. Hivert, F., Novelli, J.-C., & Thibon, J.-Y. (2005). The algebra of binary search trees. Theoretical Computer Science, 339, 129-165.
12. Hivert, F., Novelli, J.-C., & Thibon, J.-Y. (2005). Commutative Hopf algebras of permutations and trees. Preprint
13. Joyal, A. (1981). Une théorie combinatoire des séries formelles. Advances in Mathematics, 42, 1-82.
14. Krob, D., & Thibon, J.-Y. (1997). Noncommutative symmetric functions IV: Quantum linear groups and Hecke algebras at q =
0. Journal of Algebraic Combinatorics, 6, 339-376.
15. Leclerc, B., Scharf, T., & Thibon, J.-Y. (1996). Noncommutative cyclic characters of symmetric groups. Journal of Combinatorial Theory Series A, 75, 55-69.
16. Li, L., & Zhang, P. (2000). Twisted Hopf algebras, Ringel-Hall algebras, and Green's categories. Journal of Algebra, 231, 713-743.
17. Loday, J.-L., & Ronco, M. O. (1998). Hopf algebra of the planar binary trees. Advances in Mathematics, 139(2), 293-309.
18. Macdonald, I. G. (1995). Symmetric functions and Hall polynomials (2nd ed). Oxford: Oxford University Press.
19. Malvenuto, C., & Reutenauer, C. (1995). Duality between quasi-symmetric functions and the Solomon descent algebra. Journal of Algebra, 177, 967-982.
20. Novelli, J.-C., & Thibon, J.-Y. (2006). Construction de trigèbres dendriformes. Comptes Rendus. Académie des Sciences Paris Série I, 342, 365-369.
21. Novelli, J.-C., & Thibon, J.-Y. (2007). Hopf algebras and dendriform structures arising from parking functions. Fundamenta Mathematicae, 193, 189-241.
22. Novelli, J.-C., & Thibon, J.-Y. (2007). Parking functions and descent algebras. Annals of Combinatorics, 11, 59-68.
23. Novelli, J.-C., Thibon, J.-Y., & Thiéry, N. M. (2004). Algèbres de Hopf de graphes. Comptes Rendus. Académie des Sciences Paris Série A, 339(9), 607-610.
24. Novelli, J.-C., & Thibon, J.-Y. (2005). Noncommutative symmetric functions and Lagrange inversion. Preprint
25. Patras, F., Reutenauer, C. (2004). On descent algebras and twisted bialgebras. Moscow Mathematical Journal, 4, 199-216.
26. Poirier, S., & Reutenauer, C. (1995). Algèbre de Hopf des tableaux. Annales des Science Mathématiques du Québec, 19, 79-90.
27. Reutenauer, C. (1993). Free Lie algebras, London Mathematical Society Monographs. New York: Oxford University Press.
28. Rey, M. (2007). Algebraic construction on set partitions In Proc. FPSAC'07, Nankai University, July 2007.
29. Sagan, B., & Rosas, M. (2006). Symmetric functions in noncommuting variables. Transactions of the American Mathematical Society, 358, 215-232.
30. Scharf, T., & Thibon, J.-Y. (1994). A Hopf-algebra approach to inner plethysm. Advances in Mathematics, 104, 30-58.
31. Sloane, N. J. A. The on-line encyclopedia of integer sequences. .
32. Thibon, J.-Y., & Ung, B. C. V. (1996). Quantum quasi-symmetric functions and Hecke algebras. Journal of Physics A, 29, 7337-7348.