Preordered forests, packed words and contraction algebras. (English. French summary) Zbl 1298.05326
Summary: We introduce the notions of preordered and heap-preordered forests, generalizing the construction of ordered and heap-ordered forests. We prove that the algebras of preordered and heap-preordered forests are Hopf for the cut coproduct, and we construct a Hopf morphism to the Hopf algebra of packed words. Moreover, we define another coproduct on the preordered forests given by the contraction of edges. Finally, we give a combinatorial description of morphism defined on Hopf algebras of forests with values in the Hopf algebras of shuffles or quasi-shuffles.
MSC:
| 05E15 | Combinatorial aspects of groups and algebras (MSC2010) |
| 16T05 | Hopf algebras and their applications |
| 05C05 | Trees |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
Keywords:
algebraic combinatorics; planar rooted trees; Hopf algebra of ordered forests; quasi-shuffle algebraSoftware:
OEISOnline Encyclopedia of Integer Sequences:
Total number of leaves in all rooted ordered trees with n edges.Number of different forests of rooted trees, without isolated vertices, on n labeled nodes.
Number of forests of rooted trees containing n nodes not counting the root nodes.
Triangle read by rows, T(n, k) = Sum_{m=0..k} (-1)^(m + k)*binomial(n + k, n + m) * |Stirling1(n + m, m)|, for n >= 0, 0 <= k <= n.
Related to the number of Hopf subalgebras of heap-preordered forests of vertex degree n.
References:
| [1] | Calaque, D.; Ebrahimi-Fard, K.; Manchon, D., Two interacting Hopf algebras of trees, Adv. in Appl. Math., 47, 282-308 (2011) · Zbl 1235.16032 |
| [2] | Connes, A.; Kreimer, D., Hopf algebras, renormalization and noncommutative geometry, Comm. Math. Phys., 199, 203-242 (1998) · Zbl 0932.16038 |
| [3] | Connes, A.; Kreimer, D., Renormalization in quantum field theory and the Riemann-Hilbert problem I. The Hopf algebra of graphs and the main theorem, Comm. Math. Phys., 210, 249-273 (2000) · Zbl 1032.81026 |
| [4] | Connes, A.; Kreimer, D., Renormalization in quantum field theory and the Riemann-Hilbert problem II. \(β\)-Function, diffeomorphisms and the renormalization group, Comm. Math. Phys., 216, 215-241 (2001) · Zbl 1042.81059 |
| [5] | Duchamp, G.; Hivert, F.; Thibon, J.-Y., Noncommutative symmetric functions VI: free quasi-symmetric functions and related algebras, Internat. J. Algebra Comput., 12, 671 (2002) · Zbl 1027.05107 |
| [6] | Ecalle, J.; Vallet, B., The arborification-coarborification transform: analytic, combinatorial, and algebraic aspects, Ann. Fac. Sci. Toulouse, 13, 4, 575-657 (2004) · Zbl 1078.37016 |
| [7] | Foissy, L., Les algèbres de Hopf des arbres enracinés décorés, I, Bull. Sci. Math., 126, 3, 193-239 (2002) · Zbl 1013.16026 |
| [8] | Foissy, L., Les algèbres de Hopf des arbres enracinés décorés, II, Bull. Sci. Math., 126, 4, 249-288 (2002) · Zbl 1013.16027 |
| [9] | Foissy, L., Ordered forests and parking functions, Int. Math. Res. Not. IMRN, 2011 (2012) · Zbl 1242.16031 |
| [10] | Foissy, L., The Hopf algebra of Fliess operators and its dual pre-Lie algebra (2013), preprint |
| [11] | Foissy, L.; Unterberger, J., Ordered forests, permutations and iterated integrals, Int. Math. Res. Not. IMRN, 2013, 4, 846-885 (2013) · Zbl 1331.16026 |
| [12] | Grossman, R. L.; Larson, R. G., Hopf-algebraic structure of combinatorial objects and differential operators, Israel J. Math., 72, 1-2, 109-117 (1990) · Zbl 0780.16029 |
| [13] | Hoffman, M. E., Quasi-shuffle products, J. Algebraic Combin., 11, 49-68 (2000) · Zbl 0959.16021 |
| [14] | Holtkamp, R., Comparison of Hopf algebras on trees, Arch. Math. (Basel), 80, 4, 368-383 (2003) · Zbl 1056.16030 |
| [15] | Loday, J. L.; Ronco, M., On the structure of cofree Hopf algebra, J. Reine Angew. Math., 592, 123-155 (2006) · Zbl 1096.16019 |
| [16] | Loday, J. L.; Ronco, M., Combinatorial Hopf algebras, (Quanta of Maths. Quanta of Maths, Clay Math. Proc., vol. 11 (2010), Amer. Math. Soc.), 347-383 · Zbl 1217.16033 |
| [17] | Loday, J. L.; Vallette, B., Algebraic Operads (2012), Springer · Zbl 1260.18001 |
| [18] | Moerdijk, I., On the Connes-Kreimer construction of Hopf algebras, Contemp. Math., 271, 311-321 (2001) · Zbl 0987.16032 |
| [19] | Malvenuto, C.; Reutenauer, C., Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, 177, 3, 967-982 (1995) · Zbl 0838.05100 |
| [20] | Manchon, D.; Saïdi, A., Lois pré-Lie en interaction, Comm. Algebra, 39, 3662-3680 (2011) · Zbl 1262.16036 |
| [21] | Novelli, J.-C.; Thibon, J.-Y., Polynomial realizations of some trialgebras |
| [22] | Reutenauer, C., Free Lie Algebras (1993), The Clarendon Press · Zbl 0798.17001 |
| [23] | Sloane, N. J.A., On-line encyclopedia of integer sequences · Zbl 1044.11108 |
| [24] | Stanley, R. P., Enumerative Combinatorics. Vol. 1 (2002), Cambridge University Press · Zbl 1247.05003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
