Combinatorial Hopf Algebras On Generating Trees And Certain Generating Graphs

Hopf algebras capture how combinatorial objects can be decomposed into their subparts in different ways. Generating trees and generating graphs provide one structured way to understand many combinatorial classes. Furthermore, Hochschild 1-cocycle maps of renormalization Hopf algebras play an important role in quantum field theories but are not well known in combinatorics. In the generalised atmospheric method for sampling self-avoiding polygons, there is a weight function which deals with overcounting and hints at a connection with the 1-cocycle maps. Both of these combinatorial objects can be represented by generating graphs. As a first step towards understanding this connection, we provide two ways to construct Hopf algebras on generating trees through a normalizing map φ ̃. One is concatenation and deshuffle type and the other is shuffle and deconcatenation type. We also construct an incidence Hopf algebra on certain generating graphs and construct a Hopf algebra on self-avoiding polygons.