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.

**1.**D. J. Broadhurst and D. Kreimer,*Renormalization automated by Hopf algebra*, J. Symbolic Comput.**27**(1999), no. 6, 581–600. MR**1701096**, 10.1006/jsco.1999.0283**2.**C. Brouder, Runge-Kutta methods and renormalization,*European Phys. J. C***12**(2000), 521-534.**3.**Alain Connes and Dirk Kreimer,*Hopf algebras, renormalization and noncommutative geometry*, Comm. Math. Phys.**199**(1998), no. 1, 203–242. MR**1660199**, 10.1007/s002200050499**4.**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**, 10.1007/s002200050477**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*, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)**155**(1986), no. Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII, 156–175, 195 (Russian); English transl., J. Soviet Math.**41**(1988), no. 2, 979–991. MR**869582**, 10.1007/BF01247093**7.**Sergey Fomin,*Duality of graded graphs*, J. Algebraic Combin.**3**(1994), no. 4, 357–404. MR**1293822**, 10.1023/A:1022412010826**8.**Sergey Fomin,*Schensted algorithms for dual graded graphs*, J. Algebraic Combin.**4**(1995), no. 1, 5–45. MR**1314558**, 10.1023/A:1022404807578**9.**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****10.**Robert Grossman and Richard G. Larson,*Hopf-algebraic structure of families of trees*, J. Algebra**126**(1989), no. 1, 184–210. MR**1023294**, 10.1016/0021-8693(89)90328-1**11.**Michael E. Hoffman,*An analogue of covering space theory for ranked posets*, Electron. J. Combin.**8**(2001), no. 1, Research Paper 32, 12 pp. (electronic). MR**1877651****12.**Donald E. Knuth,*The art of computer programming. Volume 3*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR**0445948****13.**Dirk Kreimer,*On the Hopf algebra structure of perturbative quantum field theories*, Adv. Theor. Math. Phys.**2**(1998), no. 2, 303–334. MR**1633004**, 10.4310/ATMP.1998.v2.n2.a4**14.**Dirk Kreimer,*On overlapping divergences*, Comm. Math. Phys.**204**(1999), no. 3, 669–689. MR**1707611**, 10.1007/s002200050661**15.**D. Kreimer,*Chen’s iterated integral represents the operator product expansion*, Adv. Theor. Math. Phys.**3**(1999), no. 3, 627–670. MR**1797019**, 10.4310/ATMP.1999.v3.n3.a7**16.**Dirk Kreimer,*Knots and Feynman diagrams*, Cambridge Lecture Notes in Physics, vol. 13, Cambridge University Press, Cambridge, 2000. MR**1778151****17.**John W. Milnor and John C. Moore,*On the structure of Hopf algebras*, Ann. of Math. (2)**81**(1965), 211–264. MR**0174052****18.**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**, 10.1023/A:1007600216187**19.**N. J. A. Sloane, Online Encyclopedia of Integer Sequences, Sequence A000081,`www.research.``att.com/~njas/sequences/.`**20.**Richard P. Stanley,*Ordered structures and partitions*, American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. MR**0332509****21.**Richard P. Stanley,*Differential posets*, J. Amer. Math. Soc.**1**(1988), no. 4, 919–961. MR**941434**, 10.1090/S0894-0347-1988-0941434-9**22.**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**

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:
http://dx.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