  Combinatorial Hopf algebras of trees exemplify the connections between
operads and bialgebras. Painted trees were introduced recently as examples of
how graded Hopf operads can bequeath Hopf structures upon compositions of
coalgebras. We put these trees in context by exhibiting them as the minimal
elements of face posets of certain convex polytopes. The full face posets
themselves often possess the structure of graded Hopf algebras (with one-sided
unit). We can enumerate faces using the fact that they are structure types of
substitutions of combinatorial species. Species considered here include ordered
and unordered binary trees and ordered lists (labeled corollas). Some of the
polytopes that constitute our main results are well known in other contexts.
First we see the classical permutohedra, and then certain generalized
permutohedra: specifically the graph associahedra of suspensions of certain
simple graphs. As an aside we show that the stellohedra also appear as liftings
of generalized permutohedra: graph composihedra for complete graphs. Thus our
results give examples of Hopf algebras of tubings and marked tubings of graphs.
We also show an alternative associative algebra structure on the graph tubings
of star graphs.
