%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[revision]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{91}
\addbibresource{91.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}
\newtheorem{Thm}{Theorem}[section]
\newtheorem{theorem}[Thm]{Theorem}
\newtheorem{lemma}[Thm]{Lemma}
\newtheorem{corollary}[Thm]{Corollary}
\newtheorem{proposition}[Thm]{Proposition}
\newtheorem{example}[Thm]{Example}
\newtheorem{definition}[Thm]{Definition}
\newtheorem{remark}[Thm]{Remark}
\usepackage{pict2e}

\newcommand{\Sy}{\mathfrak{S}}
\newcommand{\boxm}{\; \Box \;}
\newcommand{\cofree}{\mathcal{T}^\vee(\mbf{p})}
\newcommand{\mathbbX}{\mathbb X}
\newcommand{\mbf}{\mathbf}
\newcommand{\checkX}{\check{\mathbb X}}
\newcommand{\openX}{\check{\mathbb X}^\circ}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\Ji}{J_i}
\newcommand{\Jip}{J_{i\ \widehat{i+1}}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\tb}[1]{\textbf{#1}}
\newcommand{\GP}{\mathbf{GP}}
\newcommand{\defeq}{\vcentcolon=}

\newcommand{\Osq}{\mathbin{\text{\scalebox{.84}{$\square$}}}}
\newcommand{\Sch}{\mathbf{Sch}}
\newcommand{\ol}[1]{\overline{\mbf{#1}}}


\usepackage{lipsum}

%% define your title in the usual way
\title{M\"obius inversion as Duality for Hopf Monoids}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Mario Sanchez\thanks{\href{mailto:Mario_Sanchez@berkeley.edu}{Mario\_Sanchez@berkeley.edu} Mario Sanchez was supported by the NSF Graduate Fellowship DGE 1752814}}

%% then use \addressmark to match authors to institutions here
\address{Department of Mathematics, University of California, Berkeley, CA 94720-38}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We study a large class of Hopf monoids which come equipped with a poset that is compatible with the Hopf structure. In these cases, we can understand duality in terms of M\"obius inversion, and . We use this to give uniform proofs for cofreeness and calculations of primitives for graphs, set partitions, matroids, and scheduling problems. Moreover, we find that the M\"obius function defines an important inner product for these Hopf monoids.}

%% put your French abstract here, or comment this out if you don't have one
%%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Hopf monoids, M\"obius inversion, Symmetric functions, Scheduling problems, Matroids}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want


%% note the \printbibliography command at the end of the file which goes with these biblatex commands

%\addbibresource{ref.bib}



\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Introduction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

The study of Hopf algebras in combinatorics revolves around forming an algebraic structure of combinatorial families that encodes a "merging" operation and a "breaking" operation, and then using structure theorems to better understand the operations. In the last few years, Hopf structures have been found for many families.

A common approach to proving results has come from using posets and M\"obius inversion to construct a new basis which behaves more nicely with respect to the Hopf structure. The standard example comes from quasisymmetric function theory, where we have the relationship between the Gessel fundamental basis $F_{\alpha}$ and the monomial basis $M_{\alpha}$ by $M_{\alpha} = \sum_{\alpha \leq \beta} \mu(\alpha,\beta) F_{\beta}$.

In other contexts, Aguiar and Sottile \cite{MRHopf} define a new basis for the Hopf algebra of permutations using M\"obius inversion in the weak order of the symmetric group. In matroids, Crapo and Schmitt \cite{PrimMatroids}, define a basis for matroids using M\"obius inversion in the weak order of matroids. In all these examples, the new basis allows for a quick calculation of the primitives and proofs of cofreeness.

We give a general framework for when this approach works. In order to make the connection to posets more explicit, we move away from Hopf algebras to Hopf monoids in the category of poset species. Then, we define a coadjoint Hopf monoid $(\mbf{H},m,\Delta)$ as a poset Hopf monoid in which the comultiplication is part of a Galois connection. This means that for every $I = S \sqcup T$, we have a second multiplication map
 \[ \Box_{S,T}: \mbf{H}[S] \times \mbf{H}[T] \to \mbf{H}[I],\]
which satisfies
 \[ \Delta_{S,T}(x) \leq (y_1,y_2) \iff x \leq y_1 \Osq y_2 .\]
Our main theorem is that the map
 \[ x \mapsto \omega_x^* = \left (\sum_{x \leq y} \mu(x,y) y \right)^*\]
gives an isomorphism between the monoid $(\mbf{H},\Box)$ and the dual monoid $(\mbf{H},\Delta^*)$.

In many examples of interest, this $\Box$ map is much simpler than the comultiplication map. This gives us a new approach for studying primitives and cofreeness. We apply this to graphs, symmetric functions, matroids, and scheduling problems, providing unified proofs of known results and new applications.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Poset Hopf Monoids
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Poset Hopf Monoids}

\subsection{Poset Background}

In this paper, every poset will be a locally finite. That is, we have that every interval $[x,y] = \{ z \; \lvert \; x \leq z \leq y\}$ is finite. This allow us to apply Rota's theory of M\"obius functions \cite{Rota1}. Recursively, for a poset $P$, define
 \[ \mu_P(x,y) = \left \{ \begin{array}{ll}
                1 & \text{if $x = y$} \\
                \displaystyle -\sum_{x \leq z < y}\mu_P(x,z) & \text{otherwise}
                \end{array} \right .\]
In this context, we have the M\"obius inversion theorem which tells us that for two functions to a field, $f,g:P \to \mbf{k}$ we have
 \[ f(x) = \sum_{x \leq y} g(y) \iff g(x) = \sum_{x \leq y} \mu(x,y) f(y).\]
 
The main tool we use is the theory of Galois connections. If $P$ and $Q$ are two posets, then a pair of order-preserving maps $f:P \to Q$ and $g: Q \to P$ is a \textbf{Galois connection}, denoted by $f \dashv g$, if for all $x \in P$ and $y \in Q$
 \[f(x) \leq_Q y \iff x \leq_P g(y). \]

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

\begin{lemma}\cite{Rota1} If $P,Q$ are posets with $x \in P$ and $b \in Q$ and $f \dashv g$ is a Galois connection then,
\[ \sum_{\substack{x \leq y \\ f(y) = b}} \mu_P(x,y) = \sum_{\substack{a \leq b \\ g(a) = x}} \mu_Q(a,b).\]
\end{lemma}

\subsection{Poset Hopf Monoids}
The traditional approach to "merging" and "breaking" operations on a combinatorial family is to form a Hopf algebra. However, since a Hopf algebra by definition is a vector space where the multiplication and comultiplication map generally output linear combinations of elements, it is not clear what it might mean for a Hopf algebra to be compatible with a poset. For this reason, we need to pass to Hopf monoids.

A poset species $\mbf{F}$ is a functor from the category of finite sets with bijections to the category of posets with poset morphisms. This means that for each finite set $I$ we have a poset $\mbf{F}[I]$ and for each bijection $I \to J$ we have an order-preserving bijection $\mbf{F}[I] \to \mbf{F}[J]$. Notice that this gives us an order-preserving action of $S_I = \text{Aut}[I]$ on $\mbf{F}[I]$. We typically think of elements in $\mbf{F}[I]$ as labelled combinatorial objects and the maps $\mbf{F}[I] \to \mbf{F}[J]$ as relabellings.

A \textbf{poset monoid} $(\mbf{M},m)$ is a poset species $\mbf{M}$ equipped with a unital, associative, and order-preserving map $m_{S,T}: \mbf{H}[S] \times \mbf{H}[T] \to \mbf{H}[I]$, and a \textbf{poset comonoid} $(\mbf{C},\Delta)$ is a poset species $\mbf{C}$ equipped with a counital, coassociative, and order-preserving map $\Delta_{S,T}: \mbf{H}[I] \to \mbf{H}[S] \times \mbf{H}[T]$. A \textbf{poset Hopf monoid} $(\mbf{H},m,\Delta)$ is a monoid and a comonoid satisfying some additional axioms.

For a more in-depth study, see \cite{fedHopf} or \cite{hopfBook}.

\begin{example} An example that we will carry throughout this paper is given by simple graphs. Define
 \[ \mbf{G}[I] = \{\text{Simple graphs on vertex set $I$}\}.\]
This forms a poset species where we use the relation $G \leq H$ when $E(H) \subset E(G)$. Notice that this relation is the opposite of the usual relation; this convention will make the other examples simpler.

We have structure maps
 \[m_{S,T}(H_1,H_2) = H_1 \sqcup H_2 \quad \quad \text{and} \quad \quad \Delta_{S,T}(G) = (G|S, G|T), \]
where $\sqcup$ is the disjoint union of graphs and $G|S$ is $G$ restricted to vertex set $S$. These operations are order-preserving. Thus, this is a poset Hopf monoid.
\end{example}

\subsection{Linearization and the Inverted Basis}

Let $\mbf{k}$ be a field of characteristic $0$. Given a poset $P$, we can define its linearization $\mbf{k}P$ to be the free vector space over $\mbf{k}$ on the set $P$. We define the \textbf{inverted basis} for $\mbf{k}P$ to be
 \[ \omega_x = \sum_{x \leq y} \mu(x,y) \cdot y \quad \text{for $x \in P$}.\]
By M\"obius inversion, this is a basis and $x = \sum_{x \leq y} \omega_y$.

A quick application of Rota's lemma on Galois connections gives the following.

\begin{lemma} 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_{y \in g^{-1}(x)} \omega_y^Q\]
\end{lemma}



Many poset theoretic properties can be extended to poset Hopf monoids. For example, we can define the \textbf{linearization} of a poset Hopf monoid by $\ol{H}[I] = \mbf{k} \mbf{H}[I]$. This comes equipped with the basis given by elements of the poset $\mbf{H}[I]$. We call this the \textbf{canonical basis}. We can define the \textbf{inverted basis} by the procedure above. Notice that we get a vector space Hopf structure on the linearization given by $m_{S,T}: \ol{H}[S] \otimes \ol{H}[T] \to \ol{H}[I]$ and $\Delta_{S,T}: \ol{H}[I] \to \ol{H}[S] \otimes \ol{H}[T].$

Now that we have linearized Hopf monoids, we can define the dual by taking $\ol{H}^*[I] = \text{Hom}(\ol{H}[I], \mbf{k)}$. Since duality is a contravariant functor, this turns a monoid into a comonoid and vice-versa. If $x \in \mbf{H}[I]$, we let $x^*$ denote the indicator function of $x$. For linearized Hopf monoids, we have the following descriptions of the dual maps,
\[
m_{S,T}^*(x^*) = \sum_{m_{S,T}(x_1,x_2) = x} x_1 \otimes x_2 \quad \text{and} \quad
\Delta^*_{S,T}(x_1^*,x_2^*) = \sum_{x \; : \; \Delta(x) = x_1 \otimes x_2} x \]

Any bilinear form $\langle -, - \rangle_I: \ol{H}[I] \otimes \ol{H}[I] \to \mbf{k}$, gives a (not necessarily Hopf) map $\ol{H}[I] \to \ol{H}^*[I]$, by $x \mapsto \langle x, - \rangle$. 

\begin{example} For graphs, the inverted basis is given by
 \[\omega_G = \sum_{G \leq H} (-1)^{|E(G) - E(H)|} H. \]
\end{example}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Mobius Inversion as Duality
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{M\"obius inversion as Duality}
\subsection{Adjoint and Coadjoint Hopf monoids}
Many of the Hopf monoids that appear in the study of combinatorics have a structure that is much stronger than just being a poset Hopf monoid. In particular, the multiplication or comultiplication map is part of a Galois connection. 

\begin{definition} A \textbf{coadjoint comonoid} is a poset comonoid equipped with a family of maps $\Box_{S,T}$ such that $\Delta_{S,T} \dashv \Box_{S,T}$ is a Galois connection for all $S,T$. We denote $\Box_{S,T}(x \otimes y)$ by $x \Box y$ where the set partition is left implicit.

An \textbf{adjoint monoid} is a poset monoid equipped with a family of maps $\nabla_{S,T}$ such that $\nabla_{S,T} \dashv m_{S,T}$ is a Galois connection for all $S,T$.

A \textbf{self-adjoint} Hopf monoid is one that is both adjoint and coadjoint with $\Delta_{S,T} \dashv m_{S,T}$.
\end{definition}

\begin{example} The Hopf monoid of graphs is self-adjoint. That is we have
 \[\Delta_{S,T}(G) \leq (H_1,H_2) \iff G \leq H_1 \sqcup H_2. \]
\end{example}

In this abstract, we focus on the story where the comultiplication is part of a Galois connection; although, everything here can be dualized. 

Some simple calculations using the comonoid axioms and the Galois connection $\Delta_{S,T} \dashv \Box_{S,T}$ gives us the following proposition.

\begin{proposition} Let $\mbf{C}$ be a coadjoint comonoid. Then poset species $\mbf{C}$ equipped with $\Box$ is a monoid.
\end{proposition}

The main theorem of our paper tells us that for coadjoint Hopf monoids, the $\Box$-map gives us a better description of the dual.

\begin{theorem} Let $\mbf{C}$ be a coadjoint monoid. Then its dual $\mbf{C}^*$ is isomorphic to the monoid $\mbf{M} = (\mbf{C}, \Box)$ by the map $\phi: \mbf{M} \to \mbf{C}^*$ given by $x \mapsto \omega_{x}^*$.
This means that $\Delta_{S, T}^*(\omega_{x_1}^*, \omega_{x_2}^*) = \omega_{x_1 \Osq x_2}^*$.
\end{theorem}
We also have the dual theorem.

\begin{theorem} Let $\mbf{M}$ be a adjoint monoid, then its dual $\mbf{M}$ is isomorphic to the comonoid $\mbf{C} = (\mbf{M}, \nabla)$ by the map $\phi:\mbf{C} \to \mbf{M}$ given by
 \[  x \mapsto (\omega^x)^*,\]
where $\omega^x = \sum_{y \leq x} \mu(y,x) y$.
\end{theorem}

If $\mbf{H}$ is a self-adjoint Hopf monoid, then the previous two theorems seem to imply that $\mbf{H}$ is self-dual; however, this is not the case because the two maps given in the theorems are not the same species morphism. With a little work, we can still prove that $\mbf{H}$ is self-dual.

\begin{corollary}\label{cor::selfad} A linearized self-adjoint Hopf monoid $\ol{H}$ is self-dual.
\end{corollary}

\begin{example} This gives us a proof that the Hopf monoid of graphs is self-dual.
\end{example}

A very interesting consequence of this theorem is that for a coadjoint comonoid $\mbf{C}$ the non-degenerate bilinear form $\langle -, -\rangle_I: \overline{\mbf{C}}[I] \otimes \overline{\mbf{C}}[I] \to \mbf{k}$ given by
 \[ \langle x, \omega_y \rangle = \delta_{x,y}, \]
for a canonical basis element $x$ and an inverted basis element $\omega_y$, is the form that gives the duality $\ol{C} \cong \ol{C}^*$. On the inverted basis it takes the form
 \[\langle \omega_x, \omega_y \rangle = \mu(x,y). \]
On the canonical basis, it takes the form,
\[ \langle x, y \rangle = \zeta(y,x) \]
which is the zeta function that is $1$ if $y \leq x$ and $0$ otherwise. The change-of-basis sends the zeta function to the M\"obius function. This suggests a connection to convolution in the incidence algebra.

This also gives us the following corollary regarding linearization.

\begin{corollary} If $\mbf{C}$ is a linearized coadjoint poset Hopf monoid, then $\mbf{C^*}$ is a linearized poset monoid. Dually, if $\mbf{M}$ is a linearized adjoint poset Hopf monoid, then $\mbf{M^*}$ is a linearized poset comonoid.
\end{corollary}

This means that for these special monoids and comonoids, we can study their duals without having to pass to their linearization.

\subsection{Primitives}
Just as in the theory of algebras, a fruitful approach to comonoids is to look at the simplest elements - those that do not break into other elements. With this in mind, we say that an element of $x \in \ol{H}[I]$ is primitive if for any $I = S \sqcup T$ with $S$ and $T$ non-trivial, we have $\Delta_{S,T}(x) = 0$. 

Say that an element $x \in \mbf{H}[I]$ is $\Box$-irreducible if there is no non-trivial $I = S\sqcup T$ and $x_1 \in \mbf{H}[S]$ and $x_2 \in \mbf{H}[T]$ with $x = x_1 \Osq x_2$. Then, our main theorem gives

\begin{theorem}\label{prim} Let $\mbf{H}$ be a coadjoint Hopf monoid. Then a basis for the primitives in $\ol{H}[I]$ is given by $\{\omega_{x} \; : \; \text{$x$ is $\Box$-irreducible} \}.$
\end{theorem}

\begin{example} For the Hopf monoid of graphs, the primitives are given by $\omega_G$ for $\Box$-irreducible graphs. Since $\Box$ is given by union, the $\Box$-irreducibles are the connected graphs.
\end{example}

\subsection{Freeness}
Another useful concept in algebra is that of freeness. A free monoid is a monoid where every element $x \in \mbf{H}[I]$ has a unique factorization into indecomposable elements. That is, there is a unique ordered set partition $S_1 \sqcup \cdots \sqcup S_k$ and indecomposable elements $x_i \in \mbf{H}[S_i]$ such that $x = m_{S_1,S_2,\cdots,S_k}(x_1,x_2, \cdots, x_k)$. The dual notion is a cofree comonoid which, roughly, is a comonoid where every element is a word of primitives and the comultiplication is deconcatenation. For a rigorous introduction see \cite{hopfBook}.

Just as freeness is useful for constructing algebraic maps, cofreeness is useful for constructing coalgebraic maps; however, it is in general not easy to prove that a comonoid is cofree due to the fact that primitives are usually complicated linear combinations of objects. In our case, we have a nice description of the dual multiplication by the $\Box$ map. A standard theorem tells us that the comonoid is cofree if and only if its dual monoid is free. This gives us
\begin{theorem}\label{cofree} A coadjoint comonoid $\mbf{C}$ is cofree if and only if every element has a unique $\Box$-factorization.
\end{theorem}

\subsection{Fock Functor}
Most of the literature concerns Hopf algebras, not Hopf monoids. We show that the Fock functor allows us to transfer our method to Hopf algebras.

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}(\mbf{H}) = \bigoplus_{n \in \mbf{N}} \mbf{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 $\mbf{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 \mbf{H}[\{1,2,\cdots,n\}]$ under the relabelling action. The multiplication and comultiplication of $H$ is given by
 \[m([x],[y]) = [x \cdot y], \quad \quad \text{and} \quad \quad \Delta([x]) = \sum_{S \sqcup T = \{1,\cdots n \}} [\Delta_{S,T}(x)]\]
 The linearized basis of $\mbf{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' \in [x]$ and $y' \in [y]$ such that $x' \leq y'$ in $\mbf{H}[\{1,2,\cdots,n\}]$.

In terms of primitives, the Fock functor behave 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$
\begin{theorem}\label{thm:fock}
Let $H$ be a Hopf algebra that is the image of a Hopf monoid $\mbf{H}$ under the Fock functor. Then space of primitives of $H_n$ is the image of the space of primitives of $\mbf{H}[\{1,\cdots,n\}]$ under the relabelling action. Further if $\mbf{H}$ is a coadjoint Hopf monoid, then the space of primitives of $H$ has a basis given by $\{ [\omega_x] \; \lvert \; \text{$x$ indecomposable with respect to $\Box$} \}$.
\end{theorem}
 


\begin{example} The Hopf monoid of graphs $\mbf{G}$ has a poset structure on $\mbf{G}[I]$ by edge-inclusion. This induces a poset structure on the Hopf algebra $Gr$ unlabelled graphs which is $[G_1] \leq [G_2]$ if there exists a labelling such that $G_1 \leq G_2$ in the Hopf monoid poset.
 
We have seen that the graphs that are $\Box$-indecomposable are the graphs which are connected. Let $[G]$ be such a graph, then the following is a primitive of $Gr$
  \[ [\omega_{G}] = \sum_{G' \leq G} (-1)^{|E(G) - E(G')|} [G']. \]
where the sum is not over equivalence classes but over elements in the poset of $\mbf{G}[I]$
 \end{example}

Something curious occurs here. In order to study the primitives of a Hopf algebra using M\"obius inversion, we need use the poset of the Hopf monoid. This is
 \[ [\omega_x] = \sum_{x \leq y} \mu(x,y) [y].\]
This is \textbf{not} using the poset of the Hopf algebra. This further justifies the need for Hopf monoids.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Examples
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Examples}

There are many examples of adjoint/coadjoint Hopf monoids. We choose a small subset based on the amount of background knowledge needed. 

\subsection{Set Partitions}

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

\begin{definition} The \textbf{poset Hopf monoid of set partitions} is the Hopf monoid on the poset species
 \[ \mbf{Par}[I] = \text{Lattice of partitions of $I$}\]
 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)\]
\end{definition}

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. By \cref{prim} the space of primitives is spanned by the inverted basis elements indexed by indecomposable partitions. Let $\pi_I$ denote the partition with one part $I$, which is the only indecomposable of $\mbf{Par}[I]$. Then the primitives are of the form


\[ \omega_{\pi_I} = \sum_{\tau \in \mbf{Par}[I]} \mu(\pi_I,\tau) \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 primitives of $Par$ is given by
\[ \omega_{(n)} = \sum_{\tau \in \mbf{Par}[I]} \mu(\pi_I,\tau) \lambda(\tau) .\]


A result of Marcelo Aguiar and Federico Ardila \cite{fedHopf} gives an isomorphism between the Hopf algebra of partitions $Par$ and the Hopf algebra of symmetric functions $\Lambda$ given by
 \[ (n) \mapsto n! \; 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 Hopf algebras by M\"obius inversion 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 \mbf{Par}[I]} \mu(\pi_I, \tau) \left (\prod_i |\lambda(\tau)_i|!\right )h_{\lambda(\tau)} \]

Since this is a graded basis for the space of primitives, standard symmetric function theory says that these $\omega_{h_n}$ coincide with the power sums $p_n$ up to a factor.
This recovers a classical result by Doubilet \cite{Doubilet} that expresses the power sum functions in terms of the homogeneous functions using M\"obius inversion over the lattice of set partitions. Notice that we did not have to guess that the lattice of set partitions was the important lattice in this M\"obius inversion. Everything came from general machinery. Since the M\"obius function for the partition lattice is known, we can use this to get explicit descriptions of the primitives.

This same story holds for most other variants of symmetric functions such as NSYM, QSYM, NCSYM, and NCQSYM, by studying the appropriate Hopf monoid. 

\subsection{Matroids}
A Hopf algebraic result which inspired the study of coadjoint Hopf monoids is Crapo and Schmitt's calculations of primitives for matroids \cite{PrimMatroids}. 

Define the poset species of matroids by
 \[ \mbf{Mat}[I] = \{\text{Matroids on ground set $I$} \},\]
where we say that $M \leq N$ if every basis of $M$ is a basis of $N$. This is known as the weak order of matroids (of the same rank). We can define structure maps by
 \[m_{S,T}(M_1,M_2) = M_1 \oplus M_2 \quad \quad \text{and} \quad \quad \Delta_{S,T}(M) = (M|_S, M/_S).\]
These maps are order-preserving and thus matroids form a poset Hopf monoid. Crapo and Schmitt proved (in a different language) that this is a coadjoint Hopf monoid with $\Box$ being the free product of matroids. Then, they used some linear algebraic methods to prove that there is a basis of the primitives by $\Box$-indecomposables. 
Furthermore, they proved that matroids have a unique $\Box$-factorization, and then used special properties of matroids to prove that this means that the comonoid of matroids is cofree. 

Our method replaces matroid-specific arguments by general poset-theoretic facts.


\subsection{Scheduling Problems}

We now use the methods of this paper to study the Hopf algebra of scheduling problems. Scheduling problems were first defined by Caroline Klivans and Felix Breuer \cite{Sch} without the Hopf structure.

Scheduling problems on an index set $I$ are defined to be boolean formulas up to logical equivalence using the symbols $\wedge, \vee, =,\not=, \neg$ with atoms of the form $x_i \leq x_j$ for $i,j \in I$. Then, a solution of a scheduling problem is an assignment of each $x_i$ to a positive integer such that the statement is true in the usual order of integers. Geometrically, we can assign to each scheduling problem the collection of cones of the braid arrangement on which the problem is true. In order to study the solutions of scheduling problems, we can define a Hopf monoid of scheduling problems as follows.

\begin{definition} The species of scheduling problems $\mbf{Sch}$ is given by
    \[ \mbf{Sch}[I] = \{ \text{All scheduling problems on variables $x_i$ for $i \in I$} \}.\]
Given a bijection $f: I \to J$, we define $\mbf{Sch}[f]$ to be the natural relabeling map of the subscripts.
\end{definition}

Define structure maps by
 \[ m_{S,T}(\phi, \psi) = \phi \wedge \psi \quad \quad \text{and} \quad \quad \Delta_{S,T}(\phi) = \phi|_S \otimes \phi/S,\]
where $\phi|_S$ is obtained by setting every variable in the complement of $S$ to $\infty$ with the convention that $\infty < \infty$ is true, and $\phi/S$ is obtained by setting every variable in $S$ to $-\infty$ with the convention that $-\infty < -\infty$. 

\begin{example} Given a graph $G$ with vertex set $I$, we build a scheduling problem by
 \[ \phi_G = \bigwedge_{(i,j) \in \text{E}(G)} x_i \not = x_j.\]
Then, solutions of this problem correspond to proper colorings of the graph $G$.

If we have two graphs $H_1$ and $H_2$ on vertex sets $S$ and $T$, respectively, we can directly see
 \[\phi_{H_1} \cdot \phi_{H_2} = \phi_{H_1 \sqcup H_2}. \]
Moreover,
 \[ \Delta_{S,T}(\phi_G) = \left \{ \begin{array}{ll}
        \phi_{G|S} \otimes \phi_{G|T} & \text{if $G|S$ and $G|T$ are edge-disjoint subgraphs} \\
        \text{False} \otimes \text{False} & \text{else}.
        \end{array} \right.\]
\end{example}

We can add a poset structure to this species to obtain a poset Hopf monoid. Say that $\phi \leq \psi$ if whenever $\phi$ is true, then so is $\psi$. That is, if $\phi \implies \psi$. Geometrically, $\phi \leq \psi$ if the support of the cones of $\phi$ is contained in the support of the cones of $\psi$.

\begin{proposition} The poset species $\Sch$ equipped with the multiplication and comultiplication maps defined above forms a coadjoint poset Hopf monoid with the free product $\Box_{S,T}$ given by 
\[\phi_1 \Osq \phi_2 = \phi_1 \wedge \phi_2 \wedge \bigwedge_{i \in S, j \in T} x_i < x_j.\]
\end{proposition}

The irreducible problems are those that can not be written as a free product of other problems. 

\begin{proposition} If $X \vDash I$ is an ordered set partition, let $\phi(X)$ be the scheduling problem associated to $X$. Then, the primitives of $\Sch[I]$ have a basis given by $\{\omega_{\phi}; \lvert \;  \text{$\phi$ is $\Box$-indecomposable}\}.$
\end{proposition}


In the full version of the paper we give a geometric description of these primitives.

\section{Conclusion}

The approach outlined in the last few examples extends to a large amount of other examples. These include QSYM, NSYM, weak order of permutations, hypergraphs, generalized permutahedra, nestohedra, simplicial complexes, and representations of towers of groups.

The full version of this paper will include a more detailed study of these examples as well as: applications to antipode calculations, Cartier--Milnore--Moore type theorems, a classification of self-adjoint Hopf monoids, applications to polynomial invariants from character theory, and connections to incidence Hopf algebras.


\acknowledgements{I would like to thank Jacob White for introducing me to the Hopf structure of scheduling problems and Federico Ardila for his helpful conversations on Hopf theory. I also thank the referees for the useful feedback. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.}

%\bibliographystyle{plain}
%\bibliography{ref}
\sloppy
\printbibliography
\fussy

\end{document}
