Combinatorics of rooted trees and Hopf algebras
HTML articles powered by AMS MathViewer
- by Michael E. Hoffman PDF
- Trans. Amer. Math. Soc. 355 (2003), 3795-3811 Request permission
Abstract:
We begin by considering the graded vector space with a basis consisting of rooted trees, with grading given by the count of non-root vertices. We define two linear operators on this vector space, the growth and pruning operators, which respectively raise and lower grading; their commutator is the operator that multiplies a rooted tree by its number of vertices, and each operator naturally associates a multiplicity to each pair of rooted trees. By using symmetry groups of trees we define an inner product with respect to which the growth and pruning operators are adjoint, and obtain several results about the associated multiplicities.
Now the symmetric algebra on the vector space of rooted trees (after a degree shift) can be endowed with a coproduct to make a Hopf algebra; this was defined by Kreimer in connection with renormalization. We extend the growth and pruning operators, as well as the inner product mentioned above, to Kreimer’s Hopf algebra. On the other hand, the vector space of rooted trees itself can be given a noncommutative multiplication: with an appropriate coproduct, this leads to the Hopf algebra of Grossman and Larson. We show that the inner product on rooted trees leads to an isomorphism of the Grossman-Larson Hopf algebra with the graded dual of Kreimer’s Hopf algebra, correcting an earlier result of Panaite.
References
- D. J. Broadhurst and D. Kreimer, Renormalization automated by Hopf algebra, J. Symbolic Comput. 27 (1999), no. 6, 581–600. MR 1701096, DOI 10.1006/jsco.1999.0283
- C. Brouder, Runge-Kutta methods and renormalization, European Phys. J. C 12 (2000), 521-534.
- Alain Connes and Dirk Kreimer, Hopf algebras, renormalization and noncommutative geometry, Comm. Math. Phys. 199 (1998), no. 1, 203–242. MR 1660199, DOI 10.1007/s002200050499
- A. Connes and H. Moscovici, Hopf algebras, cyclic cohomology and the transverse index theorem, Comm. Math. Phys. 198 (1998), no. 1, 199–246. MR 1657389, DOI 10.1007/s002200050477
- L. Foissy, Finite-dimensional comodules over the Hopf algebra of rooted trees, J. Algebra 255 (2002), 89-120.
- S. V. Fomin, The generalized Robinson-Schensted-Knuth correspondence, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 155 (1986), no. Differentsial′naya Geometriya, Gruppy Li i Mekh. VIII, 156–175, 195 (Russian); English transl., J. Soviet Math. 41 (1988), no. 2, 979–991. MR 869582, DOI 10.1007/BF01247093
- Sergey Fomin, Duality of graded graphs, J. Algebraic Combin. 3 (1994), no. 4, 357–404. MR 1293822, DOI 10.1023/A:1022412010826
- Sergey Fomin, Schensted algorithms for dual graded graphs, J. Algebraic Combin. 4 (1995), no. 1, 5–45. MR 1314558, DOI 10.1023/A:1022404807578
- José M. Gracia-Bondía, Joseph C. Várilly, and Héctor Figueroa, Elements of noncommutative geometry, Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser Boston, Inc., Boston, MA, 2001. MR 1789831, DOI 10.1007/978-1-4612-0005-5
- Robert Grossman and Richard G. Larson, Hopf-algebraic structure of families of trees, J. Algebra 126 (1989), no. 1, 184–210. MR 1023294, DOI 10.1016/0021-8693(89)90328-1
- Michael E. Hoffman, An analogue of covering space theory for ranked posets, Electron. J. Combin. 8 (2001), no. 1, Research Paper 32, 12. MR 1877651
- Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR 0445948
- Dirk Kreimer, On the Hopf algebra structure of perturbative quantum field theories, Adv. Theor. Math. Phys. 2 (1998), no. 2, 303–334. MR 1633004, DOI 10.4310/ATMP.1998.v2.n2.a4
- Dirk Kreimer, On overlapping divergences, Comm. Math. Phys. 204 (1999), no. 3, 669–689. MR 1707611, DOI 10.1007/s002200050661
- D. Kreimer, Chen’s iterated integral represents the operator product expansion, Adv. Theor. Math. Phys. 3 (1999), no. 3, 627–670. MR 1797019, DOI 10.4310/ATMP.1999.v3.n3.a7
- Dirk Kreimer, Knots and Feynman diagrams, Cambridge Lecture Notes in Physics, vol. 13, Cambridge University Press, Cambridge, 2000. MR 1778151, DOI 10.1017/CBO9780511564024
- John W. Milnor and John C. Moore, On the structure of Hopf algebras, Ann. of Math. (2) 81 (1965), 211–264. MR 174052, DOI 10.2307/1970615
- Florin Panaite, Relating the Connes-Kreimer and Grossman-Larson Hopf algebras built on rooted trees, Lett. Math. Phys. 51 (2000), no. 3, 211–219. MR 1775423, DOI 10.1023/A:1007600216187
- N. J. A. Sloane, Online Encyclopedia of Integer Sequences, Sequence A000081, https://www.research.att.com/~njas/sequences/.
- Richard P. Stanley, Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, Providence, R.I., 1972. MR 0332509
- Richard P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), no. 4, 919–961. MR 941434, DOI 10.1090/S0894-0347-1988-0941434-9
- Richard P. Stanley, Variations on differential posets, Invariant theory and tableaux (Minneapolis, MN, 1988) IMA Vol. Math. Appl., vol. 19, Springer, New York, 1990, pp. 145–165. MR 1035494
Additional Information
- Michael E. Hoffman
- Affiliation: Department of Mathematics, United States Naval Academy, Annapolis, Maryland 21402
- ORCID: 0000-0002-9436-7596
- Email: meh@usna.edu
- Received by editor(s): June 25, 2002
- Received by editor(s) in revised form: February 24, 2003
- Published electronically: May 15, 2003
- Additional Notes: The author was partially supported by a grant from the Naval Academy Research Council
Some of the results of this paper were presented to an AMS Special Session on Combinatorial Hopf Algebras on May 4, 2002. - © Copyright 2003 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 355 (2003), 3795-3811
- MSC (2000): Primary 05C05, 16W30; Secondary 81T15
- DOI: https://doi.org/10.1090/S0002-9947-03-03317-8
- MathSciNet review: 1990174