28

# Poset Hopf Monoids

Mario Sanchez

(Date: May 27, 2020)

###### Abstract.

We initiate the study of a large class of species monoids and comonoids which
come equipped with a poset structure that is compatible with the
multiplication and comultiplication maps. We show that if a monoid and a
comonoid are related through a Galois connection, then they are dual to each
other. This duality is best understood by introducing a new basis constructed
through Möbius inversion. We use this new basis to give uniform proofs for
cofreeness and calculations of primitives for the Hopf monoids of set
partitions, graphs, hypergraphs, and simplicial complexes.

Further, we show that the monoid and comonoid of a Hopf monoid are related
through a Galois connection if and only if the Hopf monoid is linearized,
commutative, and cocommutative. In these cases, we give a grouping-free
formula for the antipode in terms of an evaluation of the characteristic
polynomial of a related poset. This gives new proofs for the antipodes of the
Hopf monoids of graphs, hypergraphs, set partitions, and simplicial complexes.

University of California, Berkeley<EMAIL_ADDRESS>
The author was supported by the NSF Graduate Fellowship DGE 1752814.

##  1\. Introduction

In the last few years there has been much work on the combinatorics of Hopf
algebras. These algebraic objects abstract the notion of a family of objects
with a ”merging” operation and a ”breaking” operation. Many families of
combinatorial objects have been realized as Hopf algebras including graphs,
symmetric function families, generalized permutahedra [1], simplicial
complexes [2], pipe dreams [3], representations of towers of groups [4], etc.

There are many examples of Hopf algebras where there is a natural poset
structure on a basis which respects the algebraic structure. In these cases,
it is useful to construct a new basis using Möbius inversion. A classical
example of this is quasisymmetric function theory where we have two bases, the
monomial basis $M_{\alpha}$ and the fundamental basis $F_{\alpha}$ which are
related to each other by Möbius inversion. In a different context, Crapo and
Schmitt [5] define a new basis for the Hopf algebra of matroids using Möbius
inversion in the weak order poset of matroids. Using this new basis, the
authors give a new description for the space of primitives and a new proof of
cofreeness.

These commonalities led to the following comment by Crapo and Schimitt [5].

> Many of the Hopf algebras now of central importance in algebraic
> combinatorics share certain striking features, suggesting the existence of a
> natural, yet-to-be-identified, class of combinatorial Hopf algebras. These
> Hopf algebras are graded and cofree, each has a canonical basis consisting
> of, or indexed by, a family of (equivalence classes of) combinatorial
> objects that is equipped with a natural partial ordering, and in each case
> the algebraic structure is most clearly understood through the introduction
> of a second basis, related to the canonical one by Mobius inversion over the
> partial ordering.

This suggests two questions. First, what is this class of combinatorial Hopf
algebras? Namely, what compatibility condition between the poset on the basis
and the Hopf algebra is present in all of these examples? Second, why is
defining a new basis using Möbius inversion useful in the study of the
algebraic structure? In this paper, we answer both of these questions as well
as giving new examples of this phenomenon.

To resolve the first question, it is not sufficient to restrict ourselves to
the category of Hopf algebras. It is difficult to relate the poset structure
of the basis to the multiplication and comultiplication maps. This is because
these maps typically output linear combinations of basis elements, which
forces us to extend the poset of the basis to a poset of linear combinations;
however, it is not clear how to do this. To bypass this problem, we extend
Joyal’s theory of species to the category of posets and initiate the study of
poset monoids, poset comonoids, and poset Hopf monoids.

Define a poset species $\mathbf{F}$ to be an assignment of a poset
$\mathbf{F}[I]$ to each finite set $I$ subject to some relabelling axioms.
Then a poset monoid is a species $\mathbf{F}$ alongside an order-preserving
multiplication map
$m_{S,T}:\mathbf{F}[S]\times\mathbf{F}[T]\to\mathbf{F}[S\sqcup T]$ and a poset
comonoid is a species $\mathbf{F}$ alongside an order-preserving
comultiplication map $\Delta_{S,T}:\mathbf{F}[S\sqcup
T]\to\mathbf{F}[S]\times\mathbf{F}[T]$ both satisfying some additional
properties. Framing the examples that Crapo and Schmitt studied in this
context, reveals that in all of these examples, there is a poset monoid
$(\mathbf{F},\Box)$ and a poset comonoid $(\mathbf{F},\Delta)$ on the same
poset species where $m_{S,T}$ and $\Delta_{S,T}$ form a Galois connection.
That is,

$\Delta_{S,T}(x)\leq(y,z)\iff x\leq
y\mathbin{\text{\scalebox{0.84}{$\square$}}}_{S,T}z.$

We call this pair $(\mathbf{F},\Delta)$ and $(\mathbf{F},\Box)$ an adjoint
pair.

We can linearize a poset species $\mathbf{F}$ to obtain a vector space
$\mathbf{k}\mathbf{F}[I]=\text{span}(\\{x\in\mathbf{F}[I]\\})$. This is
equipped with the linearized basis $\\{x\in\mathbf{F}[I]\\}$. Define the
inverted basis of $\mathbf{k}\mathbf{F}[I]$ as the collection of elements

$\omega_{x}=\sum_{x\leq y}\mu(x,y)\;y$

for $x,y\in\mathbf{F}[I]$, where $\mu(-,-)$ is the Möbius function of the
poset $\mathbf{F}[I]$. Then, the answer to the second question is given by the
following theorem.

######  Theorem 1.1.

Let $(\mathbf{F},\Delta)$ be a poset comonoid and $(\mathbf{F},\Box)$ be a
poset monoid that form an adjoint pair, then

$(\mathbf{k}\mathbf{F},\Box)\cong(\mathbf{k}\mathbf{F}^{*},\Delta^{*}),$

with explicit isomorphism $x\mapsto\omega_{x}^{*}$.

In other words, if a poset monoid and a poset comonoid form an adjoint pair,
then their linearizations are dual. Further, the linearized basis of the
monoid and the inverted basis of the comonoid are dual bases. This means that
any property of the linearized basis of the monoid can be dualized into the
dual property of the inverted basis of the comonoid. Applying this to the
indecomposables of the monoid gives the following description of the
primitives of the comonoid.

######  Theorem 1.2.

Let $(\mathbf{F},\Delta)$ and $(\mathbf{F},\Box)$ be a monoid and a comonoid
that form an adjoint pair. An inverted basis element
$\omega_{x}\in\mathbf{k}\mathbf{F}[I]$ is primitive if and only if $x$ is
indecomposable in the monoid $(\mathbf{F},\Box)$. Further, the set
$\\{\omega_{x}\lvert\;\text{$x\in\mathbf{H}[I]$ and $x$ is
$\Box$-indecomposable}\\}$ is a basis for the space of primitives of
$\mathbf{k}\mathbf{F}[I]$.

Applying it to freeness and cofreeness gives the following.

######  Theorem 1.3.

Let $(\mathbf{C},\Delta)$ be a poset comonoid and $(\mathbf{C},\Box)$ be a
commutative poset monoid that form an adjoint pair. If every element in
$\mathbf{C}$ has a unique $\Box$-factorization, then
$(\mathbf{k}\mathbf{C},\Delta)$ is cofree.

With these theorems, we give new descriptions of the primitives of graphs and
set partitions as well as the first calculations of the primitives of
hypergraphs and simplcial complexes. We also give new proofs of the cofreeness
of these examples.

We obtain stronger results by focusing on the situation where the adjoint pair
$(\mathbf{F},\Delta)$ and $(\mathbf{F},\Box)$ also form a Hopf algebra
$(\mathbf{F},\Box,\Delta)$. We call these self-adjoint Hopf monoids. These
poset Hopf monoids admit a, possibly different, poset structure $\leq_{r}$
called the reassembly poset, first studied by Marberg [6], given by $x\leq y$
if and only if $y=m_{S_{1},\cdots,S_{k}}\circ\Delta_{S_{1},\cdots,S_{k}}(x)$
for some ordered set partition $S_{1}\sqcup\cdots\sqcup S_{k}=I$. We give the
following grouping-free formula for their antipodes.

######  Theorem 1.4.

Let $\mathbf{H}$ be a self-adjoint Hopf monoid and $\leq_{r}$ be the
reassembly poset. Let $[x,y]$ denote the interval from $x$ to $y$ in the
reassembly poset. Let $p_{[x,y]}(t)$ be the characteristic polynomial of this
interval. Then, the antipode for $\mathbf{H}$ is given by

$S_{I}(x)=\sum_{x\leq_{r}y}p_{[x,y]}(-1)\;y$

Applying this to graphs, hypergraphs, simplicial complexes, and set partitions
gives a new description of existing results.

Finally, we give the following classification of self-adjoint Hopf monoids.

######  Theorem 1.5.

A set Hopf monoid is self-adjoint with respect to some poset structure if and
only if it is commutative and cocommutative.

The structure of the paper is as follows. In Section 2, we extend Joyal’s
theory of species to the category of posets as well as defining poset Hopf
monoids. In Section 3, we study general results of adjoint pairs
$(\mathbf{F},\Delta)$ and $(\mathbf{F},\Box)$, such as finding a basis for the
primitives of the comonoid in terms of the monoid and giving a criteria for
when the comonoid is cofree in terms of $\Box$. We also show how to use the
Fock functor to translate our results to the category of combinatorial Hopf
algebras. In Section 4, we study self-adjoint Hopf monoids. We study
properties of the reassembly poset and use it to give a classification as the
Hopf monoids which are linearized, commutative, and cocommutative. We finish
the section by giving the formula for the antipode in terms of a
characteristic polynomial. In Section 5, we apply our theory to the examples
of set partitions, simplicial complexes, and hypergraphs.

##  2\. Poset Hopf Monoids

One of the major obstacles in trying to combine Hopf algebras with posets is
that while many Hopf algebras have a basis with a natural poset structure, it
is not clear what it means for the multiplication and comultiplication maps to
be order-preserving. This is because these two operations generally output
linear combinations of basis elements. Instead of trying to extend the poset
structure to these linear combinations, we take a different route and define
the notion of poset Hopf monoids, which allows us to bypass this problem.

###  2.1. Poset Background

We focus on posets that are locally finite, that is, given $x,z$ in the poset
$P$, the interval $[x,z]=\\{x\leq y\leq z\;\lvert\;y\in P\\}$ is finite. The
Möbius function $\mu$ of a poset $P$ is a map from intervals of $P$ to
$\mathbb{Z}$ defined recursively by

$\mu_{P}(x,y)=\left\\{\begin{array}[]{ll}1&\text{if $x=y$}\\\ -\sum_{x\leq
z<y}\mu_{P}(x,z)&\text{otherwise}.\end{array}\right.$

In this context, we have Rota’s Möbius Inversion Theorem [7] which tells us
that for two integer-valued functions, $f,g:P\to\mathbb{Z}$ we have

$f(x)=\sum_{x\leq y}g(y)\;\;\text{for all $x$}\iff g(x)=\sum_{x\leq
y}\mu(x,y)f(y)\;\;\text{for all $x$.}$

Given two posets $P,Q$, a Galois connection $f\dashv g$ is a pair of order-
preserving maps $(f,g)$ with $f:P\to Q$ and $g:Q\to P$ with the property that
for all $x\in P$ and all $y\in Q$,

$f(x)\leq_{Q}y\iff x\leq_{P}g(y).$

We say $f$ is the left-adjoint to $g$ and $g$ is the right-adjoint to $f$. An
order-preserving map has at most one left-adjoint or right-adjoint.

The main utility of Galois connections comes from the following lemma due to
Rota.

######  Lemma 2.1.

[7] If $P,Q$ are posets with $x\in P$ and $b\in Q$ and $f\dashv g$ is a Galois
connection then,

$\sum_{\begin{subarray}{c}x\leq y\\\
f(y)=b\end{subarray}}\mu_{P}(x,y)=\sum_{\begin{subarray}{c}a\leq b\\\
g(a)=x\end{subarray}}\mu_{Q}(a,b).$

Let $\mathbf{k}$ be a field of characteristic $0$ and $P$ be a poset. We call
the free vector space $\mathbf{k}P$ the linearization of $P$. This is a vector
space equipped with a basis indexed by the elements of $P$. We refer to this
basis as the linearized basis. We will abuse notation by using the same letter
to denote the elements of $P$ and the basis vectors of $\mathbf{k}P$. Define
the inverted basis by

$\omega_{x}=\omega_{x}^{P}=\sum_{x\leq y}\mu(x,y)y.$

By Möbius inversion, the set $\\{\omega_{x}\\}_{x\in P}$ is a basis of
$\mathbf{k}P$. The following lemma shows that if $f\dashv g$ is a Galois
connection between two posets $P$ and $Q$, then the image of $\omega_{x}^{P}$
under $f$ has a natural description.

######  Lemma 2.2.

Let $P$ and $Q$ be posets with a Galois connection $f\dashv g$. Let
$\omega_{x}^{P}$ be the inverted basis for $x\in P$ and $\omega_{y}^{Q}$ be
the inverted basis for $y\in Q$. Then,

$f(\omega_{x}^{P})=\sum_{a\;\lvert\;g(a)=x}\omega_{a}^{Q}$

###### Proof.

This follows from direct calculation with Rota’s lemma. We have

$\displaystyle f(\omega_{x}^{P})$ $\displaystyle=\sum_{x\leq y}\mu(x,y)f(y)$
$\displaystyle=\sum_{b\in Q}\left(\sum_{\begin{subarray}{c}x\leq y\\\
f(y)=b\end{subarray}}\mu(x,y)\right)b$ $\displaystyle=\sum_{b\in
Q}\left(\sum_{\begin{subarray}{c}a\leq b\\\
g(a)=x\end{subarray}}\mu(a,b)\right)b$

where the last equality uses Rota’s lemma. Switching the order of the sums
gives,

$\displaystyle f(\omega_{x}^{P})$
$\displaystyle=\sum_{a\;\lvert\;g(a)=x}\;\;\sum_{a\leq
b}\mu(a,b)\;b=\sum_{a\;\lvert\;g(a)=x}\omega_{a}^{Q}.$

∎

###  2.2. Poset Species

We now extend Joyal’s theory of species [8] to posets.

######  Definition 2.3.

A poset species $\mathbf{F}$ is a functor from the category of finite sets
with bijections to the category of posets that is a singleton on the empty
set. This consists of the following data.

  * •

For each finite set $I$, a poset $\mathbf{F}[I]$ called the structures of type
$F$ on label set $I$.

  * •

For each bijection $f:I\to J$ an order-preserving bijection $\mathbf{F}[f]$

$\mathbf{F}[I]\to\mathbf{F}[J],$

such for two bijections $f:I\to J$ and $g:J\to K$, we have

$\mathbf{F}[g\circ f]=\mathbf{F}[g]\circ\mathbf{F}[f],$

and $\mathbf{F}[\text{id}]=\text{id}$.

We say that $\mathbf{F}$ is connected if $|\mathbf{F}[\emptyset]|=1$.
Throughout this paper, every poset species will be assumed to be connected.

It is important to notice that for any species $F$ we have an order-preserving
action of Aut$(I)$ on $\mathbf{F}[I]$. This is called the relabelling action
on $\mathbf{F}[I]$.

######  Example 2.4.

We will follow the example of graphs throughout this paper. For a finite set
$I$, let $I\choose 2$ denote the set of distinct pairs of elements in $I$.
Define a poset species by

$\mathbf{Graphs}[I]=\left\\{G\;|\;\text{ $G=\left(I,E(G)\subset{I\choose
2}\right)$ is a simple graph on index set $I$}\right\\}.$

The poset structure on graphs is given by $H\leq G$ if and only if
$E(H)\subset E(G)$. Any bijection $f:I\to J$ induces a bijection between
$I\choose 2$ and $J\choose 2$, hence a bijection between $\mathbf{G}[I]$ and
$\mathbf{G}[J]$ that simply relabels the vertices. It is clear that this
relabelling action is order-preserving.

We also need the definition of a morphism of poset species.

######  Definition 2.5.

Let $\mathbf{F_{1}}$ and $\mathbf{F_{2}}$ be two poset species. A poset
species morphism $\alpha$ from $\mathbf{F_{1}}$ to $\mathbf{F_{2}}$ is a
natural transformation of functors. In other words, $\alpha$ is a collection
of poset maps $\alpha[I]:\mathbf{F_{1}}[I]\to\mathbf{F_{2}}[I]$ such that the
following diagram commutes

${\mathbf{F_{1}}[I]}$${\mathbf{F_{2}}[I]}$${\mathbf{F_{1}}[J]}$${\mathbf{F_{2}}[J]}$$\scriptstyle{\alpha[I]}$$\scriptstyle{\mathbf{F_{1}}[f]}$$\scriptstyle{\mathbf{F_{2}}[f]}$$\scriptstyle{\alpha[J]}$

for any two sets $I,J$ and any bijection $f:I\to J$.

A poset species isomorphism is a poset species morphism $\phi$ where each
$\phi_{I}$ is an order-preserving bijection.

We will still need the more usual variants of species.

######  Definition 2.6.

A (connected) vector space species is a functor from the category of finite
sets with bijections to vector spaces. A (connected) set species is a functor
from the category of finite sets with bijections to finite sets.

A bilinear form on a vector space species denoted by $\langle-,-\rangle$ is a
bilinear $\langle-,-\rangle_{I}$ which respects the relabeling action. The
direct sum of two vector space species $\mathbf{F}$ and $\mathbf{G}$ is given
by $\mathbf{F}\oplus\mathbf{G}[I]=\mathbf{F}[I]\oplus\mathbf{G}[I].$

More importantly, if $\mathbf{F}$ is a poset species, its linearization
$\mathbf{k}\mathbf{F}$ is a vector space species defined by
$(\mathbf{k}\mathbf{F})[I]=\mathbf{k}\mathbf{F}[I]$. A basis for a vector
species $\mathbf{F}$ is a set species $\mathbf{b}$ such that $\mathbf{b}[I]$
is a basis of $\mathbf{F}[I]$. The invertible basis of a linearized poset
species $\mathbf{k}\mathbf{F}$ is given by
$\mathbf{w}[I]=\\{\omega_{x}\\}_{x\in\mathbf{F[I]}}$.

###  2.3. Monoids, Comonoids, and Hopf Monoids

We can now define monoids and comonoids in the category of poset species. The
main difference between this and the usual theory is that all of the structure
maps are order-preserving.

######  Definition 2.7.

A (connected) poset monoid $(\mathbf{M},m)$ is a poset species equipped with a
collection of order-preserving maps

$m_{S,T}:\mathbf{M}[S]\times\mathbf{M}[T]\to\mathbf{M}[I],$

for each ordered set partition of $I$, where the poset structure on
$\mathbf{M}[S]\times\mathbf{M}[T]$ is the product poset. This operations must
satisfy the following axioms: (Naturality) Let $I$ and $J$ be two sets and
$f:I\to J$ be a bijection. Let $I=S\sqcup T$ be a decomposition and let
$f|_{S}$ and $f|_{T}$ be the restrictions of $f$ to $S$ and $T$, respectively.
This gives us a decomposition of $J=f(S)\sqcup f(T)$ and a pair of bijections
$f|_{S}:S\to f(S)$ and $f|_{T}T\to f(T)$ Then, we have the following
commutative diagram

${\mathbf{M}[S]\otimes\mathbf{M}[T]}$${\mathbf{M}[I]}$${\mathbf{M}[f(S)]\otimes\mathbf{M}[f(T)]}$${\mathbf{M}[J]}$$\scriptstyle{m_{S,T}}$$\scriptstyle{\mathbf{M}[f|_{S}]\otimes\mathbf{M}[f|_{T}]}$$\scriptstyle{\mathbf{M}[f]}$$\scriptstyle{m_{f(S),f(T)}}$

(Unitality) $\mathbf{M}[\emptyset]$ has a single element. We will denote that
element by $1$. For any $x\in\mathbf{M}[I]$ and for the two trivial
decompositions $I=I\sqcup\emptyset$ and $I=\emptyset\sqcup I$, we have

$\displaystyle 1\cdot x=x\cdot 1$ $\displaystyle=x$

(Associativity) Let $I=S\sqcup T\sqcup R$ be a decomposition of the index set
$I$. Then the following diagram commutes

${\mathbf{M}[S]\otimes\mathbf{M}[T]\otimes\mathbf{M}[R]}$${\mathbf{M}[S]\otimes\mathbf{M}[T\sqcup
R]}$${\mathbf{M}[S\sqcup
T]\otimes\mathbf{M}[R]}$${\mathbf{M}[I]}$$\scriptstyle{\text{id}\;\otimes\;m_{T,R}}$$\scriptstyle{m_{S,T}\;\otimes\;\text{id}}$$\scriptstyle{m_{S,T\sqcup
R}}$$\scriptstyle{m_{S,T\sqcup R}}$

This allows us to define a multiplication map $m_{S_{1},S_{2},\cdots,S_{k}}$
for any ordered set partition of $I$.

######  Example 2.8.

Given two graphs $G$ and $H$ on different label sets $S$ and $T$, we define
their disjoint union by $G\sqcup H=(S\sqcup T,E(G)\sqcup E(H))$. This is
order-preserving. This makes $\mathbf{Graphs}$ into a poset Hopf monoid with
$m_{S,T}(G,H)=G\sqcup H$. The unit is the empty graph
$1=(\emptyset,\emptyset)$.

A monoid homomorphism between two monoids $\mathbf{M_{1}}$ and
$\mathbf{M_{2}}$ is a poset species homomorphism $\phi$ such that

$m_{S,T}(\phi(x),\phi(y))=\phi(m_{S,T}(x,y)).$

A monoid isomorphism is a monoid homomorphism which is a poset species
isomorphism.

We also have the dual notion of a monoid.

######  Definition 2.9.

A (connected) poset comonoid111This name is somewhat misleading since a poset
comonoid is not a comonoid in the category of poset species. However, the
linearization of a poset comonoid has a natural comonoid structure in the
category of vector space comonoids. Further, every vector space comonoid which
is linearized arises in this way from a poset comonoid. $(\mathbf{C},\Delta)$
is a poset species equipped with a collection of order-preserving maps

$\Delta_{S,T}:\mathbf{C}[I]\to\mathbf{C}[S]\times\mathbf{C}[T].$

for each ordered set partition of $I$, where the poset structure on
$\mathbf{C}[S]\times\mathbf{C}[T]$ is the product poset. This operations must
satisfy the following axioms: (Naturality) Let $I$ and $J$ be two sets and
$\sigma:I\to J$ be a bijection. Let $I=S\sqcup T$ be a decomposition and let
$\sigma|_{S}$ and $\sigma|_{T}$ be the restrictions of $\sigma$ to $S$ and
$T$, respectively. Then, we have the following commutative diagrams

${\mathbf{C}[I]}$${\mathbf{C}[S]\otimes\mathbf{C}[T]}$${\mathbf{C}[J]}$${\mathbf{C}[\sigma(S)]\otimes\mathbf{C}[\sigma(T)]}$$\scriptstyle{\Delta_{S,T}}$$\scriptstyle{\mathbf{C}[\sigma]}$$\scriptstyle{\mathbf{C}[\sigma|_{T}]\otimes\mathbf{C}[\sigma|_{S}]}$$\scriptstyle{\Delta_{\sigma(S),\sigma(T)}}$

(Counitality) $\mathbf{C}[\emptyset]$ has a single element. We will denote
that element by $1$. For any $x\in\mathbf{C}[I]$ and for the two trivial
decompositions $I=I\sqcup\emptyset$ and $I=\emptyset\sqcup I$, we have

$\displaystyle\Delta_{I,\emptyset}(x)$ $\displaystyle=x\otimes 1,$
$\displaystyle\Delta_{\emptyset,I}(x)$ $\displaystyle=1\otimes x.$

(Coassociativity) Let $I=S\sqcup T\sqcup R$ be a decomposition of the index
set $I$ into three. Then the following diagram commutes

${\mathbf{C}[I]}$${\mathbf{C}[S]\otimes\mathbf{C}[T\sqcup
R]}$${\mathbf{C}[S\sqcup
T]\otimes\mathbf{C}[R]}$${\mathbf{C}[S]\otimes\mathbf{C}[T]\otimes\mathbf{C}[R]}$$\scriptstyle{\Delta_{S,T\sqcup
R}}$$\scriptstyle{\Delta_{S\sqcup
T,R}}$$\scriptstyle{\text{id}\;\otimes\;\Delta_{T,R}}$$\scriptstyle{\Delta_{S,T}\;\otimes\;\text{id}}$

A comonoid homomorphism between two comonoids $\mathbf{C_{1}}$ and
$\mathbf{C_{2}}$ is a poset species map $\phi$ such that

$\Delta_{S,T}(\phi_{I}(x))=(\phi_{S},\phi_{T})\circ(\Delta_{S,T}(x)).$

An isomorphism is an comonoid homomorphism that is a poset species
isomorphism.

######  Example 2.10.

Let $G$ be a graph on label set $I$ and $S\subset I$. Then, the restriction of
$G$ to $S$ is given by $G|S=\left(S,E(G)\cap{S\choose 2}\right)$. This gives
$\mathbf{Graph}$ the structure of a poset comonoid by

$\Delta_{S,T}(G)=\left(G|S,G|T\right).$

Since restriction is order-preserving, graphs form a poset comonoid.

######  Definition 2.11.

A poset Hopf monoid is a (connected) poset species that is a monoid and a
comonoid and has the additional axiom:

(Compatibility) Let $I=S_{1}\sqcup S_{2}$ and $I=T_{1}\sqcup T_{2}$ be two
decompositions of $I$. Let $A=S_{1}\cap T_{1}$, $B=S_{1}\cap T_{2}$,
$C=S_{2}\cap T_{1}$, and $D=S_{2}\cap T_{2}$.Then, we have the following
commutative diagram

${\textbf{H}[S_{1}]\otimes\textbf{H}[S_{2}]}$${\textbf{H}[I]}$${\textbf{H}[T_{1}]\otimes\textbf{H}[T_{2}]}$${\textbf{H}[A]\otimes\textbf{H}[B]\otimes\textbf{H}[C]\otimes\textbf{H}[D]}$${\textbf{H}[A]\otimes\textbf{H}[C]\otimes\textbf{H}[B]\otimes\textbf{H}[D]}$$\scriptstyle{m_{S_{1},S_{2}}}$$\scriptstyle{\Delta_{A,B}\;\otimes\;\Delta_{C,D}}$$\scriptstyle{\Delta_{T_{1},T_{2}}}$$\scriptstyle{\text{id}\;\otimes\;\beta\;\otimes\
\text{id}}$$\scriptstyle{m_{A,C}\;\otimes\;m_{B,D}}$

where $\beta$ is the braiding map $\beta(x,y)=(y,x)$.

A monoid is commutative if $m_{S,T}(x,y)=m_{T,S}(x,y)$. Dually, a comonoid is
cocommutative if $\Delta_{S,T}(x)=\beta_{T,S}\Delta_{T,S}(x)$, where
$\beta_{T,S}:\mathbf{C}[T]\times\mathbf{C}[S]\to\mathbf{C}[S]\times\mathbf{C}[T]$
is the map that switches factors.

We will still need the usual definitions of vector space monoids, comonoids,
and Hopf monoids as well as set monoids, comonoids, and Hopf monoids. These
are obtained by all the axioms above where $\mathbf{F}$ is a set, vector space
species and the maps are set, linear maps, respectively.

######  Definition 2.12.

The antipode of a vector space Hopf monoid $\mathbf{H}$ is the map
$S[I]:\mathbf{H}[I]\to\mathbf{H}[I]$ given by

$S[I](x)=\sum_{S_{1}\sqcup\cdots\sqcup
S_{k}}(-1)^{k}m_{S_{1},\cdots,S_{k}}\circ\Delta_{S_{1},\cdots,S_{k}}(x).$

In general this formula has a large amount of cancellation. Finding a simpler
formula of the antipode is one of the major points of study in the theory of
Hopf monoids. One reason for the interest in the antipode comes from its
connection with combinatorial reciprocity of polynomial invariants [1].

##  3\. Adjoint Pairs

We present our main definition of adjoint pairs that describes a particular
relationship between a poset monoid and a poset comonoid. We use this to
understand duality, primitives, cofreeness. We then describe how our results
descend to the category of combinatorial Hopf algebras.

###  3.1. Main Definition and Result

######  Definition 3.1.

A poset comonoid $(\mathbf{F},\Delta)$ and a poset monoid $(\mathbf{F},\Box)$
on the same poset species $\mathbf{F}$ form an adjoint pair if $\Delta_{S,T}$
and $\Box_{S,T}$ are a Galois connection for all finite sets $S$ and $T$. This
can happen in two ways. The first, denoted by $\Delta\dashv\Box$, is if for
all $x\in\mathbf{F}[I]$, $y\in\mathbf{F}[S]$, and $z\in\mathbf{F}[T]$ we have

$\Delta_{S,T}(x)\leq(y,z)\iff x\leq\Box_{S,T}(y,z),$

The second, denoted by $\Box\dashv\Delta$, is if for all $x\in\mathbf{F}[I]$,
$y\in\mathbf{F}[S]$, and $z\in\mathbf{F}[T]$

$\Box_{S,T}(x,y)\leq z\iff(x,y)\leq\Delta_{S,T}(z)$

Clearly, if we reverse the order of the poset on $\mathbf{F}$, then these two
cases are the same. However, often the combinatorics forces a particular poset
on us and reversing the order of the poset can be unnatural.

######  Example 3.2.

Let $G_{1}$ be a graph on vertex set $S$ and $G_{2}$ be a graph on vertex set
$T$. Then, define the free product of these two graphs $G_{1}\Box
G_{2}=\Box_{S,T}(G_{1},G_{2})$ by

$G_{1}\Box G_{2}=(G_{1}^{c}\sqcup G_{2}^{c})^{c},$

where $G^{c}$ denotes the complement of the graph $G$. In other words,
$G_{1}\mathbin{\text{\scalebox{0.84}{$\square$}}}G_{2}$ is the disjoint union
of $G_{1}$ and $G_{2}$ with all the edges between $S$ and $T$ added.

It is quick to verify that

$(G|S,G|T)\leq(G_{1},G_{2})\iff G\leq G_{1}\Box G_{2}.$

Thus, the comonoid of graphs $(\mathbf{Graphs},\Delta)$ and the monoid of
graphs $(\mathbf{Graphs},\Box)$ form an adjoint pair with $\Delta\dashv\Box$

This comultiplication $\Delta$ is part of a second adjoint pair. We have

$G_{1}\sqcup G_{2}\leq G\iff(G_{1},G_{2})\leq\Delta_{S,T}(G).$

This implies that the comonoid $(\mathbf{Graphs},\Delta)$ and the monoid
$(\mathbf{Graphs},m)$ form an adjoint pair with $m\dashv\Delta$.

The following simple result will be important throughout this paper.

######  Theorem 3.3.

Let $(\mathbf{F},\Delta)$ be a poset comonoid and $(\mathbf{F},\Box)$ be a
poset monoid which form an adjoint pair with $\Delta\dashv\Box$. Let
$\omega_{x}=\sum_{x\leq y}\mu(x,y)\;y$ be an inverted basis element of
$\mathbf{k}\mathbf{F}$. Then,

$\Delta_{S,T}(\omega_{x})=\sum_{\begin{subarray}{c}x_{1}\Box_{S,T}x_{2}=x\end{subarray}}\omega_{x_{1}}\otimes\omega_{x_{2}}.$

###### Proof.

We use the Galois connection $\Delta_{S,T}\dashv\Box_{S,T}$ and Lemma 2.2 to
study the comonoid structure.

By a direct application, we have

$\Delta_{S,T}(\omega_{x})=\sum_{x_{1}\mathbin{\text{\scalebox{0.84}{$\square$}}}x_{2}=x}\omega_{(x_{1},x_{2})},$

where $\omega_{(x_{1},x_{2})}$ is the inverted basis in the linearization of
the product poset
$\mathbf{k}(\mathbf{C}[S]\times\mathbf{C}[T])=\mathbf{k}\mathbf{C}[S]\otimes\mathbf{k}\mathbf{C}[T]$.
Notice,

$\displaystyle\omega_{(x_{1},x_{2})}$
$\displaystyle=\sum_{(x_{1},x_{2})\leq(y_{1},y_{2})}\mu((x_{1},x_{2}),(y_{1},y_{2}))\;y_{1}\otimes
y_{2}$
$\displaystyle=\sum_{(x_{1},x_{2})\leq(y_{1},y_{2})}\mu(x_{1},y_{1})\mu(x_{2},y_{2})y_{1}\otimes
y_{2}$ $\displaystyle=\left(\sum_{x_{1}\leq
y_{1}}\mu(x_{1},y_{1})y_{1}\right)\otimes\left(\sum_{x_{2}\leq
y_{2}}\mu(x_{2},y_{2})y_{2}\right)$
$\displaystyle=\omega_{x_{1}}\otimes\omega_{x_{2}}$

This gives us

$\Delta_{S,T}(\omega_{x})=\sum_{x_{1}\mathbin{\text{\scalebox{0.84}{$\square$}}}x_{2}}\omega_{x_{1}}\otimes\omega_{x_{2}}.$

∎

If $\Box\dashv\Delta$, then the previous theorem still holds replacing
$\omega_{x}$ by $\omega^{x}=\sum_{y\leq x}\mu(y,x)y$.

Notice that in the previous example the monoid $(\mathbf{Graphs},m)$ and the
comonoid $(\mathbf{Graphs},\Delta)$ form a Hopf monoid, that is they satisfy
the compatibility axiom, whereas the monoid $(\mathbf{Graphs},\Box)$ and the
comonoid $(\mathbf{Graphs},\Delta)$ do not form a Hopf monoid. This leads to
the following definition.

######  Definition 3.4.

A poset Hopf monoid $(\mathbf{H},m,\Delta)$ is self-adjoint if the monoid
$(\mathbf{H},m)$ and the comonoid $(\mathbf{H},\Delta)$ form an adjoint pair.

We study these objects in detail in Section 4.

###  3.2. Duality

Given a vector space species $\mathbf{F}$, its linear dual $\mathbf{F}^{*}$ is
given by $\mathbf{F}^{*}[I]=\mathbf{F}[I]^{*}$. Since duality of vector spaces
is a contravariant functor, the linear dual of a monoid has a natural comonoid
structure and vice-versa. One way of describing the dual multiplication and
comultiplications is by choosing an explicit basis. If $\mathbf{b}$ is a basis
of $\mathbf{F}$, then we can define a bilinear form $\langle-,-\rangle_{I}$ on
$\mathbf{F}[I]$ such that $\mathbf{b}[I]$ is an orthogonal basis. Using this,
we can build a dual basis $\mathbf{b}^{*}$ for $\mathbf{F}^{*}$. In this
basis, the dual comultiplication
$m_{S,T}^{*}:\mathbf{F}[I]\to\mathbf{F}[S]\otimes\mathbf{F}[T]$ is given by

$m_{S,T}^{*}(x^{*})=\sum_{\begin{subarray}{c}y\in\mathbf{b}[S]\\\
z\in\mathbf{b}[T]\end{subarray}}\langle m_{S,T}(y,z),x\rangle\quad
y^{*}\otimes z^{*}.$

Similarly, if we have a vector space comonoid $\mathbf{F}$, then on the dual
basis, the dual multiplication
$\Delta_{S,T}^{*}:\mathbf{F}[S]\otimes\mathbf{F}[T]\to\mathbf{F}[I]$ takes the
form

$\Delta_{S,T}^{*}(x^{*},y^{*})=\sum_{\langle x\otimes
y,\Delta_{S,T}(z)\rangle\not=0}\langle x\otimes y,\Delta_{S,T}(z)\rangle\quad
z^{*},$

where we extend the bilinear form to the tensor product by $\langle x\otimes
x^{\prime},y\otimes y^{\prime}\rangle=\langle x,y\rangle\cdot\langle
x^{\prime},y^{\prime}\rangle$.

We say that a vector space monoid $(\mathbf{F},m)$ and a vector space comonoid
$(\mathbf{G},\Delta)$ are dual if there is an isomorphism of monoids
$\mathbf{F}\cong\mathbf{G}^{*}$. This isomorphism can be realized by a non-
degenerate bilinear form $\langle-,-\rangle$ such that

$\langle m_{S,T}(x,y),z\rangle=\langle x\otimes y,\Delta(z)\rangle.$

A vector space Hopf monoid $(\mathbf{H},m,\Delta)$ is self-dual if there
exists an isomorphism of species $\mathbf{H}\cong\mathbf{H}^{*}$ that is
simultaneously a monoid and comonoid isomorphism. This isomorphism can be
realized as a symmetric non-degenerate bilinear form $\langle-,-\rangle_{I}$
such that

$\langle\Delta_{S,T}(x),y\otimes z\rangle=\langle x,m_{S,T}(y,z)\rangle.$

######  Definition 3.5.

If $\mathbf{F}$ is a poset species, then we can define a bilinear form
$\langle-,-\rangle$ on $\mathbf{k}\mathbf{F}$ by

$\langle x,y\rangle=\zeta(x,y)=\begin{cases}1&\text{ if $x\leq y$}\\\
0&\text{else}\end{cases}$

for $x,y\in\mathbf{F}[I]$. We call this the zeta bilinear form of
$\mathbf{F}$.

Then, if $(\mathbf{F},\Delta)$ is a poset comonoid and $(\mathbf{F},\Box)$ is
a poset monoid that form an adjoint pair with $\Delta\dashv\Box$, by the
definition of Galois connection we have

$\langle\Delta_{S,T}(x),y\otimes z\rangle=\langle x,y\Box_{S,T}z\rangle.$

Combining this with Theorem 3.3, we obtain the following result.

######  Theorem 3.6.

Let $(\mathbf{F},\Delta)$ be a poset comonoid and $(\mathbf{F},\Box)$ be a
poset monoid that form an adjoint pair with $\Delta\dashv\Box$, then
$(\mathbf{F},\Box)\cong(\mathbf{F}^{*},\Delta^{*})$ with explicit isomorphism
$x\mapsto\omega_{x}^{*}$.

One thing to notice is that for a self-adjoint poset Hopf monoid
$(\mathbf{H},m,\Delta)$ this gives an isomorphism between the monoid
$(\mathbf{H},m)$ and the monoid $(\mathbf{H}^{*},\Delta)$. Similarily, by
reversing the poset order, we have an isomorphism between
$(\mathbf{H},\Delta)$ and $(\mathbf{H}^{*},m^{*})$. This does not immediately
imply that $\mathbf{H}$ is self-dual because these two isomorphisms are not
the same species map. However, in Section 4 we see that it is still true that
every self-adjoint poset Hopf monoid is self-dual.

###  3.3. Primitives

We now turn to Crapo and Schmitt’s observation that posets seem to help
calculate primitives of Hopf algebras.

######  Definition 3.7.

Let $(\mathbf{M},m)$ be a poset monoid. An element $x\in\mathbf{M}[I]$ is
indecomposable if it is not of the form $x=m_{S,T}(y,z)$ for some $I=S\sqcup
T$ and $y\in\mathbf{M}[S]$ and $z\in\mathbf{M}[T]$. For $\mathbf{k}\mathbf{M}$
with linearized basis $\mathbf{b}$, we can define a bilinear form that makes
$\mathbf{b}$ orthonormal. Then, the subspace of indecomposables of
$\mathbf{k}\mathbf{M}[I]$ is given by the elements $x$ such that

$\langle x,m_{S,T}(y,z)\rangle=0,$

for all $I=S\sqcup T$ and $y\in\mathbf{k}\mathbf{M}[S]$ and
$z\in\mathbf{k}\mathbf{M}[T]$. This is the same as the vector space spanned by
the basis elements $x\in\mathbf{M}[I]$ which are indecomposable.

######  Definition 3.8.

Let $(\mathbf{C},\Delta)$ be a vector space comonoid. Then an element
$x\in\mathbf{C}$ is primitive if $\Delta_{S,T}(x)=0$ for all non-trivial
$I=S\sqcup T$. The subspecies of primitives of $\mathbf{C}$ is denoted by
$\mathcal{P}(\mathbf{C})$.

We now show that for an adjoint pair, the primitives of one determine the
indecomposables of the other.

######  Theorem 3.9.

Let $(\mathbf{F},\Delta)$ and $(\mathbf{F},\Box)$ be a monoid and a comonoid
that form an adjoint pair with $\Delta\dashv\Box$. An inverted basis element
$\omega_{x}\in\mathbf{k}\mathbf{F}[I]$ is primitive if and only if $x$ is
indecomposable in the monoid $(\mathbf{F},\Box)$. Further, the set
$\\{\omega_{x}\lvert\;\text{$x\in\mathbf{H}[I]$ and $x$ is
$\Box$-indecomposable}\\}$ is a basis for
$\mathcal{P}(\mathbf{k}\mathbf{F})[I]$.

###### Proof.

Let $\langle-,-\rangle$ denote the zeta bilinear form on $\mathbf{F}$. Then,
we have

$\langle\Delta(x),y\otimes z\rangle=\langle x,y\Box_{S,T}z\rangle$

for any
$x\in\mathbf{k}\mathbf{F}[I],y\in\mathbf{k}\mathbf{F}[S],z\in\mathbf{k}\mathbf{F}[T]$.
For any inverted basis element $\omega_{x}$ and any linearized basis element
$y$, we have

$\displaystyle\langle\omega_{x},y\rangle$ $\displaystyle=\sum_{x\leq
z}\mu(x,z)\zeta(z,y)$ $\displaystyle=\sum_{x\leq z\leq y}\mu(x,z)$
$\displaystyle=\begin{cases}1&\text{if $y=x$}\\\ 0&\text{else}\\\ \end{cases}$

Combining these two facts, we have that for the following expression

$\langle\Delta_{S,T}(\omega_{x}),y\otimes
z\rangle=\langle\omega_{x},y\Box_{S,T}z\rangle,$

the right-hand-side is zero for all $y$ and $z$ if and only if $x$ is
indecomposable and the left-hand-side is zero for all $y$ and $z$ if and only
if $\omega_{x}$ is primitive. This implies the result.

∎

######  Example 3.10.

For $\mathbf{Graphs}$, we have seen that $\Delta\dashv\Box$ where $\Box$ is
the free product of graphs. This means that the subspecies of primitives of
$\mathbf{Graphs}$ has a basis given by $\omega_{G}$ for graphs that are
indecomposable under the free product. With the realization that

$(G^{c}\mathbin{\text{\scalebox{0.84}{$\square$}}}H^{c})^{c}=G\sqcup H,$

we can identify these $\Box$-indecomposable graphs as the complements of
connected graphs. Thus, a basis of the primitives is given by elements of the
form

$\omega_{G}=\sum_{G\leq H}(-1)^{E(H)-E(G)}H,$

for $G$ whose complement is connected.

###  3.4. Cofreeness and Freeness

We now show why passing to the inverted basis helps proves cofreeness and
freeness.

Let $\mathbf{q}$ be a set species with the property that
$\mathbf{q}[\emptyset]=0$. The tensor species on $\mathbf{q}$ denoted by
$\mathcal{T}(\mathbf{q})$ is a vector space species given by

$\mathcal{T}(\mathbf{q})[I]=\mathbf{k}\\{(A\vDash
I,x_{1},x_{2},\cdots,x_{k})\;\lvert\;x_{i}\in\mathbf{q}[A_{i}],\\}$

where $A\vDash I$ denotes that $A$ is an ordered set partition of $I$.

The free monoid on $\mathbf{q}$ is the species $\mathcal{T}(\mathbf{q})$ with
the multiplication

$(A\vDash S,x_{1},\cdots,x_{k})\cdot(B\vDash T,y_{1},\cdots,y_{\ell})=(A\sqcup
B\vDash I,x_{1},\cdots,x_{k},y_{1},\cdots,y_{\ell}).$

We say that $S\subset I$ is an initial segment of an ordered set partition
$A\vDash I$ if there is some integer $i$ such that $(A_{1}\sqcup
A_{2}\sqcup\cdots\sqcup A_{i})=S$. In this case, we say $A|S=(A_{1}\sqcup
A_{2}\sqcup\cdots\sqcup A_{i})$ and $A/S=(A_{i+1}\sqcup\cdots\sqcup A_{k})$
Then, the free comonoid on $\mathbf{q}$ is the species
$\mathcal{T}(\mathbf{q})$ with the comultiplication map given by

$\Delta_{S,T}((A\vDash
I,x_{1},\cdots,x_{k}))=\left\\{\begin{array}[]{ll}(A|S,x_{1},\cdots,x_{i})\otimes(A/S,x_{i+1},\cdots,x_{k})&\text{if
$S$ is an initial segment of $A$}\\\ 0&\text{else}\end{array}\right.$

######  Definition 3.11.

A vector space monoid is free if for some $\mathbf{q}$ it is isomorphic to
$\mathcal{T}(\mathbf{q})$ as a monoid. A vector space comonoid is cofree if
for some $\mathbf{q}$ it is isomorphic to $\mathcal{T}(\mathbf{q})$ as a
comonoid.

A standard theorem is that a vector space comonoid is cofree if and only if
its dual monoid is free. We say that a set monoid $(\mathbf{M},\Box)$ has the
unique factorizaiton property if every element $x\in\mathbf{M}[I]$ has a
unique expression as $x=\Box_{S_{1},\cdots,S_{k}}(x_{1},\cdots,x_{k})$ for
$x_{i}$ indecomposable. Clearly, if a set monoid $(\mathbf{M},\Box)$ has the
unique factorization property, it is free.

######  Theorem 3.12.

Let $(\mathbf{C},\Delta)$ be a poset comonoid and $(\mathbf{C},\Box)$ be a
poset monoid that form an adjoint pair with $\Delta\dashv\Box$. If
$(\mathbf{C},\Box)$ has the unique factorization property, then
$(\mathbf{k}\mathbf{C},\Delta)$ is cofree.

###### Proof.

This follows from the observations above and from theorem 3.6 which says that
the dual of $(\mathbf{k}\mathbf{C},\Delta)$ is isomorphic to
$(\mathbf{k}\mathbf{C},\Box)$. ∎

There is a similar notion for (co)commutative (co)monoids. Let $\mathbf{q}$ be
a set species with $\mathbf{q}[\emptyset]$. Define a vector space species
$\mathcal{S}(\mathbf{q})$ by

$\mathcal{S}(\mathbf{q})[I]=\mathbf{k}\left\\{(A\vdash
I,\\{x_{i}\\})\;\lvert\;x_{i}\in\mathbf{q}[A_{i}]\right\\},$

where $A\vdash I$ denotes an unordered set partition of $I$. The free
commutative monoid on $\mathbf{q}$ is the monoid structure on this species
given by

$(A\vdash S,\\{x_{i}\\})\cdot(B\vdash T,\\{y_{i}\\})=(A\sqcup B\vdash
I,\\{x_{i}\\}\cup\\{y_{j}\\}).$

Say that a subset $S\subset I$ is compatible with an unordered set partition
$A\vdash I$ if $S=\bigsqcup_{i\in J}A_{i}$ for some parts $A_{i}$ of $A$. If
$S$ is compatible with $A\vdash I$, then we let $A|S$ denote the set of parts
$\\{A_{i}\\}_{i\in J}$. The free cocommutative comonoid on $\mathbf{q}$ is the
comonoid on $\mathcal{S}(\mathbf{q})$ given by

$\Delta_{S,T}((A\vdash
I,\\{x_{i}\\}))=\left\\{\begin{array}[]{ll}(A|S,\\{x_{i}\\}_{i\in
J})\otimes(A|T,\\{x_{i}\\}_{i\not\in J})&\text{if $S$ is compatible with
$A$}\\\ 0&\text{else}\end{array}\right.$

A vector space monoid is free commutative if it is isomorphic to
$\mathcal{S}(\mathbf{q})$ as a monoid and a vector space comonoid is cofree
cocommutative if it is isomorphic to $\mathcal{S}(\mathbf{q})$ as a comonoid.

A commutative set monoid $(\mathbf{M},\Box)$ has the unique unordered
factorization property if for every $x\in\mathbf{M}[I]$ there is a unique
expression (up to reordering of the parts) of $x$ as
$x=\Box_{S_{1},\cdots,S_{k}}(x_{1},\cdots,x_{k})$ where the $x_{i}$ are
indecomposable.

As before, we have the following result.

######  Theorem 3.13.

Let $(\mathbf{C},\Delta)$ be a poset comonoid and $(\mathbf{C},\Box)$ be a
commutative poset monoid that form an adjoint pair with $\Delta\dashv\Box$. If
$(\mathbf{C},\Box)$ has the unique unordered factorization property, then
$(\mathbf{k}\mathbf{C},\Delta)$ is cofree cocommutative.

######  Example 3.14.

We can now prove that the Hopf monoid of graphs is cofree cocommutative. By
the definition of the free product of graphs, we have

$(G^{c}\mathbin{\text{\scalebox{0.84}{$\square$}}}H^{c})^{c}=G\sqcup H.$

This means that if we decompose a graph $G$ into its connected components
$G=G_{1}\sqcup G_{2}\sqcup\cdots\sqcup G_{k}$ then,

$G^{c}=G_{1}^{c}\mathbin{\text{\scalebox{0.84}{$\square$}}}G_{2}^{c}\mathbin{\text{\scalebox{0.84}{$\square$}}}\cdots\mathbin{\text{\scalebox{0.84}{$\square$}}}G_{k}^{c}.$

Since every graph has a unique unordered decomposition into connected
components, we see that graphs have the unique unordered factorization
property. This tell us that $\mathbf{k}\mathbf{G}$ is cofree cocommutative.

###  3.5. Fock Functor

Crapo and Schmitt’s observation concerned Hopf algebras, not Hopf monoids. We
now show that the Fock functor allows us to transfer our method to Hopf
algebras.

Recall that a combinatorial Hopf algebra $H$ is a connected graded vector
space equipped with two linear maps $m:H\otimes H\to H$ and $\Delta:H\to
H\otimes H$ which satisfy axioms similar to those of a Hopf monoid. The
(first) Fock functor $\mathcal{F}$ is a functor from the category of Hopf
monoids to the category of Hopf algebras given by

$\mathcal{F}(\mathbf{H})=\bigoplus_{n\in\mathbf{N}}\mathbf{H}[\\{1,2,\ldots,n\\}]_{S_{n}}$

where the subscript denotes that we are passing to the $S_{n}$-coinvariants
where the action is the relabelling action of the species.

If we denote the Hopf monoid by $\mathbf{H}$ then we will denote the image of
the Fock functor by the notation $H$. Let $[x]\in H$ denote the equivalence
class of $x\in\mathbf{H}[\\{1,2,\cdots,n\\}]$ under the relabelling action.
The multiplication and comultiplication of $H$ is given by

$m([x],[y])=[x\cdot y],$

and

$\Delta([x])=\sum_{S\sqcup T=\\{1,\cdots n\\}}[\Delta_{S,T}(x)]$

The naturality axiom of Hopf monoids ensures this is well-defined.

The linearized basis of $\mathbf{H}[I]$ is mapped onto a basis of $H_{n}$ for
$|I|=n$. We call this the linearized basis of $H$. This basis has a poset
structure given by $[x]\leq[y]$ if there are representatives
$x^{\prime}\in[x]$ and $y^{\prime}\in[y]$ such that $x^{\prime}\leq
y^{\prime}$ in $\mathbf{H}[\\{1,2,\cdots,n\\}]$.

In terms of primitives, the Fock functor behaves very nicely. Recall that the
primitives of a Hopf algebra $H$ are those elements $x$ such that
$\Delta(x)=x\otimes 1+1\otimes x$.

######  Theorem 3.15.

Let $H$ be a Hopf algebra that is the image of a Hopf monoid
$(\mathbf{H},m,\Delta)$ under the Fock functor. Then the space of primitives
of $H_{n}$ is the image of the space of primitives of
$\mathbf{H}[\\{1,\cdots,n\\}]$ under the relabelling action. Further if
$(\mathbf{H},\Box)$ is a monoid that forms an adjoint pair $\Delta\dashv\Box$
with $(\mathbf{H},\Delta)$, then the space of primitives of $H$ has a basis
given by $\\{[\omega_{x}]\;\lvert\;\text{$x$ indecomposable with respect to
$\Box$}\\}$.

###### Proof.

Let $p\in\mathbf{H}[\\{1,\cdots,n\\}]$, then $p$ is primitive in the Hopf
monoid if and only if

$\Delta([p])=\sum_{S,T}[\Delta_{S,T}(p)]=\Delta_{\\{1,\cdots,n\\},\emptyset}(p)+\Delta_{\emptyset,\\{1,\cdots,n\\}}(p).$

Then, by the counitality axiom,

$\Delta([p])=[p]\otimes 1+1\otimes[p].$

Hence $p$ is primitive if and only if $[p]$ is primitive. Then this follows
from Theorem 3.9. ∎

######  Example 3.16.

The Hopf monoid of graphs $\mathbf{Graphs}$ has a poset structure given by
edge-inclusion. This induces a poset structure on the Hopf algebra
$\mathcal{F}(\mathbf{Graphs})$ of unlabelled graphs which is
$[G_{1}]\leq[G_{2}]$ if there exists a labelling such that $G_{1}\leq G_{2}$.

We have seen that the graphs that are $\Box$-indecomposable are the graphs
whose complement is connected. Let $G$ be such a graph, then the following is
a primitive of $\mathcal{F}(\mathbf{Graphs})$

$[\omega_{G}]=\sum_{G\leq G^{\prime}}(-1)^{|E(G^{\prime})-E(G)|}[G].$

where the sum is not over equivalence classes but over elements in the poset
of $\mathbf{G}[I]$

Something curious occurs here. In order to study the primitives of a Hopf
algebra using Möbius inversion, we need use the poset of the Hopf monoid. This
is

$[\omega_{x}]=\sum_{x\leq y}\mu(x,y)[y].$

This is not using the induced poset on the basis of the Hopf algebra. In the
previous example, the sum

$\sum_{[G]\leq[H]}\mu([G],[H])[H]$

using the induced poset on graphs is not a primitive element. This further
justifies the need for species.

##  4\. Self-Adjoint Hopf Monoids

We now turn our attention to the special case where a monoid $\mathbf{M}$ and
a comonoid $\mathbf{C}$ are compatible in the sense of Hopf algebras and also
form an adjoint pair. We give a full classification of these objects; they are
the linearized, commutative, and cocommutative Hopf monoids. Further, we give
a description of their antipode for these objects in terms of the
characteristic polynomial of an underlying poset.

###  4.1. Reassembly Poset

In a paper on Hopf monoid duality, Eric Marberg constructed the following
poset related to commutative and cocommutative Hopf monoids.

######  Theorem 4.1.

[6] Let $(\mathbf{H},m,\Delta)$ be a commutative and cocommutative set Hopf
monoid. Let $\leq_{r}$ be the binary relation given by

$x\leq_{r}y\iff y=m_{S_{1},\ldots,S_{k}}\circ\Delta_{S_{1},\ldots,S_{k}}(x)$

for $x,y\in\mathbf{H}[I]$ and for some set partition $S_{1}\sqcup\cdots\sqcup
S_{k}$. Then, $\leq_{r}$ is a poset on $\mathbf{H}[I]$.

Further, this poset has the following two properties.

  1. (1)

$x\leq_{r}m_{S,T}(y_{1},y_{2})$ if and only if $\Delta_{S,T}(x)=(x_{1},x_{2})$
for some $x_{1}\leq_{r}y_{1}$ and $x_{2}\leq_{r}y_{2}$.

  2. (2)

$m_{S,T}(x_{1},x_{2})\leq_{r}y$ if and only if $y=m_{S,T}(y_{1},y_{2})$ for
some $y_{1}\leq_{r}x_{1}$ and $y_{2}\leq_{r}x_{2}$.

We now show that this makes $\mathbf{H}$ into a self-adjoint poset Hopf
monoid. We call this the reassembly poset of a commutative and cocommutative
Hopf monoid.

######  Theorem 4.2.

Let $(\mathbf{H},m,\Delta)$ be a commutative and cocommutative set Hopf
monoid. Then $\mathbf{H}$ is a poset Hopf monoid with the reassembly poset
structure on $\mathbf{H}[I]$ given above. Further, it is self-adjoint with
$\Delta\dashv m$.

###### Proof.

To prove naturality, let $\gamma:I\to I$ be a set automorphism of $I$. This
induces a set map $\mathbf{H}[\gamma]:\mathbf{H}[I]\to\mathbf{H}[I]$. To show
that this map is order-preserving, let $x,y\in\mathbf{H}[I]$ with
$x\leq_{r}y$. Then,
$y=m_{S_{1},\ldots,S_{k}}\circ\Delta_{S_{1},\ldots,S_{k}}(x)$. Applying
$\mathbf{H}[\gamma]$ to both sides, we get
$\mathbf{H}[\gamma](y)=\mathbf{H}[\gamma]\circ
m_{S_{1},\ldots,S_{k}}\circ\Delta_{S_{1},\ldots,S_{k}}(x)$. By the naturality
axiom of $m$ and of $\Delta$ this gives us

$\mathbf{H}[\gamma](y)=m_{\gamma(S_{1}),\ldots,\gamma(S_{k})}\circ\Delta_{\gamma(S_{1}),\ldots\gamma(S_{k})}\circ\mathbf{H}[\gamma](x),$

hence $\mathbf{H}[\gamma](x)\leq_{r}\mathbf{H}[\gamma](y)$.

Next, we need to show that $m$ and $\Delta$ are both order-preserving. For the
multiplication, let $x_{1}\leq_{r}y_{1}$ in $\mathbf{H}[S]$ and
$x_{2}\leq_{r}y_{2}$ in $\mathbf{H}[T]$. Then, for some set partitions
$S_{1}\sqcup\cdots\sqcup S_{k}=S$ and $T_{1}\sqcup\cdots\sqcup T_{\ell}=T$,

$\displaystyle y_{1}$
$\displaystyle=m_{S_{1},\ldots,S_{k}}\circ\Delta_{S_{1},\ldots S_{k}}(x_{1})$
$\displaystyle y_{2}$
$\displaystyle=m_{T_{1},\ldots,S_{\ell}}\circ\Delta_{T_{1},\ldots,T_{\ell}}(x_{2})$

This means

$y_{1}\cdot y_{2}=m_{S_{1},\ldots,S_{k}}\circ\Delta_{S_{1},\ldots
S_{k}}(x_{1})\cdot
m_{T_{1},\ldots,T_{\ell}}\circ\Delta_{T_{1},\ldots,T_{\ell}}(x_{2}).$

The compatibility axiom of a Hopf monoid allows us to reformulate this as

$y_{1}\cdot
y_{2}=m_{X_{1},\ldots,X_{m}}\circ\Delta_{X_{1},\ldots,X_{m}}(x_{1}\cdot
x_{2}),$

for some other set partition $X_{1}\sqcup\cdots\sqcup X_{m}=I$. This shows
that $m$ is order-preserving. A similar argument can be made for the
comultiplication map $\Delta$. Therefore, $\mathbf{H}$ is a poset Hopf monoid.

We now show that $\Delta\dashv m$. In other words,

$\Delta_{S,T}(x)\leq_{r}(y,z)\iff x\leq_{r}m_{S,T}(y,z)$

where the poset on the left-hand-side is the product poset. This is just a
rewording of property (1) in the previous theorem by Marberg. ∎

######  Example 4.3.

The set Hopf monoid of graphs $\mathbf{Graphs}$ is commutative and
cocommutative. This means that the previous theorem gives a poset structure on
$\mathbf{Graphs}[I]$ where $G\leq_{r}H$ if and only if
$H=G|_{S_{1}}\sqcup\cdots\sqcup G|_{S_{k}}$ for some set partitions
$S_{1}\sqcup\cdots\sqcup S_{k}=I$.

This is best interpreted in terms of flats. Recall that
$H\in\mathbf{Graphs}[I]$ is a flat of $G\in\mathbf{Graphs}[I]$ if for any edge
$e\in E(G)\backslash E(H)$, the graph $E(H)\cup e$ has the same number of
components as $H$. Alternatively, if $C$ is a connected component of $H$ with
vertex set $S$, then $H|_{S}=G|_{S}$. From this second definition, we see that
if $H$ is a flat of $G$ and $S_{1},\cdots,S_{k}$ are the vertex sets of the
connected components of $G$, then $H=G|_{S_{1}}\sqcup\cdots\sqcup G|_{S_{k}}$,
so $G\leq_{r}H$. Conversely, if $G\leq_{r}H$, then $G$ is a flat of $H$.

Geometrically, given a graph $G\in\mathbf{Graphs}[I]$, the graphic hyperplane
arrangement is the arrangement of hyperplanes $\\{x_{i}=x_{j}\\}$ for
$(i,j)\in E(G)$. The intersection lattice of this arrangement is isomorphic to
the poset of flats of $G$ under reverse edge inclusion. This means that if
$\emptyset$ denotes the empty graph, then the interval $[G,\emptyset]$ in the
poset $\mathbf{Graphs}[I]$ is isomorphic to the intersection lattice of the
hyperplane arrangement of $G$. Further, the interval $[G,H]$ in the reassembly
poset can be interpreted as the set of all flats of $G$ containing $H$. Thus
this poset is isomorphic to the poset $[G/H,\emptyset]$ where $G/H$ is the
graph obtained by contracting $H$ in $G$.

###  4.2. Classification of Self-Adjoint Hopf Monoids

We now prove the converse to the previous theorem. We show that every self-
adjoint Hopf monoid is commutative and cocommutative.

We begin with a straight-forward extension of a result of Zelevinsky [4] on
Hopf algebras to the Hopf monoid case.

######  Lemma 4.4.

Let $\mathbf{H}$ be a self-adjoint poset Hopf monoid. Let $\mathbf{d}$ be the
subspecies of $\mathbf{k}\mathbf{H}$ where
$\mathbf{d}[I]=\\{x\in\mathbf{k}\mathbf{H}[I]\;\lvert\;x=y\cdot z\;\text{for
some y,z}\\}$. Let $\mathbf{p}$ be the subspecies of primitives of
$\mathbf{H}$. Then,

$\mathbf{H}=\mathbf{p}\oplus\mathbf{d}.$

###### Proof.

Since $\mathbf{H}$ is a self-adjoint Hopf monoid, the zeta bilinear form
$\langle-,-\rangle$ satisfies

$\langle m_{S,T}(x,y),z\rangle=\langle x\otimes y,\Delta_{S,T}(z)\rangle.$

We calculate the (left)-orthogonal complement to $\mathbf{d}$. An element $z$
is orthogonal to $\mathbf{d}$ if and only if for all $S\sqcup T$ and
$x\in\mathbf{H}[S]$, $y\in\mathbf{H}[T]$ we have

$0=\langle m_{S,T}(x,y),z\rangle=\langle x\otimes y,\Delta(z)\rangle.$

By non-degeneracy of the zeta bilinear form, the right-hand side is zero for
all $y\otimes z$ if and only if $\Delta_{S,T}(z)=0$. In other words, the
orthogonal complement of $\mathbf{d}$ is $\mathbf{p}$. We are not done since
the bilinear form is non-symmetric. To finish, we need to show that the
bilinear form is non-degenerate when it is restricted to
$\mathbf{d}^{\perp}=\mathbf{p}$.

To do this, recall that a basis of $\mathbf{p}[I]$ is given by elements of the
form $\omega_{x}$ for certain $x$. Since the zeta bilinear form on these basis
elements is given by $\langle\omega_{x},\omega_{y}\rangle=\mu(x,y)$. This
means that the matrix of the bilinear form restricted to $\mathbf{p}$ is
triangular, hence invertible. This means that
$\mathbf{H}=\mathbf{p}\oplus\mathbf{d}$. ∎

######  Lemma 4.5.

Let $\mathbf{H}$ be a self-adjoint poset Hopf monoid. Then,
$\mathbf{k}\mathbf{H}$ is commutative and cocommutative.

###### Proof.

It suffices to show that the commutator

$[x,y]_{I}=m_{S,T}(x,y)-m_{T,S}(y,x)=0$

for all elements $x,y$ and decompositions $I=S\sqcup T$. This would imply that
$\mathbf{k}\mathbf{H}$ is commutative and self-duality would give that it is
also cocommutative.

We proceed by induction on the size of $I$. The base case is when
$I=\emptyset$. By our assumption that $\mathbf{k}\mathbf{H}=\mathbf{k}$, we
have that the bracket is zero.

Now suppose that we have proven that $[-,-]_{J}=0$ for all $J$ of cardinality
smaller than $n$. Let $I$ be a set of cardinality $n$. Let
$\mathbf{d}[I]=\mathbf{k}\\{x\in\mathbf{k}\mathbf{H}[I]\;\lvert\;x=y\cdot
z\\}$. By definition, $[x,y]_{I}$ is an element in $\mathbf{d}[I]$. So, if we
show that $[x,y]_{I}$ is also primitive, then by the previous lemma it must be
$0$. Suppose $x\in{H}[S]$ and $y\in{H}[T]$.

$\displaystyle\Delta_{S^{\prime},T^{\prime}}([x,y]_{I})$
$\displaystyle=\Delta_{S^{\prime},T^{\prime}}(m_{S,T}(x,y)-m_{T,S}(y,x))$
$\displaystyle=[\Delta_{S\cap S^{\prime},S\cap T^{\prime}}(x),\Delta_{T\cap
S^{\prime},T\cap S^{\prime}}(y)]$ $\displaystyle=[x|_{S\cap
S^{\prime}},y|_{T\cap S^{\prime}}]\otimes[x/_{S\cap S^{\prime}},y/_{T\cap
S^{\prime}}]$

where we explicitly use the compatibility axiom of Hopf monoids. Notice that
as long as our decomposition $I=S^{\prime},T^{\prime}$ is non-trivial, then
the inductive hypothesis gives us that this bracket is zero. Therefore,
$[x,y]_{I}$ is in $\mathbf{p}[I]$ and $\mathbf{d}[I]$, which implies that it
is $0$. ∎

We have now proved the following classification of self-adjoint Hopf monoids.

######  Theorem 4.6.

A set Hopf monoid is self-adjoint with respect to some poset structure if and
only if it is commutative and cocommutative.

###  4.3. Antipode

We now describe the antipode of a self-adjoint Hopf monoid with the reassembly
poset. First, some additional properties of this poset.

######  Lemma 4.7.

Let $\mathbf{H}$ be a self-adjoint Hopf monoid equipped with the reassembly
poset. Let $x\in\mathbf{H}[S]$ and $y\in\mathbf{H}[T]$ with $I=S\sqcup T$.
Then, $\omega_{x}\cdot\omega_{y}=\omega_{x\cdot y}$.

###### Proof.

The left-hand-side is

$\displaystyle\omega_{x}\cdot\omega_{y}$
$\displaystyle=\sum_{\begin{subarray}{c}x\leq_{r}z_{1}\\\
y\leq_{r}z_{2}\end{subarray}}\mu_{\mathbf{H}[S]}(x,z_{1})\cdot\mu_{\mathbf{H}[T]}(y,z_{2})z_{1}\cdot
z_{2}$
$\displaystyle=\sum_{(x,y)\leq_{r}(z_{1},z_{2})}\mu_{\mathbf{H}[S]\times\mathbf{H}[T]}((x,y),(z_{1},z_{2}))z_{1}\cdot
z_{2},$

where $\mathbf{H}[S]\times\mathbf{H}[T]$ is the product poset. The right-hand-
side is given by

$\omega_{x\cdot y}=\sum_{x\cdot y\leq_{r}z}\mu_{\mathbf{H}[I]}(x\cdot y,z)z.$

Property (2) of Theorem 4.1 implies that if $x\cdot y\leq_{r}z$, then there is
a $z_{1}\in\mathbf{H}[S]$ and a $z_{2}\in\mathbf{H}[T]$ such that
$(x,y)\leq_{r}(z_{1},z_{2})$. Further, it means that the intervals $[x\cdot
y,z]_{\mathbf{H}[I]}$ and
$[(x,y),(z_{1},z_{2})]_{\mathbf{H}[S]\times\mathbf{H}[T]}$ are isomorphic and
therefore have the same Möbius number. This implies that the two sums above
are the same. ∎

Since a self-adjoint Hopf monoid is commutative and cocommutative, we have the
following extension of the Cartier-Milnor-Moore Theorem to Hopf monoids first
proven by Stover.

######  Theorem 4.8.

[9] Let $\mathbf{H}$ be a commutative and cocommutative Hopf monoid and let
$\mathcal{P}(\mathbf{H})$ be it’s species of primitives. Then,

$\mathbf{H}\cong\mathbf{S}(\mathcal{P}(\mathbf{H})).$

In particular, $\mathbf{H}$ is free commutative, free cocommutative, and self-
dual.

In our case, we know that a basis of primitives is given by
$\omega_{x}=\sum_{x\leq_{r}y}$ for $x$ indecomposable. Theorem 4.8 tells us
that this basis is a free generating set. This implies that every element
$x\in\mathbf{H}[I]$ has a unique unordered factorization $x=x_{1}\cdots x_{k}$
into indecomposables, because if an element $x$ had two factorizations
$x=x_{1}\cdots x_{k}=x_{1}^{\prime}\cdots x_{\ell}^{\prime}$, then
$\omega_{x}$ would have two factorizations in the free generating set. This
means that reassembly poset is a graded by the function $\ell(x)$ which gives
the number of terms in the unique factorization of $x$.

Recall that for a graded poset $P$ we can define the characteristic polynomial
$p_{[x,y]}(t)$ of an interval $[x,y]$ as $p_{[x,y]}(t)=\sum_{x\leq z\leq
y}\mu(x,z)t^{\ell(z)}$.

######  Theorem 4.9.

Let $\mathbf{H}$ be a self-adjoint Hopf monoid with the reassembly poset
structure and let $p_{[x,y]}(t)$ denote the characteristic polynomial of the
interval $[x,y]$ in $\mathbf{H}$ for some $x,y\in\mathbf{H}[I]$. Then,

$S_{I}(x)=\sum_{x\leq_{r}y}p_{[x,y]}(-1)\;y.$

###### Proof.

We prove this by computing $S_{I}$ on the inverted basis and then using Möbius
inversion. Towards this, let $\omega_{x}$ be an inverted basis element. Then,

$\displaystyle S(\omega_{x})$
$\displaystyle=\sum_{\begin{subarray}{c}S_{1}\sqcup\cdots\sqcup S_{k}=I\\\
S_{i}\not=\emptyset\end{subarray}}(-1)^{k}m_{S_{1},\ldots,S_{k}}\circ\Delta_{S_{1},\ldots,S_{k}}(\omega_{x})$
$\displaystyle=\sum_{\begin{subarray}{c}S_{1}\sqcup\cdots\sqcup S_{k}=I\\\
S_{i}\not=\emptyset\end{subarray}}\sum_{\begin{subarray}{c}x_{1},\ldots,x_{k}\\\
m_{S_{1},\ldots,S_{k}}(x_{1},\ldots,x_{k})=x\end{subarray}}(-1)^{k}\omega_{x_{1}}\cdots\omega_{x_{k}}$

The second step follows from Theorem 3.3. The previous lemma simplifies this
to the following.

$\displaystyle S(\omega_{x})$
$\displaystyle=\omega^{x}\sum_{\begin{subarray}{c}S_{1}\sqcup\cdots\sqcup
S_{k}=I\\\
S_{i}\not=\emptyset\end{subarray}}\sum_{\begin{subarray}{c}x_{1},\ldots,x_{k}\\\
m_{S_{1},\ldots,S_{k}}(x_{1},\ldots,x_{k})=x\end{subarray}}(-1)^{k}$

Since $x$ has a unique factorization into some irreducible elements
$y_{1},\ldots,y_{k}$, every other factorization $x=x_{1}\cdot\cdot\cdot x_{m}$
will have the property that the $x_{i}$ are products of the $y_{i}$ such that
each $y_{i}$ appears in exactly one $x_{i}$. In other words, the factorization
of $x$ are in bijection with ordered set partitions of the set
$\\{y_{1},\cdots,y_{k}\\}$. Then, this sum is the rank-generating function of
the lattice of ordered set partitions on this set evaluated at $-1$. This is

$S(\omega_{x})=(-1)^{\ell(x)}\omega_{x}$

By Möbius inversion, we have

$\displaystyle S_{I}(x)$ $\displaystyle=\sum_{x\leq_{r}z}S_{I}(\omega_{z})$
$\displaystyle=\sum_{x\leq_{r}z}(-1)^{\ell(y)}\omega_{z}$

Let $\langle y\rangle\;S_{I}$ denote the coefficient of $y$ in the expansion
of $S_{I}$ in the basis $\mathbf{b}$. Then,

$\langle y\rangle\;S_{I}(x)=\sum_{x\leq_{r}z\leq_{r}y}\mu(x,z)(-1)^{\ell(z)}$

Since the poset is graded by $\ell$, this sum is exactly $p_{[x,y]}(-1)$. ∎

######  Example 4.10.

We have seen that the reassembly poset on graphs is the poset where
$G\leq_{r}H$ if and only if $H$ is a flat of $G$. We also saw that $[G,H]$ is
isomorphic to the interval $[G/H,\emptyset]$, which is isomorphic to
intersection lattice of the graphical arrangement of $G/H$. In this situation,
the evaluation of the characteristic polynomial at $(-1)$ has a beautiful
interpretation due to Zaslavsky. He showed that for a hyperplane arrangement
$\mathcal{A}$ with intersection lattice $L(\mathcal{A})$, we have

$p_{L(\mathcal{A})}(-1)=(-1)^{r(L(\mathcal{A}))}c(\mathcal{A}),$

where $c(\mathcal{A})$ is the number of connected regions of the complement of
$\mathcal{A}$ and $r(L(\mathcal{A}))$ is the rank of the poset, see for
example [10]. For a graphical hyperplane arrangement, it is well-known that
the number of connected regions in it’s complement is the number of acyclic
orientations. Also, the rank of the intersection lattice of $G/H$ is
$|I|-rk(H)$ where the rank of $H$ is the size of the largest spanning tree pf
$H$. Combining all this with the previous theorem, we obtain the following
description of the antipode for $\mathbf{Graphs}$.

$S_{I}(G)=\sum_{\text{$H$ flat of $G$}}(-1)^{|I|-rk(H)}acyc(G/H)H,$

where $acyc(G/H)$ is the number of acyclic orientations of $G/H$. This agrees
with the previous calculations of this antipode [1].

##  5\. Examples

In this section we give quick examples of our theory to Hopf monoids. We show
how to calculate primitives and prove cofreeness for various Hopf monoids and
algebras. For the self-adjoint Hopf monoids we calculate the antipode.

We have omitted the example of matroids since rereading Crapo and Schmitt’s
paper [5] with our ideas in mind makes it clear how it fits into our
framework.

###  5.1. Set Partitions and Symmetric Functions

A set partition of $I$ is an unordered collection of non-empty subsets
$\pi=\\{\pi_{1},\pi_{2},\cdots,\pi_{k}\\}$ that are mutually disjoint such
that $I=\pi_{1}\sqcup\pi_{2}\sqcup\cdots\sqcup\pi_{k}$. These sets $\pi_{i}$
are called the parts of $\pi$ and $\ell(\pi)$ is the number of blocks of
$\pi$. We say that $\pi\leq\tau$ if $\tau$ refines $\pi$, that is each part of
$\tau$ is fully contained in some part of $\pi$. This relation gives the set
of partitions of $I$ the structure of a lattice.

If $\pi$ is a partition if $S$ and $\tau$ is a partition of $T$ with $S\cap
T=\emptyset$, define their union $\pi\cup\tau$ to be the partition with parts
$\\{\pi_{1},\cdots,\pi_{k},\tau_{1},\cdots,\tau_{\ell}\\}$. If $\pi$ is a
partition of $I$ and $S\subset I$, define the restriction $\pi|_{S}$ to be the
partition $\\{\pi_{1}\cap S,\pi_{2}\cap S,\cdots,\pi_{k}\cap S\\}$ where we
remove the empty sets that appear in these intersections.

######  Definition 5.1.

The poset Hopf monoid of set partitions is the Hopf monoid on the poset
species

$\mathbf{Par}[I]=\text{Lattice of partitions of $I$}$

where with structure maps

$m_{S,T}(\pi,\tau)=\pi\cup\tau\quad\quad\text{and}\quad\quad\Delta_{S,T}(\pi)=(\pi|_{S},\pi|_{T})$

It is not hard to see that

$(\pi|_{S},\pi|_{T})\leq(\tau_{1},\tau_{2})\iff\pi\leq\tau_{1}\cup\tau_{2}.$

So partitions forms a self-adjoint Hopf monoid. This immediately tells us that
this Hopf monoid is free commutative, free cocommutative self-dual, by Theorem
4.8. We can also calculate the primitives. Let $\pi_{I}$ denote the partition
with one part $I$, which is the only indecomposable of $\mathbf{Par}[I]$. Then
the primitives are scalings of

$\omega_{\pi_{I}}=\sum_{\tau\in\mathbf{Par}[I]}\mu(\pi_{I},\tau)\tau.$

More explicitly,

$\omega_{\pi_{I}}=\sum_{\tau\in\mathbf{Par}[I]}\left(\prod_{\tau_{i}}(-1)^{|\tau_{i}|-1}(|\tau_{i}|-1)!\right)\tau=\sum_{\tau\in\mathbf{Par}[I]}(-1)^{|I|-\ell(\tau)}\left(\prod_{\tau_{i}}(|\tau_{i}|-1)!\right)\tau.$

Applying the first Fock functor to this Hopf monoid gives us a Hopf algebra of
set partitions up to relabelling. This is the same as the Hopf algebra of
integer partitions $Par=\bigoplus_{n}Par_{n}$ where the vector space $Par_{n}$
is spanned by the integer partitions of $n$. The poset structure induced on
the basis of integer partitions is the refinement of integer partitions. For a
given set partition $\pi$, let $\lambda(\pi)$ denote its underlying integer
partition which is given by the size of the parts. By our results in the Fock
functor section, a basis of the primitives of $Par$ is given by

$\omega_{(n)}=\sum_{\tau\in\mathbf{Par}[I]}\mu(\pi_{I},\tau)\lambda(\tau).$

A result of Marcelo Aguiar and Federico Ardila [1] is that we have an
isomorphism between the Hopf algebra of partitions $Par$ and the Hopf algebra
of symmetric functions $\Lambda$ given by

$n!\;(n)\mapsto h_{n},$

where $(n)$ is the integer partition of $n$ with one part and $h_{n}$ is the
homogeneous basis of $\Lambda$.

We can combine this isomorphism with our description of primitives of Theorem
3.9 to get a description of the primitives of $\Lambda$. We get a basis of the
primitives of $\Lambda$ given by

$\omega_{h_{n}}=\sum_{\tau\in\mathbf{Par}[{1,2,\cdots,n}]}\mu(\pi_{i},\tau)$

Since this a graded basis for the space of primitives, standard symmetric
function theory tells us that these $\omega_{h_{n}}$ coincide with the power
sums $p_{n}$ up to a factor. This recovers a classical result by Doubilet [11]
that expresses the power sum functions in terms of Möbius inversion of the
homogeneous basis over the set partition lattice.

######  Theorem 5.2.

[11] The power sum symmetric functions $p_{n}\in\Lambda$ are given by

$p_{n}=\frac{1}{\mu(\hat{0},\hat{1})}\sum_{\Phi}\mu(\hat{0},\Phi)h_{\lambda(\Phi)},$

where the sum is over the set partition lattice.

Notice that we did not have to guess that the lattice of set partitions was
the important lattice for this result. Everything came from general machinery.

Using Theorem 4.9, we can also calculate the antipode of partitions. First,
notice that the reassembly poset $\leq_{r}$ of partitions is the same as the
poset above. Namely, $\pi\leq_{r}\tau$ if $\tau$ refines $\pi$. Then, the
antipode is

$S_{I}(\pi)=\sum_{\pi\leq_{r}\tau}p_{[\pi,\tau]}(-1)\tau$

The characteristic polynomial of the set partition lattice is well-studied. A
calculation is given in Example 3.10.4 in Stanely’s book [10]. He shows,

$\chi_{\mathbf{Par}[I]}(t)=t(t-1)(t-2)\cdot\cdot\cdot(t-n+1).$

Which means,

$\chi_{\mathbf{Par}[I](-1)}=(-1)^{n}n!$

Further, we know that any interval in the set partition lattice $[\pi,\tau]$
is a product of smaller set partition lattices. Suppose that
$\pi=\\{B_{1},\cdots,B_{\ell(\pi)}\\}$ and that in the refinement $\tau$ each
block $B_{i}$ is partitioned into $\lambda_{i}$ blocks. If $\Pi_{\lambda_{i}}$
denotes the set partition lattice of a set of size $\lambda_{i}$. Then,

$[\pi,\tau]\cong\Pi_{\lambda_{1}}\times\cdots\times\Pi_{\lambda_{\ell(\pi)}}$

Combining these two facts alongside the realization that
$\lambda_{1}+\cdots+\lambda_{\ell(\pi)}=\ell(\tau)$ shows that

$p_{[\pi,\tau]}(-1)=(-1)^{\ell(\tau)}\prod_{B_{i}\in\pi}\lambda_{i}!\;.$

Thus, we have

$S(\pi)=\sum_{\pi\leq_{r}\tau}(-1)^{\ell(\tau)}\left(\prod_{B_{i}\in\pi}\lambda_{i}!\right)\tau.$

This result agrees with Aguiar and Ardila’s calculation in [1].

###  5.2. Hypergraphs and Simplicial Complexes

Throughout the examples, we have already encountered the Hopf monoid of
graphs. We calculated its subspecies of primitives, proved that it is cofree,
and proved self-duality. We now extend these results to hypergraphs and to the
submonoid of simplicial complexes.

A hypergraph $\mathcal{G}$ on vertex set $I$ is the tuple $(I,E)$ where
$E\subset 2^{I}$ that does not contain the empty set or any singleton. The
elements in $E$ are called hyperedges.We can define a species by

$\mathbf{HG}[I]=\\{\mathcal{G}\;\lvert\;\text{$\mathcal{G}$ is a hypergraph on
vertex set $I$}\\}.$

Define a poset structure by $\mathcal{H}\leq\mathcal{G}$ if and only if
$E(\mathcal{H})\subset E(\mathcal{G})$. This makes $\mathbf{HG}$ a poset
species. If $\mathcal{G}_{1}$ is a hypergraph on $S$ and $\mathcal{G}_{2}$ is
a hypergraph on $T$, define their product by

$m_{S,T}(\mathcal{G}_{1},\mathcal{G}_{2})=(S\sqcup T,E(\mathcal{G}_{1})\cup
E(\mathcal{G}_{2})).$

If $\mathcal{G}$ is a hypergraph on $I$ and $S\subset I$, then the restriction
of $\mathcal{G}$ to $S$, denoted by $\mathcal{G}|S$ is the hypergraph

$\mathcal{G}|S=\left(S,\\{U\in E(\mathcal{G})\;\lvert\;U\subset
2^{S}\\}\right).$

Then

######  Lemma 5.3.

The poset species $\mathbf{HG}$ equipped with the multiplication $m_{S,T}$
above and comultiplication
$\Delta_{S,T}:\mathcal{G}\mapsto(\mathcal{G}|S,\mathcal{G}|T)$ is a poset Hopf
monoid.

###### Proof.

It is proved in [2] that this forms a Hopf monoid. The only remaining work is
to show that the multiplication and comultiplication maps are order-
preserving. Since disjoint union and restriction are both order-preserving
operations, the lemma follows. ∎

This Hopf monoid has been studied in [2] and [12]. Note that this Hopf monoid
is different from the Hopf monoid of hypergraphic polytopes studied by Aguiar
and Ardila in [1] where they allow hypergraphs to have repeated hyperedges.

Let $\mathcal{K}(S,T)$ be the complete bipartite hypergraph on vertex sets $S$
and $T$. This graph contains all hyperedges which are not strictly contained
in $2^{S}$ and $2^{T}$. Define the free product on hypergraphs by

$\mathcal{G}_{1}\mathbin{\text{\scalebox{0.84}{$\square$}}}\mathcal{G}_{2}=\left(I,E(\mathcal{G}_{1})\sqcup
E(\mathcal{G}_{2})\cup E(\mathcal{K}(S,T))\right).$

Just as in the case of graphs, we have

######  Lemma 5.4.

The poset comonoid $(\mathbf{HG},\Delta)$ and the poset monoid
$(\mathbf{HG},\Box)$ form an adjoint pair with $\Delta_{S,T}\dashv\Box_{S,T}$.

Given a hypergraph $\mathcal{G}=(I,E)$, the complement of $\mathcal{G}$ is
given by

$\mathcal{G}^{c}=(I,\\{U\subset 2^{I}\;\lvert\;U\not\in E(\mathcal{G})\text{
and $|U|\geq 2$}\\})$

A hypergraph is connected if it is not the disjoint union of two other
hypergraphs. As with graphs, we have

$(\mathcal{G}_{1}^{c}\mathbin{\text{\scalebox{0.84}{$\square$}}}\mathcal{G}_{2}^{c})^{c}=\mathcal{G}_{1}\sqcup\mathcal{G}_{2}.$

This means that if $\mathcal{G}$ is the complement of a connected graph, then
it is $\mathbin{\text{\scalebox{0.84}{$\square$}}}$-indecomposable. Theorem
3.9 and Theorem 3.15 imply the following theorem.

######  Proposition 5.5.

The primitive species $\mathcal{P}(\mathbf{k}\mathbf{HG})[I]$ of hypergraphs
has a basis given by

$\omega_{\mathcal{G}}=\sum_{\mathcal{G}\leq\mathcal{H}}\mu(\mathcal{G},\mathcal{H})\mathcal{H},$

for hypergraphs $\mathcal{G}$ on $I$ whose complement is connected.

Further, the subspace of primitives of the Hopf algebra of hypergraphs
$\mathcal{F}(\mathbf{k}\mathbf{HG})$ has a basis given by

$[\omega_{\mathcal{G}}]=\sum_{\mathcal{G}\leq\mathcal{H}}\mu(\mathcal{G},\mathcal{H})[\mathcal{H}],$

for hypergraphs $[\mathcal{G}]$ whose complement is connected.

Moreover, if
$\mathcal{G}_{1}\in\mathbf{HG}[S],\mathcal{G}_{2}\in\mathbf{HG}[T]$ and
$\mathcal{H}\in\mathbf{HG}[I]$ with $I=S\sqcup T$, then we also have

$m_{S,T}(\mathcal{G}_{1},\mathcal{G}_{2})\leq\mathcal{H}\iff(\mathcal{G}_{1},\mathcal{G}_{2})\leq(\mathcal{H}|S,\mathcal{H}|T).$

This means that $m_{S,T}\dashv\Delta_{S,T}$. So, $\mathbf{HG}$ is self-adjoint
and hence commutative and cocommutative. Theorem 4.8 implies the following
result.

######  Proposition 5.6.

The Hopf monoid of hypergraphs $\mathbf{k}\mathbf{HG}$ is free commutative,
free cocommutative, and self-dual.

Since this Hopf monoid is self-adjoint, Theorem 4.9 gives the following
grouping-free formula for this Hopf monoid.

######  Theorem 5.7.

Let $\leq_{r}$ be the reassembly poset on the Hopf monoid of hypergraphs
$\mathbf{HG}$. Let $p_{[\mathcal{H},\mathcal{G}]}$ denote the characteristic
polynomial of the interval $[\mathcal{H},\mathcal{G}]$ in reassembly poset.
Then,

$S_{I}(\mathcal{G})=\sum_{\mathcal{G}\leq_{r}\mathcal{H}}p_{[\mathcal{G},\mathcal{H}]}(-1)\;\mathcal{H}.$

This gives a new interpretation for the antipode of this Hopf monoid given by
Benedetti, Bergeron, and Machacek [12]. Notice that a hypergraph $\mathcal{G}$
is less than $\mathcal{G}$ in the reassembly poset if and only if there exists
an ordered set partition $S_{1}\sqcup\cdots\sqcup S_{k}$ of $I$ such that
$\mathcal{H}=\prod\mathcal{G}|_{S_{i}}$. In the language of [12], this means
that $\mathcal{H}$ is a flat of $\mathcal{G}$.

One commonly studied submonoid of $\mathbf{HG}$ is the Hopf monoid of
simplicial complexes defined in [2]. A simplicial complex on ground set $I$ is
a collection of subsets $\Gamma\subset 2^{I}$ that is downward closed; that
is, if $Y\subset X\subset I$ and $X\in\Gamma$, then $Y\in\Gamma$. If $S\subset
I$, then we can define the restriction of $\Gamma$ to $S$ by
$\Gamma|S=\Gamma\cap 2^{S}$. Given a simplicial complex $\Gamma_{1}$ on ground
set $S$ and a simplicial complex $\Gamma_{2}$ on ground set $T$, define their
disjoint union by $\Gamma_{1}\sqcup\Gamma_{2}=\\{A\subset
I\;\lvert\;A\in\Gamma_{1}\text{ or }A\in\Gamma_{2}$}. This defines a Hopf
monoid $\mathbf{SC}[I]=\\{\text{simplicial complexes with label set $I$}\\}$
with structure maps

$m_{S,T}(\Gamma_{1},\Gamma_{2})=\Gamma_{1}\sqcup\Gamma_{2}\;,$

and

$\Delta_{S,T}(\Gamma)=(\Gamma|S,\Gamma|T).$

This comes with a natural poset structure where $\Gamma\leq\Phi$ if and only
if every $X\in\Gamma$ is in $\Phi$.

Since a simplicial complex can be interpreted as a special type of hypergraph,
we see that $\mathbf{SC}$ embeds as a Hopf monoid into $\mathbf{HG}$. We have
to be careful since this does not immediately imply that every result
descends. To see this, notice that the free product of two simplicial
complexes (viewed as hypergraphs) is no longer a simplicial complex. However,
we still have that $m_{S,T}\dashv\Delta_{S,T}$. That is

$\Gamma_{1}\sqcup\Gamma_{2}\leq\Phi\iff(\Gamma_{1},\Gamma_{2})\leq(\Phi|S,\Phi|T).$

This means that $\mathbf{SC}$ is self-adjoint. Thus, we have the following
result.

######  Theorem 5.8.

The Hopf monoid of simplicial complexes $\mathbf{k}\mathbf{SC}$ is free
commutative, free cocommutative, and self-dual.

Further, we calculate the space of primitives. The simplicial complexes that
are $m$-indecomposable are those that can not be written as a disjoint union
of other simplicial complexes. These are called the connected simplicial
complexes. Since $m_{S,T}\dashv\Delta_{S,T}$, we need to reverse the poset
order to apply Theorem 3.9. This gives

######  Proposition 5.9.

The space of primitives $\mathcal{P}(\mathbf{k}\mathbf{SC})[I]$ has a basis
given by

$\omega^{\Gamma}=\sum_{\Phi\leq\Gamma}\mu(\Phi,\Gamma)\Gamma,$

for connected $\Gamma\in\mathbf{SC}[I]$.

The reassembly poset $\leq_{r}$ on $\mathbf{SC}$ is easier to describe that
that of $\mathbf{HG}$. For a simplicial complex $\Gamma$, let $\Gamma^{(1)}$
denote its 1-skeleton; that is, the set of subsets of size 2 in $\Gamma$. This
forms a graph. For any flat $F\subset\Gamma^{(1)}$, let
$C_{1}\sqcup\cdots\sqcup C_{k}$ denote the connected components of the flat.
Then, define $\Gamma(F)=\Gamma|_{C_{1}}\sqcup\cdots\sqcup\Gamma|_{C_{k}}$.

######  Lemma 5.10.

In the reassembly poset, $\Gamma\leq_{r}\Phi$ if and only if $\Phi=\Gamma(F)$
for some flat $F\subset\Gamma^{(1)}$. Therefore, the interval
$[\Gamma,\emptyset]$ in the reassembly poset is isomorphic to the interval
$[\Gamma^{(1)},\emptyset]$ in the reassembly poset of graphs.

###### Proof.

First, if $\Phi=\Gamma(F)$, then using the set partition
$S_{1}\sqcup\cdots\sqcup S_{k}$ induced by the connected components
$C_{1}\sqcup\cdots\sqcup C_{k}$ of $F$, we clearly see that
$\Gamma(F)=\Gamma|_{C_{1}}\sqcup\cdots\sqcup\Gamma|_{C_{k}}=m_{S_{1},\cdots,S_{k}}\circ\Delta_{S_{1},\cdots,S_{k}}(\Gamma)$.

In the other direction, for any set partition $S_{1}\sqcup\cdots\sqcup
S_{k}=I$, we need to show that
$(\Gamma|_{S_{1}})^{(1)}\sqcup\cdots\sqcup(\Gamma|_{S_{k}})^{(1)}$ is a flat
of $\Gamma^{(1)}$. Since simplical complexes are downward closed, we have that
$\Gamma|_{S_{1}}^{(1)}=\Gamma^{(1)}|S_{1}$. Therefore,
$(\Gamma|_{S_{1}})^{(1)}\sqcup\cdots\sqcup(\Gamma|_{S_{k}})^{(1)}=\Gamma^{(1)}_{S_{1}}\sqcup\cdots\sqcup\Gamma^{(1)}_{S_{k}}$.
Thus this is indeed a flat of $\Gamma^{(1)}$. ∎

The previous Lemma combined with our Theorem 4.9 gives us a new proof of the
following result by Benedetti, Hallam, and Machacek [2].

######  Theorem 5.11.

[2] Let $acyc(G)$ denote the number of acyclic orientations of a graph. Then,
the antipode for $\mathbf{SC}$ is given by

$S_{I}(\Gamma)=\sum_{\begin{subarray}{c}F\subset\Gamma^{(1)}\\\
\text{flat}\end{subarray}}(-1)^{|I|-rk(F)}acyc(\Gamma^{(1)}/F)\;\Gamma(F).$

## References

  * [1] M. Aguiar and F. Ardila, “Hopf monoids and generalized permutahedra,” ArXiv e-prints, Sept. 2017, 1709.07504.
  * [2] C. Benedetti, J. Hallam, and J. Machacek, “Combinatorial Hopf algebras of simplicial complexes,” SIAM Journal on Discrete Mathematics, vol. 30, no. 3, pp. 1737–1757, 2016, 1505.04458.
  * [3] N. Bergeron, C. Ceballos, and V. Pilaud, “Hopf dreams,” ArXiv e-prints, July 2018, 1807.03044.
  * [4] A. Zelevinsky, Representations of Finite Classical Groups: A Hopf Algebra Approach.  Lecture Notes in Mathematics, Springer Berlin Heidelberg, 2006.
  * [5] W. Crapo, H. nd Schmitt, “Primitive elements in the matroid-minor Hopf algebra,” Journal of Algebraic Combinatorics, vol. 28, 12 2005, 0511033\.
  * [6] E. Marberg, “Strong Forms of Linearization for Hopf Monoids in Species,” J. Algebraic Comb., vol. 42, pp. 391–428, Sept. 2015, 1312.5074.
  * [7] G. Rota, “On the foundations of combinatorial theory I. Theory of Möbius functions,” Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, vol. 2, no. 4, pp. 340–368, 1964.
  * [8] A. Joyal, “Une théorie combinatoire des séries formelles,” Advances in Mathematics, vol. 42, no. 1, pp. 1 – 82, 1981.
  * [9] C. R. Stover, “The equivalence of certain categories of twisted Lie and Hopf algebras over a commutative ring,” Journal of Pure and Applied Algebra, vol. 86, no. 3, pp. 289 – 326, 1993.
  * [10] R. P. Stanley, Enumerative Combinatorics: Volume 1.  New York, NY, USA: Cambridge University Press, 2nd ed., 2011.
  * [11] P. Doubilet, “On the Foundations of Combinatorial Theory. VII: Symmetric Functions through the Theory of Distribution and Occupancy,” Studies in Applied Mathematics, vol. 51, no. 4, pp. 377–396.
  * [12] C. Benedetti, N. Bergeron, and J. Machacek, “Hypergraphic polytopes: combinatorial properties and antipode,” Journal of Combinatorics, vol. 10, 12 2017.