# Cofree compositions of coalgebras

Stefan Forcey<fnref n="1" />, Aaron Lauve<fnref n="2" />† and Frank Sottile<fnref n="3" />‡

**Abstract.** We develop the notion of the composition of two coalgebras, which arises naturally in higher category theory and the theory of species. We prove that the composition of two cofree coalgebras is cofree and give conditions which imply that the composition is a one-sided Hopf algebra. These conditions hold when one coalgebra is a graded Hopf operad $\mathcal{D}$ and the other is a connected graded coalgebra with coalgebra map to $\mathcal{D}$. We conclude with examples of these structures, where the factor coalgebras have bases indexed by the vertices of multiplihedra, composihedra, and hypercubes.

**Résumé.** Nous développons la notion de composition de coalgèbres, qui apparaît naturellement dans la théorie des catégories d'ordre supérieur et dans la théorie des espèces. Nous montrons que la composée de deux coalgèbres colibres est colibre et nous donnons des conditions qui impliquent que la composée est une algèbre de Hopf uni-latérale. Ces conditions sont valables quand l'une des coalgèbres est une opérade de Hopf graduée $\mathcal{D}$ et l'autre est une coalgèbre graduée connexe avec un morphisme vers $\mathcal{D}$. Nous concluons avec des exemples de ces structures, où les coalgèbres composées ont des bases indexées par les sommets de multiplièdres, de composièdres, et d'hypercubes.

**Keywords:** multiplihedron, cofree coalgebra, Hopf algebra, operad, species

## 1 Introduction

The Hopf algebras of ordered trees (Malvenuto and Reutenauer (1995)) and of planar binary trees (Loday and Ronco (1998)) are cofree coalgebras that are connected by cellular maps from permutahedra to as-sociahedra. Related polytopes include the multiplihedra (Stasheff (1970)) and the composihedra (Forcey (2008b)), and it is natural to study what Hopf structures may be placed on these objects. The map from permutahedra to associahedra factors through the multiplihedra, and in (Forcey et al. (2010)) we used this factorization to place Hopf structures on bi-leveled trees, which correspond to vertices of multiplihedra.

Multiplihedra form an operad module over associahedra. This leads to painted trees, which also corre-spond to the vertices of the multiplihedra. In terms of painted trees, the Hopf structures of (Forcey et al. (2010)) are related to the operad module structure. We generalize this in Section 3, defining the functorial construction of a graded coalgebra $\mathcal{D} \circ \mathcal{C}$ from graded coalgebras $\mathcal{C}$ and $\mathcal{D}$. We show that this composition of coalgebras preserves cofreeness. In Section 4 we give sufficient conditions, when $\mathcal{D}$ is a Hopf algebra,

<footnote n="1">¹Department of Theoretical and Applied Mathematics, The University of Akron, Akron, OH, USA</footnote>

<footnote n="2">²Department of Mathematics, Loyola University of Chicago, Chicago, IL, USA</footnote>

<footnote n="3">³Department of Mathematics, Texas A&M University, College Station, TX, USA</footnote>

<footnote>†Supported in part by NSA grant H98230-10-1-0362.</footnote>

<footnote>‡Supported in part by NSF grants DMS-0701050 and DMS-1001615.</footnote>
for the composition of coalgebras $\mathcal{D} \circ \mathcal{C}$ (and $\mathcal{C} \circ \mathcal{D}$) to be a one-sided Hopf algebra. These conditions also guarantee that a composition is a Hopf module and a comodule algebra over $\mathcal{D}$.

This composition (also known as substitution) is familiar from the theories of operads and species. If a species is a monoid with respect to $\circ$ then it is also an operad (Aguiar and Mahajan, 2010, App. B). In Section 4 we show that an operad $\mathcal{D}$ of connected graded coalgebras is automatically a Hopf algebra.

We discuss three examples related to well-known objects from category theory and algebraic topology and show that the Hopf algebra of simplices of (Forcey and Springfield (2010)) is cofree as a coalgebra.

# 2 Preliminaries

We work over a fixed field $\mathbb{K}$ of characteristic zero. For a graded vector space $V = \bigoplus_n V_n$, we write $|v| = n$ and say $v$ has degree $n$ if $v \in V_n$.

## 2.1 Hopf algebras and cofree coalgebras

A coalgebra $\mathcal{C}$ is a vector space $\mathcal{C}$ equipped with a coassociative coproduct $\Delta: \mathcal{C} \to \mathcal{C} \otimes \mathcal{C}$ and counit $\varepsilon: \mathcal{C} \to \mathbb{K}$. For $c \in \mathcal{C}$, write $\Delta(c)$ as $\sum_{(c)} c' \otimes c''$. Coassociativity means that

$$ \sum_{(c),(c')} (c')' \otimes (c'')'' \otimes c'' = \sum_{(c),(c'')} c' \otimes (c'')' \otimes (c'')'' = \sum_{(c)} c' \otimes c'' \otimes c''' $$

and the counital condition reads $\sum_{(c)} \varepsilon(c')c'' = \sum_{(c)} c'\varepsilon(c'') = c$. A Hopf algebra is a unital associative algebra $H$ that is also a coalgebra whose structure maps (coproduct $\Delta$ and counit $\varepsilon$) are algebra homomorphisms, with the additional condition of having an antipode. See (Montgomery (1993)) for more details. Takeuchi (1971) showed that a graded bialgebra $H = (\bigoplus_{n \ge 0} H_n, \cdot, \Delta, \varepsilon)$ that is connected ($H_0 = \mathbb{K}$) is a Hopf algebra. A one-sided Hopf algebra $H = (H, u, m, \Delta, \varepsilon, S)$ is allowed to have only a one-sided unit $u$ and to satisfy only one of $m(S \otimes 1)\Delta = u\varepsilon$ and $m(1 \otimes S)\Delta = u\varepsilon$. This relaxes the standard notion appearing in the literature (Green et al. (1980)), where only the antipode is allowed to be one-sided.

The graded cofree coalgebra on a vector space $V$ is $\mathbb{C}(V) := \bigoplus_{n \ge 0} V^{\otimes n}$ with counit the projection $\varepsilon: \mathbb{C}(V) \to \mathbb{K} = V^{\otimes 0}$ and the deconcatenation coproduct: writing “\” for the tensor product in $V^{\otimes n}$, we have

$$ \Delta(c_1 \cdots c_n) = \sum_{i=0}^{n} (c_1 \cdots c_i) \otimes (c_{i+1} \cdots c_n). $$

Observe that $V$ is the set of primitive elements of $\mathbb{C}(V)$. A graded coalgebra $\mathcal{C}$ is cofree if $\mathcal{C} \simeq \mathbb{C}(P_{\mathcal{C}})$, where $P_{\mathcal{C}}$ is the space of primitive elements of $\mathcal{C}$. Many coalgebras arising in combinatorics are cofree.

## 2.2 Cofree Hopf algebras on trees

We describe three cofree Hopf algebras built on rooted planar binary trees: ordered trees $\mathfrak{S}_n$, binary trees $\mathcal{Y}_n$, and (left) combs $\mathfrak{C}_n$ on $n$ internal nodes. Set $\mathfrak{S}_n := \bigcup_{n \ge 0} \mathfrak{S}_n$ and define $\mathcal{Y}_n$ and $\mathfrak{C}_n$ similarly.

### 2.2.1 Constructions on trees

The nodes of a tree $t \in \mathcal{Y}_n$ form a poset. An ordered tree $w = w(t)$ is a linear extension of this node poset of $t$. This linear extension is indicated by placing a permutation in the gaps between its leaves, which gives a bijection between ordered trees and permutations. The map $\tau: \mathfrak{S}_n \to \mathcal{Y}_n$ sends an ordered
tree $w(t)$ to its underlying tree $t$. The map $\kappa: \mathcal{Y}_n \to \mathcal{C}_n$ shifts all nodes of a tree to the right branch from the root. Set $\mathcal{S}_0 = \mathcal{Y}_0 = \mathcal{C}_0 = \text{l}$. Note that $|\mathcal{C}_n| = 1$ for all $n \ge 0$.

<figure><img src="image_1.png" /></figure>

*Splitting* an ordered tree $w$ along the path from a leaf to the root yields an ordered forest (where the nodes in the forest are totally ordered) or a pair of ordered trees,

<figure><img src="image_2.png" /></figure>

Write $w \xrightarrow{\gamma} (w_0, w_1)$ when the ordered forest $(w_0, w_1)$ (or pair of ordered trees) is obtained by splitting $w$. (Context will determine how to interpret the result.)

We may *graft* an ordered forest $\vec{w} = (w_0, \dots, w_n)$ onto an ordered tree $v \in \mathcal{S}_n$, obtaining the tree $\vec{w}/v$ as follows. First increase each label of $v$ so that its nodes are greater than the nodes of $\vec{w}$, and then graft tree $w_i$ onto the $i^{th}$ leaf of $v$. For example,

<figure><img src="image_3.png" /></figure>

Splitting and grafting make sense for trees in $\mathcal{Y}$. They also work for $\mathcal{C}$, if, after grafting a forest of combs onto the leaves of a comb, one applies $\kappa$ to the resulting planar binary tree to get a new comb.

### 2.2.2 Three cofree Hopf algebras

Let $\mathcal{G}Sym := \bigoplus_{n \ge 0} \mathcal{G}Sym_n$ be the graded vector space whose $n^{th}$ graded piece has basis $\{F_w \mid w \in \mathcal{G}_n\}$. Define $\mathcal{Y}Sym$ and $\mathcal{C}Sym$ similarly. The set maps $\tau$ and $\kappa$ induce vector space maps $\tau$ and $\kappa$, $\tau(F_w) = F_{\tau(w)}$ and $\kappa(F_w) = F_{\kappa(w)}$. Fix $\mathcal{X} \in \{\mathcal{G}, \mathcal{Y}, \mathcal{C}\}$. For $w \in \mathcal{X}$, and $v \in \mathcal{X}_n$, set
$$F_w \cdot F_v := \sum_{w \xrightarrow{\cdot} (w_0, \dots, w_n)} F_{(w_0, \dots, w_n)/v},$$

the sum over all (ordered) forests obtained by splitting $w$ at a multiset of $n$ leaves. For $w \in \mathcal{X}$, set

$$\Delta(F_w) := \sum_{w \xrightarrow{\cdot} (w_0, w_1)} F_{w_0} \otimes F_{w_1},$$

the sum over all splittings of $w$ at one leaf. The count $\varepsilon$ is the projection onto the 0th graded piece, spanned by the unit element $1 = F_1$ for the multiplication.

**Proposition 2.1** For $(\Delta, \cdot, \varepsilon)$ above, $\mathfrak{GSym}$ is the Malvenuto–Reutenauer Hopf algebra of permutations, $\mathcal{YSym}$ is the Loday–Ronco Hopf algebra of planar binary trees, and $\mathfrak{CSym}$ is the divided power Hopf algebra. Moreover, $\mathfrak{GSym} \xrightarrow{\tau} \mathcal{YSym}$ and $\mathcal{YSym} \xrightarrow{\kappa} \mathfrak{CSym}$ are surjective Hopf algebra maps. $\square$

The part of the proposition involving $\mathfrak{GSym}$ and $\mathcal{YSym}$ is found in (Aguiar and Sottile (2005, 2006)); the part involving $\mathfrak{CSym}$ is straightforward and we leave it to the reader.

Typically (Montgomery, 1993, Ex 5.6.8), the divided power Hopf algebra is defined to be $\mathbb{K}[x] := \text{span}\{x^{(n)} | n \ge 0\}$, with basis vectors $x^{(n)}$ satisfying $x^{(m)} \cdot x^{(n)} = \binom{m+n}{n} x^{(m+n)}$, $1 = x^{(0)}$, $\Delta(x^{(n)}) = \sum_{i+j=n} x^{(i)} \otimes x^{(j)}$, and $\varepsilon(x^{(n)}) = 0$ for $n > 0$. An isomorphism between $\mathbb{K}[x]$ and $\mathfrak{CSym}$ is given by $x^{(n)} \mapsto F_{c_n}$, where $c_n$ is the unique comb in $\mathfrak{C}_n$.

**Proposition 2.2** The Hopf algebras $\mathfrak{GSym}$, $\mathcal{YSym}$, and $\mathfrak{CSym}$ are cofree as coalgebras. The primitive elements of $\mathcal{YSym}$ and $\mathfrak{CSym}$ are indexed by trees with no nodes off the right branch from the root. $\square$

The result for $\mathfrak{CSym}$ is easy. Proposition 2.2 is proven for $\mathfrak{GSym}$ and $\mathcal{YSym}$ in (Aguiar and Sottile (2005, 2006)) by performing a change of basis—from the fundamental basis $F_w$ to the monomial basis $M_w$—by means of Möbius inversion in a poset structure placed on $\mathfrak{S}$ and $\mathcal{Y}$.

# 3 Constructing Cofree Compositions of Coalgebras

## 3.1 Cofree compositions of coalgebras

Let $\mathcal{C}$ and $\mathcal{D}$ be graded coalgebras. Form a new coalgebra $\mathcal{E} = \mathcal{D} \circ \mathcal{C}$ on the vector space

$$\mathcal{D} \circ \mathcal{C} := \bigoplus_{n \ge 0} \mathcal{D}_n \otimes \mathcal{C}^{\otimes (n+1)}. \qquad (3.1)$$

When $\mathcal{C}$ and $\mathcal{D}$ are spaces of rooted, planar trees we may interpret $\circ$ in terms of a rule for grafting trees.

**Example 3.1** Suppose $\mathcal{C} = \mathcal{D} = \mathcal{YSym}$ and let $d \times (c_0, \dots, c_n) \in \mathcal{Y}_n \times (\mathcal{Y}_*^{n+1})$. Define $\circ$ by attaching the forest $(c_0, \dots, c_n)$ to the leaves of $d$ while remembering $d$, giving a *painted tree*,

<figure><img src="image_4.png" /></figure>
We represent an indecomposable tensor in $\mathcal{E} := \mathcal{D} \circ \mathcal{C}$ as

$$d \circ (c_0 \cdots c_n) \quad \text{or} \quad \frac{c_0 \cdots c_n}{d}.$$

The *degree* of such an element is $|d| + |c_0| + \cdots + |c_n|$. Write $\mathcal{E}_n$ for the span of elements of degree $n$.

### 3.1.1 The coalgebra $\mathcal{D} \circ \mathcal{C}$

We define the *compositional coproduct* $\Delta$ for $\mathcal{D} \circ \mathcal{C}$ on indecomposable tensors: if $|d| = n$, put

$$\Delta \left( \frac{c_0 \cdots c_n}{d} \right) = \sum_{i=0}^{n} \sum_{\substack{(d) \\ |d'|=i}} \sum_{(c_i)} \frac{c_0 \cdots c_{i-1} \cdot c_i'}{d''} \otimes \frac{c_i'' \cdot c_{i+1} \cdots c_n}{d''}. \quad (3.2)$$

The *count* $\varepsilon: \mathcal{D} \circ \mathcal{C} \to \mathbb{K}$ is given by $\varepsilon(d \circ (c_0 \cdots c_n)) = \varepsilon_{\mathcal{D}}(d) \cdot \prod_j \varepsilon_{\mathcal{C}}(c_j)$.

For the painted trees of Example 3.1, if the $c_i$ and $d$ are elements of the $F$-basis, then $\Delta(d \circ (c_0 \cdots c_n))$ is the sum over all splittings $t \xrightarrow{\gamma} (t', t'')$ of $t$ into a pair of painted trees.

**Theorem 3.2** ($\mathcal{D} \circ \mathcal{C}$, $\Delta$, $\varepsilon$) is a coalgebra. This composition is functorial, i.e., if $\varphi: \mathcal{C} \to \mathcal{C}'$ and $\psi: \mathcal{D} \to \mathcal{D}'$ are morphisms of graded coalgebras, then

$$\frac{c_0 \cdots c_n}{d} \mapsto \frac{\varphi(c_0) \cdots \varphi(c_n)}{\psi(d)}$$

defines a morphism of graded coalgebras $\varphi \circ \psi: \mathcal{D} \circ \mathcal{C} \to \mathcal{D}' \circ \mathcal{C}'$.

### 3.1.2 The cofree coalgebra $\mathcal{D} \circ \mathcal{C}$

Suppose that $\mathcal{C}$ and $\mathcal{D}$ are graded, connected, and cofree. Then $\mathcal{C} = \mathcal{C}(P_{\mathcal{C}})$, where $P_{\mathcal{C}} \subset \mathcal{C}$ is its space of primitive elements. Likewise, $\mathcal{D} = \mathcal{C}(P_{\mathcal{D}})$, where $P_{\mathcal{D}} \subset \mathcal{D}$ is its space of primitive elements.

**Theorem 3.3** If $\mathcal{C}$ and $\mathcal{D}$ are cofree coalgebras then $\mathcal{D} \circ \mathcal{C}$ is also a cofree coalgebra. Its space of primitive elements is spanned by indecomposable tensors of the form

$$\frac{1 \cdot c_1 \cdots c_{n-1} \cdot 1}{\delta} \quad \text{and} \quad \frac{\gamma}{1}, \qquad (3.3)$$

where $\gamma, c_i \in \mathcal{C}$ and $\delta \in \mathcal{D}_n$, with $\gamma$ and $\delta$ primitive.

**Example 3.4** The graded Hopf algebras of ordered trees $\mathfrak{S}Sym$, planar trees $\mathcal{Y}Sym$, and divided powers $\mathfrak{C}Sym$ are all cofree, and so their compositions are cofree. We have the surjective Hopf algebra maps

$$\mathfrak{S}Sym \xrightarrow{\tau} \mathcal{Y}Sym \xrightarrow{\kappa} \mathfrak{C}Sym$$

giving the commutative diagram of Figure 1 of nine cofree coalgebras as the composition $\circ$ is functorial.
<figure><img src="image_5.png" /><figcaption>Fig. 1: A commutative diagram of cofree compositions of coalgebras.</figcaption></figure>

## 3.2 Some enumeration

Set $\mathcal{E} := \mathcal{D} \circ \mathcal{C}$ and let $C_n$ and $E_n$ be the dimensions of $C_n$ and $\mathcal{E}_n$, respectively.

**Theorem 3.5** When $\mathcal{D}_n$ has a basis indexed by combs with $n$ internal nodes we have the recursion

$$E_0 = 1, \quad \text{and for } n > 0, \quad E_n = C_n + \sum_{i=0}^{n-1} C_i E_{n-i-1}.$$

**Proof:** The first term counts elements in $\mathcal{E}_n$ of the form $| \circ c$. Removing the root node of $d$ from $d \circ (c_0 \cdots c_k)$ gives a pair $| \circ (c_0)$ and $d' \circ (c_1 \cdots c_k)$ with $c_0 \in \mathcal{C}_i$, whose dimensions are enumerated by the terms of the sum. $\square$

For combs over a comb, $E_n = 2^n$, for trees over a comb, $E_n$ are the Catalan numbers, and for permutations over a comb, we have the recursion

$$E_0 = 1, \quad \text{and for } n > 0, \quad E_n = n! + \sum_{i=0}^{n-1} i! E_{n-i-1},$$

which begins 1, 2, 5, 15, 54, 235, ..., and is sequence A051295 of the OEIS (Sloane). Similarly,

**Theorem 3.6** When $\mathcal{D}_n$ has a basis indexed by $\mathcal{Y}_n$ then we have the recursion

$$E_0 = 1, \quad \text{and for } n > 0, \quad E_n = C_n + \sum_{i=0}^{n-1} E_i E_{n-i-1}.$$

For example, the combs over a tree are enumerated by the binary transform of the Catalan numbers (Forcey (2008b)). The trees over a tree are enumerated by the Catalan transform of the Catalan numbers (Forcey (2008a)). The permutations over a tree are enumerated by the recursion

$$E_0 = 1, \quad \text{and for } n > 0, \quad E_n = n! + \sum_{i=0}^{n-1} E_i E_{n-i-1},$$
which begins 1, 2, 6, 22, 92, 428, ... and is not a recognized sequence in the OEIS (Sloane). We do not have attractive recursive formulas when $D_n$ has a basis indexed by $\mathfrak{S}_n$.

# 4 Composition of Coalgebras and Hopf Modules

We give conditions that imply a composition of coalgebras is a one-sided Hopf algebra, interpret this via operads, and then investigate which compositions of Fig. 1 are one-sided Hopf algebras.

## 4.1 Module coalgebras

Let $D$ be a connected graded Hopf algebra with product $m_D$, coproduct $\Delta_D$, and unit element $1_D$.

A map $f: \mathcal{E} \to D$ of graded coalgebras is a *connection* on $D$ if $\mathcal{E}$ is a $D$-module coalgebra, $f$ is a map of $D$-module coalgebras, and $\mathcal{E}$ is connected. This means that $\mathcal{E}$ is an associative (left or right) $D$-module whose action (denoted $\star$) commutes with the coproducts, so that $\Delta_{\mathcal{E}}(e \star d) = \Delta_{\mathcal{E}}(e) \star \Delta_{D}(d)$, for $e \in \mathcal{E}$ and $d \in D$, and the coalgebra map $f$ is also a module map, so that for $e \in \mathcal{E}$ and $d \in D$ we have

$$ (f \otimes f) \Delta_{\mathcal{E}}(e) = \Delta_{D} f(e) \quad \text{and} \quad f(e \star d) = m_{D}(f(e) \otimes d). $$

**Theorem 4.1** If $\mathcal{E}$ is a connection on $D$, then $\mathcal{E}$ is also a Hopf module and a comodule algebra over $D$. It is also a one-sided Hopf algebra with right-sided unit $1_{\mathcal{E}} := f^{-1}(1_{D})$ and left-sided antipode.

**Proof:** Suppose $\mathcal{E}$ is a right $D$-module. Define the product $m_{\mathcal{E}}: \mathcal{E} \otimes \mathcal{E} \to \mathcal{E}$ via the $D$-action: $m_{\mathcal{E}} := \star \circ (1 \otimes f)$. The one-sided unit is $1_{\mathcal{E}}$. Then $\Delta_{\mathcal{E}}$ is an algebra map. Indeed, for $e, e' \in \mathcal{E}$, we have

$$ \Delta_{\mathcal{E}}(e \cdot e') = \Delta_{\mathcal{E}}(e \star f(e')) = \Delta_{\mathcal{E}}e \star \Delta_{D}f(e') = \Delta_{\mathcal{E}}e \star (f \otimes f)(\Delta_{\mathcal{E}}e') = \Delta_{\mathcal{E}}e \cdot \Delta_{\mathcal{E}}e'. $$

As usual, $\varepsilon_{\mathcal{E}}$ is just projection onto $\mathcal{E}_0$. The unit $1_{\mathcal{E}}$ is one-sided, since

$$ e \cdot 1_{\mathcal{E}} = e \star f(1_{\mathcal{E}}) = e \star f(f^{-1}(1_{D})) = e \star 1_{D} = e, $$

but $1_{\mathcal{E}} \cdot e = 1_{\mathcal{E}} \star f(e)$ is not necessarily equal to $e$. The antipode $S$ may be defined recursively to satisfy $m_{\mathcal{E}}(S \otimes 1)\Delta_{\mathcal{E}} = \varepsilon_{\mathcal{E}}$, just as for graded bialgebras with two-sided units.

Define $\rho: \mathcal{E} \to \mathcal{E} \otimes D$ by $\rho := (1 \otimes f) \Delta_{\mathcal{E}}$, which gives a coaction so that $\mathcal{E}$ is a Hopf module and a comodule algebra over $D$. $\square$

## 4.2 Operads and operad modules

Composition of coalgebras is the same product used to define operads internal to a symmetric monoidal category (Aguiar and Mahajan, 2010, App. B). A *monoid* in a category with a product $\bullet$ is an object $D$ with a morphism $\gamma: D \bullet D \to D$ that is associative. An *operad* is a monoid in the category of graded sets with an analog of the composition product $\circ$ defined in Section 3.1.

Connected graded coalgebras form a symmetric monoidal category under the composition $\circ$ of coalgebras. A *graded Hopf operad* $\mathcal{D}$ is a monoid in this monoidal category of connected graded coalgebras and coalgebra maps. That is, $\mathcal{D}$ is equipped with associative composition maps

$$ \gamma: D \circ D \to D, \text{ obeying } \Delta_D \gamma(a) = (\gamma \otimes \gamma)(\Delta_{D \circ D}(a)) \text{ for all } a \in D \circ D. $$

A *graded Hopf operad module* $\mathcal{E}$ is an operad module over $D$ and a graded coassociative coalgebra whose module action is compatible with its coproduct. We denote the left and right action maps by $\mu_l: D \circ \mathcal{E} \to \mathcal{E}$ and $\mu_r: \mathcal{E} \circ D \to \mathcal{E}$, obeying, e.g., $\Delta_{\mathcal{E}}\mu_r(b) = (\mu_r \otimes \mu_r)\Delta_{\mathcal{E}\circ D}b$ for all $b \in \mathcal{E} \circ D$.
**Example 4.2** $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ is an operad in the category of vector spaces. The action of $\gamma$ on $F_t \circ (F_{t_0} \cdots F_{t_n})$ grafts the trees $t_0, \dots, t_n$ onto the tree $t$ and, unlike in Example 3.1, forgets which nodes of the resulting tree came from $t$. This is associative in the appropriate sense. With the same $\gamma$, $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ is an operad in the category of connected graded coalgebras, making it a graded Hopf operad. Finally, operads are operad modules over themselves, so $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ is also a graded Hopf operad module.

**Remark 4.3** Our graded Hopf operads differ from those of Getzler and Jones, who defined a Hopf operad to be an operad of level coalgebras, where each component $\mathcal{D}_n$ is a coalgebra.

**Theorem 4.4** A graded Hopf operad $\mathcal{D}$ is also a Hopf algebra with product

$$a \cdot b := \gamma(b \otimes \Delta^{(n)}a) \qquad (4.1)$$

where $b \in \mathcal{D}_n$ and $\Delta^{(n)}$ is the iterated coproduct from $\mathcal{D}$ to $\mathcal{D}^{\otimes(n+1)}$.

It is possible to swap the roles of $a$ and $b$ on the right-hand side of (4.1). Our choice agrees with the product in $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ and $\mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m}$. In fact, the well-known Hopf algebra structures of $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ and $\mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m}$ follow from their structure as graded Hopf operads.

**Lemma 4.5** If $C$ is a graded coalgebra and $\mathcal{D}$ is a graded Hopf operad, then $\mathcal{D} \circ C$ is a (left) graded Hopf operad module and $C \circ \mathcal{D}$ is a (right) graded Hopf operad module.

**Lemma 4.6** A graded Hopf operad module over a graded Hopf operad is also a module coalgebra.

**Theorem 4.7** Given a coalgebra map $\lambda: C \to \mathcal{D}$ from a connected graded coalgebra $C$ to a graded Hopf operad $\mathcal{D}$, the maps $\gamma \circ (1 \circ \lambda): \mathcal{D} \circ C \to \mathcal{D}$ and $\gamma \circ (\lambda \circ 1): C \circ \mathcal{D} \to \mathcal{D}$ give connections on $\mathcal{D}$.

## 4.3 Examples of module coalgebra connections

Eight of the nine compositions of Example 3.4 are connections on one or both of the factors $C$ and $\mathcal{D}$.

**Theorem 4.8** For $C \in \{\mathcal{G}\mathcal{S}\mathcal{y}\mathcal{m}, \mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}, \mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m}\}$, the coalgebra compositions $C \circ \mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m}$ and $\mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m} \circ C$ are connections on $\mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m}$. For $C \in \{\mathcal{G}\mathcal{S}\mathcal{y}\mathcal{m}, \mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}, \mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m}\}$, the coalgebra compositions $C \circ \mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ and $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m} \circ C$ are connections on $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$.

Note that $\mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m} \circ \mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ is a connection on both $\mathcal{C}\mathcal{S}\mathcal{y}\mathcal{m}$ and on $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$, which gives two distinct one-sided Hopf algebra structures. Similarly, $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m} \circ \mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ is a connection on $\mathcal{Y}\mathcal{S}\mathcal{y}\mathcal{m}$ in two distinct ways (again leading to two distinct one-sided Hopf structures). We do not know if $\mathcal{G}\mathcal{S}\mathcal{y}\mathcal{m} \circ \mathcal{G}\mathcal{S}\mathcal{y}\mathcal{m}$ is a connection over $\mathcal{G}\mathcal{S}\mathcal{y}\mathcal{m}$.

# 5 Three Examples

The three underlined algebras in Example 3.4 arose previously in algebra, topology, and category theory.

## 5.1 Painted Trees

A *painted binary tree* is a planar binary tree $t$, together with a (possibly empty) upper order ideal of its node poset. We indicate this ideal by painting on top of a representation of $t$, as in Example 3.1 and below,

<figure><img src="image_6.png" /></figure>
An $A_n$-space is a topological $H$-space with a weakly associative multiplication of points (Stasheff (1963)). Stasheff (1970) described these maps using cell complexes called multiplihedra, while Boardman and Vogt (1973) used spaces of painted trees. Both the spaces of trees and the cell complexes are homeomorphic to convex polytope realizations of the multiplihedra as shown in (Forcey (2008a)).

If $f: (X, \bullet) \to (Y, *)$ is a map of $A_n$-spaces, then the different ways to multiply and map $n$ points of $X$ are represented by a painted tree. Unpainted nodes are multiplications in $X$, painted nodes are multiplications in $Y$, and the beginning of the painting indicates that $f$ is applied to a given point in $X$,

$$f(a) * (f(b \bullet c) * f(d)) \longleftrightarrow \text{[Picture]}.$$

### 5.1.1 Algebra structures on painted trees.

Let $P_n$ be the poset of painted trees on $n$ internal nodes, with partial order inherited from the identification with the poset $M_{n+1}$ of bi-leveled trees (i.e., the multiplihedron). Forcey et al. (2010) studied this order.

We describe the key definitions of Section 3.1 and Section 4 for $PSym := YSym \circ YSym$. In the fundamental basis $\{F_p | p \in P_*\}$ of $PSym$, the counit is $\varepsilon(F_p) = \delta_{0,|p|}$, and the product is given by

$$\Delta(F_p) = \sum_{\vec{p} \to (p_0, p_1)} F_{p_0} \otimes F_{p_1},$$

where the painting in $p \in P_n$ is preserved in the splitting $\vec{p} \to (p_0, p_1)$.

For example, we have

$$\Delta(F_{\text{[Picture]}}) = 1 \otimes F_{\text{[Picture]}} + F_{\text{[Picture]}} \otimes F_{\text{[Picture]}} + F_{\text{[Picture]}} \otimes F_{\text{[Picture]}} + F_{\text{[Picture]}} \otimes 1.$$

The identity map on $YSym$ makes $PSym$ into a connection on $YSym$. By Theorem 4.1, $PSym$ is thus also a one-sided Hopf algebra, a $YSym$-Hopf module, and a $YSym$-comodule algebra. The product $F_p \cdot F_q$ in $PSym$ is

$$F_p \cdot F_q = \sum_{\vec{p} \to (p_0, p_1, \dots, p_r)} F_{(p_0, p_1, \dots, p_r)/q^+},$$

where the painting in $p$ is preserved in the splitting $(p_0, p_1, \dots, p_r)$, and $q^+$ signifies that $q$ is painted completely before grafting. For example,

$$F_{\text{[Picture]}} \cdot F_{\text{[Picture]}} = F_{\text{[Picture]}} + F_{\text{[Picture]}} + F_{\text{[Picture]}} + F_{\text{[Picture]}}.$$

The painted tree $\downarrow$ with 0 nodes is only a right multiplicative identity element,

$$F_q \cdot F_{\downarrow} = F_q \quad \text{but} \quad F_{\downarrow} \cdot F_q = F_{q^+} \text{ for } q \in P_*.$$

As $PSym$ is graded and connected, it has a one-sided antipode.

**Theorem 5.1** There are unit and antipode maps $\mu: \mathbb{K} \to PSym$ and $S: PSym \to PSym$ making $PSym$ a one-sided Hopf algebra.
in the forest is combed and attached to the binary tree in $b$. We illustrate one term in the product. Suppose that

$a = \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture} = \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture}$ and $b = \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture} = \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture}$. Then $g(a) = \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture}$. One way to split $g(a)$ gives the forest $(|, \Y, |, \Y)$. Graft this onto $b$ to get $\begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture}$, then comb the forest to get $\begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture}$, which is $\begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture}$.

$$F_2 \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} \cdot F_1 \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} = F_3 \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} + 3F_1 \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} + F_1 \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} + 2F_2 \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} + F_2 \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} + 2F_1 \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture}$$

## 5.3 Composition trees

The simplest composition of Fig. 1 is $\mathcal{CSym} \circ \mathcal{CSym}$, whose basis is indexed by combs over combs. If we represent these as weighted trees as in (5.1), we see that we may identify combs over combs with $n$ internal nodes as compositions of $n+1$. Thus we refer to these as *composition trees*.

$$\begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture} \iff \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture} \iff (3, 2, 1, 4).$$

The coproduct is again given by splitting. Since the composition tree (1, 3) has the four splittings,

$$\begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {};
  \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {};
  \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {};
\end{tikzpicture} \xrightarrow{\Y} (|, \Y), (\Y, \Y), (\Y, \Y), (\Y, |), \qquad (5.2)$$

$$\text{we have } \Delta(F_{1,3}) = F_1 \otimes F_{1,3} + F_{1,1} \otimes F_3 + F_{1,2} \otimes F_2 + F_{1,3} \otimes F_1.$$

As we remarked, there are two connections $\mathcal{CSym} \circ \mathcal{CSym} \to \mathcal{CSym}$, using either the right or left action of $\mathcal{CSym}$. This gives two new one-sided Hopf algebra structures on compositions. With the right action, we have $F_{1,3} \cdot F_2 = 2F_{1,1,3} + F_{1,2,2} + F_{1,3,1}$, as

$$F \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} \cdot F \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} = F \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} + F \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} + F \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture} + F \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node[draw, circle, fill=red!20, inner sep=1pt] (Y) at (0,0) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y1) at (0,1) {}; \node[draw, circle, fill=red!20, inner sep=1pt] (Y2) at (0,-1) {}; \node[draw, circle, fill=blue!20, inner sep=1pt] (Y3) at (0,2) {}; \end{tikzpicture}, \qquad (5.3)$$

which may be seen by grafting the different splittings (5.2) onto the tree $\Y$ and coloring $\Y \to \Y$.

Forcey and Springfield (2010) defined a one-sided Hopf algebra $\Delta\text{Sym}$ on the graded vector space spanned by the faces of the simplices. Faces of the simplices correspond to subsets of $[n]$. Here is an example of the coproduct on the basis element corresponding to $\{1\} \subset [4]$, where subsets of $[n]$ are illustrated as circled subsets of the circled edgeless graph on $n$ nodes numbered left to right:

$$\Delta(\odot \cdots \odot) = \odot \otimes (\odot \cdots \odot) + (\odot \otimes (\odot \cdots \odot)) + (\odot \odot \otimes (\odot \odot \odot)) + (\odot \odot \odot \otimes (\odot \odot \odot \odot)) + (\odot \odot \odot \odot \otimes \odot)$$

Here is an example of the product

$$\odot \cdot (\odot \odot \odot) = (\odot \odot \odot \odot) + (\odot \odot \odot \odot) + (\odot \odot \odot \odot) + (\odot \odot \odot \odot \odot).$$

Let $\varphi$ denote the bijection between subsets $S = \{a, b, \dots, c\} \subset [n]$ and compositions $\varphi(S) = (a, b - a, \dots, n + 1 - c)$ of $n + 1$. Applying this bijection the indices of their fundamental bases gives a linear isomorphism $\varphi: \Delta\text{Sym} \to \mathcal{CSym} \circ \mathcal{CSym}$, which is nearly an isomorphism of one-sided Hopf algebras, as may be seen by comparing these schematics of operations in $\Delta\text{Sym}$ to formulas (5.2) and (5.3) in $\mathcal{CSym} \circ \mathcal{CSym}$.
**Theorem 5.3** *The map $\varphi$ is an isomorphism of coalgebras and an anti-isomorphism $(\varphi(a \cdot b) = \varphi(b) \cdot \varphi(a))$ of one-sided algebras.*

**Corollary 5.4** *The one-sided Hopf algebra of simplices introduced in (Forcey and Springfield (2010)) is cofree as a coalgebra.*

## References

M. Aguiar and S. Mahajan. *Monoidal functors, species and Hopf algebras*, volume 29 of CRM Monograph Series. American Mathematical Society, Providence, RI, 2010.

M. Aguiar and F. Sottile. Structure of the Malvenuto-Reutenauer Hopf algebra of permutations. *Adv. Math.*, 191(2):225–275, 2005.

M. Aguiar and F. Sottile. Structure of the Loday-Ronco Hopf algebra of trees. *J. Algebra*, 295(2):473–511, 2006.

J. M. Boardman and R. M. Vogt. *Homotopy invariant algebraic structures on topological spaces*. Lecture Notes in Mathematics, Vol. 347. Springer-Verlag, Berlin, 1973.

S. Forcey. Convex hull realizations of the multiplihedra. *Topology Appl.*, 156(2):326–347, 2008a.

S. Forcey. Quotients of the multiplihedron as categorified associahedra. *Homology, Homotopy Appl.*, 10(2):227–256, 2008b.

S. Forcey and D. Springfield. Geometric combinatorial algebras: cyclohedron and simplex, 2010. *J. Alg. Combin.*, DOI: 10.1007/s10801-010-0229-5.

S. Forcey, A. Lauve, and F. Sottile. Hopf structures on the multiplihedra. *SIAM J. Discrete Math.*, DOI: 10.1137/090776834.

E. Getzler and J. Jones. Operads, homotopy algebra and iterated integrals for double loop spaces. preprint, arXiv:hep-th/9403055.

J. A. Green, W. D. Nichols and E. J. Taft. Left Hopf algebras. *J. Algebra*, 65(2):399–411, 1980.

J.-L. Loday and M. O. Ronco. Hopf algebra of the planar binary trees. *Adv. Math.*, 139(2):293–309, 1998.

C. Malvenuto and C. Reutenauer. Duality between quasi-symmetric functions and the Solomon descent algebra. *J. Algebra*, 177(3):967–982, 1995.

S. Montgomery. *Hopf algebras and their actions on rings*, volume 82 of CBMS Regional Conference Series in Mathematics. Conference Board of the Mathematical Sciences, Washington, DC, 1993.

N. J. A. Sloane. The on-line encyclopedia of integer sequences. published electronically at www.research.att.com/~njas/sequences/.

J. Stasheff. Homotopy associativity of H-spaces. I, II. *Trans. Amer. Math. Soc.* **108** (1963), 275–292; ibid., 108:293–312, 1963.

J. Stasheff. *H-spaces from a homotopy point of view*. Lecture Notes in Mathematics, Vol. 161. Springer-Verlag, Berlin, 1970.

M. Takeuchi. Free Hopf algebras generated by coalgebras. *J. Math. Soc. Japan*, 23:561–582, 1971.