Research ArticleNo Access

Hopf algebras on planar trees and permutations

Diego Arcis

Facultad de Ciencias de la Salud, Universidad Autónoma de Chile – Sede Talca, 5 Poniente 1670 – 3460000 Talca, Chile

E-mail Address: diego.arcis@uautonoma.cl

Corresponding author.

Search for more papers by this author

and

Sebastián Márquez

Facultad de Ingeniería, Universidad Autónoma de Chile – Sede Talca, 4 Norte 99 – 3460000 Talca, Chile

E-mail Address: sebastian.marquez@uautonoma.cl

Search for more papers by this author

https://doi.org/10.1142/S0219498822502243Cited by:2 (Source: Crossref)

Abstract

We endow the space of rooted planar trees with the structure of a Hopf algebra. We prove that variations of such a structure lead to Hopf algebras on the spaces of labeled trees, $n$ -trees, increasing planar trees and sorted trees. These structures are used to construct Hopf algebras on different types of permutations. In particular, we obtain new characterizations of the Hopf algebras of Malvenuto–Reutenauer and Loday–Ronco via planar rooted trees.

Communicated by J. Gómez-Torrecillas

Keywords:

AMSC: 16T05, 16T10, 16T30, 05C05

References

1. E. Abe , Hopf Algebras, Cambridge Tracts in Mathematics, Vol. 74 (Cambridge University Press, Cambridge, 2004). Google Scholar
2. M. Aguiar and F. Sottile , Structure of the Malvenuto–Reutenauer Hopf algebra of permutations, Adv. Math. 191(2) (2002) 225–275. Crossref, Web of Science, Google Scholar
3. M. Aguiar and F. Sottile , Structure of the Loday–Ronco Hopf algebra of trees, J. Algebra 295(2) (2004) 473–511. 1 2004. Crossref, Web of Science, Google Scholar
4. M. Aguiar and F. Sottile , Cocommutative Hopf algebras of permutations and trees, J. Algebra Comb. 22 (2005) 451–470. Crossref, Web of Science, Google Scholar
5. P. Brass , Advanced Data Structures (Cambridge University Press, Cambridge, 2008). Crossref, Google Scholar
6. A. Connes and D. Kreimer , Hopf algebras, renormalization and noncommutative geometry, Commun. Math. Phys. 199(1) (1998) 203–242. Crossref, Web of Science, Google Scholar
7. T. Cormen, C. Leiserson, R. Rivest and C. Stein , Introduction to Algorithms, 3rd edn. (Massachusetts Institute of Technology, Cambridge, Massachusetts, 2009). Google Scholar
8. L. Foissy , Les algèbres de Hopf des arbres enracinés décorés, I, B. Sci. Math. 126(3) (2002) 193–239. Crossref, Google Scholar
9. L. Foissy , The infinitesimal Hopf algebra and the poset of planar forests, J. Algebr. Comb. 30(3) (2009) 277–309. Crossref, Web of Science, Google Scholar
10. L. Foissy and J. Fromentin , A divisibility result in combinatorics of generalized braids, J. Comb. Theory A 152 (2017) 190–224. Crossref, Web of Science, Google Scholar
11. I. Gessel and R. Stanley , Stirling polynomials, J. Comb. Theory A 24(1) (1978) 24–33. Crossref, Web of Science, Google Scholar
12. R. Grossman and R. Larson , Hopf-algebraic structure of families of trees, J. Algebra 126(1) (1989) 184–210. Crossref, Web of Science, Google Scholar
13. R. Grossman and R. Larson , Hopf algebras of heap ordered trees and permutations, Commun. Algebra 37(2) (2009) 453–459. Crossref, Web of Science, Google Scholar
14. R. Hotlkamp , Comparison of Hopf algebras on trees, Arch. Math. 80(4) (2003) 368–383. Crossref, Web of Science, Google Scholar
15. S. Janson , Plane recursive trees, Stirling permutations and an urn model, in Proc. 5th Colloq. Mathematics and Computer Science, Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings, Vol. AI, Blaubeuren, 2008, pp. 541–548. Crossref, Google Scholar
16. A. Lentin , Équations dans les Monoïdes Libres, 1st edn., Mathématiques et Sciences de l’Homme, Vol. 16 (Mouton, Paris, 1972). Crossref, Google Scholar
17. J.-L. Loday , Scindement d’associativité et algèbres de Hopf, in Actes du Colloque en l’honneur de Jean Leray (Nantes, 2004), pp. 155–172. Google Scholar
18. J.-L. Loday and M. Ronco , Hopf algebra of planar binary trees, Adv. Math. 139(2) (1998) 293–309. Crossref, Web of Science, Google Scholar
19. J.-L. Loday and M. Ronco , On the structure of cofree Hopf algebras, J. Reine Angew. Math. 2006(592) (2006) 1435–5345. Crossref, Google Scholar
20. C. Malvenuto and C. Reutenauer , Duality between quasi-symmetrical functions and the Solomon descent algebra, J. Algebra 177(3) (1995) 967–982. Crossref, Web of Science, Google Scholar
21. S. Márquez , Compatible associative bialgebras, Commun. Algebra 46(9) (2018) 3810–3832. Crossref, Web of Science, Google Scholar
22. J. Novelli and J. Thibon , Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, Discrete Math. 310(24) (2010) 3584–3606. Crossref, Web of Science, Google Scholar
23. R. Stanley , Enumerative Combinatorics, Cambridge Studies in Advanced Mathematics, Vol. 1 (Cambridge University Press, Cambridge, 1997). Crossref, Google Scholar