JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 28, No 1 (2008)

Frédéric Patras¹ and Manfred Schocker²

¹Parc Valrose CNRS, UMR 6621 06108 Nice cedex 2 France
²University of Wales Swansea Department of Mathematics Singleton Park Swansea SA2 8PP UK

We first show that increasing trees are in bijection with set compositions, extending simultaneously a recent result on trees due to Tonks and a classical result on increasing binary trees. We then consider algebraic structures on the linear span of set compositions (the twisted descent algebra). Among others, a number of enveloping algebra structures are introduced and studied in detail. For example, it is shown that the linear span of trees carries an enveloping algebra structure and embeds as such in an enveloping algebra of increasing trees. All our constructions arise naturally from the general theory of twisted Hopf algebras.

1. M.G. Barratt, “Twisted Lie algebras. Geometric applications of homotopy theory,” in Proceedings of the Conference, Evanston
1977. Lecture Notes in Mathematics 658, Springer, Berlin, 1978, pp. 9-15.
2. N. Bergeron, C. Reutenauer, M. Rosas, and M. Zabrocki, “Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables,” Preprint arXiv:math.RA/0502082.
3. N. Bergeron and M. Zabrocki, “The Hopf algebras of symmetric functions and quasisymmetric functions in non-commutative variables are free and cofree,” Preprint arXiv:math.RA/0505137.
4. C. Brouder and A. Frabetti, “QED Hopf algebras on planar binary trees,” J. Alg. 267(1) (2003), 298-322.
5. F. Chapoton, “Alg`ebres de Hopf des permutah`edres, associah`edres et hypercubes,” Adv. Math. 150(2), (2000), 264-275.
6. A. Connes and D. Kreimer, “Hopf algebras, renormalization and noncommutative geometry,” Commun. Math. Phys. 199(1) (1998), 203-242.
7. H. Figueroa and J. Gracia-Bondia, “Combinatorial Hopf algebras in quantum field theory I,” Preprint arXiv:hep-th/0408145.
8. A. Joyal, “Foncteurs analytiques et esp`eces de structures,” in Combinatoire énumérative, Proc. Colloq., Montréal, Canada,
1985. Lecture Notes in Mathematics 1234, Springer, Berlin, 1986, pp. 126-159.
9. J.-L. Loday, “Dialgebras,” in: Dialgebras and Related Operads,” Lecture Notes in Mathematics 1736, Springer, Berlin, 2001, pp. 7-66.
10. J.-L. Loday and M.O. Ronco, “Hopf algebra of the planar binary trees,” Adv. Math. 139(2) (1998), 293-309.
11. J.W. Milnor and J.C. Moore, “On the structure of Hopf algebras,” Ann. of Math. 81(2) (1965), 211-264.
12. J.-C. Novelli and J.-Y. Thibon, “Polynomial realizations of some trialgebras,” Preprint arXiv:math.CO/0605061.
13. F. Patras, “La décomposition en poids des alg`ebres de Hopf,” Ann. Inst. Fourier (Grenoble) 43(4) (1993), 1067-1087.
14. F. Patras, “L'alg`ebre des descentes d'une big`ebre graduée,” J. Alg. 170(2) (1994), 547-566.
15. F. Patras and C. Reutenauer, “On descent algebras and twisted bialgebras,” Moscow Math. J. 4(1) (2004), 199-216. Springer
16. F. Patras and M. Schocker, “Twisted descent algebras and the Solomon-Tits algebra,” Adv. in Math. 199(1) (2006), 151-184.
17. D. Rawlings, “The ABC's of classical enumeration,” Ann. Sci. Math. Québec. 10(2) (1986), 207-235.
18. M. Schocker, “The module structure of the Solomon-Tits algebra of the symmetric group,” J. Alg. 301(2) (2006), 554-586.
19. R. Stanley, Enumerative combinatorics, Volume I, The Wadsworth and Brooks/Cole Mathematics Series. Monterey, California, 1986.
20. C.R. Stover, “The equivalence of certain categories of twisted Lie and Hopf algebras over a commutative ring,” J. Pure Appl. Algebra 86(3) (1993), 289-326.
21. A. Tonks, “Relating the associahedron and the permutohedron,” Operads: Proceedings of Renaissance Conferences (Hartford, CT/Luminy, 1995), 33-36, Contemp. Math., 202, Amer. Math. Soc., Providence, RI, 1997.