\documentclass[12pt]{amsart}
\usepackage{amsmath,amsthm, amssymb,color}
%\usepackage[latin1]{inputenc}
%\usepackage[T1]{fontenc}   
\usepackage{stmaryrd}
\usepackage{shuffle,mathabx}
%\usepackage{youngtab}
\usepackage[english]{babel}
%\setlength{\textwidth}{16cm}
%\setlength{\textheight}{25cm}
%\topmargin = -25mm
%\oddsidemargin = -1mm
%\evensidemargin = 0mm


%\input{arbres}
%\input{posets}

\input{xy}
\xyoption{all}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem{rmk}[theorem]{Remark}
\newtheorem*{remark}{Remark}
\newtheorem*{example}{Example}
\newtheorem*{examples}{Examples}



%\newenvironment{proof}{\textbf{Proof.}}{\hfill $\Box$}

\def\Top{\operatorname{\it Top}}
\newcommand{\tdelta}{\tilde{\Delta}}
\newcommand{\qshuffle}{\squplus}


\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}^N_*}
\newcommand{\K}{\mathbb{K}}
\newcommand{\g}{\mathfrak{g}}

\newcommand{\dpos}{\mathbf{dp}}
\newcommand{\dqp}{\mathbf{dqp}}
\newcommand{\pqp}{\mathbf{pqp}}
\newcommand{\sqp}{\mathbf{sqp}}
\newcommand{\tqp}{\mathbf{tqp}}
\newcommand{\qp}{\mathbf{qp}}
\renewcommand{\P}{\mathbf{P}}
\newcommand{\p}{\mathbf{p}}
\newcommand{\h}{\mathcal{H}}
\newcommand{\E}{{\mathcal E}}
\newcommand{\I}{{\mathcal I}}
\newcommand{\isoclass}[1]{\lfloor #1 \rfloor}
\newcommand{\WQSym}{\mathbf{WQSym}}
\newcommand{\FQSym}{\mathbf{FQSym}}
\newcommand{\bfPW}{\mathbf{PW}}
\newcommand{\poset}{\Xi}
\newcommand{\End}{\mathrm{End}}
\newcommand{\Lin}{\mathrm{Lin}}
\newcommand{\WLin}{\mathrm{WLin}}
\newcommand{\Inv}{\mathrm{Inv}}
\newcommand{\pack}{\mathrm{pack}}
\newcommand{\Sh}{\mathrm{Sh}}

\newcommand{\rond}[1]{*++[o][F-]{#1}}


\title{Surjections as double posets}
\date{}


\begin{document}

\author{Lo\"\i c Foissy}
\address{LMPA Joseph Liouville\\
Universit\'e du Littoral C\^ote d'opale\\ Centre Universitaire de la Mi-Voix\\ 50, rue Ferdinand Buisson, CS 80699\\ 62228 Calais Cedex, France\\
email {foissy@lmpa.univ-littoral.fr}}

\author{Fr\'ed\'eric Patras}
\address{Universit\'e C\^ote d'Azur\\
        		UMR 7351 CNRS\\
        		Parc Valrose\\
        		06108 Nice Cedex 02
        		France\\
        		email {patras@unice.fr}}


\begin{abstract}
The theory of double posets and pictures between them, introduced by Malvenuto and Reutenauer, is a far reaching development of Zelevinsky's theory of pictures in that, among others, it embeds the latter into a self-dual Hopf algebraic framework. It has brought forward many ideas and results and has led recently to several developments, in various directions. Namely, besides algebraic combinatorics and  noncommutative representation theory: algebraic topology and the geometry of polytopes.

One of these developments, by the first author of this article, was the combinatorial and Hopf algebraic study of symmetric groups from the point of view of double posets. 
The present article extends these results to surjections.
We introduce first a family of double posets, packed double posets. Using an appropriate statistics on surjections that generalizes inversions, it is shown that they are in bijection with surjections or, equivalently, with packed words. The following sections investigate their self-dual Hopf algebraic properties. Using an appropriate notion of linear extensions of packed double posets, the Hopf algebra of packed double posets is proved to be isomorphic with (two different versions of) the Hopf algebra of word quasi-symmetric functions.
\end{abstract}
\maketitle

\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 82 \rms (2020), Article~B82a\hfill}
\def\thepage{}

%\tableofcontents 

\section{Introduction}
The theory of double posets and pictures between them was introduced by Malvenuto and Reutenauer in 2011 \cite{MR2}.  It is a far reaching development of Zelevinsky's theory of pictures \cite{zelevinsky1981generalization} in that it embeds for example the latter into a self-dual Hopf algebraic framework. It has brought forward many ideas and results and has recently led to several developments, in various directions. In algebraic combinatorics and  noncommutative representation theory, double posets have been used to study the combinatorics of symmetric groups \cite{foissy2013algebraic,foissy2013plane,foissy2014deformation} and, in relation to quasisymmetric functions, to generalize objects such as dual immaculate functions or quasisymmetric
$( P, \omega )$-partition enumerators \cite{Grinberg}. The theory of double posets was also generalized to double quasi-posets, a natural framework to study objects such as semi-standard tableaux on which several quasi-orders coexist naturally \cite{FMP2017}. In algebraic topology, they appear as an example of monoidal (directed) restriction species \cite{GKT}.
In the geometry of polytopes, the notion of double poset polytopes \cite{CFS,Benj}
has been introduced as a generalization of Stanley's work relating the geometry of polytopes with the combinatorics of associated posets \cite{stan}.

The present article extends the results of \cite{foissy2013algebraic,foissy2013plane} on permutations to surjections.
It is organized as follows. We introduce first (Section~\ref{sec:pack}) a family of double posets, packed double posets, that generalize the planar posets of \cite{foissy2013plane}.
They can be shown to be in bijection with surjections or, equivalently, with packed words (Theorem~\ref{th4}, Section~\ref{sec:surj}).
Section~\ref{sec:Hopf} investigates their self-dual Hopf algebraic properties, which are inherited from the Hopf algebra structure of double posets \cite{MR2}. Section~\ref{sec:hs} recalls briefly the idea of non-linear Schur--Weyl duality and how two Hopf algebra structures can be constructed on the linear span of surjections using their interpretation as operations on tensor powers of a commutative algebra. One of these two Hopf algebras is the classical Chapoton--Hivert Hopf algebra $\WQSym$ of word quasi-symmetric functions \cite{hivert,chapoton2000algebres}.
 Section~\ref{sec:lin} introduces the notion of linear and weak linear extensions of packed double posets. It gives rise to Hopf algebra isomorphisms from the Hopf algebra of packed double posets to the two Hopf algebra structures introduced in Section~\ref{sec:hs}. 

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL LO\"IC FOISSY AND FR\'ED\'ERIC PATRAS}{\SMALL SURJECTIONS AS DOUBLE POSETS}



\section{Packed double posets}\label{sec:pack}

Recall that a double poset is a set equipped with two orders. A quasi-order is a binary relation $\leq$ which is reflexive and transitive but not necessarily antisymmetric (so that one may have $x\leq y$ and $y\leq x$ with $x\not= y$). A quasi-order is total when all elements are comparable (i.e., when $x\leq y$ or $y\leq x$ for arbitrary $x$ and $y$). If $x\leq y$ and $y\leq x$, we write $x\equiv y$ and say that $x$ and $y$ are equivalent (the relation $\equiv$ is an equivalence relation). 
A quasi-poset is a set equipped with a quasi-order. All the posets, double posets, quasi-posets, \dots\ we consider here are assumed to be finite (we omit therefore ``finite'' in our definitions and statements).

\begin{definition}
A packed double poset is a double poset $(P,\leq_1,\leq_2)$ that satisfies the
following two properties:
\begin{enumerate}
\item For all $x,y\in P$, we have $(x\leq_1 y$ and $x\leq_2 y)$ $\Longrightarrow$ $(x=y)$.
\item The relation $\preceq$ defined on $P$ by $(x\leq_1 y$ or $x\leq_2 y)$ is a total quasi-order.
\end{enumerate} 
\end{definition}

In particular, the relation defined by ($x\preceq y$ and $y\preceq x$) is an equivalence relation (we denote it as above by $\equiv$).

\begin{example} A plane poset is a double poset $(P,\leq_1,\leq_2)$ with the following properties: 
\begin{itemize}
\item For all $x,y\in P$,  if $x$ and $y$ are comparable for both $\leq_1$ and $\leq_2$, then $x=y$.
\item For all $x,y\in P$, $x$ and $y$ are comparable for $\leq_1$ or for $\leq_2$.
\end{itemize}
By Proposition~11 of \cite{foissy2013plane}, if $(P,\leq_1,\leq_2)$ is a plane poset, then $\preceq$ is a total order, and obviously (1) is also satisfied.
So plane posets are packed double posets. Moreover, if $P$ is a packed double poset, then $\preceq$ is an order if,
and only if, $P$ is plane: by (2), two distinct elements $x,y$ are always comparable, and the fact that $\preceq$ is an order implies that they cannot be comparable for both $\leq_1$ and $\leq_2$.
\end{example}

\begin{lemma}\label{weaklem}
Let $(P,\leq_1,\leq_2)$ be a packed double poset. Then:
\begin{enumerate}
\item[(3)] The relation $\ll$ defined on $P$ by $(y\leq_1 x$ or $x\leq_2 y)$ is a total order.
\end{enumerate}
\end{lemma}

\begin{proof}  Let $x,y,z\in P$, such that $x\ll y$ and $y\ll z$. The following three cases are possible:
\begin{itemize}
\item ($y\leq_1 x$ and $z\leq_1 y$) or ($x\leq_2 y$ and $y\leq_2 z$). Then ($z\leq_1 x$ or $x\leq_2 z$), so $x\ll z$.
\item $x\leq_2 y$ and $z\leq_1 y$. As $\preceq$ is a total quasi-order, 
the following two subcases are possible:
\begin{itemize}
\item $x\preceq z$, then $x\leq_1 z$ or $x\leq_2 z$. If $x\leq_2 z$, then $x\ll z$. If $x \leq_ 1 z$, then $x\leq_1 y$ and $x\leq_2 y$.
By (1), $x=y$, so $x\ll z$.
\item $z\preceq x$, then $z \leq_1 x$ or $z\leq_2 x$. If $z\leq_1 x$, then $x\ll z$. If $z\leq_2 x$, then $z\leq_2 y$ and $z\leq_1 y$.
By (1), $y=z$, so $x\ll z$. 
\end{itemize}
\item $y\leq_1 x$ and $y\leq_2 z$. Similar proof.
\end{itemize}
Therefore, $\ll$ is transitive. 

Let $x,y\in P$, such that $x\ll y$ and $y\ll x$. The following two cases are possible:
\begin{enumerate}
\item ($y\leq_1 x$ and $x\leq_1 y$) or ($x\leq_2 y$ and $y\leq_2 x$): then $x=y$.
\item $y\leq_1 x$ and $y\leq_2 x$, or $x\leq_1 y$ and $x\leq_2 y$: by (1), $x=y$.
\end{enumerate}
So $\ll$ is an order.

For all $x,y\in P$, $x\preceq y$ or $y\preceq x$, so $y\leq_1 x$ or $x\leq_2 y$ or $x\leq_1 y$ or $y\leq_2 x$, so
$x\ll y$ or $y\ll x$: in other words, $\ll$ is total. \end{proof}

\begin{remark} (3) implies (1), but not (2).
\end{remark}

\begin{remark} The lemma allows one to canonically identify $P$ with $[n]$ and the pair $(P,\preceq)$ with a packed word. This is the reason for the terminology adopted for ``packed double posets''. See the next section for details.
\end{remark}

\section{Surjections and packed words}\label{sec:surj}

When a surjection $f$ from $[n]$ to $[k]$ is represented by the sequence of its values, $w_f:=f(1)\dots f(n)$, the word $w_f$ is packed: its set of letters can be identified with an initial subset of the integers (in that case, $[k]$). Conversely, an arbitrary packed word of length $n$ 
can always be obtained in that way: packed words (of length $n$) are in bijection with surjections (with domain $[n]$ and codomain an initial subset of the integers).
We write $pack$ for the packing operation: given a word $w$ with (possibly repeated) letters $x_1<\dots <x_k$ in $[n]$, $\pack(w)$ is the word obtained from $w$ by replacing the letter $x_i$ by $i$. For example, $\pack(714274)=(413243)$.

Recall also that total quasi-orders $\preceq$ on $[n]$ are in bijection with packed words. An example illustrates the general rule: assume that $n=6$ and that the quasi-order is defined by
\[2\equiv 5\preceq 1\equiv 3\equiv 6\preceq 4.\]
Then the corresponding packed word is $212312$: the first equivalence class $\{2,5\}$ gives the position of letter 1, the second, $\{1,3,6\}$, the positions of letter 2, and so on.

\begin{proposition}
Let $w$ be a packed word of length $n$. The double poset $P_w$ {\em(}also written $Dp(w)${\em)} is defined by $P_w=([n],\leq_1,\leq_2)$, with:
\begin{align*}
&\text{for all }i,j\in [n],& i\leq_1 j&\Longleftrightarrow (i\geq j\mbox{ and } w(i)\leq w(j)),\\
&&i\leq_2 j&\Longleftrightarrow (i\leq j\mbox{ and } w(i)\leq w(j)).
\end{align*}
It is a packed double poset. The total quasi-order $\preceq$ is the one associated bijectively with $w$; the total order is the natural order on $[n]$.
\end{proposition}

\begin{proof}
The fact that $P_w$ is a double poset is obvious. For all $i,j\in [n]$, if $i\leq_1 j$ and $i\leq_2 j$, then $i\geq j$ and $i\leq j$, so $i=j$: (1) is verified.
Moreover:
\[i \preceq j \Longleftrightarrow w(i)\leq w(j),\]
so $\preceq$ is indeed a total quasi-order.
\end{proof}

\begin{theorem}\label{th4}
The set of packed words of length $n$ and the set of isomorphism classes of packed double posets are in bijection through $Dp$. The inverse map, $pack$, is given as follows. Let $P$ be a packed double poset. By Lemma~\ref{weaklem}, we can assume that $P=[n]$ with $\ll$ the natural order. Then $Dp^{-1}(P)=:\pack(P)$ is the packed word associated with the total quasi-order $\preceq$.
\end{theorem}



\begin{proof} We first show that, for any packed words $w$, $w'$, the double posets $P_w$ and $P_{w'}$ are isomorphic if, and only if, $w=w'$.  Let $f:P_w\to P_{w'}$ be an isomorphism. Then $f$ is increasing from $([n],\ll)$ to $([n'],\ll')$.
As $\ll$ and $\ll'$ are the usual total orders of $[n]$ and $[n']$, $n=n'$ and $f=\text{Id}_{[n]}$. Consequently, for all $i,j\in [n]$ with $i\leq j$, we have
\[w(i)\leq w(j)\Longleftrightarrow i\leq_2 j\Longleftrightarrow i\leq_2' j\Longleftrightarrow w'(i)\leq w'(j).\]
As $w$ and $w'$ are packed words, we infer $w=w'$. 

\medskip
Let now $P$ be a packed double poset. We claim that $Dp(\pack(P))=P$.
We may assume that $(P,\ll)=([n],\leq)$. The packed word $w=\pack(P)$ is such that, for all $i,j\in [n]$, $i\preceq j$ $\Longleftrightarrow$ $w(i)\leq w(j)$.
We denote the orders of $P_w$ by $\leq_1'$ and $\leq_2'$. Then, for all $i,j\in [n]$, we have
\begin{align*}
i\leq'_1 j&\Longleftrightarrow (j\leq i) \mbox{ and }(w(i)\leq w(j))\\
&\Longleftrightarrow (j\ll i)\mbox{ and }(i\preceq j)\\
&\Longleftrightarrow (i\leq_1 j\mbox{ or } j\leq_2 i)\mbox{ and }(i\leq_1 j\mbox{ or } i\leq_2 j)\\
&\Longleftrightarrow (i\leq_1 j)\mbox{ or }(j\leq_2 i \mbox{ and } i\leq_2 j)\\
&\Longleftrightarrow (i\leq_1 j)\mbox{ or }(i=j)\\
&\Longleftrightarrow i\leq_1 j. 
\end{align*}
So $\leq_1'=\leq_1$. Similarly, $\leq_2'=\leq_2$.
\end{proof}

\section{The self-dual Hopf algebra structure}\label{sec:Hopf}

We denote by $\h_{DP}$ the vector space generated by isomorphism classes of double posets, and by $\h_{PDP}$ its subspace 
generated by isomorphism classes of packed double posets. Below we show how definitions and results in \cite{MR2,FMP2017} apply in this context (definitions and results relative to double posets are taken from \cite{MR2}).

Let $P,Q$ be two double posets. We define two orders on $P\sqcup Q$ by:
\begin{align*}
&\text{for all }i,j\in P\sqcup Q,& i\leq_1 j\mbox{ if }&(i,j\in P\mbox{ and } i\leq_1 j) \\
&&&\mbox{ or }(i,j\in Q\mbox{ and } i\leq_1 j);\\
&& i\leq_2 j\mbox{ if }&(i,j\in P\mbox{ and } i\leq_2 j)\\
&&&\mbox{ or }(i,j\in Q\mbox{ and } i\leq_2 j)\\
&&&\mbox{ or }(i\in P\mbox{ and } j\in Q).
\end{align*}
This defines a double poset, which we denote by $PQ$. Extension of this product by bilinearity makes $\h_{DP}$  an associative algebra, whose
unit is the empty double poset denoted $1$. 
If $P$ and $Q$ are packed double posets, then so is $PQ$. Hence, $\h_{PDP}$ is a subalgebra of $\h_{DP}$.

\begin{definition}
Let $P$ be a double poset (respectively packed double poset) and let $X\subseteq P$.
\begin{itemize}
\item $X$ is also a double poset (respectively packed) by restriction of $\leq_1$ and $\leq_2$:
we denote this double poset (respectively packed) by $P_{\mid X}$. 
\item We say that $X$ is an open set of $P$ if
\begin{align*}
&\text{for all }i,j\in P,& i\leq_1 j\mbox{ and }i\in X&\Longrightarrow j\in X.
\end{align*}
The set of open sets of $P$ is denoted by $\Top(P)$.
\item A coproduct is defined on $\h_{DP}$ (respectively $\h_{PDP}$)
by
\[\Delta(P)=\sum_{O\in \Top(P)}P_{\mid P\setminus O}\otimes P_{\mid O}.\]
\end{itemize} \end{definition}


\begin{theorem}
The product and the coproduct equip $\h_{DP}$ and therefore its subspace $\h_{PDP}$ with the structure of a graded, connected Hopf algebra.
\end{theorem}

See \cite{MR2} for a proof of the compatibility properties between the product and the coproduct characterizing a Hopf algebra.

Recall that, for $P=(P,\leq_1,\leq_2)$, $\iota(P):=(P,\leq_2,\leq_1)$.
If $P$ is a packed double poset, then so is $\iota(P)$. Recall also that, given two double posets $P,Q$, there exists a pairing on $\h_{DP}$ defined  by
\[\langle P,Q\rangle:=\sharp Pic(P,Q),\]
where $Pic(P,Q)$ stands for the number of pictures between $P$ and $Q$ (a picture between $P$ and $Q$ is a bijection $f$ such that 
\begin{align*}
i\leq_1 j&\Rightarrow f(i)\leq_2 f(j), &f(i)\leq_1 f(j)&\Rightarrow i\leq_2 j.
\end{align*}
The Hopf algebra of double posets $\h_{DP}$ is self-dual for this pairing. By Proposition~24 of \cite{FMP2017}, we get the following result.

\begin{proposition}
The Hopf algebra $\h_{PDP}$ is a self-dual Hopf subalgebra of the Hopf algebra of double posets $\h_{DP}$.
\end{proposition}

\section{Hopf algebras of surjections}\label{sec:hs}
We write $\WQSym_n$ for the linear span of surjections from $[n]$ to an arbitrary $[p]$, $p\leq n$ (and set $\WQSym_0:=\mathbb Q$, $\WQSym:=\bigoplus\limits_{n\geq 0}\WQSym_n$). 

The symbol $\WQSym$ stands for ``word quasi-symmetric functions''. We refer to \cite{chapoton2000algebres,hivert} for definitions and to \cite{krob2000pseudo,Novelli} for studies of their combinatorial properties. On the terminology and notation, see also Remark~\ref{rem} below.

Recall that natural transformations from the functor (from commutative algebras to vector spaces) $T_n(A):=A^{\otimes n}$ to $T_p(A):=A^{\otimes p}$, $0\leq p\leq n$, are in bijection with the linear span of surjections from $[n]$ to $[p]$ by non-linear Schur--Weyl duality \cite{foissy2}. For example, the map $f:[5]\to [3]$, $f(1)=2,f(2)=1,f(3)=3,f(4)=2,f(5)=1$ gives rise to the map
\begin{align*}
A^{\otimes 5}&\longrightarrow  A^{\otimes 3},\\
\ a_1\otimes\dots\otimes a_5&\longmapsto a_2a_5\otimes a_1a_4\otimes a_3.
\end{align*}
This observation leads to two Hopf algebra structures on $\WQSym$. Recall indeed that, given a commutative algebra $A$, the tensor algebra over $A$, $T(A)$, carries two Hopf algebra structures when equipped with the deconcatenation coproduct 
\[\delta : a_1\otimes\dots \otimes a_n\longmapsto \sum\limits_{i\leq n}(a_1\otimes\dots\otimes a_i)\otimes (a_{i+1}\otimes\dots\otimes a_n).\]
The first structure uses the shuffle product inductively defined by
\begin{multline*}
a_1\otimes\dots\otimes a_n\shuffle b_1\otimes\dots\otimes b_m:=a_1(a_2\otimes\dots\otimes a_n\shuffle b_1\otimes\dots\otimes b_m)\\
+b_1(a_1\otimes\dots\otimes a_n\shuffle b_2\otimes\dots\otimes b_m),
\end{multline*}
the second uses the quasi-shuffle product inductively defined by 
\begin{align*}
a_1\otimes\dots\otimes a_n\qshuffle b_1\otimes\dots\otimes b_m&:=a_1(a_2\otimes\dots\otimes a_n\qshuffle b_1\otimes\dots\otimes b_m)\\
&\quad +b_1(a_1\otimes\dots\otimes a_n\qshuffle b_2\otimes\dots\otimes b_m)\\
&\quad +(a_1b_1)(a_2\otimes\dots\otimes a_n\qshuffle b_2\otimes\dots\otimes b_m).
\end{align*}
Due to the embedding $\WQSym\hookrightarrow \End(T(A))$, where a surjection $f:[n]\to [p]$ acts trivially on 
$T_r(A)$ for $r\not= n$ and by the action obtained by Schur--Weyl duality otherwise, we get two graded convolution products: for $f$ as above, 
$g:[k]\to [l]$ and $w\in T(A)$, we define
\begin{align*}
f\shuffle g(w)&:=f(w^{(1)})\shuffle g(w^{(2)}),\\
f\qshuffle g(w)&:=f(w^{(1)})\qshuffle g(w^{(2)}),
\end{align*}
using the Sweedler shortcut notation $\delta(w)=w^{(1)}\otimes w^{(2)}$.
That is, equivalently,
$f\shuffle g=\sum_hh$, where $h$ runs over the surjections\break $h:[n+k]\to[p+l]$ with $\pack(h(1)\dots h(n))=(f(1)\dots f(n))$ and\break $\pack(h(n+1)\dots h(n+k))=(g(1)\dots g(k))$. Notice that these conditions imply 
\[\{h(1),\dots,h(n)\}\cap\{h(n+1),\dots,h(n+k)\}=\emptyset.\]
For the $\qshuffle$ product we have instead $f\qshuffle g=\sum_hh$, where $h$ runs over the surjections $h:[n+k]\to[q]$ with $\sup(p,l)\leq q\leq p+l$ with $\pack(h(1)\dots h(n))=(f(1)\dots f(n))$ and $\pack(h(n+1)\dots h(n+k))=(g(1)\dots g(k))$.

For example,
\begin{align*}
(211)\shuffle (1)&=(2113)+(3112)+(3221),\\
(211)\qshuffle (1)&=(2113)+(3112)+(3221)+(2111)+(2112).
\end{align*}
A coproduct $\Delta$ is defined on $\WQSym$ by
\[\Delta(f):=\sum\limits_{i\leq p}f_{|\{1,\dots,i\}}\otimes \pack(f_{|\{i+1,\dots,p\}}),\]
where a surjection is written as a packed word and, given $S\subseteq [p]$, $f_{|S}$ stands for the subword of $f$ containing the letters in $S$. For example, if $f=(5312354)$ and $S=\{2,4,5\}$, $f_{|S}=(5254)$ and $\pack(f_{|S})=(3132)$.

The following proposition is proved in \cite{hivert,chapoton2000algebres}, respectively in \cite{FM}.

\begin{proposition} The triples $(\WQSym,\qshuffle,\Delta)$ and $(\WQSym,\shuffle,\Delta)$ are graded connected (noncommutative, noncocommutative) Hopf algebras.
\end{proposition}

\begin{rmk}\label{rem} Our notation is slightly conflicting with the usual practice.
Indeed, the symbol $\WQSym$ stands very often in the literature for the Hopf algebra $(\WQSym,\qshuffle,\Delta)$, not just (as in the present article) for the underlying graded vector space. Moreover, this Hopf algebra is classically presented as a subalgebra of a ring of formal series $\K\langle\langle X\rangle\rangle$,
where $X$ is a countably infinite totally ordered alphabet, linearly generated by formal series $M_u$ indexed by surjections.
For example,
\begin{align*}
M_{(1)}&=\sum_{x\in X} x,&M_{(12)}&=\sum_{x<y\in X}xy,\\
M_{(11)}&=\sum_{x\in X}xx,&M_{(21)}&=\sum_{x<y\in X}yx.
\end{align*}
The coproduct $\Delta$ is then obtained by doubling the alphabet, see \cite{Novelli}. 

Our notational choice was motivated by the fact that we are working directly with surjections (and not linear combinations of words indexed by them) and need to define two products on their linear span, one of which {\rm ($\shuffle$)} is not induced by the product of monomials in $\K\langle\langle X\rangle\rangle$. 
\end{rmk}

\section{Linear extensions and $\WQSym$.}\label{sec:lin}
\begin{definition}
Let $P=(P,\leq_1,\leq_2)$ be a packed double poset. A linear extension of $P$ is a surjective map
$f:P\longrightarrow [k]$ such that:
\begin{enumerate}
\item For all $i,j\in P$, $i\leq_1 j$ $\Longrightarrow$ $f(i)\leq f(j)$.
\item For all $i,j\in P$, $f(i)=f(j)$ $\Longrightarrow$ $i\equiv j$.
\end{enumerate}
The set of linear extensions of $P$ is denoted by $\Lin(P)$, the set of linear extensions from $P$ to $[k]$ is denoted by $\Lin^k(P)$.
\end{definition}

If $f$ is a linear extension of a packed double poset $P$ with\break $(P,\ll)=([n],\leq)$, a property that we can always assume up to a canonical isomorphism, we see it as a packed word $f(1)\ldots f(n)$. We denote the set of packed words of length $n$ by $PW(n)$. 

\medskip
Recall that an open set $X$ of a packed double poset $P$ is a  packed double  subposet of $P$ such that 
\begin{align*}
&\text{for all }i,j\in P,& i\leq_1j \mbox{  and }i\in X&\Longrightarrow j\in X.
\end{align*}

The following lemmas follow immediately from the definitions,
and hence their proof is omitted.

\begin{lemma}
Let $P$ be a packed double poset and $X$ an open set of $P$. Let $f_X:X\to [p]$ and $f_{P-X}:P-X\to [q]$ be two linear extensions. Then the map $f:P\to[p+q]$
defined by
\begin{align*}
f(i)&:=f_{P-X}(i)\ for\ i\in P-X,\\
f(j)&:=f_X(j)+q\ for\ j\in X,
\end{align*}
is a linear extension of $P$.
\end{lemma}

\begin{lemma}
Conversely, let $f$ be a linear extension of $P$, $f:P\to [k]$. For any $i\leq k$, $X:=f^{-1}(\{i+1,\dots,k\})$ is an open subset of $P$. Moreover, $f_{|P-X}:P-X\to [i]$ and $f_X:X\to [k-i]$, $f_X(x):=f(x)-i$ are linear extensions of $P-X$, respectively of $X$.
\end{lemma}

The two lemmas show that there is a bijection between triples\break $(X,f_X,f_{P-X})$ and pairs $(f,i)$. We get the following consequence.
\begin{corollary}\label{cor12}
The following map is a coalgebra morphism:
\[\phi:\left\{\begin{array}{rcl}
(\h_{PDP},\Delta)&\longrightarrow&(\WQSym,\Delta)\\
P&\longmapsto&\displaystyle \sum_{f\in \Lin(P)} f.
\end{array}\right.\]
\end{corollary}

\begin{lemma}
Let $(P,\leq_1^P,\leq_2^P)$ and $(Q,\leq_1^Q,\leq_2^Q)$ be two packed double posets. There is a canonical isomorphism
\[\Lin^n(PQ)\cong \coprod\limits_{p+q=n}(\Lin^p(P),\Lin^q(Q),\Sh(p,q)),\]
where $\Sh(p,q)$ stands for the set of $(p,q)$-shuffles, which,
by definition, are permutations of $[p+q]$ such that
\[\sigma^{-1}(1)<\dots<\sigma^{-1}(p),\ \sigma^{-1}(p+1)<\dots <\sigma^{-1}(p+q).
\]
\end{lemma}

\begin{proof}
Let us assume that $P=[l]$ and $Q=[k]$, so that $PQ\cong [l+k]$. By definition of linear extensions, if $f$ is a linear extension of $PQ$, $f(i)\not= f(j)$ for any $i\leq l$ and $j>l$, and there are no other relations between the restriction of $f$ to $[l]$ and to $\{l+1,\dots,l+k\}$. In particular, the restrictions of $f$ to $[l]$ and to $\{l+1,\dots, l+k\}$ have disjoint images and, composing them with the packing operator defines linear extensions of $P$ and $Q\cong \{l+1,\dots, l+k\}$. The lemma follows. 
\end{proof}

The preceding proof implies the following result.

\begin{proposition}\label{prop14}
The map $\phi$ defined by
\[\phi:\left\{\begin{array}{rcl}
(\h_{PDP},\cdot,\Delta)&\longrightarrow&(\WQSym,\shuffle,\Delta)\\
P&\longmapsto&\displaystyle \sum_{f\in \Lin(P)} f
\end{array}\right.\]
is a Hopf algebra morphism.
\end{proposition}

Notice that, since the product of two double posets is a double poset, the image of packed double posets by $\phi$ is a multiplicative family (actually a multiplicative basis, see Corollary~\ref{coriso} below) in $\WQSym$ for the product $\shuffle$. This is similar to what happens with the usual product $\qshuffle$, see the construction of multiplicative bases for $(\WQSym,\qshuffle)$ in \cite{Novelli}. The forthcoming results below on $(\WQSym,\qshuffle)$ and its relations to $\h_{PDP}$ and $(\WQSym,\shuffle)$ can actually be understood as a refinement of the results in that article.

\begin{proposition}
For all $f,g\in PW(n)$, we say that $f\leq g$ if:
\begin{enumerate}
\item For all $i,j\in [n]$, $i\geq j$ and $f(i)\leq f(j)$ $\Longrightarrow$ $g(i)\leq g(j)$.
\item For all $i,j\in [n]$, $g(i)=g(j)$ $\Longrightarrow$ $f(i)=f(j)$.
\end{enumerate}
Then $\leq$ is an order on $PW(n)$. Moreover, for all $f\in PW(n)$,
we have
\[\phi(P_f)=\sum_{f\leq g} g.\]
\end{proposition}

\begin{proof}The relation
$\leq$ is clearly transitive and reflexive. Let us assume that $f\leq g$ and $g\leq f$. By (2), for all $i,j\in [n]$,
$f(i)=f(j)$ if, and only if, $g(i)=g(j)$. Hence, putting $k=\max(f)=\max(g)$, there exists a unique permutation $\sigma\in \mathfrak{S}_k$
such that, for all $i\in [k]$, $f^{-1}(i)=g^{-1}(\sigma(i))$. By (1), if $i\geq j$, we have $g(i)\leq g(j)$ $\Longleftrightarrow$ $f(i)\leq f(j)$.
Hence,
\begin{align*}
\max f^{-1}(1)&=\max\{ i\in [n]\mid \text{for all }j\leq i, f(i)\leq f(j)\}\\
&=\max\{i\in [n]\mid \text{for all }j\leq i, g(i)\leq g(j)\}\\
&=\max g^{-1}(1)\\
&=\max g^{-1}(\sigma(1)),
\end{align*}
so $\sigma(1)=1$. Iterating this, one shows that $\sigma=\text{Id}_k$, so $f=g$: the relation $\leq$ is an order.
Let $f,g\in PW(n)$. Then we have
\begin{align*}
g\in \Lin(f)&\Longleftrightarrow\begin{cases}
\text{for all }i,j\in [n], \: i\geq j\mbox{ and }\\
\kern4cm f(i)\leq f(j)\Longrightarrow g(i)\leq g(j),\\
\text{for all }i,j\in [n], \: g(i)=g(j)\Longrightarrow f(i)=f(j),
\end{cases}\\
&\Longleftrightarrow f\leq g.
\end{align*}
So $\Lin(P_f)=\{g\in PW(n), f\leq g\}$. \end{proof}

\begin{corollary}\label{coriso}
%Christian: This is which $\phi$? The one from Proposition 15?
%   But then this would be redundant.
The map $\phi$ is a Hopf algebra isomorphism.
\end{corollary}

Here are the Hasse graphs of $(PW(2),\leq)$ and $(PW(3),\leq)$.
\[\xymatrix{&21\ar@{-}[ld]\ar@{-}[rd]&\\
12&&11}\]
\[\xymatrix{&&&321\ar@{-}[llld]\ar@{-}[rrrd]\ar@{-}[ld]\ar@{-}[rd]&&&\\
221\ar@{-}[dd]\ar@{-}[rrrd]&&312\ar@{-}|(.5)\hole[ld]\ar@{-}|(.66)\hole[d]&&231\ar@{-}|(.5)\hole[rd]\ar@{-}|(.66)\hole[d]&&211\ar@{-}[llld]\ar@{-}[dd]\\
&212&213\ar@{-}[lld]\ar@{-}[rd]&111&132\ar@{-}[rrd]\ar@{-}[ld]&121&\\
112&&&123&&&122}\]

\begin{remark} If $f$ and $g$ are two permutations, then
\begin{align*}
f\leq g&\Longleftrightarrow \text{for all }i,j\in [n],\: i>j\mbox{ and }f(i)<f(j)\Longrightarrow g(i)<g(j)\\
&\Longleftrightarrow \Inv(f)\subseteq \Inv(g),
\end{align*}
where $\Inv(f)$ stands for the set of inversions of $f$.
So the restriction of $\leq$ to $\mathfrak{S}_n$ is the Bruhat order.
\end{remark}

\begin{definition}
Let $P=(P,\leq_1,\leq_2)$ be a packed double poset. We assume that $(P,\ll)=([n],\leq)$. A weak linear extension of $P$ is a surjective map
$f:[n]\longrightarrow [k]$ such that:
\begin{enumerate}
\item For all $i,j\in [n]$, $i\leq_1 j$ $\Longrightarrow$ $f(i)\leq f(j)$.
\item For all $i,j\in [n]$, if $i\leq_1 j$ and $f(i)=f(j)$ $\Longrightarrow$ $i\equiv j$.
\end{enumerate}
The set of weak linear extensions of $P$ is denoted by $\WLin(P)$.
\end{definition}

In \cite{FM}, an order is defined on $PW(n)$: for all $f,g\in PW(n)$, $f\prec g$ if
\begin{enumerate}
\item For all $i,j\in [n]$, $g(i)\leq g(j)$ $\Longrightarrow$ $f(i)\leq f(j)$.
\item For all $i,j\in [n]$, $i<j$ and $g(i)>g(j)$ $\Longrightarrow$ $f(i)>f(j)$.
\end{enumerate}
It is proved that the following map is a Hopf algebra isomorphism:
\[\psi:\left\{\begin{array}{rcl}
(\WQSym,\shuffle,\Delta)&\longrightarrow&(\WQSym,\squplus,\Delta)\\
f&\longmapsto&\displaystyle \sum_{g\preceq f} g.
\end{array}\right.\]

\begin{lemma}
Let $P$ be a packed double poset. Then
\[\WLin(P)=\bigsqcup_{f\in \Lin(P)}\{g\in PW(n), g\preceq f\}.\]
\end{lemma}

\begin{proof} $\subseteq$. Let $g\in \WLin(P)$. For any $p\in [\max(g)]$, we put $P_p=P_{\mid g^{-1}(p)}$.
Then $P_p$ is a packed double poset, so there exists a unique packed word $f_p$ such that $P_p$ is isomorphic to $P_{f_p}$.
Let us define $g'$ by $g'(i)=f_p(i)+\max(f_1)+\dots+\max(f_{p-1})$ for any $i\in P_p$; $g'$ is a packed word.

We first show that $g'\in \Lin(p)$. Assume that $i\leq_1 j$. Then $g(i)\leq g(j)$. We claim that we also have $g'(i)\leq g'(j)$:
\begin{itemize}
\item If we do not have $i\equiv j$, then, as $g$ is a weak linear extension of $P$, $g(i)<g(j)$, which implies $g'(i)<g'(j)$.
\item If $g(i)=g(j)=p$, then $i\equiv j$ in $P_p$, so $f_p(i)=f_p(j)$ and finally $g'(i)=g'(j)$.
\end{itemize}
Now, if $g'(i)=g'(j)$, then $g(i)=g(j)=p$ and $f_p(i)=f_p(j)$, so $i\equiv j$ in $P_p$ and finally $i\equiv j$. Thus, we have indeed $g'\in \Lin(P)$.

We finally show that $g\preceq g'$. 
If $g'(i)\leq g'(j)$, then necessarily $g(i)\leq g(j)$. Let us assume $i<j$ and $g'(i)>g'(j)$. Then $g(i)\geq g(j)$. If $g(i)=g(j)=p$,
then $f_p(i)>f_p(j)$, so $j\leq_i 1$ and we do not have $i\equiv j$: this contradicts the fact that $g$ is a weak linear extension. So $g(i)>g(j)$, and finally $g\preceq g'$.

\medskip
$\supseteq$. Let $f\in \Lin(P)$ and $g\preceq f$. If $i \leq_1 j$, then $f(i)\leq f(j)$, so $g(i)\leq g(j)$.
If moreover $g(i)=g(j)$, as $i\geq j$ (because $i\leq_1 j$), we can not have $f(i)<f(j)$ as $g\preceq f$, so $f(i)=f(j)$ and $i\equiv j$.
So $g\in \WLin(P)$.

\medskip
\emph{Disjoint union}. Let $f,f'\in \Lin(P)$, such that there exists $g\in PW(n)$, $g\preceq f,f'$. Let us consider $i<j$.
If $f(i)>f(j)$, then $g(i)>g(j)$. If $f'(i)\leq f'(j)$, we would have $g(i)\leq g(j)$, which is a contradiction. Hence, by symmetry,
\begin{align*}
&\text{for all }i,j\in [n] \mbox{ such that }i<j,&f(i)>f(j)&\Longleftrightarrow f'(i)>f'(j),\\
&& f(i)\leq f(j)&\Longleftrightarrow f'(i)\leq f'(j).
\end{align*}
Let us assume that $i<j$ and $f(i)=f(j)$. Then $i\equiv j$, and $f'(i)\leq f'(j)$. As $P$ is isomorphic to $P_h$ for a certain packed word $h$,
$i<j$ and $h(i)=h(j)$, so $j\leq_1 i$ in $P$; consequently, $f'(j)\leq f'(i)$ and finally $f'(i)=f'(j)$. As a conclusion, we have
\begin{align*}
&\text{for all }i,j\in [n] \mbox{ such that }i<j,& f(i)>f(j)&\Longleftrightarrow f'(i)>f'(j),\\
&& f(i)=f(j)&\Longleftrightarrow f'(i)=f'(j),\\
 &&f(i)<f(j)&\Longleftrightarrow f'(i)<f'(j).
\end{align*}
So $P_f=P_{f'}$, which implies $f=f'$. \end{proof}

\begin{proposition}
The following map is a Hopf algebra isomorphism:
\[\phi'=\psi \circ \phi:\left\{\begin{array}{rcl}
\h_{PDP}&\longrightarrow&(\WQSym,\squplus,\Delta)\\
P_f&\longmapsto&\displaystyle\sum_{f\in \WLin(P)} f.
\end{array}\right.\]
\end{proposition}

\begin{proof} Indeed, for any packed word $f$, by the preceding lemma we have
\[\psi\circ \phi(P_f)=\sum_{f\in \Lin(P)}\sum_{g\preceq f} g=\sum_{f\in \WLin(P)}f.\]
By composition, $\phi'$ is an isomorphism.
\end{proof}

\begin{examples} We order the packed words of degree $2$  in the following way:
(11,12,21).
\begin{enumerate}
\item The matrices of $\phi$ and $\phi'$ from the basis $(P_f)_{f\in PW(2)}$ to the basis $PW(2)$ are given  by
\begin{align*}
&\begin{pmatrix}
1&0&0\\ 
0&1&0\\
1&1&1
\end{pmatrix},&&\begin{pmatrix}
1&1&0\\ 
0&1&0\\
1&1&1
\end{pmatrix},
\end{align*}
respectively.
\item The matrix of the pairing of $\h_{PDP}$ in the basis $(P_f)_{f\in PW(2)}$ is given by
\begin{align*}
&\begin{pmatrix}
1&1&0\\ 
1&2&1\\
0&1&0
\end{pmatrix}.
\end{align*}
\item Via $\phi$ and $\phi'$, $(\WQSym, \shuffle,\Delta)$ and $(\WQSym,\squplus,\Delta)$ inherit nondegenerate Hopf pairings. 
The matrices of these pairings in the basis $PW(2)$ are given by
\begin{align*}
&\begin{pmatrix}
1&0&0\\ 
0&0&1\\
0&1&0
\end{pmatrix},&
\begin{pmatrix}
1&-1&0\\ 
-1&1&1\\
0&1&0
\end{pmatrix},
\end{align*}
respectively.
\end{enumerate}
\end{examples}

\begin{thebibliography}{aa}

\bibitem{Benj}{\sc A. Benjes}, {\it Incompatible double posets and double order polytopes},
The Electronic Journal of Combinatorics {\bf 27}(1) (2020), Art.~P1.9, 13~pp.

\bibitem{chapoton2000algebres}{\sc F. Chapoton}, {\it
Alg\`ebres de {H}opf des permuto\`edres, associa\`edres et hypercubes},
Advances in Mathematics {\bf 150} (2000), 264--275.

\bibitem{CFS}{\sc T. Chappell, T. Friedl} and {\sc R. Sanyal},
{\it Two double poset polytopes}, SIAM Journal of Discrete Mathematics {\bf 31} (2017), 2378--2413.

\bibitem{foissy2013algebraic}{\sc L. Foissy},
{\it Algebraic structures on double and plane posets},
Journal of Algebraic Combinatorics,
{\bf 37}(1) (2013), 39--66.

\bibitem{foissy2013plane}{\sc L. Foissy},
{\it Plane posets, special posets, and permutations},
Advances in Mathematics,
{\bf 240} (2013), 24--60.

\bibitem{foissy2014deformation}{\sc L. Foissy},
{\it Deformation of the {H}opf algebra of plane posets},
European Journal of Combinatorics,
{\bf 38} (2014), 36--60.

\bibitem{FM}{\sc L. Foissy} and {\sc C. Malvenuto},
 {\it The {H}opf algebra of finite topologies and {$T$}-partitions},
Journal of Algebra,
{\bf 438} (2015), 130--169.
     
\bibitem{FMP2017}{\sc L. Foissy, C. Malvenuto} and {\sc F. Patras},
{\it A theory of pictures for quasi-posets},
Journal of Algebra, {\bf 477} (2017), 496--515.

\bibitem{foissy2}{\sc L. Foissy, F. Patras} and {\sc J.-Y. Thibon},
{\it Deformations of shuffles and quasi-shuffles},
  Annales de l'Institut Fourier,
{\bf 66}(1) (2016), 209--237.

\bibitem{GKT}{\sc I. G\'alvez, J. Kock} and {\sc A. Tonks},
{\it Decomposition spaces and restriction species},
International Mathematics Research Notices, (2018).

\bibitem{Grinberg}{\sc D. Grinberg}, {\it Double posets and the antipode of {QSym}},
S\'eminaire Lotharingien de Combinatoire, {\bf 78B} (2017), 12p.
     
\bibitem{hivert}{\sc F. Hivert}, {\it Combinatoire des fonctions quasi-sym\'etriques}, Ph.D. Thesis, 1999.

\bibitem{krob2000pseudo}{\sc D. Krob, M. Latapy, J.-C. Novelli, H. D. Phan} and {\sc S. Schwer},
{\it Pseudo-permutations I: First combinatorial and lattice properties}, 
Proceedings of the 13th Conference on Formal Power Series and Algebraic
Combinatorics, Tempe, Arizona, 2001, H.~Barcelo, ed., (2001).
 
\bibitem{MR2}{\sc C. Malvenuto} and {\sc Ch. Reutenauer}, {\it A self paired {H}opf algebra on double posets and a {L}ittlewood--{R}ichardson rule},
Journal of Combinatorial Theory. Series~A, {\bf 118}(4) (2011), 1322--1333.

\bibitem{Novelli}{\sc J.-C. Novelli} and {\sc J.-Y. Thibon}, {\it Polynomial realizations of some trialgebras},
Proceedings of the 18th Conference on Formal Power Series and Algebraic Combinatorics, San Diego, California, 2006.
 
\bibitem{stan}{\sc R. P. Stanley}, {\it Two poset polytopes},
Discrete Computational Geometry, {\bf 1}(1), (1986), 9--23.
 
\bibitem{zelevinsky1981generalization}{\sc A. V. Zelevinsky},
{\it A generalization of the {L}ittlewood--{R}ichardson rule and the {R}obinson--{S}chensted--{K}nuth correspondence},
Journal of Algebra, {\bf 69}(1) (1981), 82--94.

\end{thebibliography}

\end{document}
