The Hopf algebra of uniform block permutations.\\ Extended abstract
Marcelo Aguiar
%
blockperm.tex
% M. Aguiar and  R.C. Orellana
% Start: 8/25/04
% Version of:  May 9 2005

\documentclass[12pt]{amsart}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{color}
%\usepackage[enableskew]{youngtab}
%\usepackage{epic}
%%\usepackage{eepic}
%\usepackage{ecltree}
\usepackage{graphicx}
\usepackage{epsfig}

\setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in} \setlength{\topmargin}{0in}
\setlength{\textheight}{8in}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{con}[theorem]{Conjecture}
\newtheorem{defi}[theorem]{Definition}
\newtheorem{rem}[theorem]{Remark}
\newtheorem{exa}[theorem]{Example}

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

\newcommand{\End}{\mathrm{End}}
 \newcommand{\Sh}{\mathrm{Sh}}
 \newcommand{\id}{{\mathit{id}}}
\newcommand{\meet}{\wedge}
\newcommand{\join}{\vee}

\def\min{\mathrm{min}}
\newcommand{\map}[1]{\xrightarrow{#1}}
\newcommand{\inc}{\hookrightarrow}
\newcommand{\mat}[1]{\begin{pmatrix}#1\end{pmatrix}} % for a matrix ( )

\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calZ}{\mathcal{Z}}
\newcommand{\Sym}{{\mathit{Sym}}}
\newcommand{\SSym}{{\calS}\Sym}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\field}{\Bbbk} % for the base field
\newcommand{\kX}{\field\langle\!\langle X\rangle\!\rangle}

\newcommand{\blue}[1]{\color{blue}{#1}\color{black}}
\newcommand{\red}[1]{\color{red}{#1}\color{black}}

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

\begin{document}
\title[Hopf algebra of uniform block permutations]{The Hopf algebra of uniform block permutations.\\
Extended abstract} 
\author{Marcelo Aguiar}
\address{Department of Mathematics\\
         Texas A\&M University\\
         College Station\\
         TX  77843\\
         USA}
\email{maguiar@math.tamu.edu}
\urladdr{http://www.math.tamu.edu/$\sim$maguiar}

\author{Rosa C. Orellana}
\address{Department of Mathematics\\
        Dartmouth College \\
        Hanover, NH 03755\\
        USA}
\email{Rosa.C.Orellana@Dartmouth.EDU}
\urladdr{http://www.math.dartmouth.edu/$\sim$orellana/}

\thanks{Aguiar supported in part by NSF grant DMS-0302423}
\thanks{Orellana supported in part by the Wilson Foundation}

\keywords{Hopf algebra, uniform block permutation,  set partition, symmetric functions, Schur-Weyl duality}
\subjclass[2000]{Primary: 05E99, 16W30; Secondary:  16G99, 20C30}
\date{November 17, 2004}

%\begin{abstract}
%\end{abstract}

 \maketitle

\begin{center}
 \begin{minipage}[c]{380pt}
 \small
 {\sc Abstract.}
 We introduce the Hopf algebra of uniform block permutations and show that it is  self-dual, free, and cofree. These results are closely related to
 the fact that  uniform block permutations form a factorizable inverse monoid.
This Hopf algebra
contains the Hopf algebra of permutations of Malvenuto and Reutenauer 
and the Hopf algebra of symmetric functions in non-commuting variables of
Gebhard, Rosas, and Sagan.
\end{minipage}\vspace{20pt}\\ 

\begin{minipage}[c]{380pt}
 \small
 {\sc R\'esum\'e.}
Nous pr\'esentons l'alg\`ebre de Hopf des permutations de blocs uniformes  est d\'emontrons qu'elle est auto duale, libre et colibre. Ces r\'esultats sont li\'es au fait que les permutations de blocs uniformes constituent un mono\"\i de inverse
factorisable.
Cette alg\`ebre de Hopf contient l'alg\`ebre de Hopf des permutations de Malvenuto et  Reutenauer et l'alg\`ebre de Hopf des fonctions 
sym\'etriques \`a variables non commutatives de Gebhard,  Rosas, et  Sagan.
\end{minipage}
\end{center}
 

 
\section{Uniform block permutations}

\subsection{Set partitions}\label{S:setpar}

Let $n$ be a non-negative integer and let $[n]:=\{1,2,\ldots, n\}$. A \emph{set partition} of $[n]$ is
a collection  of non-empty disjoint subsets of $[n]$, called {\em blocks}, whose union is $[n]$.
For example, $\calA=\big\{ \{2,5,7\}\{1,3\}\{6,8\}\{4\}\big\}$, is a set partition of $[8]$ with $4$ blocks.
  We often specify a set partition by listing the blocks from left to right so that the sequence formed by the minima of the blocks is increasing, and by listing the
  elements within each block in increasing order.
For instance,  the set partition above will be denoted 
$\calA=\{1,3\}\{2,5,7\}\{4\}\{6,8\}$.
We use $\calA\vdash [n]$ to indicate  that $\calA$ is a set partition of $[n]$.  

%Given a set partition $A=A_1A_2\ldots A_{\ell(A)}$ and a subset $\{i_1,i_2, \ldots, i_k\}\subset[\ell(A)]$,
%for $0\leq k\leq \ell(A)$. Then the blocks $A_{i_1}A_{i_2}\ldots A_{i_k}$ is called a
%\emph{subpartition} of $A$. Notice that the blocks in a subpartition are arranged in decreasing 
%order. For example, if $A=\{1,3,7\}\{2,5\}\{4\}\{6\}$, then $\{1,3,7\}\{4\}$ is a subpartition of $A$. 
%We will denote by $\mathcal{P}(A)$ the set of all subpartitions of $A$. Notice that the number of set 
%partitions is equal to the number of subsets of $\ell(A)$, that is $2^{\ell(A)}$. 
%\vskip 0in 

The {\em type} of a set partition $\calA$ of $[n]$ is the partition of $n$ formed by the sizes of the blocks of $\calA$. The symmetric group $S_n$ acts on the set of set partitions of $[n]$:
 given $\sigma\in S_n$ and $\calA\vdash [n]$, $\sigma(\calA)$ is the set partition whose blocks are $\sigma(A)$ for $A\in\calA$.
The orbit of $\calA$ consists of those set partitions of the same type as $\calA$.
The stabilizer of $\calA$ consists of those permutations that preserve the blocks, or that permute blocks of the same size. Therefore, the number 
of set partitions of type $1^{m_1}2^{m_2}\ldots n^{m_n}$ ($m_i$ blocks of size $i$) is
\begin{equation}\label{E:setpar}
 \frac{n!}{m_1! \cdots m_n! (1!)^{m_1}\cdots (n!)^{m_n}}\,.
 \end{equation}

 
%$(d_1,d_2,\ldots, d_k)$ such that $d_i$ is the
%size of block $D_j$ in $D$.  The number of set partitions of type $(d_1,d_2, \ldots, d_k)$ where 
%$m_i$ is the number of times a block of size $i$ occurs in $D$ is given by:
%$$ \frac{n!}{m_1! \cdots m_n! d_1!\cdots d_k!}.$$

%
%  
% by permuting the elements in the blocks of a set 
%partition. Let $A=A_1\cdots A_r$ be a set partition of $[n]$, then for $\sigma\in S_n$ we have 
%that the blocks of $\sigma(A)$ are $\sigma(A_1),\ldots, \sigma(A_r)$, where 
%$\sigma(A_i)=\{\sigma(a)\, |\, a\in A_i\}$. Under this action of $S_n$ the stabilizer of 
%$A$ is the Young subgroup $S_{A_1}\times S_{A_2}\times \cdots \times S_{A_r}$, where $S_{A_i}$ 
%is the group of permutations of the elements in $A_i$. 

%------------------------------------------------------------------------------------------------

\subsection{The monoid of uniform block permutations}

The monoid (and the monoid algebra) of uniform block permutations has been studied by FitzGerald \cite{f} and Kosuda \cite{k00,k01} in analogy to the partition algebra of Jones and Martin \cite{j,m}. 

A \emph{block permutation} of $[n]$ consists of  two set partitions $\calA$ and $\calB$ of $[n]$ with the same number of blocks and
 a bijection $f:\calA\to\calB$. For example, if $n=3$, $f(\{1,3\})=\{3\}$ and $f(\{2\})=\{1,2\}$ then $f$ 
is a block permutation.   
A block permutation is called \emph{uniform} if it maps each block of $\calA$ to a block of $\calB$ of the same 
cardinality.  For example, $f(\{1,3\})=\{1,2\}$, $f(\{2\})=\{3\}$
is uniform. Each permutation  may be viewed as a uniform block permutation for which all blocks have cardinality $1$.   
In this paper we only consider block permutations that are uniform. 

To specify a  uniform block permutation $f:\calA\to\calB$ we must choose
two set partitions $\calA$ and $\calB$ of the same type $1^{m_1}\ldots n^{m_n}$
and for each $i$ a bijection between the $m_i$ blocks of size $i$ of $\calA$
and those of $\calB$. We deduce from~\eqref{E:setpar} that the total number of uniform block permutations  of $[n]$ is 
\begin{equation}
u_n:=\sum_{1^{m_1}\ldots n^{m_n}\vdash n}  \left(\frac{n!}{(1!)^{m_1}\cdots (n!)^{m_n}}\right)^2\frac{1}{m_1!\cdots m_n!}
\end{equation}
where the sum runs over all partitions of $n$. Starting at $n=0$, the first values are
\[1,1,3,16,131,1496,22482,\ldots\]
This is sequence A023998 in~\cite{sl}. These numbers and generalizations
are studied in~\cite{sps}; in particular, the following recursion is given in~\cite[equation (11)]{sps}:
\[u_{n+1}=\sum_{k=0}^n\binom{n}{k}\binom{n+1}{k}u_k\,,\quad u_0=1\,.\]


We represent uniform block permutations by means of  graphs.
For instance, either one of the two graphs in Figure~\ref{F:twographs}  represents the uniform block permutation $f$ given by
\[\{1,3,4\}\rightarrow\{3,5,6\},\ 
\{2\}\rightarrow \{4\}, \ \{5,7\}\rightarrow \{1,2\},\ \{6\}\rightarrow \{8\},\ \mbox{ and } 
\{8\}\rightarrow \{7\}\,.\]
\begin{figure}[!h]
\centering
\begin{picture}(370,70)(0,0)
\put(30,10){\circle*{3}}\put(30,60){\circle*{3}}\put(29,11){\line(5,3){80}}
\put(25,0){\small{1}}\put(25,67){\small{1}}
\put(50,10){\circle*{3}}\put(50,60){\circle*{3}}\put(30,10){\line(1,0){20}}
\put(45,0){\small{2}}\put(45,67){\small{2}}
\put(70,10){\circle*{3}}\put(70,60){\circle*{3}}\put(50,10){\line(2,1){100}}
\put(65,0){\small{3}}\put(65,67){\small{3}}
\put(90,10){\circle*{3}}\put(90,60){\circle*{3}}\put(70,10){\line(-4,5){40}}
\put(85,0){\small{4}}\put(85,67){\small{4}}
\put(110,10){\circle*{3}}\put(110,60){\circle*{3}}\put(70,10){\line(2,5){20}}
\put(105,0){\small{5}}\put(105,67){\small{5}}
\put(130,10){\circle*{3}}\put(130,60){\circle*{3}}\put(70,60){\line(1,0){20}}
\put(125,0){\small{6}}\put(125,67){\small{6}}
\put(150,10){\circle*{3}}\put(150,60){\circle*{3}}\qbezier(70,60)(50,67)(30,60)
\put(145,0){\small{7}}\put(145,67){\small{7}}
\put(170,10){\circle*{3}}\put(170,60){\circle*{3}}\put(90,10){\line(-4,5){40}}
\put(165,0){\small{8}}\put(165,67){\small{8}}
\put(110,10){\line(-4,5){40}}\put(110,10){\line(1,0){20}}\put(150,10){\line(2,5){20}}
\put(170,10){\line(-4,5){40}}
%canonical diagram
\put(200,30){$\sim$}
\put(230,10){\circle*{3}}\put(230,60){\circle*{3}}\put(229,11){\line(5,3){80}}
\put(225,0){\small{1}}\put(225,67){\small{1}}
\put(250,10){\circle*{3}}\put(250,60){\circle*{3}}\put(230,10){\line(1,0){20}}
\put(245,0){\small{2}}\put(245,67){\small{2}}
\qbezier(310,60)(330,67)(350,60)
\put(270,10){\circle*{3}}\put(270,60){\circle*{3}}\put(250,10){\line(2,1){100}}
\put(265,0){\small{3}}\put(265,67){\small{3}}
\put(290,10){\circle*{3}}\put(290,60){\circle*{3}}\put(270,10){\line(-4,5){40}}
\put(285,0){\small{4}}\put(285,67){\small{4}}
\put(310,10){\circle*{3}}\put(310,60){\circle*{3}}\qbezier(270,10)(290,3)(310,10)
\put(305,0){\small{5}}\put(305,67){\small{5}}
\put(330,10){\circle*{3}}\put(330,60){\circle*{3}}\put(270,60){\line(1,0){20}}
\put(325,0){\small{6}}\put(325,67){\small{6}}
\put(350,10){\circle*{3}}\put(350,60){\circle*{3}}\qbezier(270,60)(250,67)(230,60)
\put(345,0){\small{7}}\put(345,67){\small{7}}
\put(370,10){\circle*{3}}\put(370,60){\circle*{3}}\put(290,10){\line(-4,5){40}}
\put(365,0){\small{8}}\put(365,67){\small{8}}
\put(330,10){\line(-4,5){40}}\put(310,10){\line(1,0){20}}\put(350,10){\line(2,5){20}}
\put(370,10){\line(-4,5){40}}
\end{picture}
\caption{Two graphs representing the same uniform block permutation}\label{F:twographs} 

\end{figure}


Different graphs may represent the same uniform block permutation.
For a graph to represent a uniform block permutation $f:\calA\to\calB$ of $[n]$ the vertex set must consist
of two copies of $[n]$ (top and bottom) and each connected component must contain the same number of vertices on the top as on the bottom. The set partition $\calA$ is read off from the adjacencies on the top, $\calB$ from those on the bottom, and $f$ from those in between.

 The {\em diagram} of $f$ is the unique representing graph in
which all connected components are cycles and the elements in each cycle are joined in order,
as in the second graph of Figure~\ref{F:twographs}.

The set $P_n$ of block permutations of $[n]$ is a monoid.
The product $g\cdot f$ of   two uniform block permutations $f$ and $g$ of $[n]$ is
obtained by gluing the bottom of a graph representing $f$ to the top of a graph representing $g$. The resulting graph represents a uniform block permutation which does not depend on the graphs chosen.   
An example is given in Figure~\ref{F:product}. Note that gluing the diagram of $f$ to the diagram of $g$ may not result in the diagram of $g\cdot f$.

 The identity is the uniform
block permutation that maps $\{i\}$ to $\{i\}$ for all $i$. Viewing permutations as uniform block permutations as above, we get that the symmetric group $S_n$ is a submonoid of $P_n$.

\begin{figure}[!htb]
\begin{picture}(350,70)(0,0)
\put(20,40){\large{$f =$}}
\put(50,60){\circle*{3}}\put(50,40){\circle*{3}}\put(50,40){\line(1,1){20}}
\put(70,60){\circle*{3}}\put(70,40){\circle*{3}}\put(70,40){\line(-1,1){20}}
\put(70,40){\line(1,0){20}}\put(90,40){\line(1,1){20}}\qbezier(50,60)(80,67)(110,60)
\put(90,60){\circle*{3}}\put(90,40){\circle*{3}}\put(110,40){\line(-1,1){20}}
\put(110,60){\circle*{3}}\put(110,40){\circle*{3}}\put(110,40){\line(1,0){20}}
\put(130,60){\circle*{3}}\put(130,40){\circle*{3}}\put(130,40){\line(1,1){20}}
\qbezier(90,60)(120,67)(150,60)
\put(150,60){\circle*{3}}\put(150,40){\circle*{3}}\put(150,40){\line(-1,1){20}}
\put(220,40){\large{$g =$}}
\put(250,60){\circle*{3}}\put(250,40){\circle*{3}}\put(250,40){\line(2,1){40}}
\put(270,60){\circle*{3}}\put(270,40){\circle*{3}}\put(270,40){\line(0,0){20}}
\put(290,60){\circle*{3}}\put(290,40){\circle*{3}}\put(290,40){\line(3,1){60}}
\put(310,60){\circle*{3}}\put(310,40){\circle*{3}}\qbezier(310,40)(330,30)(350,40)
\put(310,40){\line(-3,1){60}}\qbezier(250,60)(290,67)(330,60)
\put(330,60){\circle*{3}}\put(330,40){\circle*{3}}\put(330,40){\line(-1,1){20}}
\put(350,60){\circle*{3}}\put(350,40){\circle*{3}}\put(350,40){\line(-1,1){20}}
\end{picture}
\vskip 0in
\begin{picture}(350,80)(0,0)
\put(40,55){$g\cdot f=$}
\put(100,80){\circle*{3}}\put(100,60){\circle*{3}}\put(100,60){\line(1,1){20}}
\put(120,80){\circle*{3}}\put(120,60){\circle*{3}}\put(120,60){\line(-1,1){20}}
\put(120,60){\line(1,0){20}}\put(140,60){\line(1,1){20}}\qbezier(100,80)(130,87)(160,80)
\put(140,80){\circle*{3}}\put(140,60){\circle*{3}}\put(160,60){\line(-1,1){20}}
\put(160,80){\circle*{3}}\put(160,60){\circle*{3}}\put(160,60){\line(1,0){20}}
\put(180,80){\circle*{3}}\put(180,60){\circle*{3}}\put(180,60){\line(1,1){20}}
\qbezier(140,80)(170,87)(200,80)
\put(200,80){\circle*{3}}\put(200,60){\circle*{3}}\put(200,60){\line(-1,1){20}}
\put(100,45){\circle*{3}}\put(100,25){\circle*{3}}\put(100,25){\line(2,1){40}}
\put(100,45){\line(0,0){15}}
\put(120,45){\circle*{3}}\put(120,25){\circle*{3}}\put(120,25){\line(0,0){20}}
\put(120,45){\line(0,0){15}}
\put(140,45){\circle*{3}}\put(140,25){\circle*{3}}\put(140,25){\line(3,1){60}}
\put(140,45){\line(0,0){15}}
\put(160,45){\circle*{3}}\put(160,25){\circle*{3}}\qbezier(160,25)(180,15)(200,25)
\put(160,45){\line(0,0){15}}
\put(160,25){\line(-3,1){60}}\qbezier(100,45)(130,52)(180,45)
\put(180,45){\circle*{3}}\put(180,25){\circle*{3}}\put(180,25){\line(-1,1){20}}
\put(180,45){\line(0,0){15}}
\put(200,45){\circle*{3}}\put(200,25){\circle*{3}}\put(200,25){\line(-1,1){20}}
\put(200,45){\line(0,0){15}}
\put(220,55){$=$}

\put(250,65){\circle*{3}}\put(250,45){\circle*{3}}\put(250,45){\line(0,0){20}}
\put(250,45){\line(1,0){20}}\qbezier(250,65)(280,72)(310,65)
\put(270,65){\circle*{3}}\put(270,45){\circle*{3}}\put(270,45){\line(2,1){40}}
\put(290,65){\circle*{3}}\put(290,45){\circle*{3}}\put(290,45){\line(2,1){40}}
\put(310,65){\circle*{3}}\put(310,45){\circle*{3}}\put(310,45){\line(1,0){20}}
\put(310,45){\line(-2,1){40}}\put(270,65){\line(1,0){20}}\qbezier(290,65)(320,72)(350,65)
\put(330,65){\circle*{3}}\put(330,45){\circle*{3}}\put(330,45){\line(1,0){20}}
\put(350,65){\circle*{3}}\put(350,45){\circle*{3}}\put(350,45){\line(0,0){20}}
\end{picture}
\caption{Product of uniform block permutations}\label{F:product}
\end{figure}

%The linear span of uniform block permutations over $\mathbb{C}$ together with the product 
%described above forms a unital algebra which we denote $\field P_n$. We set 
%$\field P_0=\field P_1=\mathbb{C}$.
%We can identify the uniform block permutations which permute blocks of size 1 with the elements 
%of the symmetric group $S_n$.  The product on these uniform block permutations is the usual 
%composition of functions. Hence, $\mathbb{C}S_n$ is a subalgebra of $\field P_n$. 
%\vskip 0in
%The type of a set partition $D$ is a partition of $n$, $(d_1,d_2,\ldots, d_k)$ such that $d_i$ is the
%size of block $D_j$ in $D$.  The number of set partitions of type $(d_1,d_2, \ldots, d_k)$ where 
%$m_i$ is the number of times a block of size $i$ occurs in $D$ is given by:
%$$ \frac{n!}{m_1! \cdots m_n! d_1!\cdots d_k!}.$$


We recall a presentation of the monoid $P_n$ given in \cite{f,k00,k01}.
Consider the uniform block permutations $b_i$ and $s_i$ with diagrams

\begin{picture}(375,80)(0,0)
%$b_i$
\put(20,35){\large{$b_i =$}}
\put(50,60){\circle*{3}}\put(50,20){\circle*{3}}\put(50,20){\line(0,0){40}}
\put(45,67){\tiny{1}}\put(45,10){\tiny{1}}
\put(60,35){\Large{$\cdots$}}
\put(90,60){\circle*{3}}\put(90,20){\circle*{3}}\put(90,20){\line(0,0){40}}
\put(80,67){\tiny{$i-1$}}\put(80,10){\tiny{$i-1$}}
\put(105,60){\circle*{3}}\put(105,20){\circle*{3}}\put(105,20){\line(0,0){40}}
\put(103,67){\tiny{$i$}}\put(103,10){\tiny{$i$}}
\put(105,60){\line(1,0){15}}\put(105,20){\line(1,0){15}}
\put(120,60){\circle*{3}}\put(120,20){\circle*{3}}\put(120,20){\line(0,0){40}}
\put(115,67){\tiny{$i+1$}}\put(115,10){\tiny{$i+1$}}
\put(135,60){\circle*{3}}\put(135,20){\circle*{3}}\put(135,20){\line(0,0){40}}
\put(135,67){\tiny{$i+2$}}\put(135,10){\tiny{$i+2$}}
\put(145,35){\Large{$\cdots$}}
\put(175,60){\circle*{3}}\put(175,20){\circle*{3}}\put(175,20){\line(0,0){40}}
\put(173,67){\tiny{$n$}}\put(173,10){\tiny{$n$}}
%$s_i$
\put(220,35){\large{$s_i =$}}
\put(250,60){\circle*{3}}\put(250,20){\circle*{3}}\put(250,20){\line(0,0){40}}
\put(245,67){\tiny{1}}\put(245,10){\tiny{1}}
\put(260,35){\Large{$\cdots$}}
\put(290,60){\circle*{3}}\put(290,20){\circle*{3}}\put(290,20){\line(0,0){40}}
\put(280,67){\tiny{$i-1$}}\put(280,10){\tiny{$i-1$}}
\put(305,60){\circle*{3}}\put(305,20){\circle*{3}}\put(304,21){\line(2,5){15}}
\put(303,67){\tiny{$i$}}\put(303,10){\tiny{$i$}}
\put(320,60){\circle*{3}}\put(320,20){\circle*{3}}\put(321,21){\line(-2,5){15}}
\put(315,67){\tiny{$i+1$}}\put(315,10){\tiny{$i+1$}}
\put(335,60){\circle*{3}}\put(335,20){\circle*{3}}\put(335,20){\line(0,0){40}}
\put(335,67){\tiny{$i+2$}}\put(335,10){\tiny{$i+2$}}
\put(345,35){\Large{$\cdots$}}
\put(375,60){\circle*{3}}\put(375,20){\circle*{3}}\put(375,20){\line(0,0){40}}
\put(373,67){\tiny{$n$}}\put(373,10){\tiny{$n$}}
\end{picture}

The monoid $P_n$ is generated by the 
elements $\{ b_i, s_i\, |\, 1\leq i\leq n-1\}$ subject to the following relations:
\begin{enumerate}
\item $s_i^2 =1, \qquad b_i^2 =b_i, \qquad 1\leq i \leq n-1$;
\item $s_is_{i+1}s_i=s_{i+1}s_is_{i+1}, \qquad s_ib_{i+1}s_i=s_{i+1}b_is_{i+1}, \qquad 1\leq i\leq n-2$;
\item $s_is_j=s_js_i, \qquad b_is_j=s_jb_i, \qquad |i-j|>1$;
\item $ b_is_i=s_ib_i=b_i, \qquad 1\leq i \leq n-1$;
\item $ b_ib_j=b_jb_i,\qquad 1\leq i,j\leq n-1$.
\end{enumerate}

The submonoid generated by the elements $s_i$, $1\leq i\leq n-1$ is the symmetric group $S_n$, viewed as a submonoid of $P_n$ as above.
% Together with $b_1$ they generate $P_n$, by the second relation in 2.

We will see in Sections~\ref{S:selfdual} and~\ref{S:weak} that $P_n$ is a factorizable inverse monoid. Therefore, a presentation for $P_n$ may also be derived from
the results of~\cite{eef}.



%------------------------------------------------------------------------------------------

\subsection{An ideal indexed by set partitions}\label{S:ideal}

Let $\field P_n$ be the monoid algebra of $P_n$ over a commutative ring $\field$.

Given a set partition $\calA\vdash [n]$,  let $Z_\calA\in\field P_n$ denote the sum of all uniform block permutations $f:\calA\to\calB$, where $\calB$ varies:
$$Z_\calA:=\sum_{f:\calA\to\calB}f\,.$$
For instance,
\vskip 0in 
\begin{picture}(400,45)(0,0)
\put(0,15){$Z_{\{1,3\}\{2,4\}}=$}
\put(70,10){\circle*{3}}\put(80,10){\circle*{3}}\put(90,10){\circle*{3}} \put(100,10){\circle*{3}}
\put(70,30){\circle*{3}}\put(80,30){\circle*{3}}\put(90,30){\circle*{3}} \put(100,30){\circle*{3}}
\qbezier(70,30)(80,37)(90,30)\qbezier(80,30)(90,37)(100,30)\put(70,10){\line(1,0){10}}\put(90,10){\line(1,0){10}}
\put(70,10){\line(0,0){20}}\put(80,10){\line(1,2){10}}\put(90,10){\line(-1,2){10}}\put(100,10){\line(0,0){20}}
\put(110,17){$+$}
\put(130,10){\circle*{3}}\put(140,10){\circle*{3}}\put(150,10){\circle*{3}} \put(160,10){\circle*{3}}
\put(130,30){\circle*{3}}\put(140,30){\circle*{3}}\put(150,30){\circle*{3}} \put(160,30){\circle*{3}}
\qbezier(130,30)(140,37)(150,30)\qbezier(140,30)(150,37)(160,30)\put(130,10){\line(0,0){20}}
\qbezier(130,10)(140,17)(150,10)\qbezier(140,10)(150,17)(160,10)\put(140,10){\line(0,0){20}}
\put(150,10){\line(0,0){20}}\put(160,10){\line(0,0){20}}
\put(170,17){$+$}
\put(190,10){\circle*{3}}\put(200,10){\circle*{3}}\put(210,10){\circle*{3}} \put(220,10){\circle*{3}}
\put(190,30){\circle*{3}}\put(200,30){\circle*{3}}\put(210,30){\circle*{3}} \put(220,30){\circle*{3}}
\qbezier(190,30)(200,37)(210,30)\qbezier(200,30)(210,37)(220,30)\put(190,10){\line(0,0){20}}
\qbezier(190,10)(205,17)(220,10)\put(200,10){\line(1,0){10}}\put(200,10){\line(0,0){20}}
\put(210,10){\line(1,2){10}}\put(220,10){\line(-1,2){10}}
\put(230,15){$+$}
\put(250,10){\circle*{3}}\put(260,10){\circle*{3}}\put(270,10){\circle*{3}} \put(280,10){\circle*{3}}
\put(250,30){\circle*{3}}\put(260,30){\circle*{3}}\put(270,30){\circle*{3}} \put(280,30){\circle*{3}}
\qbezier(250,30)(260,37)(270,30)\qbezier(260,30)(270,37)(280,30)\put(250,10){\line(1,2){10}}
\qbezier(250,10)(265,17)(280,10)\put(260,10){\line(1,0){10}}\put(260,10){\line(-1,2){10}}
\put(270,10){\line(0,0){20}}\put(280,10){\line(0,0){20}}
\put(290,15){$+$}
\put(310,10){\circle*{3}}\put(320,10){\circle*{3}}\put(330,10){\circle*{3}} \put(340,10){\circle*{3}}
\put(310,30){\circle*{3}}\put(320,30){\circle*{3}}\put(330,30){\circle*{3}} \put(340,30){\circle*{3}}
\qbezier(310,30)(320,37)(330,30)\qbezier(320,30)(330,37)(340,30)\put(310,10){\line(1,2){10}}
\qbezier(310,10)(320,17)(330,10)\qbezier(320,10)(330,17)(340,10)\put(320,10){\line(-1,2){10}}
\put(330,10){\line(1,2){10}}\put(340,10){\line(-1,2){10}}
\put(350,15){$+$}
\put(370,10){\circle*{3}}\put(380,10){\circle*{3}}\put(390,10){\circle*{3}} \put(400,10){\circle*{3}}
\put(370,30){\circle*{3}}\put(380,30){\circle*{3}}\put(390,30){\circle*{3}} \put(400,30){\circle*{3}}
\qbezier(370,30)(380,37)(390,30)\qbezier(380,30)(390,37)(400,30)\put(370,10){\line(1,2){10}}
\put(370,10){\line(1,0){10}}\put(390,10){\line(1,0){10}}\put(380,10){\line(1,1){20}}
\put(390,10){\line(-1,1){20}}\put(400,10){\line(-1,2){10}}
\end{picture}

\begin{lemma} Let $\calA$ be a set partition of $[n]$ and $\sigma$ a permutation of $[n]$. Then
 \[\sigma \cdot Z_\calA= Z_\calA \text{ \ and \ }Z_\calA \cdot \sigma = Z_{\sigma^{-1}(\calA)}\,.\]
 In addition,
\[Z_\calA\cdot b_i= \left\{ \begin{array}{ll} Z_\calA & \mbox{if $i$ and $i+1$ belong to the same block of $\calA$}\\
\rule{0pt}{20pt}{|A|+|A'|\choose |A|} Z_\calB  & \mbox{if $i$ and $i+1$ belong to different blocks $A$ and $A'$ of $\calA$}\end{array} \right. \] 
where the set partition $\calB$ is obtained by merging the blocks $A$ and $A'$ of $\calA$ and keeping the others. 
\end{lemma}

% These properties follow from finer properties, for instance \[\sigma\cdot\id_{\calA}=\id_{\sigma(\calA)}\cdot\sigma\,.\]

Let $\calZ_n$ denote the subspace of $\field P_n$ linearly spanned by the elements $Z_\calA$ as $\calA$ runs over all set partitions of $[n]$.

\begin{cor}\label{C:ideal}
$\calZ_n$ is a right ideal of the monoid algebra $\field P_n$. 
\end{cor}


%------------------------------------------------------------------------------------------  

\section{The Hopf algebra of uniform block permutations}
In this section we define the Hopf algebra of uniform block permutations. It contains the
Hopf algebra of permutations of Malvenuto and Reutenauer as a Hopf subalgebra.

\subsection{Schur-Weyl duality for uniform block permutations}
%\subsection{Action of $\field P_n$ on $V^{\otimes k}$}

Let $r$ and $m$ be positive integers. Consider the complex reflection group
\[G(r,1,m):=\Z_r\wr S_m\,.\]
Let $t$ denote the generator of the cyclic group $\Z_r$, $t^r=1$.

Let $V$ be the {\em monomial} representation of $G(r,1,m)$. Thus, $V$ is
an $m$-dimensional vector space with a  basis $\{ e_1,e_2,\ldots, e_m\}$ on which  $G(r,1,m)$ acts as follows:
\[t\cdot e_1 = e^{2\pi i/r} e_1\,,\quad t\cdot e_i =e_i \text{ for  $i>1$, and \ }
\sigma\cdot e_i = e_{\sigma(i)} �\text{ for $\sigma \in S_m$.}\]

Consider now the diagonal action of $G(r,1,m)$ on the tensor powers $V^{\otimes n}$,
\[�g\cdot (e_{i_1}e_{i_2}\cdots e_{i_n}) =(g\cdot e_{i_1})(g\cdot e_{i_2}) \cdots (g\cdot e_{i_n})\,.\]
The centralizer of this representation has been calculated by Tanabe.
\begin{prop}~\cite{t} \label{P:block-duality}
There is a right action of the monoid $P_n$ on $V^{\otimes n}$ determined by
\[(e_{i_1}\cdots e_{i_n})\cdot b_j=\delta(i_j,i_{j+1})e_{i_1}\cdots e_{i_n} \text{ \ and \ } (e_{i_1}\cdots e_{i_n})\cdot\sigma= e_{i_{\sigma(1)}}\cdots e_{i_{\sigma(n)}}\]
for $1\leq i\leq n-1$ and   $\sigma\in S_n$. This action commutes with the left action of $G(r,1,m)$ on $V^{\otimes n}$.
Moreover, if $m\geq 2n$ and $r>n$ then the resulting map
\begin{equation} \label{E:block-duality}
\C P_n\to \End_{G(r,1,m)}(V^{\otimes n})
\end{equation}
is an isomorphism of algebras.
\end{prop}
Classical Schur-Weyl duality states that the symmetric group algebra can be similarly recovered from the diagonal action of $GL(V)$ on $V^{\otimes n}$: if $\dim V\geq n$ then
\begin{equation} \label{E:classical-duality}
\C S_n\cong \End_{GL(V)}(V^{\otimes n})\,.
\end{equation}
Malvenuto and Reutenauer~\cite{mr} deduce from here
 the existence of a multiplication among permutations as follows. 
 Given $\sigma\in S_p$ and $\tau\in S_q$, view them as linear endomorphisms
 of the tensor algebra
 \[T(V):=\bigoplus_{n\geq 0}V^{\otimes n}\]
 by means of~\eqref{E:classical-duality} ($\sigma$ acts as $0$ on $V^{\otimes n}$ if $n\neq p$, similarly for $\tau$). The tensor algebra is a Hopf algebra, so we can form the {\em convolution} product of any two linear endomorphisms:
 \[T(V)\map{\Delta}T(V)\otimes T(V)\map{\sigma\otimes\tau}T(V)\otimes T(V)\map{m}T(V)\,,\]
 where $\Delta$ and $m$ are the coproduct and product of the tensor algebra. 
 Since these two maps commute with the action of $GL(V)$, the convolution  of $\sigma$ and $\tau$ belongs to $\End_{GL(V)}(V^{\otimes n})$, where $n=p+q$.
 Therefore, there exist an element $\sigma\ast\tau\in\C S_n$ whose right action
 equals the convolution  of $\sigma$ and $\tau$. This is the product of Malvenuto and Reutenauer.
 
The same argument applies to uniform block permutations, in view of Proposition~\ref{P:block-duality}. We proceed to describe the resulting operation
in explicit terms. As for permutations, this structure can be enlarged to that
of a graded Hopf algebra.
 
\subsection{Product and coproduct of uniform block permutations}

Consider the graded vector space 
$$\calP:=\bigoplus_{n\geq 0} \field P_n\,.$$
$P_0$ consists of the unique uniform block permutation of $[n]$, represented by the empty diagram, which we denote by $\emptyset$.

 Let $f$ and  $g$ be uniform block permutations of $[n]$ and $[m]$ respectively.
 Adding $n$ to every entry in the diagram of $g$ and placing it to the right of the
 diagram of $f$ we obtain the diagram of a uniform block permutation of $[n+m]$, called the concatenation of $f$ and $g$ and denoted  $f\times g$. Figure~\ref{F:concatenation} shows an example.

\begin{figure}[!htb]
\begin{picture}(290,100)(0,0)
\put(40,75){$f=$} \put(70,90){\circle*{3}}\put(70,70){\circle*{3}}\put(70,70){\line(2,1){40}}
\put(90,90){\circle*{3}}\put(90,70){\circle*{3}}\put(90,70){\line(-1,1){20}}
\put(110,90){\circle*{3}}\put(110,70){\circle*{3}}\put(110,70){\line(-1,1){20}}
\put(130,90){\circle*{3}}\put(130,70){\circle*{3}}\put(110,70){\line(1,0){20}}
\put(130,70){\line(0,0){20}}\qbezier(90,90)(110,97)(130,90)
\put(68,95){\tiny{1}}\put(88,95){\tiny{2}}\put(108,95){\tiny{3}}\put(128,95){\tiny{4}}
\put(68,63){\tiny{1}}\put(88,63){\tiny{2}}\put(108,63){\tiny{3}}\put(128,63){\tiny{4}}
\put(135,70){\Large{,}}
\put(170,75){$g=$}\put(200,90){\circle*{3}}\put(200,70){\circle*{3}}\qbezier(200,70)(220,60)(240,70)
\put(240,70){\line(1,0){20}}\put(260,70){\line(1,1){20}}\put(220,90){\line(1,0){20}}
\put(220,90){\circle*{3}}\put(220,70){\circle*{3}}\put(200,70){\line(1,1){20}}
\put(240,90){\circle*{3}}\put(240,70){\circle*{3}}\qbezier(240,90)(260,97)(280,90)
\put(260,90){\circle*{3}}\put(260,70){\circle*{3}}\put(280,70){\line(-4,1){80}}
\put(280,90){\circle*{3}}\put(280,70){\circle*{3}}\put(220,70){\line(2,1){40}}
\put(198,95){\tiny{1}}\put(218,95){\tiny{2}}\put(238,95){\tiny{3}}\put(258,95){\tiny{4}}
\put(278,95){\tiny{5}}\put(198,63){\tiny{1}}\put(218,63){\tiny{2}}\put(238,63){\tiny{3}}
\put(258,63){\tiny{4}}\put(278,63){\tiny{5}}
\put(80,25){$f\times g=$}
\put(130,40){\circle*{3}}\put(130,20){\circle*{3}}\put(130,20){\line(2,1){40}}
\put(150,40){\circle*{3}}\put(150,20){\circle*{3}}\put(150,20){\line(-1,1){20}}
\put(170,40){\circle*{3}}\put(170,20){\circle*{3}}\put(170,20){\line(-1,1){20}}
\put(190,40){\circle*{3}}\put(190,20){\circle*{3}}\put(170,20){\line(1,0){20}}
\put(190,20){\line(0,0){20}}\qbezier(150,40)(170,47)(190,40)
\put(128,45){\tiny{1}}\put(148,45){\tiny{2}}\put(168,45){\tiny{3}}\put(188,45){\tiny{4}}
\put(208,45){\tiny{5}}\put(228,45){\tiny{6}}\put(248,45){\tiny{7}}\put(268,45){\tiny{8}}
\put(288,45){\tiny{9}}
\put(128,13){\tiny{1}}\put(148,13){\tiny{2}}\put(168,13){\tiny{3}}\put(188,13){\tiny{4}}
\put(208,13){\tiny{5}}\put(228,13){\tiny{6}}\put(248,13){\tiny{7}}\put(268,13){\tiny{8}}
\put(288,13){\tiny{9}}
\put(210,40){\circle*{3}}\put(210,20){\circle*{3}}\qbezier(210,20)(230,10)(250,20)
\put(250,20){\line(1,0){20}}\put(270,20){\line(1,1){20}}\put(230,40){\line(1,0){20}}
\put(230,40){\circle*{3}}\put(230,20){\circle*{3}}\put(210,20){\line(1,1){20}}
\put(250,40){\circle*{3}}\put(250,20){\circle*{3}}\qbezier(250,40)(270,47)(290,40)
\put(270,40){\circle*{3}}\put(270,20){\circle*{3}}\put(290,20){\line(-4,1){80}}
\put(290,40){\circle*{3}}\put(290,20){\circle*{3}}\put(230,20){\line(2,1){40}}
\end{picture}
\caption{Concatenation of diagrams} \label{F:concatenation}
\end{figure}

Let $\Sh(n,m)$ denote the set of  $(n,m)$-shuffles, that is, those 
 permutations $\xi \in S_{n+m}$ such that 
$$\xi(1)<\xi(2)< \cdots < \xi(n) \mbox{ \ and \ } \xi(n+1)<\xi(n+2)<\cdots < \xi(n+m)\,.$$
Let $sh_{n,m}\in \field S_{n+m}$ denote the sum of all $(n,m)$-shuffles.  

The product $\ast$ on 
$\calP$ is defined by 
$$f\ast g := sh_{n,m}\cdot (f\times g)\in \field P_{n+m}$$
for all $f \in P_n$ and $g \in P_m$, and extended by linearity.  It is easy to see that this product corresponds to convolution of endomorphisms of the tensor algebra via the map~\eqref{E:block-duality}, when $\field=\C$.

For example,

\begin{picture}(410,80)(0,0)
\put(0,70){\circle*{3}}\put(0,55){\circle*{3}}\put(0,55){\line(1,0){15}}
\put(15,70){\circle*{3}}\put(15,55){\circle*{3}}\put(0,70){\line(1,0){15}}
\put(0,55){\line(0,0){15}}\put(15,55){\line(0,0){15}} \put(22,60){$\ast$}
\put(35,70){\circle*{3}}\put(35,55){\circle*{3}}\put(35,55){\line(1,1){15}}
\put(50,70){\circle*{3}}\put(50,55){\circle*{3}}\put(50,55){\line(-1,1){15}}
\put(60,60){$=$}
\put(75,70){\circle*{3}}\put(75,55){\circle*{3}}\put(75,55){\line(1,0){15}}
\put(90,70){\circle*{3}}\put(90,55){\circle*{3}}\put(75,55){\line(0,0){15}}
\put(105,70){\circle*{3}}\put(105,55){\circle*{3}}\put(75,70){\line(1,0){15}}
\put(120,70){\circle*{3}}\put(120,55){\circle*{3}}\put(90,55){\line(0,0){15}}
\put(105,55){\line(1,1){15}}\put(120,55){\line(-1,1){15}}
\put(127,60){$+$}
\put(145,70){\circle*{3}}\put(145,55){\circle*{3}}\put(145,70){\line(1,0){15}}
\put(160,70){\circle*{3}}\put(160,55){\circle*{3}}\put(145,55){\line(0,0){15}}
\put(175,70){\circle*{3}}\put(175,55){\circle*{3}}\qbezier(145,55)(160,45)(175,55)
\put(190,70){\circle*{3}}\put(190,55){\circle*{3}}\put(175,55){\line(-1,1){15}}
\put(160,55){\line(2,1){30}}\put(190,55){\line(-1,1){15}}
\put(197,60){$+$}
\put(215,70){\circle*{3}}\put(215,55){\circle*{3}}\put(215,70){\line(1,0){15}}
\put(230,70){\circle*{3}}\put(230,55){\circle*{3}}\put(215,55){\line(0,0){15}}
\put(245,70){\circle*{3}}\put(245,55){\circle*{3}}\qbezier(215,55)(237,45)(260,55)
\put(260,70){\circle*{3}}\put(260,55){\circle*{3}}\put(260,55){\line(-2,1){30}}
\put(230,55){\line(2,1){30}}\put(245,55){\line(0,0){15}}
\put(267,60){$+$}
\put(285,70){\circle*{3}}\put(285,55){\circle*{3}}\put(285,70){\line(1,0){15}}
\put(300,70){\circle*{3}}\put(300,55){\circle*{3}}\put(300,55){\line(1,0){15}}
\put(315,70){\circle*{3}}\put(315,55){\circle*{3}}\put(300,55){\line(-1,1){15}}
\put(330,70){\circle*{3}}\put(330,55){\circle*{3}}\put(315,55){\line(-1,1){15}}
\put(285,55){\line(3,1){45}}\put(330,55){\line(-1,1){15}}
\put(337,60){$+$}
\put(355,70){\circle*{3}}\put(355,55){\circle*{3}}\put(355,70){\line(1,0){15}}
\put(370,70){\circle*{3}}\put(370,55){\circle*{3}}\put(370,55){\line(-1,1){15}}
\put(385,70){\circle*{3}}\put(385,55){\circle*{3}}\qbezier(370,55)(385,45)(400,55)
\put(400,70){\circle*{3}}\put(400,55){\circle*{3}}\put(400,55){\line(-2,1){30}}
\put(355,55){\line(3,1){45}}\put(385,55){\line(0,0){15}}
\put(407,60){$+$}
\put(75,35){\circle*{3}}\put(75,20){\circle*{3}}\put(75,35){\line(1,0){15}}
\put(90,35){\circle*{3}}\put(90,20){\circle*{3}}\put(105,20){\line(1,0){15}}
\put(105,35){\circle*{3}}\put(105,20){\circle*{3}}\put(105,20){\line(-2,1){30}}
\put(120,35){\circle*{3}}\put(120,20){\circle*{3}}\put(120,20){\line(-2,1){30}}
\put(75,20){\line(3,1){45}}\put(90,20){\line(1,1){15}}
\end{picture} 


\medskip

A \emph{breaking point} of a set partition $\calB$ is an integer $i\in \{0,1,\ldots, n\}$ for which there exists a subset $S\subseteq\calB$
such that
\[\bigcup_{B\in S} B =\{1,\ldots,i\} \text{ \ (and hence) \ } \bigcup_{B\in \calB\setminus S} B =\{i+1,\ldots,n\}\,.\]
Given a uniform block permutation  $f:\calA\to\calB$, let $B(f)$ denote the set of breaking points of $\calB$.
Note that $i=0$ and $i=n$ are  breaking points of any $f$. 
If $f$ is a permutation, that is if all blocks of $f$ are of size $1$, then  $B(f)=\{0,1,\ldots, n\}$. 

In terms of the diagram  of a uniform block permutation, if it is possible to put a vertical line between the first $i$
and the last $n-i$ vertices in the bottom row without intersecting an edge between the two sets of vertices, then $i$ is a breaking point. 

\begin{picture}(250,60)(0,0)
\put(30,25){$f=$}
\put(60,10){\red{\dashbox{1}(0,18){}}}
\put(70,40){\circle*{3}}\put(70,20){\circle*{3}}\put(70,20){\line(1,1){20}}
\put(80,10){\red{\dashbox{1}(0,18){}}}
\put(90,40){\circle*{3}}\put(90,20){\circle*{3}}\put(90,20){\line(3,1){60}}
\put(100,10){\red{\dashbox{1}(0,12){}}}
\put(110,40){\circle*{3}}\put(110,20){\circle*{3}}\put(110,20){\line(-2,1){40}}
\put(130,40){\circle*{3}}\put(130,20){\circle*{3}}\qbezier(110,20)(140,10)(170,20)
\put(150,40){\circle*{3}}\put(150,20){\circle*{3}}\put(130,20){\line(0,0){20}}
\put(170,40){\circle*{3}}\put(170,20){\circle*{3}}\put(150,20){\line(1,1){20}}
\put(180,10){\red{\dashbox{1}(0,18){}}}\put(190,40){\circle*{3}}\put(190,20){\circle*{3}}\put(170,20){\line(-3,1){60}}
\put(210,40){\circle*{3}}\put(210,20){\circle*{3}}\qbezier(70,40)(90,47)(110,40)
\put(190,20){\line(0,0){20}}\put(190,20){\line(1,0){20}}
\put(210,20){\line(0,0){20}}\put(190,40){\line(1,0){20}}
\put(220,10){\red{\dashbox{1}(0,18){}}}
\put(230,25){  $\Rightarrow \ \  B(f)=\{0,1,2,6,8\}$.}
\end{picture} 

\begin{lemma}\label{L:break}
If $i$ is a breaking point of $f$, then there exists a unique $(i,n-i)$-shuffle $\xi\in S_n$ and
unique uniform block permutations $f_{(i)} \in P_i$ and $f_{(n-i)}'\in  P_{n-i}$ such that
$$f=(f_{(i)}\times f'_{(n-i)})\cdot \xi^{-1}\,.$$
Conversely, if such a decomposition exists, $i$ is a breaking point of $f$.
\end{lemma} 
We illustrate this statement with an example where $i=4$ and 
$\xi=\mat{1 & 2 & 3 & 4 & 5 & 6\\2 & 3 & 5 & 6 & 1 & 4}$: 

\begin{center}
\begin{picture}(100,60)(0,-10)
\put(0,0){\circle*{3}}\put(0,40){\circle*{3}}\put(0,40){\line(4,-1){80}}
\put(20,0){\circle*{3}}\put(20,40){\circle*{3}}\put(20,40){\line(-1,-1){20}}
\put(40,0){\circle*{3}}\put(40,40){\circle*{3}}\put(40,40){\line(-1,-1){20}}
\put(60,0){\circle*{3}}\put(60,40){\circle*{3}}\put(60,40){\line(2,-1){40}}
\put(80,0){\circle*{3}}\put(80,40){\circle*{3}}\put(80,40){\line(-2,-1){40}}
\put(100,0){\circle*{3}}\put(100,40){\circle*{3}}\put(100,40){\line(-2,-1){40}}
\put(0,0){\dashbox{1}(0,20){}} \put(60,0){\dashbox{1}(0,20){}} \put(0,0){\dashbox{1}(60,0){}}\put(0,20){\dashbox{1}(60,0){}}
\put(80,0){\dashbox{1}(0,20){}} \put(100,0){\dashbox{1}(0,20){}} \put(80,0){\dashbox{1}(20,0){}}\put(80,20){\dashbox{1}(20,0){}}
\put(70,-10){\red{\dashbox{1}(0,20){}}}
\put(23,7){$f_{(4)}$} \put(83,7){$f'_{(2)}$}
\put(-35,17){$f=$} \put(110,25){$=\xi^{-1}$}
\end{picture}
\end{center}

\medskip

%%%%%%%%%%     OLD PICTURE
%\begin{picture}(100,60)(0,-10)
%\put(0,0){\circle*{3}}\put(0,40){\circle*{3}}\put(0,40){\line(1,-1){20}}
%\put(20,0){\circle*{3}}\put(20,40){\circle*{3}}\put(20,40){\line(1,-1){20}}
%\put(40,0){\circle*{3}}\put(40,40){\circle*{3}}\put(40,40){\line(2,-1){40}}
%\put(60,0){\circle*{3}}\put(60,40){\circle*{3}}\put(60,40){\line(2,-1){40}}
%\put(80,0){\circle*{3}}\put(80,40){\circle*{3}}\put(80,40){\line(-4,-1){80}}
%\put(100,0){\circle*{3}}\put(100,40){\circle*{3}}\put(100,40){\line(-2,-1){40}}
%\put(0,0){\dashbox{1}(0,20){}} \put(60,0){\dashbox{1}(0,20){}} \put(0,0){\dashbox{1}(60,0){}}\put(0,20){\dashbox{1}(60,0){}}
%\put(80,0){\dashbox{1}(0,20){}} \put(100,0){\dashbox{1}(0,20){}} \put(80,0){\dashbox{1}(20,0){}}\put(80,20){\dashbox{1}(20,0){}}
%\put(70,-10){\red{\dashbox{1}(0,20){}}}
%\put(23,7){$f_{(4)}$} \put(83,7){$f'_{(2)}$}
%\put(-35,17){$f=$} \put(110,25){$=\xi$}
%\end{picture}
%%%%%%%%%%%%%%%%%%%%%


% SAVE PROOF FOR LATER BUT OMIT FOR EXTENDED ABSTRACT
%
%\proof
%Let $x$ be uniform block permutation with range $R=\{R_1,R_2,\ldots, R_k\}$. And suppose
%$i$ be a breaking point of $x$, then there exists an integer $t$, $0\leq t\leq n$,
%such that $\{R_1,\ldots, R_t\}$ is a set partition of $[i]$ and $\{R_{t+1},\ldots, R_k\}$
%is a set partition of $\{i+1,i+2,\ldots, n\}$. Consider the inverse image of the set $[i]$:
%$x^{-1}([i])=\bigcup_{j=1}^t x^{-1}(R_j)=\{a_1,a_2,\ldots, a_i\}$, where 
%$1\leq a_1<a_2<\cdots <a_i\leq n$.
%\vskip 0in 
%We also have that $x^{-1}(\{i+1,i+2,\ldots, n\})$ is the complement of $x^{-1}([i])$ in $[n]$
%by definition of uniform block permutation. Suppose that $x^{-1}(\{i+1,i+2,\ldots, n\})=\{a_{i+1},
%a_{i+2},\ldots, a_n\}$, where $1\leq a_{i+1}<a_{i+2}<\cdots< a_n\leq n$. Now define the permutation
%$$w(r)=a_r,\qquad r=1,\ldots, n.$$
%We have that $w(1)<w(2)<\cdots<w(i)$ and $w(i+1)<\cdots< w(n)$. Thus, $w$ is an $(i,n-i)$-shuffle. 
%In order to separate $x$ into two diagrams $w$ must map $[i]$ to $x^{-1}([i])$ which makes $w$ 
%unique. The uniqueness of the shuffle $w$ forces the uniqueness of $x_{(i)}$ and $x_{(n-1)}'$.   
%\endproof

We are now ready to define the coproduct on $\calP$. Given $f\in  P_n$ set
$$\Delta(f):=\sum_{i\in B(f)}f_{(i)}\otimes f'_{(n-i)},$$
where $f_{(i)}$ and $f'_{(n-i)}$ are as in Lemma~\ref{L:break}. An example follows.
\begin{center}
\begin{picture}(320,80)(0,0)
\put(90,60){\large{$f = $}} 
\put(125,55){\circle*{3}}\put(125,70){\circle*{3}}\put(125,55){\line(1,1){15}}
\put(140,55){\circle*{3}}\put(140,70){\circle*{3}}\qbezier(125,55)(140,45)(155,55)
\put(155,55){\circle*{3}}\put(155,70){\circle*{3}}\put(140,55){\line(-1,1){15}}
\put(170,55){\circle*{3}}\put(170,70){\circle*{3}}\put(170,55){\line(-1,1){15}}
\put(185,55){\circle*{3}}\put(185,70){\circle*{3}}\put(170,55){\line(1,0){15}}
\put(200,55){\circle*{3}}\put(200,70){\circle*{3}}\put(185,55){\line(1,1){15}}
\put(200,55){\line(-1,1){15}}\qbezier(140,70)(155,77)(170,70)\qbezier(155,70)(177,77)(200,70)
\put(155,55){\line(1,1){15}}

\put(0,20){\large{$\Delta(f)=$}}
\put(50,20){\large{$f \otimes \emptyset \ + $}}
\put(105,15){\circle*{3}}\put(105,30){\circle*{3}}\put(105,15){\line(1,1){15}}
\put(120,15){\circle*{3}}\put(120,30){\circle*{3}}\qbezier(105,15)(120,5)(135,15)
\put(135,15){\circle*{3}}\put(135,30){\circle*{3}}\put(120,15){\line(-1,1){15}}
\put(135,15){\line(0,0){15}}\put(120,30){\line(1,0){15}}
\put(140,20){\large{$\otimes$}}
\put(155,15){\circle*{3}}\put(155,30){\circle*{3}}\put(155,15){\line(0,0){15}}
\put(170,15){\circle*{3}}\put(170,30){\circle*{3}}\put(155,15){\line(1,0){15}}
\put(185,15){\circle*{3}}\put(185,30){\circle*{3}}\put(170,15){\line(1,1){15}}
\put(185,15){\line(-1,1){15}}\qbezier(155,30)(170,37)(185,30)
\put(190,20){\large{$+$}}
\put(205,15){\circle*{3}}\put(205,30){\circle*{3}}\put(205,15){\line(1,1){15}}
\put(220,15){\circle*{3}}\put(220,30){\circle*{3}}\put(220,15){\line(-1,1){15}}
\put(235,15){\circle*{3}}\put(235,30){\circle*{3}}\qbezier(205,15)(220,5)(235,15)
\put(250,15){\circle*{3}}\put(250,30){\circle*{3}}\put(235,15){\line(1,1){15}}
\put(265,15){\circle*{3}}\put(265,30){\circle*{3}}\put(250,15){\line(-1,1){15}}
\put(250,15){\line(1,0){15}}\put(265,15){\line(0,0){15}}\qbezier(220,30)(235,37)(250,30)
\qbezier(235,30)(250,37)(265,30)
\put(270,20){\large{$\otimes$}}
\put(285,15){\circle*{3}}\put(285,30){\circle*{3}}\put(285,15){\line(0,0){15}}
\put(290,20){\large{$+$}}
\put(305,20){\large{$\emptyset\otimes f$.}}
\end{picture}
\end{center}
\vskip 0in  
Recall that an element $x\in\calP$ is called primitive if $\Delta(x)=x\otimes \emptyset +\emptyset\otimes x$. 
Every uniform block permutation with breaking set $\{ 0, n\}$ is primitive, but there other primitive elements in $\calP$. For example, the following element of $\field P_3$ is primitive:

 \begin{picture}(240,50)(0,0)
 \put(160,20){\circle*{3}}\put(160,35){\circle*{3}}\qbezier(160,35)(175,42)(190,35)
 \put(175,20){\circle*{3}}\put(175,35){\circle*{3}}\put(160,20){\line(0,0){15}}
 \put(190,20){\circle*{3}}\put(190,35){\circle*{3}}\put(160,20){\line(1,0){15}}
 \put(175,20){\line(1,1){15}}\put(190,20){\line(-1,1){15}}
 \put(200,25){$-$}
 \put(220,20){\circle*{3}}\put(220,35){\circle*{3}}\put(220,20){\line(1,0){15}}
 \put(235,20){\circle*{3}}\put(235,35){\circle*{3}}\put(220,20){\line(1,1){15}}
 \put(250,20){\circle*{3}}\put(250,35){\circle*{3}}\put(250,20){\line(-2,1){30}}
 \put(235,20){\line(1,1){15}}\put(235,35){\line(1,0){15}}
 \end{picture}
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Instead of this, we should give here an example of a primitive element that is a non-trivial linear combination.
%
%\begin{picture}(200,50)(0,0)
%\put(120,25){$x = $}
%\put(145,20){\circle*{3}}\put(145,35){\circle*{3}}\qbezier(145,20)(167,10)(190,20)
%\put(160,20){\circle*{3}}\put(160,35){\circle*{3}}\put(145,20){\line(1,1){15}}
%\put(175,20){\circle*{3}}\put(175,35){\circle*{3}}\put(160,20){\line(2,1){30}}
%\put(190,20){\circle*{3}}\put(190,35){\circle*{3}}\put(175,20){\line(-2,1){30}}
%\put(190,20){\line(-1,1){15}}\put(160,35){\line(1,0){15}}
%\put(195,25){ is primitive.}
%\end{picture}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Recall that $\emptyset$ denotes the empty uniform block permutation. 
Let $\varepsilon:\calP\rightarrow \field$ be 
\[\varepsilon(f)=\begin{cases} 1 &\text{ if $f=\emptyset\in P_0$,}\\
0 & \text{ if $f\in  P_n$, $n\geq 1$. }
\end{cases}\]

\begin{theorem}
The graded vector space $\calP$, equipped with the product $\ast$, coproduct $\Delta$, unit $\emptyset$ and counit $\varepsilon$, is a  graded connected Hopf algebra. 
\end{theorem}
 Associativity  and coassociativity follow from basic properties of  shuffles (for the product one may also appeal to~\eqref{E:block-duality} and associativity of the convolution product).
  The existence of the antipode is guaranteed in any graded connected bialgebra.
Compatibility between $\Delta$ and $\ast$ requires a special argument. We sketch part of it. 

Let $\beta_{n,m}$ be the $(n,m)$-shuffle such that 
\[\beta_{n,m}(i)=\begin{cases} m+i & \text{  if $1\leq i\leq n$,}\\
i-n &  \text{  if $n+1\leq i\leq n+m$.}
\end{cases}\]
  The diagram of $\beta_{3,4}$ is shown below.

\begin{picture}(270,60)(0,10)
\put(150,60){\circle*{3}}\put(150,20){\circle*{3}}\put(150,20){\line(3,2){60}}
\put(170,60){\circle*{3}}\put(170,20){\circle*{3}}\put(170,20){\line(3,2){60}}
\put(190,60){\circle*{3}}\put(190,20){\circle*{3}}\put(190,20){\line(3,2){60}}
\put(210,60){\circle*{3}}\put(210,20){\circle*{3}}\put(210,20){\line(3,2){60}}
\put(230,60){\circle*{3}}\put(230,20){\circle*{3}}\put(230,20){\line(-2,1){80}}
\put(250,60){\circle*{3}}\put(250,20){\circle*{3}}\put(250,20){\line(-2,1){80}}
\put(270,60){\circle*{3}}\put(270,20){\circle*{3}}\put(270,20){\line(-2,1){80}}
\end{picture}

The inverse of $\beta_{n,m}$ is $\beta_{m,n}$.

Let $f\in P_n$, $g\in P_m$. A summand in $\Delta(f)\ast \Delta(g)$ is of the form \[\xi_1\cdot (f'\times g')\otimes \xi_2\cdot(f''\times g'')\]
where   $p\in B(f)$, $f'\in P_p$, $f''\in P_{n-p}$, $q\in B(g)$, $g'\in P_q$, $g''\in P_{m-q}$, $\xi_1\in \Sh(p,q)$, $\xi_2\in \Sh(n-p,m-q)$, 
 and there
 exist unique $\eta_1\in \Sh(p,n-p)$ and $\eta_2\in \Sh(q,m-q)$ such that $f\cdot \eta_1=f'\times f''$ and $g\cdot \eta_2=g'\times g''$.  
 
 Let $\beta:=1_p\times \beta_{n-p,q}\times 1_{m-q}$. Then
\begin{eqnarray*}
\xi_1\cdot (f'\times g')\times \xi_2\cdot (f''\times g'') &=& (\xi_1\times \xi_2)\cdot((f'\times g')\times (f''\times g''))\\ &  =& (\xi_1\times \xi_2)\cdot \beta \cdot((f'\times f'')\times(g'\times g''))\cdot \beta^{-1}\\
& =&   (\xi_1\times \xi_2)\cdot\beta\cdot (f\cdot \eta_1\times g\cdot\eta_2)\cdot \beta^{-1}\\
& =& (\xi_1\times \xi_2)\cdot\beta\cdot(f\times g)\cdot (\eta_1\times \eta_2)\cdot \beta^{-1}\,.
\end{eqnarray*}
Let $\xi:=(\xi_1\times \xi_2)\cdot \beta$ and $\eta:=(\eta_1\times \eta_2)\cdot \beta^{-1}$. One verifies that 
$\xi\in \Sh(n,m)$ and $\eta\in \Sh(p+q,n+m-p-q)$. Therefore, 
\[\xi_1\cdot (f'\times g')\times \xi_2\cdot (f''\times g'')=\xi\cdot (f\times g)\cdot \eta\]
is a summand in $\Delta(f\ast g)$.$\quad\Box$


%%%% SAVE FOR LATER, SKIP FOR EXT ABSTRACT %%%%%%%%%%
%In order to prove that $\Delta$ is a morphism of algebras with respect to $\ast$ product
%on $\calP$ we need to introduce some notation.
%We denote by $\beta_{n,m}$ the $(n,m)$-shuffle such that $\beta_{n,m}(i)=m+1$, if $i=1,\ldots, n$ 
%and $\beta_{n,m}(n+j)=j$ for $j=1,\ldots, m$. That is $\beta_{n,m}=(m+1,m+2,\ldots, n+m, 1,2, \ldots, n)$
%\vskip 0.1in 
%\begin{picture}(100,50)(0,0)
%\put(150,40){\circle*{3}}\put(150,20){\circle*{3}}\put(150,20){\line(3,1){60}}
%\put(170,40){\circle*{3}}\put(170,20){\circle*{3}}\put(170,20){\line(3,1){60}}
%\put(190,40){\circle*{3}}\put(190,20){\circle*{3}}\put(190,20){\line(3,1){60}}
%\put(210,40){\circle*{3}}\put(210,20){\circle*{3}}\put(210,20){\line(3,1){60}}
%\put(230,40){\circle*{3}}\put(230,20){\circle*{3}}\put(230,20){\line(-4,1){80}}
%\put(250,40){\circle*{3}}\put(250,20){\circle*{3}}\put(250,20){\line(-4,1){80}}
%\put(270,40){\circle*{3}}\put(270,20){\circle*{3}}\put(270,20){\line(-4,1){80}}
%\put(180,0){Figure 6. $\beta_{3,4}$}
%\end{picture}
%\vskip 0.1in 
%The inverse of $\beta_{n,m}$ is $\beta_{m,n}$. We denote the identity
%permutation in $S_k\subseteq P_k$ by $1_k$. 

%\begin{prop}
%$\Delta$ is an algebra morphism. i.e. $\Delta(x\ast y)=\Delta(x)\ast \Delta(y)$. 
%\end{prop}
%\proof Assume that $x\in \field P_n$ and $y\in \field P_m$. On the left-handside we have
%\begin{eqnarray*}
%\Delta(x\ast y) &= &\Delta\Bigl(\sum_{\xi\in \Sh(n,m)}\xi\cdot(x\times y)\Bigr)\\
%& = & \sum_{\xi\in \Sh(n,m)}\Delta\bigl(\xi\cdot(x\times y)\bigr)\\
%& = & \sum_{\xi\in \Sh(n,m)\atop r\in B(\xi\cdot(x\times y))}a\otimes b
%\end{eqnarray*}
%by Lemma 3.1 we know that for each $r\in B(\xi\cdot(x\times y))$ there exists a unique $(r,n+m-r)$-shuffle
%$\eta$ such that $\xi\cdot(x\times y)\cdot \eta= a\times b$, where $a\in \field P_r$ and 
%$b\in \field P_{n+m-r}$. 
%\vskip 0in   
%On the other hand we have, 
%\begin{eqnarray*}
%\Delta(x)\ast\Delta(y) &=&  \sum_{p\in B(x) \atop q\in B(y)}(x'_{(p)}\ast y'_{(q)})\otimes (x''_{(n-p)}\ast y''_{(m-q)}) \\
%& = &\sum_{\xi_1\in \Sh(p,q) \atop \xi_2\in \Sh(n-p,m-q)} \sum_{p\in B(x)\atop q\in B(y)}\xi_1\cdot(x'_{(p)}\times y'_{(q)})\otimes \xi_2\cdot(x''_{(n-p)}\times y''_{(m-q)}). \end{eqnarray*} 
%By Lemma 3.1  we have that if $p\in B(x)$ and $q\in B(y)$ then there exists unique $\eta_1\in \Sh(p,n-p)$ and
%$\eta_2\in \Sh(q,m-q)$ such that $x\cdot \eta_1=x'_{(p)}\times x''_{(n-p)}$,  $y \cdot\eta_2 =y'_{(q)}\times y''_{(m-q)}$.
%\vskip 0in 
%We show that any element in the left-hanside  also occurs in 
%the righthanside and viceversa.
%
%Consider a summand in $\Delta(x)\ast \Delta(y)$: $\xi_1\cdot (x'\times y')\otimes \xi_2\cdot(x''\times y'')$
%where $a=\xi_1\cdot (x'\times y')\in \field P_{p+q}$ and $b=\xi_2(x''\times y'')\in \field P_{n+m-p-q}$. 
%We know there exists unique $\eta_1\in \Sh(p,n-p)$ and $\eta_2\in \Sh(q,m-q)$ for $p\in B(x)$ and $q\in B(y)$ 
%such that $x\cdot \eta_1=x'\times x''$ and $y\cdot \eta_2=y'\times y''$. We also have $\xi_1\in \Sh(p,q)$ and
%$\xi_2\in \Sh(n-p,m-q)$. Let $\beta=1_p\times \beta_{n-p,q}\times 1_{m-q}$, then
%\begin{eqnarray*}
%\xi_1\cdot (x'\times y')\times \xi_2(x''\times y'') &=& (\xi_1\times \xi_2)\cdot((x'\times y')\times (x''\times y''))\\ &  =& (\xi_1\times \xi_2)\cdot \beta \cdot((x'\times x'')\times(y'\times y''))\cdot \beta^{-1}\\
%& =&   (\xi_1\times \xi_2)\cdot\beta\cdot (x\cdot \eta_1\times y\cdot\eta_2)\cdot \beta^{-1}\\
%& =& (\xi_1\times \xi_2)\cdot\beta\cdot(x\times y)\cdot (\eta_1\times \eta_2)\cdot \beta^{-1}
%\end{eqnarray*}
%Note that since $\xi_1$ is a $(p,q)$-shuffle and $\xi_2$ is a $(n-p,m-q)$-shuffle we have that 
%$$\xi_1(1)<\cdots <\xi_1(p)<\xi_2(p+q+1)<\cdots <\xi_2(n+q)$$
%and 
%$$\xi_1(p+1)<\cdots < \xi_1(p+q)<\xi_2(n+q+1)<\cdots < \xi_2(n+m).$$
%Since $\beta(p+i)=p+q+i$ for $1\leq i\leq n-p$, $\beta(n+i)=p+i$ for $1\leq i\leq q$, and $\beta(i)=i$ 
%for all other $i$.  Then we have that $\xi_1(\beta(1))<\cdots <\xi_1(\beta(p))<\xi_2(\beta(p+1))<\cdots
%<\xi_2(\beta(n))$ and 
%$\xi_1(\beta(n+1))<\cdots <\xi_1(\beta(n+q))<\xi_2(\beta(n+q+1))<\cdots <\xi_2(\beta(n+m))$. Hence, 
%$(\xi_1\times \xi_2)\cdot \beta\in \Sh(n,m)$.
%Similarly, we can show that $(\eta_1\times \eta_2)\cdot \beta^{-1}\in \Sh(p+q,n+m-p-q)$. Therefore, 
%we have by Lemma 3.1 that $(\eta_1\times \eta_2)\cdot \beta^{-1}$ is the unique shuffle for the 
%break point $p+q$ such that $\xi\cdot (x\times y)\cdot \eta=a\times b$, where 
%$\xi=(\xi_1\times \xi_2)\cdot \beta$ and $\eta=(\eta_1\times \eta_2)\cdot \beta^{-1}$. 
%Thus, $a\otimes b$ is a summand in $\Delta(x\ast y)$. 
%\vskip 0in
%Consider a summand $a\otimes b$ in $\Delta(x\ast y)$ where $a\in \field P_r$ and $b\in \field P_{n+m-r}$.
%Then we can write
%$$a\times b = \xi\cdot (x\times y)\cdot \eta,$$
%where $\xi\in \Sh(n,m)$, $\eta\in \Sh(r,n+m-r)$ and $r\in B(\xi\cdot(x\times y))$. 
%Consider the bottom row of the canonical diagram of $\xi\cdot (x\times y)$.
%There exists an integer $p$, $0\leq p\leq r$, such that the first $r$ vertices (from left to right) can 
%be divided into two disjoint subsets: $S(p)$ and $S(r-p)$ so that the inverse images 
%$(\xi\cdot (x\times y))^{-1}(S(p))\subseteq \{1,2,\ldots,n\}$ and 
%$(\xi\cdot (x\times y))^{-1}(S(r-p))\subseteq \{n+1,n+2,\ldots,n+m\}$. In other words, $S(p)$ corresponds
%to blocks in $x$ and $S(r-p)$ correspond to blocks in $y$. Similarly, for the remaining $n+m-r$ vertices 
%in the bottom row we have two disjoint sets $S'(n-p)$ and $S'(n+m-(r-p))$ so that 
%$(\xi\cdot (x\times y))^{-1}(S'(n-p))\subseteq \{1,2,\ldots,n\}$ and 
%$(\xi\cdot (x\times y))^{-1}(S(n+m-(r-p)))\subseteq \{n+1,n+2,\ldots,n+m\}$.
%Suppose $S(p)=\{i_1,i_2,\ldots, i_p\}$, where $1\leq i_1<i_2<\ldots<i_p\leq r$ and
%$S(r-p)=\{j_1,j_2,\ldots, j_{r-p}\}$, where $1\leq j_1<\ldots < j_{r-p}\leq r$. 
%Now define $\xi_1\in \Sh(p, r-p)$ by
%$$\xi_1(k)=\left\{ \begin{array}{ll} i_k & \mbox{if } 1\leq k\leq p\\
%j_k & \mbox{if } p+1\leq k\leq r\end{array}\right.  $$
%Similarly, let $S'(n-p)=\{ i_1',\ldots, i'_{n-p}\}$ and $S'(m-r+p)=\{j'_1,\ldots, j'_{m-(r-p)}\}$
%where $1\leq i'_1<\ldots < i'_{n-p}\leq n+m-r$ and $1\leq j'_1<\ldots < j'_{m-(r-p)}\leq n+m-r$. 
%Thus, we define $\xi_2\in \Sh(n-p, m-(r-p))$ by
%$$\xi_2(k)=\left\{ \begin{array}{ll} i'_k & \mbox{if } 1\leq k\leq n-p\\
%j'_k & \mbox{if } n-p+1\leq k\leq n+m-r\end{array}\right.  $$
%Now, the bottom row of $(\xi_1^{-1}\times \xi_2^{-1})\cdot \xi\cdot(x\times y)$ has the 
%property that the first $p$ vertices correspond to blocks from $x$, the next $r-p$ vertices 
%correspond to blocks from $y$, the next $n-p$ correspond to blocks from $x$ and the last 
%$m-r+p$ correspond to blocks from $y$.
%\vskip 0in 
%Finally, notice that the top row of $\xi\cdot (x\times y)\cdot \eta$ has the property that
%it can be divided into four disjoint sets of sizes $n_1, n_2, m_1$ and $m_2$ similarly as we did 
%for the bottom row. However, since multiplying a uniform block permutation on the right is equivalent 
%to permuting the vertices by $\eta^{-1}$ we have that the four sets are in order from left to right, the
%first set contains 1 through $n_1$, the next set contains $n_1+1$ through $n_1+n_2$, the third set
%contains $n_1+n_2+1$ throught $n_1+n_2+m_1$ and the last set contains the remaining $m_2$ vertices. 
%$\{1,\ldots, n_1\}$ and $\{n_1+n_2+1,\ldots, n_1+n_2+m_1\}$ correspond to $x$ blocks and the other 
%two sets correspond to $y$ blocks. Since $r$ is a breaking point we must have $n_1+m_1=r$ and $n_2+m_2=n+m-r$.
%Also, since both $x$ and $y$ are uniform block permutations and the argument about the bottom row
%we must have $n_1=p$, $n_2=r-p$, $m_1=n-p$ and $m-r+p$. 
%Hence, we have 
%$(\xi_1^{\-1}\times \xi_2^{-1})\cdot \xi\cdot (x\times y)\cdot \eta=(x'\times y')\times (x''\times y'')$. 
%Therefore, 
%\begin{eqnarray*}
%\xi\cdot(x\times y)\cdot\eta &=& (\xi_1\times \xi_2)\cdot(\xi_1^{-1}\times \xi_2^{-1})\cdot \xi\cdot (x\times y)\cdot \eta \\
%& =&(\xi_1\times \xi_2)\cdot((x'\times y')\times (x''\times y'')\\
%& =& (\xi_1\cdot (x'\times y'))\times (\xi_2\cdot (x''\times y'')).
%\end{eqnarray*}
%Hence $a\times b$ is a summand in $\Delta(x)\ast \Delta(y)$. 
%\endproof
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bigskip

Consider the following graded subspace of $\calP$: 
\[\calS:=\bigoplus_{n\geq 0}\field S_n\,.\]

\begin{prop} $\calS$ is a Hopf subalgebra of $\calP$. 
\end{prop}

$\calS$ is the  Hopf algebra of permutations of Malvenuto and Reutenauer~\cite{mr}.
Let $\sigma$ be a permutation. In the notation of~\cite{as}, the element $\sigma\in \calS$ corresponds to the
basis element $F_{\sigma}^*$ of $\SSym^*$, or equivalently the element 
$F_{\sigma^{-1}}$ of $\SSym$.

\subsection{Inverse monoid structure and self-duality}\label{S:selfdual}

As $\calS$, the Hopf algebra $\calP$ is self-dual. To see this, recall that a block permutation is a bijection $f:\calA\to\calB$ between two set partitions of $[n]$. Let $\Tilde{f}:\calB\to\calA$ denote the inverse bijection.
If $f$ is uniform then so is $\Tilde{f}$. The diagram of $\Tilde{f}\in P_n$ 
 is obtained by reflecting the diagram
of $f$ across a horizontal line.  Note that for $\sigma\in S_n\subseteq P_n$ we have $\Tilde{\sigma}=\sigma^{-1}$.

Let $\calP^*$ be the
graded dual space of $\calP$:
\[\calP^*=\bigoplus_{n\geq 0}(\field P_n)^*\,.\]
Let $\{f^*\mid f\in P_n\}$ be the basis of $(\field P_n)^*$ dual to the basis $P_n$ of $\field P_n$. 

\begin{prop} The map $\calP^*\to\calP$, $f^*\mapsto \Tilde{f}$, 
is an isomorphism of graded Hopf algebras.  
\end{prop}

The operation $f\mapsto\Tilde{f}$ is also relevant to the monoid
structure of $P_n$. Indeed, the following properties are satisfied
\[ f=f\Tilde{f}f \text{ \ and \ }\Tilde{f}=\Tilde{f}f\Tilde{f}\,.\]
Together with~\eqref{E:meet} below, these properties imply that $P_n$ is an {\em inverse monoid}~\cite[Theorem 1.17]{cp}.
The following properties are consequences of this fact~\cite[Lemma 1.18]{cp}:
\[\widetilde{fg}=\Tilde{g}\Tilde{f},\quad \Tilde{\Tilde{f}}=f\]
(they can also be verified directly).

\subsection{Factorizable monoid structure and the weak order}\label{S:weak}

Let $E_n$ denote the poset of set partitions of $[n]$: we say that $\calA\leq\calB$ if every bock of $\calB$ is contained in a block of $\calA$.
This poset is a lattice, and this structure is related to the monoid structure of uniform block 
permutations as follows. If $\id_{\calA}:\calA\to\calA$ denotes the uniform block permutation which is the identity map on the set of blocks of $\calA$, then
\begin{equation}\label{E:meet}
 \id_{\calA}\cdot\id_{\calB}=\id_{\calA\meet\calB}\,.
\end{equation}
In other words, viewing $E_n$ as a monoid under the meet operation $\meet$,
the map 
\[E_n\to P_n\,,\quad \calA\mapsto\id_{\calA}\,,\]
is a morphism of monoids. 

Any uniform block permutation $f\in P_n$ decomposes (non-uniquely) as \begin{equation}\label{E:factorization}
f=\sigma\cdot\id_{\calA} 
\end{equation}
for some $\sigma\in S_n$ and $\calA\in E_n$. Note that $\sigma$ is invertible and $\id_{\calA}$ is idempotent, by~\eqref{E:meet}. It follows that $P_n$ is a {\em factorizable inverse monoid}~\cite[Section 2]{ch}, ~\cite[Chapter 2.2]{l}. Moreover, by Lemma 2.1 in~\cite{ch}, any invertible element in $P_n$ belongs to $S_n$ and any idempotent element in $P_n$ belongs to (the image of) $E_n$. 
This lemma also guarantees that in~\eqref{E:factorization}, the idempotent $\id_{\calA}$ is uniquely determined by $f$ (which is clear since $\calA$ is
the domain of $f$). On the other hand, $\sigma$ is not unique, and we will make a suitable choice of this factor to define a partial order on $P_n$.

Consider the action of $S_n$ on $P_n$ by left multiplication. Given $\calA\in E_n$, the orbit of
$\id_{\calA}$ consists of all uniform block permutations $f:\calA\to\calB$ with
domain $\calA$, and the stabilizer is the {\em parabolic} subgroup
\[S_{\calA}:=\{\sigma\in S_n \mid \sigma(A)=A\ \forall A\in\calA\}\,.\]
Consider the set of $\calA$-\emph{shuffles}:
\[\Sh(\calA):=\{ \xi\in S_n \mid  \text{ if $i<j$ are in the same block of $\calA$ then $\xi(i)<\xi(j)$} \}\,.\]
It is well-known that these permutations form a set of representatives for the left cosets of the subgroup $S_{\calA}$. Therefore, given a uniform block permutation $f:\calA\to\calB$ there is a unique $\calA$-shuffle $\xi_f$ such that
\[f=\xi_f\cdot\id_{\calA}\,.\]
We use this decomposition to define a partial order on $P_n$ as follows:
\[f\leq g \iff \xi_f\leq \xi_g\,,\]
where the partial order on the right hand side is the left weak order on $S_n$ (see for instance~\cite{as}). We refer to this partial order as the {\em weak order} on $P_n$. Thus, $P_n$ is the disjoint union of certain subposets of the weak order on $S_n$:
\[P_n\cong \bigsqcup_{\calA\vdash[n]}\Sh(\calA)\]  
(in fact,  each $\Sh(\calA)$ is a lower order ideal $S_n$). Figures~\ref{F:12-3-4}-\ref{F:14-23} show 5 of the 15 components of $P_4$. Note that even when $\calA$ and $\calB$ are set partitions of the same type the posets $\Sh(\calA)$ and $\Sh(\calB)$ need not be isomorphic.

The partial order we have defined on $P_n$ should not be confused with the {\em natural partial order} which is defined on any inverse semigroup~\cite[Chapter 7.1]{cp2}, ~\cite[Chapter 1.4]{l}.

\vskip 0in
\begin{figure}[!h]
\centering
\includegraphics[width=10cm]{12-3-4.eps}
\caption{The component of $P_4$ corresponding to $\calA=\{1,2\}\{3\}\{4\}$}\label{F:12-3-4} 
\end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=10cm]{1-23-4.eps}
\caption{The component of $P_4$ corresponding to $\calA=\{1\}\{2,3\}\{4\}$}\label{F:1-23-4} 
\end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=10cm]{14-2-3.eps}
\caption{The component of $P_4$ corresponding to $\calA=\{1,4\}\{2\}\{3\}$}\label{F:14-2-3} 
\end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=7cm]{13-2-4.eps}
\caption{The component of $P_4$ corresponding to $\calA=\{1,3\}\{2\}\{4\}$}\label{F:13-2-4} 
\end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=6cm]{14-23.eps}
\caption{The component of $P_4$ corresponding to $\calA=\{1,4\}\{2,3\}$}\label{F:14-23} 
\end{figure}

\vskip 0in 

%Recall that $S_n$ acts on $E_n$:
% given $\sigma\in S_n$ and $\calA\vdash [n]$, $\sigma(\calA)$ is the set partition whose blocks are $\sigma(A)$ for $A\in\calA$. This action is related to
% the action of $S_n$ on $P_n$ by left multiplication as follows:
% \[\sigma\cdot\id_{\calA}=\id_{\sigma(\calA)}\cdot\sigma\,.\]

\begin{rem} 
As observed by Sloane~\cite{sl}, there is a connection between
uniform block permutations and the {\em patience games} of Aldous and Diaconis~\cite{ad}. Starting from a deck of cards a patience game produces 
a number of card piles according to certain simple rules (the output is not unique). If the cards are numbered $1,\ldots,n$,
the initial deck is a permutation of $[n]$ and the resulting piles form a set partition of $[n]$. Suppose $\sigma\in S_n$. The set partitions $\calA$ such that
$\sigma\in\Sh(\calA)$ are precisely the possible outputs of patience games played from a deck of cards with $\sigma^{-1}(1)$ in the bottom, followed by $\sigma^{-1}(2)$, up to $\sigma^{-1}(n)$ on the top. Thus, 
uniform block permutations are in bijection with the pairs consisting of the input
and the output of a patience game via $(\sigma,\calA)\leftrightarrow \sigma\cdot\id_{\calA}$.
%A {\em patience game} is played as follows. Start from a deck of cards numbered $1,\ldots,n$, and arranged in any order. At each step, draw a card
%from the top and place it on an existing pile which shows a bigger card, or
\end{rem}
 
 
 \subsection{The second basis and the Hopf algebra structure}\label{S:free}
 Following the ideas of~\cite{as}, we use the weak order on $P_n$ to define
 a new linear basis of the spaces $\field P_n$, on which the algebra
 structure of $\calP$ is simple.
 
For each element $g\in P_n$ let 
$$X_g:= \sum_{f\leq g} f\,.$$
% WARNING: this differs from Rosa's definition. Both work, but this one
% agrees with the conventions of {as}.
%For instance,
%\vskip 0in 
%\begin{picture}(300,20)(0,0)
%\put(25,10){For instance, let $g=$}
%\put(140,0){\circle*{3}}\put(140,20){\circle*{3}}\qbezier(140,20)(160,25)(180,20)
%\put(160,0){\circle*{3}}\put(160,20){\circle*{3}}\qbezier(140,0)(160,-7)(180,0)
%\put(180,0){\circle*{3}} \put(180,20){\circle*{3}}\put(140,0){\line(0,0){20}}
%\put(200,0){\circle*{3}} \put(200,20){\circle*{3}}\put(180,0){\line(0,0){20}}
%\put(160,0){\line(2,1){40}}\put(200,0){\line(-2,1){40}}
%\end{picture}
%\vskip .2in
%Then, 
%\vskip 0in 
%\begin{picture}(400,30)(0,0)
%\put(0,5){$X_g=$}
%\put(30,0){\circle*{3}}\put(30,20){\circle*{3}}\qbezier(30,20)(50,25)(70,20)
%\put(50,0){\circle*{3}}\put(50,20){\circle*{3}}\qbezier(30,0)(50,-7)(70,0)
%\put(70,0){\circle*{3}} \put(70,20){\circle*{3}}\put(30,0){\line(0,0){20}}
%\put(90,0){\circle*{3}} \put(90,20){\circle*{3}}\put(70,0){\line(0,0){20}}
%\put(50,0){\line(2,1){40}}\put(90,0){\line(-2,1){40}}
%\put(97,5){$+$}
%\put(110,0){\circle*{3}}\put(110,20){\circle*{3}}\qbezier(110,20)(130,25)(150,20)
%\put(130,0){\circle*{3}}\put(130,20){\circle*{3}}\qbezier(110,0)(140,-7)(170,0)
%\put(150,0){\circle*{3}} \put(150,20){\circle*{3}}\put(130,0){\line(2,1){40}}
%\put(170,0){\circle*{3}}\put(170,20){\circle*{3}}\put(150,0){\line(-1,1){20}}
%\put(110,0){\line(0,0){20}}\put(170,0){\line(-1,1){20}}
%\put(177,5){$+$}
%\put(190,0){\circle*{3}}\put(190,20){\circle*{3}}\qbezier(190,20)(210,25)(230,20)
%\put(210,0){\circle*{3}}\put(210,20){\circle*{3}}\put(190,0){\line(1,0){20}}
%\put(230,0){\circle*{3}} \put(230,20){\circle*{3}}\put(210,0){\line(1,1){20}}
%\put(250,0){\circle*{3}}\put(250,20){\circle*{3}}\put(230,0){\line(1,1){20}}
%\put(190,0){\line(0,0){20}}\put(250,0){\line(-2,1){40}}
%\put(257,5){$+$}
%\put(270,0){\circle*{3}}\put(270,20){\circle*{3}}\qbezier(270,20)(290,25)(310,20)
%\put(290,0){\circle*{3}}\put(290,20){\circle*{3}}\qbezier(270,0)(300,-7)(330,0)
%\put(310,0){\circle*{3}} \put(310,20){\circle*{3}}\put(290,0){\line(0,0){20}}
%\put(330,0){\circle*{3}}\put(330,20){\circle*{3}}\put(310,0){\line(1,1){20}}
%\put(270,0){\line(0,0){20}}\put(330,0){\line(-1,1){20}}
%\put(337,5){$+$}
%\put(350,0){\circle*{3}}\put(350,20){\circle*{3}}\qbezier(350,20)(370,25)(390,20)
%\put(370,0){\circle*{3}}\put(370,20){\circle*{3}}\put(350,0){\line(1,0){20}}
%\put(390,0){\circle*{3}} \put(390,20){\circle*{3}}\put(370,0){\line(1,1){20}}
%\put(410,0){\circle*{3}}\put(410,20){\circle*{3}}\put(390,0){\line(-1,1){20}}
% \put(350,0){\line(0,0){20}}\put(410,0){\line(0,0){20}}
%\put(417,5){$+$}
%\end{picture}
%\vskip 0in 
%\begin{picture}(400,30)(0,0)
%\put(30,0){\circle*{3}}\put(30,20){\circle*{3}}\qbezier(30,20)(50,25)(70,20)
%\put(50,0){\circle*{3}}\put(50,20){\circle*{3}}\qbezier(30,0)(50,-7)(70,0)
%\put(70,0){\circle*{3}} \put(70,20){\circle*{3}}\put(30,0){\line(0,0){20}}
%\put(90,0){\circle*{3}}\put(90,20){\circle*{3}}\put(70,0){\line(0,0){20}}
%\put(50,0){\line(2,1){40}}\put(90,0){\line(-2,1){40}}
%\put(30,0){\line(0,0){20}}
%\end{picture}
%\vskip 0in 

By M\"obius inversion, the set $\{X_g \mid g\in P_n\}$ is a linear basis of $\calP_n$.

Given $p,q\geq 0$, let $\xi_{p,q}\in S_{p+q}$ be the permutation
\[\xi_{p,q}:=\begin{pmatrix} 1 & 2 & \ldots & p & p+1 & p+2&  \ldots &p+q\\
q+1 & q+2 & \ldots & q+p& 1 & 2 & \ldots & q
\end{pmatrix}\,.\]
This is the maximum element of $\Sh(p,q)$ under the weak order. The product of $\calP$ takes the following simple form on the $X$-basis.
\begin{prop} \label{P:X-product}
Let $g_1\in P_p$ and $g_2\in P_q$ be uniform block permutations. Then \[X_{g_1}\ast X_{g_2} = X_{\xi_{p,q}\cdot(g_1\times g_2)}\,.\] 
\end{prop} 

\begin{cor}\label{C:free} The Hopf algebra $\calP$ is free as an algebra and cofree as a graded coalgebra.
\end{cor}

Let $V$ denote the space of primitive elements of $\calP$. It follows that the
generating series of $\calP$ and $V$ are related by
\[\calP(x)=\frac{1}{1-V(x)}\,.\]
Since \[\calP(x)=1+x+3x^2+16x^3+131x^4+1496x^5+22482x^6+\cdots\]
we deduce that
\[V(x)=x+2x^2+11x^3+98x^4+1202x^5+19052x^6+\cdots\,.\]


\begin{rem} The same conclusion may be derived by introducing another basis
$$Z_g:= \sum_{f\geq g} f\,.$$
% This is Rosa's basis, denoted X in previous versions.
This has the property that
\[Z_{g_1}\ast Z_{g_2} = Z_{g_1\times g_2}\,.\] 
Note that $Z_{\id_{\calA}}$ is the element denoted $Z_{\calA}$ in Section~\ref{S:ideal}.
\end{rem}

% Should verify the prop of the X-basis and calculate the antipode on both bases. I think we did it already on the Z-basis but maybe not on the X-basis.
%----------------------------------------------------------------------------------

\section{The Hopf algebra of symmetric functions in non-commuting variables}

Let $X$ be a countable set, the {\em alphabet}. A {\em word of length $n$} is a function $w:[n]\to X$. Let $\kX$ be the algebra of non-commutative
power series on the set of variables $X$. Its elements are infinite linear combinations of words, finitely many of each length, and the product is 
 concatenation of words.

The {\em kernel} of a word $w$ of length $n$ is the set partition $\calK(w)$ of $[n]$ whose blocks are the non-empty fibers of $w$.
Order the set of set partitions of $[n]$ by refinement, as in Section~\ref{S:weak}.  For each set partition $\calA$ of $[n]$, let
\[p_A:=\sum_{\calK(w)\leq A} w \in \kX\,.\]
This is the sum of all words $w$ such that if $i$ and $j$ are in the same block of $\calA$ then $w(i)=w(j)$. For instance
\[p_{\{1,3\}\{2,4\}}= xyxy+xzxz+ yxyx+ \cdots+ x^4+y^4+z^4+\cdots\,.\]

The subspace of $\kX$ linearly spanned by the  elements $p_\calA$ as $\calA$ runs over all set partitions of $[n]$, $n\geq 0$, is a subalgebra $\Pi$ of $\kX$, graded by length. The elements of $\Pi$ can be characterized  as those power series of finite degree that are invariant under any permutation of the variables.
$\Pi$ is the algebra of symmetric functions in non-commuting variables introduced by Wolf~\cite{w} and recently studied by Gebhard, Rosas, and Sagan~\cite{gs00, gs01,rs} in connection to Stanley's chromatic symmetric function.

$\Pi$ is in fact a graded Hopf algebra~\cite{brrz,am}. The coproduct is defined via evaluation of symmetric functions on two copies of the alphabet $X$. In order to describe
 the product and coproduct of $\Pi$ on the basis elements $p_\calA$ we introduce some notation.

Given set partitions  $\calA\vdash [n]$ and $\calB\vdash [m]$ let $\calA\times\calB$ be the set partition of $[n+m]$ whose blocks are the blocks of $\calA$ and the sets $\{b+n\, |\, b\in B\}$ where $B$ is a block of $\calB$.
This corresponds to the operation $\times$ on uniform block permutations in the sense that $\id_{\calA}\times\id_{\calB}=\id_{\calA\times\calB}$.
For example, if $\calA=\{1,3,4\}\{2,5\}\{6\}\vdash [6]$ and $\calB=\{1,4\}\{2\}\{3,5\}\vdash [5]$, then 
$\calA\times \calB =\{1,3,4\}\{2,5\}\{6\}\{7,10\}\{8\}\{9,11\}\vdash [11]$. 

To a set partition $\calA\vdash[n]$ and a subset $S\subseteq\calA$ we associate a new set partition $\calA_S$ as follows. Write
\[\bigcup_{A\in S} A=\{j_1,\cdots, j_m\} \subseteq [n]\]
 with $j_1<j_2<\cdots <j_m$. $\calA_S$ is the set partition of $[m]$ whose blocks
 are obtained from the blocks $A\in S$ by replacing each $j_t$ by $t$, for $1\leq t\leq m$. For instance, if $S=\{1,5\}\{2,7\}$ then $\calA_S=\{1,3\}\{2,4\}\vdash [4]$.
 
The product and coproduct of $\Pi$ are given by
\begin{align}
p_\calA p_\calB & = p_{\calA\times\calB}\,, \label{E:prodPi}\\
\Delta(p_\calA) & =\sum_{S\sqcup T=\calA}p_{\calA_S}\otimes p_{\calA_T}\,, \label{E:coprodPi}
\end{align}
the sum over all decompositions of $\calA$ into disjoint sets of blocks $S$ and $T$. For example, if $\calA=\{1,2,6\}\{3,5\}\{4\}$, then
\begin{eqnarray*}
\Delta(p_\calA) &=& p_\calA \otimes 1 + p_{\{1,2,5\}\{3,4\}}\otimes p_{\{1\}} 
+ p_{\{1,2,4\}\{3\}}\otimes p_{\{1,2\}} 
+p_{\{1,3\}\{2\}}\otimes p_{\{1,2,3\}} + \\  && p_{\{1,2,3\}}\otimes p_{\{1,3\}\{2\}} + 
p_{\{1,2\}} \otimes p_{\{1,2,4\}\{3\}} + p_{\{1\}}\otimes p_{\{1,2,5\}\{3,4\}} + 1 \otimes p_{\calA}\,.
\end{eqnarray*}

Consider now the direct sum of the subspaces $\calZ_n$ of $\field P_n$ introduced in Section~\ref{S:ideal}:
\[\calZ:=\bigoplus_{n\geq 0}\calZ_n \subset \calP \,.\]

\begin{theorem} $\calZ$ is a Hopf subalgebra of $\calP$. Moreover, the map
\[\calZ\to\Pi, \quad Z_{\calA}\mapsto p_{\calA}\]
is an isomorphism of graded Hopf algebras.
\end{theorem}

Thus the Hopf algebra of uniform block permutations $\calP$ contains the Hopf algebra $\Pi$ of symmetric functions in non-commuting variables. Note also that this reveals the
existence of a second operation on $\Pi$: according to Corollary~\ref{C:ideal}, each homogeneous component $\Pi_n$ carries an associative non-unital product that turns it into a right ideal of the
monoid algebra $\field P_n$. Connections between $\Pi$ and other combinatorial
Hopf algebras are studied in~\cite{am}.


 
%\bibliographystyle{plain}
\begin{thebibliography}{999}

\bibitem{am} Marcelo Aguiar and Swapneel Mahajan, 
\emph{Species and equivariant Hopf algebras}, in preparation (2004).

\bibitem{as} Marcelo Aguiar and Frank Sottile, 
\emph{Structure of the Malvenuto-Reutenauer Hopf algebra of 
Permutations}, 
Advances in Mathematics {\bf 191} n2 (2005) 225--275.

\bibitem{ad}
David Aldous and Persi  Diaconis,
\emph{Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem}, Bull. Amer. Math. Soc.  {\bf 36} (1999) 413--432.                          


\bibitem{brrz}
Nantel Bergeron ,  Christophe Reutenauer, Mercedes Rosas,   and Mike Zabrocki,
\emph{The Hopf algebra of symmetric functions in noncommutative variables},   in preparation (2004).
 
 \bibitem{ch}
S. Y. Chen and S. C. Hsieh,
\emph{Factorizable Inverse Semigroups},
 Semigroup Forum {\bf 8} (1974) n4 283--297.

 \bibitem{cp} A. H. Clifford and G. B. Preston,
 \emph{The algebraic theory of semigroups. Vol. I}, 
  Mathematical Surveys, No. 7 American Mathematical Society, 
 Providence, R.I., 1961 xv+224 pp.
 
 \bibitem{cp2} A. H. Clifford and G. B. Preston,
 \emph{The algebraic theory of semigroups. Vol. II}, 
  Mathematical Surveys, No. 7 American Mathematical Society, 
 Providence, R.I., 1967 xv+350 pp.

 
 \bibitem{eef}
David Easdown, James East, and D. G. FitzGerlad,
\emph{Presentations of factorizable inverse monoids}, 2004.


  \bibitem{f} Desmond G. FitzGerald, 
\emph{A presentation for the monoid of uniform block permutations}, 
Bull. Austral. Math. Soc., {\bf 68} (2003) 317--324.

\bibitem{gs00}
 David D. Gebhard, Bruce E. Sagan,
 \emph{Sinks in Acyclic Orientations of Graphs},
   J. Combin. Theory (B) {\bf 80} (2000) 130--146.

\bibitem{gs01}
 David D. Gebhard, Bruce E. Sagan,
\emph{ A chromatic symmetric function in noncommuting variables}, 
J. Alg. Combin. {\bf 13} (2001) 227--255.

\bibitem{j} 
Vaughan F. R. Jones, 
\emph{The Potts Model and the symmetric group},
in Subfactors: Proceedings of the Tanaguchi Symposium on Operator Algebras,
Kyuzeso, 1993, pp. 259-267, World Scientific, River Edge, NJ 1994. 

\bibitem{k00} Masashi Kosuda, \emph{Characterization for the party algebra},
 Ryukyu Math. J. {\bf 13} (2000) 7--22. 

\bibitem{k01} Masashi Kosuda, \emph{Party algebra and construction of its irreducible representations},
 paper presented at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), 
May 20-26, 2001. 
 
\bibitem{l} Mark V. Lawson,
 \emph{Inverse semigroups. The theory of partial symmetries}, 
 World Scientific, River Edge, NJ, 1998. xiv+411 pp.
 
\bibitem{mr} Claudia Malvenuto and Christophe Reutenauer, 
\emph{Duality between quasi-symmetric functions and the 
Solomon descent algebra}, 
J. Algebra {\bf 177} n3 (1995), 967--982. 

\bibitem{m} Paul P. Martin, 
\emph{Temperley-Lieb algebras for non-planar statistical mechanics - The 
partition algebra construction}, 
J. Knot Theory and its Applicatitions, {\bf 3}  n1 (1994) 51--82. 

\bibitem{rs} Mercedes Rosas  and Bruce Sagan, 
\emph{Symmetric functions in non-commuting variables},
to appear in Trans. Amer. Math. Soc.

\bibitem{sps} 
J.-M. Sixdeniers, K. A. Penson, and A. I. Solomon,
\emph{Extended {B}ell and {S}tirling numbers from hypergeometric exponentiation}, J. Integer Seq., {\bf 4} (2001), Article 01.1.4.

\bibitem{sl}
Neil J.~A.~Sloane, \emph{An on-line version of the encyclopedia of integer
  sequences}, Electron. J. Combin. \textbf{1} (1994), Feature 1, approx.\ 5
  pp.\ (electronic), {\tt
  http://akpublic.research.att.com/\~{}njas/sequences/ol.html}.
 
 \bibitem{t}  Kenichiro Tanabe,  
 \emph{On the centralizer algebra of the unitary 
 reflection group $G(m,p,n)$}, Nagoya Math. J. {\bf 148} (1997)
 113--126.
 
\bibitem{w} M. C. Wolf, 
\emph{Symmetric functions of non-commuting elements}, 
Duke Math. J. {\bf 2} (1936) 626--637.

\end{thebibliography}

\end{document}

%%% Additional references


  

math0505199.extracted_bib
\begin{thebibliography}{999}

\bibitem{am} Marcelo Aguiar and Swapneel Mahajan, 
\emph{Species and equivariant Hopf algebras}, in preparation (2004).

\bibitem{as} Marcelo Aguiar and Frank Sottile, 
\emph{Structure of the Malvenuto-Reutenauer Hopf algebra of 
Permutations}, 
Advances in Mathematics {\bf 191} n2 (2005) 225--275.

\bibitem{ad}
David Aldous and Persi  Diaconis,
\emph{Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem}, Bull. Amer. Math. Soc.  {\bf 36} (1999) 413--432.                          


\bibitem{brrz}
Nantel Bergeron ,  Christophe Reutenauer, Mercedes Rosas,   and Mike Zabrocki,
\emph{The Hopf algebra of symmetric functions in noncommutative variables},   in preparation (2004).
 
 \bibitem{ch}
S. Y. Chen and S. C. Hsieh,
\emph{Factorizable Inverse Semigroups},
 Semigroup Forum {\bf 8} (1974) n4 283--297.

 \bibitem{cp} A. H. Clifford and G. B. Preston,
 \emph{The algebraic theory of semigroups. Vol. I}, 
  Mathematical Surveys, No. 7 American Mathematical Society, 
 Providence, R.I., 1961 xv+224 pp.
 
 \bibitem{cp2} A. H. Clifford and G. B. Preston,
 \emph{The algebraic theory of semigroups. Vol. II}, 
  Mathematical Surveys, No. 7 American Mathematical Society, 
 Providence, R.I., 1967 xv+350 pp.

 
 \bibitem{eef}
David Easdown, James East, and D. G. FitzGerlad,
\emph{Presentations of factorizable inverse monoids}, 2004.


  \bibitem{f} Desmond G. FitzGerald, 
\emph{A presentation for the monoid of uniform block permutations}, 
Bull. Austral. Math. Soc., {\bf 68} (2003) 317--324.

\bibitem{gs00}
 David D. Gebhard, Bruce E. Sagan,
 \emph{Sinks in Acyclic Orientations of Graphs},
   J. Combin. Theory (B) {\bf 80} (2000) 130--146.

\bibitem{gs01}
 David D. Gebhard, Bruce E. Sagan,
\emph{ A chromatic symmetric function in noncommuting variables}, 
J. Alg. Combin. {\bf 13} (2001) 227--255.

\bibitem{j} 
Vaughan F. R. Jones, 
\emph{The Potts Model and the symmetric group},
in Subfactors: Proceedings of the Tanaguchi Symposium on Operator Algebras,
Kyuzeso, 1993, pp. 259-267, World Scientific, River Edge, NJ 1994. 

\bibitem{k00} Masashi Kosuda, \emph{Characterization for the party algebra},
 Ryukyu Math. J. {\bf 13} (2000) 7--22. 

\bibitem{k01} Masashi Kosuda, \emph{Party algebra and construction of its irreducible representations},
 paper presented at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), 
May 20-26, 2001. 
 
\bibitem{l} Mark V. Lawson,
 \emph{Inverse semigroups. The theory of partial symmetries}, 
 World Scientific, River Edge, NJ, 1998. xiv+411 pp.
 
\bibitem{mr} Claudia Malvenuto and Christophe Reutenauer, 
\emph{Duality between quasi-symmetric functions and the 
Solomon descent algebra}, 
J. Algebra {\bf 177} n3 (1995), 967--982. 

\bibitem{m} Paul P. Martin, 
\emph{Temperley-Lieb algebras for non-planar statistical mechanics - The 
partition algebra construction}, 
J. Knot Theory and its Applicatitions, {\bf 3}  n1 (1994) 51--82. 

\bibitem{rs} Mercedes Rosas  and Bruce Sagan, 
\emph{Symmetric functions in non-commuting variables},
to appear in Trans. Amer. Math. Soc.

\bibitem{sps} 
J.-M. Sixdeniers, K. A. Penson, and A. I. Solomon,
\emph{Extended {B}ell and {S}tirling numbers from hypergeometric exponentiation}, J. Integer Seq., {\bf 4} (2001), Article 01.1.4.

\bibitem{sl}
Neil J.~A.~Sloane, \emph{An on-line version of the encyclopedia of integer
  sequences}, Electron. J. Combin. \textbf{1} (1994), Feature 1, approx.\ 5
  pp.\ (electronic), {\tt
  http://akpublic.research.att.com/\~{}njas/sequences/ol.html}.
 
 \bibitem{t}  Kenichiro Tanabe,  
 \emph{On the centralizer algebra of the unitary 
 reflection group $G(m,p,n)$}, Nagoya Math. J. {\bf 148} (1997)
 113--126.
 
\bibitem{w} M. C. Wolf, 
\emph{Symmetric functions of non-commuting elements}, 
Duke Math. J. {\bf 2} (1936) 626--637.

\end{thebibliography}