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.