Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Combinatorics of rooted trees and Hopf algebras

Author: Michael E. Hoffman
Journal: Trans. Amer. Math. Soc. 355 (2003), 3795-3811
MSC (2000): Primary 05C05, 16W30; Secondary 81T15
Published electronically: May 15, 2003
MathSciNet review: 1990174
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. D. J. Broadhurst and D. Kreimer, Renormalization automated by Hopf algebra, J. Symbolic Comput. 27 (1999), 581-600. MR 2000h:81167
  • 2. C. Brouder, Runge-Kutta methods and renormalization, European Phys. J. C 12 (2000), 521-534.
  • 3. A. Connes and D. Kreimer, Hopf algebras, renormalization, and noncommutative geometry, Comm. Math. Phys. 199 (1998), 203-242. MR 99h:81137
  • 4. A. Connes and H. Moscovici, Hopf algebras, cyclic cohomology and the transverse index theorem, Comm. Math. Phys. 198 (1998), 199-246. MR 99m:58186
  • 5. L. Foissy, Finite-dimensional comodules over the Hopf algebra of rooted trees, J. Algebra 255 (2002), 89-120.
  • 6. S. V. Fomin, The generalized Robinson-Schensted-Knuth correspondence (Russian), Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 155 (1986), Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII, 156-175, 195; translation in J. Soviet Math. 41 (1988), 979-991. MR 88b:06003
  • 7. S. Fomin, Duality of graded graphs, J. Algebraic Combin. 3 (1994), 357-404. MR 95i:05088
  • 8. S. Fomin, Schensted algorithms for dual graded graphs, J. Algebraic Combin. 4 (1995), 5-45. MR 95m:05246
  • 9. J. M. Gracia-Bondía, J. C. Várilly, and H. Figueroa, Elements of Noncommutative Geometry, Birkhäuser, Boston, 2001. MR 2001h:58038
  • 10. R. Grossman and R. G. Larson, Hopf-algebraic structure of families of trees, J. Algebra 126 (1989), 184-210. MR 90j:16022
  • 11. M. E. Hoffman, An analogue of covering space theory for ranked posets, Electron. J. Combin. 8(1) (2001), #R32. MR 2003d:06004
  • 12. D. E. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, Reading, MA, 1998. MR 56:4281
  • 13. D. Kreimer, On the Hopf algebra structure of perturbative quantum field theory, Adv. Theor. Math. Phys. 2 (1998), 303-334. MR 99e:81156
  • 14. D. Kreimer, On overlapping divergences, Comm. Math. Phys. 204 (1999), 669-689. MR 2000f:81128
  • 15. D. Kreimer, Chen's iterated integral represents the operator product expansion, Adv. Theor. Math. Phys. 3 (1999), 627-670. MR 2003b:81128
  • 16. D. Kreimer, Knots and Feynman Diagrams, Cambridge University Press, Cambridge, 2000. MR 2002f:81078
  • 17. J. W. Milnor and J. C. Moore, On the structure of Hopf algebras, Ann. of Math. (2) 81 (1965), 211-261. MR 30:4259
  • 18. F. Panaite, Relating the Connes-Kreimer and Grossman-Larson Hopf algebras built on rooted trees, Lett. Math. Phys. 51 (2000), 211-219. MR 2002a:81177
  • 19. N. J. A. Sloane, Online Encyclopedia of Integer Sequences, Sequence A000081, www.research.
  • 20. R. P. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc. No. 119, American Mathematical Society, Providence, RI, 1972. MR 48:10836
  • 21. R. P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), 919-961. MR 89h:06005
  • 22. R. P. Stanley, Variations on differential posets, Invariant Theory and Tableaux (Minneapolis, MN 1988), IMA Volumes in Mathematics and its Applications 19, Springer-Verlag, New York, 1990, pp. 145-165. MR 91h:06004

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05C05, 16W30, 81T15

Retrieve articles in all journals with MSC (2000): 05C05, 16W30, 81T15

Additional Information

Michael E. Hoffman
Affiliation: Department of Mathematics, United States Naval Academy, Annapolis, Maryland 21402

Keywords: Rooted tree, Hopf algebra, differential poset
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.
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society