Thursday, April 7, 2011

Theory Update 78

Recall that the rooted trees of Connes-Kreimer renormalization theory form a Hopf algebra using a cutting rule on trees. We therefore need to consider forests, meaning collections of trees. The set of rooted forests will then have its vertices labeled. When only leaf vertices are labeled, as in the table below, the number of labeled forests on $n$ vertices is the same as the number of parking functions for $n$, which is the same as the number of simplices in the associahedron of dimension $n$.

Note that label sets are attached to each tree in a forest, so that separated trees commute. Labels within a tree do not commute. If we labeled all the vertices in each graph, there would clearly be $24$ vertices for $n = 3$. This is the number of vertices in the larger permutohedron polytope, based on the permutation group $S_4$. Stanley has also studied parking functions in such a context, defining a $q$ function for rooted forests, where the grading on the polynomial comes from the forest list.

Update: we should alter the labels on the lowest two diagrams for $n = 3$. That is, we put a total order on the vertices of each graph, to obtain a total of $16$ graphs. On the V shaped graph, this means placing $23$, $13$ or $12$ on the leaves, but not the reverse, so there are three graphs of this type. There are then $6$ graphs for the three level tree, namely the $6$ permutations of $123$.


  1. The Hopf algebra equivalence (ie. for parking functions and rooted trees) proves that the associahedra are closely linked to renormalization theory, and are hence of importance to physics, as we keep saying.

  2. The same binary sequence that describes the branches of the canopy of a tree is that which describes the growth over time to reach the canopy of branches. (something your article inspired from old reading.)

    The PeSla

  3. Lovely prose as usual, thanks, ThePeSla.


Note: Only a member of this blog may post a comment.