% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \excludecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.
% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
%   \theoremstyle{definition}
% and until the line
%   {\end{leftbar}\end{exmp}}

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, September 24, 2015 23:39:18}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{obsolete}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\QSym}{\operatorname{QSym}_{\mathbf{k}}}
\newcommand{\QSYM}{\operatorname{QSYM}_{\mathbf{k}}}
\newcommand{\Powser}{\mathbf{k}\left[\left[x_1,x_2,x_3,\ldots\right]\right]}
\newcommand{\bdd}{\operatorname{bdd}}
\newcommand{\Bdd}{\Powser_{\bdd}}
\newcommand{\bD}{\mathbf{D}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand{\NN}{\mathbb{N}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{Quasisymmetric functions and $\Gamma$-partitions}
\ohead{\today}
\begin{document}

\begin{center}
{\Huge \textbf{Quasisymmetric functions and $\Gamma$-partitions}}

Darij Grinberg

version 0.3, {\today}
\end{center}

The goal of this note is to give a new proof (and restatement) of Malvenuto's
and Reutenauer's antipode formula for quasisymmetric functions \cite[Theorem
3.1]{Mal-Reu}, and to generalize it in a way which also encompasses Jochemko's
enumerative results in \cite[Theorem 2.8]{Joch}. Along the way, we will give a
self-contained introduction into quasisymmetric functions and reprove some of
their basic properties.

[... add some material about the chain lemma as used in my original proof of
Zabrocki's conjecture.]

This note is work in progress and the proofs are mostly just sketched.
Nevertheless please let me know of any errors you find! (Just don't act surprised.)

\subsection{Acknowledgments}

Katharina Jochemko's work on order polynomials \cite{Joch} and my attempts at
generalizing that work gave the present paper its first impetus.

\begin{obsolete}
Here are some obsolete acknowledgments:
Further thanks are due to Michiel Hazewinkel and Vic Reiner for their very
accessible expositions \cite{Hazew-Witt1} and \cite{Reiner} which originally
introduced me to the theory of quasisymmetric functions, Vic Reiner and Ira
Gessel for very helpful explanations, and Christine Bessenrodt and Richard
Stanley for a work \cite{StanBess} which inspired the proof of Theorem [...
refer -- but this might no longer be slated for this paper].
The second impetus came from an unpublished conjecture Mike Zabrocki kindly
shared with me during a visit to University of York, Toronto; I am also
grateful to Nantel Bergeron for the invitation and the hospitality.
\end{obsolete}


\section{\label{sect.qsym}Quasisymmetric functions}

The ring $\operatorname*{QSym}$ of quasisymmetric functions (along with its
further structure, such as it being a Hopf algebra, having an internal
coproduct, dendriform operations etc.) has been the object of decades of
research, probably beginning with Gessel \cite{Gessel-multipar} [... check
what he actually does in that paper] and continued, among other places, in the
7-part NCSF study [... add references]. Introductions into the theory of this
ring can be found in \cite{Malve-Thesis}, \cite[Chapter 5]{Reiner},
\cite[\S 11]{Hazew-Witt1}, \cite[\S 7.19]{Stanley-EC2}, \cite{Hivert-CQS},
\cite{Gessel-multipar} and \cite[\S 1]{Mal-Reu} [... update references to
ever-expanding Reiner notes]; applications appear in \cite{ABS}. We recall the
definitions and the facts that we need. [... check self-containedness.] First,
we make some conventions which we will use throughout the text:

\begin{definition}
In the following, we use the notations $\mathbb{N}=\left\{  0,1,2,\ldots
\right\}  $ and $\mathbb{N}_{+}=\left\{  1,2,3,\ldots\right\}  $.
\end{definition}

\begin{definition}
\label{def.emptyset}If $a$ and $b$ are two integers such that $a\geq b+1$,
then $\left\{  a,a+1,\ldots,b\right\}  $ means the empty set. (In particular,
$\left\{  1,2,\ldots,-1\right\}  $ means $\varnothing$.)
\end{definition}

\begin{definition}
\label{def.iverson} If $\mathcal{A}$ is any statement, then $\left[
\mathcal{A}\right]  $ will mean the integer $\left\{
\begin{array}
[c]{c}%
1,\text{ if }\mathcal{A}\text{ is true;}\\
0,\text{ if }\mathcal{A}\text{ is false}%
\end{array}
\right.  $.
\end{definition}

\begin{definition}
Let $\mathbf{k}$ be any commutative ring. We consider $\mathbf{k}$ to be fixed
for the following (unless otherwise stated). (The reader can assume that
$\mathbf{k}=\mathbb{Z}$ without losing anything; we will briefly use
$\mathbf{k}=\mathbb{Q}$ in a proof.)

Let $x_{1},x_{2},x_{3},\ldots$ be a countable family of pairwise distinct
symbols; we will use these symbols as (commuting) indeterminates.

In the following, a \textit{monomial} means a monomial in these commuting
indeterminates $x_{1},x_{2},x_{3},\ldots$ (without coefficient). (We view
monomials as formal expressions\footnotemark; thus, e.g., we distinguish
between the monomials $1$ and $x_{1}$ even if $\mathbf{k}=0$.) For instance,
$x_{1}^{3}x_{5}x_{9}$, $x_{2}x_{4}^{2}$, $x_{7}$ and $1$ are monomials. We
regard, e.g., the monomials $x_{1}^{0}x_{2}$ and $x_{2}$ as identical. The
\textit{total degree} of a monomial is defined as the sum of the exponents of
all indeterminates in the monomial. For example, the total degree of the
monomial $x_{2}x_{3}^{4}x_{15}^{2}$ is $1+4+2=7$, while the total degree of
the monomial $1$ is $\left(  \text{empty sum}\right)  =0$.

Two monomials $\mathfrak{m}$ and $\mathfrak{n}$ are said to be
\textit{pack-equivalent} if there exists an $\ell\in\mathbb{N}$, a list
$\left(  a_{1},a_{2},\ldots,a_{\ell}\right)  \in\mathbb{N}_{+}^{\ell}$ of
positive integers, and two strictly increasing sequences $\left(  i_{1}%
<i_{2}<\cdots<i_{\ell}\right)  $ and $\left(  j_{1}<j_{2}<\cdots<j_{\ell
}\right)  $ of positive integers such that $\mathfrak{m}=x_{i_{1}}^{a_{1}%
}x_{i_{2}}^{a_{2}}\cdots x_{i_{\ell}}^{a_{\ell}}$ and $\mathfrak{n}=x_{j_{1}%
}^{a_{1}}x_{j_{2}}^{a_{2}}\cdots x_{j_{\ell}}^{a_{\ell}}$. For instance, the
monomials $x_{1}x_{2}^{2}$, $x_{1}x_{3}^{2}$, $x_{4}x_{19}^{2}$ are pairwise
pack-equivalent (all having $\ell=2$ and $\left(  a_{1},a_{2}\right)  =\left(
1,2\right)  $), while the monomials $x_{1}x_{3}^{2}$ and $x_{3}x_{1}^{2}$ are
not pack-equivalent. We will collect some (mostly trivial) properties of
pack-equivalent monomials in Proposition \ref{prop.pack.generalities}; as for
now, let us remark that pack-equivalent monomials can be intuitively regarded
as monomials which can be obtained from each other by \textquotedblleft
pulling apart\textquotedblright\ or \textquotedblleft pushing
together\textquotedblright\ the variables (without moving them past each other
or merging them).

A power series $f\in\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]
\right]  $ is said to be \textit{bounded-degree} if there exists an
$n\in\mathbb{N}$ such that every monomial having total degree $\geq n$ has
coefficient $0$ in $f$. For instance, the power series $\sum\limits_{i}%
x_{i}=x_{1}+x_{2}+x_{3}+\cdots$ is bounded-degree. (Here and in the following,
summation indices are supposed to be positive integers if not otherwise
specified.) Also, the power series $x_{1}+x_{2}+x_{3}+\cdots+x_{1}x_{2}%
+x_{2}x_{3}+x_{3}x_{4}+\cdots$ is bounded-degree, while the power series
$\dfrac{1}{1-x_{2}}=1+x_{2}+x_{2}^{2}+x_{2}^{3}+\cdots$ is not.

Let $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]
_{\operatorname*{bdd}}$ denote the set of bounded-degree power series in
$\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  $. This
set is a $\mathbf{k}$-subalgebra of $\mathbf{k}\left[  \left[  x_{1}%
,x_{2},x_{3},\ldots\right]  \right]  $ (by Proposition \ref{prop.QSym.ksubalg}
\textbf{(a)} below).

A power series $f\in\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]
\right]  $ is said to be \textit{quasisymmetric} if for any two
pack-equivalent monomials $\mathfrak{m}$ and $\mathfrak{n}$, the coefficient
of $\mathfrak{m}$ in $f$ equals the coefficient of $\mathfrak{n}$ in $f$. For
instance, the power series%
\[
\sum\limits_{i<j}x_{i}x_{j}^{2}=x_{1}x_{2}^{2}+x_{1}x_{3}^{2}+x_{1}x_{4}%
^{2}+\cdots+x_{2}x_{3}^{2}+x_{2}x_{4}^{2}+\cdots+x_{3}x_{4}^{2}+\cdots
\]
is quasisymmetric, while the power series%
\[
\sum\limits_{i<j}x_{i}x_{j+1}^{2}=x_{1}x_{3}^{2}+x_{1}x_{4}^{2}+x_{1}x_{5}%
^{2}+\cdots+x_{2}x_{4}^{2}+x_{2}x_{5}^{2}+\cdots+x_{3}x_{5}^{2}+\cdots
\]
is not (its coefficients before $x_{1}x_{2}^{2}$ and before $x_{1}x_{3}^{2}$
are not equal, despite $x_{1}x_{2}^{2}$ and $x_{1}x_{3}^{2}$ being
pack-equivalent). The set of all quasisymmetric power series in $\mathbf{k}%
\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  $ is a $\mathbf{k}%
$-subalgebra of $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]
\right]  $ (by Proposition \ref{prop.QSym.ksubalg} \textbf{(b)} further below).

We denote by $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ the set of all
quasisymmetric power series in $\mathbf{k}\left[  \left[  x_{1},x_{2}%
,x_{3},\ldots\right]  \right]  _{\operatorname*{bdd}}$. This is a $\mathbf{k}%
$-subalgebra of $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]
\right]  _{\operatorname*{bdd}}$ (by Proposition \ref{prop.QSym.ksubalg}
\textbf{(c)} further below). This $\mathbf{k}$-subalgebra
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$ is called the $\mathbf{k}%
$\textit{-algebra of quasisymmetric functions over }$\mathbf{k}$ (even though
its elements are not \textquotedblleft functions\textquotedblright\ in any
literal sense).

If $\mathbf{k}=\mathbb{Z}$, then the ring $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}=\operatorname*{QSym}\nolimits_{\mathbb{Z}}$ is simply
denoted by $\operatorname*{QSym}$. The ring $\operatorname*{QSym}$ is called
the \textit{ring of quasisymmetric functions.}

We endow the ring $\mathbf{k}$ with the discrete topology. To define a
topology on the $\mathbf{k}$-algebra $\mathbf{k}\left[  \left[  x_{1}%
,x_{2},x_{3},\ldots\right]  \right]  $, we (temporarily) regard every power
series in $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]
$ as the family of its coefficients. Thus, $\mathbf{k}\left[  \left[
x_{1},x_{2},x_{3},\ldots\right]  \right]  $ becomes a product of infinitely
many copies of $\mathbf{k}$ (one for each monomial). This allows us to define
a product topology on $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3}%
,\ldots\right]  \right]  $. This product topology is the topology that we will
be using whenever we make statements about convergence in $\mathbf{k}\left[
\left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  $ or write down infinite
sums of power series. A sequence $\left(  a_{n}\right)  _{n\in\mathbb{N}}$ of
power series converges to a power series $a$ with respect to this topology if
and only if for every monomial $\mathfrak{m}$, all sufficiently high
$n\in\mathbb{N}$ satisfy%
\[
\left(  \text{the coefficient of }\mathfrak{m}\text{ in }a_{n}\right)
=\left(  \text{the coefficient of }\mathfrak{m}\text{ in }a\right)  .
\]
Note that this is \textbf{not} the topology obtained by taking the completion
of $\mathbf{k}\left[  x_{1},x_{2},x_{3},\ldots\right]  $ with respect to the
standard grading (in which all $x_{i}$ have degree $1$). In fact, the latter
completion is not even $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3}%
,\ldots\right]  \right]  $ as a set.
\end{definition}

\footnotetext{More precisely, a monomial is an element of the free abelian
monoid on the set $\left\{  x_{1},x_{2},x_{3},\ldots\right\}  $ (where
$x_{1},x_{2},x_{3},\ldots$ are countably many distinct indeterminates).}Many
authors work only in the situation when $\mathbf{k}=\mathbb{Z}$; this usually
does not render their results any less general, because $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}\cong\operatorname*{QSym}\nolimits_{\mathbb{Z}}%
\otimes\mathbf{k}$ for every commutative ring $\mathbf{k}$ (by Proposition
\ref{prop.QSym.basechange} further below).

Before we proceed any further, let us state some basic facts. The first is a
collection of properties of pack-equivalent monomials.

\begin{definition}
\textbf{(a)} A monomial is said to be \textit{packed} if it has the form
$x_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{\ell}^{a_{\ell}}$ for some $\ell
\in\mathbb{N}$ and some $\left(  a_{1},a_{2},\ldots,a_{\ell}\right)
\in\mathbb{N}_{+}^{\ell}$.

\textbf{(b)} If $\mathfrak{m}$ is a monomial, then $\operatorname*{Supp}%
\mathfrak{m}$ will be the finite subset
\[
\left\{  i\in\mathbb{N}_{+}\ \mid\ \text{the variable }x_{i}\text{ appears
with a positive exponent in }\mathfrak{m}\right\}
\]
of $\mathbb{N}_{+}$.
\end{definition}

\begin{proposition}
\label{prop.pack.generalities}\textbf{(a)} Let $\mathfrak{m}$ be a monomial.
Then, the monomial $\mathfrak{m}$ is packed if and only if there exists an
$\ell\in\mathbb{N}$ such that $\operatorname*{Supp}\mathfrak{m}=\left\{
1,2,\ldots,\ell\right\}  $.

\textbf{(b)} Let $\mathfrak{m}$ be a monomial. Then, there exists a unique
packed monomial $\mathfrak{n}$ which is pack-equivalent to $\mathfrak{m}$.
This monomial $\mathfrak{n}$ is called the \textit{packing} of $\mathfrak{m}$
and denoted by $\operatorname*{pack}\mathfrak{m}$.

\textbf{(c)} For any $\ell\in\mathbb{N}$, any list $\left(  a_{1},a_{2}%
,\ldots,a_{\ell}\right)  \in\mathbb{N}_{+}^{\ell}$ of positive integers, and
any strictly increasing sequence $\left(  i_{1}<i_{2}<\cdots<i_{\ell}\right)
$ of positive integers, we have $\operatorname*{pack}\left(  x_{i_{1}}^{a_{1}%
}x_{i_{2}}^{a_{2}}\cdots x_{i_{\ell}}^{a_{\ell}}\right)  =x_{1}^{a_{1}}%
x_{2}^{a_{2}}\cdots x_{\ell}^{a_{\ell}}$.

\textbf{(d)} Let $\mathfrak{m}$ and $\mathfrak{n}$ be two monomials. Then,
$\mathfrak{m}$ and $\mathfrak{n}$ are pack-equivalent if and only if
$\operatorname*{pack}\mathfrak{m}=\operatorname*{pack}\mathfrak{n}$.

\textbf{(e)} Being pack-equivalent is an equivalence relation.
\end{proposition}

Properties like Proposition \ref{prop.pack.generalities} are normally used
without explicit mention in literature; the idea of formalizing them using the
notion of pack-equivalence originates in work of Hivert, Novelli and Thibon
\cite{Nov-Thi}.

\begin{proof}
[Proof of Proposition \ref{prop.pack.generalities} (sketched).]\textbf{(a)}
Let us first show the following logical implication:%
\begin{align}
&  \ \left(  \text{the monomial }\mathfrak{m}\text{ is packed}\right)
\nonumber\\
&  \Longrightarrow\ \left(  \text{there exists an }\ell\in\mathbb{N}\text{
such that }\operatorname*{Supp}\mathfrak{m}=\left\{  1,2,\ldots,\ell\right\}
\right)  . \label{pf.prop.pack.generalities.a.dir1}%
\end{align}


\textit{Proof of (\ref{pf.prop.pack.generalities.a.dir1}):} Assume that the
monomial $\mathfrak{m}$ is packed. Recall that the monomial $\mathfrak{m}$ is
packed if and only if $\mathfrak{m}$ has the form $x_{1}^{a_{1}}x_{2}^{a_{2}%
}\cdots x_{\ell}^{a_{\ell}}$ for some $\ell\in\mathbb{N}$ and some $\left(
a_{1},a_{2},\ldots,a_{\ell}\right)  \in\mathbb{N}_{+}^{\ell}$ (due to the
definition of \textquotedblleft packed\textquotedblright). Thus,
$\mathfrak{m}$ has the form $x_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{\ell
}^{a_{\ell}}$ for some $\ell\in\mathbb{N}$ and some $\left(  a_{1}%
,a_{2},\ldots,a_{\ell}\right)  \in\mathbb{N}_{+}^{\ell}$ (since the monomial
$\mathfrak{m}$ is packed). Denote this $\ell$ and this $\left(  a_{1}%
,a_{2},\ldots,a_{\ell}\right)  $ by $m$ and $\left(  b_{1},b_{2},\ldots
,b_{m}\right)  $. Thus, $m$ is an element of $\mathbb{N}$, and $\left(
b_{1},b_{2},\ldots,b_{m}\right)  $ is an element of $\mathbb{N}_{+}^{m}$ such
that $\mathfrak{m}=x_{1}^{b_{1}}x_{2}^{b_{2}}\cdots x_{m}^{b_{m}}$.

For every $i\in\left\{  1,2,\ldots,m\right\}  $, the variable $x_{i}$ appears
in the monomial $\mathfrak{m}$ with exponent $b_{i}$ (because $\mathfrak{m}%
=x_{1}^{b_{1}}x_{2}^{b_{2}}\cdots x_{m}^{b_{m}}$). This exponent $b_{i}$ is
positive (since $b_{i}\in\mathbb{N}_{+}$ (since $\left(  b_{1},b_{2}%
,\ldots,b_{m}\right)  \in\mathbb{N}_{+}^{m}$)). Therefore XXX

Now, the definition of $\operatorname*{Supp}\mathfrak{m}$ yields%
\begin{align*}
&  \operatorname*{Supp}\mathfrak{m}\\
&  =
\end{align*}


XXX

[...]
\end{proof}

We owe the reader a proof of the following fact:

\begin{proposition}
\label{prop.QSym.ksubalg}\textbf{(a)} The set $\mathbf{k}\left[  \left[
x_{1},x_{2},x_{3},\ldots\right]  \right]  _{\operatorname*{bdd}}$ is a
$\mathbf{k}$-subalgebra of $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3}%
,\ldots\right]  \right]  $.

\textbf{(b)} The set of all quasisymmetric power series in $\mathbf{k}\left[
\left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  $ is a $\mathbf{k}%
$-subalgebra of $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]
\right]  $.

\textbf{(c)} The subset $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ of
$\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]
_{\operatorname*{bdd}}$ is a $\mathbf{k}$-subalgebra of $\mathbf{k}\left[
\left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  _{\operatorname*{bdd}}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.QSym.ksubalg} (sketched).]\textbf{(a)} [...]

\textbf{(b)} Let $\operatorname*{QSYM}\nolimits_{\mathbf{k}}$ denote the set
of all quasisymmetric power series in $\mathbf{k}\left[  \left[  x_{1}%
,x_{2},x_{3},\ldots\right]  \right]  $. In order to prove Proposition
\ref{prop.QSym.ksubalg} \textbf{(b)}, we need to show that
$\operatorname*{QSYM}\nolimits_{\mathbf{k}}$ is a $\mathbf{k}$-subalgebra of
$\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  $. In
order to do that, it is enough to check that $fg\in\operatorname*{QSYM}%
\nolimits_{\mathbf{k}}$ for every $f\in\operatorname*{QSYM}%
\nolimits_{\mathbf{k}}$ and $g\in\operatorname*{QSYM}\nolimits_{\mathbf{k}}$
(because it is clear that $\operatorname*{QSYM}\nolimits_{\mathbf{k}}$ is a
$\mathbf{k}$-submodule of $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3}%
,\ldots\right]  \right]  $, and contains the power series $1$).

So let $f\in\operatorname*{QSYM}\nolimits_{\mathbf{k}}$ and $g\in
\operatorname*{QSYM}\nolimits_{\mathbf{k}}$ be arbitrary. Then, $f$ and $g$
are quasisymmetric power series.

Now, let $\mathfrak{m}$ and $\mathfrak{n}$ be two pack-equivalent monomials.
We are going to show that the coefficient of $\mathfrak{m}$ in $fg$ equals the
coefficient of $\mathfrak{n}$ in $fg$.

For every power series $h\in\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3}%
,\ldots\right]  \right]  _{\operatorname*{bdd}}$ and every monomial
$\mathfrak{p}$, let $\left[  \mathfrak{p}\right]  h$ denote the coefficient of
$\mathfrak{p}$ in $h$. By the definition of the product of two power series,
we have%
\[
\left[  \mathfrak{m}\right]  \left(  fg\right)  =\sum_{\substack{\mathfrak{u}%
\text{ and }\mathfrak{v}\text{ are monomials;}\\\mathfrak{uv}=\mathfrak{m}%
}}\left(  \left[  \mathfrak{u}\right]  f\right)  \left(  \left[
\mathfrak{v}\right]  g\right)
\]


[...]

\textbf{(c)} It is clear that $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ is
a $\mathbf{k}$-submodule of $\mathbf{k}\left[  \left[  x_{1},x_{2}%
,x_{3},\ldots\right]  \right]  _{\operatorname*{bdd}}$, and contains the power
series $1$. Hence, in order to prove Proposition \ref{prop.QSym.ksubalg}
\textbf{(c)}, we only need to check that $fg\in\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ for every $f\in\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ and $g\in\operatorname*{QSym}\nolimits_{\mathbf{k}}$.

So let $f\in\operatorname*{QSym}\nolimits_{\mathbf{k}}$ and $g\in
\operatorname*{QSym}\nolimits_{\mathbf{k}}$ be arbitrary. Then, $f$ and $g$
belong to $\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]
_{\operatorname*{bdd}}$, [...]
\end{proof}

We will later give an alternative proof of this theorem, as a consequence of
our results on $\Gamma$-partitions later on. [... when?] [... also part
\textbf{(b)}]

A natural question is how $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ looks
like, e.g., whether it has a basis as a $\mathbf{k}$-module. It is clear that
every symmetric power series in $\mathbf{k}\left[  \left[  x_{1},x_{2}%
,x_{3},\ldots\right]  \right]  $ is quasisymmetric, so the $\mathbf{k}%
$-algebra of symmetric functions is a $\mathbf{k}$-subalgebra of
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$. However, $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ is bigger (when $\mathbf{k}\neq0$), containing
non-symmetric power series such as $\sum\limits_{i<j}x_{i}x_{j}^{2}$.

A $\mathbf{k}$-basis of $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ can be
easily found:

\begin{definition}
In the following, a \textit{composition} will mean a tuple of positive
integers. For example, $\left(  3,1\right)  $ and $\left(  1,2,1\right)  $ are
compositions, and so is the empty tuple $\left(  {}\right)  $.

Let $\operatorname*{Comp}$ denote the set of all compositions.

If $\alpha$ is a composition, then the sum of the elements of $\alpha$ is
called the \textit{size} of $\alpha$. We write $\alpha\models n$ to say that
$\alpha$ is a composition of size $n$. Also, if $\alpha$ is any tuple of
integers (e.g., a composition), then the length of $\alpha$ (that is, the
number of entries of $\alpha$) is called $\ell\left(  \alpha\right)  $.

Let $\alpha$ be a composition. Write $\alpha$ in the form $\left(  \alpha
_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)  \in\mathbb{N}_{+}^{\ell}$. Then,
we denote by $M_{\alpha}$ the power series%
\[
\sum_{i_{1}<i_{2}<\cdots<i_{\ell}}x_{i_{1}}^{\alpha_{1}}x_{i_{2}}^{\alpha_{2}%
}\cdots x_{i_{\ell}}^{\alpha_{\ell}}\in\mathbf{k}\left[  \left[  x_{1}%
,x_{2},x_{3},\ldots\right]  \right]
\]
This power series $M_{\alpha}$ is called the $\alpha$\textit{-th monomial
quasisymmetric function}.

For instance, $M_{\left(  {}\right)  }=1$ (here, the sum is over all choices
of $i_{1}<i_{2}<\cdots<i_{\ell}$ with $\ell=0$; but there is only one such
choice, namely the \textquotedblleft empty choice\textquotedblright), while%
\begin{align*}
M_{\left(  2\right)  }  &  =\sum\limits_{i}x_{i}^{2}=x_{1}^{2}+x_{2}^{2}%
+x_{3}^{2}+\cdots;\\
M_{\left(  1,3\right)  }  &  =\sum\limits_{i<j}x_{i}x_{j}^{3}=x_{1}x_{2}%
^{3}+x_{1}x_{3}^{3}+x_{1}x_{4}^{3}+\cdots+x_{2}x_{3}^{3}+x_{2}x_{4}^{3}%
+\cdots+x_{3}x_{4}^{3}+\cdots;\\
M_{\left(  2,2\right)  }  &  =\sum\limits_{i<j}x_{i}^{2}x_{j}^{2}=x_{1}%
^{2}x_{2}^{2}+x_{1}^{2}x_{3}^{2}+x_{1}^{2}x_{4}^{2}+\cdots+x_{2}^{2}x_{3}%
^{2}+x_{2}^{2}x_{4}^{2}+\cdots+x_{3}^{2}x_{4}^{2}+\cdots.
\end{align*}

\end{definition}

\begin{proposition}
\label{prop.M.qsym} Let $\alpha$ be a composition. Then, $M_{\alpha}
\in\operatorname*{QSym}\nolimits_{\mathbf{k}}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.M.qsym} (sketched).][...]
\end{proof}

\begin{proposition}
\label{prop.M.basis}The family $\left(  M_{\alpha}\right)  _{\alpha
\in\operatorname*{Comp}}$ is a basis of the $\mathbf{k}$-module
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.M.basis} (sketched).]The family $\left(
M_{\alpha}\right)  _{\alpha\in\operatorname*{Comp}}$ is linearly independent,
since its elements are nonzero and have no monomials in common (pairwise).
Thus it remains to prove that this family spans the $\mathbf{k}$-module
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$.

Let $f\in\operatorname*{QSym}\nolimits_{\mathbf{k}}$. For every $\left(
\beta_{1},\beta_{2},\beta_{3},\ldots\right)  \in\mathbb{N}^{\mathbb{N}_{+}}$,
let $\operatorname*{coeff}\nolimits_{\beta_{1},\beta_{2},\beta_{3},\cdots}f$
denote the coefficient of the monomial $x_{1}^{\beta_{1}}x_{2}^{\beta_{2}%
}x_{3}^{\beta_{3}}\cdots$ in $f$. Then,%
\[
f-\sum_{\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)
\in\operatorname*{Comp}}\left(  \operatorname*{coeff}\nolimits_{\alpha
_{1},\alpha_{2},\ldots,\alpha_{\ell},0,0,0,\ldots}f\right)  \cdot M_{\left(
\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)  }%
\]
is quasisymmetric, but its coefficient before each packed monomial is $0$. But
a quasisymmetric power series whose coefficient before each packed monomial is
$0$ must be identically $0$ (since the definition of \textquotedblleft
quasisymmetric\textquotedblright\ shows that every of its coefficients equals
its coefficient before some packed monomial). Hence, $f-\sum\limits_{\left(
\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)  \in\operatorname*{Comp}%
}\left(  \operatorname*{coeff}\nolimits_{\alpha_{1},\alpha_{2},\ldots
,\alpha_{\ell},0,0,0,\ldots}f\right)  \cdot M_{\left(  \alpha_{1},\alpha
_{2},\ldots,\alpha_{\ell}\right)  }$ is identically $0$, so that%
\[
f=\sum_{\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)
\in\operatorname*{Comp}}\left(  \operatorname*{coeff}\nolimits_{\alpha
_{1},\alpha_{2},\ldots,\alpha_{\ell},0,0,0,\ldots}f\right)  \cdot M_{\left(
\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)  }%
\]
lies in the $\mathbf{k}$-span of $\left(  M_{\alpha}\right)  _{\alpha
\in\operatorname*{Comp}}$. This proves Proposition \ref{prop.M.basis}.
\end{proof}

As a consequence of the above proposition, we can see that the dependence of
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$ on the ground ring $\mathbf{k}$
is fairly simple:

\begin{proposition}
\label{prop.QSym.basechange}We have $\operatorname*{QSym}\nolimits_{\mathbf{k}%
}\cong\mathbf{k}\otimes\operatorname*{QSym}\nolimits_{\mathbb{Z}}$ as
$\mathbf{k}$-algebras.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.QSym.basechange} (sketched).][...]
\end{proof}

A result similar to Proposition \ref{prop.M.basis} also holds for power series
without the bounded-degree requirement:

\begin{proposition}
\label{prop.M.basis.completed}

\textbf{(a)} For any family $\left(  \lambda_{\alpha}\right)  _{\alpha
\in\operatorname*{Comp}}$, the (infinite) sum $\sum\limits_{\alpha
\in\operatorname*{Comp}}\lambda_{\alpha}M_{\alpha}$ converges coefficientwise
(i.e., for each monomial $\mathfrak{m}$, the sum of the coefficients of
$\mathfrak{m}$ in $\lambda_{\alpha}M_{\alpha}$ over all $\alpha\in
\operatorname*{Comp}$ converges with respect to the discrete topology). It is
a well-defined quasisymmetric power series in $\mathbf{k}\left[  \left[
x_{1},x_{2},x_{3},\ldots\right]  \right]  $.

\textbf{(b)} If $f$ is a quasisymmetric power series in $\mathbf{k}\left[
\left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  $, then there exists a
unique family $\left(  \lambda_{\alpha}\right)  _{\alpha\in
\operatorname*{Comp}}$ such that $f = \sum\limits_{\alpha\in
\operatorname*{Comp}} \lambda_{\alpha} M_{\alpha}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.M.basis.completed} (sketched).]Let
$\operatorname*{QSYM}\nolimits_{\mathbf{k}}$ denote the set of all
quasisymmetric power series in $\mathbf{k}\left[  \left[  x_{1},x_{2}%
,x_{3},\ldots\right]  \right]  $. [...]
\end{proof}

To find a more interesting basis of $\operatorname*{QSym}\nolimits_{\mathbf{k}%
}$ than $\left(  M_{\alpha}\right)  _{\alpha\in\operatorname*{Comp}}$, we need
to introduce the notion of descents and of descent sets. First, let us relate
compositions to subsets of $\left\{  1,2,\ldots,n-1\right\}  $:

\begin{definition}
\label{def.D} Let $n\in\mathbb{N}$. In the following, a \textit{composition of
}$n$ means a composition of size $n$.

\textbf{(a)} If $\alpha$ is a composition of $n$, then we define a subset
$D\left(  \alpha\right)  $ of $\left\{  1,2,\ldots,n-1\right\}  $ by%
\begin{align*}
D\left(  \alpha\right)   &  =\left\{  \alpha_{1},\alpha_{1}+\alpha_{2}%
,\alpha_{1}+\alpha_{2}+\alpha_{3},\ldots,\alpha_{1}+\alpha_{2}+\cdots
+\alpha_{\ell-1}\right\} \\
&  =\left\{  \alpha_{1}+\alpha_{2}+\cdots+\alpha_{i}\ \mid\ i\in\left\{
1,2,\ldots,\ell-1\right\}  \right\}  ,
\end{align*}
where $\alpha$ is written in the form $\left(  \alpha_{1},\alpha_{2}%
,\ldots,\alpha_{\ell}\right)  \in\mathbb{N}_{+}^{\ell}$. (Keep in mind that we
are using Definition \ref{def.emptyset} if $n=0$.) This subset $D\left(
\alpha\right)  $ is well-defined (by Proposition \ref{prop.D.welldef}
\textbf{(a)} below). For instance,%
\begin{align*}
D\left(  \left(  {}\right)  \right)   &  =\varnothing\subseteq\left\{
1,2,\ldots,0-1\right\}  =\varnothing;\\
D\left(  \left(  4\right)  \right)   &  =\varnothing\subseteq\left\{
1,2,\ldots,4-1\right\}  ;\\
D\left(  \left(  2,3\right)  \right)   &  =\left\{  2\right\}  \subseteq
\left\{  1,2,\ldots,5-1\right\}  ;\\
D\left(  \left(  1,4,2,3,1\right)  \right)   &  =\left\{  1,5,7,10\right\}
\subseteq\left\{  1,2,\ldots,11-1\right\}  ;\\
D\left(  \left(  1,4,2,3,2\right)  \right)   &  =\left\{  1,5,7,10\right\}
\subseteq\left\{  1,2,\ldots,12-1\right\}  .
\end{align*}


Thus, we have defined a subset $D\left(  \alpha\right)  $ of $\left\{
1,2,\ldots,n-1\right\}  $ for every composition $\alpha$ of $n$. In other
words, we have defined a map $D$ from the set of compositions of $n$ to the
set of subsets of $\left\{  1,2,\ldots,n-1\right\}  $.

\textbf{(b)} Conversely, given a subset $S$ of $\left\{  1,2,\ldots
,n-1\right\}  $, define a $\operatorname*{comp}\nolimits_{n}S$ of $n$ as follows:

\begin{itemize}
\item If $n = 0$, then set $\operatorname*{comp}\nolimits_{n}S = \left(
\right)  $.

\item Otherwise, write the set $S$ in the form $\left\{  s_{1},s_{2}%
,\ldots,s_{k}\right\}  $ with $s_{1}<s_{2}<\cdots<s_{k}$. Furthermore, set
$s_{0}=0$ and $s_{k+1}=n$. Thus, a $\left(  k+2\right)  $-tuple $\left(
s_{0},s_{1},s_{2},\ldots,s_{k+1}\right)  $ of nonnegative integers is defined.
Then, define $\operatorname*{comp}\nolimits_{n}S$ as the composition%
\[
\left(  s_{1}-s_{0},s_{2}-s_{1},s_{3}-s_{2},\ldots,s_{k}-s_{k-1},s_{k+1}%
-s_{k}\right)
\]
of $n$.
\end{itemize}

This composition $\operatorname*{comp}\nolimits_{n}S$ of $n$ is well-defined
(by Proposition \ref{prop.D.welldef} \textbf{(b)} below). (Note that this
composition $\operatorname*{comp}\nolimits_{n}S$ depends on both $S$ and $n$.)
For instance,%
\begin{align*}
\operatorname*{comp}\nolimits_{3} \left\{  1,2\right\}   &  =\left(
1,1,1\right)  ;\\
\operatorname*{comp}\nolimits_{4} \left\{  1,2\right\}   &  =\left(
1,1,2\right)  ;\\
\operatorname*{comp}\nolimits_{9} \left\{  3,5,6\right\}   &  =\left(
3,2,1,3\right)  ;\\
\operatorname*{comp}\nolimits_{9}\varnothing &  =\left(  9\right)  .
\end{align*}


Thus, we have defined a composition $\operatorname*{comp}\nolimits_{n}S$ of
$n$ for every subset $S$ of $\left\{  1,2,\ldots,n-1\right\}  $. In other
words, we have defined a map $\operatorname*{comp}\nolimits_{n}$ from the set
of subsets of $\left\{  1,2,\ldots,n-1\right\}  $ to the subset of
compositions of $n$.

\textbf{(c)} We now have defined a map $D$ from the set of compositions of $n$
to the set of subsets of $\left\{  1,2,\ldots,n-1\right\}  $, and a map
$\operatorname*{comp}\nolimits_{n}$ in the opposite direction. These two maps
are mutually inverse (by Proposition \ref{prop.D.welldef} \textbf{(c)} below),
and thus the compositions of $n$ are in 1-to-1 correspondence with the subsets
of $\left\{  1,2,\ldots,n-1\right\}  $. Hence, the number of compositions of
$n$ equals $2^{n-1}$ if $n\geq1$ (and $1$ if $n=0$).
\end{definition}

\begin{proposition}
\label{prop.D.welldef} Let $n\in\mathbb{N}$.

\textbf{(a)} If $\alpha$ is a composition of $n$, then the subset of $D\left(
\alpha\right)  $ of $\left\{  1,2,\ldots,n-1\right\}  $ defined in Definition
\ref{def.D} \textbf{(a)} is well-defined.

\textbf{(b)} If $S$ is a subset of $\left\{  1,2,\ldots,n-1\right\}  $, then
the composition $\operatorname*{comp}\nolimits_{n}S$ of $n$ defined in
Definition \ref{def.D} \textbf{(b)} is well-defined.

\textbf{(c)} The maps $D$ and $\operatorname*{comp}\nolimits_{n}$ defined in
Definition \ref{def.D} are mutually inverse.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.D.welldef} (sketched).][...]
\end{proof}

\begin{definition}
Let $\alpha$ be a composition. Let $n$ be the size of $\alpha$ (so that
$\alpha$ is a composition of $n$). The $\alpha$\textit{-th fundamental
quasisymmetric function} is defined as the power series%
\[
\sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq i_{n};\\i_{j}<i_{j+1}\text{ for
every }j\in D\left(  \alpha\right)  }}x_{i_{1}}x_{i_{2}} \cdots x_{i_{n}}%
\in\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  .
\]
It is denoted by $L_{\alpha}$.

For instance, $D\left(  \left(  1,3,2\right)  \right)  =\left\{  1,4\right\}
$, so that
\begin{align*}
L_{\left(  1,3,2\right)  }  &  =\sum_{\substack{i_{1}\leq i_{2}\leq i_{3}\leq
i_{4}\leq i_{5}\leq i_{6};\\i_{j}<i_{j+1}\text{ for every }j\in D\left(
\left(  1,3,2\right)  \right)  }}x_{i_{1}}x_{i_{2}}x_{i_{3}}x_{i_{4}}x_{i_{5}%
}x_{i_{6}}\\
&  =\sum_{\substack{i_{1}\leq i_{2}\leq i_{3}\leq i_{4}\leq i_{5}\leq
i_{6};\\i_{1}<i_{2}\text{ and }i_{4}<i_{5}}}x_{i_{1}}x_{i_{2}}x_{i_{3}%
}x_{i_{4}}x_{i_{5}}x_{i_{6}}=\sum_{i_{1}<i_{2}\leq i_{3}\leq i_{4}<i_{5}\leq
i_{6}}x_{i_{1}}x_{i_{2}}x_{i_{3}}x_{i_{4}}x_{i_{5}}x_{i_{6}}.
\end{align*}

\end{definition}

\begin{proposition}
\label{prop.L.qsym} Let $\alpha$ be a composition. We have $L_{\alpha}
\in\operatorname*{QSym}\nolimits_{\mathbf{k}}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.L.qsym} (sketched).][...]
\end{proof}

To understand the relation between the family $\left(  L_{\alpha}\right)
_{\alpha\in\operatorname*{Comp}}$ and the basis $\left(  M_{\alpha}\right)
_{\alpha\in\operatorname*{Comp}}$ (and, in particular, to see that the former
family also is a basis), we need to introduce a partial order on the set of
compositions of a given integer:

\begin{definition}
Let $n\in\mathbb{N}$. Let $\alpha$ and $\beta$ be two compositions of $n$. We
say that $\alpha$ \textit{refines} $\beta$ if $D\left(  \beta\right)
\subseteq D\left(  \alpha\right)  $. For example, the composition $\left(
2,1,3,4,2\right)  $ of $12$ refines $\left(  3,3,6\right)  $, since $D\left(
\left(  3,3,6\right)  \right)  =\left\{  3,6\right\}  \subseteq\left\{
2,3,6,10\right\}  =D\left(  \left(  2,1,3,4,2\right)  \right)  $.

The relation \textquotedblleft refines\textquotedblright\ is a partial order
on the set of all compositions of $n$ (since $D$ is a bijection, and since
inclusion is a partial order on the set of subsets of $\left\{  1,2,\ldots
,n-1\right\}  $). It is called the \textit{refinement order}. It turns the set
of all compositions of $n$ into a poset, which is order-isomorphic to the
lattice of subsets of $\left\{  1,2,\ldots,n-1\right\}  $ under reverse inclusion.
\end{definition}

The idea behind the refinement order is that a composition $\alpha$ refines
another composition $\beta$ of the same size if and only one can obtain
$\alpha$ from $\beta$ by breaking apart entries (e.g., breaking apart the
first $3$ in the composition $\left(  1,3,2,1,3\right)  $ into $1$ and $2$
results in $\left(  1,1,2,2,1,3\right)  $). More formally, one can easily show
that a composition $\alpha$ of size $n$ refines a composition $\beta= \left(
\beta_{1}, \beta_{2}, \ldots, \beta_{k}\right)  $ of size $n$ if there exists
a composition $\left(  \beta_{i,1},\beta_{i,2},\ldots,\beta_{i,m_{i}}\right)
$ of $\beta_{i}$ for every $i\in\left\{  1,2,\ldots,k\right\}  $ such that
\[
\alpha= \left(  \beta_{1,1}, \beta_{1,2}, \ldots, \beta_{1,m_{1}},
\ \beta_{2,1}, \beta_{2,2}, \ldots, \beta_{2,m_{2}}, \ \ldots, \ \beta_{k,1},
\beta_{k,2}, \ldots, \beta_{k,m_{k}} \right)  .
\]


\begin{proposition}
\label{prop.M(L)}Let $n\in\mathbb{N}$. Let $\alpha$ be a composition of $n$.
Then,%
\[
L_{\alpha}=\sum_{\substack{\beta\models n;\\\beta\text{ refines }\alpha
}}M_{\beta}.
\]

\end{proposition}

Proposition \ref{prop.M(L)} appears in \cite[Proposition 5.17]{Reiner}%
.\footnote{To be more precise, $L_{\alpha}$ is defined as $\sum
_{\substack{\beta\models n;\\\beta\text{ refines }\alpha}}M_{\beta}$ in
\cite[Definition 5.15]{Reiner}, and then \cite[Proposition 5.17]{Reiner}
states that $L_{\alpha} = \sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq
i_{n};\\i_{j}<i_{j+1}\text{ for every }j\in D\left(  \alpha\right)  }%
}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}$ (thus showing that the $L_{\alpha}$
defined in \cite[Definition 5.15]{Reiner} is identical to the $L_{\alpha}$
that we defined above).}

Before we prove Proposition \ref{prop.M(L)}, we rewrite the definition of
$M_{\alpha}$ in terms similar to how we defined $L_{\alpha}$:

\begin{proposition}
\label{prop.L(L)}Let $n\in\mathbb{N}$. Let $\alpha$ be a composition of $n$.
Then,%
\[
M_{\alpha}=\sum_{\substack{i_{1}\leq i_{2}\leq\cdots\leq i_{n};\\i_{j}%
<i_{j+1}\text{ for every }j\in D\left(  \alpha\right)  ;\\i_{j}=i_{j+1}\text{
for every }j\in\left\{  1,2,\ldots,n-1\right\}  \setminus D\left(
\alpha\right)  }}x_{i_{1}}x_{i_{2}}\cdots x_{i_{n}}.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.L(L)} (sketched).][...]
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.M(L)} (sketched).][... add this proof?]
\end{proof}

\begin{corollary}
\label{cor.L.basis}The family $\left(  L_{\alpha}\right)  _{\alpha
\in\operatorname*{Comp}}$ is a basis of the $\mathbf{k}$-module
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.L.basis} (sketched).][... add this proof?]
\end{proof}

\section{\label{sect.gammapart}$\Gamma$-partitions}

Much of the use of the ring $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ stems
from the fact that to every \textquotedblleft$P$-partition\textquotedblright%
\ (a notion which we will define in Section \ref{sect.ppart}) one can assign a
certain generating function in $\operatorname*{QSym}\nolimits_{\mathbf{k}}$.
This was discovered by Stanley and Gessel [... refs], and generalizes both the
definition of $L_{\alpha}$ for $\alpha$ a composition and the definition of a
Schur function. See \cite[proof of Corollary 5.29]{Reiner} and \cite[mainly
\S 7.19]{Stanley-EC2} for applications of this notion.

In \cite{Mal-Reu}, Malvenuto and Reutenauer have generalized the notion of a
$P$-partition to the notion of a $\Gamma$-partition, for $\Gamma$ a finite
directed graph whose arcs are partitioned into ``strict'' and ``weak'' arcs.
(Malvenuto and Reutenauer denote the graph by $G$ instead of $\Gamma$; we will
not follow their notation for reasons that should become clear in Section [...
add ref to section with group action]. We will also allow the set of weak arcs
and the set of strict arcs to be non-disjoint, and make a few other
non-substantial generalizations just to simplify the statements of our results.)

We begin by introducing the notion of graphs we will be using:

\begin{definition}
In the following, a \textit{directed graph} means a pair $\left(  V, A\right)
$, where $V$ is a set and $A$ is a subset of $V \times V$. If $\mathbf{D} =
\left(  V,A\right)  $ is a directed graph, then the elements of $V$ are called
the \textit{vertices} of $\mathbf{D}$, and the elements of $A$ are called the
\textit{arcs} of $\mathbf{D}$. A \textit{cycle} of a directed graph
$\mathbf{D} = \left(  V,A\right)  $ is defined to mean a sequence $\left(
v_{1}, v_{2}, \ldots, v_{k}\right)  $ of elements of $V$ such that $k > 1$ and
$v_{k} = v_{1}$ and such that, for every $i \in\left\{  1,2,\ldots
,k-1\right\}  $, the pair $\left(  v_{i}, v_{i+1}\right)  $ is an arc of
$\mathbf{D}$. A directed graph $\mathbf{D}$ is said to be \textit{acyclic} if
there are no cycles of $\mathbf{D}$. A directed graph $\mathbf{D} = \left(  V,
A\right)  $ is said to be \textit{finite} if the set $V$ is finite.
\end{definition}

Note that directed graphs (in this sense) can have no double arcs, and their
arcs carry no other information than what vertices they connect.

Next, we introduce the concept of a weak-strict digraph, mostly following
\cite{Mal-Reu} (except that we allow the set of weak arcs and the set of
strict arcs to have common elements):

\begin{definition}
A \textit{weak-strict digraph} means a triple $\Gamma= \left(  V,A_{w}%
,A_{s}\right)  $, where $V$, $A_{w}$ and $A_{s}$ are three sets such that
$\left(  V,A_{w}\cup A_{s}\right)  $ is a finite directed graph. (We don't
require $A_{w}$ and $A_{s}$ to be disjoint.) Given a weak-strict diagraph
$\Gamma= \left(  V,A_{w},A_{s}\right)  $, the elements of $A_{w}$ are called
the \textit{weak arcs} of our weak-strict digraph $\Gamma$, and the elements
of $A_{s}$ are called the \textit{strict arcs} of $\Gamma$. The elements of
$V$ are called the \textit{vertices} of $\Gamma$, and the set $V$ is called
the \textit{vertex set} of $\Gamma$.

To any weak-strict digraph $\Gamma=\left(  V,A_{w},A_{s}\right)  $, we can
assign the finite directed graph $\left(  V,A_{w}\cup A_{s}\right)  $. This
finite directed graph will be simply referred to as the \textquotedblleft
directed graph $\Gamma$\textquotedblright\ (although, of course, it does not
carry all the information that the weak-strict digraph $\Gamma$ carries).
Every notion defined for a finite directed graph can thus be applied to a
weak-strict digraph $\Gamma=\left(  V,A_{w},A_{s}\right)  $ simply by applying
it to this directed graph $\left(  V,A_{w}\cup A_{s}\right)  $. This way, for
example, the notion of an acyclic weak-strict digraph is well-defined. So a
weak-strict digraph $\left(  V,A_{w},A_{s}\right)  $ is acyclic if and only if
the directed graph $\left(  V,A_{w}\cup A_{s}\right)  $ is acyclic.
\end{definition}

The reason why we have required finiteness in this definition is simply to
avoid assuming it in all our statements below.

We next define some transformations on weak-strict digraphs:

\begin{definition}
\textbf{(a)} If $p$ is a pair of two objects, then we define a new pair
$\overline{p}$ by $\overline{p} = \left(  b,a\right)  $, where $p$ is written
in the form $\left(  a,b\right)  $. This pair $\overline{p}$ will be called
the \textit{reverse} of the pair $p$. Thus, in particular, $\overline{p}$ is
defined whenever $p$ is an arc of a directed graph.

\textbf{(b)} If $B$ is a set of arcs of a directed graph $D$, then
$\overline{B}$ will denote the set of the reverses of all arcs from $B$. In
other words,
\[
\overline{B} = \left\{  \left(  v,u\right)  \mid\left(  u,v\right)  \in B
\right\}  .
\]

\end{definition}

Next, we define the notion of ``$\Gamma$-partitions'' for a weak-strict
digraph $\Gamma$:

\begin{definition}
Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a weak-strict digraph. Let $X$
be a poset. We use the notations $\leq$ and $<$ for the smaller relation and
the smaller-or-equal relation, respectively, of the poset $X$. A $\Gamma
$\textit{-partition to }$X$ will mean a function $f:V \rightarrow X$ such that:

\textbf{(a)} every weak arc $\left(  u,v\right)  $ of $\Gamma$ satisfies
$f\left(  u\right)  \leq f\left(  v\right)  $;

\textbf{(b)} every strict arc $\left(  u,v\right)  $ of $\Gamma$ satisfies
$f\left(  u\right)  <f\left(  v\right)  $.

In the following, we regard $\mathbb{N}_{+}$ as a poset using the standard
smaller relation on $\mathbb{N}_{+}$ (so this poset is actually a totally
ordered set). When we don't explicitly mention $X$ and just speak of "$\Gamma
$-partitions", we always mean $\Gamma$-partitions to this poset $\mathbb{N}%
_{+}$.
\end{definition}

The notion of a $\Gamma$-partition generalizes Stanley's notions of a
$P$-partition and of a $\left(  P,\omega\right)  $-partition (we will see how
in Section \ref{sect.ppart}). While the added generality it provides is not of
much use in applications (this paper could have been written about $\left(
P,\omega\right)  $-partitions just as well!), it is helpful in simplifying the
proofs (the main advantage being that a weak-strict digraph is easier to
``tweak'', or modify, than a poset) and a little tad easier to apply in many
cases (e.g., to writing the fundamental quasisymmetric functions -- see
Section \ref{sect.ppart} below). In \cite{Mal-Reu}, Malvenuto and Reutenauer
put this notion to use in studying plethysms of quasisymmetric functions.

Let us connect $\Gamma$-partitions to $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ by defining a certain generating function, an idea
which goes back to Malvenuto and Reutenauer\footnote{A remark about our
notation: What we call $F_{\Gamma}$ in the following definition has been
denoted by $\Gamma\left(  G\right)  $ in the paper \cite{Mal-Reu} by Malvenuto
and Reutenauer, where their $G$ stands for the weak-strict digraph that we
call $\Gamma$, and their $\Gamma$ is a symbol signifying this generating
function. We found it difficult to adher to standard notation in this subject,
since we will later want to use the letter $G$ for a group.}:

\begin{definition}
\label{def.FGamma}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a weak-strict digraph.

Define a formal power series $F_{\Gamma}\in\mathbf{k}\left[  \left[
x_{1},x_{2},x_{3},\ldots\right]  \right]  $ by%
\[
F_{\Gamma}=\sum_{f\text{ is a }\Gamma\text{-partition}}\prod\limits_{p\in
V}x_{f\left(  p\right)  }.
\]
This is well-defined [... explain].
\end{definition}

Before Malvenuto and Reutenauer, various special cases of $F_{\Gamma}$ have
been studied, some of which are almost as general as $F_{\Gamma}$. The most
important one is the $P$-partition enumerator $F_{P,\omega}$ which we will
introduce in Section \ref{sect.ppart}. It first appeared in Gessel's
\cite{Gessel-multipar}, and in some special cases has been anticipated in the
work of Thomas \cite{Thomas-Bax}.

A warning is in order here. My notation imitates \cite{Reiner}; it (sadly)
conflicts with other notation in literature. In particular, what we denote by
$F_{\Gamma}$ is not a generalization of what Stanley calls $F_{P,\omega}$ in
\cite[\S 3.15]{Stanley-EC1} (but rather is a generalization of what he calls
$K_{P,\omega}$ in \cite[\S 7.19]{Stanley-EC2}).

\begin{example}
\label{ex.FGamma}Before we study $F_{\Gamma}$ in general, let us illustrate
its definition on a particular case.

For this example, let $\Gamma$ be the weak-strict digraph with vertex set
$\left\{  1,2,3,4,5\right\}  $, weak arcs $\left(  1,3\right)  $ and $\left(
2,5\right)  $, and strict arcs $\left(  1,2\right)  $, $\left(  3,4\right)  $
and $\left(  4,5\right)  $. Then, the $\Gamma$-partitions are the maps
$f:\left\{  1,2,3,4,5\right\}  \rightarrow\mathbb{N}_{+}$ satisfying $f\left(
1\right)  \leq f\left(  3\right)  $, $\left(  2\right)  \leq f\left(
5\right)  $, $f\left(  1\right)  <f\left(  2\right)  $, $f\left(  3\right)
<f\left(  4\right)  $ and $f\left(  4\right)  <f\left(  5\right)  $. Hence,
\begin{align*}
F_{\Gamma}  &  =\sum_{f\text{ is a }\Gamma\text{-partition}}\prod
\limits_{p\in\left\{  1,2,3,4,5\right\}  }x_{f\left(  p\right)  }%
=\sum_{\substack{f:\left\{  1,2,3,4,5\right\}  \rightarrow\mathbb{N}%
_{+};\\f\left(  1\right)  \leq f\left(  3\right)  ;\ f\left(  2\right)  \leq
f\left(  5\right)  ;\\f\left(  1\right)  <f\left(  2\right)  ;\ f\left(
3\right)  <f\left(  4\right)  ;\\f\left(  4\right)  <f\left(  5\right)
}}x_{f\left(  1\right)  }x_{f\left(  2\right)  }x_{f\left(  3\right)
}x_{f\left(  4\right)  }x_{f\left(  5\right)  }\\
&  =\sum_{\substack{\left(  i_{1},i_{2},i_{3},i_{4},i_{5}\right)
\in\mathbb{N}_{+}^{5};\\i_{1}\leq i_{3};\ i_{2}\leq i_{5};\ i_{1}%
<i_{2};\ i_{3}<i_{4};\ i_{4}<i_{5}}}x_{i_{1}}x_{i_{2}}x_{i_{3}}x_{i_{4}%
}x_{i_{5}}.
\end{align*}

\end{example}

Our first observation is:

\begin{proposition}
\label{prop.FGamma.QSym}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a
weak-strict digraph. Then, $F_{\Gamma} \in\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$.
\end{proposition}

Proposition \ref{prop.FGamma.QSym} can be proven by a standard argument,
similar to \cite[proof of Proposition 3.3.19]{LMvW}. It can actually
generalized to so-called scheduling problems and extended to quasisymmetric
functions in non-commuting variables -- see \cite[\S 4]{BreKli14} for the
definitions of these notions --, and still be proven by the same argument. We
are going to give a slight variation of this argument, which has the advantage
of proving the following explicit formula:

\begin{proposition}
\label{prop.FGamma.QSym.explicit}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $
be a weak-strict digraph.

Let us say that a $\Gamma$-partition $f$ is \textit{packed} if there exists
some $\ell\in\mathbb{N}$ such that $f\left(  V\right)  = \left\{
1,2,\ldots,\ell\right\}  $.

\textbf{(a)} If $f$ is any $\Gamma$-partition, then $f$ is packed if and only
if $f\left(  V\right)  =\left\{  1,2,\ldots,\left\vert V\right\vert \right\}
$.

\textbf{(b)} If $f$ is any packed $\Gamma$-partition, and if we write $\ell$
for $\left\vert f\left(  V\right)  \right\vert $, then
\[
\left(  \left\vert f^{-1}\left(  \left\{  1\right\}  \right)  \right\vert
,\left\vert f^{-1}\left(  \left\{  2\right\}  \right)  \right\vert
,\ldots,\left\vert f^{-1}\left(  \left\{  \ell\right\}  \right)  \right\vert
\right)
\]
is a composition of $\left\vert V\right\vert $. This composition will be
called $\operatorname*{ev}f$.

\textbf{(c)} We have
\[
F_{\Gamma} = \sum\limits_{f \text{ is a packed }\Gamma\text{-partition}}
M_{\operatorname*{ev} f}.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.FGamma.QSym.explicit} (sketched).][...]
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.FGamma.QSym} (sketched).][...]
\end{proof}

The quasisymmetric function $F_{\Gamma}$ already generalizes a number of
quasisymmetric functions appearing in literature; but it is so far not more
general than what has been classically constructed for $P$-partitions by
Gessel (see Section \ref{sect.ppart} below). But Malvenuto and Reutenauer have
extended it further:

\begin{definition}
For any set $Y$, we denote by $\mathbf{1}$ the map $Y \to\mathbb{N}_{+}$ that
sends everything to $1\in\mathbb{N}_{+}$. (The domain $Y$ of this map is going
to be clear from the context.)
\end{definition}

\begin{definition}
\label{def.FGammaw}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a
weak-strict digraph. Let $w:V\rightarrow\mathbb{N}_{+}$ be any map.

Define a formal power series $F_{\left(  \Gamma,w\right)  }\in\mathbf{k}%
\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  $ by%
\[
F_{\left(  \Gamma,w\right)  }=\sum_{f\text{ is a }\Gamma\text{-partition}%
}\prod\limits_{p\in V}x_{f\left(  p\right)  }^{w\left(  p\right)  }.
\]
This is well-defined [... explain].
\end{definition}

Note that the definition of $F_{\left(  \Gamma,w\right)  }$ would no longer
make sense if we would allow $w$ to be a map $V\rightarrow\mathbb{N}$ rather
than a map $V\rightarrow\mathbb{N}_{+}$ (not every sum converges!).

\begin{example}
The weak-strict digraph $\Gamma$ considered in Example \ref{ex.FGamma}
satisfies $F_{\left(  \Gamma,w\right)  }=\sum\limits_{\substack{\left(
i_{1},i_{2},i_{3},i_{4},i_{5}\right)  \in\mathbb{N}_{+}^{5};\\i_{1}\leq
i_{3};\ i_{2}\leq i_{5};\ i_{1}<i_{2};\ i_{3}<i_{4};\ i_{4}<i_{5}}}x_{i_{1}%
}^{w\left(  1\right)  }x_{i_{2}}^{w\left(  2\right)  }x_{i_{3}}^{w\left(
3\right)  }x_{i_{4}}^{w\left(  4\right)  }x_{i_{5}}^{w\left(  5\right)  }$ for
any map $w:\left\{  1,2,3,4,5\right\}  \rightarrow\mathbb{N}_{+}$.
\end{example}

In analogy to Proposition \ref{prop.FGamma.QSym}, we have:

\begin{proposition}
\label{prop.FGammaw.QSym}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a
weak-strict digraph. Let $w : V\rightarrow\mathbb{N}_{+}$ be any map. Then,
$F_{\left(  \Gamma,w\right)  }\in\operatorname*{QSym}\nolimits_{\mathbf{k}}$.
\end{proposition}

We have an analogue of Proposition \ref{prop.FGamma.QSym.explicit}
\textbf{(b)} and \textbf{(c)}:

\begin{proposition}
\label{prop.FGammaw.QSym.explicit}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $
be a weak-strict digraph. Let $w:V\rightarrow\mathbb{N}_{+}$ be any map.

\textbf{(b)} If $f$ is any packed $\Gamma$-partition, and if we write $\ell$
for $\left\vert f\left(  V\right)  \right\vert $, then
\[
\left(  \sum\limits_{p\in f^{-1}\left(  \left\{  1\right\}  \right)  }w\left(
p\right)  ,\sum\limits_{p\in f^{-1}\left(  \left\{  2\right\}  \right)
}w\left(  p\right)  ,\ldots,\sum\limits_{p\in f^{-1}\left(  \left\{
\ell\right\}  \right)  }w\left(  p\right)  \right)
\]
is a composition of $\sum\limits_{p\in V}w\left(  p\right)  $. This
composition will be called $\operatorname*{ev}_{w}f$.

\textbf{(c)} We have
\[
F_{\left(  \Gamma,w\right)  } = \sum\limits_{f \text{ is a packed }%
\Gamma\text{-partition}} M_{\operatorname*{ev}_{w} f}.
\]

\end{proposition}

(This proposition has no part \textbf{(a)} since there is nothing to
generalize about Proposition \ref{prop.FGamma.QSym.explicit} \textbf{(a)}.)

\begin{proof}
[Proof of Proposition \ref{prop.FGammaw.QSym.explicit} (sketched).]%
\textbf{(b)} [...]

\textbf{(c)} For any finite subset $S$ of $\mathbb{Z}$, there exists a unique
strictly increasing bijection $r:\left\{  1,2,\ldots,\left\vert S\right\vert
\right\}  \rightarrow S$. This strictly increasing bijection will be denoted
by $r_{S}$. Clearly, its inverse $r_{S}^{-1}$ is also strictly increasing (in
the sense that whenever $s$ and $t$ are elements of $S$ satisfying $s<t$, then
$r_{S}^{-1}\left(  s\right)  <r_{S}^{-1}\left(  t\right)  $).

Let us define the notion of a \textit{packing} of a $\Gamma$-partition.

In fact, let $f$ be a $\Gamma$-partition. Then, $f\left(  V\right)  $ is a
finite subset of $\mathbb{Z}$, and so the map $r_{f\left(  V\right)  }$ is a
strictly increasing bijection $\left\{  1,2,\ldots,\left\vert f\left(
V\right)  \right\vert \right\}  \rightarrow f\left(  V\right)  $. As we know,
$r_{f\left(  V\right)  }^{-1}$ also is a strictly increasing bijection. Now,
$r_{f\left(  V\right)  }^{-1}\circ f$ is well-defined (since the range of $f$
is $f\left(  V\right)  $, which coincides with the domain of $r_{f\left(
V\right)  }^{-1}$) and is also a $\Gamma$-partition (since $f$ is a $\Gamma
$-partition and $r_{f\left(  V\right)  }^{-1}$ is strictly increasing).
Moreover, $\left(  r_{f\left(  V\right)  }^{-1}\circ f\right)  \left(
V\right)  =r_{f\left(  V\right)  }^{-1}\left(  f\left(  V\right)  \right)
=\left\{  1,2,\ldots,\left\vert f\left(  V\right)  \right\vert \right\}  $
(since $r_{f\left(  V\right)  }$ is a bijection $\left\{  1,2,\ldots
,\left\vert f\left(  V\right)  \right\vert \right\}  \rightarrow f\left(
V\right)  $). Hence, $r_{f\left(  V\right)  }^{-1}\circ f$ is a packed
$\Gamma$-partition (due to Proposition \ref{prop.FGamma.QSym.explicit}
\textbf{(a)}). We call $r_{f\left(  V\right)  }^{-1}\circ f$ the
\textit{packing} of the $\Gamma$-partition $f$.

Now, forget that we fixed $f$. Thus, for every $\Gamma$-partition $f$, we have
defined the packing of the $\Gamma$-partition $f$. This packing is a packed
$\Gamma$-partition.

Now,%
\begin{align}
F_{\left(  \Gamma,w\right)  }  &  =\sum_{f\text{ is a }\Gamma\text{-partition}%
}\prod\limits_{p\in V}x_{f\left(  p\right)  }^{w\left(  p\right)  }%
=\sum_{\substack{g\text{ is a packed}\\\Gamma\text{-partition}}}\sum
_{\substack{f\text{ is a }\Gamma\text{-partition;}\\\text{the packing of
}f\text{ is }g}}\prod\limits_{p\in V}x_{f\left(  p\right)  }^{w\left(
p\right)  }\nonumber\\
&  =\sum_{\substack{f\text{ is a packed}\\\Gamma\text{-partition}}%
}\sum_{\substack{g\text{ is a }\Gamma\text{-partition;}\\\text{the packing of
}g\text{ is }f}}\prod\limits_{p\in V}x_{g\left(  p\right)  }^{w\left(
p\right)  } \label{pf.FGammaw.QSym.explicit.c.1}%
\end{align}
(here, we renamed the indices $g$ and $f$ in the two sums as $f$ and $g$).

Now, let us fix a packed $\Gamma$-partition $f$. We are going to show that
\begin{equation}
\sum_{\substack{g\text{ is a }\Gamma\text{-partition;}\\\text{the packing of
}g\text{ is }f}}\prod\limits_{p\in V}x_{g\left(  p\right)  }^{w\left(
p\right)  }=M_{\operatorname*{ev}\nolimits_{w}f}.
\label{pf.FGammaw.QSym.explicit.c.2}%
\end{equation}
First of all, let $\ell=\left\vert f\left(  V\right)  \right\vert $. Thus,%
\begin{equation}
\operatorname*{ev}\nolimits_{w}f=\left(  \sum\limits_{p\in f^{-1}\left(
\left\{  1\right\}  \right)  }w\left(  p\right)  ,\sum\limits_{p\in
f^{-1}\left(  \left\{  2\right\}  \right)  }w\left(  p\right)  ,\ldots
,\sum\limits_{p\in f^{-1}\left(  \left\{  \ell\right\}  \right)  }w\left(
p\right)  \right)  . \label{pf.FGammaw.QSym.explicit.c.3}%
\end{equation}
Let us write $\alpha_{k}$ for $\sum\limits_{p\in f^{-1}\left(  \left\{
k\right\}  \right)  }w\left(  p\right)  $ whenever $k\in\left\{
1,2,\ldots,\ell\right\}  $. Then, (\ref{pf.FGammaw.QSym.explicit.c.3})
rewrites as%
\[
\operatorname*{ev}\nolimits_{w}f=\left(  \alpha_{1},\alpha_{2},\ldots
,\alpha_{\ell}\right)  .
\]
Hence,%
\begin{align}
M_{\operatorname*{ev}\nolimits_{w}f}  &  =M_{\left(  \alpha_{1},\alpha
_{2},\ldots,\alpha_{\ell}\right)  }=\sum_{i_{1}<i_{2}<\cdots<i_{\ell}}%
x_{i_{1}}^{\alpha_{1}}x_{i_{2}}^{\alpha_{2}}\cdots x_{i_{\ell}}^{\alpha_{\ell
}}\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }M_{\left(
\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)  }\right) \nonumber\\
&  =\sum_{i_{1}<i_{2}<\cdots<i_{\ell}}\prod\limits_{k\in\left\{
1,2,\ldots,\ell\right\}  }x_{i_{k}}^{\alpha_{k}}.
\label{pf.FGammaw.QSym.explicit.c.5}%
\end{align}


But if $i_{1}$, $i_{2}$, $\ldots$, $i_{\ell}$ are some positive integers
satisfying $i_{1}<i_{2}<\cdots<i_{\ell}$, then $i_{k}=r_{\left\{  i_{1}%
,i_{2},\ldots,i_{\ell}\right\}  }\left(  k\right)  $ for every $k\in\left\{
1,2,\ldots,\ell\right\}  $ (by the definition of $r_{\left\{  i_{1}%
,i_{2},\ldots,i_{\ell}\right\}  }$). Thus, (\ref{pf.FGammaw.QSym.explicit.c.5}%
) becomes%
\begin{align}
M_{\operatorname*{ev}\nolimits_{w}f}  &  =\sum_{i_{1}<i_{2}<\cdots<i_{\ell}%
}\prod\limits_{k\in\left\{  1,2,\ldots,\ell\right\}  }\underbrace{x_{i_{k}%
}^{\alpha_{k}}}_{\substack{=x_{r_{\left\{  i_{1},i_{2},\ldots,i_{\ell
}\right\}  }\left(  k\right)  }^{\alpha_{k}}\\\text{(since }i_{k}=r_{\left\{
i_{1},i_{2},\ldots,i_{\ell}\right\}  }\left(  k\right)  \text{)}}}=\sum
_{i_{1}<i_{2}<\cdots<i_{\ell}}\prod\limits_{k\in\left\{  1,2,\ldots
,\ell\right\}  }x_{r_{\left\{  i_{1},i_{2},\ldots,i_{\ell}\right\}  }\left(
k\right)  }^{\alpha_{k}}\nonumber\\
&  =\sum\limits_{\substack{I\subseteq\mathbb{N}_{+};\\\left\vert I\right\vert
=\ell}}\prod\limits_{k\in\left\{  1,2,\ldots,\ell\right\}  }x_{r_{I}\left(
k\right)  }^{\alpha_{k}} \label{pf.FGammaw.QSym.explicit.c.Mevf}%
\end{align}
(here, we substituted $I$ for $\left\{  i_{1},i_{2},\ldots,i_{\ell}\right\}
$, because the map%
\begin{align*}
\left\{  \left(  i_{1},i_{2},\ldots,i_{\ell}\right)  \in\mathbb{N}_{+}^{\ell
}\ \mid\ i_{1}<i_{2}<\cdots<i_{\ell}\right\}   &  \rightarrow\left\{
I\subseteq\mathbb{N}_{+}\ \mid\ \left\vert I\right\vert =\ell\right\}  ,\\
\left(  i_{1},i_{2},\ldots,i_{\ell}\right)   &  \mapsto\left\{  i_{1}%
,i_{2},\ldots,i_{\ell}\right\}
\end{align*}
is a bijection).

On the other hand, recall that $f$ is a packed $\Gamma$-partition, so that
Proposition \ref{prop.FGamma.QSym.explicit} \textbf{(a)} yields $f\left(
V\right)  =\left\{  1,2,\ldots,\left\vert f\left(  V\right)  \right\vert
\right\}  =\left\{  1,2,\ldots,\ell\right\}  $ (since $\left\vert f\left(
V\right)  \right\vert =\ell$). If $g$ is a $\Gamma$-partition such that the
packing of $g$ is $f$, then $\left\vert g\left(  V\right)  \right\vert =\ell
$\ \ \ \ \footnote{\textit{Proof.} Let $g$ be a $\Gamma$-partition such that
the packing of $g$ is $f$. Then, $f=\left(  \text{the packing of }g\right)
=r_{g\left(  V\right)  }^{-1}\circ g$, so that $f\left(  V\right)  =\left(
r_{g\left(  V\right)  }^{-1}\circ g\right)  \left(  V\right)  =r_{g\left(
V\right)  }^{-1}\left(  g\left(  V\right)  \right)  $ and thus%
\[
\left\vert f\left(  V\right)  \right\vert =\left\vert r_{g\left(  V\right)
}^{-1}\left(  g\left(  V\right)  \right)  \right\vert =\left\vert g\left(
V\right)  \right\vert \ \ \ \ \ \ \ \ \ \ \left(  \text{since }r_{g\left(
V\right)  }^{-1}\text{ is a bijection}\right)
\]
and thus $\left\vert g\left(  V\right)  \right\vert =\left\vert f\left(
V\right)  \right\vert =\ell$, qed.}. Hence,%
\begin{equation}
\sum_{\substack{g\text{ is a }\Gamma\text{-partition;}\\\text{the packing of
}g\text{ is }f}}\prod\limits_{p\in V}x_{g\left(  p\right)  }^{w\left(
p\right)  }=\sum\limits_{\substack{I\subseteq\mathbb{N}_{+};\\\left\vert
I\right\vert =\ell}}\sum_{\substack{g\text{ is a }\Gamma\text{-partition;}%
\\\text{the packing of }g\text{ is }f;\\g\left(  V\right)  =I}}\prod
\limits_{p\in V}x_{g\left(  p\right)  }^{w\left(  p\right)  }.
\label{pf.FGammaw.QSym.explicit.c.7}%
\end{equation}


Now, fix a subset $I$ of $\mathbb{N}_{+}$ satisfying $\left\vert I\right\vert
=\ell$. We are going to show that there exists exactly one $\Gamma$-partition
$g$ such that the packing of $g$ is $f$ and such that $g\left(  V\right)  =I$;
this will be the $\Gamma$-partition $r_{I}\circ f$.

Indeed, it is first clear that $r_{I}\circ f$ is a $\Gamma$-partition (since
$f$ is a $\Gamma$-partition, and since $r_{I}$ is strictly increasing).
Moreover,
\begin{align*}
\left(  r_{I}\circ f\right)  \left(  V\right)   &  =r_{I}\left(
\underbrace{f\left(  V\right)  }_{=\left\{  1,2,\ldots,\ell\right\}  }\right)
=r_{I}\left(  \left\{  1,2,\ldots,\ell\right\}  \right) \\
&  =r_{I}\left(  \left\{  1,2,\ldots,\left|  I\right|  \right\}  \right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\ell=\left|  I\right|  \right) \\
&  = I
\end{align*}
(by the definition of $r_{I}$). Now, the packing of $r_{I}\circ f$ is (by its
definition) equal to
\begin{align*}
r_{\left(  r_{I}\circ f\right)  \left(  V\right)  }^{-1} \circ\left(
r_{I}\circ f\right)   &  = r_{I}^{-1}\circ\left(  r_{I} \circ f\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left(  r_{I}\circ f\right)  \left(
V\right)  = I\right) \\
&  = f.
\end{align*}
Altogether, we thus have shown that $r_{I}\circ f$ is a $\Gamma$-partition $g$
such that the packing of $g$ is $f$ and such that $g\left(  V\right)  =I$. We
now need to prove that it is the only such $\Gamma$-partition.

So fix any $\Gamma$-partition $g$ such that the packing of $g$ is $f$ and such
that $g\left(  V\right)  =I$. The packing of $g$ is $r_{g\left(  V\right)
}^{-1}\circ g$ (by the definition of the packing of $g$). Since the packing of
$g$ is the map $f$, this rewrites as follows: The map $f$ is $r_{g\left(
V\right)  }^{-1}\circ g$. Thus, $f = r_{g\left(  V\right)  }^{-1}\circ g =
r_{I}^{-1}\circ g$ (since $g\left(  V\right)  =I$). In other words,
$r_{I}\circ f=g$, so that $g = r_{I}\circ f$.

Let us now forget that we fixed $g$. We thus have shown that if $g$ is any
$\Gamma$-partition such that the packing of $g$ is $f$ and such that $g\left(
V\right)  =I$, then $g=r_{I}\circ f$. Hence, there exists at most one $\Gamma
$-partition $g$ such that the packing of $g$ is $f$ and such that $g\left(
V\right)  =I$. Combining this with the fact that $r_{I}\circ f$ is a $\Gamma
$-partition $g$ such that the packing of $g$ is $f$ and such that $g\left(
V\right)  =I$, we obtain the following: There exists exactly one $\Gamma
$-partition $g$ such that the packing of $g$ is $f$ and such that $g\left(
V\right)  =I$; this $\Gamma$-partition is $r_{I}\circ f$. Hence, the sum
$\sum\limits_{\substack{g\text{ is a }\Gamma\text{-partition;}\\\text{the
packing of }g\text{ is }f;\\g\left(  V\right)  =I}}\prod\limits_{p\in
V}x_{g\left(  p\right)  }^{w\left(  p\right)  }$ has precisely one term,
namely the term for $g=r_{I}\circ f$. Thus, this sum becomes
\begin{align}
&  \sum_{\substack{g\text{ is a }\Gamma\text{-partition;}\\\text{the packing
of }g\text{ is }f;\\g\left(  V\right)  =I}}\prod\limits_{p\in V}x_{g\left(
p\right)  }^{w\left(  p\right)  }\nonumber\\
&  =\prod_{p\in V}x_{\left(  r_{I}\circ f\right)  \left(  p\right)
}^{w\left(  p\right)  }=\prod_{p\in V}x_{r_{I}\left(  f\left(  p\right)
\right)  }^{w\left(  p\right)  }=\prod_{k\in\left\{  1,2,\ldots,\ell\right\}
}\underbrace{\prod_{\substack{p\in V;\\f\left(  p\right)  =k}}}_{=\prod_{p\in
f^{-1}\left(  \left\{  k\right\}  \right)  }}\underbrace{x_{r_{I}\left(
f\left(  p\right)  \right)  }^{w\left(  p\right)  }}_{=x_{r_{I}\left(
k\right)  }^{w\left(  p\right)  }\text{ (since }f\left(  p\right)  =k\text{)}%
}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \ \left(  \text{since }f\left(  p\right)  \in f\left(
V\right)  =\left\{  1,2,\ldots,\ell\right\}  \text{ for every }p\in V\right)
\nonumber\\
&  =\prod_{k\in\left\{  1,2,\ldots,\ell\right\}  }\underbrace{\prod_{p\in
f^{-1}\left(  \left\{  k\right\}  \right)  }x_{r_{I}\left(  k\right)
}^{w\left(  p\right)  }}_{\substack{=x_{r_{I}\left(  k\right)  }^{\sum_{p\in
f^{-1}\left(  \left\{  k\right\}  \right)  }w\left(  p\right)  }%
=x_{r_{I}\left(  k\right)  }^{\alpha_{k}}\\\text{(since }\sum\limits_{p\in
f^{-1}\left(  \left\{  k\right\}  \right)  }w\left(  p\right)  =\alpha
_{k}\\\text{(by the definition of }\alpha_{k}\text{))}}}=\prod_{k\in\left\{
1,2,\ldots,\ell\right\}  }x_{r_{I}\left(  k\right)  }^{\alpha_{k}}.
\label{pf.FGammaw.QSym.explicit.c.8}%
\end{align}


Now, forget that we fixed $I$. We thus have shown that every subset $I$ of
$\mathbb{N}_{+}$ satisfying $\left\vert I\right\vert =\ell$, the equality
(\ref{pf.FGammaw.QSym.explicit.c.8}) holds. Now,
(\ref{pf.FGammaw.QSym.explicit.c.7}) becomes%
\begin{align*}
\sum_{\substack{g\text{ is a }\Gamma\text{-partition;}\\\text{the packing of
}g\text{ is }f}}\prod\limits_{p\in V}x_{g\left(  p\right)  }^{w\left(
p\right)  }  &  =\sum\limits_{\substack{I\subseteq\mathbb{N}_{+};\\\left\vert
I\right\vert =\ell}}\underbrace{\sum_{\substack{g\text{ is a }\Gamma
\text{-partition;}\\\text{the packing of }g\text{ is }f;\\g\left(  V\right)
=I}}\prod\limits_{p\in V}x_{g\left(  p\right)  }^{w\left(  p\right)  }%
}_{\substack{=\prod_{k\in\left\{  1,2,\ldots,\ell\right\}  }x_{r_{I}\left(
k\right)  }^{\alpha_{k}}\\\text{(by (\ref{pf.FGammaw.QSym.explicit.c.8}))}}}\\
&  =\sum\limits_{\substack{I\subseteq\mathbb{N}_{+};\\\left\vert I\right\vert
=\ell}}\prod_{k\in\left\{  1,2,\ldots,\ell\right\}  }x_{r_{I}\left(  k\right)
}^{\alpha_{k}}=M_{\operatorname*{ev}\nolimits_{w}f}\ \ \ \ \ \ \ \ \ \ \left(
\text{by (\ref{pf.FGammaw.QSym.explicit.c.5})}\right)  .
\end{align*}
This proves (\ref{pf.FGammaw.QSym.explicit.c.2}).

Now, forget that we fixed $f$. We thus have shown that every packed $\Gamma
$-partition $f$ satisfies (\ref{pf.FGammaw.QSym.explicit.c.2}). The equality
(\ref{pf.FGammaw.QSym.explicit.c.1}) becomes%
\[
F_{\left(  \Gamma,w\right)  }=\sum_{\substack{f\text{ is a packed}%
\\\Gamma\text{-partition}}}\underbrace{\sum_{\substack{g\text{ is a }%
\Gamma\text{-partition;}\\\text{the packing of }g\text{ is }f}}\prod
\limits_{p\in V}x_{g\left(  p\right)  }^{w\left(  p\right)  }}%
_{=M_{\operatorname*{ev}\nolimits_{w}f}}=\sum_{\substack{f\text{ is a
packed}\\\Gamma\text{-partition}}}M_{\operatorname*{ev}\nolimits_{w}f}.
\]
This proves Proposition \ref{prop.FGammaw.QSym.explicit} \textbf{(c)}.
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.FGammaw.QSym} (sketched).][...]
\end{proof}

We notice that Proposition \ref{prop.FGamma.QSym} and Proposition
\ref{prop.FGamma.QSym.explicit} are particular cases of Proposition
\ref{prop.FGammaw.QSym} and Proposition \ref{prop.FGammaw.QSym.explicit},
respectively, obtained by setting $w$ equal to the map $\mathbf{1}%
:V\rightarrow\mathbb{N}_{+}$. In fact, we have the following:

\begin{proposition}
\label{prop.FGamma.w1}Let $\Gamma$ be a weak-strict digraph.

\textbf{(a)} We have $F_{\Gamma}=F_{\left(  \Gamma,\mathbf{1}\right)  }$.

\textbf{(b)} For any packed $\Gamma$-partition $f$, we have
$\operatorname*{ev}f=\operatorname*{ev}\nolimits_{\mathbf{1}}f$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.FGamma.w1} (sketched).][...]
\end{proof}

Let us give two families of examples of $F_{\left(  \Gamma,w\right)  }$,
exhibiting the $M_{\alpha}$ and the $L_{\alpha}$ as particular cases of this construction.

\begin{proposition}
\label{prop.FGammaw.M}Let $\alpha=\left(  \alpha_{1},\alpha_{2},\ldots
,\alpha_{\ell}\right)  $ be a composition. Let $\operatorname*{Path}%
\nolimits_{s}\alpha$ denote the weak-strict digraph%
\[
\left(  \left\{  1,2,\ldots,\ell\right\}  ,\ \varnothing,\ \left\{  \left(
i,i+1\right)  \ \mid\ i\in\left\{  1,2,\ldots,\ell-1\right\}  \right\}
\right)  .
\]
(Colloquially speaking, this is a directed graph which consists of a single
path on $\ell$ vertices, with all its arcs being strict.) Let $w\left(
\alpha\right)  $ be the map $\left\{  1,2,\ldots,\ell\right\}  \rightarrow
\mathbb{N}_{+}$ which sends every $i\in\left\{  1,2,\ldots,\ell\right\}  $ to
$\alpha_{i}$. Then, $F_{\left(  \operatorname*{Path}\nolimits_{s}%
\alpha,w\left(  \alpha\right)  \right)  }=M_{\alpha}$.
\end{proposition}

\begin{proposition}
\label{prop.FGamma.L}Let $\alpha$ be a composition. Let $n$ be the size of
$\alpha$. Let $\operatorname*{DPath}\alpha$ denote the weak-strict digraph%
\[
\left(  \left\{  1,2,\ldots,n\right\}  ,\ \left\{  \left(  i,i+1\right)
\ \mid\ i\in\left\{  1,2,\ldots,n-1\right\}  \setminus D\left(  \alpha\right)
\right\}  ,\ \left\{  \left(  i,i+1\right)  \ \mid\ i\in D\left(
\alpha\right)  \right\}  \right)  .
\]
(Colloquially speaking, this is a directed graph which consists of a single
path on $n$ vertices, with the $i$-th arc being strict if $i\in D\left(
\alpha\right)  $ and weak otherwise.) Then, $F_{\operatorname*{DPath}\alpha
}=L_{\alpha}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.FGamma.L} (sketched).][...]
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.FGamma.w1} (sketched).][...]
\end{proof}

The following proposition demonstrates that the skew Schur functions of
classical symmetric function theory are particular cases of the $F_{\Gamma}$
construction as well:

\begin{proposition}
\label{prop.FGamma.s}Let $\lambda\diagup\mu$ be a skew partition. (For this
and all other terminology of symmetric function theory, see, e.g.,
\cite[Chapter 7]{Stanley-EC2}, \cite[\S 2]{Reiner} and other sources.) Let $V$
denote the Young diagram of $\lambda\diagup\mu$ (regarded as a set). We draw
Young diagrams in English notation, so that cell $\left(  i,j\right)  $ is one
unit lower than cell $\left(  i-1,j\right)  $ but one unit to the right of
cell $\left(  i,j-1\right)  $. Let $A_{w}$ denote the set of all $\left(
a,b\right)  \in V^{2}$ such that the cell $b$ is the right neighbor of $a$.
Let $A_{s}$ denote the set of all $\left(  a,b\right)  \in V^{2}$ such that
the cell $b$ is the lower neighbor of $a$. Then, $F_{\left(  V,A_{w}%
,A_{s}\right)  }$ is the Schur function $s_{\lambda\diagup\mu}$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.FGamma.s} (sketched).][...]
\end{proof}

The dual immaculate quasisymmetric functions introduced in \cite[\S 3.7]%
{BBSSZ} are also particular case of the $F_{\Gamma}$ construction:

\begin{proposition}
\label{prop.FGamma.dI}Let $\alpha= \left(  \alpha_{1}, \alpha_{2}, \ldots,
\alpha_{\ell}\right)  $ be a composition. Define the \textit{diagram} of
$\alpha$ to be the set of all $\left(  i,j\right)  \in\mathbb{N}_{+}^{2}$ such
that $j \leq\alpha_{i}$. The elements of this set are called the
\textit{cells} of this diagram. More generally, the same notions that are
defined for Young diagrams (such as rows, columns, descents, English notation,
etc.) can be defined for diagrams of compositions analogously. We draw
diagrams of compositions in English notation (but of course, this no longer
means that the rows weakly decrease in length from top to bottom).

Let $V$ denote the diagram of $\alpha$. Let $A_{w}$ denote the set of all
$\left(  a,b\right)  \in V^{2}$ such that the cell $b$ is the right neighbor
of $a$. Let $A_{s}$ denote the set of all $\left(  a,b\right)  \in V^{2}$ such
that the cell $b$ is the lower neighbor of $a$ and both cells lie \textbf{in
the first column} (i.e., they have their second coordinates equal to $1$).
Then, $F_{\left(  V,A_{w},A_{s}\right)  }$ is the dual immaculate function
$\mathfrak{S}_{\alpha}$ defined in \cite[\S 3.7]{BBSSZ}.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.FGamma.dI} (sketched).][... Use
\cite[Proposition 3.36]{BBSSZ} and compare the notion of an immaculate tableau
with that of a $\Gamma$-partition; then recall Proposition
\ref{prop.FGamma.QSym.explicit}.]
\end{proof}

Let us reap the first harvest from the notion of $\Gamma$-partitions. We will
introduce the disjoint union of two weak-strict digraphs and show that the
$F_{\Gamma}$ corresponding to that disjoint union is the product of the
$F_{\Gamma}$'s corresponding to the two weak-strict digraphs:

\begin{definition}
\label{def.disjointunion}Let $\Gamma_{0}=\left(  V_{0},A_{w0},A_{s0}\right)  $
and $\Gamma_{1}=\left(  V_{1},A_{w1},A_{s1}\right)  $ be two weak-strict
digraphs. The \textit{disjoint union} of $\Gamma_{0}$ and $\Gamma_{1}$ is
defined as the weak-strict digraph $\left(  V,A_{w},A_{s}\right)  $, where%
\begin{align*}
V  &  =\left\{  \left(  v,0\right)  \ \mid\ v\in V_{0}\right\}  \cup\left\{
\left(  v,1\right)  \ \mid\ v\in V_{1}\right\}  ;\\
A_{w}  &  =\left\{  \left(  \left(  a,0\right)  ,\left(  b,0\right)  \right)
\ \mid\ \left(  a,b\right)  \in A_{w0}\right\}  \cup\left\{  \left(  \left(
a,1\right)  ,\left(  b,1\right)  \right)  \ \mid\ \left(  a,b\right)  \in
A_{w1}\right\}  ;\\
A_{s}  &  =\left\{  \left(  \left(  a,0\right)  ,\left(  b,0\right)  \right)
\ \mid\ \left(  a,b\right)  \in A_{s0}\right\}  \cup\left\{  \left(  \left(
a,1\right)  ,\left(  b,1\right)  \right)  \ \mid\ \left(  a,b\right)  \in
A_{s1}\right\}  .
\end{align*}
In more friendly terms, the disjoint union of $\Gamma_{0}$ and $\Gamma_{1}$ is
defined as the weak-strict digraph whose vertex set is the disjoint union of
the vertex sets of $\Gamma_{0}$ and $\Gamma_{1}$, and whose set of weak (resp.
strict) arcs is the union of the sets of weak (resp. strict) arcs of
$\Gamma_{0}$ and $\Gamma_{1}$ (with their endpoints relabelled accordingly).
We denote the disjoint union of $\Gamma_{0}$ and $\Gamma_{1}$ by $\Gamma
_{0}\Gamma_{1}$. When $V_{0}$ and $V_{1}$ are disjoint, we identify $V$ with
the set-theoretic union $V_{0}\cup V_{1}$ (by equating each $v\in V_{0}$ with
$\left(  v,0\right)  \in V$, each $v\in V_{1}$ with $\left(  v,1\right)  \in
V$) and similarly identifying $A_{w}$ with the union $A_{w0}\cup A_{w1}$ (by
equation $\left(  a,b\right)  \in A_{w0}$ with $\left(  \left(  a,0\right)
,\left(  b,0\right)  \right)  \in A_{w}$, etc.) and $A_{s}$ with the union
$A_{s0}\cup A_{s1}$; in this case, we thus simply have $\Gamma_{0}\Gamma
_{1}=\left(  V_{0}\cup V_{1},A_{w0}\cup A_{w1},A_{s0}\cup A_{s1}\right)  $.
\end{definition}

\begin{proposition}
\label{prop.FGamma.disjointunion}Let $\Gamma_{0}$ and $\Gamma_{1}$ be two
weak-strict digraphs. Then, $F_{\Gamma_{0}\Gamma_{1}}=F_{\Gamma_{0}}\cdot
F_{\Gamma_{1}}$.
\end{proposition}

\begin{proposition}
\label{prop.FGammaw.disjointunion}Let $\Gamma_{0}=\left(  V_{0},A_{w0}%
,A_{s0}\right)  $ and $\Gamma_{1}=\left(  V_{1},A_{w1},A_{s1}\right)  $ be two
weak-strict digraphs such that $V_{0}$ and $V_{1}$ are disjoint. Identify the
disjoint union $\Gamma_{0}\Gamma_{1}$ with $\left(  V_{0}\cup V_{1},A_{w0}\cup
A_{w1},A_{s0}\cup A_{s1}\right)  $. Let $w:V_{0}\cup V_{1}\rightarrow
\mathbb{N}_{+}$ be a map. Then,%
\[
F_{\Gamma_{0}\Gamma_{1},w}=F_{\Gamma_{0},w\mid_{V_{0}}}\cdot F_{\Gamma
_{1},w\mid_{V_{1}}}.
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.FGamma.disjointunion} (sketched).][...]
\end{proof}

\begin{proof}
[Proof of Proposition \ref{prop.FGammaw.disjointunion} (sketched).][...]
\end{proof}

[...]

[... Second proof of $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ being closed
under mult!]

\section{\label{sect.hopf}The Hopf algebra structure on $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$}

We have so far been regarding $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ as
an algebra -- with algebra structure inherited from $\mathbf{k}\left[  \left[
x_{1},x_{2},x_{3},\ldots\right]  \right]  $. In this section, we are going to
endow $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ with a further structure --
that of a Hopf algebra.

We will not give an introduction into Hopf algebras here, as this has already
been done by various authors in various references -- for example,
\cite{Montg-Hopf}, \cite[\S 1]{Reiner}, \cite[\S 1-\S 2]{Manchon-HA},
\cite{Abe-HA}, \cite{Sweedler-HA}, \cite{Dasca-HA} and \cite[Chapter
7]{Fresse-Op} each include the definitions and the basic properties of
bialgebras and Hopf algebras, and we will not need anything beyond that. [...
check that the latter claim is true!] (While most authors discussing Hopf
algebras limit themselves to Hopf algebras over fields, the notion can be
defined over any commutative ring in the same way, and all properties of Hopf
algebras which are sufficiently elementary to be used in the present papers
continue to hold in this generality.)

[... introduce coalgebras and/or give references]

Let us define the coalgebra structure on $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$. This is commonly done (e.g., in \cite[\S 5]{Reiner})
using what is usually called \textquotedblleft alphabet doubling
trick\textquotedblright; we are going to give a more down-to-earth definition instead:

\begin{definition}
\label{def.QSym.coproduct} \textbf{(a)} In the following, the tensor sign
$\otimes$ without subscript always means $\otimes_{\mathbb{k}}$.

\textbf{(b)} We define a $\mathbf{k}$-linear map $\Delta:\operatorname*{QSym}%
\nolimits_{\mathbf{k}}\rightarrow\operatorname*{QSym}\nolimits_{\mathbf{k}%
}\otimes\operatorname*{QSym}\nolimits_{\mathbf{k}}$ by requiring that every
composition $\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)  $
satisfy
\[
\Delta\left(  M_{\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{\ell}\right)
}\right)  =\sum\limits_{k=0}^{\ell}M_{\left(  \alpha_{1},\alpha_{2}%
,\ldots,\alpha_{k}\right)  }\otimes M_{\left(  \alpha_{k+1},\alpha
_{k+2},\ldots,\alpha_{\ell}\right)  }.
\]
This is clearly well-defined, because the $M_{\left(  \alpha_{1},\alpha
_{2},\ldots,\alpha_{\ell}\right)  }$ with $\left(  \alpha_{1},\alpha
_{2},\ldots,\alpha_{\ell}\right)  $ ranging over all compositions form a
$\mathbf{k}$-basis of $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ (by
Proposition \ref{prop.M.basis}). The map $\Delta$ is called the
\textit{coproduct} of $\operatorname*{QSym}\nolimits_{\mathbf{k}}$.

\textbf{(c)} We further define a $\mathbf{k}$-linear map $\varepsilon
:\operatorname*{QSym}\nolimits_{\mathbf{k}}\rightarrow\mathbf{k}$ by requiring
that every composition $\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{\ell
}\right)  $ satisfy
\[
\varepsilon\left(  M_{\left(  \alpha_{1},\alpha_{2},\ldots,\alpha_{\ell
}\right)  }\right)  =\left[  \ell=0\right]
\]
(where we are using the notation of Definition \ref{def.iverson}). This is
clearly well-defined, because the $M_{\left(  \alpha_{1},\alpha_{2}%
,\ldots,\alpha_{\ell}\right)  }$ with $\left(  \alpha_{1},\alpha_{2}%
,\ldots,\alpha_{\ell}\right)  $ ranging over all compositions form a
$\mathbf{k}$-basis of $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ (by
Proposition \ref{prop.M.basis}). The map $\varepsilon$ is called the
\textit{counity} of $\operatorname*{QSym}\nolimits_{\mathbf{k}}$.
\end{definition}

We state some basic properties of these maps $\Delta$ and $\varepsilon$:

\begin{proposition}
\label{prop.QSym.bialgebra} \textbf{(a)} The triple $\left(
\operatorname*{QSym}\nolimits_{\mathbf{k}},\Delta,\varepsilon\right)  $ is a
$\mathbf{k}$-coalgebra. That is, the diagrams%
\begin{align}
&
%TCIMACRO{\TeXButton{Delta coassociative}{{
%\xymatrixcolsep{4pc}
%\xymatrix{
%\QSym\ar[r]^{\Delta} \ar[d]_{\Delta} & \QSym\otimes\QSym\ar[d]^{\Delta
%\otimes\id} \\
%\QSym\otimes\QSym\ar[r]_-{\id\otimes\Delta} & \QSym\otimes\QSym\otimes\QSym}
%}}}%
%BeginExpansion
{
\xymatrixcolsep{4pc}
\xymatrix{
\QSym\ar[r]^{\Delta} \ar[d]_{\Delta} & \QSym\otimes\QSym\ar[d]^{\Delta
\otimes\id} \\
\QSym\otimes\QSym\ar[r]_-{\id\otimes\Delta} & \QSym\otimes\QSym\otimes\QSym}
}%
%EndExpansion
,\label{prop.QSym.bialgebra.a.1}\\
&
%TCIMACRO{\TeXButton{epsilon counital with k QSym}{{
%\xymatrixcolsep{3pc}
%\xymatrix{
%\QSym\ar[dr]_{i_1} \ar[r]^-{\Delta} & \QSym\otimes\QSym\ar[d]^-{\varepsilon
%\otimes\id} \\
%& \bk\otimes\QSym}
%}}}%
%BeginExpansion
{
\xymatrixcolsep{3pc}
\xymatrix{
\QSym\ar[dr]_{i_1} \ar[r]^-{\Delta} & \QSym\otimes\QSym\ar[d]^-{\varepsilon
\otimes\id} \\
& \bk\otimes\QSym}
}%
%EndExpansion
\ \ \ \ \ \ \ \ \ \ \text{and}\label{prop.QSym.bialgebra.a.2}\\
&
%TCIMACRO{\TeXButton{epsilon counital with QSym k}{{
%\xymatrixcolsep{3pc}
%\xymatrix{
%\QSym\ar[dr]_{i_2} \ar[r]^-{\Delta} & \QSym\otimes\QSym\ar[d]^-{\id
%\otimes\varepsilon} \\
%& \QSym\otimes\bk}
%}} }%
%BeginExpansion
{
\xymatrixcolsep{3pc}
\xymatrix{
\QSym\ar[dr]_{i_2} \ar[r]^-{\Delta} & \QSym\otimes\QSym\ar[d]^-{\id
\otimes\varepsilon} \\
& \QSym\otimes\bk}
}
%EndExpansion
\label{prop.QSym.bialgebra.a.3}%
\end{align}
are commutative, where $i_{1}:\operatorname*{QSym}\nolimits_{\mathbf{k}%
}\rightarrow\mathbf{k}\otimes\operatorname*{QSym}\nolimits_{\mathbf{k}}$ and
$i_{2}:\operatorname*{QSym}\nolimits_{\mathbf{k}}\rightarrow
\operatorname*{QSym}\nolimits_{\mathbf{k}}\otimes\mathbf{k}$ are the canonical
$\mathbf{k}$-module isomorphisms.

\textbf{(b)} The $\mathbf{k}$-coalgebra $\left(  \operatorname*{QSym}%
\nolimits_{\mathbf{k}},\Delta,\varepsilon\right)  $ combined with the
$\mathbf{k}$-algebra structure on $\operatorname*{QSym}\nolimits_{\mathbf{k}}$
forms a $\mathbf{k}$-bialgebra. In other words, the maps $\Delta
:\operatorname*{QSym}\nolimits_{\mathbf{k}}\rightarrow\operatorname*{QSym}%
\nolimits_{\mathbf{k}}\otimes\operatorname*{QSym}\nolimits_{\mathbf{k}}$ and
$\varepsilon:\operatorname*{QSym}\nolimits_{\mathbf{k}}\rightarrow\mathbf{k}$
are $\mathbf{k}$-algebra homomorphisms.
\end{proposition}

This proposition would have more or less fallen into our hands had we used the
alphabet doubling trick; with our definition, it is less obvious. However, we
can obtain it easily once we understand how $\Delta$ and $\varepsilon$ act on
the $F_{\left(  \Gamma,w\right)  }$. To do so, first we need a definition:

\begin{definition}
\label{def.admcut}Let $\mathbf{D}=\left(  V,A\right)  $ be a directed graph.
An \textit{admissible cut} of $\mathbf{D}$ will denote a pair $\left(
P,Q\right)  $, where $P$ and $Q$ are subsets of $V$ satisfying $P\cup Q=V$ and
$P\cap Q=\varnothing$ such that there exists no $\left(  q,p\right)  \in A$
satisfying $p\in P$ and $q\in Q$. We denote by $\operatorname*{Adm}\mathbf{D}$
the set of all admissible cuts of $\mathbf{D}$.
\end{definition}

\begin{definition}
\label{def.admcut.Gamma}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a
weak-strict digraph. An \textit{admissible cut} of $\Gamma$ will mean an
admissible cut of the directed graph $\Gamma$ (that is, of the directed graph
$\left(  V,A_{w}\cup A_{s}\right)  $). We denote by $\operatorname*{Adm}%
\Gamma$ the set of all admissible cuts of $\Gamma$.

Let $P$ be a subset of $V$. Then, $\Gamma\mid_{P}$ will denote the weak-strict
digraph $\left(  P,\ A_{w}\cap\left(  P\times P\right)  ,\ A_{s}\cap\left(
P\times P\right)  \right)  $. (This is simply the weak-strict digraph obtained
by keeping only the vertices from $P$ and the weak and strict arcs connecting
these vertices to each other.)
\end{definition}

The notion of admissible cuts is classical, although more usually applied to
trees rather than to directed graphs (see, e.g., \cite[\S II.9.3]{Manchon-HA},
albeit the definition there is in our opinion not the best). We will use it
here to compute the coproduct and the counity on $F_{\left(  \Gamma,w\right)
}$:

\begin{proposition}
\label{prop.FGammaw.De}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a
weak-strict digraph. Let $w:V\rightarrow\mathbb{N}_{+}$ be any map.

\textbf{(a)} We have%
\[
\Delta\left(  F_{\left(  \Gamma,w\right)  }\right)  =\sum_{\left(  P,Q\right)
\in\operatorname*{Adm}\Gamma}F_{\left(  \Gamma\mid_{P},w\mid_{P}\right)
}\otimes F_{\left(  \Gamma\mid_{Q},w\mid_{Q}\right)  }.
\]


\textbf{(b)} We have%
\[
\varepsilon\left(  F_{\left(  \Gamma,w\right)  }\right)  =\left[  \left\vert
V\right\vert =0\right]  .
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.FGammaw.De} (sketched).][... use packed stuff here]
\end{proof}

Now,

\begin{proof}
[Proof of Proposition \ref{prop.QSym.bialgebra} (sketched).][... do this using
$\Gamma$-partitions!]
\end{proof}

We have so far shown that $\operatorname*{QSym}\nolimits_{\mathbf{k}}$ is a
$\mathbf{k}$-bialgebra. Is it a Hopf algebra? There is a sense in which the
answer is \textquotedblleft obviously yes\textquotedblright, because
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$ is a case of what is called a
connected graded $\mathbf{k}$-bialgebra, and such $\mathbf{k}$-bialgebras are
automatically Hopf algebras (see \cite[Proposition 1.36]{Reiner} for a proof,
and \cite[Corollary II.3.2]{Manchon-HA} for a more general result). We will,
however, reprove this result in a different way, and derive an explicit
formula for the antipode on $F_{\left(  \Gamma,w\right)  }$ for a wide class
of weak-strict digraphs $\Gamma$.

\section{\label{sect.antipode}The antipode of $F_{\Gamma}$}

\begin{definition}
\label{def.comp.omega}Let $\alpha$ be a composition. Let $n=\left\vert
\alpha\right\vert $. Then, we define a composition $\omega\left(
\alpha\right)  $ of $n$ by%
\[
\omega\left(  \alpha\right)  =\operatorname*{comp}\nolimits_{n}\left(
\left\{  1,2,\ldots,n-1\right\}  \setminus\left\{  n-i\ \mid\ i\in D\left(
\alpha\right)  \right\}  \right)  .
\]

\end{definition}

\begin{proposition}
\label{prop.comp.omega}Let $\alpha$ be a composition. Then, $\omega\left(
\omega\left(  \alpha\right)  \right)  =\alpha$.
\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.comp.omega} (sketched).][...]
\end{proof}

Let us now state the existence of an antipode on $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ and an explicit formula for it:

\begin{theorem}
\label{thm.QSym.antipode}Define a $\mathbf{k}$-linear map
$S:\operatorname*{QSym}\nolimits_{\mathbf{k}}\rightarrow\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ by requiring that every composition $\alpha$ satisfy%
\[
S\left(  L_{\alpha}\right)  =\left(  -1\right)  ^{\left\vert \alpha\right\vert
}L_{\omega\left(  \alpha\right)  }.
\]
This is clearly well-defined, because the $L_{\alpha}$ with $\alpha$ ranging
over the compositions form a basis of $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ (by Corollary \ref{cor.L.basis}).

Then, $S$ is an antipode of the $\mathbf{k}$-bialgebra $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$.
\end{theorem}

We will actually prove a much more general statement about how $S$ acts.
First, we define two ways to construct new weak-strict digraphs from a given one:

\begin{definition}
Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a weak-strict digraph. We
define a new weak-strict digraph $\Gamma^{\prime}$ by
\[
\Gamma^{\prime}=\left(  V,A_{w},\overline{A_{s}}\right)
\]
(that is, it is the result of reversing all strict arcs in $\Gamma$). We
define a further weak-strict digraph $\omega\left(  \Gamma\right)  $ by%
\[
\omega\left(  \Gamma\right)  =\left(  V,\overline{A_{s}},\overline{A_{w}%
}\right)
\]
(that is, the weak-strict digraph obtained from $\Gamma$ by reversing all arcs
and exchanging strict and weak arcs). Notice that $\Gamma^{\prime\prime
}=\Gamma$ and $\omega\left(  \omega\left(  \Gamma\right)  \right)  =\Gamma$.
\end{definition}

\begin{theorem}
\label{thm.FGammaw}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a
weak-strict digraph. Let $w:V\rightarrow\mathbb{N}_{+}$ be any map. Assume
that $\Gamma^{\prime}$ is acyclic. Then,
\[
S\left(  F_{\left(  \Gamma,w\right)  }\right)  =\left(  -1\right)
^{\left\vert V\right\vert }F_{\left(  \omega\left(  \Gamma\right)  ,w\right)
}.
\]

\end{theorem}

\begin{corollary}
\label{cor.FGamma}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a weak-strict
digraph. Assume that $\Gamma^{\prime}$ is acyclic. Then,
\[
S\left(  F_{\Gamma}\right)  =\left(  -1\right)  ^{\left\vert V\right\vert
}F_{\omega\left(  \Gamma\right)  }.
\]

\end{corollary}

Of course, Corollary \ref{cor.FGamma} is obtained from Theorem
\ref{thm.FGammaw} by setting $w=\mathbf{1}$.

Theorem \ref{thm.FGammaw} is more or less equivalent to \cite[Theorem
3.1]{Mal-Reu}, while Corollary \ref{cor.FGamma} is more or less equivalent to
\cite[Lemma 3.2]{Mal-Reu}. We are saying \textquotedblleft more or
less\textquotedblright\ since the statements in \cite{Mal-Reu} are formulated
in a slightly different way (mainly, instead of the weight map $w$ in Theorem
\ref{thm.FGammaw}, the authors of \cite{Mal-Reu} are considering vertices
connected by \textquotedblleft undirected edges\textquotedblright\ -- in our
opinion, a slightly awkward technique) and burdened by some unnecessary
conditions which are easy to lift (the statements in \cite{Mal-Reu} require
$A_{w}$ to be distinct from $A_{s}$, and $\Gamma$ to be acyclic as well as
$\Gamma^{\prime}$). We will see in somewhat more detail how to derive Theorem
\ref{thm.FGammaw} from \cite[Theorem 3.1]{Mal-Reu} in the Second proof of
Theorem \ref{thm.FGammaw} below.

Also, Corollary \ref{cor.FGamma} is easily seen to be equivalent to the rather
well-known \cite[Corollary 5.27]{Reiner}, a cornerstone of $P$-partition
theory (we will say more about this in Section \ref{sect.ppart}). The main
difference between these two facts is that we are using $\Gamma$-partitions
instead of $P$-partitions; the condition that $\Gamma^{\prime}$ be acyclic is
precisely what is needed to reduce the former to the latter. However, it seems
to us that the setting of $\Gamma$-partitions is more natural.

We are going to give three proofs of Theorem \ref{thm.FGammaw}. The reader is
advised to only read the first one (which, to our knowledge, is new and
probably the most enlightening) unless interested in the history of the
subject. The other two proofs are merely there to show that Theorem
\ref{thm.FGammaw} is not very novel: the second proof derives it from
\cite[Theorem 3.1]{Mal-Reu}, whereas the third derives it from \cite[Corollary
5.27]{Reiner}.

The vehicle that carries us to the proof of Theorems \ref{thm.QSym.antipode}
and to our first proof of Theorem \ref{thm.FGammaw} is the following fact
(which, per se, involves neither Hopf algebras nor quasisymmetric functions):

\begin{proposition}
\label{prop.cuts}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a weak-strict
digraph. Assume that $\Gamma^{\prime}$ is acyclic. Let $X$ be a totally
ordered set (regarded as a poset). Let $A$ be a topological commutative ring.
For every $v\in V$ and $u\in X$, let $z_{v,u}$ be an element of $A$. Assume
that, for every subset $S$ of $V$, the sum $\sum\limits_{f\in X^{S}}%
\prod\limits_{v\in S}z_{v,f\left(  v\right)  }$ converges with respect to the
topology on $A$. (Notice that this happens, for example, when $X=\mathbb{N}%
_{+}$, $A=\mathbf{k}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]
$ and $z_{v,u}=x_{u}$.)

For every subset $S$ of $V$, define an element $Z_{S,X}\in A$ by%
\[
Z_{S,X}=\sum\limits_{\substack{f\text{ is a }\Gamma\mid_{S}\text{-partition}%
\\\text{to }X}}\prod\limits_{v\in S}z_{v,f\left(  v\right)  }.
\]
(This sum converges, since it is a subsum of the convergent sum $\sum
\limits_{f\in X^{S}}\prod\limits_{v\in S}z_{v,f\left(  v\right)  }$.) Also,
for every subset $S$ of $V$, define an element $Z_{S,X}^{\prime}\in A$ by%
\[
Z_{S,X}^{\omega}=\sum\limits_{\substack{f\text{ is a }\omega\left(
\Gamma\right)  \mid_{S}\text{-partition}\\\text{to }X}}\prod\limits_{v\in
S}z_{v,f\left(  v\right)  }.
\]
(This sum converges, since it is a subsum of the convergent sum $\sum
\limits_{f\in X^{S}}\prod\limits_{v\in S}z_{v,f\left(  v\right)  }$.)

\textbf{(a)} We have%
\[
\sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}\left(  -1\right)
^{\left\vert Q\right\vert }Z_{P,X}Z_{Q,X}^{\omega}=\left[  V=\varnothing
\right]  .
\]


\textbf{(b)} We have
\[
\sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}\left(  -1\right)
^{\left\vert P\right\vert }Z_{P,X}^{\omega}Z_{Q,X}=\left[  V=\varnothing
\right]  .
\]

\end{proposition}

We shall prove Proposition \ref{prop.cuts} with the help of a sign-reversed
involution. The idea of using sign-reversing involutions to identify antipodes
of Hopf algebras is natural and not new (see, e.g., \cite[proof of Theorem
5.11]{Reiner}, and, more recently, \cite{BenSag}), but the crux of such
involutive proofs is the precise construction of the involution. The one that
we will use will proceed by \textquotedblleft exiling\textquotedblright\ a
certain element of $V$ from $P$ into $Q$ or vice versa; this is again far from
being a novel motive, but the choice of the element to be exiled is (in our
opinion) interesting.

\begin{proof}
[Proof of Proposition \ref{prop.cuts} (sketched).]\textbf{(a)} Proposition
\ref{prop.cuts} \textbf{(a)} can be checked immediately in the case when
$V=\varnothing$. Hence, for the rest of this proof, we can WLOG assume that
$V\neq\varnothing$. Let us assume this.

Let us fix a $\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma$ first. We have%
\[
Z_{P,X}=\sum\limits_{\substack{f\text{ is a }\Gamma\mid_{P}\text{-partition}%
\\\text{to }X}}\prod\limits_{v\in P}z_{v,f\left(  v\right)  }=\sum
\limits_{\substack{f:P\rightarrow X;\\f\text{ is a }\Gamma\mid_{P}%
\text{-partition to }X}}\prod\limits_{v\in P}z_{v,f\left(  v\right)  }%
\]
and%
\begin{align*}
Z_{Q,X}^{\omega}  &  =\sum\limits_{\substack{f\text{ is a }\omega\left(
\Gamma\right)  \mid_{Q}\text{-partition}\\\text{to }X}}\prod\limits_{v\in
Q}z_{v,f\left(  v\right)  }=\sum\limits_{\substack{f:Q\rightarrow X;\\f\text{
is a }\omega\left(  \Gamma\right)  \mid_{Q}\text{-partition to }X}%
}\prod\limits_{v\in Q}z_{v,f\left(  v\right)  }\\
&  =\sum\limits_{\substack{g:Q\rightarrow X;\\g\text{ is a }\omega\left(
\Gamma\right)  \mid_{Q}\text{-partition to }X}}\prod\limits_{v\in
Q}z_{v,g\left(  v\right)  }.
\end{align*}
Multiplying these two equalities, we obtain%
\begin{align}
Z_{P,X}Z_{Q,X}^{\omega}  &  =\left(  \sum\limits_{\substack{f:P\rightarrow
X;\\f\text{ is a }\Gamma\mid_{P}\text{-partition to }X}}\prod\limits_{v\in
P}z_{v,f\left(  v\right)  }\right)  \left(  \sum
\limits_{\substack{g:Q\rightarrow X;\\g\text{ is a }\omega\left(
\Gamma\right)  \mid_{Q}\text{-partition to }X}}\prod\limits_{v\in
Q}z_{v,g\left(  v\right)  }\right) \nonumber\\
&  =\sum\limits_{\substack{f:P\rightarrow X;\\f\text{ is a }\Gamma\mid
_{P}\text{-partition to }X}}\sum\limits_{\substack{g:Q\rightarrow X;\\g\text{
is a }\omega\left(  \Gamma\right)  \mid_{Q}\text{-partition to }X}}\left(
\prod\limits_{v\in P}z_{v,f\left(  v\right)  }\right)  \left(  \prod
\limits_{v\in Q}z_{v,g\left(  v\right)  }\right) \nonumber\\
&  =\sum\limits_{\substack{\left(  f,g\right)  ;\\f:P\rightarrow
X;\ g:Q\rightarrow X;\\f\text{ is a }\Gamma\mid_{P}\text{-partition to
}X;\\g\text{ is a }\omega\left(  \Gamma\right)  \mid_{Q}\text{-partition to
}X}}\left(  \prod\limits_{v\in P}z_{v,f\left(  v\right)  }\right)  \left(
\prod\limits_{v\in Q}z_{v,g\left(  v\right)  }\right) \nonumber\\
&  =\sum\limits_{\substack{h:V\rightarrow X;\\h\mid_{P}\text{ is a }\Gamma
\mid_{P}\text{-partition to }X;\\h\mid_{Q}\text{ is a }\omega\left(
\Gamma\right)  \mid_{Q}\text{-partition to }X}}\left(  \prod\limits_{v\in
P}\underbrace{z_{v,\left(  h\mid_{P}\right)  \left(  v\right)  }%
}_{=z_{v,h\left(  v\right)  }}\right)  \left(  \prod\limits_{v\in
Q}\underbrace{z_{v,\left(  h\mid_{Q}\right)  \left(  v\right)  }%
}_{=z_{v,h\left(  v\right)  }}\right) \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we substituted }\left(  h\mid_{P},h\mid_{Q}\right)  \text{ for
}\left(  f,g\right)  \text{,}\\
\text{since the pairs }\left(  f,g\right)  \text{ of maps }f:P\rightarrow
X\text{ and }g:Q\rightarrow X\text{ are in}\\
\text{1-to-1 correspondence with the maps }h:V\rightarrow X\text{, and the}\\
\text{former pair }\left(  f,g\right)  \text{ can be reconstructed from its
respective}\\
h\text{ by }\left(  f,g\right)  =\left(  h\mid_{P},h\mid_{Q}\right)
\end{array}
\right) \nonumber\\
&  =\sum\limits_{\substack{h:V\rightarrow X;\\h\mid_{P}\text{ is a }\Gamma
\mid_{P}\text{-partition to }X;\\h\mid_{Q}\text{ is a }\omega\left(
\Gamma\right)  \mid_{Q}\text{-partition to }X}}\underbrace{\left(
\prod\limits_{v\in P}z_{v,h\left(  v\right)  }\right)  \left(  \prod
\limits_{v\in Q}z_{v,h\left(  v\right)  }\right)  }_{=\prod\limits_{v\in
V}z_{v,h\left(  v\right)  }}\nonumber\\
&  =\sum\limits_{\substack{h:V\rightarrow X;\\h\mid_{P}\text{ is a }\Gamma
\mid_{P}\text{-partition to }X;\\h\mid_{Q}\text{ is a }\omega\left(
\Gamma\right)  \mid_{Q}\text{-partition to }X}}\prod\limits_{v\in
V}z_{v,h\left(  v\right)  }. \label{pf.cuts.1}%
\end{align}


Now, forget that we fixed $\left(  P,Q\right)  $. We thus have proven
(\ref{pf.cuts.1}) for every $\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma
$. Now,%
\begin{align*}
&  \sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}\left(  -1\right)
^{\left\vert Q\right\vert }\underbrace{Z_{P,X}Z_{Q,X}^{\omega}}%
_{\substack{=\sum\limits_{\substack{h:V\rightarrow X;\\h\mid_{P}\text{ is a
}\Gamma\mid_{P}\text{-partition to }X;\\h\mid_{Q}\text{ is a }\omega\left(
\Gamma\right)  \mid_{Q}\text{-partition to }X}}\prod\limits_{v\in
V}z_{v,h\left(  v\right)  }\\\text{(by (\ref{pf.cuts.1}))}}}\\
&  =\sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}\left(  -1\right)
^{\left\vert Q\right\vert }\sum\limits_{\substack{h:V\rightarrow X;\\h\mid
_{P}\text{ is a }\Gamma\mid_{P}\text{-partition to }X;\\h\mid_{Q}\text{ is a
}\omega\left(  \Gamma\right)  \mid_{Q}\text{-partition to }X}}\prod
\limits_{v\in V}z_{v,h\left(  v\right)  }\\
&  =\sum\limits_{h:V\rightarrow X}\prod\limits_{v\in V}z_{v,h\left(  v\right)
}\sum\limits_{\substack{\left(  P,Q\right)  \in\operatorname*{Adm}%
\Gamma;\\h\mid_{P}\text{ is a }\Gamma\mid_{P}\text{-partition to }%
X;\\h\mid_{Q}\text{ is a }\omega\left(  \Gamma\right)  \mid_{Q}%
\text{-partition to }X}}\left(  -1\right)  ^{\left\vert Q\right\vert }.
\end{align*}
Hence, in order to prove Proposition \ref{prop.cuts} \textbf{(a)}, it is
enough to show that every map $h:V\rightarrow X$ satisfies%
\begin{equation}
\sum\limits_{\substack{\left(  P,Q\right)  \in\operatorname*{Adm}%
\Gamma;\\h\mid_{P}\text{ is a }\Gamma\mid_{P}\text{-partition to }%
X;\\h\mid_{Q}\text{ is a }\omega\left(  \Gamma\right)  \mid_{Q}%
\text{-partition to }X}}\left(  -1\right)  ^{\left\vert Q\right\vert }=0
\label{pf.cuts.goal2}%
\end{equation}
(because once (\ref{pf.cuts.goal2}) will be proven, we will be able to
conclude that%
\begin{align*}
&  \sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}\left(  -1\right)
^{\left\vert Q\right\vert }Z_{P,X}Z_{Q,X}^{\omega}\\
&  =\sum\limits_{h:V\rightarrow X}\prod\limits_{v\in V}z_{v,h\left(  v\right)
}\underbrace{\sum\limits_{\substack{\left(  P,Q\right)  \in\operatorname*{Adm}%
\Gamma;\\h\mid_{P}\text{ is a }\Gamma\mid_{P}\text{-partition to }%
X;\\h\mid_{Q}\text{ is a }\omega\left(  \Gamma\right)  \mid_{Q}%
\text{-partition to }X}}\left(  -1\right)  ^{\left\vert Q\right\vert }%
}_{\substack{=0\\\text{(by (\ref{pf.cuts.goal2}))}}}=\sum
\limits_{h:V\rightarrow X}\prod\limits_{v\in V}z_{v,h\left(  v\right)  }0\\
&  =0=\left[  V=\varnothing\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{since
}V\neq\varnothing\right)
\end{align*}
). It is (\ref{pf.cuts.goal2}) that we will now be proving.

So let $h:V\rightarrow X$ be any map. We need to show that
(\ref{pf.cuts.goal2}) holds.

We will use the notations $<$, $\leq$, $>$ and $\geq$ for the smaller
relation, the smaller-or-equal relation, the greater relation and the
greater-or-equal relation, respectively, of the poset $X$.

Let us first define a certain set $\mathfrak{C}$. Namely, we let
$\mathfrak{C}$ be the set of all pairs $\left(  P,Q\right)  $ of subsets of
$V$ which satisfy the following five properties:

\textit{Property C1:} For any $a\in V$ and any $b\in P$ satisfying $\left(
a,b\right)  \in A_{w}$, we have $h\left(  a\right)  \leq h\left(  b\right)  $.

\textit{Property C2:} For any $a\in V$ and any $b\in P$ satisfying $\left(
a,b\right)  \in A_{s}$, we have $h\left(  a\right)  <h\left(  b\right)  $.

\textit{Property C3:} For any $a\in Q$ and any $b\in V$ satisfying $\left(
a,b\right)  \in A_{w}$, we have $h\left(  a\right)  >h\left(  b\right)  $.

\textit{Property C4:} For any $a\in Q$ and any $b\in V$ satisfying $\left(
a,b\right)  \in A_{s}$, we have $h\left(  a\right)  \geq h\left(  b\right)  $.

\textit{Property C5:} We have $P\cup Q=V$ and $P\cap Q=\varnothing$.

Now, our first claim is the following:

\textit{Claim 1:} Let $\left(  P,Q\right)  $ be a pair of subsets of $V$.
Then, $\left(  P,Q\right)  $ belongs to $\mathfrak{C}$ if and only if the
following three properties hold:

\textit{Property S1:} We have $\left(  P,Q\right)  \in\operatorname*{Adm}%
\Gamma$.

\textit{Property S2:} The map $h\mid_{P}$ is a $\Gamma$-partition to $X$.

\textit{Property S3:} The map $h\mid_{Q}$ is a $\omega\left(  \Gamma\right)
\mid_{Q}$-partition to $X$.

\textit{Proof of Claim 1:} Let us first assume that the Properties S1, S2 and
S3 hold.

We have $\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma$ (since Property S1
holds). In other words, $\left(  P,Q\right)  $ is an admissible cut of the
directed graph $\Gamma=\left(  V,A_{w}\cup A_{s}\right)  $. In other words,
$P$ and $Q$ are subsets of $V$ satisfying $P\cup Q=V$ and $P\cap
Q=\varnothing$ such that
\begin{equation}
\text{there exists no }\left(  q,p\right)  \in A_{w}\cup A_{s}\text{
satisfying }p\in P\text{ and }q\in Q. \label{pf.cuts.Adm}%
\end{equation}
As a consequence, Property C5 holds, so that $Q=V\setminus P$ and
$P=V\setminus Q$.

We know that $h\mid_{P}$ is a $\Gamma\mid_{P}$-partition to $X$ (since
Property S2 holds). In other words,
\begin{equation}
\text{every }\left(  u,v\right)  \in P\times P\text{ satisfying }\left(
u,v\right)  \in A_{w}\text{ satisfies }h\left(  u\right)  \leq h\left(
v\right)  , \label{pf.cuts.hP1}%
\end{equation}
and%
\begin{equation}
\text{every }\left(  u,v\right)  \in P\times P\text{ satisfying }\left(
u,v\right)  \in A_{s}\text{ satisfies }h\left(  u\right)  <h\left(  v\right)
. \label{pf.cuts.hP2}%
\end{equation}


We know that $h\mid_{Q}$ is a $\omega\left(  \Gamma\right)  \mid_{Q}%
$-partition to $X$ (since Property S3 holds). In other words,%
\begin{equation}
\text{every }\left(  u,v\right)  \in Q\times Q\text{ satisfying }\left(
u,v\right)  \in\overline{A_{s}}\text{ satisfies }h\left(  u\right)  \leq
h\left(  v\right)  , \label{pf.cuts.hQ1}%
\end{equation}
and%
\begin{equation}
\text{every }\left(  u,v\right)  \in Q\times Q\text{ satisfying }\left(
u,v\right)  \in\overline{A_{w}}\text{ satisfies }h\left(  u\right)  <h\left(
v\right)  . \label{pf.cuts.hQ2}%
\end{equation}


Now, let us prove that Property C1 holds. In fact, let $a\in V$ and $b\in P$
be such that $\left(  a,b\right)  \in A_{w}$. If we had $a\in Q$, then
$\left(  a,b\right)  \in A_{w}\subseteq A_{w}\cup A_{s}$ would contradict
(\ref{pf.cuts.Adm}) (applied to $q=a$ and $p=b$). Hence, we cannot have $a\in
Q$. We thus have $a\in V\setminus Q=P$, and now $h\left(  a\right)  \leq
h\left(  b\right)  $ follows from (\ref{pf.cuts.hP1}) (applied to $u=a$ and
$v=b$). This proves Property C1.

Similarly we can prove Property C2 (using (\ref{pf.cuts.hP2}) instead of
(\ref{pf.cuts.hP1})).

Let us now show that Property C3 holds. In fact, let $a\in Q$ and $b\in V$ be
such that $\left(  a,b\right)  \in A_{w}$. If we had $b\in P$, then $\left(
a,b\right)  \in A_{w}\subseteq A_{w}\cup A_{s}$ would contradict
(\ref{pf.cuts.Adm}) (applied to $q=a$ and $p=b$). Hence, we cannot have $b\in
P$. We thus have $b\in V\setminus P=Q$. But $\left(  a,b\right)  \in A_{w}$
shows that $\left(  b,a\right)  =\overline{\left(  a,b\right)  }\in
\overline{A_{w}}$, so that (\ref{pf.cuts.hQ2}) (applied to $u=b$ and $v=a$)
yields $h\left(  b\right)  <h\left(  a\right)  $. In other words, $h\left(
a\right)  >h\left(  b\right)  $. This proves Property C3.

Analogously we can prove Property C4 (but this time we would have to derive
$h\left(  b\right)  \leq h\left(  a\right)  $ from (\ref{pf.cuts.hQ1}) instead
of deriving $h\left(  b\right)  <h\left(  a\right)  $ from (\ref{pf.cuts.hQ2})).

We thus know that the pair $\left(  P,Q\right)  $ satisfies all five
Properties C1, C2, C3, C4 and C5. By the definition of $\mathfrak{C}$, this
means precisely that the pair $\left(  P,Q\right)  $ belongs to $\mathfrak{C}$.

Now, forget that we assumed that the Properties S1, S2 and S3 hold. We thus
have shown that%
\begin{equation}
\left(  \text{if the Properties S1, S2 and S3 hold, then }\left(  P,Q\right)
\text{ belongs to }\mathfrak{C}\right)  . \label{pf.cuts.C1.pf.1}%
\end{equation}


Now, let us assume that $\left(  P,Q\right)  $ belongs to $\mathfrak{C}$. By
the definition of $\mathfrak{C}$, this means that the pair $\left(
P,Q\right)  $ satisfies all five Properties C1, C2, C3, C4 and C5.

From Property C5, we conclude that $P\cup Q=V$ and $P\cap Q=\varnothing$.

Let us now see that there exists no $\left(  q,p\right)  \in A_{w}\cup A_{s}$
satisfying $p\in P$ and $q\in Q$. In fact, assume the contrary. Then, there
exists a $\left(  q,p\right)  \in A_{w}\cup A_{s}$ satisfying $p\in P$ and
$q\in Q$. Consider such a $\left(  q,p\right)  $. We have $\left(  q,p\right)
\in A_{w}\cup A_{s}$. Let us assume (for the sake of contradiction) that
$\left(  q,p\right)  \in A_{w}$. Then, Property C3 (applied to $\left(
a,b\right)  =\left(  q,p\right)  $) yields $h\left(  q\right)  >h\left(
p\right)  $. But Property C1 (applied to $\left(  a,b\right)  =\left(
q,p\right)  $) yields $h\left(  q\right)  \leq h\left(  p\right)  $, which
contradicts $h\left(  q\right)  >h\left(  p\right)  $. This contradiction
shows that our assumption (that $\left(  q,p\right)  \in A_{w}$) was wrong.
Hence, we cannot have $\left(  q,p\right)  \in A_{w}$. So we have $\left(
q,p\right)  \notin A_{w}$. Since $\left(  q,p\right)  \in A_{w}\cup A_{s}$,
this yields $\left(  q,p\right)  \in\left(  A_{w}\cup A_{s}\right)  \setminus
A_{w}\subseteq A_{s}$. Thus, Property C2 (applied to $\left(  a,b\right)
=\left(  q,p\right)  $) yields $h\left(  q\right)  <h\left(  p\right)  $. But
Property C4 (applied to $\left(  a,b\right)  =\left(  q,p\right)  $) yields
$h\left(  q\right)  \geq h\left(  p\right)  $, which contradicts $h\left(
q\right)  <h\left(  p\right)  $. This contradiction shows that our assumption
was wrong. We thus have proven that there exists no $\left(  q,p\right)  \in
A_{w}\cup A_{s}$ satisfying $p\in P$ and $q\in Q$. This (combined with the
fact that $P\cup Q=V$ and $P\cap Q=\varnothing$) shows that $\left(
P,Q\right)  $ is an admissible cut of the directed graph $\left(  V,A_{w}\cup
A_{s}\right)  $. In other words, $\left(  P,Q\right)  $ is an admissible cut
of the directed graph $\Gamma$ (since the directed graph $\Gamma$ is defined
as $\left(  V,A_{w}\cup A_{s}\right)  $). In other words, $\left(  P,Q\right)
\in\operatorname*{Adm}\Gamma$. Property S1 thus holds.

Next, let us prove Property S2. Let $\left(  u,v\right)  $ be a weak arc of
$\Gamma\mid_{P}$. Then, $\left(  u,v\right)  \in A_{w}\cap\left(  P\times
P\right)  $ (because of how $\Gamma\mid_{P}$ is defined). In other words,
$\left(  u,v\right)  \in A_{w}$, $u\in P$ and $v\in P$. Property C1 (applied
to $a=u$ and $b=v$) yields $h\left(  u\right)  \leq h\left(  v\right)  $.
Since $u\in P$ and $v\in P$, we can rewrite this as $\left(  h\mid_{P}\right)
\left(  u\right)  \leq\left(  h\mid_{P}\right)  \left(  v\right)  $. Now
forget that we fixed $\left(  u,v\right)  $. We have thus proven that every
weak arc $\left(  u,v\right)  $ of $\Gamma\mid_{P}$ satisfies $\left(
h\mid_{P}\right)  \left(  u\right)  \leq\left(  h\mid_{P}\right)  \left(
v\right)  $. Combining this with the fact that every strict arc $\left(
u,v\right)  $ of $\Gamma\mid_{P}$ satisfies $\left(  h\mid_{P}\right)  \left(
u\right)  <\left(  h\mid_{P}\right)  \left(  v\right)  $ (the proof of this is
analogous, but we now have to use Property C2 instead of Property C1), we
conclude that $h\mid_{P}$ is a $\Gamma\mid_{P}$-partition to $X$. In other
words, Property S2 holds.

Let us prove Property S3 now. Let $\left(  u,v\right)  $ be a weak arc of
$\omega\left(  \Gamma\right)  \mid_{Q}$. Then, $\left(  u,v\right)
\in\overline{A_{s}}\cap\left(  Q\times Q\right)  $ (because $\omega\left(
\Gamma\right)  =\left(  V,\overline{A_{s}},\overline{A_{w}}\right)  $ and thus
\newline$\omega\left(  \Gamma\right)  \mid_{Q}=\left(  Q,\overline{A_{s}}%
\cap\left(  Q\times Q\right)  ,\overline{A_{w}}\cap\left(  Q\times Q\right)
\right)  $). In other words, $\left(  u,v\right)  \in\overline{A_{s}}$, $u\in
Q$ and $v\in Q$. Since $\left(  u,v\right)  \in\overline{A_{s}}$, we have
$\left(  v,u\right)  \in A_{s}$. Property C4 (applied to $a=v$ and $b=u$) thus
yields $h\left(  v\right)  \geq h\left(  u\right)  $. In other words,
$h\left(  u\right)  \leq h\left(  v\right)  $. Since $u\in Q$ and $v\in Q$, we
can rewrite this as $\left(  h\mid_{Q}\right)  \left(  u\right)  \leq\left(
h\mid_{Q}\right)  \left(  v\right)  $. Now forget that we fixed $\left(
u,v\right)  $. We have thus proven that every weak arc $\left(  u,v\right)  $
of $\omega\left(  \Gamma\right)  \mid_{Q}$ satisfies $\left(  h\mid
_{Q}\right)  \left(  u\right)  \leq\left(  h\mid_{Q}\right)  \left(  v\right)
$. Combining this with the fact that every strict arc $\left(  u,v\right)  $
of $\omega\left(  \Gamma\right)  \mid_{Q}$ satisfies $\left(  h\mid
_{P}\right)  \left(  u\right)  <\left(  h\mid_{P}\right)  \left(  v\right)  $
(the proof of this is analogous, but we now have to use Property C3 instead of
Property C4), we conclude that $h\mid_{Q}$ is a $\omega\left(  \Gamma\right)
\mid_{Q}$-partition to $X$. In other words, Property S3 holds.

We have thus proven that all three Properties S1, S2 and S3 hold. Now, forget
that we assumed that $\left(  P,Q\right)  $ belongs to $\mathfrak{C}$. We thus
have shown that%
\[
\left(  \text{if }\left(  P,Q\right)  \text{ belongs to }\mathfrak{C}\text{,
then the Properties S1, S2 and S3 hold}\right)  .
\]
Combined with (\ref{pf.cuts.C1.pf.1}), this proves that $\left(  P,Q\right)  $
belongs to $\mathfrak{C}$ if and only if the Properties S1, S2 and S3 hold.
Claim 1 is thus proven.

Clearly, the summation sign $\sum\limits_{\substack{\left(  P,Q\right)
\in\operatorname*{Adm}\Gamma;\\h\mid_{P}\text{ is a }\Gamma\mid_{P}%
\text{-partition to }X;\\h\mid_{Q}\text{ is a }\omega\left(  \Gamma\right)
\mid_{Q}\text{-partition to }X}}$ in (\ref{pf.cuts.goal2}) can be rewritten as
$\sum\limits_{\substack{\left(  P,Q\right)  \text{ is a pair of subsets of
}V;\\\text{the Properties S1, S2 and S3 hold}}}$. Due to Claim 1, the latter
summation sign can be replaced by $\sum\limits_{\substack{\left(  P,Q\right)
\text{ is a pair of subsets of }V;\\\left(  P,Q\right)  \text{ belongs to
}\mathfrak{C}}}=\sum\limits_{\left(  P,Q\right)  \in\mathfrak{C}}$. Hence,
(\ref{pf.cuts.goal2}) is equivalent to%
\begin{equation}
\sum\limits_{\substack{\left(  P,Q\right)  \in\mathfrak{C}}}\left(  -1\right)
^{\left\vert Q\right\vert }=0. \label{pf.cuts.goal3o}%
\end{equation}
Thus, instead of proving (\ref{pf.cuts.goal2}), it is enough to prove
(\ref{pf.cuts.goal3o}). Let us introduce the notation $\operatorname*{snd}U$
for the second component of an ordered pair $U$ (so that $\operatorname*{snd}%
\left(  P,Q\right)  =Q$ for any ordered pair $\left(  P,Q\right)  $). Then,
(\ref{pf.cuts.goal3o}) further rewrites as%
\begin{equation}
\sum\limits_{\substack{U\in\mathfrak{C}}}\left(  -1\right)  ^{\left\vert
\operatorname*{snd}U\right\vert }=0. \label{pf.cuts.goal3}%
\end{equation}
Hence, our goal is now to prove (\ref{pf.cuts.goal3}).

In order to prove this, it clearly is enough to construct a map $\Theta
:\mathfrak{C}\rightarrow\mathfrak{C}$ satisfying the following three properties:

\textit{Property Th1:} We have $\Theta\circ\Theta=\operatorname*{id}%
\nolimits_{\mathfrak{C}}$.

\textit{Property Th2:} Every $U\in\mathfrak{C}$ satisfies $\left(  -1\right)
^{\left\vert \operatorname*{snd}\left(  \Phi\left(  U\right)  \right)
\right\vert }=-\left(  -1\right)  ^{\left\vert \operatorname*{snd}U\right\vert
}$.

\textit{Property Th3:} Every $U\in\mathfrak{C}$ satisfies $\Theta\left(
U\right)  \neq U$.

In fact, once a map $\Theta$ satisfying the Properties Th1, Th2 and Th3 is
constructed, we can quickly conclude that (\ref{pf.cuts.goal3}) holds by
fixing any total order on the set $\mathfrak{C}$ (which will be referred to
using the $>$ and $<$ symbols) and arguing that%
\begin{align*}
\sum\limits_{\substack{U\in\mathfrak{C}}}\left(  -1\right)  ^{\left\vert
\operatorname*{snd}U\right\vert }  &  =\sum\limits_{\substack{U\in
\mathfrak{C};\\\Theta\left(  U\right)  >U}}\left(  -1\right)  ^{\left\vert
\operatorname*{snd}U\right\vert }+\sum\limits_{\substack{U\in\mathfrak{C}%
;\\\Theta\left(  U\right)  <U}}\left(  -1\right)  ^{\left\vert
\operatorname*{snd}U\right\vert }\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{because every }U\in\mathfrak{C}\text{
satisfies }\Theta\left(  U\right)  \neq U\text{ (by Property Th3)}\right) \\
&  =\sum\limits_{\substack{U\in\mathfrak{C};\\\Theta\left(  U\right)
>U}}\left(  -1\right)  ^{\left\vert \operatorname*{snd}U\right\vert
}+\underbrace{\sum\limits_{\substack{U\in\mathfrak{C};\\\Theta\left(
\Theta\left(  U\right)  \right)  <\Theta\left(  U\right)  }}}_{\substack{=\sum
\limits_{\substack{U\in\mathfrak{C};\\U<\Theta\left(  U\right)  }%
}\\\text{(since Property 1}\\\text{yields }\Theta\left(  \Theta\left(
U\right)  \right)  =U\text{)}}}\underbrace{\left(  -1\right)  ^{\left\vert
\operatorname*{snd}\left(  \Theta\left(  U\right)  \right)  \right\vert }%
}_{\substack{=-\left(  -1\right)  ^{\left\vert \operatorname*{snd}U\right\vert
}\\\text{(by Property Th2)}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have substituted }\Theta\left(  U\right)  \text{ for }U\text{
in the second sum}\\
\text{(since the map }\Theta:\mathfrak{C}\rightarrow\mathfrak{C}\text{ is a
bijection (by Property Th1))}%
\end{array}
\right) \\
&  =\sum\limits_{\substack{U\in\mathfrak{C};\\\Theta\left(  U\right)
>U}}\left(  -1\right)  ^{\left\vert \operatorname*{snd}U\right\vert
}-\underbrace{\sum\limits_{\substack{U\in\mathfrak{C};\\U<\Theta\left(
U\right)  }}}_{=\sum\limits_{\substack{U\in\mathfrak{C};\\\Theta\left(
U\right)  >U}}}\left(  -1\right)  ^{\left\vert \operatorname*{snd}U\right\vert
}\\
&  =\sum\limits_{\substack{U\in\mathfrak{C};\\\Theta\left(  U\right)
>U}}\left(  -1\right)  ^{\left\vert \operatorname*{snd}U\right\vert }%
-\sum\limits_{\substack{U\in\mathfrak{C};\\\Theta\left(  U\right)  >U}}\left(
-1\right)  ^{\left\vert \operatorname*{snd}U\right\vert }=0.
\end{align*}
Hence, it remains to construct a map $\Theta$ satisfying the Properties Th1,
Th2 and Th3.

Before we can define our map $\Theta$, we shall introduce some more notations.

We say that an element $v \in V$ is a \textit{swing voter} if it satisfies the
following four properties:

\textit{Property SW1:} For any $u \in V$ satisfying $\left(  u, v\right)  \in
A_{w}$, we have $h\left(  v\right)  \geq h\left(  u\right)  $.

\textit{Property SW2:} For any $u \in V$ satisfying $\left(  u, v\right)  \in
A_{s}$, we have $h\left(  v\right)  > h\left(  u\right)  $.

\textit{Property SW3:} For any $u \in V$ satisfying $\left(  v, u\right)  \in
A_{w}$, we have $h\left(  v\right)  > h\left(  u\right)  $.

\textit{Property SW4:} For any $u \in V$ satisfying $\left(  v, u\right)  \in
A_{s}$, we have $h\left(  v\right)  \geq h\left(  u\right)  $.

Our next goal is to show that there exists at least one swing voter.

In fact, recall that the set $V$ is nonempty, so that $h\left(  V\right)  $ is
nonempty as well. Thus, $h\left(  V\right)  $ is a nonempty finite subset of
the totally ordered set $X$. Hence, the maximum element $\max\left(  h\left(
V\right)  \right)  $ of $h\left(  V\right)  $ is well-defined. Let $M$ be the
set of all $w\in V$ such that $h\left(  w\right)  =\max\left(  h\left(
V\right)  \right)  $. Then, $M$ is nonempty.

Consider the weak-strict digraph $\Gamma^{\prime}\mid_{M}$ as a directed
graph. This directed graph $\Gamma^{\prime}\mid_{M}$ is acyclic (since
$\Gamma^{\prime}$ is acyclic), and its vertex set $M$ is nonempty and finite.
Hence, there exists a vertex $v\in M$ such that no arc of $\Gamma^{\prime}%
\mid_{M}$ starts\footnote{We say that an arc \textit{starts} at $v$ if it has
the form $\left(  v,u\right)  $ for some $u\in V$.} at $v$ (because it is
known that whenever $\mathbf{D}$ is an acyclic finite directed graph with
nonempty vertex set, there exists at least one vertex $v$ of $\mathbf{D}$ such
that no arc of $\mathbf{D}$ starts at $v$). Consider this $v$. We are going to
show that $v$ is a swing voter.

First of all, $v$ belongs to the set $M$ of all $w\in V$ such that $h\left(
w\right)  =\max\left(  h\left(  V\right)  \right)  $. As a consequence,%
\begin{equation}
\text{every }u\in V\text{ satisfies }h\left(  u\right)  \leq h\left(
v\right)  , \label{pf.cuts.M1}%
\end{equation}
and
\begin{equation}
\text{every }u\in V\text{ such that }h\left(  u\right)  \geq h\left(
v\right)  \text{ must belong to }M. \label{pf.cuts.M2}%
\end{equation}
From (\ref{pf.cuts.M1}), we conclude immediately that $v$ satisfies Property
SW1 and Property SW4.

Let us next prove that Property SW2 holds. Let $u\in V$ be such that $\left(
u,v\right)  \in A_{s}$. Assume (for the sake of contradiction) that $h\left(
u\right)  \geq h\left(  v\right)  $. Then, (\ref{pf.cuts.M2}) shows that $u$
belongs to $M$. But $\left(  u,v\right)  \in A_{s}$, so that $\left(
v,u\right)  = \overline{\left(  u,v\right)  } \in\overline{A_{s}} \subseteq
A_{w} \cup\overline{A_{s}}$. Thus, $\left(  v,u\right)  $ is an arc of
$\Gamma^{\prime}$, and therefore also an arc of $\Gamma^{\prime}\mid_{M}$
(since $u$ and $v$ belong to $M$). This contradicts the fact that no arc of
$\Gamma^{\prime}\mid_{M}$ starts at $v$. This contradiction shows that we were
wrong to assume that $h\left(  u\right)  \geq h\left(  v\right)  $. Hence, we
must have $h\left(  v\right)  > h\left(  u\right)  $. This proves Property SW2.

The proof of Property SW3 is exactly analogous, with the only difference that
the relation $\left(  v,u\right)  \in A_{w} \cup\overline{A_{s}}$ is now
proven using $\left(  v,u\right)  \in A_{w} \subseteq A_{w} \cup
\overline{A_{s}}$.

We now have shown that our $v$ satisfies all four Properties SW1, SW2, SW3,
and SW4. In other words, $v$ is a swing voter. Hence, there exists a swing voter.

Let us now fix a swing voter $v$. Here comes a final piece of notation before
define the map $\Theta$: Namely, we denote the symmetric difference of two
sets $A$ and $B$ by $A \triangle B$ (this is the set $\left(  A\cup B\right)
\setminus\left(  A\cap B\right)  $).

Now, let $\left(  P,Q\right)  \in\mathfrak{C}$ be an arbitrary. We then define
$\Theta\left(  P,Q\right)  $ as $\left(  P\triangle\left\{  v\right\}
,Q\triangle\left\{  v\right\}  \right)  $. We must prove that this map
$\Theta$ is well-defined; in other words, we must prove that $\left(
P\triangle\left\{  v\right\}  ,Q\triangle\left\{  v\right\}  \right)  $
belongs to $\mathfrak{C}$ for every $\left(  P,Q\right)  \in\mathfrak{C}$. In
order to do so, we fix some $\left(  P,Q\right)  \in\mathfrak{C}$. By the
definition of $\mathfrak{C}$, this means that $\left(  P,Q\right)  $ is a pair
of subsets of $V$ satisfying the Properties C1, C2, C3, C4 and C5.

We will now show that the Properties C1, C2, C3, C4 and C5 with $P$ and $Q$
replaced by $P\triangle\left\{  v\right\}  $ and $Q\triangle\left\{
v\right\}  $ are also satisfied.

Let us start with Property C5. Since Property C5 itself is satisfied, we have
$P\cup Q=V$ and $P\cap Q=\varnothing$. Therefore, $v$ belongs to exactly one
of the two sets $P$ and $Q$. From this, it is easy to conclude (by checking
both possible cases) that $\left(  P\triangle\left\{  v\right\}  \right)
\cup\left(  Q\triangle\left\{  v\right\}  \right)  =V$ and $\left(
P\triangle\left\{  v\right\}  \right)  \cap\left(  Q\triangle\left\{
v\right\}  \right)  =\varnothing$. In other words, Property C5 with $P$ and
$Q$ replaced by $P\triangle\left\{  v\right\}  $ and $Q\triangle\left\{
v\right\}  $ is satisfied.

Let now $a\in V$ and $b\in P\triangle\left\{  v\right\}  $ be such that
$\left(  a,b\right)  \in A_{w}$. We are going to prove that $h\left(
a\right)  \leq h\left(  b\right)  $. If $b\in P$, then this follows from
Property C1. Hence, for the rest of the proof of $h\left(  a\right)  \leq
h\left(  b\right)  $, we can WLOG assume that we don't have $b\in P$. Assume
this. So we have $b\in P\triangle\left\{  v\right\}  \subseteq P\cup\left\{
v\right\}  $ but we don't have $b\in P$. Thus, we must have $b\in\left(
P\cup\left\{  v\right\}  \right)  \setminus P=\left\{  v\right\}  $, so that
$b=v$. Thus, $\left(  a,\underbrace{v}_{=b}\right)  =\left(  a,b\right)  \in
A_{w}$. Now, Property SW1 (applied to $u=a$) yields $h\left(  v\right)  \geq
h\left(  a\right)  $. Hence, $h\left(  a\right)  \leq h\left(  \underbrace{v}%
_{=b}\right)  =h\left(  b\right)  $. This completes the proof of $h\left(
a\right)  \leq h\left(  b\right)  $. Now, forget that we fixed $a$ and $b$. We
thus have proven that for any $a\in V$ and any $b\in P\triangle\left\{
v\right\}  $ satisfying $\left(  a,b\right)  \in A_{w}$, we have $h\left(
a\right)  \leq h\left(  b\right)  $. In other words, Property C1 with $P$ and
$Q$ replaced by $P\triangle\left\{  v\right\}  $ and $Q\triangle\left\{
v\right\}  $ is satisfied.

Similarly we can prove that Property C2 with $P$ and $Q$ replaced by
$P\triangle\left\{  v\right\}  $ and $Q\triangle\left\{  v\right\}  $ is
satisfied (but now we have to apply Property SW2 instead of Property SW1).
Similarly we can prove that Property C3 with $P$ and $Q$ replaced by
$P\triangle\left\{  v\right\}  $ and $Q\triangle\left\{  v\right\}  $ is
satisfied (but now we have to rule out the case $a\in Q$ instead of the case
$b\in P$, and to apply Property SW3 instead of Property SW1). Similarly we can
prove that Property C4 with $P$ and $Q$ replaced by $P\triangle\left\{
v\right\}  $ and $Q\triangle\left\{  v\right\}  $ is satisfied (but now we
have to rule out the case $a\in Q$ instead of the case $b\in P$, and to apply
Property SW4 instead of Property SW1).

Altogether, we now know that the Properties C1, C2, C3, C4 and C5 with $P$ and
$Q$ replaced by $P\triangle\left\{  v\right\}  $ and $Q\triangle\left\{
v\right\}  $ are also satisfied. Since $\left(  P\triangle\left\{  v\right\}
,Q\triangle\left\{  v\right\}  \right)  $ is a pair of subsets of $V$, this
yields that $\left(  P\triangle\left\{  v\right\}  ,Q\triangle\left\{
v\right\}  \right)  $ belongs to $\mathfrak{C}$ (because of the definition of
$\mathfrak{C}$). We thus have proven that the map $\Theta$ is well-defined.

It remains to prove that this map $\Theta$ satisfies the Properties Th1, Th2
and Th3. It is clear that $\Theta$ satisfies Property Th2 (in fact, if
$U\in\mathfrak{C}$ is arbitrary, then we can write $U$ in the form $U=\left(
P,Q\right)  $ for some $P$ and $Q$, and then we have $\Theta\left(  U\right)
=\Theta\left(  P,Q\right)  =\left(  P\triangle\left\{  v\right\}
,Q\triangle\left\{  v\right\}  \right)  $ (by the definition of $\Theta$), so
that%
\begin{align*}
\left\vert \operatorname*{snd}\left(  \underbrace{\Theta\left(  U\right)
}_{=\left(  P\triangle\left\{  v\right\}  ,Q\triangle\left\{  v\right\}
\right)  }\right)  \right\vert  &  =\left\vert \underbrace{\operatorname*{snd}%
\left(  P\triangle\left\{  v\right\}  ,Q\triangle\left\{  v\right\}  \right)
}_{=Q\triangle\left\{  v\right\}  }\right\vert =\left\vert Q\triangle\left\{
v\right\}  \right\vert \\
&  \equiv\left\vert Q\right\vert +\underbrace{\left\vert \left\{  v\right\}
\right\vert }_{=1}=\left\vert \underbrace{Q}_{=\operatorname*{snd}%
U}\right\vert +1=\left\vert \operatorname*{snd}U\right\vert
+1\operatorname{mod}2,
\end{align*}
so that $\left(  -1\right)  ^{\left\vert \operatorname*{snd}\left(
\Phi\left(  U\right)  \right)  \right\vert }=\left(  -1\right)  ^{\left\vert
\operatorname*{snd}U\right\vert +1}=-\left(  -1\right)  ^{\left\vert
\operatorname*{snd}U\right\vert }$), and therefore also satisfies Property Th3
(since Property Th2 yields $\left(  -1\right)  ^{\left\vert
\operatorname*{snd}\left(  \Phi\left(  U\right)  \right)  \right\vert
}=-\left(  -1\right)  ^{\left\vert \operatorname*{snd}U\right\vert }%
\neq\left(  -1\right)  ^{\left\vert \operatorname*{snd}U\right\vert }$ for
every $U\in\mathfrak{C}$). It therefore remains to prove Property Th1. In
order to do so, we fix $U\in\mathfrak{C}$. Write $U$ in the form $\left(
P,Q\right)  $. Then,%
\[
\Theta\left(  U\right)  =\Theta\left(  P,Q\right)  =\left(  P\triangle\left\{
v\right\}  ,Q\triangle\left\{  v\right\}  \right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{by the definition of }\Theta\right)  ,
\]
so that%
\begin{align*}
\Theta\left(  \Theta\left(  U\right)  \right)   &  =\Theta\left(
P\triangle\left\{  v\right\}  ,Q\triangle\left\{  v\right\}  \right) \\
&  =\left(  \underbrace{\left(  P\triangle\left\{  v\right\}  \right)
\triangle\left\{  v\right\}  }_{=P},\underbrace{\left(  Q\triangle\left\{
v\right\}  \right)  \triangle\left\{  v\right\}  }_{=Q}\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\Theta\right) \\
&  =\left(  P,Q\right)  =U.
\end{align*}
Since this holds for every $U\in\mathfrak{C}$, we thus have $\Theta\circ
\Theta=\operatorname*{id}\nolimits_{\mathfrak{C}}$. Hence, Property Th1 is proven.

We now know that the map $\Theta$ satisfies all three Properties Th1, Th2 and
Th3. Thus, as we have seen, (\ref{pf.cuts.goal3}) holds, and this completes
the proof of Proposition \ref{prop.cuts} \textbf{(a)} (as we have seen).

\textbf{(b)} Let $X^{\operatorname*{op}}$ denote the opposite poset of $X$;
this is the poset with the same ground set as $X$, but whose smaller relation
is the greater relation of $X$. Of course, $X^{\operatorname*{op}}$ is a
totally ordered set (since $X$ is a totally ordered set).

We denote by $\widetilde{\Gamma}$ the weak-strict digraph $\left(
V,A_{s},A_{w}\right)  $. (This is obtained from $\Gamma$ by interchanging the
set of weak arcs with the set of strict arcs.) It is easy to see that the
$\omega\left(  \Gamma\right)  \mid_{P}$-partitions to $X$ are the same thing
as the $\widetilde{\Gamma}$-partitions to $X^{\operatorname*{op}}$. Moreover,
the $\Gamma\mid_{Q}$-partitions to $X$ are the same as the $\omega\left(
\widetilde{\Gamma}\right)  \mid_{Q}$-partitions to $X^{\operatorname*{op}}$.
Finally, $\operatorname*{Adm}\widetilde{\Gamma}=\operatorname*{Adm}\Gamma$.
Hence, Proposition \ref{prop.cuts} \textbf{(a)} (applied to $A_{s}$, $A_{w}$,
$\widetilde{\Gamma}$ and $X^{\operatorname*{op}}$ instead of $A_{w}$, $A_{s}$,
$\Gamma$ and $X$) yields%
\[
\sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}\left(  -1\right)
^{\left\vert Q\right\vert }Z_{P,X}^{\omega}Z_{Q,X}=\left[  V=\varnothing
\right]  .
\]
But since every $\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma$ satisfies
$\left\vert Q\right\vert =\left\vert V\right\vert -\left\vert P\right\vert $
(because $P\cup Q=V$ and $P\cap Q=\varnothing$), the left hand side of this
rewrites as%
\begin{align*}
&  \sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}\underbrace{\left(
-1\right)  ^{\left\vert Q\right\vert }}_{=\left(  -1\right)  ^{\left\vert
V\right\vert -\left\vert P\right\vert }=\left(  -1\right)  ^{\left\vert
V\right\vert }\left(  -1\right)  ^{\left\vert P\right\vert }}Z_{P,X}^{\omega
}Z_{Q,X}\\
&  =\left(  -1\right)  ^{\left\vert V\right\vert }\sum_{\left(  P,Q\right)
\in\operatorname*{Adm}\Gamma}\left(  -1\right)  ^{\left\vert P\right\vert
}Z_{P,X}^{\omega}Z_{Q,X}.
\end{align*}
The rest is clear.

[... detail proof of (b)]
\end{proof}

\begin{proof}
[Proof of Theorem \ref{thm.QSym.antipode}.]Let $m:\operatorname*{QSym}%
\nolimits_{\mathbf{k}}\otimes\operatorname*{QSym}\nolimits_{\mathbf{k}%
}\rightarrow\operatorname*{QSym}\nolimits_{\mathbf{k}}$ be the multiplication
map of the $\mathbf{k}$-algebra $\operatorname*{QSym}\nolimits_{\mathbf{k}}$
(that is, the $\mathbf{k}$-linear map sending every $a\otimes b$ to $ab$). Let
$u:\mathbf{k}\rightarrow\operatorname*{QSym}\nolimits_{\mathbf{k}}$ be the
unity map of the $\mathbf{k}$-algebra $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ (that is, the $\mathbf{k}$-linear map sending $1$ to
$1_{\operatorname*{QSym}\nolimits_{\mathbf{k}}}$).

We need to prove that $S$ is an antipode of the $\mathbf{k}$-bialgebra
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$. For this, it is clearly enough
to show that
\begin{equation}
m\circ\left(  S\otimes\operatorname*{id}\nolimits_{\operatorname*{QSym}%
\nolimits_{\mathbf{k}}}\right)  \circ\Delta=u\circ\varepsilon
\label{pf.QSym.antipode.goal1}%
\end{equation}
and%
\begin{equation}
m\circ\left(  \operatorname*{id}\nolimits_{\operatorname*{QSym}%
\nolimits_{\mathbf{k}}}\otimes S\right)  \circ\Delta=u\circ\varepsilon.
\label{pf.QSym.antipode.goal2}%
\end{equation}


We first introduce a certain class of weak-strict digraphs. Namely, a
\textit{dipath} will mean a weak-strict digraph of the form
$\operatorname*{DPath}\alpha$ for a composition $\alpha$. For any dipath
$\Gamma$, the weak-strict digraph $\omega\left(  \Gamma\right)  $ also is a
dipath, and in fact we have $\omega\left(  \Gamma\right)
=\operatorname*{DPath}\left(  \omega\left(  \alpha\right)  \right)  $ for the
composition $\alpha$ satisfying $\Gamma=\operatorname*{DPath}\alpha$. Hence,
if $\Gamma=\left(  V,A_{w},A_{s}\right)  $ is a dipath, then%
\begin{equation}
S\left(  F_{\Gamma}\right)  =\left(  -1\right)  ^{\left\vert V\right\vert
}F_{\omega\left(  \Gamma\right)  } \label{pf.QSym.antipode.1}%
\end{equation}
(because the formula $S\left(  L_{\alpha}\right)  =\left(  -1\right)
^{\left\vert \alpha\right\vert }L_{\omega\left(  \alpha\right)  }$, applied to
the composition $\alpha$ satisfying $\Gamma=\operatorname*{DPath}\alpha$,
rewrites as $S\left(  F_{\Gamma}\right)  =\left(  -1\right)  ^{\left\vert
V\right\vert }F_{\omega\left(  \Gamma\right)  }$ once we recall Proposition
\ref{prop.FGamma.L}).

Let us now prove (\ref{pf.QSym.antipode.goal1}). Indeed, let $\alpha$ be any
composition. Let $\Gamma$ be the weak-strict digraph $\operatorname*{DPath}%
\alpha$. Proposition \ref{prop.FGamma.L} yields $F_{\operatorname*{DPath}%
\alpha}=L_{\alpha}$, so that $L_{\alpha}=F_{\operatorname*{DPath}\alpha
}=F_{\Gamma}=F_{\left(  \Gamma,\mathbf{1}\right)  }$ and thus%
\begin{align*}
\Delta\left(  L_{\alpha}\right)   &  =\Delta\left(  F_{\left(  \Gamma
,\mathbf{1}\right)  }\right)  =\sum_{\left(  P,Q\right)  \in
\operatorname*{Adm}\Gamma}\underbrace{F_{\left(  \Gamma\mid_{P},\mathbf{1}%
\mid_{P}\right)  }}_{=F_{\Gamma\mid_{P}}}\otimes\underbrace{F_{\left(
\Gamma\mid_{Q},\mathbf{1}\mid_{Q}\right)  }}_{=F_{\Gamma\mid_{Q}}%
}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition \ref{prop.FGammaw.De}
\textbf{(a)}}\right) \\
&  =\sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}F_{\Gamma\mid_{P}%
}\otimes F_{\Gamma\mid_{Q}}.
\end{align*}
Hence,%
\begin{align*}
&  \left(  m\circ\left(  S\otimes\operatorname*{id}%
\nolimits_{\operatorname*{QSym}\nolimits_{\mathbf{k}}}\right)  \circ
\Delta\right)  \left(  L_{\alpha}\right) \\
&  =\left(  m\circ\left(  S\otimes\operatorname*{id}%
\nolimits_{\operatorname*{QSym}\nolimits_{\mathbf{k}}}\right)  \right)
\left(  \underbrace{\Delta\left(  L_{\alpha}\right)  }_{=\sum_{\left(
P,Q\right)  \in\operatorname*{Adm}\Gamma}F_{\Gamma\mid_{P}}\otimes
F_{\Gamma\mid_{Q}}}\right) \\
&  =\left(  m\circ\left(  S\otimes\operatorname*{id}%
\nolimits_{\operatorname*{QSym}\nolimits_{\mathbf{k}}}\right)  \right)
\left(  \sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}F_{\Gamma
\mid_{P}}\otimes F_{\Gamma\mid_{Q}}\right) \\
&  =\sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}%
\underbrace{S\left(  F_{\Gamma\mid_{P}}\right)  }_{\substack{=\left(
-1\right)  ^{\left\vert P\right\vert }F_{\omega\left(  \Gamma\mid_{P}\right)
}\\\text{(by (\ref{pf.QSym.antipode.1}) (applied to}\\\Gamma\mid_{P}\text{
instead of }\Gamma\text{) (since }\Gamma\mid_{P}\text{ is a dipath}%
\\\text{(since }\Gamma\text{ is a dipath and }\left(  P,Q\right)
\in\operatorname*{Adm}\Gamma\text{)))}}}\cdot F_{\Gamma\mid_{Q}}\\
&  =\sum_{\left(  P,Q\right)  \in\operatorname*{Adm}\Gamma}\left(  -1\right)
^{\left\vert P\right\vert }F_{\omega\left(  \Gamma\mid_{P}\right)  }%
F_{\Gamma\mid_{Q}}.
\end{align*}


But $\Gamma^{\prime}$ is acyclic (since $\Gamma$ is a dipath). Let $X$ be the
totally ordered set $\mathbb{N}_{+}$ (with the usual ordering). For every
$v\in V$ and

[...]

XXX

[... detail this pf]
\end{proof}

[...]

\begin{proof}
[First proof of Theorem \ref{thm.FGammaw} (sketched).][...]

[...]
\end{proof}

\begin{proof}
[Second proof of Theorem \ref{thm.FGammaw} (sketched).]Let us define one more
notion: Let a \textit{weak-strict-undirected digraph} be defined as a
quadruple $\left(  V,A_{s},A_{w},E\right)  $ such that $\left(  V,A_{s}%
,A_{w}\right)  $ is a weak-strict digraph and $\left(  V,E\right)  $ is a
simple undirected graph. If $\Gamma$ is a weak-strict-undirected digraph,
define two new weak-strict-undirected digraphs $\Gamma^{\prime}=\left(
V,A_{w},\overline{A_{s}},E\right)  $ and $\omega\left(  \Gamma\right)
=\left(  V,\overline{A_{s}},\overline{A_{w}},E\right)  $ (these definitions
imitate the analogous definitions for weak-strict digraphs, and leave $E$ unchanged).

We assume that $\mathbf{k}=\mathbb{Z}$ to match the setting of \cite{Mal-Reu}
(we don't lose anything from this assumption, because of Proposition
\ref{prop.QSym.basechange}). Thus, $\operatorname*{QSym}\nolimits_{\mathbf{k}%
}=\operatorname*{QSym}$.

We define the conjugation map $\omega:\operatorname*{QSym}\rightarrow
\operatorname*{QSym}$ as in \cite[\S 3]{Mal-Reu}. It is well-known that%
\begin{equation}
S\left(  f\right)  =\left(  -1\right)  ^{d}\omega\left(  f\right)
\label{def.QSym.Somega}%
\end{equation}
for every homogeneous $f\in\operatorname*{QSym}$ having degree $d$.

We can WLOG assume that the directed graph $\Gamma$ is acyclic\footnote{In
fact, assume that it is not. Thus, there exists a cycle consisting of weak
arcs and strict arcs in $\Gamma$. This cycle cannot consist of weak arcs alone
(because $\Gamma^{\prime}$ is acyclic), so its existence forces an
unsatisfiable chain of inequalities upon any $\Gamma$-partition. Hence, there
exist no $\Gamma$-partitions; thus, $F_{\left(  \Gamma,w\right)  }=0$. Also,
the cycle that we have just found cannot consist of strict arcs alone (because
$\Gamma^{\prime}$ is acyclic again), so its reversal is a cycle consisting of
weak arcs and strict arcs in $\omega\left(  \Gamma\right)  $ which cannot
consist of weak arcs alone. This latter cycle forces an unsatisfiable chain of
inequalities upon any $\omega\left(  \Gamma\right)  $-partition; thus,
$F_{\left(  \omega\left(  \Gamma\right)  ,w\right)  }=0$. Hence, Theorem
\ref{thm.FGammaw} boils down to $0=\left(  -1\right)  ^{\left\vert
V\right\vert }0$ in this case, which is obvious.}. Assume this. Notice also
that $A_{w}\cap A_{s}=\varnothing$ (since $\Gamma^{\prime}$ is acyclic).

Define the set $\widetilde{V}$ as $\left\{  \left(  p,i\right)  \ \mid\ p\in
V,\ 1\leq i\leq w\left(  p\right)  \right\}  $. Roughly speaking, this set
$\widetilde{V}$ is obtained from $V$ by breaking up each element $p\in V$ into
$w\left(  p\right)  $ distinct elements. Embed $V$ into $V$ by sending every
$p\in V$ to $\left(  p,1\right)  \in\widetilde{V}$. Then, $A_{w}$ and $A_{s}$
are subsets of $\widetilde{V}\times\widetilde{V}$. Therefore, $\left(
\widetilde{V},A_{w},A_{s}\right)  $ becomes a weak-strict digraph. Denote this
weak-strict digraph by $\widetilde{\Gamma}$. Now, define a set $E\subseteq
\dbinom{\widetilde{V}}{2}$ by%
\[
E=\left\{  \left\{  \left(  p,i\right)  ,\left(  p,i+1\right)  \right\}
\ \mid\ p\in V,\ 1\leq i\leq w\left(  p\right)  -1\right\}  .
\]
Then, $\left(  \widetilde{V},A_{w},A_{s},E\right)  $ is a
weak-strict-undirected digraph. It is easily seen that both $\left(
\widetilde{V},A_{w},A_{s},E\right)  $ and $\left(  \widetilde{V},A_{w}%
,A_{s},E\right)  ^{\prime}$ are acyclic. We can therefore apply \cite[Theorem
3.1]{Mal-Reu} to the set of equalities and inequalities induced by $\left(
\widetilde{V},A_{w},A_{s},E\right)  $ (that is, $x_{u}\leq x_{v}$ for each
$\left(  u,v\right)  \in A_{w}$, as well as $x_{u}<x_{v}$ for each $\left(
u,v\right)  \in A_{s}$, as well as $x_{u}=x_{v}$ for each $\left\{
u,v\right\}  \in E$). The result is basically $\omega\left(  F_{\left(
\Gamma,w\right)  }\right)  =\left(  -1\right)  ^{\left\vert E\right\vert
}F_{\left(  \omega\left(  \Gamma\right)  ,w\right)  }$. Now, $S\left(
F_{\left(  \Gamma,w\right)  }\right)  =\left(  -1\right)  ^{\left\vert
V\right\vert }F_{\left(  \omega\left(  \Gamma\right)  ,w\right)  }$ follows
from this by applying (\ref{def.QSym.Somega}) and by noticing that $\left\vert
E\right\vert =\sum\limits_{p\in V}w\left(  p\right)  -\left\vert V\right\vert
$. Theorem \ref{thm.FGammaw} is proven.
\end{proof}

\begin{proof}
[Third proof of Theorem \ref{thm.FGammaw} (sketched).]We will prove Theorem
\ref{thm.FGammaw} by a series of reductions to simpler cases.

First, we notice that $A_{w}\cap A_{s}=\varnothing$ (since $\Gamma^{\prime}$
is acyclic).

For any arc $a$, let $\overline{a}$ denote the reverse of the arc $a$.

Second, if $a\in A_{w}$ is any arc, then Theorem \ref{thm.FGammaw} for the
weak-strict digraph $\Gamma=\left(  V,A_{w},A_{s}\right)  $ follows if we can
prove Theorem \ref{thm.FGammaw} for the weak-strict digraph $\left(
V,A_{w}\setminus\left\{  a\right\}  ,A_{s}\right)  $ and Theorem
\ref{thm.FGammaw} for the weak-strict digraph $\left(  V,A_{w}\setminus
\left\{  a\right\}  ,A_{s}\cup\left\{  \overline{a}\right\}  \right)  $. In
fact, the $\Gamma$-partitions are precisely the $\left(  V,A_{w}%
\setminus\left\{  a\right\}  ,A_{s}\right)  $-partitions which are not
$\left(  V,A_{w}\setminus\left\{  a\right\}  ,A_{s}\cup\left\{  \overline
{a}\right\}  \right)  $-partitions (just look at the definitions); hence,%
\[
F_{\left(  \Gamma,w\right)  }=F_{\left(  \left(  V,A_{w}\setminus\left\{
a\right\}  ,A_{s}\right)  ,w\right)  }-F_{\left(  \left(  V,A_{w}%
\setminus\left\{  a\right\}  ,A_{s}\cup\left\{  \overline{a}\right\}  \right)
,w\right)  },
\]
and similarly%
\[
F_{\left(  \omega\left(  \Gamma\right)  ,w\right)  }=F_{\left(  \omega\left(
V,A_{w}\setminus\left\{  a\right\}  ,A_{s}\right)  ,w\right)  }-F_{\left(
\omega\left(  V,A_{w}\setminus\left\{  a\right\}  ,A_{s}\cup\left\{
\overline{a}\right\}  \right)  ,w\right)  }.
\]
Moreover, both $\left(  V,A_{w}\setminus\left\{  a\right\}  ,A_{s}\right)
^{\prime}$ and $\left(  V,A_{w}\setminus\left\{  a\right\}  ,A_{s}\cup\left\{
\overline{a}\right\}  \right)  ^{\prime}$ are acyclic (since $\Gamma^{\prime}$
is acyclic), so that Theorem \ref{thm.FGammaw} applies to them. Thus, Theorem
\ref{thm.FGammaw} for the weak-strict digraph $\Gamma=\left(  V,A_{w}%
,A_{s}\right)  $ follows if we can prove Theorem \ref{thm.FGammaw} for the
weak-strict digraph $\left(  V,A_{w}\setminus\left\{  a\right\}
,A_{s}\right)  $ and Theorem \ref{thm.FGammaw} for the weak-strict digraph
$\left(  V,A_{w}\setminus\left\{  a\right\}  ,A_{s}\cup\left\{  \overline
{a}\right\}  \right)  $. Hence, we have reduced Theorem \ref{thm.FGammaw} for
the weak-strict digraph $\Gamma=\left(  V,A_{w},A_{s}\right)  $ to two cases
of Theorem \ref{thm.FGammaw} for weak-strict digraphs with a smaller number of
weak arcs than $\Gamma$ (but with the same number of vertices). Hence, by
induction over $\left\vert A_{w}\right\vert $, we can reduce the general case
to the case when $A_{w}=\varnothing$.

We thus WLOG assume that $A_{w}=\varnothing$. Hence, the weak-strict digraph
$\Gamma$ is acyclic (since $\Gamma^{\prime}$ is acyclic).

We now want to get rid of $w$ (or, more precisely, assume WLOG that
$w=\mathbf{1}$). In fact, assume that $w\neq\mathbf{1}$. Then, there exists
some $p\in V$ such that $w\left(  p\right)  \neq1$. Consider this $p$.
Clearly, $w\left(  p\right)  >1$. Now, let $p_{1}$ be a new vertex not in $V$,
and set $V_{1}$ be the set $V\cup\left\{  p_{1}\right\}  $. Let $w_{1}%
:V_{1}\rightarrow\mathbb{N}_{+}$ be the map which sends every $q\in
V\setminus\left\{  p\right\}  $ to $w\left(  q\right)  $, sends $p$ to
$w\left(  p\right)  -1$ and sends $p_{1}$ to $1$. Let $\Gamma_{1}$ be the
weak-strict digraph $\left(  V_{1},\varnothing,A_{s}\right)  $; let
$\Gamma_{\rightarrow1}$ be the weak-strict digraph $\left(  V_{1}%
,\varnothing,A_{s}\cup\left\{  \left(  p,p_{1}\right)  \right\}  \right)  $;
let $\Gamma_{\leftarrow1}$ be the weak-strict digraph $\left(  V_{1}%
,\varnothing,A_{s}\cup\left\{  \left(  p_{1},p\right)  \right\}  \right)  $.
It is easy to see that all three weak-strict digraphs $\Gamma_{1}^{\prime}$,
$\Gamma_{\rightarrow1}^{\prime}$ and $\Gamma_{\leftarrow1}^{\prime}$ are
acyclic, but we have%
\[
F_{\left(  \Gamma,w\right)  }=F_{\left(  \Gamma_{1},w_{1}\right)  }-F_{\left(
\Gamma_{\rightarrow1},w_{1}\right)  }-F_{\left(  \Gamma_{\leftarrow1}%
,w_{1}\right)  }%
\]
and similarly%
\[
F_{\left(  \omega\left(  \Gamma\right)  ,w\right)  }=F_{\left(  \omega\left(
\Gamma_{\rightarrow1}\right)  ,w_{1}\right)  }-F_{\left(  \omega\left(
\Gamma_{\leftarrow1}\right)  ,w_{1}\right)  }-F_{\left(  \omega\left(
\Gamma_{1}\right)  ,w_{1}\right)  }%
\]
(because the map $\omega$ turns strict arcs into weak arcs!). Thus, Theorem
\ref{thm.FGammaw} for the weak-strict digraph $\Gamma$ follows from Theorem
\ref{thm.FGammaw} for the weak-strict digraphs $\Gamma_{1}$, $\Gamma
_{\rightarrow1}$ and $\Gamma_{\leftarrow1}$ (keep in mind that $\left\vert
V_{1}\right\vert =\left\vert V\right\vert +1$, whence the signs switch). While
these weak-strict digraphs $\Gamma_{1}$, $\Gamma_{\rightarrow1}$ and
$\Gamma_{\leftarrow1}$ have more vertices than $\Gamma$, they have the same
number $\sum\limits_{p\in V}w\left(  p\right)  $, and thus we can use this as
a recursive proof to transform our problem until $w$ becomes $\mathbf{1}$ (and
of course the fact that $A_{w}=\varnothing$ does not break in the process). So
we can WLOG assume that $w=\mathbf{1}$. Assume this.

The directed graph $\Gamma$ is acyclic, and hence there exists a poset
structure on $V$ such that $a>b$ for every $\left(  a,b\right)  \in A_{s}$.
Consider this poset structure. Give this poset a natural labelling, i.e., a
labelling of the vertices of $\Gamma$ by the integers $1$, $2$, $\ldots$,
$\left\vert V\right\vert $ such that $a>b$ as integers whenever $a>b$ in $V$.
Hence, $V$ is a labelled poset. It is easy to see that $F_{\left(
\Gamma,w\right)  }=F_{V}\left(  \mathbf{x}\right)  $ and $F_{\left(
\omega\left(  \Gamma\right)  ,w\right)  }=F_{V^{\operatorname*{opp}}}\left(
\mathbf{x}\right)  $ using the notations of \cite[Section 5]{Reiner}. Thus,
the equality that needs to be proven, $S\left(  F_{\left(  \Gamma,w\right)
}\right)  =\left(  -1\right)  ^{\left\vert V\right\vert }F_{\left(
\omega\left(  \Gamma\right)  ,w\right)  }$, rewrites as $S\left(  F_{V}\left(
\mathbf{x}\right)  \right)  =\left(  -1\right)  ^{\left\vert V\right\vert
}F_{V^{\operatorname*{opp}}}\left(  \mathbf{x}\right)  $. This follows from
\cite[Corollary 5.27]{Reiner}. Theorem \ref{thm.FGammaw} is thus proven.
\end{proof}

[...]

\begin{obsolete}
\section{The chain lemma}
\label{sect.chain}
[...]
\section{Dendriform operations on $\operatorname*{QSym}\nolimits_{\mathbf{k}}%
$}
\label{sect.dendriform}
[...]
\section{Dual immaculate functions and Zabrocki's conjecture}
\label{sect.zabrocki}
[...]
\end{obsolete}


\section{\label{sect.ppart}$P$-partitions and special cases}

Let us now relate the notion of $\Gamma$-partitions, which we so far have been
studying, with the far more classical notion of $P$-partitions. This allows
applying our results to reprove existing results in literature, but also
conversely deriving our results from known results.

The theory of $P$-partitions (or, to be more precise, $\left(  P,\omega
\right)  $-partitions, of which $P$-partitions are but a particular case) goes
back to Richard Stanley's thesis \cite{Stanley-Thes}, where it was introduced
as a common generalization for the enumerations of multiple combinatorial
objects (such as usual partitions, plane partitions and various others); this
allowed Stanley to derive several results of enumerative combinatorics from a
rather manageable collection of (fairly uncomplicated) theorems. We will skip
the (too restrictive) notion of $P$-partitions for a poset $P$, and introduce
$\left(  P,\omega\right)  $-partitions right away:

\begin{definition}
\label{def.Ppart}Let $P$ be a finite poset. Let $X$ be a poset. Let
$\omega:P\rightarrow\left\{  1,2,\ldots,\left\vert P\right\vert \right\}  $ be
a bijection. We will use the symbols $\leq$ and $<$ for the smaller relation
and the smaller-or-equal relation, respectively, of a poset. (Which poset we
mean will be clear from the types of the objects on both sides of these
symbols.) A $\left(  P,\omega\right)  $\textit{-partition to }$X$ will mean a
function $f:P\rightarrow X$ such that:

\textbf{(a)} every two elements $u$ and $v$ of $P$ satisfying $u<v$ and
$\omega\left(  u\right)  <\omega\left(  v\right)  $ satisfy $f\left(
u\right)  \leq f\left(  v\right)  $;

\textbf{(b)} every two elements $u$ and $v$ of $P$ satisfying $u<v$ and
$\omega\left(  u\right)  >\omega\left(  v\right)  $ satisfy $f\left(
u\right)  <f\left(  v\right)  $.

As before, we regard $\mathbb{N}_{+}$ as a poset using the standard smaller
relation on $\mathbb{N}_{+}$ (so this poset is actually a totally ordered
set). When we don't explicitly mention $X$ and just speak of "$\left(
P,\omega\right)  $-partitions", we always mean $\left(  P,\omega\right)
$-partitions to this poset $\mathbb{N}_{+}$.
\end{definition}

\begin{remark}
Conflicting definitions of the notion of a \textquotedblleft$\left(
P,\omega\right)  $-partition\textquotedblright\ exist in literature. We follow
the notation of Reiner \cite[\S 5.2]{Reiner} (except that Reiner subsumes both
the poset $P$ and the bijection $\omega$ into one object $P$, which he calls a
\textquotedblleft labelled poset\textquotedblright), while Stanley (in
\cite[\S 3.15]{Stanley-EC1} and in \cite[Definition 2.2]{Stanley-Thes}) has a
definition which differs from ours in requiring $f\left(  u\right)  \geq
f\left(  v\right)  $ (instead of $f\left(  u\right)  \geq f\left(  v\right)
$) in \textbf{(a)}, requiring $f\left(  u\right)  >f\left(  v\right)  $
(instead of $f\left(  u\right)  <f\left(  v\right)  $) in \textbf{(b)}, and
assuming that $X=\mathbb{N}$ (not $\mathbb{N}_{+}$). Our notion of
\textquotedblleft$\left(  P,\omega\right)  $-partition\textquotedblright\ is
what Stanley calls a \textquotedblleft reverse $\left(  P,\omega\right)
$-partition\textquotedblright\ in \cite[\S 7.19]{Stanley-EC2}. Our definition
of a $\left(  P,\omega\right)  $-partition is essentially equivalent to that
given by Gessel in \cite[\S 2]{Gessel-multipar} and that given by Malvenuto in
\cite[\S 4.2]{Malve-Thesis} (except that both Gessel and Malvenuto require $X$
to be infinite, and equate $u$ with $\omega\left(  u\right)  $). The
definition given in \cite[Definition 3.3.13]{LMvW} differs from ours only in
having $\omega$ map $P$ injectively into a totally ordered set rather than
bijectively into $\left\{  1,2,\ldots,\left\vert P\right\vert \right\}  $.
\end{remark}

It should be fairly obvious that $\left(  P,\omega\right)  $-partitions are a
particular case of $\Gamma$-partitions.

[... proposition, proof]

Conversely, however, $\Gamma$-partitions are a particular case of $\left(
P,\omega\right)  $-partitions for those weak-strict digraphs $\Gamma$ for
which $\Gamma^{\prime}$ is acyclic.

[... proposition, proof]

The connection between $\left(  P,\omega\right)  $-partitions and
quasisymmetric functions uses a generating function $F_{P,\omega}$ similar to
our generating function $F_{\Gamma}$ defined in Definition \ref{def.FGamma}
(and, in fact, being a particular case thereof):

[... Definition]

[... Why particular case]

\begin{remark}
The quasisymmetric function $F_{P,\omega}$ for a finite poset $P$ and a
bijection $\omega:P\rightarrow\left\{  1,2,\ldots,\left\vert P\right\vert
\right\}  $ has been first introduced by Stanley in \cite[\S 21]%
{Stanley-Thes}, however under a different name (he called it $\left\{
P,\omega\right\}  $, or more precisely, he called $\left\{  P,\omega\right\}
$ the quasisymmetric function that would be $F_{P,\omega}$ if we had defined
the notion of $\left(  P,\omega\right)  $-partition as he defined it); it has
later been denoted by $K_{P,\omega}$ in \cite[\S 7.19]{Stanley-EC2}. The
reader should be warned that it is \textbf{not} related to the function called
$F_{P,\omega}$ in Stanley's \cite[\S 3.15]{Stanley-EC1} (or the function
called $F\left(  P,\omega\right)  $ in \cite{Stanley-Thes}). The
quasisymmetric function $F_{P,\omega}$ is denoted $F_{P}$ in \cite[\S 5.2]%
{Reiner} (where the poset $P$ and the bijection $\omega$ are subsumed into one
object $P$), denoted by $F\left(  P,\omega\right)  $ in \cite[Definition
3.3.18]{LMvW}, and denoted by $\Gamma\left(  P\right)  $ in \cite[\S 2]%
{Gessel-multipar} and in \cite[\S 4.2]{Malve-Thesis} (the map $\omega$ is
assumed to be $\operatorname*{id}$ in both of these references).
\end{remark}

Historically, the concept of $F_{P,\omega}$ has been anticipated in the work
of Gl\^{a}nffrwd Thomas (\cite{Thomas-Bax}, \cite{Thomas-Further}), who
defined a particular case (in which $P$ is a subset of the lattice
$\mathbb{Z}\times\mathbb{Z}$, and $\omega$ is a \textquotedblleft
column-strict labelling\textquotedblright, so that $F_{P,\omega}$ becomes a
generalization of Schur functions) using the formalism of Baxter operators.

In view of Proposition [... ref], we might wonder what we have gain from
generalizing $\left(  P,\omega\right)  $-partitions to $\Gamma$-partitions,
given that the main results (Theorem \ref{thm.FGammaw} and Corollary
\ref{cor.FGamma}) include the very condition that forces $\Gamma$-partitions
to be just $\left(  P,\omega\right)  $-partitions (the acyclicity of
$\Gamma^{\prime}$), and therefore follow from known theorems about the latter
[... formulate!]. It is our opinion, however, that the notion of a $\Gamma
$-partition is more natural and more malleable than that of a $\left(
P,\omega\right)  $-partition. In particular, in weak-strict digraphs, the
symmetry between the notion of weak arcs and that of strict arcs is more
obvious, and it is easier to add or remove an arc from a weak-strict digraph
than to add or remove relations to a poset. Also, it is somewhat simpler to
present $L_{\alpha}$ as a particular case of $F_{\Gamma}$ (see Proposition
\ref{prop.FGamma.L}) than to present it as a particular case of $F_{\left(
P,\omega\right)  }$; here is how the latter works:

[...]

\begin{definition}
Let $n\in\mathbb{N}$. We denote by $S_{n}$ the symmetric group on the set
$\left\{  1,2,\ldots,n\right\}  $. Let $\sigma\in S_{n}$. Then, an
element\textit{ }$i\in\left\{  1,2,\ldots,n-1\right\}  $ is said to be a
\textit{descent} of $\sigma$ if $\sigma\left(  i\right)  >\sigma\left(
i+1\right)  $. The set of all descents of $\sigma$ is called the
\textit{descent set} of $\sigma$, and denoted by $\operatorname*{Des}\sigma$.
The composition $\operatorname*{comp}\nolimits_{n}\left(  \operatorname*{Des}%
\sigma\right)  $ is called the \textit{descent composition} of $\sigma$. For
instance, if $\sigma$ is the permutation in $S_{6}$ written as $\left(
3,1,4,2,6,5\right)  $ in one-line notation, then the descent set of $\sigma$
is $\left\{  1,3,5\right\}  $, and the descent composition of $\sigma$ is
$\left(  1,2,2,1\right)  $.
\end{definition}

[...]

\section{\label{sect.Gaction}$\Gamma$-partitions up to group action}

We are now ready to introduce a group action into the picture:

\begin{corollary}
\label{cor.FGammawG}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a
weak-strict digraph. Let $w:V\rightarrow\mathbb{N}_{+}$ be any map. Assume
that $\Gamma^{\prime}$ is acyclic.

An \textit{automorphism} of a weak-strict digraph means an automorphism of its
vertex set which preserves both the set of weak arcs and the set of strict arcs.

Given a group $G$, we say that the group $G$ \textit{acts on }$\Gamma$\textit{
by automorphisms} if we are given an action of $G$ on the vertex set $V$ of
$\Gamma$ such that the action of each $g\in G$ is an automorphism of $\Gamma$.

Let $G$ be a finite group which acts on $\Gamma$ by automorphisms and which
preserves $w$ (that is, $w\left(  gp\right)  =w\left(  p\right)  $ for every
$g\in G$ and $p\in V$).

Let $\operatorname*{Par}\Gamma$ denote the set of all $\Gamma$-partitions.
Clearly, $G$ acts on this set $\operatorname*{Par}\Gamma$ too.

\textbf{(a)} We have $\prod\limits_{p\in V}x_{f\left(  p\right)  }^{w\left(
p\right)  }=\prod\limits_{p\in V}x_{\left(  gf\right)  \left(  p\right)
}^{w\left(  p\right)  }$ for every $f\in\operatorname*{Par}\Gamma$ and every
$g\in G$. Hence, we can define a formal power series $F_{\left(
\Gamma,w\right)  ,G}\in\mathbb{Z}\left[  \left[  x_{1},x_{2},x_{3}%
,\ldots\right]  \right]  $ by%
\[
F_{\left(  \Gamma,w\right)  ,G}=\sum_{f\in S}\prod\limits_{p\in V}x_{f\left(
p\right)  }^{w\left(  p\right)  }%
\]
by picking a system of representatives $S$ of the orbits $\left(
\operatorname*{Par}\Gamma\right)  \diagup G$, and this series will not depend
on the choice of $S$. This series satisfies $F_{\left(  \Gamma,w\right)
,G}\in\operatorname*{QSym}$.

\textbf{(b)} Let $\rho:G\rightarrow S_{V}$ denote the action of $G$ on the
vertex-set $V$ of $\Gamma$, written as a group homomorphism from $G$ into the
symmetric group $S_{V}$. A $\Gamma$-partition $f\in\operatorname*{Par}\Gamma$
is said to be \textit{even} if every $g\in G$ satisfying $gf=f$ must satisfy
$\operatorname*{sgn}\left(  \rho\left(  g\right)  \right)  =1$. Let $\left(
\operatorname*{Par}\Gamma\right)  ^{+}$ denote the set of all even $\Gamma
$-partitions. Then, the action of $G$ on $\operatorname*{Par}\Gamma$ restricts
to an action on $\left(  \operatorname*{Par}\Gamma\right)  ^{+}$. Hence, we
can define a formal power series $F_{\left(  \Gamma,w\right)  ,G}^{+}%
\in\mathbb{Z}\left[  \left[  x_{1},x_{2},x_{3},\ldots\right]  \right]  $ by%
\[
F_{\left(  \Gamma,w\right)  ,G}^{+}=\sum_{f\in T}\prod\limits_{p\in V
}x_{f\left(  p\right)  }^{w\left(  p\right)  }%
\]
by picking a system of representatives $T$ of the orbits $\left(
\operatorname*{Par}\Gamma\right)  ^{+}\diagup G$, and this series will not
depend on the choice of $T$. This series satisfies $F_{\left(  \Gamma
,w\right)  ,G}^{+}\in\operatorname*{QSym}$.

\textbf{(c)} We have
\[
S\left(  F_{\left(  \Gamma,w\right)  ,G}\right)  =\left(  -1\right)
^{\left\vert V\right\vert }F_{\left(  \omega\left(  \Gamma\right)  ,w\right)
,G}^{+}.
\]

\end{corollary}

\textit{Proof sketch.} For every $g\in G$, define a weak-strict digraph
$\Gamma^{g}$ as follows: Let $V^{g}$ be the set $V$ modulo the equivalence
relation $\left(  p\sim gp\text{ for every }g\in G\text{ and }p\in V\right)
$. This set $V^{g}$ will be the vertex set of $\Gamma^{g}$. The set of all
weak arcs of $\Gamma^{g}$ will be $\left\{  \left(  \left[  u\right]
_{g},\left[  v\right]  _{g}\right)  \ \mid\ \left(  u,v\right)  \in
A_{w}\right\}  $ (where $\left[  p\right]  _{g}$ denotes the projection of
$p\in V$ onto $V^{g}$). The set of all strict arcs of $\Gamma^{g}$ will be
$\left\{  \left(  \left[  u\right]  _{g},\left[  v\right]  _{g}\right)
\ \mid\ \left(  u,v\right)  \in A_{s}\right\}  $. The resulting weak-strict
digraph $\Gamma^{G}$ is easily seen to satisfy the property that $\left(
\Gamma^{g}\right)  ^{\prime}$ is acyclic. (This is mostly due to the fact that
$G$ acts on $\Gamma$ by automorphisms, thus $G$ acts on $\Gamma^{\prime}$ by
automorphisms, and consequently each orbit of $g$ on $V^{\prime}$ is an
independent set of $\Gamma^{\prime}$ (since $\Gamma^{\prime}$ is acyclic).)

Furthermore, for every $g\in G$, define a map $w^{g}:V^{g}\rightarrow
\mathbb{N}_{+}$ by $w^{g}\left(  \left[  p\right]  _{g}\right)  =\left\vert
\left[  p\right]  _{g}\right\vert \cdot w\left(  g\right)  $.

By the usual trick that goes into the proof of Burnside's lemma,%
\begin{align*}
\sum_{f\in S}\prod\limits_{p\in V}x_{f\left(  p\right)  }^{w\left(  p\right)
}  &  =\sum\limits_{f\text{ is a }\Gamma\text{-partition}}\dfrac{1}{\left\vert
Gf\right\vert }\prod\limits_{p\in V}x_{f\left(  p\right)  }^{w\left(
p\right)  }=\sum\limits_{f\text{ is a }\Gamma\text{-partition}}\dfrac
{\left\vert \operatorname*{Stab}\nolimits_{G}f\right\vert }{\left\vert
G\right\vert }\prod\limits_{p\in V}x_{f\left(  p\right)  }^{w\left(  p\right)
}\\
&  =\dfrac{1}{\left\vert G\right\vert }\sum\limits_{g\in G}\underbrace{\sum
\limits_{\substack{f\text{ is a }\Gamma\text{-partition;}\\gf=f}%
}\prod\limits_{p\in V}x_{f\left(  p\right)  }^{w\left(  p\right)  }}%
_{=\sum\limits_{f\text{ is a }\Gamma^{g}\text{-partition}}\prod\limits_{p\in
V^{g}}x_{f\left(  p\right)  }^{w^{g}\left(  p\right)  }=F_{\left(  \Gamma
^{g},w^{g}\right)  }}=\dfrac{1}{\left\vert G\right\vert }\sum\limits_{g\in
G}F_{\left(  \Gamma^{g},w^{g}\right)  }.
\end{align*}
This proves \textbf{(a)}. Similarly, one can show \textbf{(b)}, and finally
these formulas reduce \textbf{(c)} to Theorem \ref{thm.FGammaw} \textbf{(b)}
(because $\omega\left(  \Gamma^{g}\right)  =\left(  \omega\left(
\Gamma\right)  \right)  ^{g}$ for every $g\in G$).

\section{An enumerative corollary}

\label{sect.enumerative}

Let us now reap some enumerative harvest:

\begin{corollary}
\label{cor.FGammawG.enum}Let $\Gamma=\left(  V,A_{w},A_{s}\right)  $ be a
weak-strict digraph. Assume that $\Gamma^{\prime}$ is acyclic.

An \textit{automorphism} of a weak-strict digraph means an automorphism of its
vertex set which preserves both the set of weak arcs and the set of strict arcs.

Let $G$ be a finite group which acts on $\Gamma$ by automorphisms.

For every $n\in\mathbb{N}$, let $\operatorname*{Par}\nolimits_{n}\Gamma$
denote the set of all $\Gamma$-partitions to $\left\{  1,2,\ldots,n\right\}
$. Clearly, $G$ acts on this set $\operatorname*{Par}\nolimits_{n}\Gamma$ too.

\textbf{(a)} Let $W_{\Gamma,G}\left(  n\right)  =\left\vert \left(
\operatorname*{Par}\nolimits_{n}\Gamma\right)  \diagup G\right\vert $. Then,
$W_{\Gamma,G}\left(  n\right)  $ agrees with a polynomial of degree
$\left\vert V\right\vert $ in $n$ for $n\geq0$.

\textbf{(b)} Let $\rho:G\rightarrow S_{V}$ denote the action of $G$ on the
vertex-set $V$ of $\Gamma$, written as a group homomorphism from $G$ into the
symmetric group $S_{V}$. A $\Gamma$-partition $f\in\operatorname*{Par}%
\nolimits_{n}\Gamma$ is said to be \textit{even} if every $g\in G$ satisfying
$gf=f$ must satisfy $\operatorname*{sgn}\left(  \rho\left(  g\right)  \right)
=1$. Let $\left(  \operatorname*{Par}\nolimits_{n}\Gamma\right)  ^{+}$ denote
the set of all even $\Gamma$-partitions to $\left\{  1,2,\ldots,n\right\}  $.
Let $W_{\Gamma,G}^{+}\left(  n\right)  =\left\vert \left(  \operatorname*{Par}%
\nolimits_{n}\Gamma\right)  ^{+}\diagup G\right\vert $. Then, $W_{\Gamma
,G}^{+}\left(  n\right)  $ agrees with a polynomial of degree $\left\vert
V\right\vert $ in $n$ for $n\geq0$.

\textbf{(c)} We have%
\[
W_{\Gamma,G}\left(  -n\right)  =\left(  -1\right)  ^{\left\vert V\right\vert
}W_{\omega\left(  \Gamma\right)  ,G}^{+}\left(  n\right)  .
\]

\end{corollary}

Notice that this yields \cite[Theorem 2.8]{Joch} when $\Gamma$ is set to
$\left(  P,\operatorname*{cov}P,\varnothing\right)  $ with
$\operatorname*{cov}P$ being the set of all covering relations of $P$. This
also yields the twin of \cite[Theorem 2.8]{Joch} when $\Gamma$ is set to
$\left(  P,\varnothing,\operatorname*{cov}P\right)  $.

\begin{definition}
We use standard Hopf-algebraic notations for the Hopf algebra
$\operatorname*{QSym}\nolimits_{\mathbf{k}}$. In particular, $S$ denotes the
antipode of $\operatorname*{QSym}\nolimits_{\mathbf{k}}$, and $\ast$ denotes
the convolution product on linear maps from $\operatorname*{QSym}%
\nolimits_{\mathbf{k}}$ to any algebra.
\end{definition}

\begin{definition}
If $f\in\operatorname*{QSym}$, and if $a_{1}$, $a_{2}$, $\ldots$, $a_{k}$ are
some elements of a commutative ring, then the evaluation $f\left(  a_{1}%
,a_{2},\ldots,a_{k},\underbrace{0,0,0,\ldots}_{\text{just zeroes}}\right)  $
will be denoted by $f\left(  a_{1},a_{2},\ldots,a_{k}\right)  $ (as is usual
for symmetric functions).

Let $\varepsilon^{\times}$ denote the "second counit" of $\operatorname*{QSym}%
$; this is the ring homomorphism $\operatorname*{QSym}\rightarrow\mathbb{Z}$
which sends every $f\in\operatorname*{QSym}$ to $f\left(  1\right)  $.
\end{definition}

\textit{Proof sketch for Corollary \ref{cor.FGammawG.enum}.} We use the
standard(?) tactic to derive polynomiality and combinatorial reciprocity
phenomena from Hopf algebras. (For example, this is how \cite[Theorem
2.3]{Joch} follows from \cite[Proposition 7.7, Corollary 5.27 and Theorem
5.19]{Reiner}.)

Comparing the definitions of $W_{\Gamma,G}\left(  n\right)  $ and $F_{\left(
\Gamma,\mathbf{1}\right)  ,G}$ (recall that $\mathbf{1}$ is the map
$V\rightarrow\mathbb{N}_{+}$ sending everything to $1$), we easily observe
that $W_{\Gamma,G}\left(  n\right)  =F_{\left(  \Gamma,\mathbf{1}\right)
,G}\left(  \underbrace{1,1,\ldots,1}_{n\text{ ones}}\right)  $. But every
$f\in\operatorname*{QSym}$ satisfies%
\[
f\left(  \underbrace{1,1,\ldots,1}_{n\text{ ones}}\right)  =\left(
\Delta^{\left(  n\right)  }f\right)  \left(  \underbrace{\left(  1\right)
,\left(  1\right)  ,\ldots,\left(  1\right)  }_{n\text{ times the alphabet
}\left(  1\right)  }\right)  ,
\]
where $\Delta^{\left(  n\right)  }$ denotes the $n$-fold iterated coproduct
$\operatorname*{QSym}\rightarrow\operatorname*{QSym}\nolimits^{\otimes n}$
(depending on your tastes you might be calling this $\Delta^{\left(
n-1\right)  }$) and where elements of $\operatorname*{QSym}\nolimits^{\otimes
n}$ are supposed to be evaluated on $n$-tuples of alphabets by evaluating each
tensorand on the corresponding alphabet and then multiplying. In other words,
every $f\in\operatorname*{QSym}$ satisfies%
\[
f\left(  \underbrace{1,1,\ldots,1}_{n\text{ ones}}\right)  =\left(
\varepsilon^{\times}\right)  ^{\otimes n}\left(  \Delta^{\left(  n\right)
}f\right)  =\left(  \varepsilon^{\times}\right)  ^{\ast n}f,
\]
where $\left(  \varepsilon^{\times}\right)  ^{\ast n}$ denotes the $n$-th
power of $\varepsilon^{\times}$ in the convolution algebra
$\operatorname*{Hom}\left(  \operatorname*{QSym},\mathbb{Z}\right)  $ (the
algebra of all $\mathbb{Z}$-linear maps $\operatorname*{QSym}\rightarrow
\mathbb{Z}$). Thus,%
\[
W_{\Gamma,G}\left(  n\right)  =F_{\left(  \Gamma,\mathbf{1}\right)  ,G}\left(
\underbrace{1,1,\ldots,1}_{n\text{ ones}}\right)  =\left(  \varepsilon
^{\times}\right)  ^{\ast n}F_{\left(  \Gamma,\mathbf{1}\right)  ,G}.
\]
Now, why is this polynomial in $n$ ? Well, the counit $\varepsilon$ of the
coalgebra $\operatorname*{QSym}$ is the unity of the convolution algebra
$\operatorname*{Hom}\left(  \operatorname*{QSym},\mathbb{Z}\right)  $, and we
can write $\varepsilon^{\times}=\varepsilon+\left(  \varepsilon^{\times
}-\varepsilon\right)  $. The element $\varepsilon^{\times}-\varepsilon
\in\operatorname*{Hom}\left(  \operatorname*{QSym},\mathbb{Z}\right)  $ is
locally nilpotent: specifically, for every homogeneous $f\in
\operatorname*{QSym}$ of degree $d$, we have $\left(  \varepsilon^{\times
}-\varepsilon\right)  ^{\ast e}f=0$ for every integer $e>d$. Since $F_{\left(
\Gamma,\mathbf{1}\right)  ,G}$ is homogeneous of degree $\left\vert
V\right\vert $, this yields that $\left(  \varepsilon^{\times}-\varepsilon
\right)  ^{\ast e}F_{\left(  \Gamma,\mathbf{1}\right)  ,G}=0$ for every
integer $e>\left\vert V\right\vert $. Now,%
\begin{align}
W_{\Gamma,G}\left(  n\right)   &  =\left(  \underbrace{\varepsilon^{\times}%
}_{=\varepsilon+\left(  \varepsilon^{\times}-\varepsilon\right)  }\right)
^{\ast n}F_{\left(  \Gamma,\mathbf{1}\right)  ,G}=\underbrace{\left(
\varepsilon+\left(  \varepsilon^{\times}-\varepsilon\right)  \right)  ^{\ast
n}}_{\substack{=\sum\limits_{k=0}^{n}\dbinom{n}{k}\left(  \varepsilon^{\times
}-\varepsilon\right)  ^{\ast k}\\\text{(by the binomial formula, since
}\varepsilon\text{ is the unity}\\\text{of }\operatorname*{Hom}\left(
\operatorname*{QSym},\mathbb{Z}\right)  \text{)}}}F_{\left(  \Gamma
,\mathbf{1}\right)  ,G}\nonumber\\
&  =\sum\limits_{k=0}^{n}\dbinom{n}{k}\left(  \varepsilon^{\times}%
-\varepsilon\right)  ^{\ast k}F_{\left(  \Gamma,\mathbf{1}\right)  ,G}%
=\sum\limits_{k=0}^{\left\vert V\right\vert }\dbinom{n}{k}\left(
\varepsilon^{\times}-\varepsilon\right)  ^{\ast k}F_{\left(  \Gamma
,\mathbf{1}\right)  ,G}\label{pf.FGammawG.enum.1}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{we have cut the sum at }k=\left\vert V\right\vert \text{ since}\\
\left(  \varepsilon^{\times}-\varepsilon\right)  ^{\ast e}F_{\left(
\Gamma,\mathbf{1}\right)  ,G}=0\text{ for every integer }e>\left\vert
V\right\vert
\end{array}
\right)  .\nonumber
\end{align}
This clearly is a polynomial in $n$ of degree at most $\left\vert V\right\vert
$. That the degree is not less than $\left\vert V\right\vert $ follows from
asymptotics (we have $W_{\Gamma,G}\left(  n\right)  \geq\dbinom{n}{\left\vert
V\right\vert }$). This proves Corollary \ref{cor.FGammawG.enum} \textbf{(a)}.

The proof of \textbf{(b)} is not much different. Let us now come to
\textbf{(c)}. Recall that $W_{\Gamma,G}\left(  n\right)  =\left(
\varepsilon^{\times}\right)  ^{\ast n}F_{\left(  \Gamma,\mathbf{1}\right)
,G}$. But it is a general fact that if $H$ is a Hopf algebra and $A$ is an
algebra, and $f:H\rightarrow A$ is an algebra homomorphism, then
$f^{\ast\left(  -1\right)  }=f\circ S$ (where $f^{\ast\left(  -1\right)  }$ is
the inverse of $f$ with respect to convolution). Since $\left(  \varepsilon
^{\times}\right)  ^{\ast n}:\operatorname*{QSym}\rightarrow\mathbb{Z}$ is an
algebra homomorphism (this follows, e. g., from $\left(  \varepsilon^{\times
}\right)  ^{\ast n}f=f\left(  \underbrace{1,1,\ldots,1}_{n\text{ ones}%
}\right)  $, or from general Hopf algebra lore), this yields that $\left(
\left(  \varepsilon^{\times}\right)  ^{\ast n}\right)  ^{\ast\left(
-1\right)  }=\left(  \varepsilon^{\times}\right)  ^{\ast n}\circ S$. In other
words, $\left(  \varepsilon^{\times}\right)  ^{\ast\left(  -n\right)
}=\left(  \varepsilon^{\times}\right)  ^{\ast n}\circ S$. Now, since
$W_{\Gamma,G}\left(  n\right)  =\left(  \varepsilon^{\times}\right)  ^{\ast
n}F_{\left(  \Gamma,\mathbf{1}\right)  ,G}$, we have%
\[
W_{\Gamma,G}\left(  -n\right)  =\left(  \varepsilon^{\times}\right)
^{\ast\left(  -n\right)  }F_{\left(  \Gamma,\mathbf{1}\right)  ,G}%
\]
(we used the polynomiality of $\left(  \varepsilon^{\times}\right)  ^{\ast
n}F_{\left(  \Gamma,\mathbf{1}\right)  ,G}$ here), so that%
\begin{align*}
W_{\Gamma,G}\left(  -n\right)   &  =\underbrace{\left(  \varepsilon^{\times
}\right)  ^{\ast\left(  -n\right)  }}_{=\left(  \varepsilon^{\times}\right)
^{\ast n}\circ S}F_{\left(  \Gamma,\mathbf{1}\right)  ,G}=\left(
\varepsilon^{\times}\right)  ^{\ast n}\left(  \underbrace{S\left(  F_{\left(
\Gamma,\mathbf{1}\right)  ,G}\right)  }_{\substack{=\left(  -1\right)
^{\left\vert V\right\vert }F_{\left(  \omega\left(  \Gamma\right)
,\mathbf{1}\right)  ,G}^{+}\\\text{(by Corollary \ref{cor.FGammawG}
\textbf{(c)})}}}\right) \\
&  =\left(  -1\right)  ^{\left\vert V\right\vert }\underbrace{\left(
\varepsilon^{\times}\right)  ^{\ast n}\left(  F_{\left(  \omega\left(
\Gamma\right)  ,\mathbf{1}\right)  ,G}^{+}\right)  }_{\substack{=W_{\left(
\omega\left(  \Gamma\right)  ,\mathbf{1}\right)  ,G}^{+}\left(  n\right)
\\\text{(by an analogue of (\ref{pf.FGammawG.enum.1}))}}}=\left(  -1\right)
^{\left\vert V\right\vert }W_{\left(  \omega\left(  \Gamma\right)
,\mathbf{1}\right)  ,G}^{+}\left(  n\right)  .
\end{align*}
This proves part \textbf{(c)}.

\begin{thebibliography}{999999999}                                                                                        %


\bibitem[Abe77]{Abe-HA}Eiichi Abe, \textit{Hopf Algebras}, CUP 1977.

\bibitem[ABS03]{ABS}Marcelo Aguiar, Nantel Bergeron, Frank Sottile,
\textit{Combinatorial Hopf algebras and generalized Dehn-Sommerville
relations}, Compositio Mathematica, vol. 142, Issue 01, January 2006, pp.
1--30.\newline Also available as arXiv:math/0310016.\newline Newer version at
\texttt{\url{http://www.math.tamu.edu/~maguiar/CHalgebra.pdf}}

\bibitem[BBSSZ13]{BBSSZ}Chris Berg, Nantel Bergeron, Franco Saliola, Luis
Serrano, Mike Zabrocki, \textit{A lift of the Schur and Hall-Littlewood bases
to non-commutative symmetric functions}, Canadian Journal of Mathematics,
\newline\texttt{\url{http://dx.doi.org/10.4153/CJM-2013-013-0}} \newline Also
available as arXiv:1208.5191v3. \newline%
\texttt{\url{http://arxiv.org/abs/1208.5191v3}}

\bibitem[BenSag14]{BenSag}Carolina Benedetti, Bruce Sagan, \textit{Antipodes
and involutions}, arXiv:1410.5023v1.\newline%
\texttt{\url{http://arxiv.org/abs/1410.5023v1}}

\begin{obsolete}
\bibitem[BesSta13]{StanBess}Christine Bessenrodt, Richard P. Stanley,
\textit{Smith Normal Form of a Multivariate Matrix Associated with
Partitions}, arXiv:1311.6123v1.\newline%
\texttt{\url{http://arxiv.org/abs/1311.6123v1}}
\end{obsolete}


\bibitem[BreKli14]{BreKli14}Felix Breuer, Caroline J. Klivans,
\textit{Scheduling Problems}, arXiv:1401.2978v1.\newline%
\texttt{\url{http://arxiv.org/abs/1401.2978v1}}

\bibitem[DNR01]{Dasca-HA}Sorin D\u{a}sc\u{a}lescu, Constantin
N\u{a}st\u{a}sescu, \c{S}erban Raianu, \textit{Hopf Algebras}, Marcel Dekker 2001.

\bibitem[EbrFar08]{EbrFar08}Kurusch Ebrahimi-Fard, Dominique Manchon,
\textit{Dendriform Equations}, Journal of Algebra 322 (2009), pp.
4053--4079.\newline%
\texttt{\url{http://www.sciencedirect.com/science/article/pii/S0021869309003524}}
\newline An older version is also available as arXiv:0805.0762v2:\newline%
\texttt{\url{http://arxiv.org/abs/0805.0762v2}}

\bibitem[Fresse14]{Fresse-Op}Benoit Fresse, \textit{Homotopy of operads and
Grothendieck-Teichm\"{u}ller groups, Part I: From operads to
Grothendieck-Teichm\"{u}ller groups}, preprint, March 2, 2014.\newline%
\texttt{\url{http://math.univ-lille1.fr/~fresse/OperadGT-December2012Preprint.pdf}}%


\bibitem[Gessel84]{Gessel-multipar}Ira M. Gessel, \textit{Multipartite
P-partitions and Inner Products of Skew Schur Functions}, Contemporary
Mathematics, vol. 34, 1984, pp. 289--301.\newline%
\texttt{\url{http://people.brandeis.edu/~gessel/homepage/papers/multipartite.pdf}}%


\bibitem[GriRei15]{Reiner}Darij Grinberg, Victor Reiner, \textit{Hopf algebras
in Combinatorics}, June 1, 2015, arXiv:1409.8356v2.\newline%
\texttt{\url{http://www.math.umn.edu/~reiner/Classes/HopfComb.pdf}}

\bibitem[Hazewi08]{Hazew-Witt1}Michiel Hazewinkel, \textit{Witt vectors. Part
1}, arXiv:0804.3888v1.\newline\texttt{\url{http://arxiv.org/abs/0804.3888v1}}
\newline Also appears as a chapter in: Michiel Hazewinkel, \textit{Handbook of
Algebra: Volume 6}, Elsevier 2009.

\bibitem[Hivert99]{Hivert-CQS}Florent Hivert, \textit{Combinatoire des
fonctions quasi-sym\'{e}triques}, PhD thesis, defended 1999, January the
15.\newline\texttt{\url{https://www.lri.fr/~hivert/PAPER/these.ps}}

\bibitem[Joch13]{Joch}Katharina Jochemko, \textit{Order polynomials and
P\'{o}lya's enumeration theorem}, arXiv:1310.0838v2.\newline%
\texttt{\url{http://arxiv.org/abs/1310.0838v2}}

\bibitem[LMvW13]{LMvW}Kurt Luoto, Stefan Mykytiuk and Stephanie van
Willigenburg, \textit{An introduction to quasisymmetric Schur functions --
Hopf algebras, quasisymmetric functions, and Young composition tableaux}, May
23, 2013.\newline%
\texttt{\url{http://www.math.ubc.ca/~steph/papers/QuasiSchurBook.pdf}}

\bibitem[Malve93]{Malve-Thesis}Claudia Malvenuto, \textit{Produits et
coproduits des fonctions quasi-sym\'{e}triques et de l'alg\`{e}bre des
descentes}, thesis, defended November 1993.\newline%
\texttt{\url{http://www1.mat.uniroma1.it/people/malvenuto/Thesis.pdf}}

\bibitem[MalReu98]{Mal-Reu}Claudia Malvenuto, Christophe Reutenauer,
\textit{Plethysm and conjugation of quasi-symmetric functions}, Discrete
Mathematics, Volume 193, Issues 1--3, 28 November 1998, Pages
225--233.\newline%
\texttt{\url{http://www.sciencedirect.com/science/article/pii/S0012365X98001423}}%


\bibitem[Manchon04]{Manchon-HA}Dominique Manchon, \textit{Hopf algebras, from
basics to applications to renormalization}, Comptes Rendus des Rencontres
Mathematiques de Glanon 2001 (published in 2003).\newline%
\texttt{\url{http://arxiv.org/abs/math/0408405v2}}

\bibitem[Montg93]{Montg-Hopf}Susan Montgomery, \textit{Hopf Algebras and their
Actions on Rings}, Regional Conference Series in Mathematics Nr. 82, AMS 1993.

\bibitem[NovThi05]{Nov-Thi}Jean-Christophe Novelli, Jean-Yves Thibon,
\textit{Hopf algebras and dendriform structures arising from parking
functions}, Fundamenta Mathematicae 193 (2007), 189--241. A preprint also
appears on arXiv as arXiv:math/0511200v1.

\bibitem[Stan11]{Stanley-EC1}Richard Stanley, \textit{Enumerative
Combinatorics, volume 1}, Cambridge University Press, 2011. \newline%
\texttt{\url{http://math.mit.edu/~rstan/ec/ec1/}}

\bibitem[Stan99]{Stanley-EC2}Richard Stanley, \textit{Enumerative
Combinatorics, volume 2}, Cambridge University Press, 1999.

\bibitem[Stan71]{Stanley-Thes}Richard Stanley, \textit{Ordered Structures and
Partitions}, Memoirs of the American Mathematical Society, No. 119, American
Mathematical Society, Providence, R.I., 1972. \newline%
\texttt{\url{http://www-math.mit.edu/~rstan/pubs/pubfiles/9.pdf}}

\bibitem[Sweed69]{Sweedler-HA}Moss E. Sweedler, \textit{Hopf Algebras}, W. A.
Benjamin 1969.

\bibitem[Thomas77]{Thomas-Bax}Gl\^{a}nffrwd P. Thomas, \textit{Frames, Young
Tableaux, and Baxter Sequences}, Advances in Mathematics, Volume 26, Issue 3,
December 1977, pp. 275--289.\newline%
\texttt{\url{http://www.sciencedirect.com/science/article/pii/0001870877900421}}%


\bibitem[Thomas76]{Thomas-Further}Gl\^{a}nffrwd P. Thomas, \textit{Further
Results on Baxter Sequences and Generalized Schur Functions}, Actes de la
Table Ronde du C.N.R.S. tenue \`{a} l'Universit\'{e} Louis-Pasteur de
Strasbourg, 26 au 30 avril 1976, Lecture Notes in Mathematics Volume 579
(1977), pp. 155-167.
\end{thebibliography}


\end{document}