\documentclass[12pt]{iopart}

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

\usepackage[dvips]{epsfig}
\usepackage{xy}
\xyoption{all}
\usepackage{iopams}
\usepackage{amscd}

%%%%%%%%%%%%%%%%%%%%%%
% Jumps
%%%%%%%%%%%%%%%%%%%%%%

\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}
\def\mhs{\hbox to 1cm{}}

%%%%%%%%%%%%%%%%%%%%%%
% Arrows and lines
%%%%%%%%%%%%%%%%%%%%%%

\def\ra{\rightarrow}
\def\da{\downarrow}
\def\sw{\swarrow}
\def\se{\searrow}
\def\ne{\nearrow}
\def\lra{\leftrightarrow}
\def\Lra{\Longrightarrow}
\def\ul#1{\underline{#1}}
%%%%%%%%%%%%%%%%%%%%%%
% Environment
%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\ep}{\rule{3mm}{3mm}}
\newcommand{\ed}{\hbox{\rlap{$\sqcap$}$\sqcup$}}
\newtheorem{rmk}{Remark}[section]
\newenvironment{demo}{{\em Proof.\mbox{}}}{{$\Box$}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\eenu}{\end{enumerate}}
\newtheorem{Lemma}{Lemma}[section]
\newtheorem{definition}{Definition}[section] 
\newtheorem{example}{Example}[section]  
\newenvironment{Example}{\begin{example}\rm}{\end{example}}
\newtheorem{prop}{Proposition}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{theo}{Theorem}[section]

%%%% Discusive markers %%%%

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

\newenvironment{Proof}{\smallskip\noindent{\bf Proof.}}                      
{{\hfill\ed}\medskip}

%%%%%% Signs %%%%%%%%%%

\def\SG{\mathfrak{S}}
\def\pointir{\unskip . --- \ignorespaces}

%%%%%%%%%%%%%%%%%%%%

\begin{document}
\title[]{The Hopf Algebra of Feynman-like Diagrams}

\author{{\tt order to be discussed} G H E Duchamp$^{d}$, P Blasiak$^{a,b}$, A 
Horzela$^{b}$, K A Penson$^{a}$ and A I Solomon$^{a,e}$
\vspace{2mm}}
\address{$^a$ Laboratoire de Physique Th\'eorique de la Mati\`{e}re 
Condens\'{e}e\\
Universit\'e Pierre et Marie Curie, CNRS UMR 7600\\Tour 24 - 2i\`{e}me \'et., 4 
pl. Jussieu, F 75252 Paris Cedex 05, France
\vspace{2mm}}
\address{$^b$ H. Niewodnicza\'nski Institute ofNuclear Physics, Polish Academy 
of Sciences\\ul. Eliasza-Radzikowskiego 152,  PL 31342 Krak\'ow, Poland
\vspace{2mm}}
\address{$^d$ Institut Galil\'ee, LIPN, CNRS UMR 7030\linebreak99 Av. J.-B. 
Clement, F-93430 Villetaneuse, France
\vspace{2mm}}
\address{$^e$ The Open University, Physics and Astronomy Department\\Milton 
Keynes MK7 6AA, United Kingdom
\vspace{2mm}}
\eads{\linebreak \mailto{ghed@lipn-univ.paris13.fr}, 
\mailto{pawel.blasiak@ifj.edu.pl}, \mailto{andrzej.horzela@ifj.edu.pl},
\mailto{a.i.solomon@open.ac.uk}, \mailto{penson@lptl.jussieu.fr}}

%\pacs{}\begin{abstract}\\...\end{abstract}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
It is in the purpose of proving that any sequence of numbers could be produced by 
special classes of Feynman-like diagrams that Bender, Brody and Meister 
(see BBM and also our papers) introduced a special Field Theory (Field Theory of Partitions)
based on the following \emph{product formula}
\begin{eqnarray}
\left.F\left(z\frac{d}{dx}\right)G(x)\right|_{x=0}=\mathcal{H}(F,G).
\end{eqnarray}
This product corresponds to the Hadamard product of the EGF's (see ...). 
The case when $F(0)=G(0)=1$ is of special interest and, here, $F$ and $G$ can be seen as
specializations of free exponentials, that is
\begin{eqnarray}
F(z)=\exp\left(\sum_{n=1}^\infty L_n\frac{z^n}{n!}\right),\ \ \ \ \ \ \ 
G(z)=\exp\left(\sum_{n=1}^\infty V_n\frac{z^n}{n!}\right).
\end{eqnarray}
It is well known that, individually, $F$ and $G$ develop according to Bell polynomials
where coefficients are the number of set partitions of a certain type 
$\alpha=1^{\alpha_1} 2^{\alpha_2} ... k^{\alpha_k}$
\begin{eqnarray}
numpart(\alpha)=\frac{|\alpha|!}{\alpha_1!\alpha_2!...\alpha_k!1!2!...3!}
\end{eqnarray}
(see Comtet, Stanley) hence, in multiindex notation
\begin{eqnarray}
F(z)=\sum_{n=0}^\infty\frac{z^n}{n!}\sum_{|\alpha|=n}numpart(\alpha)\mathbb{L}^\alpha\\
G(z)=\sum_{n=0}^\infty\frac{z^n}{n!}\sum_{|\beta|=n}numpart(\beta)\mathbb{V}^\beta,
\end{eqnarray}
and the product formula reads
\begin{eqnarray}\label{H}
\mathcal{H}(F,G)=\sum_{n=0}^\infty\frac{z^n}{n!}\sum_{|\alpha|=|\beta|}numpart(\alpha)numpart(\alpha)\mathbb{L}^\alpha \mathbb{V}^\beta.
\end{eqnarray}
This is here that the Feynman-like diagrams of this theory and their structure arise.

To every pair $(P_1,P_2)$ of set partitions one can associate an incidence matrix. 
For example, with $P_1=\{1,3\},\{5\},\{2,4,6\}$ and $P_2=\{1,2\},\{3,4\},\{5,6\}$ one gets

\begin{table}[h]
	\centering
		\begin{tabular}{cccc}
			&1,3&5&2,4,6\\
1,2&1&0&1\\
3,5&1&1&0\\
4,6&0&0&2
		\end{tabular}
\end{table}
which has the representation by the Feynman-like diagram as in Fig.(\ref{Fig0}) which are finite
biparate graphs with multiplicities in $\mathbb{N}_+=\{1,2,3,...\}$.

\begin{figure}
\hspace{1cm}
\begin{center}
\resizebox{7cm}{!}{\includegraphics{Fig0.eps}}\caption{\label{Fig0}...}
\end{center}
\end{figure}


There are two remarks to be made:

(1) The order of the (white and black) spots is irrelevant now (it will be later, see paragraph ...)
as the set partitions $(P_1,P_2)$ are unordered.

(2) To rewrite the Eq.(\ref{H}) one can forget the blocks, \emph{only the diagram counts}.

With these two remarks Eq.(\ref{H}) reads
\begin{eqnarray}\label{H}
\mathcal{H}(F,G)=\sum_{d\in diag}^\infty mult(d)\mathbb{L}^\alpha(d) \mathbb{V}^\beta(d)\frac{z^{|d|}}{|d|!},
\end{eqnarray}
where
\begin{itemize}
\item{$\alpha(d)$ is the multiindex of the degrees ingoing the white spots.}

\item{$\beta(d)$ is the multiindex of the degrees outgoing from the black spots 
(lines are thought as going from bottom to top.}

\item{$|d|$ is the \emph{weight} of the diagram, \emph{i.e.} the number of its edges.}

\item{$mult(d)$ is the number of pairs of (unordered) partitions whose incidence diagram is $d$}

\end{itemize}

Because we want to compute on the diagrams themselves (use perturbative methods, compose and decompose).
We want to endow the set of diagrams (or better the set of finite supported complex functions over them)
with a structure which is compatible with the indexation of the monomials, \emph{i.e.} such that the arrow
\begin{eqnarray}
diag&\longrightarrow & Pol(\mathbb{L},\mathbb{V})\\
d&\longrightarrow &\mathbb{L}^{\alpha(d)}\mathbb{V}^{\beta(d)}.
\end{eqnarray}
is a morphism of algebras. 

We have in mind three models  Free Boson Gas, Kerr and Superfluidity such that $N_n=1$.
In a second step, we will see that this is a natural comultiplication, induced by the black spots
(whence the denotation $\Delta_{BS}$) such that the arrow (induced by these three models)
\begin{eqnarray}
diag&\longrightarrow & Pol(\mathbb{V})\\
d&\longrightarrow &\mathbb{V}^{\beta(d)}
\end{eqnarray}
is compatible with the decomposition.

Endowed with these two operations, a unite (the empty diagram), 
counit (the Dirac measure located on the unit) and antipode (which is directly computed on the diagrams), see ...) one gets the Hopf algebra $DIAG$ which has immediately a noncommutative analogue $LDIAG$ obtained by labeling the (white and black) spots from left to right and composing them by concatenation (lists) rather than union (multisets). The latter is also endowed with the structure of a Hopf algebra for which the arrow
\begin{eqnarray}
LDIAG\longrightarrow DIAG
\end{eqnarray}
is a Hopf arrow.
The primitive graphs (\emph{i.e.} the primitive elements of the graphs) of these algebras are the ones
for which there is only one black spot in each connected (irreducible) component. These sub-albebras
will be called $Bell$ and $LBell$ and will be of special interest as baby models.

It turns out that the data structure involved in $LDIAG$ is in one-to-one correspondence with the so called
\emph{packed matrices} of $MQSym$ \cite{NCSFVI}, the algebra of Matrix NonCommutative Functions, but the product
and the coproduct in $MQSym$ are completely different.

In a forthcoming paper we will construct a multiparametric deformation of $LDIAG$ of which $LDIAG$ and $MQSym$ are specializations. 

The paper is organized as follows ...





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Monoids of Feynman-like diagrams and functions over them}

\subsection{Description of the monoids of Feynman-like diagrams}

\subsubsection{Labelled diagrams ($ldiag$)}\  

In order to precise the operations on them, we have now to describe in details our data structures. 
A Feynman-like labelled 
diagram (labelled diagram for short) is just a multiset of arrows of 
$[1...p]\times[1...q]$ with no isolated vertex. Formally it gives the following 
definition
\begin{definition}\label{ldiag_def} A labelled diagram $\Gamma$ of dimension $p\times q$ is the 
data of
\begin{itemize}\item[a)]{$\Gamma\subset[1...p]\times[1...q]$ with no 
isolated vertex, \emph{i.e.} $pr_1(\Gamma)=[1...p]$ and 
$pr_2(\Gamma)=[1...q]$}\item[b)]{A weight function $w:\Gamma\longrightarrow 
\mathbb{N}^+=\{1,2,3,...\}$.}
\end{itemize}
The set of labelled diagrams will be denoted $\mathrm{ldiag}$.
\end{definition}

\begin{Example} One usually draws such graphs as bipartite 
graphs with multiple edges. For instance a diagram in Fig.(\ref{Fig1}) is 
composed as follows: \\
$\Gamma=\left\{(1,1),(2,1),(2,2),(2,3),(3,2),(3,3),(4,2)\right\}$ and the weight 
mapping (or function) $w$ is $(1,1)\ra 2$; $(2,1)\ra 1$; 
$(2,2)\ra 3$; $(2,3)\ra 1$; $(3,2)\ra 1$; 
$(3,3)\ra 2$; $(4,2)\ra 1$.

\begin{figure}
\hspace{1cm}
\begin{center}
\resizebox{4cm}{!}{\includegraphics{Fig1.eps}}\caption{\label{Fig1}...}
\end{center}
\end{figure}
\end{Example}


\begin{rmk}
\begin{itemize}
\item[(i)]{ If either $p=0$ or $q=0$, then the condition of ``no isolated vertex'' implies 
 automatically that $p=q=0$ and then $w$ is the void mapping \cite{B-St}. 
We obtain a \emph{unique} void diagram which 
will be denoted by $\emptyset$. This diagram will play an important r\^ole in the 
sequel.}
\item[(ii)]{ One can make the labelled diagrams $\mathrm{ldiag}$ in one-to-one 
correspondence with the \emph{packed matrices} which are 
rectangular matrices of integers with no zero line or column \cite{NCSFVI}. The correspondence is 
made by the weight function. To a labelled diagram of dimension $p\times q$ one 
associates the packed matrix of dimension $p\times q$ defined by

\begin{eqnarray}
\nonumber M[i,j]=
\left\{
\begin{array}
{cl}w(i,j) &\rm{if }\ (i,j)\in\Gamma\\
0&\rm{otherwise.}
\end{array}
\right.
\end{eqnarray}

It is clear that the result is a packed matrix and the correspondence is one-to-one.}
\end{itemize}
\end{rmk}

Now we define the monoid structure on $ldiag$. This monoid structure will turn 
out to be compatible with the evaluation by multipliers\\ 
{\tt cite related papers}.\\

Let $d_1=(\Gamma_1,w_1)$ (resp. $d_2=(\Gamma_2,w_2)$) be labelled diagrams of 
dimension $p_1\times q_1$ (resp. $p_2\times q_2$) then their concatenation 

$d_3=\left[\begin{array}{c}d_1\\d_2\end{array}\right]_L=(\Gamma_3,w_3)$ is defined by

\begin{eqnarray}
\hspace{-17mm}
\nonumber (i,j)\in\Gamma_3\ \ \rm{if}\ \ 
\left\{
\begin{array}{c}
1\leq i\leq p_1,\ \ 1\leq j\leq q_1\ \  \rm{and}\ \  (i,j)\in\Gamma_1
\\
\nonumber\rm{or}
\\
p_1+1\leq i\leq p_1+p_2,\ \ q_1+1\leq j\leq q_1+q_2\ \ \mathrm{and}\ \ (i-p_1,j-q_1)\in\Gamma_2
\end{array}
\right.
\end{eqnarray}

and

\begin{eqnarray}
\hspace{-17mm}
\nonumber w_3(i,j)=
\left\{
\begin{array}{c}
w_1(i,j)\ \ \rm{if}\ \ (i,j)\in [1\cdots p_1]\times[1\cdots q_1]
\\
\nonumber\rm{and}
\\w_2(i-p_1,j-q_1)\ \ \rm{if}\ \ (i,j)\in [p_1+1\cdots p_1+p_2]\times[q_1+1\cdots q_1+q_2]\end{array}
\right.
\end{eqnarray}
\begin{rmk}

\begin{itemize}\item[(i)]{At the level of drawing $d_3$ is just the diagram 
obtained by putting $d_2$ under $d_1$, as shown by Fig.(\ref{Fig2})

\begin{figure}\hspace{1cm}
\begin{center}
\resizebox{10cm}{!}{\includegraphics{Fig2.eps}}\caption{\label{Fig2}...}
\end{center}
\end{figure}}

\item[(ii)]{As regards the correspondence $d\longrightarrow packed(d)$ one has

\begin{eqnarray}
\nonumber packed
\left(\left[
\begin{array}{c}d_1\\d_2\end{array}
\right]_L
\right) =
%
\left(
\begin{array}{c|c}packed(d_1)&0_{p_1\times q_2}
\\
0_{p_2\times q_1}&packed(d_2)
\end{array}
\right),
\end{eqnarray}

hence juxtaposition product becomes the blockdiagonal product on matrices.}

\end{itemize}
\end{rmk}

In general $\left[\begin{array}{c}d_1\\d_2\end{array}\right]_L\neq 
\left[\begin{array}{c}d_2\\d_1\end{array}\right]_L$. More precisely, the 
following result will be a consequence of proposition \mref{freemonoid}.\\

\begin{prop}If 
$\left[\begin{array}{c}d_1\\d_2\end{array}\right]_L=\left[\begin{array}{c}d_2\\d
_1\end{array}\right]_L$ 
then $d_1$ and $d_2$ are powers of a common diagram (say 
$d$), \emph{i.e.} 

\begin{eqnarray}
\nonumber d_1=
\underbrace{\left[\begin{array}{c}
d\\
d\\
\vdots
\\
d
\end{array}
\right]_L}_{\rm{n\ times}}
\ \ \ \ \ \ \ \ \ \ \rm{and} 
\ \ \ \ \ \ \ \ 
\ \  
d_2=\underbrace{\left[\begin{array}{c}d\\d\\\vdots\\d\end{array}\right]_L}_{\rm{
m\ times}}.
\end{eqnarray}
\end{prop}

We have the following proposition

\begin{prop}\label{freemonoid}
$(ldiag,[\ ]_L,\emptyset)$ is a free monoid.
\end{prop}
\begin{Proof} 
...\end{Proof}\\

\begin{definition}\label{parameters}
Let $d$ be a labelled diagram of dimension $p\times q$. Then we 
set
\begin{eqnarray}
\nonumber WS(d)=[1\cdots p]\ \ \rm{''white\ 
spots''}\\
\nonumber BS(d)=[1\cdots q]\ \ \rm{''black\ spots''}\\
\nonumber\rm{for}\ \ 
\ (i,j)\in\Gamma\ \ \ 
\left\{\begin{array}{l}
out(i)=\sum_{(i,k)\in\Gamma}w(i,k)\\
in(j)=\sum_{(k,j)\in\Gamma}w(k,j)
\end{array}\right.
\end{eqnarray}

and the total weight $|d|$ is the number of edges, \emph{i.e.}

\begin{eqnarray}
\nonumber|d|=\sum_{(i,j)\in\Gamma}w(i,j).
\end{eqnarray}
\end{definition}


In order to describe precisely other operations (such as the coproduct and the action of the symmetric group on the spots) 
we have advantage to consider also an horizontal composition.

Let $d_1\in ldiag_{p\times q}$ and $d_2\in ldiag_{q\times r}$ described by their weight functions $w_1,\ w_2$, then one builds a diagram 
$d_3=d_1.d_2$ with weight function
\begin{equation}
w_3(i,k)=\sum_{j=1}^q w_1(i,j)w_2(j,k)
\end{equation}
this amounts to counting the number of paths going from $i$ to $k$.

If one allows the diagrams to have isolated vertices (i.e. if one relaxes condition (a) of \mref{ldiag_def}), one just obtains the subcategory of 
the category of matrices formed by the matrices with non-negative coefficients. For such a {\it generalised labelled diagram} $d$  
of dimension $p\times q$ (their set will be denoted by $gldiag_{p\times q}$), with weight function $w$, one has the support 

\begin{equation}
\Gamma=supp(d)=\{(i,j)\in [1\cdots p]\times [1\cdots q]\ \mathbf{\big|}\ w(i,j)\not=0\}
\end{equation}
and $WS(d)=pr_1(supp(d)),\ BS(d)=pr_2(supp(d))$ (the functions $in,\ out$ and $|\ |$ being defined as in definition \mref{parameters}). Thus a labelled diagram can be characterized among those of $gldiag_{p\times q}$ 
by the conditions $WS(d)=[1\cdots p],\ BS(d)=[1\cdots q]$.

This category of diagrams (generalised labelled diagrams) will be endowed with the two compositions : vertical and horizontal. Moreover, we will need the natural involution $d\ra d*$ which consist in exchanging the white and black spots by a vertical symmetry. This involution is perfectly described by means of the weight functions as
\begin{equation}
	w_{d^*}(j,i)=w_d(i,j)
\end{equation}
One can check easily that
\begin{equation}
	d\in ldiag\Longleftrightarrow d^*\in ldiag
\end{equation}

\subsubsection{Functional diagrams}

Let $f : [1\cdots p]\mapsto [1\cdots q]$, we denote by $d_f\in gldiag$ the diagram of dimension $p\times q$ with weight function $w_f(i,j)=\delta_{f(i),j}$. 

\begin{Example}
i) (Some non-crossing diagrams) Let $X\subset [1\cdots n]$ and $j^{(n)}_X$ denote the unique strictly increasing mapping $[1\cdots |X|]\mapsto [1\cdots n]$ such that $j^{(n)}_X([1\cdots |X|])=X$. In other words, if $|X|=k$ and $X=\{x_1<x_2<\cdots <x_k\}$ one has $j^{(n)}_X(t)=x_t$.\\
ii) (Permutations) Let $\SG_n$ be the symmeric group of order $n$. For every permutation $\sigma\in \SG_n$, the diagram $d_\sigma$ belongs to $ldiag_{n\times n}$. 
\end{Example}

It is straightforward to check that, in general, if $f : [1\cdots p]\mapsto [1\cdots q]$ and $g : [1\cdots q]\mapsto [1\cdots r]$ then 
\begin{equation}
	d_f.d_g=d_{g\circ f}
\end{equation}

One can, with this setting, construct two important operations on the labelled diagrams : selections and relabelling.

\bs
{\bf Selection}\pointir

 Let $d\in ldiag_{p\times q}$ and $I\subset [1\cdots p]$. We set 
 
 
\begin{equation}
	J=supp(d)\langle I\rangle=\{j\ |\ (\exists i\in I)((i,j)\in supp(d))\}
\end{equation}
  (the image of $I$ by the correspondence $supp(d)$, see also \cite{B-St} chap II par 3.1 Def 3) 

then, we define
\begin{definition}
With the denotations as above, the restriction of $d\in ldiag_{p\times q}$ to the white spots of $I\subset [1\cdots p]$ is
\begin{equation}
	d|_I=d_{j^{(p)}_I}.d.(d_{j^{(q)}_J})^*
\end{equation}
\end{definition}

\bs
{\bf Relabelling}\pointir

Let $d\in ldiag$. For 
$(\sigma,\tau)\in \SG_{WS(d)}\times \SG_{BS(d)}$ one defines $d^{(\sigma,\tau)}$
by 
$d^{(\sigma,\tau)}=(\Gamma^{(\sigma,\tau)},w^{(\sigma,\tau)})$where
\\ 
$(i,j)\in\Gamma^{(\sigma,\tau)}\Leftrightarrow (\sigma(i),\tau(j))\in\Gamma$ and 
$w^{(\sigma,\tau)}(i,j)=w(\sigma(i),\tau(j))$.
\\ 

It can be easily seen that these formulas define an action of the group 
$\SG_{[1\cdots p]}\times\SG_{[1\cdots q]}$ on the set of labelled 
diagrams of dimension $p\times q$.
\\
One says that two diagrams are equivalent 
(and denotes $d_1\thicksim d_2$) if they are in the same orbit for this 
action. The class function of this equivalence class turns out to be compatible with the 
``vertical composition''. One has the following result.
\\
\begin{prop} The product on $ldiag$ is compatible with respect to the equivalence 
$\thicksim$. 
In other words if 
$d_{11}\thicksim d_{12}$ and $d_{21}\thicksim d_{22}$ 
then
\begin{eqnarray}
\nonumber
\left[
\begin{array}{c}
d_{11}
\\d_{21}
\end{array}
\right]_L
\thicksim
\left[
\begin{array}{c}
d_{12}
\\d_{22}
\end{array}
\right]_L
\end{eqnarray}
\end{prop}

\begin{Proof} For two pemutations $\sigma\in \SG_n,\tau\in \SG_m$ one can check that 

\begin{eqnarray}
\nonumber
\left[
\begin{array}{c}
d_\sigma
\\
d_\tau
\end{array}
\right]_L
\end{eqnarray}

is the labelled diagram of a permuation which we will denote $\sigma.\tau$ in this proof \cite{NCSFIII}.\\ 
Now, let $d_{i1}\in ldiag_{p_i\times q_i};\ i=1,2$ and $d_{12}=d_{11}^{(\sigma_1,\tau_1)}
;\ d_{22}=d_{21}^{(\sigma_2,\tau_2)}$.\\
One has the following equality
\begin{eqnarray}
\nonumber
\left[
\begin{array}{c}
d_{12}
\\
d_{22
}
\end{array}
\right]_L=
\left[
\begin{array}{c}
d_{11}^{(\sigma_1,\tau_1)}
\\
d_{21}^{(\sigma_2,\tau_2)}
\end{array}
\right]_L
=
\left[
\begin{array}{c}
d_{11}
\\
d_{21}
\end{array}
\right]_L^{(\sigma_1\cdot\sigma_2,\tau_1\cdot\tau_2)}
\end{eqnarray}
\end{Proof}
\\
We are now in position of defining the monoid $diag$.

\begin{prop} 
Set $diag:=ldiag/\thicksim$. Then, the set $diag$ is endowed with the 
unique structure of monoid such that the class arrow 
$\Phi_d:ldiag\longrightarrow diag$ is a morphism of monoids.
\end{prop}

\begin{Proof}
\end{Proof}


The set of parameters of a diagram is invariant in the following sense. Let 
$(\sigma,\tau)\in\SG_{WS(d)}\times\SG_{BS(d)}$ then for 
$(i,j)\in\Gamma$ one has 
($d=(\Gamma,w)$)
\begin{eqnarray}
\nonumber
out(d^{(\sigma,\tau)};\sigma(i))=out(d;i)\\
\nonumber
in(d^{(\sigma,\tau)};\tau(i))=in(d;i)\\
\nonumber
|d^{(\sigma,\tau)}|=|d|
\end{eqnarray}

\subsection{Algebras of functions}
\subsubsection{Generalities}

Let $X$ be a set. The set of complex-valued functions on $X$ will be denoted 
by $\mathbb{C}^X$ \cite{B-St}. This set is at once endowed with a pointwise 
(or Hadamard) product $f\odot d:x\longmapsto f(x)g(x)$ which makes the 
$\mathbb{C}$-vector space $\mathbb{C}^X$ an algebra. A function $f$ is 
idempotent ($f\odot f=f$) in this algebra iff it ranges in $\{0,1\}$; these are 
the characteristic functions of sets. Minimal idempotents are identified with Dirac measures, 
that is to say characteristic functions of singletons, \emph{i.e.} 
$\delta_x:=(y\longrightarrow\delta_{xy})$ (which is the characteristic function of 
$\{x\}$).
The vector space generated by the $(\delta_x)_{x\in X}$ is exactly the 
space of finitely supported functions, it will be denoted $\mathbb{C}^{(X)}$, 
and for $f\in \mathbb{C}^{(X)}$ one has $f=\sum_{x\in X}f(x)\delta_x$. If, 
additionally, $X$ is a monoid, $\mathbb{C}^X$ is endowed with a second product, 
the \emph{Cauchy} or \emph{convolution product} 
\cite{B-AlgI}
\cite{BR}
\cite{Ei}
 given by
\begin{eqnarray}
\label{Cauchy}
\left(
\sum_{x\in X} f(x)\delta_x\right)\left(\sum_{y\in X}g(y)\delta_y\right)=
\sum_{z\in X}\left(\sum_{xy=z}f(x)g(y)\right)\delta_z
\end{eqnarray}

We note that 
Eq.(\ref{Cauchy}) still makes sense for general functions if the monoid fulfills the condition 
\begin{eqnarray}\nonumber[D]\ \ \ \ \ (\forall x\in X)(\left|\{(x,y)\in X\times X:\ xy=z\}\right|<\infty).
\end{eqnarray}
(see \cite{B-AlgI} for this discussion).\\
In this case (which will be fulfilled by $ldiag$ and $diag$) the algebra $\mathbb{C}^X$ (which is then called the 
total algebra of $X$ \cite{B-AlgI}) is 
endowed with two structures of algebra given by the Hadamard (denoted $\odot$) 
and the Cauchy product (denoted by $\cdot$ or without a sign).
\begin{prop} The monoid $ldiag$ and $diag$ fulfill condition $[D]$.
\end{prop}
\begin{Proof}This can be seen by the fact that the number of diagrams with total weight $n$ is 
finite and from the fact that in the two cases the product is 
graded
\begin{eqnarray}
\left|
\left[
\begin{array}{c}
d_1\\d_2
\end{array}
\right]
\right|_s
=|d_1|_s+|d_2|_s
\end{eqnarray}
where $s$ stands for one of the two signs $L$ or $D$.
\end{Proof}\\

>From now on, we set 
\begin{equation}
Ldiag_\mathbb{C}=\mathbb{C}^{(ldiag)},\ \overline{Ldiag}_\mathbb{C}=\mathbb{C}^{ldiag},\ Diag_\mathbb{C}=\mathbb{C}^{(diag)},\ 
\overline{Diag}_\mathbb{C}=\mathbb{C}^{diag}
\end{equation}
 these spaces being endowed with 
the structure of the associative algebra with unit (AAU) given by the Cauchy 
product.

{\tt prehilbertian structure and denotation of Dirac-Sch\"utzenberger}

\section{Hopf algebra structure of $Ldiag_\mathbb{C}$ and 
$Diag_\mathbb{C}$}

\subsection{$Ldiag_\mathbb{C}$}
\subsubsection{Coproduct}\ 
\\
First, for $I\subset WS(d)$ we have defined the operation of restriction to 
$I$ which amounts to take the white spots belonging to $I$ and the subgraph 
conected to these white spots and removing all the other edges and spots.\\ 
The coproduct of $Ldiag_\mathbb{C}$ is defined on the generators by

\begin{eqnarray}
\Delta(d)=\sum_{I+J\subset WS(d)}d|_I\otimes d|_J.
\end{eqnarray}

\subsubsection{The bialgebra $Ldiag_\mathbb{C}$}\ 
\\
First, we prove that 
$\Delta:Ldiag_\mathbb{C}\longrightarrow Ldiag_\mathbb{C}\otimes Ldiag_\mathbb{C}$ 
is coassociative, that is to say that the following diagram is commutative

$$
\xymatrix{Ldiag \ar[r]^-\Delta \ar[d]^\Delta & Ldiag_\mathbb{C}\otimes Ldiag_\mathbb{C} \ar[d]^{\Delta\otimes Id}
\\
Ldiag_\mathbb{C}\otimes Ldiag_\mathbb{C} \ar[r]^-{Id\otimes \Delta} & Ldiag_\mathbb{C}\otimes Ldiag_\mathbb{C}\otimes Ldiag_\mathbb{C}}
$$

Indeed, we have, for $d$ of dimension $p\times q$

\begin{eqnarray}
\nonumber
\Delta\otimes Id(\Delta(d)) &=& (\Delta\otimes Id)\left(\sum_{I+J = [1\cdots p]}d|_I\otimes d|_J\right)
\\
\nonumber &=& (\Delta\otimes Id)\left(\sum_{k=0}^p\left(\sum_{I+J = [1\cdots p],\ |I|=k}d|_I\otimes 
d|_J\right)\right)
\\
\nonumber &=&\sum_{k=0}^p\sum_{I+J = [1\cdots p],\atop I=\{i_1<\cdots <i_k\}}\Delta(d|_I) \otimes d|_J
\\
\nonumber &=&\sum_{k=0}^p\sum_{I+J= [1\cdots p]\atop I=\{i_1<\cdots i_k\}}
\left(\sum_{I_1+I_2=[1\cdots k]}\left.(d|_I)\right|_{I_1}\otimes 
\left.(d|_I)\right|_{I_2}\right)\otimes 
d|_J\\\nonumber&=&\sum_{I+J+K=[1\cdots p]}d|_I\otimes d|_J \otimes 
d|_K
\end{eqnarray}

To prove that $\Delta$ is a morphism we need the following 
lemma\\

\begin{Lemma} Let $s_{p_1}[1,\cdots ,p_1]\longrightarrow [p_1+1,\cdots ,p_1+p_2]$ 
denote the unique strictly increasing mapping and $s_{-p_1}$ its reciprocal 
(in other words $d_{s_{p_1}}$ is the unique non-crossing functional diagram 
from $[1\cdots p_1]$ to $[p_1+1\cdots p_1+p_2]$ with no isolated vertex).

Then for $d_i$ ($i=1,2$) of dimension $p_i\times q_i$ one has
\begin{eqnarray}
\nonumber
%\left.
\left[
\begin{array}{c}
d_1\\d_2
\end{array}
\right]_L |_{I+s_{p_1}(I_2)}=
\left[
\begin{array}{c}
d_1|_{I_1}\\
d_2|_{I_2}
\end{array}
\right]_L
\end{eqnarray}

\end{Lemma}

Then
\begin{eqnarray}
\nonumber
\Delta(d_1)[\ ]_L^{\otimes^2}\Delta(d_2)
&=&
\left(\sum_{I_1+I_2=[1\cdots p_1]}d_1|_{I_1}\otimes d_2|_{I_2}\right)[\ ]_L^{\otimes^2}\left(\sum_{J_1+J_2=[1\cdots p_2]}d_1|_{J_1}\otimes d_2|_{J_2}\right)
\\
\nonumber&=&\sum_{I_1+J_1=[1\cdots p_1],\ I_2+J_2=[1\cdots p_2]}
\left[
\begin{array}{c} 
d_1|_{I_1}\\
d_2|_{I_2}
\end{array}
\right]_L 
\otimes
\left[
\begin{array}{c}
d_1|_{J_1}\\d_2|_{J_2}
\end{array}
\right]_L
\\
\nonumber&=&\sum_{I_1+J_1=[1\cdots p_1],\ I_2+J_2=[1\cdots p_2]}
\left.
\left[
\begin{array}{c}d_1
\\
d_2
\end{array}
\right]_L
\right|_{I+s_{p_1}(I_2)}
\otimes
\left.
\left[
\begin{array}{c}
d_1\\d_2
\end{array}
\right]_L\right|_{J+s_{p_1}(J_2)}
\end{eqnarray}
but the mapping

\begin{eqnarray}\nonumber\left\{(I_1,J_1,I_2,J_2):\ I_1+J_1=[1\cdots p_1],\ 
I_2+J_2=[1\cdots p_2]\right\}\longrightarrow\left\{I+J=[1\cdots p_1+p_2]\right\}
\end{eqnarray}
defined by 
$(I_1,J_1,I_2,J_2)\longrightarrow(I_1+s_{p_1}(I_2),J_1+s_{p_1}(J_2))$ is one-to-
one. 

So the sum equals to
\begin{eqnarray}
\nonumber\sum_{I+J=[1\cdots p_1+p_2]}
\left.\left[
\begin{array}{c}d_1\\d_2
\end{array}
\right]_L
\right|_I\otimes
\left.
\left[
\begin{array}{c}d_1\\d_2
\end{array}
\right]_L
\right|_J =
\Delta
\left(
\left[
\begin{array}{c}d_1\\d_2
\end{array}
\right]_L
\right)
\end{eqnarray}

\underline{Counity:} The counit 
$Ldiag_\mathbb{C}\stackrel{\epsilon}{\longrightarrow}\mathbb{C}$ is defined on 
the generators by $\epsilon(d)=\delta_{d,\emptyset}$ so that, if 
$a=\sum_{d\in ldiag}\alpha_d d$, one has 
$\epsilon(a)=\alpha_\emptyset$ 
\begin{eqnarray}
\nonumber nat_l(\epsilon\otimes Id)(\Delta(d))=
nat_l\left(\sum_{I+J=[1\cdots p_1]}
\epsilon(d|_I)\otimes d|_J\right)\\\nonumber=
nat_l\left(\sum_{I+J=[1\cdots p_1],\ I\neq 0}\epsilon(d|_I)\otimes d|_J+\epsilon(\emptyset)\otimes 
d\right)\\\nonumber\stackrel{(*)}{=}nat_l(\epsilon(\emptyset)\otimes d)=
nat_l(1_\mathbb{C}\otimes d)=d,
\end{eqnarray}
where equality $(*)$ is due to vanishing of the first sum inside 
$nat_l$.The same computation gives $nat_r(Id\otimes\epsilon )(\Delta(d))=d$.
 As a consequence the following diagram is commutative
$$\xymatrix{diag_\mathbb{C}\otimes\mathbb{C}\ar[d]^{nat_r}  
&  Ldiag_\mathbb{C}\otimes Ldiag_\mathbb{C} \ar[l]_-{Id\otimes \epsilon} 
\ar[r]^-{\epsilon\otimes Id}  & \mathbb{C}\otimes Ldiag_\mathbb{C} 
\ar[d]^{nat_l}\\Ldiag_\mathbb{C}\ar[r]^{Id} & 
Ldiag_\mathbb{C}\ar[r]^{Id}\ar[u]^\Delta & Ldiag_\mathbb{C}}$$

All these properties prove that 
$(Ldiag_\mathbb{C},\cdot,\delta_\emptyset,\Delta,\epsilon)$ is a bialgebra.\\
One can remark that this bialgebra is graded with respect to the total weight and 
the homogeneous components have finite dimensions thus by a general theorem 
antipode exists. We can even give an explicit formula.
\\
\begin{prop} Let $d$ be 
a diagram of dimension $p\times q$, then the antipode of $d$ 
reads
\begin{eqnarray}
\nonumber
\alpha(d)=\sum_{k=0}^\infty (-1)^k\sum_{I_1+I_2+\cdots +I_k=[1\cdots p],\atop I_j\neq\emptyset}
\left[
\begin{array}{c}d|_{I_1}\\
\vdots\\
d|_{I_k}
\end{array}
\right]_L
\end{eqnarray}
\end{prop}

\subsection{The Hopf arrow $Ldiag_\mathbb{C}\longrightarrow Diag_\mathbb{C}$}...

\emph{Compatibility of $\Delta$}\\

Let us prove that $d^{(\sigma,\tau)}|_I=\left(d|_{\sigma(I)}\right)^{(\sigma ',\tau ')}$ 
where
$$\xymatrix{I\ar[r]^{j_I^<} \ar[dr]_\sigma& \sigma(I) \ar[d]^{\sigma '} \\& 
\sigma(I)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\xymatrix{J\ar[r]^{j_J^<} \ar[dr]_\tau& \tau(J) \ar[d]^{\tau '} \\& \tau(J)}$$

If we select $I\in BS(d)$, 
we must select only $j$'s that are nonzero columns, so...

\subsection{Sweedler's duals and a modified Kleene-Sch\"utzenberger's Theorem}...

\section{Conclusion} ...  

%%%%%%\ackWe thank ... for important discussion

\Bibliography{99}
%
\bibitem{BR} {\sc Berstel J. and Reutenauer C.}, {\it Rational series and their 
languages}, EATCS, 1988.
%
\bibitem{B-St} {\sc Bourbaki N.}, {\it Elements of Mathematics: Theory of sets}, Springer-Verlag (2004)
%
\bibitem{B-AlgI} {\sc Bourbaki N.}, {\it Elements of Mathematics: Algebra I}, Springer-Verlag (1989)
%
\bibitem{NCSFIII} {\sc Duchamp G., Klyachko A., Krob D., Thibon J.Y.},
 {\it Noncommutative symmetric functions III: Deformations of Cauchy and 
convolution algebras} Discrete Mathematics and Theoretical Computer Science
Vol. {\bf 2} (1998).
%
\bibitem{NCSFVI} {\sc Duchamp G., Hivert F., Thibon J.Y.}, {\it Non commutative 
functions VI: Free quasi-symm\'etric functions and related algebras} 
IJAC Vol. 12 {\bf 5} (2002).
%
\bibitem{Ei} {\sc S. Eilenberg}, {\em Automata, languages and machines}, Vol. A and B, 
Academic press, 1976.
\endbib

\end{document}




