\documentclass{fpsac}

%%%%%%%%%%%%%%%%%%%%%%
% Packages
%%%%%%%%%%%%%%%%%%%%%%

\usepackage{mathptmx}
\usepackage{graphicx}
\usepackage{bm}
\usepackage{pstricks}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{xypic}
\usepackage{latexsym}
\usepackage{rotating}
\usepackage{times}


%%%%%%%%%%%%%%%%%%%%%%
% Fl\^eches et traits
%%%%%%%%%%%%%%%%%%%%%%

\def\ra{\rightarrow}
\def\da{\downarrow}
\def\sw{\swarrow}
\def\se{\searrow}
\def\ne{\nearrow}
\def\ua{\uparrow}
\def\lra{\leftrightarrow}
\def\Lra{\Longrightarrow}
\def\ul#1{\underline{#1}}
%decalage de #1 points vers la gauche
\def\k#1{\kern -#1pt}


%matrice avec deux colonnes
\def\mcc#1{{\tiny\left(\k{5}\begin{array}{cc}#1\end{array}\k5\right)}}

%matrice avec trois col
\def\mccc#1{{\tiny\left(\k5\begin{array}{ccc}#1\end{array}\k5\right)}}

%matrice avec 4 col
\def\mcccc#1{{\tiny\left(\k5\begin{array}{cccc}#1\end{array}\k5\right)}}



%%%%%%%%%%%%%%%%%%%%%%
% Divers
%%%%%%%%%%%%%%%%%%%%%%

%\def\b{$\bullet\ $}
\def\mod{{\rm mod}}
%\def\quo{{\rm quo}}
%\def\irem{{\rm rem}}
%%\def\peb#1{\lfloor #1\rfloor}
%\def\peh#1{\lceil #1\rceil}
%\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.}
%\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}}
%\def\binomial#1#2{\left(\,\matrix{#1 \cr #2}\,\right)}
%\def\que{{\bf Question}}
%\def\rep{{\bf Reponse}}
%\def\pointir{\unskip . --- \ignorespaces}
%\def\nequiv{\equiv\hspace{-9pt}\slash\hspace{9pt}}
%\def\ra{\rightarrow}
%\def\lra{\leftrightarrow}
%\def\mup{MuPAD}
%\def\tr#1#2{{\rm trunc}(#1,#2)}

%%%%%%%%%%%%%%%%%%%%%%
% \'Enonc\'es
%%%%%%%%%%%%%%%%%%%%%%

\def\mref#1{{\footnotesize ({\ref{#1}})}}

\def\Proof{\medskip\noindent {\it Proof --- \ }}
\def\cqfd{\hfill $\Box$ \bigskip}


%%%%%%%%%%%%%%%%%%%%%%
% Miscellaneous
%%%%%%%%%%%%%%%%%%%%%%

%%% Letters et abbreviations %%%

\def\A{\mathcal{A}}
\def\U{\mathcal{U}}
\def\TBD{\times_{BD}}
\def\C{\mathbb{C}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\D{\mathcal{D}}
\def\H{\textrm{H}}
\def\DWS{\Delta_{WS}}
\def\DBS{\Delta_{BS}}
\def\E{{\sym E}}
\def\HWS{{\cal H}_{WS}}
\def\1H{\mathbf{1}_{\HWS}}
\def\L{\mathbb{L}}
\def\V{\mathbb{V}}
\def\X{\mathbb{X}}
\def\Y{\mathbb{Y}}
\def\Q{{\sym Q}}
\def\SG{{\mathfrak S}}
\def\al{\alpha}
\def\be{\beta}
\def\ga{\gamma}
\def\ep{\varepsilon}
\def\la{\lambda}
\def\Om{\Omega}
\def\om{\omega}
\def\MQSym{{\bf MQSym}}
\def\red{\stackrel{\small red}{\longrightarrow}}
\def\bd{\bar\Delta}
\def\pointir{\unskip . --- \ignorespaces}

%%% TBR %%%%

\def\inf{*}
\def\2m#1#2{\begin{bmatrix}#1\cr #2\end{bmatrix}}
\def\3m#1#2#3{\begin{bmatrix}#1\cr #2\cr #3\end{bmatrix}}

%%% Spaces %%%

\def\diag{\mathbf{diag}}
\def\ldiag{\mathbf{ldiag}}
\def\lldiag{\mathbf{lldiag}}
\def\DIAG{\mathbf{DIAG}}
\def\LDIAG{\mathbf{LDIAG}}
\def\MLD{\mathbf{MLDIAG}}
\def\MQS{\mathbf{MQSym}}
\def\SMQ{\mathbf{SMQSym}}
\def\End{\mathrm{End}}

\def\shuff#1#2{\mathbin{
      \hbox{\vbox{
        \hbox{\vrule
              \hskip#2
              \vrule height#1 width 0pt
               }%
        \hrule}%
             \vbox{
        \hbox{\vrule
              \hskip#2
              \vrule height#1 width 0pt
               \vrule }%
        \hrule}%
}}}
\def\shuffl{{\mathchoice{\shuff{7pt}{3.5pt}}%
                        {\shuff{6pt}{3pt}}%
                        {\shuff{4pt}{2pt}}%
                        {\shuff{3pt}{1.5pt}}}}%
\def\shuffle{\, \shuffl \,}

\def\ash{\, \underline{\shuffl} \, }



\def\setinterlineskip#1{\baselineskip=0pt
  \lineskip=#1 \lineskiplimit=\maxdimen}
\def\DessinsMatrix#1{\vcenter{\hbox{\makebox[1.3ex]{$\scriptstyle#1$}}}}
\def\GensMatrix#1{\vcenter{\halign{&$\DessinsMatrix{##}$\cr#1}}\egroup}



%% matrice de petite taille
\def\smallmatrice{%
  \bgroup
  \let\ =\omit
  \let\\=\cr
  \setinterlineskip{8.0pt}
  \GensMatrix}

\newcommand{\SMat}[1]{{\left[\smallmatrice{#1\\}\right]}}


%%%%%%%%%%%%%%%%%%%%%%
% Sauts
%%%%%%%%%%%%%%%%%%%%%%

\def\ss{\smallskip}
\def\ms{\medskip}
\def\bs{\bigskip}
%\def\small{\footnotesize}
%\def\b{$\Bullet\ $}
%\def\gcr{\hfill\cr}
%\def\hs{\hbox to 3mm{}}
%\def\hhs{\hbox to 5cm{}}
%\def\btu{\bigtriangleup}
%\def\Box{\triangle}

%%%%%%%%%%%%%%%%%%%%%%
% Operateurs et espaces
%%%%%%%%%%%%%%%%%%%%%%

%\def\scal#1#2{\langle #1 | #2 \rangle}
%\def\kd#1#2{\delta{#1#2}}
%\def\ncs#1#2{#1\langle\langle #2\rangle\rangle}
%\def\rncs#1#2{#1^{\rm rat}\langle\langle #2\rangle\rangle}
\def\ncp#1#2{#1\langle #2\rangle}
%\def\func#1#2{{\cal F}(#1,#2)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Letters et abbreviations %%%
\def\S{\mathfrak S}
\def\A{\mathcal{A}}
\def\U{\mathcal{U}}
\def\TBD{\times_{BD}}
\def\C{\mathbb{C}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\D{\mathcal{D}}
\def\saug{\uplus}
\parindent=0pt
\def\ra{\rightarrow}
\def\ul#1{\underline {#1}}
\def\pointir{\unskip . --- \ignorespaces}
\def\ss{\smallskip}

\newtheorem{example}{Example}[section]
\newtheorem{note}[example]{Note}
\newtheorem{theorem}[example]{Theorem}
\newtheorem{exercise}{Exercise}[section]
\newtheorem{corollary}[example]{Corollary}
\newtheorem{conjecture}[example]{Conjecture}
\newtheorem{definition}[example]{Definition}
\newtheorem{proposition}[example]{Proposition}
\newtheorem{algorithm}[example]{Algorithm}
\newtheorem{lemma}[example]{Lemma}
\def\mref#1{(\ref{#1})}
\def\Proof{\medskip\noindent {\it Proof --- \ }}
\def\cqfd{\hfill$\Box$ \bigskip}
%\def\cqfd{\hfill \\ \hbox{ }\hfill$\Box$ \bigskip}
%

%%% les alg\`ebres
%%% Diagrams
\def\LDiag{{\bf LDIAG}}


%% word symmetric and word quasisymmetric functions
\def\WQSym{{\bf WQSym}}
\def\WSym{{\bf WSym}}
% basis
\def\WQ{{\bf WQ}} % Base de WQSym
\def\W{{\bf W}} % base de WSym
\def\FQ{{\bf F}}% base multiplicative de WQSym
\def\F{{F}} % base multiplicatice de WSym

%% set matrix symmetric and quasisymmetric functions
\def\SMQSym{{\bf SMQSym}}
%\def\SMLSym{{\bf SMLSym}}
\def\SMRSym{{\bf SMRSym}}
\def\SMCSym{{\bf SMCSym}}
\def\SMSym{{\bf SMSym}}
%basis
\def\SMQ{{\bf SMQ}} %base de SMQSym
\def\SMR{{\bf SMR}} %base de SMRSym
\def\SMC{{\bf SMC}} %base de SMCSym
%\def\SML{{\bf CHANGER}} %base de SMCSym
\def\SM{{\bf SM}} %base de SMSym

%%  matrix symmetric and quasisymmetric functions
\def\MQSym{{\bf MQSym}}
\def\MRSym{{\bf MRSym}}
\def\MCSym{{\bf MCSym}}
\def\MSym{{\bf MSym}}
%basis
\def\MQ{{\bf MQ}} %base de MQSym
\def\MR{{\bf MR}} %base de MLSym
\def\MC{{\bf MC}} %base de MRSym
\def\M{{\bf M}} %base de MSym


%% operations
\def\ssh{\Cup} % shuffle
\def\std{{\rm std}}% standardization
%% convertions
\def\Mat{{\rm Mat}} % To matrix
\def\mset{{\rm multiset}}% to multiset
\def\word{{\rm word}}% to word
\def\biword{{\rm biword}}% to biword
\def\packed{{\rm packed}}% packed word
\def\bipacked{{\rm bipacked}}% bipacked word
\def\mup{{\rm mup}}% maximal unpacked
\def\scomp{{\rm setcomp}}% to set composition
\def\comp{{\rm comp}}% to composition

\def\st{\scriptstyle}
\def\es{\emptyset}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Hopf algebras of diagrams} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\author{G. H. E. Duchamp$^{a}$, J-G. Luque$^{b}$, J-C. Novelli$^{b}$, C.
%Tollu$^{a}$, F. Toumazet$^{a}$\\
%$^a$ Institut Galil\'ee, LIPN, CNRS UMR 7030\\
%99 Av. J.-B. Clement, F-93430 Villetaneuse, France\\
%e-mail: {\tt ghed,ct,ft@lipn.univ-paris13.fr}\vspace{2mm}\\
%$^b$ IGM, Universit\'e de Marne-la-Vall\'ee,
%5, Boulevard Descartes, Champs-sur-Marne \\
%77454 Marne-la-Vall\'ee cedex 2, France\\
%e-mail: {\tt luque,novelli@univ-mlv.fr}
%}

\author{G. H. E. Duchamp$^{a}$, J-G. Luque$^{b}$, J-C. Novelli$^{b}$, C.
Tollu$^{a}$, F. Toumazet$^{a}$}

\address[a] {Institut Galil\'ee, LIPN, Universit\'e de Paris~13 et CNRS, UMR 7030\\
99, avenue J.-B. Cl\'ement, 93430 Villetaneuse, France}

\address[b] {Institut Gaspard Monge, Universit\'e de Marne-la-Vall\'ee \\
5, boulevard Descartes, Champs-sur-Marne \\77454 Marne-la-Vall\'ee Cedex 2 \\
France}

\email[G\'erard Henry Edmond Duchamp]{ghed@lipn.univ-paris13.fr}
\email[Jean-Gabriel Luque]{luque@univ-mlv.fr}
\email[Jean-Christophe Novelli]{novelli@univ-mlv.fr}
\email[Christophe Tollu]{ct@lipn.univ-paris13.fr}
\email[Fr\'ed\'eric Toumazet]{ft@lipn.univ-paris13.fr}
\date{}

\keywords{Hopf algebras, Bi-partite graphs, dendriform structures}

\subjclass[200]{Primary 05E99, Secondary 16W30, 18D50, 81T18}


\begin{document}

\begin{abstract}
We investigate several Hopf algebras of diagrams related to the Quantum
Field Theory of Partitions and whose product comes from $\WSym$ or $\WQSym$, 
the algebras of word symmetric or quasi-symmetric functions. Bases of these algebras are indexed either by bipartite graphs
(labelled or unlabelled) or by packed matrices (with integer or set
coefficients).
Realizations on bi-words are exhibited, and it is shown how these algebras fit
well into a commutative diagram. Hopf deformations and dendriform structures
are also considered for some algebras in the picture.

\begin{resume}
Nous \'etudions plusieurs alg\`ebres de Hopf de diagrammes li\'ees \`a la
Th\'eorie Quantique des Champs des Partitions et dont le produit provient de
$\WSym$ et $\WQSym$. Ces alg\`ebres ont des bases index\'ees \`a des graphs
bipartis (\'etiquet\'es ou non) ou \`a des matrices tass\'ees (\`a
c{\oe}fficients entiers ou ensemblistes). On donne des r\'ealisations sur des
bi-mots et on montre comment ces alg\`ebres s'int\`egrent dans un diagramme
commutatif. Pour certaines d'entre elles, on \'etablit des structures
dendriformes et l'existence de d\'eformations pr\'eservant la structure de
Hopf.
\end{resume}
\end{abstract}

\maketitle

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

\bs The purpose of the present paper is twofold. First, we want to tighten the
links between a body of Hopf algebras related to physics and the realm of
noncommutative symmetric functions, although the latter domains are no longer
disconnected \cite{Foissy, GOF4, NY}. Second, we aim at providing examples
of combinatorial shifting (a generic way of deforming algebras) and expounding
how $\MQS$ could be considered a construction scheme including its first
appearance with integers \cite{DHT} as a special case.

Our paper is the continuation of \cite{DLPT}, as we go deeper into 
the connections between combinatorial Hopf algebras and the Feynman
diagrams of a special Field Theory introduced by Bender, Brody and
Meister \cite{BBM}. These Feynman diagrams arose in the expansion of
 \begin{equation}
 G(z)=\left.\exp\left\{\sum_{n\geq 1}{L_n \over n!}\left(z{\partial\over\partial
 x}\right)^n\right\}\exp\left\{\sum_{m\geq1}V_m{x^m\over
 m!}\right\}\right|_{x=0}
 \end{equation}
and are bipartite finite graphs with no isolated vertex, and edges weighted
with integers. They are in bijective correspondence with packed matrices of
integers up to a permutation of the columns and a permutation of the rows. The
algorithm constructing the matrix from the associated diagram uses as an
intermediate structure a particular packed matrix whose entries are sets. Such
set matrices appear when one computes the internal product in
$\WSym$~\cite{SR} and in $\WQSym$~\cite{Hiv,NT}, then isomorphic to the
Solomon-Tits algebra. In this context, it becomes natural to investigate
Hopf algebras of (set) packed matrices whose product comes from $\WSym$ or
$\WQSym$.

The paper is organized as follows. In Section \ref{Phys}, the connection
between the Quantum Field Theory of Partitions and a three-parameter
deformation of the Hopf algebra \LDiag\  of labelled diagrams is explained. We
introduce the shifting principle (Subsection \ref{shift}) and give two
illustrations. The first one enables to see $\LDiag$ as the shifted version of
an algebra of unlabelled diagrams.
The second one (Subsection \ref{MQS_k}) explains how to carry over some
constructions from algebras of integer matrices to algebras of set
matrices.\\
In Section \ref{SMQ}, we investigate eight Hopf algebras of
matrices related to labelled or unlabelled diagrams. In particular, we
exhibit realizations on biwords and show how some of these are
dendriform bialgebras.
%One gives realization on bi-words and a commutative
%diagram relying the eight algebras. In Subsection \ref{trid}, one
%investigate the dendriform structures of some these algebras. To end
%with (Subsection \ref{LDbw}, one gives a bi-words realization of the
%two parameters deformation $\LDiag(q_c,q_s)$.


{\sc Acknowledgements}.
The first author would like to thank Bodo Lass for an illuminating
seminar talk on the algebraic treatment of bipartite graphs. He is also
greatly indebted to Karol Penson for clearing up the physical origin of the
diagrams.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Hopf algebras coming from physics}\label{Phys}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Algebras of diagrams}

Many computations carried out by physicists reduce to the `product formula', a
bilinear coupling between two Taylor expandable functions, introduced by 
C.M. Bender, D.C. Brody, and B.K. Meister in their celebrated 
{\it Quantum field theory of partitions} (henceforth referred to as QFTP)
\cite{BBM}. For an example of such a computation derived from a
partition function linked to the Free Boson Gas model,
see~\cite{GOF9}.

To make the story short, the last expansion of the formula involves
a summation over all diagrams of a certain type \cite{BBM,OPG} a
labelled version of which is described below. These diagrams
are bipartite graphs with multiple edges. It is in order to
show that every (combinatorial) sequence of integers can be
represented by Feynman diagrams subjected to suited rules that
Bender, Brody and Meister \cite{BBM} introduced QFTP as a toy model.

The case when the expansions of the two functions occurring in the product
formula have constant term 1 is of special interest. The functions can
then be presented as exponentials which can be regarded as "free" through the
classical Bell polynomials expansion \cite{GOF4} or as coming from the
integration of a Frechet one-parameter group of operators \cite{OPG}. Working
out the formal case, one sees that the coupling results in a summation without
multiplicity of a certain kind of labelled bipartite graphs which are
equivalent, as a data structure, to pairs of unordered partitions of the same
set \{1,2,...,n\}. The sum can be reduced to a sum of topologically inequivalent
diagrams (a monoidal basis of $\DIAG$), at the cost of introducing
multiplicities.
Theses graphs, which can be considered as the Feynman diagrams of the QFTP,
generate a Hopf algebra compatible with the product and co-addition on the
multipliers. Interpreting $\DIAG$ as the Hopf homomorphic image of its planar
counterpart, $\LDIAG$, gives access to the noncommutative world and to
deformations: the product is deformed by taking into account, through two
variables, the number of crossings of edges involved in the superposition or
the transposition of two vertices, the coproduct is obtained by interpolating.
This gives the final picture of~\cite{GOF9}.

Labelled diagrams can be identified with their weight functions which
are mappings $\om : \N^+\times\N^+\ra \N$ such that the supporting
subgraph
\begin{equation}
\Gamma_\om=\{(i,j)\in \N^+\times\N^+\ |\ w(i,j)\not=0\}
\end{equation}
has projections \emph{i.e.}, $pr_1(\Gamma_\om)=[1,p];\
pr_2(\Gamma_\om)=[1,q]$ for some $p,q\in \N^+$.

\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.2]{fig12.eps}
\caption{\label{labelled} A labelled diagram of shape $3\times 4$.}
\end{center}
\end{figure}

Let $\ldiag$ denote the set of labelled diagrams. With any element $d$ of
$\ldiag$, one can associate the monomial $\L^{\al(d)}\V^{\be(d)}$, called its multiplier, where
$\al(d)$ (resp. $\be(d)$) is the ``white spot type'' (resp. the ``black spot
type'') \emph{i.e.}, the multi-index $(\al_i)_{i\in \N^+}$ (resp.
$(\be_i)_{i\in \N^+}$) such that $\al_i$ (resp.  $\be_i$) is the number of
white spots (resp. black spots) of degree $i$.
For example, the multiplier of the labelled diagram of Figure~\ref{labelled} is
$\L^{(0,0,2,0,1)} \V^{(1,1,1,0,1)}$.

One can endow $\ldiag$ with an algebra structure denoted by $\LDIAG$
where the sum is the formal sum and the product is the shifted concatenation of diagrams,
{\em i.e.} consists in juxtaposing the second diagram to the right of the first one
and then adding to the labels of the black spots (resp. of the white spots) of
the second diagram the number of black spots (resp. of white spots) of the
first diagram. Then the application sending a diagram to its multiplier is an
algebra homomorphism.

Moreover, the black spots (resp. white spots) of diagram $d$ can be permuted
without changing the monomial $\L^{\al(d)}\V^{\be(d)}$. The classes of
labelled diagrams up to this equivalence relation (permutations of white -- or
black -- spots among themselves) are naturally represented by unlabelled
diagrams. The set of unlabelled diagrams will be henceforth denoted by
$\diag$.

%\begin{figure}[ht]
%\begin{center}
%\includegraphics[scale=0.4]{fig22.eps}
%\caption{\label{nonetiq}Equivalent labelled diagrams.}
%\end{center}
%\end{figure}
%
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.4]{fig22.eps}
\begin{pspicture}(-5,1)(233.95,0)
\rput(-0.4,3.4){1}\rput(.5,3.4){2}\rput(1.35,3.4){3}
\rput(2.7,3.4){1}\rput(3.5,3.4){2}\rput(4.4,3.4){3}
\rput(5.2,3.4){1}\rput(6.1,3.4){2}\rput(7.0,3.4){3}
 
\rput(0,1){1}\rput(0.9,1){2}
 \rput(3.1,1){1}\rput(4,1){2}
 \rput(5.6,1){1}\rput(6.7,1){2}
\end{pspicture}
\end{center}
\caption{\label{nonetiq}Equivalent labelled diagrams.}
\end{figure}

The set $\diag$ can also be endowed with an algebra structure, denoted by
$\DIAG$, \emph{e.g.} as the quotient of $\LDIAG$ by the equivalence classes
of labelled diagrams. In $\DIAG$, the product of $d_1$ by $d_2$ is basic
concatenation, {\em i.e.} simply consists in juxtaposing %types 
$d_2$ to the right of $d_1$ \cite{GOF4}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Shifted algebras and applications}
\label{shift}

A three-parameter deformation of $\LDIAG$, $\LDIAG(q_c,q_s,t)$ has been
recently constructed, which specializes to both $\LDIAG$ ($q_c=q_s=t=0$) and
$\MQS$ ($q_c=q_s=t=1$). This construction involves a deformation of the
algebra structure, which can be seen as a particular case of the rather
general principle of \emph{shifting}. This principle will be further
exemplified in the sequel of the present paper.

%This principle rests on the following lemma.

\begin{lemma} (Shifting lemma.)\\
Let $\A=\oplus_{\al\in M} \A_\al$ be an algebra graded (as a vector space) on
a commutative monoid $(M,+)$.
Let $s\ :\ (M,+)\mapsto (\End_{alg}(\A),\circ)$ be an homomorphism such that
the modified law, given by
\begin{equation}
x *_s y:=x\ s_{\al}(y)  \text{ for all } x\in\A_\al,\ y\in \A
\end{equation}
is $M$-graded. Then, if $\A$ is associative, so is the deformed law $*_s$.
\end{lemma}

Such a procedure, whenever possible, will be called the \emph{shifting of $\A$
by the shift $s$}. We now recall the construction of $\LDIAG(q_c,q_s)$ as
the shifting of another algebra of diagrams.

\ss
Let $M=\N^{(\N^+)}$ be the additive monoid of multidegrees and $M^+=M-\{0\}$
the associated semigroup. A labelled diagram $d$ with $p$ white spots and $q$
black spots can be encoded by a word $W(d)\in (M^+)^*$ as
\begin{equation}
W(d)=\al_1\al_2\cdots \al_q,
\end{equation}
where, for all $i\leq p$, the $i$-th letter of $\al_j$ is the number
of edges joining the black spot $j$ and the white spot $i$
(see Figure~\ref{diag2mot}).  \vspace{1cm}
\begin{figure}[h]
%\label{}
\begin{center}
\input{coding1}
\end{center}
\begin{flushleft}
The edges adjacent to the blackspots correspond successively to the
multidegrees $(2)$ (two edges to the first white spot), $(1,3,1)$
(one edge to the first and third white spots and three edges to the second
one), $(0,1,2)$ and $(0,1)$.
Thus the code is $W(d)=(2)(1,3,1)(0,1,2)(0,1)$.\end{flushleft}
\caption{\label{diag2mot}Coding a diagram with a word of multidegrees. }
\end{figure}
\\ \\Let $k$ be a ring, one can skew the product in $\ncp{k}{M^+}$, counting crossings and
superpositions as for $\LDIAG$.

\begin{proposition}
Let $k$ be a ring, $q_c,q_s\in k$, and consider the deformed graded law on $\ncp{k}{M^+}$ defined by

\begin{equation}
\left\{
\begin{array}{rcl}
1_{(M^+)^*}*w & = & w*1_{(M^+)^*}=w,\\[5pt]
\al u * \be v & = & \al(u*\be v)+ q_c^{|\al u||\be|} \be (\al u *v) +
q_s^{|\al||\be|}q_c^{|u||\be|} (\al+\be)(u*v),
\end{array}
\right.
\end{equation}
where $\alpha,\beta\in M^+$, $u,v\in(M^+)^*$, the weight
$|\alpha|$ of multidegree $\alpha$ is just the sum of its
coordinates and the weight $|u|$ of the word
$u=\alpha_1\cdots\alpha_t$ is $|u|=\sum_{i=1}^t|\alpha_i|$.


This product is associative.
\end{proposition}

The algebra $(k\langle M^+\rangle,+,*)$ is denoted by $\MLD (q_c,q_s)$. In the shifted version, 
the product amounts to performing all superpositions of black spots and/or crossings of edges, weighting them 
with the corresponding value $q_s$ or $q_c$, powered by the number of crossings of edges. 

This construction is reminiscent, up to the deformations, of Hoffman's~\cite{Ho} and its variants~\cite{Ca,FG}, 
and also of an older one, the infiltration product in computer science~\cite{Oc,DFLL}.

\ss The shift going from $\MLD(q_c,q_s)$ to itself is the following.
Let $\al_1\al_2\cdots \al_p\in (M^+)^*$ and $n\in \N$. One sets
\begin{equation}
s_n(\al_1\al_2\cdots \al_p):=(0^n\al_1)(0^n\al_2)\cdots (0^n\al_p)
\end{equation}
where $0^n\al$ is the insertion of $n$ zeroes on the left of $\al$.
Note that $n\mapsto s_n$ is a homomorphism of monoids $(\N,+)\ra
\End_{alg}\big(\MLD (q_c,q_s)\big)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Another application of the shifting principle}
\label{MQS_k}
 The Hopf operations of $\MQS$ as described
in~\cite{DHT} do not depend on the fact that the entries of the
matrices are integers.

For a pointed set $(X,x_0)$ (\emph{i.e.}, $x_0\in X$), let us denote by
$\MQS_k(X,x_0)$ the $k$-vector space spanned by rectangular matrices with
entries in $X$ with no line or column filled with $x_0$ (which plays now the
r\^ole of zero) and the product, coproduct, unit and counit as in~\cite{DHT}.
%
It is clear that $\MQS_k(X,x_0)$ is a Hopf algebra and that the correspondence
$(X,x_0)\mapsto \MQS_k(X,x_0)$ is a functor from the category of pointed sets
(endowed with the strict arrows, that is, the mappings $\phi\ :\ (X,x_0)\ra
(Y,y_0)$ such that $\phi(x_0)=y_0$ and $\phi(X-\{x_0\})\subset Y-\{y_0\}$) to
the category of $k$-Hopf algebras.
In the particular case when $X=2^{(N^+)}$, that is, finite subsets of $\N^+$,
and $x_0=\emptyset$, one can define a shift by a translation of the elements.
More precisely, for $F\in 2^{(N^+)}$ and $M$ a $p\times q$ matrix
with coefficients in $2^{(N^+)}$, one sets
%
\begin{equation}
s_n(F)=\{x+n\}_{x\in F}\ ,\ s_n(M)
   =\big(s_n(M[i,j])\big)_{\genfrac{}{}{0pt}{}{1\leq i\leq p}{1\leq j\leq q}}
\,.
\end{equation}

One can check that the $s_n$ define a shift on $\MQS_k(2^{(N^+)},\emptyset)$
for the grading given by
%
\begin{equation}
\MQS_k(2^{(N^+)},\emptyset)_n=
\textrm{span of the matrices whose maximum number in the entries is }n.
\end{equation}

For example, the vector space generated by the packed matrices whose
entries partition the set $\{1,2,\cdots n\}$ is closed by the product. This
is the algebra $\SMQSym$. We shall soon see that this corresponds to labelling
also the edges of a labelled diagram with numbers from 1 to $k$.

\input{hopf.tex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%  BIBLIOGRAPHIE !!! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\footnotesize
\begin{thebibliography}{aa}
%
\bibitem{BBM} {\sc C. M. Bender, D. C. Brody}, and {\sc B. K. Meister},
{\it Quantum field theory of partitions}, J. Math. Phys. {\bf 40} (1999) 3239
%
\bibitem{Ca} {\sc P. Cartier}, {\it Fonctions polylogarithmes,
nombres polyz\^etas et groupes pro-unipotents}, S\'eminaire Bourbaki, Mars 2001, 53\`eme ann\'ee, 2000-2001, {\bf 885}
%
%\bibitem{Co1} {\sc L. Comtet}, Analyse Combinatoire, PUF, Tome 1 (1970)
%
%\bibitem{Co2} {\sc L. Comtet}, Analyse Combinatoire, PUF, Tome 2 (1970)
%
%\bibitem{DKPTT} {\sc G. H. E. Duchamp, G. Koshevoy, K. A. Penson, C. Tollu, F. Toumazet}, {\it Geometric combinatorial twisting and shifting}, S\'eminaire Lotharingien (in preparation).
%
%\bibitem{GOF0} {\sc G. H. E. Duchamp, A.I. Solomon, P. Blasiak, A. Horzela and K.A. Penson}, {\it The Hopf Algebra of Feynman-like Diagrams : Twisting and Shifting.} (in preparation)
%
%\bibitem{Fo1} {\sc L. Foissy}, {\it Isomorphisme entre l'alg\`ebre des fonctions quasi-sym\'etriques libres et une alg\`ebre de Hopf des arbres enracin\'es d\'ecor\'es plans}, personal communication.
%
%\bibitem{Fo2} {\sc L. Foissy}, {\it Les alg\`ebres de Hopf des arbres enracin\'es decor\'es}, PhD Memoir, Reims University (2002).
%
\bibitem{DLPT} {\sc G.H.E. Duchamp, J.-G. Luque, K.A. Penson,} and {\sc C.
Tollu}, {\it Free quasi-symmetric functions, product actions and
quantum field theory of partition}, Proc. FPSAC/SFCA 2005, Messina, Italy. ArXiv: {\tt cs.SC/0412061}


\bibitem{OPG} {\sc G. Duchamp, A.I. Solomon, K.A. Penson, A. Horzela},
and {\sc P. Blasiak}, {\it One-parameter groups and combinatorial
physics}, Proceedings of the Symposium Third International Workshop
on Contemporary Problems in Mathematical Physics (COPROMAPH3)
(Porto-Novo, Benin, Nov. 2003),  J. Govaerts, M. N. Hounkonnou and
A. Z. Msezane (eds.), p.436 (World Scientific Publishing 2004).
ArXiv: {\tt quant-ph/04011262}
%
\bibitem{GOF4} {\sc G. H. E. Duchamp, P. Blasiak, A. Horzela, K. A. Penson},
and {\sc A. I. Solomon},
{\it Feynman graphs and related Hopf algebras}, J. Phys:
Conference Series (30) (2006) 107, Proc of SSPCM'05, Myczkowce, Poland.
ArXiv: {\tt cs.SC/0510041}
%
\bibitem{DFLL} {\sc G. Duchamp , M. Flouret, \'E. Laugerotte.}, and
{\sc J.-G. Luque},
{\it Direct and dual laws for automata with multiplicities}, Theoret. Comp. Sci.
{\bf 267}, 105-120 (2001).
%
%\bibitem{GOF6} {\sc A. Horzela, P. Blasiak, G. Duchamp, K. A. Penson
%and A.I. Solomon}, {\it A product formula and combinatorial field theory},
%Proceedings of the XI International Conference on Symmetry Methods
%in Physics (SYMPHYS-11) (Prague, Czech Republic, June 2004), C. Burdik, O. Navratil, and S. Posta (eds.) (JINR Publishers, Dubna). arXiv:{\tt quant-ph/0409152}
%
%\bibitem{GOF7} {\sc P. Blasiak, A. Horzela, K. A. Penson, G. H. E. Duchamp,
%A.I. Solomon}, {\it Boson normal ordering via substitutions and Sheffer-Type Polynomials},
%Phys. Lett. A {\bf 338} (2005) 108
%
%\bibitem{GOF8} {\sc P. Blasiak,  K. A. Penson, A.I. Solomon,
%A. Horzela, G. H. E. Duchamp},
%{\it Some useful formula for bosonic operators}, J. Math. Phys.
% {\bf 46} 052110 (2005).
%
\bibitem{DHT} {\sc G. Duchamp, F. Hivert,} and {\sc J.-Y. Thibon}, {\it Non commutative
functions VI: Free quasi-symmetric functions and related algebras},
International Journal of Algebra and Computation {\bf 12}(5) (2002). ArXiv: {\tt math.CO/0105065}

\bibitem{NY} {\sc G.H.E. Duchamp, A.I. Solomon, P. Blasiak, K.A. Penson,} and {\sc A. Horzela}, {\it A 
multipurpose Hopf deformation of the algebra Feynman-like diagrams}, Group26, New York, 2006. ArXiv: {\tt cs.OH/0609107}
%
\bibitem{FG} {\sc K. Ebrahimi-Fard} and {\sc L. Guo},
{\it Mixable shuffles, quasi-shuffles and Hopf algebras}, J. Algebr. Comb. {\bf 24}
(2006) 83–101.

\bibitem{Foissy} {\sc L. Foissy}, {\it Bidendriform bialgebras, trees, and free quasisymmetric 
functions}, to appear in J. Pure and Applied Algebra. ArXiv: math.RA/0505207
%
\bibitem{Hiv} {\sc F. Hivert},
{\it Combinatoire des fonctions quasi-sym\'etriques},
Th\`ese de Doctorat, Marne-La-Vall\'ee, 1999.
%
\bibitem{Ho} {\sc M. E. Hoffman}, {\it The Hopf algebra structure of multiple
harmonic sums},  Nuclear Physics B (Proceedings Supplement) {\bf 135} (2004),
215-219.
%
\bibitem{NT}{\sc J.-C Novelli} and {\sc J.-Y. Thibon},
{\it Polynomial realizations of some trialgebras},
Proc. FPSAC/SFCA 2006, San Diego.
%
\bibitem{Oc} {\sc P. Ochsenschl\"ager},
{\it Binomialkoeffitzenten und Shuffle-Zahlen}, Technischer Bericht,
Fachbereich Informatik, T. H. Darmstadt (1981).
%
\bibitem{SR} {\sc M. Rosas} and {\sc B. Sagan},
{\it Symmetric functions in noncommuting variables},
Trans. Amer. Math. Soc. {\bf 358} (2006) 215-232. 
%
\bibitem{Slo} {\sc N.J.A. Sloane},
{\it The On-Line Encyclopedia of Integer Sequences},\\
\verb+http://www.research.att.com/~njas/sequences/+
%
\bibitem{GOF9} {\sc A.I. Solomon, G.H.E. Duchamp, P. Blasiak, A. Horzela}, and
{\sc K. A. Penson},
{\it Hopf Algebra Structure of a model Quantum Field Theory}, Group26, New York, 2006. 
%
\end{thebibliography}
\end{document}

