\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\OneNumberAllTheorems
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\specialcomment{moredetails}{\begingroup\color{red}}{\endgroup}
\usepackage{tikz}
%\usepackage{comment}
\usepackage[all]{xy}
%\usepackage{todonotes}
%\usepackage{color}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\green}[1]{\textcolor{green}{#1}}
\newcommand{\blueun}[1]{\textcolor{blue}{#1}}
\newcommand{\redun}[1]{\textcolor{red}{#1}}
\newcommand{\greenun}[1]{\textcolor{green}{#1}}
\newenvironment{associativity}{\begin{enonce*}[remark]{Associativity}}{\end{enonce*}}
\newenvironment{compatibility}{\begin{enonce*}[remark]{Compatibility}}{\end{enonce*}}
%-------------------------------------------------------------------
% MACROS
%-------------------------------------------------------------------
%\newcommand{\draftnote}[1]{\marginpar{\raggedright\textsf{\hspace{0pt}\red{#1}}}}
%\newcommand{\Vinc}{\begin{turn}{90}$\subseteq$\end{turn}}
%\newcommand{\Veq}{\begin{turn}{90}$=$\end{turn}}
\def\Id{\mathbf{1}}
%\DeclareMathOperator{\coker}{coker}
%\DeclareMathOperator{\supp}{supp}
%\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\id}{id}
%\def\llb{{[\![}}
%\def\rrb{{]\!]}}
%\newcommand{\abs}[1]{\lvert#1\rvert} %for absolute value
%\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}} %for round matrix
%\newcommand{\larc}[1]{\hspace{-.4ex}\overset{#1}{\frown}\hspace{-.4ex}}
%\newcommand{\slarc}[1]{\overset{#1}{\frown}}
\newcommand{\gel}{>_{\ell}}
\newcommand{\lel}{<_{\ell}}
%\newcommand{\one}{\mathbf{1}}
%\newcommand{\euler}{\mathbf{e}}
%\let\onto=\twoheadrightarrow
%\let\into=\hookrightarrow
\let\map=\xrightarrow
%\newcommand{\xyinc}{\ar@{^{(}->}}
%\newcommand{\mapsby}[1]{ \overset{#1}{\longmapsto}}
%\newcommand{\type}[2]{\mathsf T_{#1}(#2)}
\def\field{\Bbbk}
\newcommand{\rL}{\mathbf{l}}
\newcommand{\rG}{\mathbf{g}}
\newcommand{\bL}{\mathbf{L}}
%\newcommand{\bE}{\mathbf{E}}
\newcommand{\bH}{\mathbf{H}}
\newcommand{\bh}{\mathbf{h}}
%\newcommand{\bk}{\mathbf{k}}
%\newcommand{\bK}{\mathbf{K}}
\newcommand{\bPi}{\bpi}
\newcommand{\bG}{\mathbf{G}}
%\newcommand{\bp}{\mathbf{p}}
%\newcommand{\bq}{\mathbf{q}}
%\newcommand{\bmm}{\mathbf{m}}%\bm exists
%\newcommand{\bd}{\mathbf{d}}
\newcommand{\bpi}{\boldsymbol \pi}
%\newcommand{\Fc}{\mathcal{F}}
%\newcommand{\Tc}{\mathcal{T}}
\newcommand{\Kc}{\mathcal{K}}
\newcommand{\Kcb}{\overline{\Kc}}
%\newcommand{\Nb}{\mathbb{N}}
%\newcommand{\Qb}{\mathbb{Q}}
%\newcommand{\Cb}{\mathbb{C}}
%\newcommand{\Zb}{\mathbb{Z}}
%\newcommand{\Fb}{\mathbb{F}}
%\newcommand{\Fq}{\Fb_q}
%\newcommand{\Nf}{\mathfrak{n}}
%\newcommand{\bNf}{\overline{\Nf}}
%\newcommand{\Mf}{\mathfrak{m}}
%\newcommand{\bMf}{\overline{\Mf}}
\newcommand{\qand}{\quad\text{and}\quad}
\newcommand{\qqand}{\qquad\text{and}\qquad}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
\author{\firstname{Carolina} \lastname{Benedetti}} %%%%1
\address
{Departamento de Matem\'aticas\\
Universidad de los Andes\\
Bogot\'a, Colombia}
\email{c.benedetti@uniandes.edu.co}
\urladdr{https://sites.google.com/site/carobenedettimath/}
%
\thanks{Carolina Benedetti thanks the faculty of Science of the University of Los Andes for its support.}
%
\author{\firstname{Nantel} \lastname{Bergeron}} %%%%2
\address
{Department of Mathematics and Statistics\\
York University\\
Toronto, Ontario M3J 1P3, Canada}
\email{bergeron@mathstat.yorku.ca}
\urladdr{http://www.math.yorku.ca/bergeron}
\thanks{With partial support of Bergeron's York University Research Chair and NSERC}
%%%%% Sujet
\subjclass{16T30, 05E15, 16T05, 18D35}
\keywords{Antipode, Hopf monoid, Hopf algebra, combinatorial identities, colorings, hypergraphs, orientations}
%%%%% Gestion
\DOI{10.5802/alco.53}
\datereceived{2018-02-23}
\daterevised{2018-11-23}
\dateaccepted{2018-12-07}
%%%%% Titre et résumé
\title[Antipode of linearized Hopf monoids]{The antipode of linearized Hopf monoids}
\begin{abstract}
In this paper, a Hopf monoid is an algebraic structure built on objects in the category of Joyal's vector species.
There are two Fock functors, $\mathcal{K}$ and $\overline{\mathcal{K}}$,
that map a Hopf monoid $\mathbf{H}$ to graded Hopf algebras $\mathcal{K} (\mathbf{H})$ and $\overline{\mathcal{K}} (\mathbf{H}) $, respectively.
There is a natural Hopf monoid structure on linear orders $\mathbf L$, and the two Fock functors are related by $\mathcal{K}(\mathbf{H}) = \overline{\mathcal{K}}(\mathbf{H} \times \mathbf{L})$.
Unlike the functor $\overline{\mathcal{K}}$, the functor $\mathcal{K}$ applied to $\mathbf{H}$ may not preserve the antipode of $\mathbf{H}$. In view of the relation between $\mathcal{K}$ and $\overline{\mathcal{K}}$, one may consider instead of $\mathbf{H}$ the larger Hopf monoid $\mathbf{L}\times \mathbf{H}$ and study the antipode of $\mathbf{L}\times \mathbf{H}$. One of the main results in this paper provides a cancellation free and multiplicity free formula for the antipode of $\mathbf{L}\times \mathbf{H}$. As a consequence, we obtain a new antipode formula for the Hopf algebra $H=\mathcal{K} (\mathbf{H})$. We explore the case when $\mathbf{H}$ is commutative and cocommutative, and obtain new antipode formulas that, although not cancellation free, they can be used to obtain an antipode formula for $\overline{\mathcal{K}}(\mathbf{H})$ in some cases. We also recover many well-known identities in the literature involving antipodes of certain Hopf algebras. In our study of commutative and cocommutative Hopf monoids, hypergraphs and acyclic orientations play a central role. We obtain polynomials analogous to the chromatic polynomial of a graph, and also identities parallel to Stanley's ($-1$)-color theorem. An important consequence of our notion of acyclic orientation of hypergraphs is a geometric interpretation for the antipode formula for hypergraphs. This interpretation, which differs from the recent work of Aguiar and Ardila as the Hopf structures involved are different, appears in subsequent work by the authors.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%
%% BEGIN DOCUMENT
%%%%%%%%%%%%%%
\begin{document}
\maketitle
%%%%%%%%%%%%%%
%% INTRODUCTION
%%%%%%%%%%%%%%
\section*{Introduction}
Computing antipode formulas in any graded Hopf algebra is a classical yet difficult problem. Recently, numerous results in this direction have been provided for various families of Hopf algebras~\cite{Aguiar-Ardila,AM:2010,BakerJarvisBergeronThiem,Benedetti-Sagan, Bergeron-Ceballos, Darij-Reiner,Humpert-Martin}. Some motivations to find such formulas lie in their geometric interpretation~\cite{Aguiar-Ardila}, their use in quantum field theories~\cite{FGB2005}, or their role in deriving combinatorial invariants of the discrete objects in play.
A key example of this is the Hopf algebra of graphs $\mathcal{G}$ as given in~\cite{Humpert-Martin}, where the authors derive the antipode formula and use it to obtain the celebrated Stanley's $(-1)$-color theorem: the chromatic polynomial of a graph evaluated at $-1$ is, up to a sign, the number of acyclic orientations of the graph. A remarkable result in~\cite{Aguiar-Ardila} shows that the antipode formula of a graph as given in~\cite{Humpert-Martin} is encoded in the $f$-vector of the graphical zonotope corresponding to the underlying graph.
A general principle is that antipode formulas provide interesting identities for the combinatorial invariants of combinatorial objects.
One of the key results in the theory of \emph{Combinatorial Hopf algebras (CHAs)} gives us a canonical way of constructing combinatorial invariants with values in the space $QSym$ of quasisymmetric functions (see~\cite{ABS}).
That is, letting $H=\bigoplus_{n\ge 0} H_n$ be a CHA over a field $\field$ and letting $\zeta\colon H\to\field$ be a \emph{character of $H$},
there is a unique Hopf morphism $\Psi:H\to QSym$
such that $\zeta=\phi_1\circ\Psi$ where $\phi_1\big(f(x_1,x_2,\ldots)\big)=f(1,0,0,\ldots)$. Moreover, there is a Hopf
morphism $\phi_t \colon QSym\to \field[t]$ given by
$\phi_t (M_a)=%{t \choose \ell}
\genfrac{(}{)}{0pt}{1}{t}{\ell},$
where $M_a$ is the monomial quasisymmetric function indexed by an integer composition $a=(a_1,a_2,\ldots,a_\ell)$.
This Hopf morphism has the property that
$$\phi_t\big(f(x_1,x_2,\ldots)\big) \Big|_{t=1}=\phi_1(f)\,.$$
In particular,
$$\phi_t\circ\Psi\Big|_{t=1}=\left( \phi_t\big|_{t=1}\right)\circ\Psi=\phi_1\circ\Psi=\zeta.$$
In the case when $H=\mathcal{G}$ and $\zeta$ is the character
$$\zeta(G)=\begin{cases}
1&\text{if $G$ has no edges,}\\
0&\text{otherwise,}
\end{cases}$$
we obtain that $\phi_t\circ \Psi(G)=\chi_G(t)$ is the chromatic polynomial of $G$ as shown in~\cite[Example~4.5]{ABS}.
Stanley's $(-1)$-color theorem can be deduced in this Hopf setting using the fact that the antipode of $\field [t]$ is given by $S\big(p(t)\big)=p(-t)$. Hence
$$\chi_G(-1)=S\circ\phi_t\circ \Psi(G)\Big|_{t=1} = \phi_t\circ \Psi\circ S(G)\Big|_{t=1}=\zeta\circ S(G).$$
Moreover, if $G$ is a graph on $n$ vertices and $a(G)$ is the number of acyclic orientations of $G$, one has that the coefficient in $S(G)$ of the edgeless graph with $n$ vertices is given by $(-1)^{n}a(G)$ (see~\cite{Aguiar-Ardila,Benedetti-Sagan,Humpert-Martin}). Therefore, $\chi_G(-1)=\zeta\circ S(G)=(-1)^{n}a(G)$.
Here, we present a general framework that allows us to derive new formulas for the antipode of many of the graded Hopf algebras in the literature.
%To achieve this, we lift the structure of a graded Hopf algebra to a Hopf monoid in Joyal's category of species, as described in~\cite{AM:2010} and in~\cite{PR:2004}.
Combinatorial objects which compose and decompose often give rise
to Hopf monoids in Joyal's symmetric monoidal category of vector species. A Hopf monoid $\bH$ is linearized if it can be described from a set species $\bh$ as follows. For a finite set $I$, the vector space $\bH[I]$ is the linear span of the set $\bh[I]$, and the structure of $\bH$ is obtained by
linearization of the functions that define the structure on $\bh$. We provide several examples of linearized Hopf monoids throughout.
There are two natural functors, the Fock functors $\mathcal{K}$ and $\overline{\mathcal{K}}$,
that map Hopf monoids to graded Hopf algebras.
Via these functors, it is sometimes possible to \emph{lift} a Hopf algebra structure to the monoid level.
All the objects and notions above are found in~\cite{AM:2010}. See also~\cite{PR:2004} where Hopf monoids are referred to as twisted Hopf algebras.
The few basic notions and examples needed for our purposes are reviewed in
Section~\ref{s:hopf}, including the Hopf monoid of linear orders $\bL$, the notion of linearized Hopf monoid, the Hadamard product and the Fock functors $\mathcal{K}$ and $\overline{\mathcal{K}}$.
The first goal of this paper is to construct a cancellation free and multiplicity free formula for
the antipode of the Hadamard product $\bL\times\bH$ where $\bH$ is a linearized Hopf monoid.
This result will be developed in Section~\ref{s:antiLxH}. One interesting fact is that even if the antipode formula of a Hopf monoid $\bH$ is cancellation free, the Hopf algebra $\Kcb(\bH)$ may potentially have lots of cancellations in its antipode formula.
%this formula contains potencially lots of cancellation
%at the level of Hopf monoids the antipode formula is cancellation free,
%many cancellations may occur when applying $\Kcb$.
However, $\Kcb$ gives us new ways of formulating antipodes and potentially new identities.
We discuss this in Section~\ref{s:KLxH}.
In Section~\ref{s:antiH} we consider antipode formulas for commutative and cocommutative linearized Hopf monoids $\bH$.
This case is especially interesting as many of the Hopf monoids in combinatorics fall into this class.
One consequence of our analysis is that the most relevant case to consider is the Hopf monoid of hypergraphs $\mathbf{HG}$ as defined in Section~\ref{ss:hypergraph}.
The Hopf monoid $\mathbf{HG}$ contains all the information to compute antipodes for any other commutative and cocommutative linearized Hopf monoid $\bH$.
This is a remarkable fact which we will unveil along the way.
We give two antipode formulas for such $\bH$. One is derived in Section~\ref{ss:antiHwithLxH} from our work in Section~\ref{s:antiLxH} and one is obtained in Section~\ref{subsec:acyclic} using orientations of hypergraphs. The second antipode formula is obtained using a sign reversing involution as in~\cite{Benedetti-Sagan,Bergeron-Ceballos}.
Applications of our computations are presented in Section~\ref{ss:anticom}.
In Section~\ref{ss:antiStan} we derive combinatorial identities using our antipode formulas.
In particular we introduce a chromatic polynomial for total orders (permutations) and show an analogue of Stanley's $(-1)$-theorem.
We finish with a remark relating the results presented here to subsequent work obtained jointly with J. Machacek~\cite{BBM:2017} in which we provide a geometric interpretation for the antipode of $\mathbf{HG}$ as encoded by a hypergraphic polytope.
We point out that this interpretation differs from the one in~\cite{Aguiar-Ardila}. Part of the difference relies on the fact that $\mathbf{HG}$ is cocommutative whereas the Hopf algebra of hypergraphs in~\cite{Aguiar-Ardila} is not. We encourage the reader to see~\cite{BBM:2017} for more details.
%{is not} and . The geometric interpretation we have \emph{looks} similar to~\cite{Aguiar-Ardila} but it is in fact very different.
%%%%%%%%%%%%%%
%% HOPF MONOID
%%%%%%%%%%%%%%
\section{Hopf monoids}\label{s:hopf}
We review basic notions on Hopf monoids and illustrate definitions with three classical examples. We encourage the reader to see~\cite{AM:2010} for a deeper study on this topic. Throughout the paper $\field$ denotes an arbitrary field and all vector spaces are assumed to be over $\field$.
In general, a Hopf monoid is defined in a symmetric monoidal category, but here we will use the term {Hopf monoid} in a much more
restrictive manner. From now on, \emph{Hopf monoid} stands for a connected Hopf monoid in the symmetric monoidal category of vector species using Cauchy product. Rather than defining these concepts in their full generality, we give here a brief description of the data that is needed for our purposes. However we highly encourage the reader to see~\cite{AM:2010} for more details on Hopf monoids and~\cite{species98} for more details on species.
%%%%%%%%%%%%%%
%% Basic Definition of Hopf monoid
%%%%%%%%%%%%%%
\subsection{Species and Hopf monoids}\label{ss:sp-hopf}
A \emph{vector species} is a functor from the category of finite sets and bijections to the category of vector spaces and linear maps. Informally, a {vector species} $\bH$ is a collection of vector spaces $\bH[I]$,
one for each finite set $I$, equivariant with respect to bijections $I\cong J$.
A morphism of species $f:\bH\to\mathbf{Q}$ is a collection of linear maps
$f_I:\bH[I]\to{\mathbf{Q}}[I]$ which commute with bijections.
A \emph{set composition} of a finite set $I$ is a finite sequence $(A_1,\ldots,A_k)$
of disjoint non-empty subsets of $I$ whose union is $I$. In this situation, we write
$
(A_1,\ldots,A_k)\models I.
$
A \emph{Hopf monoid} consists of a vector species $\bH$
equipped with two collections $\mu$ and $\Delta$ of equivariant linear maps
\[
\bH[A_1]\otimes\bH[A_2] \map{\mu_{A_1,A_2}}\bH[I]
\qand
\bH[I]\map{\Delta_{A_1,A_2}} \bH[A_1]\otimes\bH[A_2]
\]
subject to a number of axioms, of which the main ones follow.
%\noindent
%{\bf Associativity}:
\begin{associativity}
For each set composition $(A_1, A_2, A_3)\models I$, the diagrams
\begin{equation}\label{e:assoc}
\begin{gathered}
\xymatrix@R+1pc@C+20pt{
\bH[A_1]\otimes\bH[A_2]\otimes\bH[A_3]\ar[r]^-{\id\otimes\mu_{A_1,A_2}}
\ar[d]_{\mu_{A_1,A_2}\otimes\id} & \bH[A_1]\otimes\bH[A_2\cup A_3]\ar[d]^{\mu_{A_1,A_2\cup A_3}} \\
\bH[A_1\cup A_2]\otimes \bH[A_3]\ar[r]_-{\mu_{A_1\cup A_2,A_3}} & \bH[I]
}
\end{gathered}
\end{equation}
\begin{equation}
\label{e:coassoc}
\begin{gathered}
\xymatrix@R+1pc@C+40pt{
\bH[I]\ar[r]^-{\Delta_{A_1\cup A_2,A_3}} \ar[d]_{\Delta_{A_1,A_2\cup A_3}}
& \bH[A_1\cup A_2]\otimes \bH[A_3]\ar[d]^{\Delta_{A_1,A_2}\otimes\id}
\\
\bH[A_1]\otimes\bH[A_2\cup A_3]\ar[r]_-{\id\otimes\Delta_{A_1,A_2}}
& \bH[A_1]\otimes\bH[A_2]\otimes\bH[A_3]
}
\end{gathered}
\end{equation}
commute.
\end{associativity}
%\noindent
%{\bf Compatibility}:
\begin{compatibility}
Fix two set compositions $(A_1,A_2)$ and $(B_1,B_2)$ of $I$,
and consider the resulting pairwise intersections:
\[
P:=A_1\cap B_1,\ Q:=A_1\cap B_2,\ R:=A_2\cap B_1,\ T:=A_2\cap B_2,
\]
as illustrated below
\begin{equation}\label{e:4sets}
\begin{gathered}
\quad \begin{picture}(100,90)(20,0)
\put(50,40){\oval(90,70)}
\put(5,40){\dashbox{2}(90,0){}}
\put(45,55){$A_1$}
\put(45,15){$A_2$}
\end{picture}
\quad
\begin{picture}(100,90)(10,0)
\put(50,40){\oval(90,70)}
\put(50,5){\dashbox{2}(0,70){}}
\put(20,35){$B_1$}
\put(70,35){$B_2$}
\end{picture}
\quad
\begin{picture}(100,90)(0,0)
\put(50,40){\oval(90,70)}
\put(5,40){\dashbox{2}(90,0){}}
\put(50,5){\dashbox{2}(0,70){}}
\put(20,55){$P$}
\put(70,55){$Q$}
\put(20,15){$R$}
\put(70,15){$T$}
\end{picture}
\end{gathered}.
\end{equation}
For any such pair of set compositions, the diagram
\begin{equation}\label{e:comp}
\begin{gathered}
\xymatrix@R+2pc@C-5pt{
\bH[P] \otimes \bH[Q] \otimes \bH[R] \otimes \bH[T] \ar[rr]^{\cong} & &
\bH[P] \otimes \bH[R] \otimes \bH[Q] \otimes \bH[T] \ar[d]^{\mu_{P,R}
\otimes \mu_{Q,T}}\\
\bH[A_1] \otimes \bH[A_2] \ar[r]_-{\mu_{A_1,A_2}}\ar[u]^{\Delta_{P,Q} \otimes
\Delta_{R,T}} & \bH[I] \ar[r]_-{\Delta_{B_1,B_2}} & \bH[B_1] \otimes
\bH[B_2]
}
\end{gathered}
\end{equation}
must commute. The top arrow stands for the map that interchanges the middle factors.
In addition, we require that the Hopf monoid $\bH$ is \emph{connected}, that is,
$\bH[\emptyset]\cong\field$ and the maps
\[
\xymatrix{
\bH[I]\otimes\bH[\emptyset] \ar@<0.5ex>[r]^-{\mu_{I,\emptyset}} &
\bH[I] \ar@<0.5ex>[l]^-{\Delta_{I,\emptyset}}
}
\qqand
\xymatrix{
\bH[\emptyset]\otimes\bH[I] \ar@<0.5ex>[r]^-{\mu_{\emptyset,I}} &
\bH[I] \ar@<0.5ex>[l]^-{\Delta_{\emptyset,I}}
}
\]
are the canonical identifications.
The collection $\mu$ is the \emph{product} and the collection $\Delta$
is the \emph{coproduct} of the Hopf monoid $\bH$. For any Hopf monoid $\bH$ the antipode map $S\colon \bH\to\bH$ is computed using Takeuchi's formula (see Section 8.4.2 of~\cite{AM:2010}). More precisely, for any finite set $I$ and a set composition $A=(A_1,\ldots,A_k)\models I$, if $k=1$ we let $\mu_{A_1}=\Delta_{A_1}=\Id_I$ the identity map on $\bH[I]$, and if $k>1$ we let
$$ \mu_{A_1,\ldots,A_k} = \mu_{A_1,I\setminus A_1}(\Id_{A_1}\otimes\mu_{A_2,\ldots,A_k})\quad\text{and}\quad
\Delta_{A_1,\ldots,A_k} =(\Id_{A_1}\otimes\Delta_{A_2,\ldots,A_k}) \Delta_{A_1,I\setminus A_1}.
$$
We then have
\begin{equation}\label{eq:takeuchi}
S_I = \sum_{k=1}^{|I|}\sum_{(A_1,\ldots,A_k)\models I} (-1)^{k} \mu_{A_1,\ldots,A_k} \Delta_{A_1,\ldots,A_k}
= \sum_{A\models I} (-1)^{\ell(A)} \mu_A \Delta_A\,.
\end{equation}
A Hopf monoid is (co)commutative if the left (right) diagram below commutes
for all set compositions $(A_1,A_2)\models I$.
\begin{equation}\label{e:comm}
\begin{gathered}
\xymatrix@C-15pt{
\bH[A_1]\otimes\bH[A_2] \ar[rr]^-{\tau_{A_1,A_2}} \ar[rd]_{\mu_{A_1,A_2}} & & \bH[A_2]\otimes\bH[A_1] \ar[ld]^{\mu_{A_2,A_1}} \\
& \bH[I] &
}
\\
\xymatrix@C-15pt{
\bH[A_1]\otimes\bH[A_2] \ar[rr]^-{\tau_{A_1,A_2}} & &\bH[A_2]\otimes\bH[A_1] \\
& \bH[I] \ar[lu]^{\Delta_{A_1,A_2}} \ar[ru]_{\Delta_{A_2,A_1}} &
}
\end{gathered}
\end{equation}
The arrow $\tau_{A_1,A_2}$ stands for
the map that interchanges the factors.
A morphism of Hopf monoids $f:\bH\to\mathbf{Q}$ is a morphism of species that
commutes with $\mu$ and $\Delta$.
\end{compatibility}
%%%%%%%%%%%%%%
%% HOPF MONOID of LINEAR ORDERs
%%%%%%%%%%%%%%
\subsection{The Hopf monoid of linear orders \texorpdfstring{$\bL$ (\cite{AM:2010})}{L ([4])}}\label{ss:order}
For any finite set $I$ let
$\rL[I]$ be the set of all linear orders on $I$. For instance, if $I=\{a,b,c\}$,
\[
\rL[I]=\{abc,\,bac,\,acb,\,bca,\,cab,\,cba\}.
\]
The vector species $\bL$ is such that $\bL[I]:=\field\rL[I]$ is the vector space with basis $\rL[I]$.
Given $(A_1,A_2)\models I$
and linear orders $\alpha_1,\alpha_2$ on $A_1,A_2$, respectively,
their concatenation $\alpha_1\cdot \alpha_2$
is the linear order on $I$ given by $\alpha_1$ followed by $\alpha_2$.
Given a linear order $\alpha$ on $I$ and $P\subseteq I$, the restriction
$\alpha|_P$ is the ordering in $P$ given by the order $\alpha$.
These operations give rise to maps
\begin{equation}\label{e:L}
\begin{aligned}
\rL[A_1]\times\rL[A_2] & \to \rL[I] &\qquad\qquad \rL[I] & \to \rL[A_1]\times\rL[A_2]\\
(\alpha_1,\alpha_2) & \to \alpha_1\cdot\alpha_2
& \alpha & \to (\alpha |_{A_1},\alpha |_{A_2}).
\end{aligned}
\end{equation}
Extending by linearity, we obtain linear maps
\[
\mu_{A_1,A_2}:\bL[A_1]\otimes\bL[A_2] \to \bL[I]
\qand
\Delta_{A_1,A_2}:\bL[I]\to \bL[A_1]\otimes\bL[A_2]
\]
which turn $\bL$ into a cocommutative but not commutative Hopf monoid. The reader should check that all the required axioms for a Hopf monoid are indeed satisfied for this and the upcoming examples.
%%%%%%%%%%%%%%
%% HOPF MONOID of SET PARTITIONs
%%%%%%%%%%%%%%
\subsection{The Hopf monoid of set partitions \texorpdfstring{$\bPi$ (\cite{AM:2010})}{pi ([4])} }\label{ss:partition}
A \emph{partition} of a finite set $I$ is a collection $X$ of disjoint nonempty subsets whose union is $I$. The subsets are the \emph{blocks} of $X$.
Given a partition $X$ of $I$ and $P\subseteq I$, the restriction
$X|_P$ is the partition of $P$ whose blocks are
the nonempty intersections of the blocks of $X$ with $P$.
Given $(A_1,A_2)\models I$
and partitions $X_i$ of $A_i$, $i=1,2$,
the union $X_1\cup X_2$ is the partition of $I$
whose blocks are the blocks of $X_1$ and the blocks of $X_2$.
Let ${\bpi}[I]$ denote the set of partitions of $I$ and $\bPi[I]=\field {\bpi}[I]$ the vector
space with basis ${\bpi}[I]$.
A Hopf monoid structure on $\bPi$ is defined and studied in~\cite{AguiarBergeronThiem,AM:2010,BakerJarvisBergeronThiem,BergeronZabrocki}. Among its various linear bases, we are interested in the \emph{power-sum} basis
on which the operations are as follows.
The product
\[
\mu_{A_1,A_2}: \bPi[A_1] \otimes \bPi[A_2] \to \bPi[I]
\]
is given by
\begin{equation}\label{e:prod-m}
\mu_{A_1,A_2}({X_1} \otimes {X_2}) = X_1\cup X_2.
\end{equation}
for $X_i\in {\bpi}[A_i]$ and extended linearly. The coproduct
\[
\Delta_{A_1,A_2}: \bPi[I] \to \bPi[A_1]\otimes\bPi[A_2]
\]
is given by
\begin{equation}\label{e:coprod-m}
\Delta_{A_1,A_2}(X) =
\begin{cases}
{X|_{A_1}} \otimes {X|_{A_2}} & \text{if $A_1$ is the union of some blocks of $X$,} \\
0 & \text{otherwise,}
\end{cases}
\end{equation}
for $X\in {\bpi}[I]$ and extended linearly.
These operations turn the species $\bPi$ into a Hopf monoid that is both commutative and cocommutative.
%%%%%%%%%%%%%% APR-
%% HOPF MONOID of GRAPHS
%%%%%%%%%%%%%%
\subsection{The Hopf monoid of simple graphs \texorpdfstring{$\mathbf{G}$}{G}}\label{ss:graph}
A \emph{(simple) graph} $g$ on a finite set $I$ is a collection $E$ of subsets of $I$ of size 2.
% relation on $I$ that is symmetric and irreflexive.
The elements of $I$ are the \emph{vertices} of $g$.
There is an \emph{edge} between two vertices $i, j$ if $e=\{i,j\}\in E$. In this case we say that $e$ is \emph{incident} to $i$ and $j$.
Given a graph $g$ on $I$ and $P\subseteq I$, the restriction
$g|_P$ is the graph on the vertex set $P$ whose edges are the edges of $g$ incident to elements of $P$ only.
Let $(A_1, A_2)\models I$ and
consider the graphs $g_i$ of $A_i$, for $i=1,2$.
The union $g_1\cup g_2$ is the graph on $I$
whose edges are those of $g_1$ and those of $g_2$.
Let $\rG[I]$ denote the set of graphs on $I$ and $\bG[I]=\field \rG[I]$ the vector
space with basis $\rG[I]$.
A Hopf monoid structure on $\bG$ is defined using the maps
\begin{equation}\label{e:G}
\begin{aligned}
\rG[A_1]\times\rG[A_2] & \to \rG[I] &\qquad\qquad \rG[I] & \to \rG[A_1]\times\rG[A_2]\\
(g_1,g_2) & \to g_1\cup g_2
& g & \to (g |_{A_1},g |_{A_2}).
\end{aligned}
\end{equation}
Extending linearly, we obtain linear maps
\[
\mu_{A_1,A_2}:\bG[A_1]\otimes\bG[A_2] \to \bG[I]
\qand
\Delta_{A_1,A_2}:\bG[I]\to \bG[A_1]\otimes\bG[A_2].
\]
These operations turn the species $\bG$ into a Hopf monoid that is both commutative and cocommutative.
%%%%%%%%%%%%%%
%% HOPF MONOID of HYPERGRAPHS
%%%%%%%%%%%%%%
\subsection{The Hopf monoid of simple hypergraphs \texorpdfstring{$\mathbf{HG}$}{HG}}\label{ss:hypergraph}
Let $2^I$ denote the collection of subsets of $I$. Let $\mathbf{HG} [I]=\field {\mathbf{hg}} [I]$ be the space spanned by the basis $\mathbf{hg} [I]$ where
$$\mathbf{hg}[I]=\big\{h \subseteq 2^I\,: U\in h\text{ implies }|U|\ge 2\big\}.$$
%\caro{but then, what is the construction on sets of size 1? it is only the empty set}
An element $h\in\mathbf{hg}[I]$ is a \emph{hypergraph on $I$}.
For $(P,T)\models I$ and $h,k\in \mathbf{hg}[I]$, the multiplication is given by $\mu_{P,T}(h,k)=h\cup k$ and the comultiplication
is given by $\Delta_{P,T}(h) = h |_P\otimes h |_T$ where $h |_P=\{U\in h : U\cap P = U\}$. Extending these definitions linearly we have that $\mathbf{HG}$ is
commutative and cocommutative Hopf monoid.
%\begin{rema}\label{r:selfdual}
%The dual of a species $\bH$ is the collection $\bH^*$ of dual vector spaces:
%$\bH^*[I]=\bH[I]^*$.
%A species $\bH$ is said to be finite-dimensional if each space $\bH[I]$
%is finite-dimensional.
%Dualizing the operations of a finite-dimensional Hopf monoid $\bH$,
%one obtains a Hopf monoid $\bH^*$. The Hopf monoid $\bH$ is called self-dual
%if $\bH\cong\bH^*$. In general, such isomorphism is not unique.
%
%Over a field of characteristic $0$, a Hopf monoid that is connected, commutative and cocommutative, is always
%self-dual. This is a consequence of the Cartier-Milnor-Moore theorem.
%The isomorphism with the dual is not canonical.
%In particular, the Hopf monoids $\bPi$ and $\bG$ are self-dual.
%\end{rema}
%%%%%%%%%%%%%%
%% HADAMARD PRODUCT
%%%%%%%%%%%%%%
\subsection{The Hadamard product}\label{ss:hadamard}
Given two species $\bH$ and $\mathbf{Q}$, their \emph{Hadamard product} is the species $\bH\times\mathbf{Q}$ defined by
\[
(\bH\times\mathbf{Q})[I] = \bH[I]\otimes\mathbf{Q}[I],
\]
where $\otimes$ is the usual tensor product of vector spaces over $\field$.
If $\bH$ and $\mathbf{Q}$ are Hopf monoids, then so is $\bH\times\mathbf{Q}$, with the following operations. For $(A_1, A_2)\models I$, the product on $\bH\times\mathbf{Q}$ is depicted in the diagram:
\[
\xymatrix@C+12pt{
(\bH\times\mathbf{Q})[A_1]\otimes(\bH\times\mathbf{Q})[A_2] \ar@{=}[d] \ar@{-->}[rr] &&
(\bH\times\mathbf{Q})[I] \ar@{=}[dd] \\
\bH[A_1]\otimes \mathbf{Q}[A_1]\otimes \bH[A_2]\otimes \mathbf{Q}[A_2]
\ar[d]_{\cong} && \\
\bH[A_1]\otimes \bH[A_2]\otimes \mathbf{Q}[A_1]\otimes \mathbf{Q}[A_2]
\ar[rr]_-{\mu_{A_1,A_2}^{\mathbf{H}}\otimes\mu_{A_1,A_2}^{\mathbf{Q}}} &&
\bH[I]\otimes\mathbf{Q}[I]
}
\]
The coproduct is defined similarly. If $\bH$ and $\mathbf{Q}$ are (co)commutative, then so is $\bH\times\mathbf{Q}$.
%%%%%%%%%%%%%%
%% linearized
%%%%%%%%%%%%%%
\subsection{Linearized Hopf monoids}\label{ss:stronglin} A \emph{set species} $\bh$ is a collection of sets $\bh[I]$,
one for each finite set $I$, equivariant with respect to bijections $I\cong J$.
We say that $\bh$ is a basis for a Hopf monoid $\bH$ if for every finite set $I$ we have that $\bH[I]=\field \bh[I]$, the vector space with basis $\bh[I]$. We say that the monoid $\bH$ is \emph{linearized} in the basis $\bh$ if the product and coproduct maps have the following properties.
The product
\[
\mu_{A_1,A_2}: \bH[A_1] \otimes \bH[A_2] \to \bH[I]
\]
is the linearization of a map
\begin{equation}\label{e:prod-lin}
\mu_{A_1,A_2}: \bh[A_1] \times \bh[A_2] \to \bh[I]
\end{equation}
and the coproduct
\[
\Delta_{A_1,A_2}: \bH[I] \to \bH[A_1]\otimes\bH[A_2]
\]
is the linearization of a map
\begin{equation}\label{e:coprod-lin}
\Delta_{A_1,A_2}: \bh[I] \to (\bh[A_1]\times\bh[A_2])\cup\{0\}\,.
\end{equation}
It is understood that for any bijection $\sigma\colon I \to J$, the linear isomorphism $\bH[\sigma]\colon \bH[I]\to \bH[j]$ maps the basis $\bh[I]$ to the basis $\bh[J]$ via the bijection $\bh[\sigma]$.
From now on, we will use capital letters for vector species and lower case for set species.
The Hopf monoids $\bL$, $\bPi$, $\bG$ and $\mathbf{HG}$ are linearized in the bases $\mathbf{l}$, $\bpi$, $\mathbf{g}$ and $\mathbf{hg}$ respectively. As remarked in~\cite{MarbergLin}, many of the Hopf monoids in the literature are linearized in some basis.
%On the other hand, the Hopf monoid $\bL^{\star}$ is not linearized by $\bf l^{*}$, where $\bL^{\star}$ denotes the Hopf monoid \emph{dual} to $\bL$ (see~\cite{AM:2010}).
%%%%%%%%%%%%%%
%% FUNCTOR K and Kbar
%%%%%%%%%%%%%%
\subsection{Functors \texorpdfstring{$\mathcal{K}$}{K} and \texorpdfstring{$\overline{\mathcal{K}}$}{overline K}} \label{ss:K_Kbar}
As describe in~\cite[Section~III]{AM:2010}, there are some interesting functors from the category of species to the category of graded vector spaces. Let $[n]:=\{1,2,\ldots,n\}$ and assume throughout that $\text{char}(\field)=0$. Given a species $\bH$, we write $\bH[n]$ instead of $\bH[[n]]$. The symmetric group $S_n$ acts on $\bH[n]$ by relabelling. Define the functors $\Kc$ and $\Kcb$ as
$$ \Kc(\mathbf{H}) = \bigoplus_{n\ge 0} \mathbf{H}[n]
\qquad\qquad
\Kcb(\mathbf{H}) = \bigoplus_{n\ge 0} \mathbf{H}[n]_{S_n}
$$
where
$$
\mathbf{H}[n]_{S_n}={\bH}[n]\Big/ \langle x-{\bH}[\sigma](x) \mid \ \sigma\in S_n; \ x\in {\bH}[n]\rangle
$$
denotes the quotient space of equivalence classes under the $S_n$-action. When $\bH$ is a Hopf monoid,
we can build a product and coproduct
on $ \Kc({\bH})$ and $ \Kcb({\bH})$ from those of $\bH$ together
with certain canonical transformations.
For example, one has that
\[
\Kcb(\bL)\cong\field[t]
\]
is the polynomial algebra on one generator, while $\Kc(\bL)$
is the Hopf algebra introduced by Patras and Reutenauer in~\cite{PR:2004}. The antipode map $S:\bL\rightarrow\bL$ is such that
for $\alpha=a_1\cdots a_n\in\mathbf{l}[n]$
$$ S_{[n]}(\alpha)=(-1)^n a_n\cdots a_1.$$
However, the antipode of the graded Hopf algebra $\Kc[\bL]$ is not given by the formula above (see Section~\ref{s:KLxH}). On the other hand, in the Hopf algebra $\Kcb[\bL]\cong \field[t]$, the antipode is given by $S(t^n)=(-1)^nt^n$ and it is the functorial image of the map above. This is not an accident: the functor $\Kc$ may not preserve the antipode but the functor $\Kcb$ always does.
%One has that $\Kcb(\bPi)$ is the
%Hopf algebra of \emph{symmetric functions}, while
%$\Kc(\bPi)$ is the Hopf algebra of \emph{symmetric functions in noncommuting variables}, an object studied in various
%references including~\cite{AM:2006,BHRZ:2006,BZ:2009,RS:2006,BakerJBergeronThiem}.
A very interesting relation between the functors $\Kc$ and $\Kcb$ is given in~\cite[Theorem~15.13]{AM:2010} as follows
\begin{equation}\label{eq:KbarK}
\Kcb(\bL\times\bH) \cong \Kc(\bH),
\end{equation}
where $\bH$ is an arbitrary Hopf monoid. In this paper we aim to make use of this relation to study the antipode problem for some Hopf algebras.
%%%%%%%%%%%%%%
%% ANTIPODE FOR LxP
%%%%%%%%%%%%%%
\section{Antipode for linearized Hopf Monoid \texorpdfstring{$\bL\times \bH$}{L times H}}\label{s:antiLxH}
In this section we show a multiplicity free and cancellation free formula for the antipode of Hopf monoids of the form $\bL\times \bH$ where $\bH$ is linearized in some basis. Thus, by (\ref{eq:KbarK}), we obtain an antipode formula for $\Kc(\bH)$ as well. However, in $\Kc(\bH)$ this antipode formula may not be cancellation free.
%%%%%%%%%%%%%%
%% ANTIPODE FROM TAKEUCHI
%%%%%%%%%%%%%%
\subsection{Antipode Formula for \texorpdfstring{$\bL\times \bH$}{L times H}}\label{ss:UsingTakeushi}
Let $\bH$ be a Hopf monoid linearized in the basis $\bh$. We intend to resolve the cancellations in the Takeuchi formula for the antipode of $\bL\times\bH$. For a fixed finite set $I$ let $(\alpha,x)\in (\mathbf{l}\times\bh)[I]$, that is, $\alpha$ is a linear ordering on $I$ and $x$ is an element of $\bh [I]$. From~\eqref{eq:takeuchi} we have
\begin{equation}\label{eq:takeuchi1}
S_I(\alpha,x) = \sum_{A\models I} (-1)^{\ell(A)} \mu_A \Delta_A(\alpha,x)
= \sum_{\stackrel{A\models I} %\atop
{\Delta_A(x)\ne 0}} (-1)^{\ell(A)} (\alpha_A,x_A),
\end{equation}
summing over all $A=(A_1,\ldots,A_k)\models I$, where $\alpha_A$ denotes the element in $\mathbf{l} [I]$ given~by
$$\alpha_A= \alpha|_{A_1}\cdot \alpha|_{A_2}\cdots \alpha|_{A_k}\,.
$$ Also, provided $\Delta_A(x)\neq 0$ we set
$$x_A=\mu_A\Delta_A(x) \in \bh[I]\,.$$
Each composition $A$ gives rise to single elements $\alpha_A$ and $x_A$ since $\bL$ and $\bH$ are linearized in the basis $\mathbf{l}$ and $\bh$, respectively.
We can thus rewrite equation~\eqref{eq:takeuchi1} as
\begin{equation}\label{eq:takeuchi2}
S_I(\alpha,x) = \sum_{(\beta,y)\in (\mathbf{l}\times\bh)[I]}\left(\sum_{\stackrel{A\models I}
% \atop
{(\alpha_A,x_A)=(\beta,y)}} (-1)^{\ell(A)}\right) (\beta,y)\,.
\end{equation}
Let
\begin{equation}\label{eq:alphabetaxy}
\mathcal{C}_{\alpha,x}^{\beta,y}=\big\{A\models I : (\alpha_A,x_A)=(\beta,y)\big\}\,.
\end{equation}
Using the notation above we have the following theorem which provides us a multiplicity-free and cancellation-free formula for the antipode of $\bL\times\bH$.
\begin{theorem}\label{thm:antiLxP} Let $\bH$ be a linearized Hopf monoid in the basis $\mathbf{h}$. For $(\alpha, x)\in(\mathbf{l}\times\bh)[I]$ we have
$$ S_I(\alpha,x) = \sum_{(\beta,y)\in (\mathbf{l}\times\bh)[I]} c_{\alpha,x}^{\beta,y} \,(\beta,y),
\qquad\text{ where }\qquad
c_{\alpha,x}^{\beta,y}=\sum_{A\in \mathcal{C}_{\alpha,x}^{\beta,y}} (-1)^{\ell(A)}.$$
In Section~\ref{ss:involution} we define a non nested graph $G_{\alpha,x}^{\beta,y}$ and see that $c_{\alpha,x}^{\beta,y}=c(G_{\alpha,x}^{\beta,y})$ where $c(G)$, defined in Section~\ref{ss:proof1}, is an invariant associated to a non-nesting graph $G$
with values $\pm1 \text{ or } 0$. We then have the cancellation free formula
\begin{equation}\label{eq:thm1}
S_I(\alpha,x) = \sum_{\beta, y} c(G_{\alpha,x}^{\beta,y}) (\beta,y).
\end{equation}
\end{theorem}
The proof of this theorem will be given in Section~\ref{ss:proof1}. We make use of the refinement order on set compositions to show that the set $\mathcal{C}_{\alpha,x}^{\beta,y}$ has a unique minimum. We will use this fact along with other properties to construct sign reversing involutions on $\mathcal{C}_{\alpha,x}^{\beta,y}$ and the result will follow once we understand the fixed points of such involutions.
%%%%%%%%%%%%%%
%% REFINEMENT ORDER
%%%%%%%%%%%%%%
\subsection{Minimal element of \texorpdfstring{$\mathcal{C}_{\alpha,x}^{\beta,y}$}{C alpha,x beta,y}}\label{ss:refinementonC}
Given set compositions $A=(A_1,\ldots,A_k)$ and $B=(B_1,\ldots,B_\ell)$ on a set $I$,
we say that $A$ \emph{refines} $B$, and we write $A\le B$, if the parts of $B$ are unions of consecutive parts of $A$. For example
$$A = \big(\{1,4\},\{2\},\{5,7\},\{3\},\{9\},\{6,8\}\big) \le \big(\{1,4\},\{2,3,5,7\},\{6,8,9\}\big)=B$$
but $A$ does not refine $\big(\{1,4,5,7\},\{2\},\{3\},\{9\},\{6,8\}\big)$. Denote by $(\mathcal{P}_I,\leq)$ the poset of set compositions of $I$, ordered by refinement.
In what follows we will write $(14,2,57,3,9,68)$ instead of $\big(\{1,4\},\{2\},\{5,7\},\{3\},\{9\},\{6,8\}\big)$. Consider the order $\le$ restricted to the set $\mathcal{C}_{\alpha,x}^{\beta,y}$.
\begin{lemma}\label{le:min}
If $\mathcal{C}_{\alpha,x}^{\beta,y}\ne\emptyset$, then there is a unique minimal element in $(\mathcal{C}_{\alpha,x}^{\beta,y},\le)$.
\end{lemma}
\begin{proof} Suppose that $A=(A_1,\ldots,A_k)$ and $B=(B_1,\ldots,B_\ell)$ are minimal in $\in \mathcal{C}_{\alpha,x}^{\beta,y}$ and $A\neq B$. We have that $\alpha_A=\beta=\alpha_B$ and $x_A=y=x_B$. Since $\alpha_A=\beta$, the parts of $A$ appear consecutively in $\beta$ and the same is true for the parts of $B$. For example if $\alpha=abcdef$ and $\beta=bcfade$, then for $A=(bc,f,ad,e)$ and $B=(bc,f,a,de)$ we have $\alpha_A=\alpha_B=\beta$.
Let $1\le i\le k$ be the smallest index such that $A_i\ne B_i$, and assume without loss of generality that $|A_i|>|B_i|$. If $i=k$ then $B$ refines $A$ and this is a contradiction. Hence we assume that $i0$ and let $A$ be such that $r+1= \ell(\Lambda)-\ell(A)$. Let $B=(B_1,\dots,B_{k+1})\in \mathcal{P}_I$ such that $\Lambda\leq B< A$ with $\ell(B)-\ell(A)=1$. Hence there is a unique $i$ such that $A=(B_1,\ldots,B_i\cup B_{i+1},B_{i+2},\ldots,B_{k+1})$. We aim to show that $B\in\mathcal{C}_{\alpha,x}^{\beta,y}$, and then by induction hypothesis $[\Lambda,B]\subseteq \mathcal{C}_{\alpha,x}^{\beta,y}$.
Since $\Lambda\le B$, there is a unique $j$ such that
$$ B_1\cup\cdots\cup B_i=\Lambda_1\cup\cdots\cup \Lambda_j.$$
Let $P=\Lambda_1\cup\cdots\cup \Lambda_j$ and $Q=\Lambda_{j+1}\cup\cdots\cup \Lambda_m$. Arguing as in equations~\eqref{eq:Tcutx} and~\eqref{eq:TcutS} we have that
$$
\begin{aligned}
y&=\mu_\Lambda\Delta_\Lambda(x)=\mu_{P,Q}(\mu_{\Lambda_1,\ldots, \Lambda_j}\otimes \mu_{\Lambda_{j+1},\ldots, \Lambda_m})\Delta_\Lambda(x)\\
&=\mu_{P,Q}\Delta_{P,Q}\big(\mu_{P,Q}(\mu_{\Lambda_1,\ldots, \Lambda_j}\otimes \mu_{\Lambda_{j+1},\ldots, \Lambda_m})\Delta_\Lambda(x)\big)
=\mu_{P,Q}\Delta_{P,Q}(y)\\
&=\mu_{P,Q}\Delta_{P,Q}(\mu_A\Delta_A(x))= \mu_B\Delta_B(x)=x_B.
\end{aligned}
$$
The same argument shows that $\beta=\mu_{P,Q}\Delta_{P,Q}\mu_A\Delta_A(\alpha)= \mu_B\Delta_B(\alpha)=\alpha_B$. Hence $B\in \mathcal{C}_{\alpha,x}^{\beta,y}$. We can now appeal to the induction hypothesis and conclude that for each such $B$ the interval $[\Lambda,B]\subseteq \mathcal{C}_{\alpha,x}^{\beta,y}$ and thus the claim follows. Moreover, we conclude that $\mathcal{C}_{\alpha,x}^{\beta,y}$ is a lower ideal of the subposet
$[\Lambda,(I)]=\{B\models I : \Lambda \le B\}$.
\end{proof}
\begin{lemma}\label{le:upperideal} If $ \mathcal{C}_{\alpha,x}^{\beta,y}\ne \emptyset$,
then the minimal elements of $[\Lambda,(I)]\setminus \mathcal{C}_{\alpha,x}^{\beta,y}$ are each of the form
$$(\Lambda_1,\ldots,\Lambda_{i-1},\Lambda_i\cup\Lambda_{i+1}\cup\cdots\cup \Lambda_j,\Lambda_{j+1},\ldots,\Lambda_m)$$
for some $1\le i_{\alpha}b$, where $b$ is the smallest entry of $\alpha|_{\Lambda_{i+1}}$. Hence,
$$\Lambda**1$, $i=\min(A_j)$ and \big($j=1$ or $A_{j-1}\ne\{i-1\}$ or $(i-1,i)\in G_{\alpha,x}^{\beta,y}$\big), then
$$ \varphi_i(A)=(A_1,\ldots,A_{j-1},\{i\},A_{j}\setminus\{i\},A_{j+1},\ldots, A_k).$$
\end{enonce*}
\begin{enonce*}{$i$-Fix} If we do not have an $i$-merge or an $i$-split, then
$$\varphi_i(A)=A.$$
\end{enonce*}
Then the map $\varphi$ is defined as
\begin{equation}\label{eq:involution}
\varphi(A):=\begin{cases}
A & \text{if $\varphi_i(A)=A$ for all $1\le i\max(A_j)$, then we must have that
%$j1$ and that $A=(A_1,\ldots,A_k)\in \mathcal{C}(G)$ is a fixed point of $\varphi$. We have that $A_1=\{1\}$; otherwise we could perform a 1-split on $A$. Similarly, $A_2=\{2,\ldots,r\}$ and thus $ \ell\le r$; otherwise we could perform a 1-merge on $A$. Also, $\ell\le r2$ and $\{r+1,\ldots,m\}$ has at least two elements. Thus $A_3=\{r+1,...\}$ is nonempty. If $|A_3|>1$, then we can perform an $r+1$-split which contradicts the choice of $A$. Hence, $A_3=\{r+1\}$. Let $c=r+1$ and $A_4=\{c+1,\ldots,r'\}$. If there is no edge $(c,d)\in G$, then we would be allowed to do a $c$-merge on $A$, contradicting its choice. Thus such an edge $(c,d)$ exists. Since $G$ is non-nesting, we have $ 11$, we have seen in the proof of Lemma~\ref{le:nequal1} that if there is no arc $(c,d)\in G$ with $ 11$, the edges $(a_j,b_j)$ do not play a role
in our analysis of the fixed point of $\varphi$, we can omit them. Let $(a,b)=(a_1,b_1)$ and consider the set of arcs $\big\{(c_1,d_1),\ldots,(c_n,d_n)\big\}\subseteq G$ such that $\ell0$, in which case $y_{2k}=m$ and the edge $(x_{2k},y_{2k})$ is determined. With $i=k-1$ in condition~\ref{lemma2.12_i} of Lemma~\ref{le:fixshape} we have
\begin{equation}\label{eq:lastarcs}
G=
\begin{tikzpicture}[baseline=.2cm]
\foreach \x in {1,3,5,7,9,11,13,15,17}
\node (\x) at (\x/2,0) [inner sep=-1pt] {$\bullet$};
\node at (1/2,-.2) {$\scriptstyle 1$};
\node at (2/2,-.2) {$\scriptstyle $};
\node at (3/2,-.2) {$\scriptstyle \cdots$};
\node at (4/2,-.2) {$\scriptstyle $};
\node at (5/2,-.2) {$\scriptstyle \cdots$};
\node at (6/2,-.2) {$\scriptstyle $};
\node at (7/2,-.2) {$\scriptstyle x_{2k-2}$};
\node at (8/2,-.2) {$\scriptstyle <$};
\node at (9/2,-.2) {$\scriptstyle x_{2k-1}$};
\node at (10/2,-.2) {$\scriptstyle \le$};
\node at (11/2,-.2) {$\scriptstyle y_{2k-2}$};
\node at (12/2,-.2) {$\scriptstyle <$};
\node at (13/2,-.2) {$\scriptstyle x_{2k}$};
\node at (14/2,-.2) {$\scriptstyle \le$};
\node at (15/2,-.2) {$\scriptstyle y_{2k-1}$};
\node at (16/2,-.2) {$\scriptstyle <$};
\node at (17.5/2,-.2) {$\scriptstyle y_{2k}=m$};
\draw [densely dotted,thick] (7) .. controls (8/2,.75) and (10/2,.75) .. (11);
\draw [densely dotted,thick] (9) .. controls (11/2,.75) and (13/2,.75) .. (15);
\draw [thick] (13) .. controls (14/2,.75) and (16/2,.75) .. (17);
\end{tikzpicture} ,
\end{equation}
and condition~\ref{lemma2.12_ii} on the edges $(x_{2k-2},y_{2k-2})$, $(x_{2k-1},y_{2k-1})$ must also satisfy the condition~\ref{lemma2.12_ii} of Lemma~\ref{le:fixshape}.
% Since $G$ has no nesting this
% implies that there is no edge $(x,y)\in G$ such that $y_{2k-2}1$, then we repeat the process above with $ \mu_{U_{i\cdot\cdot r},T_{i\cdot\cdot m}}\Delta_{U_{i\cdot\cdot r},T_{i\cdot\cdot m}} \mu_{(\Lambda_i,\ldots,\Lambda_m)}$ for $2\le i\le r$ and we obtain
$y=x_C$ in all cases. This shows that $C\in \mathcal{C}_{x}^{y}$ contradicting the minimality of $\Lambda$.
\end{proof}
We now consider the analogue to Lemmas~\ref{le:lowerideal} and~\ref{le:upperideal} for $\bH$.
\begin{lemma}\label{le:Hlowerideal}
If $\mathcal{C}_{x}^{y}\ne\emptyset$, then for any $A\in\mathcal{C}_{x}^{y}$ and $\Lambda\in\mathcal{C}_{x}^{y}$ minimal, we have that
$[\Lambda,A]\subseteq \mathcal{C}_{x}^{y}$.
\end{lemma}
\begin{proof}[Proof sketch]
If $[\Lambda,A]=\emptyset$, then the lemma is trivially true. If $\Lambda\le A$, then the proof is exactly as in Lemma~\ref{le:lowerideal}.
This shows that $\mathcal{C}_{x}^{y}$ is a lower ideal in the order $\bigcup_{\sigma\in S_m} [\sigma\Lambda,(I)]$. \end{proof}
The next lemma shows us how $\mathcal{C}_{x}^{y}$
cuts off from $\bigcup_{\sigma\in S_m} [\sigma\Lambda,(I)]$.
\begin{lemma}\label{le:Hupperideal}
The minimal elements of $\big(\bigcup_{\sigma\in S_m} [\sigma\Lambda,(I)]\big)\setminus \mathcal{C}_{x}^{y}$ are all the permutations of set compositions of the form
$$(\bigcup_{i\in U} \Lambda_i,\Lambda_{v_1},\Lambda_{v_2},\ldots,\Lambda_{v_r})$$
for some $U\in\{1,2,\ldots,m\}$, where $r=m-|U|$ and $\{v_1,\ldots,v_r\}=I\setminus U$.
\end{lemma}
\begin{proof}[Proof sketch]
This proof is a direct adaptation of the proof of Lemma~\ref{le:upperideal}. It is clear that the upper ideal $\big(\bigcup_{\sigma\in S_m} [\sigma\Lambda,(I)]\big)\setminus \mathcal{C}_{x}^{y}$ is invariant under permutations. Let $B\in \big(\bigcup_{\sigma\in S_m} [\sigma\Lambda,(I)]\big)\setminus \mathcal{C}_{x}^{y}$ be minimal. If $B$ has more than two parts that are not single parts of $\Lambda$, then let $\sigma\in S_m$ be such that $\sigma\Lambda****\tau(i+1)$. Also, we draw an arc $(i,j)$ for each hyperedge $U\in G$ where $i=\min_\tau(U)$ and $j=\max_\tau(U)$ are the minimum and maximum values of $U$ according to the order $\tau$. Then we erase all drawn arcs that contain a nested arc.
With $\tau$ as above, we have the arc $(4,3)$ from the descent of $\tau$ and the arcs $(1,4)$ and $(2,3)$ for the hyperedges $\{1,2,4\}$ and $\{2,3,4\}$ respectively. Then we erase the arc $(2,3)$ since it contains the nested arc $(4,3)$.
The resulting graph is
$$G=G_{1234,x/\epsilon}^{1243,\epsilon}=
\begin{tikzpicture}[baseline=.2cm]
\foreach \x in {1,2,3,4}
\node (\x) at (\x/2,0) [inner sep=-1pt] {$\bullet$};
\node at (1/2,-.2) {$\scriptstyle 1$};
\node at (2/2,-.2) {$\scriptstyle 2$};
\node at (3/2,-.2) {$\scriptstyle 4$};
\node at (4/2,-.2) {$\scriptstyle 3$};
\draw (1) .. controls (1.5/2,.75) and (2.5/2,.75) .. (3);
\draw [densely dotted] (2) .. controls (2.5/2,.75) and (3.5/2,.75) .. (4);
%\draw [densely dotted] (1) .. controls (1.7/2,1) and (3.3/2,1) .. (4);
\draw (3) .. controls (3.25/2,.5) and (3.75/2,.5) .. (4);
\end{tikzpicture}
$$
where the dotted arcs correspond to the removed edges. Then we get $$c(G)=c(G|_{124})\cdot c(G|_3)=(1)\cdot(-1)$$
where the first equality comes from Lemma~\ref{le:shortedge} and the second equality follows by Lemma~\ref{le:fixshape} since the only fixed point adding up to $c(G|_{124})$ is the composition $(1,24)$, which contributes to 1; similarly, the only fixed point adding up to $c(G|_3)$ is the composition $(3)$ which contributes to $(-1)$.
For different $\tau$'s in this example, we get a decomposible graph and Lemma~\ref{le:decomposible} gives us $c(G_{1234,x/\epsilon}^{\tau,\epsilon})=0$ in those cases. For example,
$$G_{1234,x/\epsilon}^{1342,\epsilon}=
\begin{tikzpicture}[baseline=.2cm]
\foreach \x in {1,2,3,4}
\node (\x) at (\x/2,0) [inner sep=-1pt] {$\bullet$};
\node at (1/2,-.2) {$\scriptstyle 1$};
\node at (2/2,-.2) {$\scriptstyle 3$};
\node at (3/2,-.2) {$\scriptstyle 4$};
\node at (4/2,-.2) {$\scriptstyle 2$};
\draw [densely dotted](1) .. controls (1.5/2,1) and (3.5/2,1) .. (4);
\draw [densely dotted] (2) .. controls (2.5/2,.75) and (3.5/2,.75) .. (4);
\draw (3) .. controls (3.25/2,.5) and (3.75/2,.5) .. (4);
\end{tikzpicture} .
$$
Removing the dotted arcs produce a decomposible graph; hence the result is zero. The only permutations
$\tau$ that will contribute non-trivially are $1243, 2341, 3124,4321$ with signs $-1,-1,-1,1$ respectively.
Hence the coefficient of $\epsilon$ in $S(x)$ is $-1-1-1+1=-2$.
\end{exam}
%%%%%%%%%%%%%%
%% Acyclic orientation of Hypergraphs
%%%%%%%%%%%%%%
\subsection{\texorpdfstring{$c_x^y$}{cxy} as a signed sum of acyclic orientations of simple hypergraphs.}\label{subsec:acyclic} We now turn to Theorem~\ref{thm:antiH} to get an antipode formula for $c_x^y$ as a signed sum of acyclic orientations of the hypergraph $G_x^y$. When $G_x^y$ is a graph, then we will recover the formula of Humpert and Martin~\cite{Humpert-Martin}. If $G_x^y$ is an arbutrary hypergraph, then the antipode formula may still have cancellation but, in sequel work~\cite{BBM:2017}, we make sense of this formula geometrically.
%and get that the antipode compute the homology of certain connected component on the hypergraphic nestohedron.
Recall that $G_x^y$ is a hypergraph on the vertex set $[m]$ as defined in Equation~\eqref{eq:Gcom}. The ordering of the vertex set depends on a fixed choice of minimal element in $\mathcal{C}_x^y$.
\begin{defi}[Orientation] Given a hypergraph $G$ an \emph{orientation} $(\mathfrak{a},\mathfrak{b})$ of a hyperedge $U\in G$ is a choice of two nonempty subsets $\mathfrak{a},\mathfrak{b}$ of $U$ such that $U=\mathfrak{a}\cup\mathfrak{b}$ and $\mathfrak{a}\cap\mathfrak{b}=\emptyset$. We can think of the orientation of a hyperedge $U$ as current or flow on $U$ from a single vertex of $\mathfrak{a}$ to the vertices in $\mathfrak{b}$ in which case we say that $\mathfrak{a}$ is the \emph{head} of the orientation $\mathfrak{a}\rightarrow\mathfrak{b}$ of $U$.
If $|U|=n$, then there are a total of $2^{n}-2$ possible orientations. An \emph{orientation of $G$} is an orientation of all its hyperedges. Given an orientation $\mathcal{O}$ on $G$, we say that $(\mathfrak{a},\mathfrak{b})\in\mathcal{O}$ if it is the orientation of a hyperedge $U$ in $G$.
\end{defi}
\begin{exam}\label{hypergraph}
With $G=\big\{\{b,c\},\redun{\{a,b,e\}},\blueun{\{a,d,e,f\}},\greenun{\{b,c,e\}},\{f,c\}\big\}$, we can orient the edge $U=\{a,b,e\}$ in $2^3-2=6$ different ways; three with a head of size 1: $(\{a\},\{b,e\})$, $(\{b\},\{a,e\})$, $(\{e\},\{a,b\})$, and three with a head of size 2: $(\{b,e\},\{a\})$, $(\{a,e\},\{b\})$, $(\{a,b\},\{e\})$. We represent this graphically as follows:
$$
\begin{tikzpicture}[scale=1.2,baseline=.5cm]
\node (a) at (0,0) {$\scriptstyle a$};
\node (b) at (1,.1) {$\scriptstyle b$};
\node (e) at (.6,1.2) {$\scriptstyle e$};
\draw [thick,color=red,->] (.1,.1) .. controls (.5,.3) .. (.9,.2) ;
\draw [thick,color=red,<-] (.6,1) .. controls (.5,.5) .. (.1,.1) ;
\end{tikzpicture} ,\
\begin{tikzpicture}[scale=1,baseline=.5cm]
\node (a) at (0,0) {$\scriptstyle a$};
\node (b) at (1,.1) {$\scriptstyle b$};
\node (e) at (.6,1.2) {$\scriptstyle e$};
\draw [thick,color=red,->] (.9,.2) .. controls (.65,.6) .. (.6,1);
\draw [thick,color=red,<-] (.1,.1) .. controls (.5,.3) .. (.9,.2) ;
\end{tikzpicture} ,\
\begin{tikzpicture}[scale=1,baseline=.5cm]
\node (a) at (0,0) {$\scriptstyle a$};
\node (b) at (1,.1) {$\scriptstyle b$};
\node (e) at (.6,1.2) {$\scriptstyle e$};
\draw [thick,color=red,->] (.6,1) .. controls (.5,.5) .. (.1,.1);
\draw [thick,color=red,<-] (.9,.2) .. controls (.65,.6) .. (.6,1) ;
\end{tikzpicture} ,\
\begin{tikzpicture}[scale=1,baseline=.5cm]
\node (a) at (0,0) {$\scriptstyle a$};
\node (b) at (.8,.8) {$\scriptstyle be$};
\draw [thick,color=red,->] (b) -- (a);
\end{tikzpicture} ,\
\begin{tikzpicture}[scale=1,baseline=.5cm]
\node (a) at (1,.1) {$\scriptstyle b$};
\node (b) at (.3,.9) {$\scriptstyle ae$};
\draw [thick,color=red,->] (b) -- (a);
\end{tikzpicture} ,\
\begin{tikzpicture}[scale=1,baseline=.5cm]
\node (a) at (.6,1.2) {$\scriptstyle e$};
\node (b) at (.5,0) {$\scriptstyle ab$};
\draw [thick,color=red,->] (b) -- (a);
\end{tikzpicture}.
$$
To orient $G$, we have to make a choice of orientation for each hyperedge. For example we can choose
$\mathcal{O}=\big\{(\{b\},\{c\}),\redun{(\{a\},\{b,e\})},\blueun{(\{a,e\},\{d,f\})},\greenun{(\{b,c\},,\{e\})},(\{f\},\{c\})\big\}$ and we represent this
as
$${ G/\mathcal{O}}=
\begin{tikzpicture}[scale=1.2,baseline=.5cm]
\node (a) at (.3,.5) {$\scriptstyle ae$};
\node (b) at (1.5,.1) {$\scriptstyle bc$};
\node (d) at (-.5,1) {$\scriptstyle d$};
\node (f) at (0,1.5) {$\scriptstyle f$};
\draw [thick,color=red,->] (.4,.4).. controls (.5,.3) and (.5,-.1)..(.3,-.1) .. controls (.1,-.1) and (.1,.1).. (.3,.3);
\draw [thick,color=red,->] (.4,.4) -- (b);
\draw [thick,color=green!60!black,->] (b).. controls (.9,.6) .. (.45,.55);
\draw [thick,color=blue,->] (.2,.6).. controls (-.1,.8) .. (d);
\draw [thick,color=blue,->] (.2,.6).. controls (-0.1,1) .. (f);
\draw [thick,->] (f) .. controls (1.5,1.3) .. (b);
\draw [thick,->] (1.7,.1) .. controls (1.8,-.1) and (2.2,-.1) ..(2.2,.2) .. controls (2.2,.5) and (1.8,.3).. (1.7,.2);
\end{tikzpicture}
$$
\end{exam}
In general, given a hypergraph $G$ on the vertex set $V$ and an orientation $\mathcal{O}$ of $G$, we construct an oriented (not necessarily simple) graph $G/\mathcal{O}$ as follows.
We let $V/\mathcal{O}$ be the finest equivalence class of elements of $V$ defined by the heads of $\mathcal{O}$.
That is, the transitive closure of the relation $a\sim a'$ if $a,a'\in \mathfrak{a}$ for some head $\mathfrak{a}$ of $\mathcal{O}$.
For each oriented hyperedge $(\mathfrak{a},\mathfrak{b})$ of $\mathcal{O}$, we have $|\mathfrak{b}|$ oriented edges $([\mathfrak{a}],[b])$ in $G/\mathcal{O}$
where $[\mathfrak{a}],[b]\in V/\mathcal{O}$ are equivalence classes and $b\in \mathfrak{b}$.
\begin{defi}[Acyclic orientation] An orientation $\mathcal{O}$ of $G$ is \emph{acyclic} if the oriented graph $G/\mathcal{O}$ has no cycles.
\end{defi}
\begin{exam}\label{ex:124_234}
Let $G=\big\{\blueun{\{1,2,4\}},\redun{\{2,3,4\}}\big\}$ be a hypergraph on $V=\{1,2,3,4\}$. As we can see the orientations $\mathcal{O}=\big\{\blueun{ (\{4\},\{1,2\})},\redun{(\{2,4\},\{3\})}\big\}$ and $\mathcal{O}'=\big\{ \blueun{(\{4\},\{1,2\})},$ $\redun{(\{2,3\},\{4\})}\big\}$ are not acyclic, but $\mathcal{O}''=\big\{\blueun{ (\{4\},\{1,2\})},\redun{(\{4\},\{2,3\})}\big\}$ is acyclic:
$$
\begin{array}{cccc}
\begin{tikzpicture}[scale=.9,baseline=.2cm]
\node (a) at (0,0) {$\scriptstyle 2$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (d) at (-.5,1) {$\scriptstyle 3$};
\node (e) at (.6,1.2) {$\scriptstyle 4$};
\draw [fill=blue!40] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ;
\draw [fill=red!40] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ;
\end{tikzpicture}\quad &
\begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (a) at (.3,.6) {$\scriptstyle 24$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (d) at (-.5,1) {$\scriptstyle 3$};
\draw [thick,color=blue,->] (.4,.4).. controls (.5,.3) and (.5,-.1)..(.3,-.1) .. controls (.1,-.1) and (.1,.1).. (.3,.3);
\draw [thick,color=blue,->] (.4,.4).. controls (.5,.3) ..(.9,.1);
\draw [thick,color=red,->] (.1,.7)--(-.4,1);
\end{tikzpicture} \quad&
\begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (a) at (0,0) {$\scriptstyle 23$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (e) at (.6,1.2) {$\scriptstyle 4$};
\draw [thick,color=blue,->] (.6,1) .. controls (.5,.5) .. (.1,.1) ;
\draw [thick,color=blue,<-] (.9,.2) .. controls (.65,.6) .. (.6,1) ;
\draw [thick,color=red,<-] (.5,1) .. controls (.1,.6) .. (0,.15) ;
\end{tikzpicture} \quad&
\begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (a) at (0,0) {$\scriptstyle 2$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (d) at (-.5,1) {$\scriptstyle 3$};
\node (e) at (.6,1.2) {$\scriptstyle 4$};
\draw [thick,color=blue,->] (.6,1) .. controls (.5,.5) .. (.1,.1) ;
\draw [thick,color=blue,<-] (.9,.2) .. controls (.65,.6) .. (.6,1) ;
\draw [thick,color=red,->] (.5,1) .. controls (.1,.6) .. (0,.15) ;
\draw [thick,color=red,<-] (-.35,1) .. controls (.1,.8) .. (.5,1) ;
\end{tikzpicture} \quad\\
G&G/\mathcal{O}&G/\mathcal{O}'&G/\mathcal{O}''\\
\end{array}
$$
Out of the possible 36 orientations of $G$ only 20 are acyclic:
$$
\begin{gathered}
\begin{array}{c}
% \scriptstyle
\{ (\{4\},\{1,2\}),(\{4\},\{2,3\})\};\quad \{ (\{4\},\{1,2\}),(\{3\},\{2,4\})\};\\[1pt]
% \scriptstyle
\{ (\{2\},\{1,4\}),(\{2\},\{3,4\})\};\quad \{ (\{2\},\{1,4\}),(\{2,3\},\{4\})\};\\[1pt]
%\scriptstyle
\{ (\{1\},\{2,4\}),(\{2\},\{3,4\})\};\quad\{ (\{1\},\{2,4\}),(\{2,3\},\{4\})\};\\[1pt]
%\scriptstyle
\{ (\{1,2\},\{4\}),(\{3\},\{2,4\})\};\quad\{ (\{1,2\},\{4\}),(\{2\},\{3,4\})\};\\[1pt]
%\scriptstyle
\{ (\{1,4\},\{2\}),(\{3\},\{2,4\})\};\quad\{ (\{1,4\},\{2\}),(\{3,4\},\{2\})\};
\end{array}
%%%%%%%%%%%%%
\\[6pt]
%%%%%%%%%%%%%
\begin{array}{c}
% \scriptstyle
\{ (\{4\},\{1,2\}),(\{3,4\},\{2\})\};\quad \{ (\{2\},\{1,4\}),(\{3\},\{2,4\})\};\\[1pt]
% \scriptstyle
\{ (\{1\},\{2,4\}),(\{4\},\{2,3\})\};\quad\{ (\{1\},\{2,4\}),(\{3\},\{2,4\})\};\\[1pt]
%\scriptstyle
\{ (\{1\},\{2,4\}),(\{2,4\},\{3\})\};\quad\{ (\{1\},\{2,4\}),(\{3,4\},\{2\})\};\\[1pt]
%\scriptstyle
\{ (\{1,2\},\{4\}),(\{2,3\},\{4\})\};\quad\{ (\{1,4\},\{2\}),(\{4\},\{2,3\})\};\\[1pt]
%\scriptstyle
\{ (\{2,4\},\{1\}),(\{3\},\{2,4\})\};\quad\{ (\{2,4\},\{1\}),(\{2,4\},\{3\})\}.
\end{array}
\end{gathered}
$$
\end{exam}
Our next lemma will show that for every set composition $A\in \mathcal{C}_{x}^{y}$ there is a unique acyclic orientation of $G_x^y$. Conversely for any acyclic orientation there is a least one $A=(A_1,A_2,\ldots, A_\ell)\in \mathcal{C}_{x}^{y}$ that gives that orientation. Denote by $\mathfrak{O}_x^y$ the set of acyclic orientations of $G_x^y$, and consider the following surjective
map $\Omega\colon \mathcal{C}_{x}^{y} \to \mathfrak{O}_x^y$.
For any $1\le i\le\ell$, let $A_{i,\ell}=A_i\cup A_{i+1}\cup\cdots\cup A_\ell$ and let $G/\mathcal{O}_{i,\ell}$ be the restriction of $G/\mathcal{O}$ to the set $A_{i,\ell}$.
\begin{lemma}\label{lem:Omega}
Let $x,y\in \mathbf{h}[I]$ and let $G_x^y$ be the hypergraph on $V=[m]$ as defined before. The map $\Omega\colon \mathcal{C}_{x}^{y} \to \mathfrak{O}_x^y$ defined as follows is surjective:
\begin{enumerate} [(a)]%\alphenumi
\item %[(a)]
\label{lemma3.15_a} For any $A=(A_1,A_2,\ldots, A_\ell)\in \mathcal{C}_{x}^{y}$ let $\Omega(A)$ be the unique element in $\mathfrak{O}_x^y$ such that for any $U\in G_x^y$ the orientation of $U$ is given by $(U\cap A_i,U\setminus A_i)$ where
$i=\min\{j: A_j\cap U\ne \emptyset\}.$
\item %[(b)]
\label{lemma3.15_b} For any $\mathcal{O}\in \mathfrak{O}_x^y$, there is a unique $A_\mathcal{O}=(A_1,A_2,\ldots, A_\ell)\in \mathcal{C}_{x}^{y}$ such that $\{A_1,A_2,\ldots, A_\ell\}=V/\mathcal{O}$ and $A_i$ is the unique source of the restriction $G/\mathcal{O}_{i,\ell}$ such that $\min(A_i)$ is maximal among the sources of $G/\mathcal{O}_{i,\ell}$. Thus, $\Omega(A_{\mathcal{O}})=\mathcal{O}$.
\end{enumerate}
Moreover, $V/{\Omega(A)}$ is a refinement of $\{A_1,A_2,\ldots,A_\ell\}$.
\end{lemma}
\begin{proof}
For part~\ref{lemma3.15_a}, let $A=(A_1,A_2,\ldots,A_\ell)\in \mathcal{C}_{x}^{y}$. From Theorem~\ref{thm:hyper}, we have that $A$ must break every hyperedge of $G_x^y$. In particular, for any part $A_i$ of $A$ and $U\in G_x^y$, we always have $A_i\cap U\ne U$.
Hence $(U\cap A_i,U\setminus A_i)$ for $i=\min\{j: A_j\cap U\ne \emptyset\}$ defines a proper orientation of each edge of $G_x^y$.
Thus we obtain an orientation $\mathcal{O}$ of $G_x^y$. By construction, each head $\mathfrak{a}$ of $\mathcal{O}$ is completely included within a part $A_i$ for a unique part $1\le i\le \ell$. This implies that $V/\mathcal{O}$ refines $\{A_1,\ldots,A_\ell\}$ and it allows us to define a function $f\colon V/\mathcal{O}\to \{1,2,\ldots,\ell\}$ where $f([a])=i$ if and only if $[a]\subseteq A_i$.
By the way $\mathcal{O}$ is constructed we have that for any $([a],[b])\in G_x^y/\mathcal{O}$ the function $f$ is such that $f([a])i\,.$$
If this were not the case, then there would be $j***i$.
\end{proof}
\begin{theorem} \label{thm:anticoco}
For any $x,y\in \mathbf{h}[I]$ such that $\mathcal{C}_{x}^{y}\ne\emptyset$ we have
$$c_x^y=\sum_{\mathcal{O} \in \mathfrak{O}_x^y} (-1)^{\ell{(A_{\mathcal{O}}})} \,.$$
\end{theorem}
\begin{proof}
Our proof will be similar to the one appearing in~\cite{Bergeron-Ceballos}. First we use the surjective map $\Omega$ from Lemma~\ref{lem:Omega} to decompose the formula~\eqref{eq:cxycocom}
$$c_x^y=\sum_{B\in \mathcal{C}_{x}^{y}} (-1)^{\ell(B)} = \sum_{\mathcal{O} \in \mathfrak{O}_x^y}\left(\sum_{\stackrel{B\in \mathcal{C}_{x}^{y}}% \atop
{\Omega(B)=\mathcal{O}}} (-1)^{\ell(B)}\right)\,.$$
For any fixed orientation $\mathcal{O}$, we thus have to show
$$ \sum_{\stackrel{B\in \mathcal{C}_{x}^{y}} % \atop
{\Omega(B)=\mathcal{O}}} (-1)^{\ell(B)} = (-1)^{\ell(A_{\mathcal{O}})} \,.$$
Let $\mathcal{C}_{x,\mathcal{O}}^{y}=\{B \in \mathcal{C}_{x}^{y}: \Omega(B)=\mathcal{O}\}$.
As in~\cite{Benedetti-Sagan,Bergeron-Ceballos}, we construct a sign reversing involution $\varphi\colon \mathcal{C}_{x,\mathcal{O}}^{y}\to \mathcal{C}_{x,\mathcal{O}}^{y}$ such that
\begin{enumerate}[(A)]
% (A)
\item\label{proof_theo3.16A}
$\varphi(A_\mathcal{O})=A_{\mathcal{O}}$ is the only fixed point,
% (B)
\item\label{proof_theo3.16B} for $B\ne A_{\mathcal{O}}$, we have $\ell(\varphi(B))=\ell(B)\pm 1$.
\end{enumerate}
\noindent If $B\ne A_{\mathcal{O}}$, then we have from Lemma~\ref{lem:Omega} that each part of $A_{\mathcal{O}}$ is included in a part of $A$. Let $A_{\mathcal{O}}=(A_1,A_2,\ldots,A_\ell)$ and $B=(B_1,B_2,\ldots,B_k)$. We define
$$f_B\colon \{A_1,A_2,\ldots,A_\ell\}\to \{ B_1,B_2,\ldots,B_k\}$$
as the function such that $A_i\subseteq f(A_i)$. Since $B \ne A_{\mathcal{O}}$, we have that $f_B\ne Id$.
Find the smallest $i$ such that $f_B^{-1}(B_i)\ne\{A_i\}$.
Let $G/\mathcal{O}_{i,\ell}$ be the restriction of $G/\mathcal{O}$ to the set $A_{i,\ell}$.
All the elements in $f^{-1}_B(B_i)$ are sources in the graph $G/\mathcal{O}_{i,\ell}$.
By Lemma~\ref{lem:Omega}(b), we have that $\min(A_i)$ is the largest among the sources of $G/\mathcal{O}_{i,\ell}$.
Since $f^{-1}_B(B_i)\ne\{A_i\}$, there must be a source $A_r \in f^{-1}_B(i)$ such that $\min(A_r)<\min(A_i)$.
Let $X\in f^{-1}_B(B_i)$ be such that $\min(X)<\min(A_r)$ for all $A_r\in f^{-1}_B(B_i)$.
We then find the smallest $j\ge i$ such that $A_r\in f^{-1}_{B}(B_j)$ is a source of $G/\mathcal{O}_{i,\ell}$ and $\min(A_r)>\min(X)$.
Such $j$ exists since $G/\mathcal{O}_{i,\ell}$ contain at least one source, namely $A_i$, such that $\min(A_i)>\min(X)$.
We let
$$U=\left\{ Z\in f^{-1}_{B}(B_j) : \begin{aligned}[t]
\exists \text{$Y$ a source of } G/\mathcal{O}_{i,\ell},\text{ a path } &\text{from } Y \text{ to } X\\ %\atop
&\text{ and } \min(Y)\le \min(X)
\end{aligned}
\right\}.$$
If $U=\emptyset$, then $j>i$ since $X\not\in U$.
In this case we remark that our choice of $j$ implies that for all $A_r\in f^{-1}_{B}(B_j)$, the element $A_r$ is connected to a source $Y$ where $\min(Y)\le \min(X)$.
Hence, there is no edge $(Y,X)$ in $G/\mathcal{O}_{i,\ell}$ where $Y\in f^{-1}_{B}(B_{j-1})$ and $X\in f^{-1}_{B}(B_j)$.
If $U=\emptyset$, then we define
\begin{equation}\label{a_merge}
\varphi(B)= (B_1,\ldots,B_{j-2},B_{j-1}\cup B_{j},B_{j+1},\ldots,B_k).
\end{equation}
Let $B'= \varphi(B)$. It is clear that $ \varphi(B)={B}'\in \mathcal{C}_{x,\mathcal{O}}^{y}$ with $\ell({B'})=\ell({B})-1$.
Moreover
$$f^{-1}_{B'}(B'_r)= \begin{cases}
f^{-1}_{B}(B_r) &\text{ if $rj-1$.}\cr
\end{cases}$$
Repeating the procedure above for ${B}'$ we will obtain $i',X',j',U'$ in such a way that $i'=i$, $X'=X$, $j'=j-1$ and $U'=f^{-1}_{B}(B_{j-1})\ne\emptyset$.
Now we consider the case when $U\ne\emptyset$.
Reversing what we did, let $U^c=f^{-1}_{B}(B_j)\setminus U$.
All the $Z\in U$ are connected to a source $Y$ of $G/\mathcal{O}_{i,\ell}$ with value $\min(Y)\le \min(X)$.
Since there is no edge $e$ of $G/\mathcal{O}_{i,\ell}$ such that $e$ is incident to a vertex in $U$ and a vertex in $U^c$, then
\begin{equation}\label{a_split}
\varphi({B})={B}'= (B_1,\ldots,B_{j-1},\bigcup_{Z\in U} Z,\bigcup_{Z'\in U^c} Z',B_{j+1},\ldots,B_k).
\end{equation}
Remark that now $\ell({B'})=\ell({B})+1$.
Moreover
$$f^{-1}_{B'}(B_r)= \begin{cases}
f^{-1}_{B}(B_r) &\text{ if $rj+1$}\cr
\end{cases}$$
and for this ${B}'$ we will obtain $i',X',j',U'$ in such a way that $i'=i$, $X'=X$, $j'=j+1$ and $U'=\emptyset$. The map $ \varphi$ is thus the desired involution.
\end{proof}
\begin{exam}
Let us revisit Example~\ref{ex:twotriangles} in the Hopf monoid of hypergraphs. Let $x=\big\{\{1,2,4\},\{2,3,4\}\big\}$ be a hypergraph on the vertices $\{1,2,3,4\}$.
A full computation of the antipode gives us
$$S\Mk \left(
\begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (a) at (0,0) {$\scriptstyle 2$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (d) at (-.5,1) {$\scriptstyle 3$};
\node (e) at (.6,1.2) {$\scriptstyle 4$};
\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ;
\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ;
\end{tikzpicture}
\right) \Mk = \Mk - \Mk \left(\begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (a) at (0,0) {$\scriptstyle 2$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (d) at (-.5,1) {$\scriptstyle 3$};
\node (e) at (.6,1.2) {$\scriptstyle 4$};
\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ;
\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ;
\end{tikzpicture} \right)
+2\ \left( \begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (a) at (0,0) {$\scriptstyle 2$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (d) at (-.5,1) {$\scriptstyle 3$};
\node (e) at (.6,1.2) {$\scriptstyle 4$};
%\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ;
\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ;
\end{tikzpicture} \right)
+2\ \left(\begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (a) at (0,0) {$\scriptstyle 2$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (d) at (-.5,1) {$\scriptstyle 3$};
\node (e) at (.6,1.2) {$\scriptstyle 4$};
\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ;
%\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ;
\end{tikzpicture} \right)
-2\ \left(\begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (a) at (0,0) {$\scriptstyle 2$};
\node (b) at (1,.1) {$\scriptstyle 1$};
\node (d) at (-.5,1) {$\scriptstyle 3$};
\node (e) at (.6,1.2) {$\scriptstyle 4$};
%\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ;
%\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ;
\end{tikzpicture} \right)\Mk\mk.
$$
The coefficient $-2$ in front of the empty hypergraph $\epsilon$ was computed in Example~\ref{ex:twotriangles} using $4!$ permutations.
Here we do so by means of Theorem~\ref{thm:antiH} and the 20 acyclic orientations of Example~\ref{ex:124_234}.
Lemma~\ref{lem:Omega}~(b) tells us that each of those orientations is paired with one of the following 20 set compositions (respectively)
$$ \begin{array}{l@{\quad}l@{\quad}l@{\quad}l}
% \scriptstyle
(4,3,2,1);%\quad
&(3,4,2,1);%\quad
&(34,2,1);%\quad
&(3,2,4,1);\\
% \scriptstyle
(2,4,3,1);%\quad
&(23,4,1);%\quad
&(1,4,3,2);%\quad
& (3,1,4,2);\\
%\scriptstyle
(1,2,4,3);%\quad
&(1,23,4);%\quad
&(1,24,3);%\quad
&(1,34,2);\\
%\scriptstyle
(3,12,4);%\quad
& (12,4,3);%\quad
&(123,4);%\quad
&(14,3,2);\\
%\scriptstyle
(3,14,2);%\quad
& (134,2);%\quad
& (3,24,1);%\quad
& (24,3,1).
\end{array}$$
There are $9$ even length set compositions in this list and $11$ odd length. The coefficient is indeed $9-11=-2$.
For the coefficient of $x$ in $S(x)$, we remark that $x/x$ is a single point with no edges. There is a unique orientation of $x/x$
and it is represented by a set composition with a single part. Thus the coefficient is $-1$. For $y=\big\{\{1,2,4\}\big\}$,
$x/y$ is a graph on two vertices, say $u$ and $v$, with a single edge between them and thus it has two acyclic orientations, which correspond to the set compositions $(u,v),\,(v,u)$. Hence the coefficient is $2$. The same argument applies for $y'=\big\{\{2,3,4\}\big\}$.
\end{exam}
%%%%%%%%%%%%%%
%% Applications ???
%%%%%%%%%%%%%%
\section{Some applications with Hopf algebras}\label{s:HopfAlgebras}
In this section, we will consider some examples of antipodes corresponding to some combinatorial Hopf algebras. We recover results from~\cite{Aguiar-Ardila,BakerJarvisBergeronThiem,BenedettiHallamMachacek, Benedetti-Sagan, Humpert-Martin}, and derive some new formulas.
%%%%%%%%%%%%%%
%% Commutative case
%%%%%%%%%%%%%%
\subsection{Antipode in the commutative case \texorpdfstring{$H=\Kcb(\bH)$}{H=overline K(H)}}\label{ss:anticom} We now consider some commutative and cocommutative Hopf monoid $\bH$ and look at the antipode of $H=\Kcb(\bH)$.
\begin{exam} Consider the Hopf monoid $\bPi$ in Section~\ref{ss:partition} and the basis $\bpi$. Given a set partition $X\in{\bpi}[I]$
and any set composition $A\models I$ we have that $X_A=X$ if a permutation of $X$ refines $A$, and $X_A=0$ otherwise. This means that the only term in $S(X)$ is $X$
and its coefficient is $c_X^X$. A minimal $\Lambda$ in $\mathcal{C}_X^X$ is $X$ with some ordering of its parts. The hypergraph $G_X^X$ has $m=|X|$ vertices
and no hyperedges. If we use Theorem~\ref{thm:anticoco}, there is a unique orientation of $G_X^X$ and its sign is $(-1)^m$.
If instead we use Proposition~\ref{lem:Cxydecomp}, we sum over the permutations $\tau$ of $m$ where $G_{12\cdots m,\epsilon}^{\tau,\epsilon}$ has only short edges $(i,i+1)$
for each descent $\tau(i)>\tau(i+1)$ of $\tau$. This graph is decomposible unless $\tau=(m,m-1,\ldots,2,1)$ for which $c(G_{12\cdots m,\epsilon}^{\tau,\epsilon})=(-1)^m$.
The Hopf algebra $\Kcb(\bPi)$ is the space of symmetric functions $Sym$ and the basis element $\Kcb(X)=p_{type(X)}$ is the power sum basis where $type(X)=(|X_1|,|X_2|,\ldots,|X_m|)$ written in non-increasing order. This gives the well known antipode formula $S(p_\lambda)=(-1)^{\ell(\lambda)}p_{\lambda}$.
\end{exam}
\begin{exam} \label{ex:graphdone}
Consider the Hopf monoid $\bG$ from Section~\ref{ss:graph} with basis $\mathbf g$. Given a graph $x\in{\mathbf g}[I]$
and $A\models I$ we have that $x_A=y$ is a subgraph of $x$ and in fact, subgraphs $y$ obtained in this way are also known as flats of $x$.
A minimal element $\Lambda$ in $\mathcal{C}_x^y$ is given by any ordering of the equivalence relation $I/y$ where $a,b\in I$ are equivalent whenever there is a path in $y$ connecting them.
The hypergraph $G_x^y$ is the simple graph $x/y$, obtained by contracting $x$ along the edges of $y$. It is a graph on the vertex set $V=I/y$ and edges $\{[a],[b]\}$ whenever $[a]\ne [b]$ and there is an edge $\{a',b'\}$ in $x$ such that $a'\in[a]$ and $b'\in[b]$. Since $G_x^y$ has no hyperedges $U$ such that $|U|>2$, all orientations $\mathcal{O}$ of $G_x^y$
are such
that $V/\mathcal{O}=V$, since the head of each edge has cardinality 1. Hence in Theorem~\ref{thm:anticoco} we have that $\ell(A_{\mathcal{O}})=|V|=|I/y|$ for each $\mathcal{O}$.
No cancellation occurs and we recover the formula in~\cite{Benedetti-Sagan,Humpert-Martin}.
\end{exam}
\begin{exam} \label{ex:simplicial}
We can extend the previous example to a Hopf monoid $\mathbf{SC}$ of abstract simplicial complexes. A simplicial complex on a set $I$ is a collection $x\in 2^I$ such that
$$V\in x \implies U\in x,\;\;\;\; \forall U\subseteq V,\; |U|>1.$$
In this way, simplicial complexes extend the notion of graphs and it is a subfamily of hypergraphs. Now let $\mathbf{sc}[I]$ be the linear span of all simplicial complexes on $I$.
The product and coproduct of $\mathbf{HG}$, as defined in~\ref{ss:hypergraph}, restricts well to $\mathbf{SC}$. Hence, $\mathbf{SC}$ is a monoid of abstract simplicial complexes
with basis $\mathbf{sc}$.
Given $x\in{\mathbf {sc}}[I]$ and any set composition $A\models I$ we have that $x_A=y$ is a simplicial subcomplex of $x$.
A minimal element $\Lambda$ in $\mathcal{C}_x^y$ is given by any ordering of the equivalence relation $I/y$ where $a,b\in I$ are equivalent whenever there is a path in $y$ connecting them.
The hypergraph $G_x^y$ is the simple graph given by the 1-skeleton of $x/y$, where $x/y$ is obtained by contracting $x$ along the all hyperedeges of $y$. It is a graph on the vertex set $V=I/y$ and edges $\{[a],[b]\}$ whenever $[a]\ne [b]$ and there is an edge $\{a',b'\}$ in $x$ such that $a'\in[a]$ and $b'\in[b]$. Since $G_x^y$ is a simple graph, all orientations $\mathcal{O}$ of $G_x^y$
are such
that $V/\mathcal{O}=V$. Hence Theorem~\ref{thm:anticoco} gives $\ell(A_{\mathcal{O}})=|V|=|I/y|$ for each $\mathcal{O}$.
No cancellation occurs and we recover the formula of~\cite{BenedettiHallamMachacek}.
\end{exam}
\begin{rema} \label{ex:Hyper}
As seen in Examples~\ref{ex:graphdone} and~\ref{ex:simplicial}. the antipode formula in the Hopf monoid $\mathbf{SC}$ is a lifting of the antipode of $\bG$. Thus, it is natural to ask if such a lifting can be done to find an antipode formula in $\mathbf{HG}$. This case, however, is more intricate as lots of cancellation occur in Theorem~\ref{thm:anticoco}. Many of these cancellations are resolved
in~\cite{BenedettiHallamMachacek}.
\end{rema}
\begin{exam} \label{ex:Hypertree} (suggested to us by J. Machacek)
Given a hypergraph $G$, we say that $a_0{\buildrel U_1\over \longrightarrow}a_1{\buildrel U_2\over \longrightarrow}\cdots
{\buildrel U_\ell\over \longrightarrow}a_\ell$ is a \emph{path} of $G$ if $a_{i-1}\ne a_i$ and $\{a_{i-1},a_{i}\}\subset U_i\in G$ for each $1\le i\le \ell$.
We say that a path is \emph{proper} if all the hyperedges $U_i$ are distinct.
A proper cycle in $G$ is a proper path such that $a_0=a_\ell$.
A hypergraph is a \emph{hyperforest} if it does not contain proper cycles.
Let us consider the family of \emph{hyperforests}.
Let $\mathbf{hf}[I]$ be the set of hyperforest on $I$.
It is not hard to check that the operations of $\mathbf{HG}$ restrict properly in the subset of hyperforests.
Hence we have $\mathbf{HF}$ the hopf submonoid of hyperforests of $\mathbf{HG}$ with basis $\mathbf{hf}$.
Given a $x\in{\mathbf hf}[I]$ and any set composition $A\models I$ we have that $f_A=h$ is a subforest of $f$.
A minimal element $\Lambda$ in $\mathcal{C}_f^h$ is given by any ordering of the equivalence relation $I/h$ where $a,b\in I$ are equivalent whenever there is a path in $h$ connecting them.
The hypergraph $G_f^h$ is the hyperforest given by $f/h$, the contraction of $f$ along all the hyperedeges of $h$.
Any two vertices of $G_f^h$ that are connected, will be so via a unique proper path.
Since it is a hyperforest, any orientation of $G_f^h$ is acyclic and will contribute to the computation of the coefficient in Theorem~\ref{thm:anticoco}.
\begin{prop} Let $k=|G_f^h|$ and $\ell$ be the number of connected components of $G_f^h$.~Then
$$c_f^h = \begin{cases}
(-1)^\ell (-2)^k& \text{if $\forall U\in G_f^h$ we have $|U|$ is even,}
\\
0& \text{otherwise.}
\end{cases}
$$
\end{prop}
\begin{proof} We give a proof based on a sign reversing involution on acyclic orientation of $G_f^h$. As in Theorem~\ref{thm:anticoco} let $\mathfrak{O}_f^h$ denote the set of acyclic orientation of $G_f^h$. As we remarked above, for a hyperforest, these are all the orientations of $G_f^h$.
Recall from Section~\ref{subsec:acyclic} that $G_f^h$ is thought of as a hypergraph (here a hyperforest) on $V=[m]$.
We now define
a sign reversing involution $\Phi\colon \mathfrak{O}_f^h\to \mathfrak{O}_f^h$.
Given an orientation $\mathcal{O}$ of $G_f^h$,
if possible, find the largest element $z\in V$ such that for some $(\mathfrak{a},\mathfrak{b})\in \mathcal{O}$ we have $z=\max(\mathfrak{a}\cup \mathfrak{b})$ and
\begin{equation}\label{eq:thezcond}
( z\in \mathfrak{a}, \quad |\mathfrak{a}|>1 )\quad \text{or} \quad ( z\in \mathfrak{b}, \quad |\mathfrak{b}|>1 ).
\end{equation}
Then choose $(\mathfrak{a},\mathfrak{b})\in \mathcal{O}$ such that $\mathfrak{a}\cup\mathfrak{b}$ is lexicographically maximal among the hyperedges that satisfy~\eqref{eq:thezcond}. We then define $\Phi(\mathcal{O})=\mathcal{O}'$ where $\mathcal{O}'$ is obtained from $\mathcal{O}$
after replacing $(\mathfrak{a},\mathfrak{b})$ by $(\mathfrak{a}\setminus\{z\},\mathfrak{b}\cup\{z\})$ if $z\in \mathfrak{a}$, or $(\mathfrak{a}\cup\{z\},\mathfrak{b}\setminus\{z\})$ otherwise. It is clear that $\Phi$ is an involution that toggles the maximal element of the orientation of a hyperedge between the two situations in~\eqref{eq:thezcond}. If no such $z$ exists, then define $\Phi(\mathcal{O})=\mathcal{O}$.
We now show that $\Phi$ reverses sign, except in its fixed points. First recall from Lemma~\ref{lem:Omega} that $\ell(A_{\mathcal{O}})=|V/\mathcal{O}|$.
Assume $\Phi(\mathcal{O})=\mathcal{O}'\ne \mathcal{O}$ and let $z$ and $(\mathfrak{a},\mathfrak{b})$ be as above.
In the situation where $z\in \mathfrak{a}$, we now have $(\mathfrak{a}\setminus\{z\},\mathfrak{b}\cup\{z\})\in\mathcal{O}'$ and the rest of the orientations are the same as in $\mathcal{O}$.
Since there exists a unique proper path between any two equivalent vertices in the
equivalent classes $[\mathfrak{a}]_{\mathcal{O}}$ containing $z$ in $V/\mathcal{O}$, this class will break in exactly two classes $[\mathfrak{a}\setminus \{z\}]_{\mathcal{O}'}$ and
$[\{z\}]_{\mathcal{O}'}$ in $V/\mathcal{O}'$. All the other classes of $V/\mathcal{O}$ and $V/\mathcal{O}'$ remain the same. Hence $(-1)^{\ell(A_{\mathcal{O}})}=-(-1)^{\ell(A_{\mathcal{O}'})}$
and $\Phi$ is sign reversing in this case. The argument in the other case is similar.
The involution $\Phi$ reduces the identity in Theorem~\ref{thm:anticoco} to
$$ c_f^h = \sum_{\stackrel{\mathcal{O}\in \mathfrak{O_f^h}} % \atop
{\Phi(\mathcal{O})=\mathcal{O}}} (-1)^{\ell(A_{\mathcal{O}})}.$$
To finish the proof, we need to describe the fixed points of $\Phi$. If there is no $z$ satisfying equation~\eqref{eq:thezcond}, then for all $(\mathfrak{a},\mathfrak{b})\in \mathcal{O}$ and $z=\max(\mathfrak{a}\cup \mathfrak{b})$ we have
\begin{equation}\label{eq:fixed}
\mathfrak{a}=\{z\} \quad \text{or} \quad \mathfrak{b}=\{z\},
\end{equation}
and the orientations $\mathcal{O}$ that satisfy~\eqref{eq:fixed} are the fixed points of $\Phi$. If $|G_f^h|=0$, so that $G_f^h$ has $m=\ell$ vertices and no hyperedges, then $c_f^h=(-1)^\ell$ as desired. If $|G_f^h|>0$, then let $U\in G_f^h$ be any fixed hyperedge. For instance, pick $U$ to be lexicographically maximal in $G_f^h$ and let $z=\max(U)$.
In any orientation of $G_f^h$ fixed by $\Phi$ we can toggle the orientation of $U$ between the two situations in~\eqref{eq:fixed} and still get a fixed point of $\Phi$.
That is, we can pair all the fixed point of $\Phi$ as $(\mathcal{O},\mathcal{O}')$ where $\mathcal{O}\ne\mathcal{O}'$ and they differ only by the orientation of $U=\mathfrak{c}\cup\{z\}$ with $(\mathfrak{c},\{z\})\in \mathcal{O}$ and $(\{z\},\mathfrak{c})\in \mathcal{O}'$. Using again the fact that there is at most a unique proper path between any vertices in $G_f^h$,
the elements of $\mathfrak{c}$ are in a single equivalence class in $V/\mathcal{O}$ and in distinct equivalent classes in $V/\mathcal{O}'$. Hence $|V/\mathcal{O}'|=|V/\mathcal{O}|+|U|-2$.
We now have
$$ c_f^h =
\sum_{\stackrel{\mathcal{O}\in \mathfrak{O_f^h}}{\Phi(\mathcal{O})=\mathcal{O}}}
(-1)^{\ell(A_{\mathcal{O}})}
= \sum_{(\mathcal{O},\mathcal{O}')} (-1)^{\ell(A_{\mathcal{O}})} (1+(-1)^{|U|}).
$$
Let us denote by $G_f^{h\cup U}$ the hyperforest obtained by contracting the hyperedge $U$ in $G_f^h$. There is a clear correspondence between the orientation $\mathcal{O}$ of $G_f^h$
and the orientation $\mathcal{O}''$ of $G_f^{h\cup U}$ together with an orientation of $U$. This is true only for hyperforest as there is a unique proper path between any two vertices.
We thus have
$$ c_f^h = \sum_{(\mathcal{O},\mathcal{O}')} (-1)^{\ell(A_{\mathcal{O}})} (1+(-1)^{|U|})
=- (1+(-1)^{|U|}) \sum_{\stackrel{\mathcal{O}''\in \mathfrak{O_f^{h\cup U}}}
%\atop
{\Phi(\mathcal{O}'')=\mathcal{O}''}} (-1)^{\ell(A_{\mathcal{O}''})}.
$$
The negative sign in the second equality comes from the fact that contracting $U$ joins together the classes $[z]_{\mathcal{O}}$ and $[\mathfrak{c}]_{\mathcal{O}}$.
We now have that
$ c_f^h = -(1+(-1)^{|U|}) c_f^{h\cup U} $. The proposition follows by induction. If $|U|$ is odd, then we get zero. If $|U|$ is even,
then we get a contribution of $-2$ for that edge and the induction ends with an empty hypergraph with the same number of connected component as $G_f^h$.
\end{proof}
\end{exam}
%%%%%%%%%%%%%%
%% Our formula for LxH in K(LxH)
%%%%%%%%%%%%%%
\subsection{Antipode of \texorpdfstring{$ \Kcb(\bL\times\bH) \cong \Kc(\bH)$}{ overline K(L times H)
approximately equal K(H)} for linearized \texorpdfstring{$\bH$}{H}}\label{s:KLxH}
As we noticed in Section~\ref{ss:K_Kbar} we have that $\Kcb(\bL\times\bH) \cong \Kc(\bH)$ for
any Hopf monoid $\bH$. Given $(\alpha,x)\in (\bL\times\bH)[n]_{S_n}$, the isomorphism is explicitly given by the map $(\alpha,x)\mapsto \bH[\alpha^{-1}](x)$ where $\alpha^{-1}\colon[n]\to[n]$
is the unique bijection such that $\alpha^{-1}(\alpha)=12\cdots n$ and $\bH[\alpha^{-1}](x)\in \bH[n]$ is the image of $x$ under the bijection $\bH[\alpha^{-1}]\colon \bH[n]\to\bH[n]$ obtained via the functor $\bH$.
Since $\Kcb$ preserves antipodes (see~\cite[Section~15.2]{AM:2010}), in the case where $\bH$ is linearized, Theorem~\ref{thm:antiLxP} gives us the following formula. For $x\in \bH[n]$
\begin{equation}\label{eq:SforKH}
S(x)= \sum_{(\beta,y)\in (\mathbf{l}\times\bh)[n]} c_{12\cdots n,x}^{\beta,y} \bH[\beta^{-1}](y) = \sum_{z\in\bh[n]}\Big( \sum_{\beta\in \mathbf{l}[n]} c_{12\cdots n,x}^{\beta, \bH[\beta](z)} \Big) z\,.
\end{equation}
Here we have identified the linear order $\beta\in\mathbf{l}[n]$ and the bijection $\beta=(\beta^{-1})^{-1}\colon[n]\to[n]$ in the notation $\bH[\beta](z)$. From Theorem~\ref{thm:antiLxP}
we have that the coefficients $c_{12\cdots n,x}^{\beta, \bH[\beta](z)}$ are $\pm 1$, but further cancellation may occur in Equation~\eqref{eq:SforKH}. It is not a cancellation free formula in most cases but it is definitely improves the computation compared to Takeuchi's formula.
\begin{exam} \label{ex:super}
Consider the Hopf monoid $\bPi$ from Section~\ref{ss:partition}. As seen in~\cite{BakerJarvisBergeronThiem}, the Hopf algebra $\Kc(\bPi)$ is the space of symmetric functions
in non-commutative variables. Our formula~\eqref{eq:SforKH} is cancellation free in this case as all the non-zero terms have the same sign (see Corollary~4.9 of~\cite{BakerJarvisBergeronThiem} for more details).
\end{exam}
\begin{exam} \label{ex:PR}
Consider now the Hopf monoid $\bL$ in Section~\ref{ss:order}. The Hopf algebra $PR=\Kc(\bL)$ was introduced by Patras-Reutenauer~\cite{PR:2004}
and is also studied under the name $R\Pi$ in~\cite{AM:2010}.
The antipode formula~\eqref{eq:SforKH} for $PR$ gives us that for $\alpha\in\mathbf{l}[n]$:
\begin{equation}\label{eq:SforKL}
S(\alpha)=\sum_{\gamma\in\mathbf{l}[n]}\Big( \sum_{\beta\in \mathbf{l}[n]} c_{\epsilon,\alpha}^{\beta, \beta\circ\gamma} \Big) \gamma\,
\end{equation}
where $\epsilon=12\ldots n$ is the identity permutation.
In this example, $\beta=(\beta_1,\ldots,\beta_n)\in \mathbf{l}[n]$ can be encoding three different objects depending on the context.
It is first the total order $\beta_1<\beta_2<\cdots<\beta_n$ on the points $1,2,\ldots,n$. In~\eqref{eq:SforKL}, when we write $\beta\circ\gamma$, we consider
$\beta$ as the permutation defined by $\beta(i)=\beta_i$. Hence $\beta\circ\gamma=(\beta(\gamma_1),\beta(\gamma_2),\ldots,\beta(\gamma_n))$.
Bellow we will consider $\beta$ and $\beta\circ\gamma$ as encoding the set composition $(\{\beta_1\},\ldots,\{\beta_n\})$ and $(\{\beta(\gamma_1)\},\ldots,\{\beta(\gamma_n)\})$.
These conventions should be clear from the context.
We now need a complete description of
$c_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}$ in order to understand (\ref{eq:SforKL}). The set $\mathcal{C}_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}\ne \emptyset$ if and only if the minimal element $\Lambda$ of $\mathcal{C}_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}$ exists and it is the finest set composition such that
\begin{enumerate}
\item $\beta\le\Lambda$ and $\beta$ is increasing with respect to $\epsilon$ within each part of $\Lambda$,
\item $\beta\circ\gamma\le\Lambda$ and $\beta\circ\gamma$ is increasing with respect to $\alpha$ within each part of $\Lambda$.
\end{enumerate}
These conditions follow from the proof of Lemma~\ref{le:min} in the case of $\bL\times\bL$.
Let $A=\beta\lor(\beta\circ\gamma)$ be the finest set composition such that $\beta\le A$ and $\beta\circ\gamma\le A$.
We must have that $A\le \Lambda$. Now, if $\beta$ is not increasing with respect to $\epsilon$ within each part of $A$, then it would not be increasing with respect to $\epsilon$ within each part of $\Lambda$ either. Similarly
if $\beta\circ\gamma$ is not increasing with respect to $\alpha$ within each part of $A$, then $\Lambda$ would not be increasing with respect to $\epsilon$ within each part of $A$ either. Hence we have that $\mathcal{C}_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}\ne \emptyset$ if and only if $\Lambda=\beta\lor(\beta\circ\gamma)$ is such that $\beta$ is increasing with respect to $\epsilon$ within each part of $\Lambda$ and $\beta\circ\gamma$ is increasing with respect to $\alpha$ within each part of $\Lambda$.
For instance, if $\alpha=(5,2,1,3,4)$, $\beta=(2,1,3,5,4)$ and $\beta\circ\gamma=(2,5,1,3,4)$, then we see that $\Lambda=\beta\lor(\beta\circ\gamma)=(2,135,4)$. The elements $1,3,5$ of $\beta$ are increasing with respect
to $\epsilon=(1,2,3,4,5)$ within the part $135$ of $\Lambda$. In $\beta\circ\gamma$ these elements are in the order $5,1,3$ which is increasing with respect to $\alpha$. Hence in this little example
$\mathcal{C}_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}\ne \emptyset$ and $\Lambda=(2,135,4)$ is the minimum. If we take a different $\gamma'$ so that $\beta\circ\gamma'=(2,5,3,1,4)$,
then $\Lambda=\beta\lor(\beta\circ\gamma')=(2,135,4)$ but the element $5,3,1$ are not in increasing order with respect to $\alpha$, hence $\mathcal{C}_{\epsilon,\alpha}^{\beta, \beta\circ\gamma'}= \emptyset$.
Now we remark that the number of parts of $\Lambda=\beta\lor(\beta\circ\gamma)$ depends only on $\gamma$ and not $\beta$. This follows from the simple fact that
$$ \beta\lor(\beta\circ\gamma) = \beta\circ\big( \epsilon\lor\gamma\big).$$
Hence $\ell\big(\beta\lor(\beta\circ\gamma)\big)=\ell\big( \epsilon\lor\gamma\big)=m$ and if $\mathcal{C}_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}\ne \emptyset$, then the graph $G_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}$ is a graph on the vertex set $[m]$
with an edge $(i,i+1)$ if and only if $\max_\epsilon(\Lambda_i)>_\epsilon\min_\epsilon(\Lambda_{i+1})$ or $\max_\alpha(\Lambda_i)>_\alpha \min_\alpha(\Lambda_{i+1})$, using the order $\epsilon$ and $\alpha$ respectively. We remark that $G_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}$ contains only short edges. Hence $c_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}=(-1)^m$ if $(i,i+1)\in G_{\epsilon,\alpha}^{\beta, \beta\circ\gamma}$ for all $1\le i_\epsilon\min_\epsilon(\Lambda_{i+1})$ or $\max_\alpha(\Lambda_i)>_\alpha \min_\alpha(\Lambda_{i+1})$ for all $1\le i\beta_{i+1}\text{ or }\alpha^{-1}(\beta_i)>\alpha^{-1}(\beta_{i+1})\}\big|.
\end{equation}
The identity in Equation~\eqref{eq:PRidentity} relates combinatorial invariants for permutation that looks a priori unrelated. We summarize this in the following theorem
\begin{theorem}
For $\alpha\in\mathbf{l}[n]$, the chromatic polynomial $\chi_\alpha(t)$ counts the number of ways to color increasing sequences of $\alpha$ with at most $t$ distinct colors.
We have the identity
$$ \chi_\alpha(-1) = (-1)^n d_{\alpha,\epsilon},$$
where $d_{\alpha,\epsilon}$ is the number of $\alpha$-decreasing orders (as defined in Equation~\eqref{eq:alphadecr}).
\end{theorem}
\end{exam}
\begin{rema} Given $\alpha\in\mathbf{l}[n]$, one can associate a partial order $P_\alpha$ where $\alpha_i\prec \alpha_j$ if $i\alpha_j$.
As in~\cite{stanley} we can construct the incomparable graph $G_\alpha$ associated to $P_\alpha$.
The symmetric function $\Psi(\alpha)$ above is in fact the Stanley chromatic symmetric function of the Graph $G_\alpha$.
A famous conjecture of Stanley and Stembridge~\cite{stanley} states that $\Psi(\alpha)$ is $e$-positive if $P_\alpha$ is $(\mathbf{3}+ \mathbf{1})$-avoiding.
In the language of permutations this is equivalent to say that $\alpha$ is $4123$ and $2341$ avoiding~\cite{Atkinson-Sagan}.
From the Hopf structure, one can see that it is natural to describe $e$ positivity in terms of pattern-avoiding sequences.
What is surprising here is the fact that there should be finitely many and very simple patterns to avoid.
We also point out that here $d_{\alpha,\epsilon}$ also counts the number of acyclic orientations of $G_\alpha$.
\end{rema}
The Hopf algebra $PR$ is free and generated by total orders that do not have any global ascent.
The free generators are $\{1,21,321,231,312,\ldots\}$. In the example above, we choose $\zeta$ to be $1$
on the generator $1$ and zero for all other generators. One can construct different $\zeta$'s by choosing any
subset of generators. This would lead to different coloring schemes and new identities with permutations.
\begin{exam} Let us consider the case where $\zeta_{21}\colon PR\to\field$ is defined to be $1$ on the (free) generator $21$
and zero on the other. That is, define $\zeta_{21}(x)=1$ if $x=2143\ldots(2n)(2n-1)$, zero otherwise.
This defines a symmetric function valued morphism $\Psi_{21}\colon PR\to QSym$
such that for $\alpha\in\mathbf{l}[n]$ we have
$$ \Psi_{21}(\alpha)=\sum_{a\models n} c'_a(\alpha) M_a, $$
where $a=(2a_1,\ldots,2a_\ell)\models n$ is an integer composition of $n$ with even parts, and $c_a(\alpha)$ is the number of ways to decompose $\alpha$ into $21^*$-subsequences of type $a$.
More precisely
$$c'_a(\alpha)=\big|\{ A\models [n] : \text{for } 1\le i\le \ell,\ |A_i|=2a_i \text{ and }st(\alpha|_{A_i})=2143\ldots(2a_i)(2a_i-1)\}\big|,$$
where $st(-)$ denotes the standardization map via the functor $PR$ as defined in~\cite[Notation~2.5]{AM:2010}.
It would be interesting to understand the properties of the numbers $c'_a(\alpha)$.
The \emph{chromatic} polynomial $\chi^{21}_\alpha(t)$ is then given by
$$ \chi^{21}_\alpha(t)=\sum_{a\models n} c'_a(\alpha) %{t \choose \ell(a)}
\genfrac{(}{)}{0pt}{0}{t}{\ell(a)}. $$
This polynomial, when evaluated at $t=m$ counts the number of ways to color the entries of $\alpha$ with at most $m$ distinct colors such that $\alpha$ restricted to a single color is a $21^*$-sequence.
Using Theorem~\ref{thm:AntipodePR} we get the identity
\begin{equation}\label{eq:PRidentity21}
\sum_{a\models n} (-1)^{\ell(a)}c'_a(\alpha) = (-1)^{n/2} d_{\alpha,2143\ldots(2n)(2n-1)}.
\end{equation}
\end{exam}
%\begin{rema}
%The symmetric function $\Psi_{21}(\alpha)$ above is very different from the Stanley chromatic symmetric function for graphs.
%However, we believe that using the Hopf structure, one can get some natural positivity using pattern avoidance.
%\end{rema}
\begin{conjecture}\label{conj:h} There is a finite set of permutations $\mathcal{A}$ such that for $\alpha\in\mathbf{l}[n]$
$$(-1)^{n/2}\Psi_{21}(\alpha)(-h_1,-h_2,\ldots)$$
is $h$-positive for any $\alpha$ that is $\mathcal{A}$-avoiding. So far, our computer evidence suggests that $\mathcal{A}=\emptyset$.
We also conjecture that Stanley chromatic symmetric functions satisfy this property.
\end{conjecture}
\noindent
In a forthcoming paper~\cite{BA:2018}, Aval, Bergeron and Machacek will present a proof of Conjecture~\ref{conj:h}.
%\medskip
%\begin{moredetails}
%
%Some interesting character for hypergraphs:
%
% \ \quad - one if is the size of all hyperedges divisible by k, zero otherwise (k=2)
%
% \ \quad - $q^rk(h)$ where $rk(h)$ the lengh of a maximal sequence of edges that strickly decrease the number of connected component at each step as we add one by one the el ement of the sequence.
%\end{moredetails}
%
To conclude this paper, we remark that the Hopf monoid of hypergraphs $\mathbf{HG}$ as defined in Section~\ref{ss:hypergraph} plays a central
role in the computation of antipodes for commutative and cocommutative Hopf monoid.
This Hopf monoid is different in nature from the Hopf algebra of hypergraphs in~\cite{Aguiar-Ardila} which is not cocommutative.
In a forthcoming paper~\cite{BBM:2017} we show that
given a hypergraph $G$ on the vertex set $V=[n]$, the coefficient of the edgeless hypergraph in the antipode $S(G)$
is the homology of the complex labelled by the acyclic orientations of $G$. This can be understood from facets of
the \emph{Hypergraphic polytope} $P_G$ associated to $G$. That is the polytope in ${\mathbb R}^n={\mathbb R}\{e_1,e_2,\ldots,e_n\}$
defined by the Minkowsk sum
$$P_G=\sum_{U\in G} \mathbf{\Delta}_U,$$
where $\mathbf{\Delta}_U$ is the simplex given by the convex hull of the points $\{e_i : i\in U\}$.
The acyclic orientations of $G$ actually label certain \emph{exterior} faces of $P_G$. Hence the coefficient of the discrete hypergraph in $S(G)$
is the homology of the complex labelled by the acyclic orientations of $G$. The other coefficients of $S(G)$ are also encoded in~$P_G$.
For example, consider the hypergraph $G=
\begin{tikzpicture}[scale=.7,baseline=.2cm]
\node (1) at (0,.1) {$\scriptstyle 1$};
\node (2) at (2.5,.5) {$\scriptstyle 4$};
\node (3) at (0,1) {$\scriptstyle 2$};
\node (4) at (1,.5) {$\scriptstyle 3$};
\draw [fill=blue!40] (.1,.1) .. controls (.25,.5) .. (.15,.9) .. controls (.4,.5) .. (.85,.5) .. controls (.5,.4) .. (.1,.1) ;
\draw [thick,color=red!80] (4).. controls (1.8,.6) ..(2);
\end{tikzpicture}
$, the flats of $G$ are $G,\{\{3,4\}\},\{\{1,2,3\}\}$ and $\emptyset$. The coefficient of each flat $F$ in $S(G)$ is, up to a sign, given by the Euler characteristic of the union of some faces of $P_G=\blueun{\mathbf{\Delta}_{123}}+ \redun{\mathbf{\Delta}_{34}}$ indexed by acyclic orientations of $G/F$:
$$\begin{array}{cccc}
\begin{tikzpicture}[scale=1,baseline=.5cm]
\draw [fill=gray!10,dotted ] (0,0) -- (.6,.75)-- (1.6,1.25) -- (2.2,.5) -- (1.2,0) --(0,0) ;
\draw [dotted] (0,0)--(1,.5);
\draw [dotted] (1.6,1.25)--(1,.5)--(2.2,.5);
\draw [color=green!60!black,fill=green!60!black ] (.32,.125) -- (.74,.65)-- (1.16,.1250) --(.32,.125) ;
\draw [color=green!60!black,fill=green!60!black ] (.74,.65)--(1.54,1.05)-- (1.96,.5250)-- (1.16,.1250)--(.74,.65) ;
\draw [densely dotted,color=green!40!black] (1.16,.1250)--(.74,.65) ;
\draw [dotted] (1.5,1.05)--(1.15,.525)--(1.92,.5250);
\draw [dotted] (.6,.75)--(1.2,0);
\end{tikzpicture} \quad &
\begin{tikzpicture}[scale=1,baseline=.5cm]
\draw [fill=gray!10,dotted ] (0,0) -- (.6,.75)-- (1.6,1.25) -- (2.2,.5) -- (1.2,0) --(0,0) ;
\draw [dotted] (0,0)--(1,.5);
\draw [dotted] (1.6,1.25)--(1,.5)--(2.2,.5);
\draw [color=green!60!black,fill=green!60!black] (.7,.8)-- (1.5,1.2) -- (2.1,.45) -- (1.3,0.05) --(.7,.8) ;
\draw [color=green!65!black,fill=green!65!black] (.1,0.05) -- (.7,.8) -- (1.3,0.05)--(.1,0.05) ;
\draw [thick,color=green!40!black] (.7,.8)-- (1.5,1.2);
\draw [thick,color=green!40!black] (2.1,.45) -- (1.3,0.05);
\draw [thick,color=green!40!black] (.1,0.05) -- (.92,0.46);
\draw [dotted] (.6,.75)--(1.2,0);
\node (1) at (0,-.1) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.1,.1) -- (.15,.9) ;
\draw [->] (.1,.1) -- (.85,.5) ; }
\end{tikzpicture} $};
\node (2) at (0.9,1.25) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.15,.9) -- (.1,.1) ;
\draw [->] (.15,.9) -- (.85,.5) ; }
\end{tikzpicture} $};
\node (12) at (0.1,.7) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.15,.5) -- (.85,.5) ; }
\end{tikzpicture} $};
\node (3) at (1.8,.15) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.85,.5) -- (.1,.1) ;
\draw [->] (.85,.5) -- (.15,.9); }
\end{tikzpicture} $};
\node (13) at (.6,-.1) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [<-] (.5,.9) -- (.85,.5) ; }
\end{tikzpicture} $};
\node (23) at (2.,1.2) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [<-] (.5,.1) -- (.85,.5) ; }
\end{tikzpicture} $};
\end{tikzpicture} \quad &
\begin{tikzpicture}[scale=1,baseline=.5cm]
\draw [fill=gray!10,dotted ] (0,0) -- (.6,.75)-- (1.6,1.25) -- (2.2,.5) -- (1.2,0) --(0,0) ;
\draw [dotted] (0,0)--(1,.5);
\draw [dotted] (1.6,1.25)--(1,.5)--(2.2,.5);
\draw [dotted ](.6,.75)--(1.2,0);
\draw [color=gray!10,fill=green!60!black] (.18,.075) -- (.6,.6)-- (1.02,.0750) --(.18,.075) ;
\draw [color=gray!10,fill=green!60!black ] (1.18,.575) -- (1.6,1.1)-- (2.02,.5750) --(1.18,.575) ;
\node (13) at (.5,0) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\red{\draw [->] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node at (2,1.3) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\red{\draw [<-] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\end{tikzpicture} \quad&
\begin{tikzpicture}[scale=1,baseline=.5cm]
\draw [fill=gray!10,dotted ] (0,0) -- (.6,.75)-- (1.6,1.25) -- (2.2,.5) -- (1.2,0) --(0,0) ;
\draw [dotted] (0,0)--(1,.5);
\draw [thick,color=green!60!black] (1.6,1.25)--(1,.5)--(2.2,.5);
\draw [thick,color=green!60!black] (0,0) --(.6,.75)--(1.2,0)--(0,0);
\draw [thick,color=green!60!black] (1.6,1.25) -- (2.2,.5);
\node at (0,0) {\textcolor{green!60!black}{$\scriptstyle \bullet$}};
\node at (.6,.75) {\textcolor{green!60!black}{$\scriptstyle \bullet$}};
\node at (1.6,1.25) {\textcolor{green!60!black}{$\scriptstyle \bullet$}};
\node at (2.2,.5) {\textcolor{green!60!black}{$\scriptstyle \bullet$}};
\node at (1.2,0) {\textcolor{green!60!black}{$\scriptstyle \bullet$}};
\node at (1,.5) {\textcolor{green!60!black}{$\scriptstyle \bullet$}};
\node (1) at (-0.2,-.1) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.1,.1) -- (.15,.9) ;
\draw [->] (.1,.1) -- (.85,.5) ; }
\red{\draw [->] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node (2) at (0.5,1.1) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.15,.9) -- (.1,.1) ;
\draw [->] (.15,.9) -- (.85,.5) ; }
\red{\draw [->] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node (12) at (0,.6) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.15,.5) -- (.85,.5) ; }
\red{\draw [->] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node (3) at (1.5,-.1) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.85,.5) -- (.1,.1) ;
\draw [->] (.85,.5) -- (.15,.9); }
\red{\draw [->] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node (13) at (.5,-.1) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [<-] (.5,.9) -- (.85,.5) ; }
\red{\draw [->] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node (23) at (1.,.35) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [<-] (.5,.1) -- (.85,.5) ; }
\red{\draw [->] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node at (1.3,.8) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.1,.1) -- (.15,.9) ;
\draw [->] (.1,.1) -- (.85,.5) ; }
\red{\draw [<-] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node at (1.7,1.6) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.15,.9) -- (.1,.1) ;
\draw [->] (.15,.9) -- (.85,.5) ; }
\red{\draw [<-] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node at (1.4,1.15) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.15,.5) -- (.85,.5) ; }
\red{\draw [<-] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node at (2.6,.6) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [->] (.85,.5) -- (.1,.1) ;
\draw [->] (.85,.5) -- (.15,.9); }
\red{\draw [<-] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node at (1.7,.6) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [<-] (.5,.9) -- (.85,.5) ; }
\red{\draw [<-] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\node at (2.2,1.2) {
$\begin{tikzpicture}[scale=.3,baseline=.5cm]
\blue{\draw [<-] (.5,.1) -- (.85,.5) ; }
\red{\draw [<-] (.85,.5) -- (1.5,.5) ; }
\end{tikzpicture} $};
\end{tikzpicture} \quad\\
\textcolor{green!60!black}{-1}\cdot
\begin{tikzpicture}[scale=.5,baseline=.2cm]
\node (1) at (0,.1) {$\scriptstyle 1$};
\node (2) at (2.5,.5) {$\scriptstyle 4$};
\node (3) at (0,1) {$\scriptstyle 2$};
\node (4) at (1,.5) {$\scriptstyle 3$};
\draw [fill=blue!40] (.1,.1) .. controls (.25,.5) .. (.15,.9) .. controls (.4,.5) .. (.85,.5) .. controls (.5,.4) .. (.1,.1) ;
\draw [thick,color=red!80] (4).. controls (1.8,.6) ..(2);
\end{tikzpicture}
&\textcolor{green!60!black}{+\quad 0}\cdot
\begin{tikzpicture}[scale=.5,baseline=.2cm]
\node (1) at (0,.1) {$\scriptstyle 1$};
\node (2) at (2.5,.5) {$\scriptstyle 4$};
\node (3) at (0,1) {$\scriptstyle 2$};
\node (4) at (1,.5) {$\scriptstyle 3$};
\draw [thick,color=red!80] (4).. controls (1.8,.6) ..(2);
\end{tikzpicture}
& \textcolor{green!60!black}{+\quad 2} \cdot
\begin{tikzpicture}[scale=.5,baseline=.2cm]
\node (1) at (0,.1) {$\scriptstyle 1$};
\node (2) at (2.5,.5) {$\scriptstyle 4$};
\node (3) at (0,1) {$\scriptstyle 2$};
\node (4) at (1,.5) {$\scriptstyle 3$};
\draw [fill=blue!40] (.1,.1) .. controls (.25,.5) .. (.15,.9) .. controls (.4,.5) .. (.85,.5) .. controls (.5,.4) .. (.1,.1) ;
\end{tikzpicture}
& \textcolor{green!60!black}{+\quad 0} \cdot\begin{tikzpicture}[scale=.5,baseline=.2cm]
\node (1) at (0,.1) {$\scriptstyle 1$};
\node (2) at (2.5,.5) {$\scriptstyle 4$};
\node (3) at (0,1) {$\scriptstyle 2$};
\node (4) at (1,.5) {$\scriptstyle 3$};
\end{tikzpicture}
% \\
\end{array}
$$
\begin{rema} It is interesting to see that hypergraphs play a crutial role in the study of square free ideals~\cite{KNM:2013}.
As an open question, how could one use the invariants studied in this paper for hypergraphs to derive properties of the associated ideal?
\end{rema}
%\noindent {\bf Acknowledgement}:
\longthanks{%
We are very grateful to the referees for their useful comments that helped us improving our exposition.%
}
%-------------------------------------------------------------------
% Begin BIBLIOGRAPHY
%-------------------------------------------------------------------
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Bergeron_123}
\end{document}
*