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

DOI:
https://doi.org/10.1090/S0002-9947-03-03317-8

Published electronically:
May 15, 2003

MathSciNet review:
1990174

Full-text PDF

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.

**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.``att.com/~njas/sequences/.`**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**

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

Email:
meh@usna.edu

DOI:
https://doi.org/10.1090/S0002-9947-03-03317-8

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