Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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.
N. Bergeron, C. Reutenauer, M. Rosas, and M. Zabrocki, “Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables,” Preprint arXiv:math.RA/0502082.
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.
C. Brouder and A. Frabetti, “QED Hopf algebras on planar binary trees,” J. Alg. 267(1) (2003), 298–322.
F. Chapoton, “Algébres de Hopf des permutahédres, associahédres et hypercubes,” Adv. Math. 150(2), (2000), 264–275.
A. Connes and D. Kreimer, “Hopf algebras, renormalization and noncommutative geometry,” Commun. Math. Phys. 199(1) (1998), 203–242.
H. Figueroa and J. Gracia-Bondia, “Combinatorial Hopf algebras in quantum field theory I,” Preprint arXiv:hep-th/0408145.
A. Joyal, “Foncteurs analytiques et espéces de structures,” in Combinatoire énumérative, Proc. Colloq., Montréal, Canada, 1985. Lecture Notes in Mathematics 1234, Springer, Berlin, 1986, pp. 126–159.
J.-L. Loday, “Dialgebras,” in: Dialgebras and Related Operads,” Lecture Notes in Mathematics 1736, Springer, Berlin, 2001, pp. 7–66.
J.-L. Loday and M.O. Ronco, “Hopf algebra of the planar binary trees,” Adv. Math. 139(2) (1998), 293–309.
J.W. Milnor and J.C. Moore, “On the structure of Hopf algebras,” Ann. of Math. 81(2) (1965), 211–264.
J.-C. Novelli and J.-Y. Thibon, “Polynomial realizations of some trialgebras,” Preprint arXiv:math.CO/0605061.
F. Patras, “La décomposition en poids des algébres de Hopf,” Ann. Inst. Fourier (Grenoble) 43(4) (1993), 1067–1087.
F. Patras, “L’algébre des descentes d’une bigébre graduée,” J. Alg. 170(2) (1994), 547–566.
F. Patras and C. Reutenauer, “On descent algebras and twisted bialgebras,” Moscow Math. J. 4(1) (2004), 199–216.
F. Patras and M. Schocker, “Twisted descent algebras and the Solomon–Tits algebra,” Adv. in Math. 199(1) (2006), 151–184.
D. Rawlings, “The ABC’s of classical enumeration,” Ann. Sci. Math. Québec. 10(2) (1986), 207–235.
M. Schocker, “The module structure of the Solomon-Tits algebra of the symmetric group,” J. Alg. 301(2) (2006), 554–586.
R. Stanley, Enumerative combinatorics, Volume I, The Wadsworth and Brooks/Cole Mathematics Series. Monterey, California, 1986.
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.
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.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Patras, F., Schocker, M. Trees, set compositions and the twisted descent algebra. J Algebr Comb 28, 3–23 (2008). https://doi.org/10.1007/s10801-006-0028-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-006-0028-1