%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[submission]{FPSAC2019}

\articlenumber{58}
\addbibresource{58.bib}

\usepackage{eucal,tikz,genyoungtabtikz}
\usetikzlibrary{knots} 
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{defn}{Definition}
\newtheorem{examp}{Example}
\newtheorem{rem}{Remark}
\numberwithin{equation}{section}
\numberwithin{thm}{section}
\numberwithin{lem}{section}
\numberwithin{defn}{section}
\numberwithin{examp}{section}
\numberwithin{rem}{section}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% MACROS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% BB
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}  

% BF
\newcommand{\A}{\mathbf{A}} 
\newcommand{\C}{\mathbf{C}}  
\newcommand{\J}{\mathbf{J}} 
\newcommand{\Motz}{\mathbf{M}}
\newcommand{\Pb}{\mathbf{P}\hspace{-1pt}}
\newcommand{\PR}{\mathbf{PR}}
\newcommand{\planarP}{\mathbf{PP}\hspace{-1pt}}
\newcommand{\R}{\mathbf{R}}
\newcommand{\RB}{\mathbf{RB}}
\renewcommand{\S}{\mathbf{S}}  
\newcommand{\TL}{\mathbf{TL}}
\newcommand{\W}{\mathbf{W}}
\newcommand{\XX}{\mathbf{X}}

% SF
\newcommand{\ds}{\mathsf{d}}
\newcommand{\e}{\mathsf{e}}  
\newcommand{\m}{\mathsf{m}}
\newcommand{\n}{\mathsf{n}}
\newcommand{\us}{\mathsf{u}}
\newcommand{\vs}{\mathsf{v}}

\newcommand{\BB}{\mathsf{B}}
\newcommand{\F}{\mathsf{F}}
\newcommand{\N}{\mathsf{N}}
\newcommand{\PP}{\mathsf{P}\hspace{-1pt}}
\newcommand{\T}{\mathsf{T}} 
\newcommand{\V}{\mathsf{V}}
\newcommand{\M}{\mathsf{M}}
\newcommand{\Z}{\mathsf{Z}}

\newcommand{\Ind}{\mathsf{Ind}}
\newcommand{\Res}{\mathsf{Res}}

% CAL
\newcommand{\calA}{\mathcal{A}}  
\newcommand{\calF}{\mathcal{F}}  
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calW}{\mathcal{W}}
\newcommand{\B}{\mathcal{B}}

% MISC
\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}
\newcommand{\Wm}{\calW^{m}_{\!\!\calA_k}}
\newcommand{\WWm}{\W^{m}_{\!\!\calA_k}}
\newcommand{\ot}{\otimes}
\newcommand{\End}{\mathsf{End}}
\newcommand{\YT}{\mathcal{YT}}
\newcommand{\SYT}{\mathcal{SYT}}
\newcommand{\SPT}{\mathcal{SPT}}
\newcommand{\SPTb}{\overline{\mathcal{SPT}}}
\newcommand{\SSPT}{\mathcal{SSPT}}
\newcommand{\tp}{\mathsf{top}}
\newcommand{\bt}{\mathsf{bot}} 
\newcommand{\pn}{\mathsf{rank}} 
\newcommand{\param}{{n}}
\newcommand{\half}{{\frac{1}{2}}}

\newcommand{\mg}{\color{magenta}}
\newcommand{\cy}{\color{cyan}}
\newcommand\marg[1]{\marginpar{\raggedright #1}} 

\usepackage{lipsum}

%% define your title in the usual way
\title[Set-Partition Tableaux]{Set-Partition Tableaux,  Symmetric Group Multiplicities, and  Partition Algebra Modules}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Tom Halverson]{Tom Halverson\thanks{\href{mailto:halverson@macalester.edu}{halverson@macalester.edu}. Partially supported by Simons Foundation Grant 283311.}}

%% then use \addressmark to match authors to institutions here
\address{Department of Mathematics, Statistics, and Computer Science, Macalester College, Saint Paul, MN 55105, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Set-partition tableaux are Young tableaux whose boxes are filled with the blocks of a set partition. We use them to compute multiplicities of symmetric group modules in tensor product representations and to index bases of irreducible modules of the partition algebra. We give an action of the partition algebra on this basis analogous to Young's natural representation of the symmetric group. This action restricts to give natural representations for subalgebras of the partition algebra including the Brauer, Temperley--Lieb, rook-monoid, and Motzkin algebras.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{678910}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Set partitions, tableaux, partition algebra, symmetric group}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{PartAlgReps.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands
\begin{document}



\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above
\section{Introduction}

We survey recent work on applications \cite{BH-invariant2,BH-invariant1,BHH,HJ} of set-partition tableaux in representation theory. These tableaux appeared first in the work of Benkart, Halverson, and Harmon \cite{BHH} to describe tensor power multiplicities in the symmetric group and the dimensions of simple modules of partition algebras. At nearly the same time, Orellana and Zabrocki \cite{OZ} used them to analyze reduced  Kronecker coefficients for the  symmetric group. Via Schur--Weyl duality these symmetric group representations are reflected in the representation theory of the partition algebra, and Halverson and Jacobson \cite{HJ} describe the irreducible modules of the partition algebra on set-partition tableaux in the same way that Young described the natural representation of the symmetric group on standard Young tableaux.

In \cref{sec:tensor-power}, we study the $k$-fold tensor power of the permutation module of the symmetric group, and give the multiplicities of irreducible symmetric group modules in this tensor power in terms of paths in a restriction-induction Bratteli diagram or, equivalently, in terms of up-down tableaux. This is "classical" result that can be found for example in \cite{HL-RSK,HR}. We  examine this same decomposition from the point of view of modules on ordered set partitions, give a closed formula for this multiplicity, and show that it equals the number of standard set-partition tableaux. We then give a bijection between up-down tableaux and set-partition tableaux. These are new results found in \cite{BHH}.

In \cref{sec:partalg} we use Schur--Weyl duality on tensor space between the symmetric group $\S_n$ and the partition algebra $\Pb_k(n)$ to show that the partition algebra has irreducible modules $\Pb_k^\lambda$. These are labeled by integer partitions $\lambda$ have bases indexed by set-partition tableaux.  We give an action of the basis diagrams of $\Pb_k(n)$ on set-partition tableaux. This action is analogous to Young's action of permutations on standard Young tableaux, and our representation is the partition-algebra version of Young's natural representation. The partition algebra contains a collection of diagram  subalgebras that are important in  representation theory; these include the Brauer, Temperley--Lieb, Motzkin, rook-monoid, rook-Brauer, and planar rook-monoid algebras. Our representations restrict naturally to each of these subalgebras, and we thereby obtain a uniform construction of Young's natural representation on set-partition tableaux for each of these algebras.


\section{Tensor power representations of the symmetric group\label{sec:tensor-power}}

We let $\S_n$ denote the symmetric group of permutations on $[n]=\{1, \ldots, n\}$. The irreducible $\S_n$-modules over $\CC$ (or any field of characteristic 0) are indexed by integer partitions $\lambda \vdash n$, and we let $\S_n^\lambda$ denote the irreducible module associated with $\lambda$.

The $n$-dimensional permutation module $\M_n$ of $\S_n$ has a basis $\{\vs_1, \ldots, \vs_n\}$ such that $\sigma. \vs_i = \vs_{\sigma(i)}$ for all $\sigma \in \S_n$, and it decomposes into a direct sum  $\M_n \cong \S_n^{[n]} \oplus \S_n^{[n-1,1]}$ of a trivial module $\S_n^{[n]}$ and a "reflection" module $\S_n^{[n-1,1]}$. The $k$-fold tensor product  $\M_n^{\otimes k}$ has a basis of simple tensors
$\{ \vs_{i_1} \otimes \cdots \vs_{i_k} \mid i_j \in [n] \}$ on which permutations act diagonally
$$
\sigma ( \vs_{i_1} \otimes \cdots \otimes \vs_{i_k} ) =  \vs_{\sigma(i_1)} \otimes \cdots \otimes \vs_{\sigma(i_k)}, \qquad \sigma \in \S_n.
$$
A fundamental question in the representation theory of $\S_n$ is to decompose $\M_n^{\otimes k}$ into irreducible constituents; that is, to find the multiplicities $\m_{k,n}^\lambda$ in 
\begin{equation}\label{tensor-multiplicity}
\M_n^{\otimes k} \cong \bigoplus_{\lambda \vdash n} \m_{k,n}^\lambda \S_n^\lambda.
\end{equation}

\subsection{Computing $\m_{k,n}^\lambda$ via restriction-induction}

The "tensor identity" tells us that tensoring with the permutation module is isomorphic to first restricting to $\S_{n-1}$ and then inducing back to $\S_n$. That is,
\begin{equation}
\S_n^\lambda \otimes \M_n \cong \Ind^{\S_n}_{\S_{n-1}} \Res^{\S_n}_{\S_{n-1}}(\M_n).
\end{equation}
Furthermore, restriction to $\S_{n-1}$ removes a box from the partition $\lambda$ and induction adds a box back, so we have
\begin{equation}\label{add-remove}
\S_n^\lambda \otimes \M_n \cong \Ind^{\S_n}_{\S_{n-1}} \Res^{\S_n}_{\S_{n-1}}(\M_n) 
\cong \Ind^{\S_n}_{\S_{n-1}} \bigoplus_{\nu = \lambda - \square}  \S_{n-1}^\nu
\cong \bigoplus_{\mu = \nu + \square}  \bigoplus_{\nu = \lambda - \square}  \S_{n}^\mu.
\end{equation}

If we define $\M_n^{\otimes 0} := \S_n^{[n]}$, the trivial module, and recursive apply \eqref{add-remove}, we obtain the restriction-induction Bratteli diagram $\B(\S_n,\S_{n-1})$, which is shown for $n = 6$ in \cref{fig-bratteli}. The Bratteli diagram $\B(\S_n,\S_{n-1})$ is an infinite, rooted lattice whose vertices on rows $k$ and $k+\half$ are labeled by
\begin{align}
\Lambda_{k,n} = \left\{ \lambda \vdash n \mid |\overline{\lambda}| \le k \right\} \qquad\hbox{and}\qquad
\Lambda_{k+\half,n}  = \left\{ \nu \vdash (n-1) \mid |\overline{\nu}| \le k \right\}, 
\end{align}
respectively,  
where if $\lambda = [\lambda_1, \lambda_2, \ldots, \lambda_\ell]$ is an integer partition of $n$ then $\overline{\lambda} = [\lambda_2, \ldots, \lambda_\ell]$ is the partition $\lambda$ with its first part removed.
There is an edge from $\lambda \in \Lambda_{k,n}$ to $\nu \in \Lambda_{k+\half,n}$ if $\nu$ can be obtained from $\lambda$ by removing a box, and there is an edge  from  $\nu \in \Lambda_{k+\half,n}$ to $\lambda \in \Lambda_{k+1,n}$ if $\lambda$ can be obtained from $\nu$ by adding a box. 
By induction on \eqref{add-remove}, 
\begin{itemize}
\item the partitions in $\Lambda_{k,n}$ index the irreducible $\S_n$ modules which appear in $\M_n^{\otimes k}$, and  
\item the multiplicity $\m_{k,n}^\lambda$ of $\S_n^\lambda$ in $\M_n^{\otimes k}$ equals the number of length-$2k$ paths from $[n]$ on row 0 to $\lambda$ on row $k$ in $\B(\S_n,\S_{n-1})$. 
\end{itemize}

Motivated by the previous paragraph, we define an $(n,k)$-\emph{up-down tableau} of shape $\lambda$ to be a sequence
$$
([n] = \lambda^{(0)}, \lambda^{(\half)}, \lambda^{(1)}, \lambda^{(1 \half)},  \ldots, \lambda^{(k-\half)}, \lambda^{(k)} = \lambda)
$$
such that  for each integer $0 \le i \le k$ we have: (i)  $\lambda^{(i)} \in \Lambda_{i,n}$; (ii) $\lambda^{(i+ \half)} \in \Lambda_{i + \half,n}$; (iii) $\lambda^{(i + \half)} = \lambda^{(i)} - \square$; and (iv) $\lambda^{(i)} = \lambda^{(i-\half)} + \square$. It follows that (\cite{HL-RSK, HR})
\begin{equation}
\m_{k,n}^\lambda = \#(\text{$(k,n)$-up-down tableaux of shape $\lambda$}).
\end{equation}
 These tableaux also appear in the study \cite{CDDSY} of crossing and nesting set partitions.

\begin{figure}[!ht]
$$ 
\includegraphics[width=4.5in]{Bratteli} 
$$
\caption{\label{fig-bratteli} Rows 0 to 4 of the restriction-induction Bratteli diagram $\B(\S_6,\S_5)$. The label associated to the partition $\lambda$ on row $k$ is the multiplicity $\m_{k,6}^\lambda$ in \eqref{tensor-multiplicity}.} 
\end{figure}

\subsection{Computing $\m_{k,n}^\lambda$ via permutation modules}

If $\pi$ is a set partition of $\{1,\ldots,k\}$ into $t$ blocks, where $1 \le t \le n$,  then the vector space
\begin{equation}\label{eq:PermutationCondition}
\M(\pi) := \text{ span}_\CC\left\{\vs_{j_1} \ot \cdots \ot \vs_{j_k} \mid  j_a = j_b \iff a, b \text{ are in the same block of } \pi
\right\}
\end{equation}
is an $\S_n$-submodule of $\M_n^{\otimes k}$.
To see this, recall that  $\sigma \in \S_{n}$ acts diagonally on simple tensors,
$\sigma (\vs_{j_1} \ot \vs_{j_2} \ot \cdots \ot \vs_{j_k}) =  \vs_{\sigma({j_1})} \ot \vs_{\sigma(j_2)} \ot \cdots \ot \vs_{\sigma({j_k})},$ and so it preserves the condition in
\eqref{eq:PermutationCondition}.   As an example,  if $n = 8$ and $k = 12$, then 
\begin{equation}\label{ex:simpltensor}
\vs=\vs_3 \ot \vs_1 \ot \vs_3 \ot \vs_3 \ot \vs_4 \ot \vs_5 \ot \vs_4 \ot \vs_1 \ot \vs_1 \ot \vs_3 \ot \vs_4 \ot \vs_5 \in \M_8^{\ot 12}
\end{equation}
belongs to $\M(\pi)$ for $\pi = \{1,3,4,10 \mid 2,8,9 \mid 5,7,11 \mid 6,12\}$.
The diagonal action of $\S_n$ on the simple tensors in $\M(\pi)$ corresponds exactly to the permutation action of $\S_n$ on the ordered set partitions of $\{1, 2, \ldots, n\}$, which is the permutation module $\M^{[n-t,1^t]}$ obtained by inducing the trivial module for the subgroup $\S_{n-t} \times {\S_1 \times \cdots \times \S_1}$ (with $t$ copies of $\S_1$) to $\S_n$.
% (see for example \cite[Sec.~2.1]{Sa}).  
Thus,
$\M(\pi) \cong \M^{[n-t,1^t]}$ when $\pi$ has $t$ blocks.  
  
The number of set partitions $\pi$ of $\{1,\ldots,k\}$ into $1 \le t \le n$ parts is the Stirling number
$\stirling{k}{t}$ of the second kind, so this partitioning of simple tensors gives the following decomposition
of $\M_n^{\ot k}$:
\begin{equation}
\M_n^{\ot k} \cong \bigoplus_{t=1}^n \stirling{k}{t} \M^{[n-t,1^t]}. 
\end{equation} 
Young's rule %(see for example, \cite[Thm.~2.11.2]{Sa}) 
says that  for $\gamma = [\gamma_1, \gamma_2, \ldots,\gamma_n] \vdash n$, the multiplicity of $\S_n^\lambda$ in $\M^\gamma$  equals the Kostka number $\mathsf{K}_{\lambda,\gamma}$, which counts the number of \emph{semistandard tableaux} $T$ of shape $\lambda$ and type $\gamma$.   It follows that 
 \begin{equation*}
\M_n^{\ot k} \cong \bigoplus_{t=1}^n \stirling{k}{t} \M^{[n-t,1^t]} \cong
\bigoplus_{t=1}^n \stirling{k}{t} \left(\sum_{\lambda \vdash n} \mathsf{K}_{\lambda, [n-t,1^t]} \S_n^\lambda\right)
\cong  \bigoplus_{\lambda \vdash n} \left(\sum _{t=1}^n \stirling{k}{t}  \mathsf{K}_{\lambda, [n-t,1^t]}\right) \S_n^\lambda.
\end{equation*}
In this particular case, the Kostka number $\mathsf{K}_{\lambda, [n-t, 1^t]}$ counts the number of semistandard tableaux of shape $\lambda$ filled with the entries 
$\{ 0^{n-t}, 1, 2, \ldots, t\}$. Such a  tableau  must have $n-t$ zeros in the first row and a standard filling of the skew shape $\lambda/[n-t]$ with the numbers $1,2,\dots,t$.  For example, if $\lambda = [7,5,3]$ and $t = 3$
then one such semistandard tableau is  
\Yboxdim{13pt} \Ylinethick{.6pt}  \def\ten{{10}}  \def\eleven{{11}}  \def\twelve{{12}}
$$
\young(000368\twelve,1457\eleven,29\ten).
$$  
The number $f^{\lambda/[n-t]}$ of such fillings is given by the hook formula for skew shapes  (see for example, \cite[Cor. 7.16.3]{Stanley1}). 
It follows that
\begin{equation}\label{closed-formula}
\m_{k,n}^\lambda = \sum_{t = 1}^n \stirling{k}{t} f^{\lambda/[n-t]}.
\end{equation}

\subsection{Set-partition tableaux}

Formula \eqref{closed-formula} relates $\m_{k,n}^\lambda$ to the number pairs $(\pi,T)$ consisting of a set partition $\pi$ of $\{1,\ldots,k\}$ into $t$ parts and a standard tableau of skew shape $\lambda/[n-t]$. Since, the skew shape $\lambda/[n-t]$ has $t$ boxes, we fill the boxes with the blocks of $\pi$ in a standard way. This motivates the following definition.

\begin{defn} {\rm
Let $\lambda \in \Lambda_{k,n}$ so that $\lambda$ is an integer partition of $n$ with $0 \le |\lambda^\ast| \le k$. A \textit{set-partition tableau $\T$ of shape $\lambda$} is a filling of the boxes of $\lambda$ with subsets of $\{1,\ldots,k\}$, including the empty set, such that:
\begin{enumerate}
\item[(a)] the empty subsets are only in the first row  of  $\lambda$ and are left-justified;
\item[(b)] the non-empty subsets form a set partition $\pi$ of $\{1,\ldots,k\}$, called the \emph{content} of $\T$.
\end{enumerate}
The set-partition tableau is  \textit{standard} if 
\begin{enumerate}
\item[(c)] the  non-empty entries of $\T$ increase across the rows and down the columns using maximum-entry order on the blocks of $\pi$. 
\end{enumerate}
By construction, the non-empty boxes of $\T$  form a skew shape $\lambda/[n-t]$ with $|\overline{\lambda}| \le t \le n$.
}
 \end{defn}


Below is a standard set-partition tableau $\T$ of shape $\lambda = [8,4,3,1] \vdash 16$ and content 
\begin{equation*}
\pi = \{3\mid 5 \mid 6 \mid 8 \mid 2,9 \mid  12 \mid 4,7,10,14\mid 13,15  \mid 1,16 \mid 11,17 \}.
\end{equation*}
We have emphasized maximum-entry order by underlining the maximum elements in each block of $\pi$ (box of $\T$). 
\begin{align*}\T=
\begin{array}{c}
\scalebox{0.85}{
\begin{tikzpicture}[scale=.55]
\filldraw[fill=gray!20, draw=black] (0,3) rectangle (12.5,4);
\draw (0,3) rectangle (12.5,4);
\draw[line width=1] (1.5,3) -- (1.5,0) -- (0,0) -- (0,3) -- (10,3) -- (10,2) -- (0,2);
\draw[line width=1] (7.7,3) -- (7.7,1) -- (0,1);
\draw[line width=1] (5.4,3) -- (5.4,1);
\draw[line width=1] (12.5,3) -- (12.5,4) -- (15.5,4) -- (15.5,3) -- (12.5,3); \draw[line width=1] (13.75,4) -- (13.75,3);
\draw (1.5,4) -- (1.5,3); \draw (5.4,4) -- (5.4,3); \draw (7.7,4) -- (7.7,3); \draw (10,4) -- (10,3); \draw (11.25,4) -- (11.25,3);
%\draw[line width=1] (1.5,4) -- (1.5,3); \draw[line width=1] (5.4,4) -- (5.4,3); \draw[line width=1] (7.7,4) -- (7.7,3); \draw[line width=1] (10,4) -- (10,3); \draw[line width=1] (11.25,4) -- (11.25,3);
\path (13.1,3.5) node {$\underline{12}$}; \path (14.6,3.5) node {$1,\underline{16}$}; 
\path (.75,2.5) node {$\underline{3}$}; \path (3.4,2.5) node {$\underline{6}$}; \path (6.5,2.5) node {$\underline{8}$}; \path (8.8,2.5) node {$11,\underline{17}$};
\path (.75,1.5) node {$\underline{5}$}; \path (3.4,1.5) node {$4,7,10,\underline{14}$}; \path (6.5,1.5) node {$13,\underline{15}$};
\path (.75,0.5) node {$2,\underline{9}$};
\end{tikzpicture} }
\end{array}
\end{align*}

It follows from this definition and \eqref{closed-formula} that
\begin{equation}\label{equals-set-part-tab}
\m_{k,n}^\lambda =   \#\left(\begin{array}{l} \text{standard set-partition tableaux of shape $\lambda$ and} \\ \text{content equal to a set partition of $\{1,\ldots,k\}$}\end{array}\right).
\end{equation}

\subsection{Bijection between up-down and set-partition tableaux}

\begin{figure}
$$
\includegraphics[trim={2cm 13.0cm 2cm 5cm},clip,width=5.5in]{bijection} 
$$
\caption{\label{fig:bijection} The delete-insert bijection between a $(7,5)$-up-down tableaux of shape $[2,2,1]$ (the underlying sequence of shapes) and a set-partition tableaux of shape $[2,2,1]$ and content $\pi = \{ 1,3,5 \mid 2 \mid 4, 7 \mid 6 \}$ (the set-partition tableaux when $j=7$).}
\end{figure}


Given a set-partition tableau $\mathsf{T}$ of shape $\lambda \vdash n$ and content $\pi$, a set partition of $\{1, \ldots, k\}$, 
the following algorithm recursively produces a $(k,n)$-up-down tableau $([n]=\lambda^{(0)}, \lambda^{(\frac{1}{2})},$ $ \lambda^{(1)},$ $\ldots,$ $\lambda^{(k)}=\lambda)$ of shape $\lambda$.  An example is given in \cref{fig:bijection}.


\begin{itemize}
\item[(1)] Let $\lambda^{(k)} = \lambda$,  and set $\mathsf{T}^{(k)} = \mathsf{T}$.

\item[(2)] For $j = k, k-1, \ldots, 1$ (in descending order), do the following:

\begin{itemize}
\item[(a)] Let $\mathsf{T}^{(j-\frac{1}{2})}$ be the tableau obtained from $\mathsf{T}^{(j)}$ by removing the box $b$ that contains $j$. At this stage, $j$ will be the largest entry of $\mathsf{T}$ so this box will be removable. Let $\lambda^{(j-\frac{1}{2})}$ be the shape of $\mathsf{T}^{(j-\frac{1}{2})}$.
\item[(b)] Delete the entry $j$ from $b$. If $b$ is then empty,  add 0 to it.

\item[(c)] Let $\mathsf{T}^{(j-1)} = \mathsf{T}^{(j-\frac{1}{2})} \leftarrow b$ be the Schensted row insertion of $b$ into $\mathsf{T}^{(j-\frac{1}{2})}$, and let $\lambda^{(j-1)}$ be the shape of $\mathsf{T}^{(j-1)}$.
\end{itemize}

\end{itemize}
In \cite{BHH} we prove that this algorithm is a bijection.



\section{Irreducible modules for the partition algebra\label{sec:partalg}}

\subsection{Schur--Weyl duality}

We now examine the centralizer algebra,
\begin{equation}\label{def:centralizer}
 \Z_{k,n}: =\End_{\S_n}(\M_n^{\ot k}) =\{\varphi \in \End(\M_n^{\ot k}) \mid \varphi \sigma (x) = 
\sigma \varphi(x), \  \  \sigma \in \S_n, x \in \M_n^{\ot k}\},\end{equation} 
of the symmetric group action on $\M_n^{\ot k}$.   
Schur--Weyl duality tells us that the  irreducible modules $\Z_{k,n}^\lambda$  for the semisimple associative algebra 
 $\Z_{k,n}$ 
are indexed by the same subset $\Lambda_{k,n}$ that indexes the irreducible $\S_n$-modules in $\M_n^{\ot k}$.  When we compare the decompositions
\begin{equation}\label{SW1}
 \M_n^{\otimes k} \ \cong \ \underbrace{\bigoplus_{\lambda \in \Lambda_{k,\S_n}} \mathsf{m}_{k,n}^\lambda \S_n^\lambda}_{\text{as an $\S_n$-module}}
\ \cong \  \underbrace{\bigoplus_{\lambda \in \Lambda_{k,n}} f^\lambda \Z_{k,n}^\lambda}_{\text{as a $\Z_{k,n}$-module} }; 
\end{equation}
of $\M_n^{\otimes k}$ as an $\S_n$ and a $\Z_k(n)$-module, respectively, the dimensions and the multiplicities are reversed:
\begin{align}  
 \bullet &\quad \dim(\Z_{k,n}^\lambda)   = \mathsf{m}_{k,n}^\lambda   \hspace{.78in}   \text{(the multiplicity  of $\S_n^\lambda$ in $\M_n^{\ot k}$)}; \label{SW2} \\
 \bullet &\quad  \mathsf{mult}(\Z_{k,n}^\lambda) = \dim(\S_n^\lambda) =  f^\lambda  \quad   \text{(the number of standard tableaux of shape $\lambda$).} \label{SW3} 
 \end{align}
Furthermore, by general Artin-Wedderburn theory,  $\dim(\Z_{k,n})$ is the sum of the squares of the dimensions of its irreducible modules $\Z_{k,n}^\lambda$, and thus
\begin{equation} \label{SW4}
\dim(\Z_{k,n}) = \displaystyle{\sum_{\lambda\in \Lambda_{k,\S_n}} (\mathsf{m}_{k,n}^\lambda)^2} = \m_{2k,n}^{[n]} = \dim\big(\Z_{2k,n}^{[n]}\big).
\end{equation} 
The second equality in (\ref{SW4}) comes from observing that pairs of paths from the top of $\B(\S_n,\S_{n-1})$ to $\lambda$ on level $k$ are in bijection, by reversing the second path, to paths from the top of the diagram to $[n]$ on level $2k$. Alternatively,  $\Z_{k,n} =\End_{\S_n}(\M_n^{\ot k}) \cong (\M_n^{\ot 2k})^{\S_n}$, since the   
$\S_n$-invariants in $\M_n^{\ot 2k}$ correspond to copies of the trivial  module $\S_n^{[n]}$,
 and  $\m_{2k,n}^{[n]} = \dim\big(\Z_{2k,n}^{[n]}\big)$ is the number of trivial summands of $\M_n^{\ot 2k}$.   

\subsection{The partition algebra}

For $k \ge 0$ and $n \in \CC$, the partition algebra $\Pb_k(n)$ is a unital associative algebra with a basis of set partition diagrams.
It is semisimple for  $\param \not \in \{0,1, \ldots, 2k-2\}$ (\cite{MS2}, \cite{HR}). For a set partition $\pi$ of $\{1, \ldots, k,1',\ldots, k'\}$, the associated set partition diagram $d_\pi$ has two rows of vertices labeled by $1', \dots, k'$ on bottom and $1, \ldots, k$ on top, such that two vertices are in the same connected component of the diagram if and only if they are in the same block of the set partition. For example, 
\begin{equation} \label{eqn:setpartition}
\pi = \left\{
\begin{array}{l}
1',2 \ \mid \ 2',3' \ \mid \ 4',1,3 \ \mid  \ 5',7'   \\
\ \mid 6', 4, 7, 8 \ \mid \ 8',6 \ \mid \ 5 \end{array} \right\}
\qquad \longleftrightarrow\qquad
d_\pi = \begin{array}{c}
\scalebox{0.75}{\begin{tikzpicture}[scale=.6,line width=1.35pt] 
\foreach \i in {1,...,8} 
{ \path (\i,2) coordinate (T\i); \path (\i,0) coordinate (B\i); } 
%%%%%%%
\filldraw[fill=gray!25,draw=gray!25,line width=4pt]  (T1) -- (T8) -- (B8) -- (B1) -- (T1);
\draw (T3) -- (B4);
\draw (T2) -- (B1);
\draw (T6) -- (B8);
\draw (T4)  .. controls +(.1,-1) and +(-.1,.7) .. (B6);
\draw (T1) .. controls +(.1,-.8) and +(-.1,-.8) .. (T3) ;
\draw (T4) .. controls +(.1,-.8) and +(-.1,-1) .. (T7) ;
\draw (T7) .. controls +(.1,-.6) and +(-.1,-.6) .. (T8) ;
\draw (B2) .. controls +(.1,.6) and +(-.1,.6) .. (B3) ;
{\draw (B5) .. controls +(.1,.8) and +(-.1,.8) .. (B7) ;}
\foreach \i in {1,...,8}
{\draw  (B\i)  node[below=0.05cm]{${\i'}$}; \draw  (T\i)  node[above=0.05cm]{${\i}$};}
\foreach \i in {1,...,8} 
{ \fill (T\i) circle (4.5pt); \fill (B\i) circle (4.5pt); } 
\end{tikzpicture}} \end{array}.
\end{equation}
 The number of set partitions of $\{1, \ldots, k,1',\ldots, k'\}$ with $t$ blocks is given by the Stirling number of the 2nd kind $\stirling{2k}{t}$, and $\dim(\Pb_k(n)) = \BB(2k) = \sum_t  \stirling{2k}{t}$, the $2k$th Bell number. 

Multiplication of  two diagrams $d_1$, $d_2$ is accomplished by placing $d_1$ above $d_2$,
identifying the vertices in the bottom row of $d_1$ with those in the top row of $d_2$,
concatenating  the edges,  deleting all connected components that lie entirely in the middle row of the joined diagrams, and scaling the resulting diagram by $x^{c(d_1,d_2)}$, where $c(d_1,d_2)$ is the number of components removed from the middle row.  For example, 
\begin{equation}\label{eq:diagrammultexample}
\begin{array}{r}
\begin{array}{c}
\scalebox{0.75}{\begin{tikzpicture}[scale=.55,line width=1.35pt] 
\foreach \i in {1,...,12} 
{ \path (\i,2) coordinate (T\i); \path (\i,0) coordinate (B\i); } 
%%%%%%%
\filldraw[fill=gray!25,draw=gray!25,line width=4pt]  (T1) -- (T12) -- (B12) -- (B1) -- (T1);
\draw (T2) .. controls +(.1,-.6) and +(-.1,-.6) .. (T3) ;
\draw (T6) .. controls +(.1,-.6) and +(-.1,-.6) .. (T7) ;
\draw (T3) .. controls +(.1,-.8) and +(-.1,-.8) .. (T5) ;
\draw (T9) .. controls +(.1,-.8) and +(-.1,-.8) .. (T11) ;
\draw (T10) .. controls +(.1,-.8) and +(-.1,-.8) .. (T12) ;
\draw (B3) .. controls +(.1,.8) and +(-.1,.8) .. (B5) ;
\draw (B8) .. controls +(.1,.8) and +(-.1,.8) .. (B10) ;
\draw (B7) .. controls +(.1,1.3) and +(-.1,1.3) .. (B12) ;
\draw (B1) -- (T4);
\draw (B2) -- (T1);
\draw (B6) .. controls +(.1,1) and +(-.1,-.8) .. (T9) ;
\draw (B9) -- (T8);
\draw (B11) .. controls +(.1,.6) and +(-.1,-.6) .. (T12) ;
%%%
\foreach \i in {1,...,12}  { \fill (T\i) circle (4.5pt); \fill (B\i) circle (4.5pt); } 
\end{tikzpicture}}\end{array} \\
\begin{array}{c}
\scalebox{0.75}{\begin{tikzpicture}[scale=.55,line width=1.35pt] 
\foreach \i in {1,...,12} 
{ \path (\i,2) coordinate (T\i); \path (\i,0) coordinate (B\i); } 
%%%%%%%
\filldraw[fill=gray!25,draw=gray!25,line width=4pt]  (T1) -- (T12) -- (B12) -- (B1) -- (T1);
\draw (T1) .. controls +(.1,-.6) and +(-.1,-.6) .. (T2) ;
\draw (T7) .. controls +(.1,-.6) and +(-.1,-.6) .. (T8) ;
\draw (T10) .. controls +(.1,-.8) and +(-.1,-.8) .. (T12) ;
\draw (T3) .. controls +(.1,-1) and +(-.1,-1) .. (T6) ;
\draw (B3) .. controls +(.1,.6) and +(-.1,.6) .. (B4) ;
\draw (B6) .. controls +(.1,.6) and +(-.1,.6) .. (B7) ;
\draw (B10) .. controls +(.1,.6) and +(-.1,.6) .. (B11) ;
\draw (B1) .. controls +(.1,.8) and +(-.1,.8) .. (B3) ;
\draw (B9) .. controls +(.1,1) and +(-.1,1) .. (B12) ;
\draw (B2) -- (T2);
\draw (B6) -- (T5);
\draw (B8) .. controls +(.1,1) and +(-.1,-.8) .. (T11) ;
\draw (B10) .. controls +(-.1,.6) and +(.1,-.6) .. (T9) ;
%%%% 
\foreach \i in {1,...,12}  { \fill (T\i) circle (4.5pt); \fill (B\i) circle (4.5pt); } 
\end{tikzpicture}}\end{array} \end{array} 
= x^2
\begin{array}{c}  
\scalebox{0.75}{\begin{tikzpicture}[scale=.55,line width=1.35pt] 
\foreach \i in {1,...,12} 
{ \path (\i,2) coordinate (T\i); \path (\i,0) coordinate (B\i); } 
%%%%%%%
\filldraw[fill=gray!25,draw=gray!25,line width=4pt]  (T1) -- (T12) -- (B12) -- (B1) -- (T1);
\draw (T2) .. controls +(.1,-.6) and +(-.1,-.6) .. (T3) ;
\draw (T6) .. controls +(.1,-.6) and +(-.1,-.6) .. (T7) ;
\draw (T3) .. controls +(.1,-.8) and +(-.1,-.8) .. (T5) ;
\draw (T9) .. controls +(.1,-.8) and +(-.1,-.8) .. (T11) ;
\draw (T10) .. controls +(.1,-.8) and +(-.1,-.8) .. (T12) ;
\draw (B3) .. controls +(.1,.6) and +(-.1,.6) .. (B4) ;
\draw (B6) .. controls +(.1,.6) and +(-.1,.6) .. (B7) ;
\draw (B10) .. controls +(.1,.6) and +(-.1,.6) .. (B11) ;
\draw (B1) .. controls +(.1,.8) and +(-.1,.8) .. (B3) ;
\draw (B9) .. controls +(.1,1) and +(-.1,1) .. (B12) ;
\draw (T1) -- (B2) -- (T4);
\draw (B7) .. controls +(.1,.6) and +(-.1,-.6) .. (T9) ;
\draw (B8) .. controls +(.1,.6) and +(-.1,-.6) .. (T10) ;
\draw (B10) .. controls +(-.1,.6) and +(.1,-.6) .. (T8) ;
%%%% 
\foreach \i in {1,...,12} { \fill (T\i) circle (4.5pt); \fill (B\i) circle (4.5pt); } 
\end{tikzpicture} }
 \end{array} 
 \end{equation} 
 
For $k \in \ZZ_{\geq 1}$,  the partition algebra $\Pb_k(n)$  has a presentation by the generators
\begin{equation}
\label{s-gen}
\begin{array}{ccc}
\mathfrak{s}_i =  \!
\begin{array}{c}\scalebox{.75}{\begin{tikzpicture}[scale=.55,line width=1.35pt] 
\foreach \i in {1,...,8} 
{ \path (\i,2) coordinate (T\i); \path (\i,0) coordinate (B\i); } 
\filldraw[fill=gray!25,draw=gray!25,line width=4pt]  (T1) -- (T8) -- (B8) -- (B1) -- (T1);
\draw (T1) -- (B1);
\draw (T3) -- (B3);
\draw (T4) -- (B5);
\draw (T5) -- (B4);
\draw (T6) -- (B6);
\draw (T8) -- (B8);
\foreach \i in {1,3,4,5,6,8} { \fill (T\i) circle (4.5pt); \fill (B\i) circle (4.5pt); } 
\draw (T2) node  {$\cdots$}; \draw (B2) node  {$\cdots$}; \draw (T7) node  {$\cdots$}; \draw (B7) node  {$\cdots$}; 
\draw  (T4)  node[black,above=0.05cm]{$\scriptstyle{i}$};
\draw  (T5)  node[black,above=0.0cm]{$\scriptstyle{i+1}$};
\end{tikzpicture}}\end{array},
&
\ \mathfrak{p}_i = \!
\begin{array}{c}\scalebox{0.75}{\begin{tikzpicture}[scale=.55,line width=1.35pt] 
\foreach \i in {1,...,8} 
{ \path (\i,2) coordinate (T\i); \path (\i,0) coordinate (B\i); } 
\filldraw[fill=gray!25,draw=gray!25,line width=4pt]  (T1) -- (T8) -- (B8) -- (B1) -- (T1);
\draw (T1) -- (B1);
\draw (T3) -- (B3);
\draw (T5) -- (B5);
\draw (T6) -- (B6);
\draw (T8) -- (B8);
\foreach \i in {1,3,4,5,6,8} { \fill (T\i) circle (4.5pt); \fill (B\i) circle (4.5pt); } 
\draw (T2) node  {$\cdots$}; \draw (B2) node  {$\cdots$}; \draw (T7) node  {$\cdots$}; \draw (B7) node  {$\cdots$}; 
\draw  (T4)  node[black,above=0.05cm]{$\scriptstyle{i}$};
\end{tikzpicture}}\end{array},
&
\ \mathfrak{b}_i =  \!
\begin{array}{c}\scalebox{0.75}{\begin{tikzpicture}[scale=.55,line width=1.35pt] 
\foreach \i in {1,...,8} 
{ \path (\i,2) coordinate (T\i); \path (\i,0) coordinate (B\i); } 
\filldraw[fill=gray!25,draw=gray!25,line width=4pt]  (T1) -- (T8) -- (B8) -- (B1) -- (T1);
\draw (T1) -- (B1);
\draw (T3) -- (B3);
\draw (T4) .. controls +(.1,-.6) and +(-.1,-.6) .. (T5);
\draw (B4) .. controls +(.1,+.60) and +(-.1,+.6) .. (B5);
\draw (T4) -- (B4);
\draw (T5) -- (B5);
\draw (T6) -- (B6);
\draw (T8) -- (B8);
\foreach \i in {1,3,4,5,6,8} { \fill (T\i) circle (4.5pt); \fill (B\i) circle (4.5pt); } 
\draw (T2) node  {$\cdots$}; \draw (B2) node  {$\cdots$}; \draw (T7) node  {$\cdots$}; \draw (B7) node  {$\cdots$}; 
\draw  (T4)  node[black,above=0.05cm]{$\scriptstyle{i}$};
\draw  (T5)  node[black,above=0.0cm]{$\scriptstyle{i+1}$};
\end{tikzpicture}}\end{array} \\
\hskip.3in 1 \leq i \leq k-1 &\hskip.3in 1 \leq i \leq k &\hskip.3in 1 \leq i \leq k-1
\end{array}
\end{equation}
and the relations found in  \cite[Thm.~1.11]{HR}. 

 In \cite{Jo}, V. Jones constructed a surjective algebra homomorphism
\begin{equation}\label{eq:Phi}
\Phi_{k,n}:  \Pb_k(n) \rightarrow \Z_{k,n} = \End_{\S_n}(\M_n^{\ot k})
\end{equation}
from the partition algebra  
onto the centralizer algebra  $\End_{\S_n}(\M_n^{\ot k})$  defined in \eqref{def:centralizer}.   When $n \ge 2k$, this surjection is an isomorphism.   The kernel of $\Phi_{k,n}$ is described in \cite{HR}, and in \cite{BH-invariant1} it is shown to be 
 a two-sided ideal  $\ker(\Phi_{k,n}) = \langle \mathsf{e}_{k,n} \rangle$  generated  by a single idempotent.
 
\subsection{Subalgebras} \label{sec:subalgebras} The partition algebra is a central object in algebraic combinatorics. The group algebra of the symmetric group $\CC \S_k = \langle \mathfrak{s}_i \rangle_{1 \le i < k}$ is the subalgebra of $\Pb_k(n)$ generated by the simple transpositions $\mathfrak{s}_i$. If we define $\mathfrak{e}_i = \mathfrak{b}_i \mathfrak{p}_i \mathfrak{p}_{i+1} \mathfrak{b}_i$, then Brauer's centralizer algebra $\mathbf{B}_k(n) =  \langle \mathfrak{s}_i, \mathfrak{e}_i \rangle_{1 \le i < k}$ and the Temperley--Lieb algebra $\mathbf{TL}_k(n) =  \langle \mathfrak{e}_i \rangle_{1 \le i < k}$ are subalgebras. The rook-monoid, rook-Brauer, Motzkin, and planar rook-monoid algebras are similarly generated as diagram subalgebras.  Moreover, it can be shown that if $\mathbf{G}$ is any group and $\V$ is any finite dimensional $\CC\mathbf{G}$-module, then  $\End_{\mathbf{G}}(\V^{\ot k})$ contains a quotient of the partition algebra as a subalgebra.


\subsection{Representation on set-partition tableaux}

When $n \ge 2k$, we have an isomorphism $\Phi_{k,n}:  \Pb_k(n) \rightarrow  \End_{\S_n}(\M_n^{\ot k})$, and so by Schur--Weyl duality \eqref{SW1}, the irreducible modules of the partition algebra are indexed by the partitions in $\Lambda_{k,n}$. For each $\lambda \in \Lambda_{k,n}$, we let $\Pb_k^\lambda$ denote this module. It follows from \eqref{SW2} that the dimension of  $\Pb_k^\lambda$ equals the number of standard set partition tableaux of shape $\lambda$ and content equal to a set partition of $\{1, \ldots, k\}$. The main result of \cite{HJ} is to give a basis of $\Pb_k^\lambda$ that is indexed by these set partition tableaux, and to give an action of $\Pb_k(n)$ on this basis that is analogous to Young's natural representation of $\S_k$. Upon restriction, this method gives analogs of Young's natural representations on set partition tableaux for each of the diagram subalgebras listed in \cref{sec:subalgebras}.

For $\lambda \in \Lambda_{k,n}$ let $\mathcal{SPT}(\lambda,k)$ denote the set of standard set partition tableaux of shape $\lambda$ and content equal to a set partition of $\{1, \ldots, k\}$. We let $\{ \N_\T \mid \T \in \mathcal{SPT}(\lambda,k)\}$ be a set of vectors indexed by $\mathcal{SPT}(\lambda,k)$ and define a vector space with these vectors as a basis,
\begin{equation}
\Pb_k^\lambda = \CC\text{-span}\{\, \N_\T \mid \T \in \mathcal{SPT}(\lambda,k)\}.
\end{equation}
For a set partition diagram $d \in \Pb_k(n)$  let $\tp(d)$ be the partition of $\{1,\ldots,k\}$ induced on the top row of $d$. 

\begin{defn} \label{def:dT} {\rm
For a diagram $d \in \Pb_k$ and a set partition $\pi$ of $\{1,\ldots,k\}$, let $d\circ \pi$ denote the diagram concatenation of $d$ with $\pi$, where $\pi$ is viewed as a one-line set-partition diagram. Given a  set-partition tableau $\T$ of shape $\lambda\vdash n$ and content $\pi$,  define the action of $d$ on $\T$, denoted $d(\T)$, to be the set-partition tableau of shape $\lambda$, where:
\begin{enumerate} 
\item[(a)] the propagating blocks in $d(\T)$ are obtained by replacing each propagating block of $\T$ with the block it is connected to in $\tp(d \circ \pi)$, 
\item[(b)] the non-propagating blocks in $d(\T)$ are the non-propagating blocks of $\tp(d\circ \pi)$ and  blocks of $\tp(d\circ \pi)$ that are connected only to non-propagating blocks of $\T$,
\item[(c)] the non-propagating blocks increase from left to right in the first row of $d(\T)$,
\item[(d)] if the results of this process do not produce a set-partition tableau, then $d(\T) = 0$.
\end{enumerate}
The action of a diagram $d$ on a tableau $\T$ is easily obtained by placing $d$ above $\T$, drawing edges from the blocks of $\T$ to the corresponding blocks on the bottom row of $d$, and performing diagram multiplication as seem in \cref{ex:dTpartition}.
}
\end{defn}

\begin{examp} \label{ex:dTpartition}
Here is a set-partition diagram $d$ acting on two set partition tableaux.
\begin{equation*}
\hspace{-0.75cm}
\begin{array}{c}
\scalebox{1}{
\begin{tikzpicture}[scale=0.55] 
\foreach \i in {1,...,13} 
{ \path (\i-2.1,5.4) coordinate (T\i); \path (\i-2.1,7.4) coordinate (t\i); \path (\i-2.1,5) coordinate (b\i);}
\path (0.5,1.5) coordinate (B1);
\path (2.9,1.5) coordinate (B2);
\path (7.5,2.65) coordinate (B3);
\path (2.35,0.75) coordinate (B4);
\path (9.35,2.5) coordinate (B5);
\path (5.1,1.85) coordinate (B6);
\path (4.1,0.55) coordinate (B7);
%%%DIAGRAM
\path (-2,6.4) node {$d=$};
\draw[rounded corners=.15mm, fill=gray!25,draw=gray!25,line width=4.5pt]  (t1) -- (t13) -- (T13) -- (T1) -- cycle;
\draw[line width = 1.35] (t5) .. controls +(.1,-.5) and +(-.1,-.5) .. (t6);
\draw[line width = 1.35] (t6) .. controls +(.1,-.5) and +(-.1,-.5) .. (t7);
\draw[line width = 1.35] (t8) .. controls +(.1,-1.2) and +(-.1,-1.2) .. (t12);
\draw[line width = 1.35] (t10) .. controls +(.1,-.5) and +(-.1,-.5) .. (t11);
\draw[line width = 1.35] (t7) .. controls +(.1,-.5) and +(-.1,.5) .. (T8);
\draw[line width = 1.35] (t1) .. controls +(.1,-.8) and +(-.1,.8) .. (T5);
\draw[line width = 1.35] (t8) .. controls +(.1,-.8) and +(-.1,.8) .. (T4);
\draw[line width = 1.35] (t9) .. controls +(.1,-.7) and +(-.1,.7) .. (T12);
\draw[line width = 1.35] (t2) -- (T2);
\draw[line width = 1.35] (t3) -- (T3);
\draw[line width = 1.35] (t13) -- (T13);
\draw[line width = 1.35] (T1) .. controls +(.1,.7) and +(-.1,.7) .. (T3);
\draw[line width = 1.35] (T9) .. controls +(.1,.5) and +(-.1,.5) .. (T10);
%%%TABLEAU
\path (-1,1.5) node {$\T=$};
\filldraw[fill=gray!20, draw=black] (0,2) rectangle (6.75,3);
\draw (2.5,2) -- (2.5,3); \draw (4.25,2) -- (4.25,3); \draw (5.25,2) -- (5.25,3);
\draw[line width = 1] (4.25,2) -- (4.25,0) -- (0,0) -- (0,2) -- (5.25,2) -- (5.25,1) -- (0,1);
\draw[line width = 1] (2.5,0) -- (2.5,2);
\draw[line width = 1] (6.75,2) -- (9.85,2) -- (9.85,3) -- (6.75,3) -- (6.75,2); \draw[line width = 1] (8.85,2) -- (8.85,3);
\path (6.1,2.5) node {$\cdots$};
\path (7.8,2.5) node {$3,5,\underline{6}$};  \path (9.35,2.5) node {$\underline{11}$}; 
\path (1.25,1.5) node {$1,\underline{2}$}; \path (3.375,1.5) node {$\underline{4}$}; \path (4.75,1.5) node {$\underline{12}$};
 \path (1.25,0.5) node {$8,9,\underline{10}$}; \path (3.35,0.5) node {$7,\underline{13}$}; 
 %%%CONNECTIONS
 \begin{knot}[clip width=3,end tolerance=2pt]
 \strand[line width = 1] (b4) .. controls +(.5,-1) and +(-.5,1) .. (B2);
\strand[line width = 1] (b3) .. controls +(.1,-.9) and +(-.1,-.9) .. (b5);
\strand[line width = 1] (b5) .. controls +(.1,-.7) and +(-.1,-.7) .. (b6);
\strand[line width = 1] (b1) .. controls +(.1,-.7) and +(-.1,-.7) .. (b2);
\strand[line width = 1] (b2) .. controls +(.5,-1) and +(-.5,1) .. (B1);
\strand[line width = 1] (b12)  .. controls +(3,-5) and +(1,-0.5) .. (B6);
 \strand[line width = 1] (b10) .. controls +(-.5,-2) and +(.5,0.5) .. (B4);
\strand[line width = 1] (b7) .. controls +(.1,-1.2) and +(-.1,-1) .. (b13);
\strand[line width = 1] (b13) .. controls +(2,-5) and +(1,-0.5) .. (B7);
\strand[line width = 1] (b11) .. controls +(.1,-.5) and +(-.1,.5) .. (B5);
\strand[line width = 1] (b6) .. controls +(.5,-2) and +(-.5,2) .. (B3);
\end{knot}
 \draw[line width = 1] (b8) .. controls +(.1,-.7) and +(-.1,-.7) .. (b9);
\draw[line width = 1] (b9) .. controls +(.1,-.7) and +(-.1,-.5) .. (b10);
\foreach \i in {1,...,7} { \fill (B\i) circle (2.5pt); } 
\foreach \i in {1,...,13} {\draw[line width=1] (b\i) -- (T\i); \fill (T\i) circle (4pt); \fill (t\i) circle (4pt); \fill (b\i) circle (4pt); 
\draw  (t\i)  node[above=0.05cm]{${\scriptstyle \i}$}; } 
\end{tikzpicture} } 
\end{array} \hspace{-1cm} = \begin{array}{c}
\scalebox{1}{
\begin{tikzpicture}[scale=0.55] 
\filldraw[fill=gray!20, draw=black] (0,2) rectangle (6.25,3);
\draw (2.125,2) -- (2.125,3); \draw (3.875,2) -- (3.875,3); \draw (4.75,2) -- (4.75,3);
\draw[line width = 1] (3.875,2) -- (3.875,0) -- (0,0) -- (0,2) -- (4.75,2) -- (4.75,1) -- (0,1);
\draw[line width = 1] (2.125,0) -- (2.125,2); \draw[line width = 1] (7.1,2) -- (7.1,3);
\draw[line width = 1] (6.25,2) -- (9.15,2) -- (9.15,3) -- (6.25,3) -- (6.25,2);
\path (5.6,2.5) node {$\cdots$};
 \path (6.65,2.5) node {$\underline{4}$}; \path (8.1, 2.5) node {$10,\underline{11}$};
\path (1.0625,1.5) node {$1,2,\underline{3}$}; \path (3,1.5) node {$8,\underline{12}$}; \path (4.3,1.5) node {$\underline{9}$};
 \path (1.0625,0.5) node {$5,6,\underline{7}$}; \path (3,0.5) node {$\underline{13}$}; 
\end{tikzpicture} } 
\end{array}\hspace{-0.25cm} = d(\T).
\end{equation*}
The following diagram acts as zero on $\T$, since the result is not a set-partition tableau.
\begin{equation*}
\hspace{-0.75cm}
\begin{array}{c}
\scalebox{1}{
\begin{tikzpicture}[scale=0.55] 
\foreach \i in {1,...,13} 
{ \path (\i-2.1,5.4) coordinate (T\i); \path (\i-2.1,7.4) coordinate (t\i); \path (\i-2.1,5) coordinate (b\i);}
\path (0.5,1.5) coordinate (B1);
\path (2.9,1.5) coordinate (B2);
\path (7.5,2.65) coordinate (B3);
\path (2.35,0.75) coordinate (B4);
\path (9.35,2.5) coordinate (B5);
\path (5.1,1.85) coordinate (B6);
\path (4.1,0.55) coordinate (B7);
%%%DIAGRAM
\path (-2,6.4) node {$d=$};
\draw[rounded corners=.15mm, fill=gray!25,draw=gray!25,line width=4.5pt]  (t1) -- (t13) -- (T13) -- (T1) -- cycle;
\draw[line width = 1.35] (t1) .. controls +(.1,-.5) and +(-.1,-.5) .. (t2);
\draw[line width = 1.35] (t3) .. controls +(.1,-1) and +(-.1,-1) .. (t6);
\draw[line width = 1.35] (t8) .. controls +(.1,-.5) and +(-.1,-.5) .. (t9);
\draw[line width = 1.35] (t12) .. controls +(.1,-.5) and +(-.1,-.5) .. (t13);
\draw[line width = 1.35] (t10) .. controls +(.1,-.8) and +(-.1,-.8) .. (t12);
\draw[line width = 1.35] (T2) .. controls +(.1,.5) and +(-.1,.5) .. (T3);
\draw[line width = 1.35] (T8) .. controls +(.1,.5) and +(-.1,.5) .. (T9);
\draw[line width = 1.35] (T6) .. controls +(.1,.8) and +(-.1,.8) .. (T8);
\draw[line width = 1.35] (t2) .. controls +(.1,-1) and +(-.1,1) .. (T5);
\draw[line width = 1.35] (t4)  .. controls +(-.1,-.8) and +(.1,.8) ..  (T3);
\draw[line width = 1.35] (t6) .. controls +(-.1,-1) and +(.1,.8) .. (T4);
\draw[line width = 1.35] (t7) -- (T7);
\draw[line width = 1.35] (t10) .. controls +(.1,-1) and +(-.1,.8) .. (T11);
\draw[line width = 1.35] (t11) .. controls +(.1,-.8) and +(-.1,.8) .. (T13);
%%%TABLEAU
\path (-1,1.5) node {$\T=$};
\filldraw[fill=gray!20, draw=black] (0,2) rectangle (6.75,3);
\draw (2.5,2) -- (2.5,3); \draw (4.25,2) -- (4.25,3); \draw (5.25,2) -- (5.25,3);
\draw[line width = 1] (4.25,2) -- (4.25,0) -- (0,0) -- (0,2) -- (5.25,2) -- (5.25,1) -- (0,1);
\draw[line width = 1] (2.5,0) -- (2.5,2);
\draw[line width = 1] (6.75,2) -- (9.85,2) -- (9.85,3) -- (6.75,3) -- (6.75,2); \draw[line width = 1] (8.85,2) -- (8.85,3);
\path (6.1,2.5) node {$\cdots$};
\path (7.8,2.5) node {$3,5,\underline{6}$};  \path (9.35,2.5) node {$\underline{11}$}; 
\path (1.25,1.5) node {$1,\underline{2}$}; \path (3.375,1.5) node {$\underline{4}$}; \path (4.75,1.5) node {$\underline{12}$};
 \path (1.25,0.5) node {$8,9,\underline{10}$}; \path (3.35,0.5) node {$7,\underline{13}$}; 
 %%%CONNECTIONS
 \begin{knot}[clip width=3,end tolerance=2pt]
\strand[line width = 1] (b4) .. controls +(.5,-1) and +(-.5,1) .. (B2);
\strand[line width = 1] (b3) .. controls +(.1,-.9) and +(-.1,-.9) .. (b5);
\strand[line width = 1] (b5) .. controls +(.1,-.7) and +(-.1,-.7) .. (b6);
\strand[line width = 1] (b1) .. controls +(.1,-.7) and +(-.1,-.7) .. (b2);
\strand[line width = 1] (b2) .. controls +(.5,-1) and +(-.5,1) .. (B1);
\strand[line width = 1] (b12)  .. controls +(3,-5) and +(1,-0.5) .. (B6);
\strand[line width = 1] (b10) .. controls +(-.5,-2) and +(.5,0.5) .. (B4);
\strand[line width = 1] (b7) .. controls +(.1,-1.2) and +(-.1,-1) .. (b13);
\strand[line width = 1] (b13) .. controls +(2,-5) and +(1,-0.5) .. (B7);
\strand[line width = 1] (b11) .. controls +(.1,-.5) and +(-.1,.5) .. (B5);
\strand[line width = 1] (b6) .. controls +(.5,-2) and +(-.5,2) .. (B3);
\end{knot}
 \draw[line width = 1] (b8) .. controls +(.1,-.7) and +(-.1,-.7) .. (b9);
\draw[line width = 1] (b9) .. controls +(.1,-.7) and +(-.1,-.5) .. (b10);
\foreach \i in {1,...,7} { \fill (B\i) circle (2.5pt); } 
\foreach \i in {1,...,13} {\draw[line width=1] (b\i) -- (T\i); \fill (T\i) circle (4pt); \fill (t\i) circle (4pt); \fill (b\i) circle (4pt); 
\draw  (t\i)  node[above=0.05cm]{${\scriptstyle \i}$}; } 
\end{tikzpicture} } 
\end{array} \hspace{-1cm} = \begin{array}{c}
\scalebox{1}{
\begin{tikzpicture}[scale=0.55] 
\filldraw[fill=gray!20, draw=black] (0,2) rectangle (6.25,3);
\draw (2.125,2) -- (2.125,3); \draw (3.875,2) -- (3.875,3); \draw (4.75,2) -- (4.75,3);
\draw[line width = 1] (3.875,2) -- (3.875,0) -- (0,0) -- (0,2) -- (4.75,2) -- (4.75,1) -- (0,1);
\draw[line width = 1] (2.125,0) -- (2.125,2); \draw[line width = 1] (7.1,2) -- (7.1,3);
\draw[line width = 1] (6.25,2) -- (8.5,2) -- (8.5,3) -- (6.25,3) -- (6.25,2);
\draw[line width = 1] (8.5,3) -- (11.5,3) -- (11.5,2) -- (8.5,2);
\path (5.6,2.5) node {$\cdots$};
 \path (6.65,2.5) node {$\underline{5}$}; \path (7.8, 2.5) node {$8,\underline{9}$}; \path (10, 2.5) node {$10,12,\underline{13}$};
\path (1.0625,1.5) node {$1,2,\underline{4}$}; \path (3,1.5) node {$3,\underline{6}$}; \path (4.3,1.5) node {$$};
 \path (1.0625,0.5) node {$1,2,\underline{4}$}; \path (3,0.5) node {$7,\underline{11}$}; 
\end{tikzpicture} } 
\end{array}\hspace{-0.25cm} =0.
\end{equation*}
\end{examp}


For a diagram $d \in \Pb_k(n)$ and $\T \in \SPT(\lambda,k)$ define
\begin{equation}  \label{eqn:naturalaction} 
d\cdot \N_\T = \begin{cases} 
n^{\ell(d,\T)} \N_{d(\T)} & \text{if $d(\T)$ is a set-partition tableau, } \\
0 & \text{if $d(\T)$ is not a set-partition tableau, }
\end{cases} 
\end{equation}
where $d(\T)$ is defined in \cref{def:dT} and $\ell(d,\T)$ is the number of connected components removed in the construction of $d(\T)$. If $d(\T)$ is not standard, then $\N_{d(\T)}$ can be expressed as an integer linear combination of basis elements using Garnir relations  (see, for example, \cite{Sa} or \cite{Turbo}). One can also apply the method of tableaux intersection  \cite{GM}.


\begin{examp}{\rm
Let $d$ and $\T$ be defined as in the first example from \cref{ex:dTpartition}. In the construction of $d(\T)$ there is one connected component removed, so that
\begin{equation*}
d\cdot \N_\T =n \N_{d(\T)}, \text{ where } d(\T) = 
\begin{array}{c}
\scalebox{0.9}{
\begin{tikzpicture}[scale=0.55] 
\filldraw[fill=gray!20, draw=black] (0,2) rectangle (6.25,3);
\draw (2.125,2) -- (2.125,3); \draw (3.875,2) -- (3.875,3); \draw (4.75,2) -- (4.75,3);
\draw[line width = 1] (3.875,2) -- (3.875,0) -- (0,0) -- (0,2) -- (4.75,2) -- (4.75,1) -- (0,1);
\draw[line width = 1] (2.125,0) -- (2.125,2); \draw[line width = 1] (7.1,2) -- (7.1,3);
\draw[line width = 1] (6.25,2) -- (9.15,2) -- (9.15,3) -- (6.25,3) -- (6.25,2);
\path (5.6,2.5) node {$\cdots$};
 \path (6.65,2.5) node {$\underline{4}$}; \path (8.1, 2.5) node {$10,\underline{11}$};
\path (1.0625,1.5) node {$1,2,\underline{3}$}; \path (3,1.5) node {$8,\underline{12}$}; \path (4.3,1.5) node {$\underline{9}$};
 \path (1.0625,0.5) node {$5,6,\underline{7}$}; \path (3,0.5) node {$\underline{13}$}; 
\end{tikzpicture} } 
\end{array}.
\end{equation*}
The result is nonstandard, and the Garnir relation for straightening $\N_{d(\T)}$ is:
\begin{equation*}
\begin{array}{c}
\scalebox{0.85}{
\begin{tikzpicture}[scale=0.55] 
\filldraw[fill=gray!20, draw=black] (0,2) rectangle (6.25,3);
\draw (2.125,2) -- (2.125,3); \draw (3.875,2) -- (3.875,3); \draw (4.75,2) -- (4.75,3);
\draw[line width = 1] (3.875,2) -- (3.875,0) -- (0,0) -- (0,2) -- (4.75,2) -- (4.75,1) -- (0,1);
\draw[line width = 1] (2.125,0) -- (2.125,2); \draw[line width = 1] (7.1,2) -- (7.1,3);
\draw[line width = 1] (6.25,2) -- (9.15,2) -- (9.15,3) -- (6.25,3) -- (6.25,2);
\path (5.6,2.5) node {$\cdots$};
 \path (6.65,2.5) node {$\underline{4}$}; \path (8.1, 2.5) node {$10,\underline{11}$};
\path (1.0625,1.5) node {$1,2,\underline{3}$}; \path (3,1.5) node {$8,\underline{11}$}; \path (4.3,1.5) node {$\underline{9}$};
 \path (1.0625,0.5) node {$5,6,\underline{7}$}; \path (3,0.5) node {$\underline{12}$}; 
\end{tikzpicture} } 
\end{array} =
\begin{array}{c}
\scalebox{0.85}{
\begin{tikzpicture}[scale=0.55] 
\filldraw[fill=gray!20, draw=black] (0,2) rectangle (6.35,3);
\draw (2.125,2) -- (2.125,3); \draw (3.125,2) -- (3.125,3); \draw (4.85,2) -- (4.85,3);
\draw[line width = 1] (3.125,2) -- (3.125,0) -- (0,0) -- (0,2) -- (4.85,2) -- (4.85,1) -- (0,1);
\draw[line width = 1] (2.125,0) -- (2.125,2); \draw[line width = 1] (7.2,2) -- (7.2,3);
\draw[line width = 1] (6.35,2) -- (9.25,2) -- (9.25,3) -- (6.35,3) -- (6.35,2);
\path (5.7,2.5) node {$\cdots$};
 \path (6.75,2.5) node {$\underline{4}$}; \path (8.2, 2.5) node {$10,\underline{11}$};
\path (1.0625,1.5) node {$1,2,\underline{3}$}; \path (2.625,1.5) node {$\underline{9}$}; \path (4,1.5) node {$8,\underline{11}$};
 \path (1.0625,0.5) node {$5,6,\underline{7}$}; \path (2.625,0.5) node {$\underline{12}$}; 
\end{tikzpicture} } 
\end{array} - 
\begin{array}{c}
\scalebox{0.85}{
\begin{tikzpicture}[scale=0.55] 
\filldraw[fill=gray!20, draw=black] (0,2) rectangle (6.45,3);
\draw (2.125,2) -- (2.125,3); \draw (3.875,2) -- (3.875,3); \draw (4.95,2) -- (4.95,3);
\draw[line width = 1] (3.875,2) -- (3.875,0) -- (0,0) -- (0,2) -- (4.95,2) -- (4.95,1) -- (0,1);
\draw[line width = 1] (2.125,0) -- (2.125,2); \draw[line width = 1] (7.3,2) -- (7.3,3);
\draw[line width = 1] (6.45,2) -- (9.35,2) -- (9.35,3) -- (6.45,3) -- (6.45,2);
\path (5.8,2.5) node {$\cdots$};
 \path (6.85,2.5) node {$\underline{4}$}; \path (8.3, 2.5) node {$10,\underline{11}$};
\path (1.0625,1.5) node {$1,2,\underline{3}$}; \path (3,1.5) node {$\underline{9}$}; \path (4.4,1.5) node {$\underline{12}$};
 \path (1.0625,0.5) node {$5,6,\underline{7}$}; \path (3,0.5) node {$8,\underline{11}$}; 
\end{tikzpicture} } 
\end{array}, 
\end{equation*}
and hence 
$
d\cdot \N_\T =n \N_{\T_1} - n \N_{\T_2},
$
where $\T_1$ and $\T_2$ are the two standard set-partition tableaux appearing above. }
\end{examp}

\begin{thm} [\cite{HJ}] \label{thm:naturalrep}
The action defined in~\eqref{eqn:naturalaction} makes $\{\Pb^\lambda_k \mid \lambda \in \SPT(\lambda)\}$ into a complete set of pairwise-nonisomorphic $\Pb_k(n)$-modules. 
\end{thm}

When the action is specialized to the partition algebra generators found in \eqref{s-gen}, then the action on set-partition tableaux is especially nice.

\begin{thm} [\cite{HJ}] \label{thm:generatorsactionSPT}
Let $\lambda \in \Lambda_{k,n}$ and let $\T$ be a standard set partition tableau. Then
%The action of $\mathfrak{s}_i$, $\mathfrak{p}_i$, $\mathfrak{b}_i$, and $\mathfrak{e}_i$ on $\N_\T$ are given by:
\begin{enumerate}

\item[{\rm (a)}] $\displaystyle \mathfrak s_i \cdot \N_\T = \N_{\mathfrak s_i(\T)},$ where $\mathfrak s_i(\T)$ is the set-partition tableau obtained from $\T$ by swapping $i$ and $i+1$, and standardizing the first row. 


\item[{\rm (b)}]  $\displaystyle \mathfrak p_i \cdot \N_\T = \begin{cases}
n \N_{\T} & \text{if $\{i\}$ is a non-propagating singleton block in $\T$, }\\
0 & \text{if $\{i\}$ is a propagating singleton block in $\T$, }\\
\N_{\mathfrak p_i(\T)} & \text{otherwise, } 
\end{cases}$

\noindent
where $\mathfrak p_i(\T)$ is the set-partition tableau obtained from $\T$ by removing $i$ from its block, 
placing the singleton block $\{i\}$ into the first row,
and standardizing the first row.   


\item [{\rm (c)}] $\displaystyle \mathfrak b_i \cdot \N_\T = \begin{cases}
\N_{\T} & \text{if $i$ and $i+1$ are in the same block in $\T$, }\\
0 & \text{if $i$ and $i+1$ are in different propagating blocks in $\T$,} \\
\N_{\mathfrak b_i(\T)} & \text{otherwise, } 
\end{cases}$

\noindent
where $\mathfrak b_i(\T)$ is  obtained from $\T$ by joining the block containing $i$ with the block containing $i+1$, and standardizing the first row.  
The resulting block becomes propagating if one of the original blocks was propagating, and otherwise stays non-propagating. 



\end{enumerate}
If ${\mathfrak s_i(\T)}$, ${\mathfrak p_i(\T)}$, ${\mathfrak b_i(\T)}$
is a nonstandard set-partition tableau then $\N_{\mathfrak s_i(\T)}$, $\N_{\mathfrak p_i(\T)}$, $\N_{\mathfrak b_i(\T)}$ 
can be expressed as an integer linear combination of basis elements using Garnir relations.% (see Section~\ref{subsec:choiceofbasis1}).
\end{thm}




\printbibliography



\end{document}
