Combinatorics of rooted trees and Hopf algebras
Author:
Michael E. Hoffman
Journal:
Trans. Amer. Math. Soc. 355 (2003), 37953811
MSC (2000):
Primary 05C05, 16W30; Secondary 81T15
Published electronically:
May 15, 2003
MathSciNet review:
1990174
Fulltext 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 nonroot 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 GrossmanLarson 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
(2000h:81167), http://dx.doi.org/10.1006/jsco.1999.0283
 2.
C. Brouder, RungeKutta methods and renormalization, European Phys. J. C 12 (2000), 521534.
 3.
Alain
Connes and Dirk
Kreimer, Hopf algebras, renormalization and noncommutative
geometry, Comm. Math. Phys. 199 (1998), no. 1,
203–242. MR 1660199
(99h:81137), http://dx.doi.org/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
(99m:58186), http://dx.doi.org/10.1007/s002200050477
 5.
L. Foissy, Finitedimensional comodules over the Hopf algebra of rooted trees, J. Algebra 255 (2002), 89120.
 6.
S.
V. Fomin, The generalized RobinsonSchenstedKnuth
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 (88b:06003), http://dx.doi.org/10.1007/BF01247093
 7.
Sergey
Fomin, Duality of graded graphs, J. Algebraic Combin.
3 (1994), no. 4, 357–404. MR 1293822
(95i:05088), http://dx.doi.org/10.1023/A:1022412010826
 8.
Sergey
Fomin, Schensted algorithms for dual graded graphs, J.
Algebraic Combin. 4 (1995), no. 1, 5–45. MR 1314558
(95m:05246), http://dx.doi.org/10.1023/A:1022404807578
 9.
José
M. GraciaBondí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
(2001h:58038)
 10.
Robert
Grossman and Richard
G. Larson, Hopfalgebraic structure of families of trees, J.
Algebra 126 (1989), no. 1, 184–210. MR 1023294
(90j:16022), http://dx.doi.org/10.1016/00218693(89)903281
 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
(2003d:06004)
 12.
Donald
E. Knuth, The art of computer programming. Volume 3,
AddisonWesley Publishing Co., Reading, Mass.LondonDon Mills, Ont., 1973.
Sorting and searching; AddisonWesley Series in Computer Science and
Information Processing. MR 0445948
(56 #4281)
 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
(99e:81156)
 14.
Dirk
Kreimer, On overlapping divergences, Comm. Math. Phys.
204 (1999), no. 3, 669–689. MR 1707611
(2000f:81128), http://dx.doi.org/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
(2003b:81128)
 16.
Dirk
Kreimer, Knots and Feynman diagrams, Cambridge Lecture Notes
in Physics, vol. 13, Cambridge University Press, Cambridge, 2000. MR 1778151
(2002f:81078)
 17.
John
W. Milnor and John
C. Moore, On the structure of Hopf algebras, Ann. of Math. (2)
81 (1965), 211–264. MR 0174052
(30 #4259)
 18.
Florin
Panaite, Relating the ConnesKreimer and GrossmanLarson Hopf
algebras built on rooted trees, Lett. Math. Phys. 51
(2000), no. 3, 211–219. MR 1775423
(2002a:81177), http://dx.doi.org/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
(48 #10836)
 21.
Richard
P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), no. 4, 919–961. MR 941434
(89h:06005), http://dx.doi.org/10.1090/S08940347198809414349
 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
(91h:06004)
 1.
 D. J. Broadhurst and D. Kreimer, Renormalization automated by Hopf algebra, J. Symbolic Comput. 27 (1999), 581600. MR 2000h:81167
 2.
 C. Brouder, RungeKutta methods and renormalization, European Phys. J. C 12 (2000), 521534.
 3.
 A. Connes and D. Kreimer, Hopf algebras, renormalization, and noncommutative geometry, Comm. Math. Phys. 199 (1998), 203242. MR 99h:81137
 4.
 A. Connes and H. Moscovici, Hopf algebras, cyclic cohomology and the transverse index theorem, Comm. Math. Phys. 198 (1998), 199246. MR 99m:58186
 5.
 L. Foissy, Finitedimensional comodules over the Hopf algebra of rooted trees, J. Algebra 255 (2002), 89120.
 6.
 S. V. Fomin, The generalized RobinsonSchenstedKnuth correspondence (Russian), Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 155 (1986), Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII, 156175, 195; translation in J. Soviet Math. 41 (1988), 979991. MR 88b:06003
 7.
 S. Fomin, Duality of graded graphs, J. Algebraic Combin. 3 (1994), 357404. MR 95i:05088
 8.
 S. Fomin, Schensted algorithms for dual graded graphs, J. Algebraic Combin. 4 (1995), 545. MR 95m:05246
 9.
 J. M. GraciaBondí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, Hopfalgebraic structure of families of trees, J. Algebra 126 (1989), 184210. 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., AddisonWesley, 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), 303334. MR 99e:81156
 14.
 D. Kreimer, On overlapping divergences, Comm. Math. Phys. 204 (1999), 669689. MR 2000f:81128
 15.
 D. Kreimer, Chen's iterated integral represents the operator product expansion, Adv. Theor. Math. Phys. 3 (1999), 627670. 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), 211261. MR 30:4259
 18.
 F. Panaite, Relating the ConnesKreimer and GrossmanLarson Hopf algebras built on rooted trees, Lett. Math. Phys. 51 (2000), 211219. 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), 919961. 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, SpringerVerlag, New York, 1990, pp. 145165. 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
Email:
meh@usna.edu
DOI:
http://dx.doi.org/10.1090/S0002994703033178
PII:
S 00029947(03)033178
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
