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$.