
\documentclass[finalversion]{FPSAC2020}
\articlenumber{48}
\addbibresource{fpsac.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\usepackage{enumitem}

%% note that the class file already loads {amsmath, amsthm, amssymb}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}

\theoremstyle{definition}
\newtheorem{example}[thm]{Example}
\newtheorem{definition}[thm]{Definition}
\newtheorem{remark}[thm]{Remark}
\numberwithin{equation}{section}


\title[An insertion algorithm for diagram algebras]{An insertion algorithm for diagram algebras}


\author[L. Colmenarejo, R. Orellana, F. Saliola, A. Schilling, and M. Zabrocki]{
Laura Colmenarejo\thanks{\href{mailto:laura.colmenarejo.hernando@gmail.com}
 {laura.colmenarejo.hernando@gmail.com}.}\addressmark{1}, 
Rosa Orellana\thanks{\href{mailto:Rosa.C.Orellana@dartmouth.edu}
 {Rosa.C.Orellana@dartmouth.edu}. Supported by NSF grant DMS--1700058.}\addressmark{2}, 
Franco Saliola\thanks{\href{mailto:saliola.franco@uqam.ca}{saliola.franco@uqam.ca}. 
 Supported by NSERC Discovery Grants.}\addressmark{3}, 
Anne Schilling\thanks{\href{mailto:anne@math.ucdavis.edu}{anne@math.ucdavis.edu}. Supported by NSF grants DMS--1760329 and 1764153.}\addressmark{4}, 
\and Mike Zabrocki\thanks{\href{mailto:zabrocki@mathstat.yorku.ca}{zabrocki@mathstat.yorku.ca}. 
Supported by NSERC Discovery Grants.}\addressmark{5}}

%% then use \addressmark to match authors to institutions here
\address{
\addressmark{1}Department of Mathematics and Statistics, University of Massachusetts Amherst, MA, USA \\ 
\addressmark{2}Department of Mathematics, Dartmouth College, NH, USA.\\ 
\addressmark{3}D\'epartement de math\'ematiques, Universit\'e du Qu\'ebec \`a Montr\'eal, Canada\\ 
\addressmark{4}Department of Mathematics, University of California, Davis, CA, USA\\ 
\addressmark{5}Department of Mathematics and Statistics, York University, Toronto, Canada}

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

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


\abstract{We generalize the Robinson--Schensted--Knuth algorithm to the insertion of two row arrays of multisets. 
This generalization leads to an algorithm from partition diagrams to pairs of a standard tableau and a standard 
multiset tableau of the same shape, which has the remarkable property that it is well-behaved with respect to 
restricting a representation to a subalgebra. This insertion algorithm matches recent  representation-theoretic 
results of Halverson and Jacobson.}% \cite{HJ}.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{multisets, diagram algebras, RSK algorithm, enumerative results}



%% our packages
\usepackage{booktabs}
\usepackage{tikz,caption}
\usepackage{multirow}

%% our symbols and other commands
\newcommand{\ie}{\textit{i.e.}}
\newcommand{\SSYT}{\operatorname{SSYT}}
\newcommand{\SYT}{\operatorname{SYT}}
\newcommand{\SSMT}{\operatorname{SSMT}}
\newcommand{\SMT}{\operatorname{SMT}}
\newcommand{\cells}{\operatorname{cells}}
\newcommand{\wt}{\operatorname{wt}}
\newcommand{\cf}{\textit{cf.} }
\newcommand{\content}{\operatorname{content}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\pchoose}[2]{\begin{pmatrix}#1\\ #2\end{pmatrix}}
\newcommand{\bchoose}[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}}
\newcommand{\stirling}[2]{\left\{\begin{matrix}#1\\ #2\end{matrix}\right\}}
\newcommand{\smallstirling}[2]{\left\{\!\begin{smallmatrix}#1\\#2\end{smallmatrix}\!\right\}}
\newcommand{\smallbinom}[2]{\left(\!\strut\begin{smallmatrix}#1\\#2\end{smallmatrix}\!\right)}
\newcommand\compactcdots{\makebox[1em][c]{.\hfil.\hfil.}}

\def\ABsim{{{{\sim}\atop{\tiny{A,B}}}}}
\def\ABsim{{\frac{\sim}{A,B}}}
\def\MSP{{\mathcal{MSP}}}
\def\CMSP{{\mathcal{CMSP}}}
\def\NN{{\mathbb N}}
\def\CC{{\mathbb C}}
\def\dcl{{\{\!\!\{}}
\def\dcr{{\}\!\!\}}}
\def\mvdash{{\,\vdash\!\!\vdash}}
\def\o{\overline}

% Dark red emphasis
\newcommand{\defncolor}{\color{blue}}
%\newcommand{\defn}[1]{{\defncolor\emph{#1}}} % emphasis of a definition
\newcommand{\defn}[1]{{\emph{#1}}} % emphasis of a definition


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Young diagrams, grace a Francois Bergeron

\newdimen\squaresize \squaresize=10pt
\newdimen\thickness \thickness=0.4pt


\def\square#1{\hbox{\vrule width \thickness
     \vbox to \squaresize{\hrule height \thickness\vss
        \hbox to \squaresize{\hss#1\hss}
     \vss\hrule height\thickness}
\unskip\vrule width \thickness}
\kern-\thickness}

\def\vsquare#1{\vbox{\square{$#1$}}\kern-\thickness}
\def\blk{\omit\hskip\squaresize}
\def\noir{\vrule height\squaresize width\squaresize}%

\def\young#1{
\vbox{\smallskip\offinterlineskip
\halign{&\vsquare{##}\cr #1}}}

\def\thisbox#1{\kern-.09ex\fbox{#1}}
\def\downbox#1{\lower1.200em\hbox{#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newdimen\Squaresize \Squaresize=20pt
\newdimen\Thickness \Thickness=0.4pt


\def\Square#1{\hbox{\vrule width \Thickness
     \vbox to \Squaresize{\hrule height \Thickness\vss
        \hbox to \Squaresize{\hss#1\hss}
     \vss\hrule height\Thickness}
\unskip\vrule width \Thickness}
\kern-\Thickness}

\def\Vsquare#1{\vbox{\Square{$#1$}}\kern-\Thickness}
\def\Blk{\omit\hskip\Squaresize}
\def\Noir{\vrule height\Squaresize width\Squaresize}%

\def\Young#1{
\vbox{\smallskip\offinterlineskip
\halign{&\Vsquare{##}\cr #1}}}


\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}
\label{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We explore a variant of the Robinson--Schensted--Knuth (RSK) algorithm, where we insert
multisets instead of integer entries.  If we restrict the multisets to all have size one,
the algorithm we are using is the usual RSK algorithm.
Applying this insertion to different arrays of multisets gives
rise to a purely enumerative result that is a combinatorial
manifestation of a double centralizer theorem from representation theory.

The RSK algorithm evolved over the last century from a procedure defined on
permutations (in the work of Robinson \cite{Robinson}) to a procedure defined
on finite sequences of integers (in the work of Schensted \cite{Schensted}) and finally to a procedure defined 
on ``generalized permutations'' by Knuth~\cite{Knuth}. In each of these versions, the algorithm establishes
a correspondence between the initial input and pairs of combinatorial objects
called tableaux subject to certain constraints (see
\cref{section.notation} for definitions).

In this paper, we adapt the RSK algorithm to the insertion of arrays of multisets and obtain an algorithm 
from elements of diagram algebras to pairs of standard multiset tableaux.
Note that algorithms that relate partition diagrams and pairs of paths
in the Bratteli diagram for the partition algebras 
have been known since the late 1990s \cite{HalLew, MarRol}. 
These paths are referred as ``vacillating tableaux''
and they are analogues of a path in the Young's lattice,
which is the Bratteli diagram for the symmetric groups.
Paths in the Young lattice are encoded by standard Young tableaux.

Recently, a new combinatorial interpretation for the dimensions of the
irreducible representations for the partition algebra has appeared in the
literature \cite{BH,BHH,OZ,HJ,Halverson.2019}. In particular, Benkart and Halverson \cite{BH}
presented a bijection between vacillating tableaux and ``set-partition tableaux''
(tableaux whose entries are sets of positive integers).
There are two main advantages to working with set-partition tableaux instead
of vacillating tableaux. Firstly, they are closer in spirit to the ubiquitous
Young tableaux. Secondly, the definition extends naturally to the notion of
multiset tableaux (tableaux whose entries are multisets of positive integers, see \cite{OZ2}).

Our insertion algorithm from partition diagrams to pairs of a standard tableau and a standard
multiset tableau of the same shape has the remarkable property that it is well-behaved
with respect to the subalgebra structure of the partition algebra.
One surprising consequence is that we are able to provide explicit combinatorial
descriptions of the sets of tableaux that give the dimensions of the irreducible representations 
associated to the prominent subalgebras of the partition algebras, such
as the symmetric group,  Brauer, rook, rook-Brauer, Temperley--Lieb,
Motzkin, planar rook, and the planar algebras (see \cref{lemma:tableauxdesc}).
This gives rise to analogues of the famous identity $n! = \sum_{\lambda \vdash n} (f^{\lambda})^2$ for the symmetric
group, where $f^\lambda$ is the number of standard tableaux of shape $\lambda$,
to all of the above mentioned algebras (see \cref{alg-dim}). We prove that the dimensions of the
irreducible representations of the various algebras
are equal to the number of our combinatorially-defined tableaux
by establishing that the branching rules are encoded in the tableaux
(see \cref{section.bratteli} and \cref{irred-dim}).
Our insertion is different from combining the insertion of Halverson and Lewandowski~\cite{HalLew}
from partition diagrams to paths in the Bratteli diagram with the bijection of Halverson and Benkart~\cite{BH}
from paths in the Bratteli diagram to set-partition tableaux (see \cref{section.bratteli}).

For more details on the insertion algorithm for multiset partitions and the proofs of the results presented in this extended abstract, see \cite{COSSZ}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Basic definitions}
\label{section.notation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Throughout this paper, we work with tableaux whose entries are multisets.
Note that any Young tableau---that is, a tableau with integer entries---can be
viewed as a multiset tableau by considering each entry to be a multiset of cardinality $1$.
In this section, we fix notation and define the total order on multisets that
we use in order to extend the property of being (semi)standard to multiset
tableaux.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A \defn{partition} of $n \in \NN$ is a sequence of
positive integers $\lambda = (\lambda_1, \lambda_2, \ldots,
\lambda_r)$ with $\lambda_1 \geqslant \lambda_2 \geqslant \cdots
\geqslant \lambda_r > 0$ whose sum is $n$.
The notation $\lambda \vdash n$ is used to indicate that $\lambda$ is
a partition of $n$.
The \defn{length} of the partition is denoted by $\ell(\lambda) = r$.
The \defn{cells} of the partition are the coordinates of the boxes in the diagram; that is,
$\cells(\lambda) = \{ (i,j) \mid 1 \leqslant i \leqslant \lambda_j, 1 \leqslant j \leqslant \ell(\lambda) \}$.  
The operation of removing the first row of the partition $\lambda$
is denoted by $\o\lambda=(\lambda_2, \lambda_3, \ldots, \lambda_r)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A \defn{set partition} $\pi$ of a set $S$ is a collection $\{\pi_1, \ldots, \pi_k\}$ of non-empty
subsets of $S$ that are mutually disjoint, i.e., $\pi_i\cap\pi_j =\emptyset$ for all $i\neq j$, and $\bigcup_{i} \pi_i = S$. 
The subsets $\pi_i$ are called the \defn{blocks}. We write $\pi\vdash S$ to mean that $\pi$ is a 
set partition of the set $S$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let $(A, \leqslant_A)$ be a totally ordered set, which we refer to as an
\defn{(ordered) alphabet}.
A \defn{multiset} $S = \dcl a_1, a_2, \ldots, a_r \dcr$ over $A$
is an unordered collection of elements of $A$, allowing repeats.
The collection of multisets
forms an associative monoid with operation
\[
    \dcl a_1, a_2, \ldots, a_r \dcr \uplus
    \dcl b_1, b_2, \ldots, b_d \dcr =
    \dcl a_1, a_2, \ldots, a_r, b_1, b_2, \ldots, b_d \dcr~.
\]
To simplify notation, we let $\dcl {a}^{m_a}, b^{m_b}, c^{m_c}, \ldots \dcr$
denote the multiset that contains $m_a$ occurrences of $a$, $m_b$ occurrences
of $b$, and so on;
for example $\dcl 1^2, 4^3, 5\dcr = \dcl 1, 1, 4, 4, 4, 5\dcr$.

A \defn{multiset partition} of a multiset $S$ is a multiset of multisets,
$\pi = \dcl S^{(1)}, S^{(2)}, \ldots, S^{(r)} \dcr$, such that
$S = S^{(1)} \uplus S^{(2)} \uplus \cdots \uplus S^{(r)}$.
We indicate this by the notation $\pi \mvdash S$.

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

Given two disjoint sets $S$ and $S'$ with elements in an ordered set $A$, we say
$S<S'$ in the \defn{last letter order} if $\mbox{max}(S) <_A \mbox{max}(S')$,
where $\mbox{max}(S)$ is the largest element in $S$.
For example, $\{1,3,5\} < \{2,7\}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let $\lambda$ be a partition, $A$ an ordered alphabet, and a fixed total order $<$ on multisets (such as the graded
lexicographic order or the last letter order if the multisets are all disjoint sets).
A \defn{semistandard multiset tableau} of \defn{shape} $\lambda$ is a function $T$ that
associates with each cell $(i, j) \in \cells(\lambda)$ a multiset over $A$
such that:
\begin{itemize}[noitemsep]
    \item
        $T(i,j) \leqslant T(i,j+1)$ whenever $(i, j)$ and $(i, j+1)$ both belong to $\cells(\lambda)$; and
    \item
        $T(i,j) < T(i+1,j)$ whenever $(i, j)$ and $(i+1, j)$ both belong to $\cells(\lambda)$.
\end{itemize}
The \defn{shape} of a multiset tableau $T$ is the partition $\lambda$,
and the \defn{cells} of $T$ are the cells of its shape.
If $T(i, j) = S$, then we say that $S$ \defn{labels} the cell $(i, j)$,
and that $S$ is an \defn{entry} of $T$.
When drawing multiset tableaux, the multisets are abbreviated as words
without the surrounding multiset delimiters $\dcl, \dcr$, and empty
sets are depicted by blank cells.
The \defn{content} of a semistandard multiset tableau $T$ is the (disjoint) union of the
entries of $T$. More precisely, the content of $T$ is the multiset
\begin{equation*}
    \content(T) = \biguplus_{(i, j) \in \cells(T)} T(i, j).
\end{equation*}
A semistandard multiset tableau is said to be
\begin{itemize}[noitemsep]
    \item
        a \defn{standard multiset tableau} if its content is the set ${\defncolor[k]} := \{1,2, \ldots, k\}$ for some
        $k \in \NN$;
    \item
        a \defn{semistandard Young tableau}
        if all its entries are multisets of size $1$;
    \item
        a \defn{standard Young tableau} if it is both standard and
        a semistandard Young tableau.
\end{itemize}
The \defn{set-partition tableaux} of~\cite[Definition 3.14]{BH} are closely related to our standard multiset tableaux.
Finally, for a multiset $S$, let
\begin{itemize}[noitemsep]
    \item
        \defn{$\SSMT(\lambda, S)$} be the set of \emph{semistandard} multiset tableaux of shape $\lambda$ and content $S$;
    \item
        \defn{$\SMT(\lambda,k)$} be the set of \emph{standard} multiset tableaux of shape $\lambda$ and content $[k]$;
    \item
        \defn{$\SSYT(\lambda, S)$} be the set of semistandard Young tableaux of
        shape $\lambda$ and content $S$;
    \item
        \defn{$\SYT(\lambda)$} be the set of standard Young tableaux of shape $\lambda$.
\end{itemize}

\begin{example}
    \label{ex:multiset-tableaux}
    Let $A = \{1, 2, 3, 4, 5\}$ with the usual order on integers.
    Then
    \begin{equation*}
        \squaresize=17pt
        \scalebox{0.7}{
        \young{114\cr2&14\cr&2&5\cr}}
        \qquad
        \qquad
        \scalebox{0.7}{
        \young{3\cr2&3\cr1&1&4\cr}}
        \qquad
        \qquad
        \scalebox{0.7}{
        \young{134\cr5&26\cr&7&8\cr}}
    \end{equation*}
    are three semistandard multiset tableaux of shape $(3, 2, 1)$.
    The leftmost tableau has content $\dcl 1^3, 2^2, 4^2, 5\dcr$.
    The middle tableau has content $\dcl 1^2, 2, 3^2, 4\dcr$
    and is also a semistandard Young tableau.
    The rightmost multiset tableau is standard
    since its content is $\{1, \ldots, 8\}$.
\end{example}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let $A$ and $B$ be two ordered alphabets.
A \defn{generalized permutation} from $A$ to $B$ is a two-line array of the
form
$\left(\begin{smallmatrix} a_1 & a_2 & \cdots & a_r \\ b_1 & b_2 & \cdots& b_r \end{smallmatrix}\right)$
satisfying:
$a_1, \ldots, a_r \in A$; $b_1, \ldots, b_r \in B$;
$a_i \leqslant_A a_{i+1}$ for $1 \leqslant i \leqslant r-1$;
and $b_{i} \leqslant_B b_{i+1}$ whenever $a_i = a_{i+1}$.

\begin{thm}[Knuth] \label{th:oldRSK}
There is a one-to-one correspondence between
generalized permutations from $A$ to $B$
and pairs of tableaux $(P, Q)$ satisfying:
$P$ and $Q$ are of the same shape;
$P$ is semistandard with entries in $B$;
and $Q$ is semistandard with entries in $A$.
\end{thm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Insertion algorithm for diagram algebras}
\label{sec:diagramalgebras}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
For any parameter $n$ and positive integer $k$,  the partition algebra 
$P_k(n)=\mbox{span}_{\mathbb{C}} \{\pi \mid \pi \vdash [k]\cup[\o{k}]\}$
is defined as the complex vector space with basis given by the set partitions on  two disjoint sets  
$[k] \cup [\overline{k}]=\{1, 2, \ldots, k\} \cup \{\o1,\o2, \ldots, \overline{k}\}$.
Although we do not define the product here, as we will not use it explicitly,
we remark that the dependency of the algebra on $n$
arises when we multiply the set partitions \cite{HalRam}.

A \defn{diagram} is a graphical representation of a set partition of the set
$[k] \cup [\overline{k}]$: the vertex set of the graph is $[k] \cup [\overline{k}]$  arranged in two horizontal 
rows, where the top row is labelled by $1,2, \ldots, k$ and the bottom row are labelled 
by $\o1, \o2, \ldots, \overline{k}$; and there is a path connecting two vertices if and only if
they belong to the same block of the set partition. Note that there is more than one graph that
represents a set partition, but this is immaterial to the following.
In our examples, we will connect vertices in the same block with
a cycle.

\begin{example}
    \label{ex:diagram}
The set partition
$\pi = \{\{ 1,2,4,\o2,\o5\},\{3\}, \{5,6,7, \o3,\o4,\o6,\o7\},\{8,\o8\}, \{\o1\}\}$ 
is represented by the following diagram:
\begin{center}$\pi = $
\begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}]
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt]
\node[vertex] (G--5) at (6.0, -1) [shape = circle, draw] {\tiny $\overline 5$};
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$};
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$};
\node[vertex] (G-5) at (6.0, 1) [shape = circle, draw] {\tiny 5};
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny 4};
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$};
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$};
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny 1};
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny 2};
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny 3};
\node[vertex] (G-6) at (7.5, 1) [shape = circle, draw] {\tiny 6};
\node[vertex] (G--6) at (7.5, -1) [shape = circle, draw] {\tiny $\overline 6$};
\node[vertex] (G-7) at (9.0, 1) [shape = circle, draw] {\tiny 7};
\node[vertex] (G--7) at (9.0, -1) [shape = circle, draw] {\tiny $\overline 7$};
\node[vertex] (G-8) at (10.5, 1) [shape = circle, draw] {\tiny 8};
\node[vertex] (G--8) at (10.5, -1) [shape = circle, draw] {\tiny $\overline 8$};
\draw (G-1) .. controls +(0.5, -0.5) and +(-0.5, -0.5) .. (G-2);
\draw (G-2) .. controls +(0.7, -0.7) and +(-0.7, -0.7) .. (G-4);
\draw (G--5) .. controls +(-1, 1) and +(0.7, 0.7) .. (G--2);
\draw (G-1) .. controls +(0.3, -0.5) and +(-.5, .5) .. (G--2);
\draw (G-4) .. controls +(0.3, -0.5) and +(-.5, .5) .. (G--5);
\draw (G-5) .. controls +(0.5, -0.5) and +(-0.5, -0.5) .. (G-6);
\draw (G-6) .. controls +(0.5, -0.5) and +(-0.5, -0.5) .. (G-7);
\draw (G--3) .. controls +(0.4, 0.4) and +(-0.4, 0.4) .. (G--4);
\draw (G--4) .. controls +(0.7, 0.7) and +(-0.7, 0.7) .. (G--6);
\draw (G-5) .. controls +(0.5, -0.5) and +(0.5, 0.5) .. (G--3);
\draw (G--6) .. controls +(0.7, 0.7) and +(-0.7, 0.7) .. (G--7);
\draw (G-7)--(G--7);
\draw (G-8)--(G--8);
\end{tikzpicture}
\end{center}
\vskip 2mm
\end{example}

The partition algebra $P_k(n)$ is semisimple whenever the parameter $n\notin \{0, 1, \ldots, 2k-2\}$ in which
case the irreducible representations are indexed by partitions $\lambda$ with $0\leqslant |\lambda| \leqslant k$ \cite{MS}.
We assume throughout that $n\geqslant 2k$, so that $P_k(n)$ is semisimple and
isomorphic to $\End_{S_n}(V^{\otimes k})$.

In \cite{HalLew,MarRol}, the authors introduce RSK-type algorithms
between partition algebra diagrams and pairs of
paths in the Bratteli diagram of the partition algebras;
in \cite{HalLew} these paths are called vacillating tableaux.
In \cite{BH}, the authors define a bijection between vacillating tableaux and standard multiset tableaux.
In this section we provide a different bijection from partition
algebra diagrams to standard multiset tableaux.  This algorithm not
only encodes the representation theory of the partition algebra, in the sense that the tableaux of 
shape $\lambda$  index an irreducible representation associated with $\lambda$,
but it also encodes the representation theory of subalgebras of the partition
algebra when we restrict the set of diagrams considered.
This allows us to obtain enumerative results for representations of various diagram algebras
using standard multiset tableaux.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The correspondence}
\label{ssec:RSK-for-diagrams}

A block is said to be \defn{isolated} if it is of size $1$.
A block in a set partition $\pi$ is called \defn{propagating} if it contains vertices in both $[k]$ and $[\overline{k}]$
and it is \defn{non-propagating} otherwise.
For example, $\{1, 2, 4, \o2, \o5\}$ is a propagating block and $\{\o3\}$ is isolated.  All isolated blocks are non-propagating.
The number of propagating blocks in $\pi$ is called the \defn{propagating number} and we denote it by $\operatorname{pr}(\pi)$. For example,  the set partition $\pi$ in \cref{ex:diagram} has 
$\operatorname{pr}(\pi)=3$.
Let $\pi = \{\pi_1, \pi_2, \ldots, \pi_r\}$ be a set partition of $[k]\cup [\o{k}]$.
We associate with $\pi$ a pair $(T, S)$ of standard multiset tableaux as follows.
To begin,
\begin{itemize}[noitemsep]
    \item
        let $\pi_{j_1},\pi_{j_2}, \ldots, \pi_{j_p}$ denote the propagating
        blocks of $\pi$ ordered so that $\pi_{j_1}^+ < \cdots < \pi_{j_p}^+$ in
        the last letter order, where $\pi_{j}^+ = \pi_{j} \cap [k]$;

    \item
        let $\sigma_{i_1}, \ldots, \sigma_{i_a} \subseteq [k]$ denote
        the non-propagating blocks contained in $[k]$ and ordered so that
        $\sigma_{i_1} < \cdots < \sigma_{i_a}$ in the last letter order;

    \item
        let $\tau_{i_1}, \ldots, \tau_{i_b} \subseteq [\o{k}]$ denote
        the non-propagating blocks contained in $[\o{k}]$ and ordered so that
        $\tau_{i_1} < \cdots < \tau_{i_b}$ in the last letter order.
\end{itemize}
Let $(P, Q)$ denote the pair of standard multiset tableaux obtained by
applying the RSK algorithm to the generalized permutation
\begin{equation*}
    \left(
        \begin{array}{cccc}
            \pi_{j_1}^+ &
            \pi_{j_2}^+ &
            \cdots &
            \pi_{j_p}^+
            \\[4pt]
            \pi_{j_1}^- &
            \pi_{j_2}^- &
            \cdots &
            \pi_{j_p}^-
        \end{array}
    \right),
\end{equation*}
where $\pi_{j}^+ = \pi_j \cap [k]$ and $\pi_{j}^- = \pi_j \cap [\o{k}]$.
Let $T$ be the tableau obtained from $P$ by adjoining a row containing $n-p-b$
empty cells followed by cells labelled $\tau_{i_1}, \ldots, \tau_{i_b}$.
Let $S$ be the tableau obtained from $Q$ by adjoining a row containing $n-p-a$
empty cells followed by cells labelled $\sigma_{i_1}, \ldots, \sigma_{i_a}$.

\begin{thm} \label{thm:settableaux}
Let $n\geqslant 2k$. The set partitions of $[k]\cup[\o{k}]$ are in bijection
with pairs $(T,S)$ of standard multiset tableaux satisfying: $T$ and $S$ are of
the same shape $\lambda$, where $\lambda$ is a partition of $n$; $T$ has
content $[\o{k}]$; and $S$ has content $[k]$.
\end{thm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Restriction to subalgebras}
There are other bijections between partition algebra diagrams and pairs of
standard multiset tableaux, but an important aspect of the algorithm in this paper is that
it is compatible with the (representation theory) restriction to many prominent subalgebras of $P_k(n)$.
More precisely, we will see that this single procedure captures the
combinatorics of the representation theory of all these subalgebras.
For instance, for an integer $r$ with $0 \leqslant r \leqslant k$ the subspace
spanned by the set partitions with propagating number at most $r$ is
a subalgebra of $P_k(n)$
and the irreducible representations of this subalgebra are indexed by partitions
of size less than or equal to $r$. Then, we have
\begin{equation}
    \# \Big\{ \pi \vdash [k] \cup [\o{k}] ~\Big|~ \operatorname{pr}(\pi) \leqslant r \Big\} =
    \sum_{\substack{\lambda \vdash n\\[1pt]|\o\lambda|\leqslant r}} \# \SMT(\lambda, k)^2~.
\end{equation}

\subsubsection{Definition of the subalgebras}

\begin{figure}[ht!]
\begin{tabular}{cccc}
 \begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}]
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt]
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$};
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$};
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny 4};
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$};
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$};
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny 1};
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny 2};
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny 3};
\draw (G-1)--(G--2);
\draw (G-2)--(G--4);
\draw (G-3)--(G--1);
\draw (G-4)--(G--3);
\end{tikzpicture}{\hskip .2in}&{\hskip .3in}
\begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}]
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt]
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$};
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$};
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny 4};
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$};
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$};
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny 1};
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny 2};
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny 3};
\draw (G-1) .. controls +(0.5, -0.7) and +(-0.5, -0.7) .. (G-3);
\draw (G-2)--(G--1);
\draw (G-4)--(G--3);
\draw (G--2) .. controls +(0.5, 0.7) and +(-0.5, 0.7) .. (G--4);
\end{tikzpicture}{\hskip .3in} &{\hskip .01in}
\begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}]
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt]
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$};
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$};
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny 4};
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$};
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$};
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny 1};
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny 2};
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny 3};
\draw (G-1)--(G--3);
\draw (G-2)--(G--1);
\draw (G-4)--(G--4);
\end{tikzpicture}{\hskip .5in}&{\hskip .1in}
\begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}]
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt]
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$};
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$};
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny 4};
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$};
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$};
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny 1};
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny 2};
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny 3};
\draw (G-1) .. controls +(0.5, -0.7) and +(-0.5, -0.7) .. (G-3);
\draw (G-2)--(G--1);
\draw (G-4)--(G--3);
\end{tikzpicture}\\[17pt]
permutation&perfect matching&partial permutation&matching
\\[15pt]
\begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}] 
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt] 
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$}; 
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$}; 
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny $4$}; 
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$}; 
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$}; 
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny $1$}; 
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny $3$}; 
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny $2$}; 
\draw (G-4) .. controls +(0, -1) and +(0, 1) .. (G--4); 
\draw (G--4) .. controls +(-0.7, 0.7) and +(0.7, 0.7) .. (G--1); 
\draw (G--3) .. controls +(-0.5, 0.5) and +(0.5, 0.5) .. (G--2); 
\draw (G-1) .. controls +(0.6, -0.6) and +(-0.6, -0.6) .. (G-3); 
\end{tikzpicture}{\hskip .2in}&{\hskip .2in}
\begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}]
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt]
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$};
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$};
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny 4};
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$};
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$};
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny 1};
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny 2};
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny 3};
\draw (G-1) .. controls +(0.5, -0.5) and +(-0.5, -0.5) .. (G-2);
\draw (G-3)--(G--1);
\draw (G-4)--(G--4);
\end{tikzpicture}{\hskip .3in} &{\hskip .01in}
\begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}]
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt]
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$};
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$};
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny 4};
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$};
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$};
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny 1};
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny 2};
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny 3};
\draw (G-1) .. controls +(0.5, -0.5) and +(-0.5, -0.5) .. (G-2);
\draw (G-3)--(G--1);
\draw (G-4)--(G--2);
\draw (G--3) .. controls +(0.5, 0.5) and +(-0.5, 0.5) .. (G--4);
\end{tikzpicture}{\hskip .4in}&{\hskip .1in}
\begin{tikzpicture}[scale = 0.5,thick, baseline={(0,-1ex/2)}]
\tikzstyle{vertex} = [shape = circle, minimum size = 7pt, inner sep = 1pt]
\node[vertex] (G--4) at (4.5, -1) [shape = circle, draw] {\tiny $\overline 4$};
\node[vertex] (G--3) at (3.0, -1) [shape = circle, draw] {\tiny $\overline 3$};
\node[vertex] (G-4) at (4.5, 1) [shape = circle, draw] {\tiny 4};
\node[vertex] (G--2) at (1.5, -1) [shape = circle, draw] {\tiny $\overline 2$};
\node[vertex] (G--1) at (0.0, -1) [shape = circle, draw] {\tiny $\overline 1$};
\node[vertex] (G-1) at (0.0, 1) [shape = circle, draw] {\tiny 1};
\node[vertex] (G-2) at (1.5, 1) [shape = circle, draw] {\tiny 2};
\node[vertex] (G-3) at (3.0, 1) [shape = circle, draw] {\tiny 3};
\draw (G-2)--(G--1);
\draw (G-4)--(G--2);
\end{tikzpicture}
\\[17pt]
planar&planar matching&planar perfect&planar partial\\[-2pt]
&&matching&permutation
\end{tabular}
\caption{Examples of types of set partition diagrams.}
\label{fig:setpartitions}
\end{figure}

We introduce some terminology that will make it easier to define
the subalgebras.
See \cref{fig:setpartitions} for examples of the types of diagrams that
we define below.
A set partition $\pi$ is called \defn{planar}
if it can be represented as a graph without edge crossings inside the rectangle formed by its vertices.  A set partition is 
called a \defn{matching} if all its blocks are of size at most 2. We call a set partition a \defn{perfect matching} if all its 
blocks are of size 2. Note that the number of perfect matchings of $2n$ elements is equal to $(2n-1)!! = (2n-1)(2n-3)\cdots(1)$.
A perfect matching, where each block contains an element in $[k]$ and an element in $[\overline{k}]$ 
is a \defn{permutation}.  A set partition is a \defn{partial permutation} if all its blocks have size one or two and 
every block of size two is propagating.

The first two columns in \cref{tab:characterisation_subalgebras} summarizes the definitions of the subalgebras that we work with.
In \cite{HJ}, the authors construct the irreducible representations
of these subalgebras using standard multiset tableaux (which they call \emph{set-partition tableaux}) and compute their
characters. Their results provide a detailed study of the
representation theory of these subalgebras from which we extract the
information in \cref{tab:dimensions}.

\subsubsection{Restricting the correspondence to the subalgebras}
We characterize the standard multiset tableaux produced by the
correspondence of \cref{ssec:RSK-for-diagrams} when restricted to
the diagrams spanning one of the subalgebras $A_k$ in
\cref{tab:characterisation_subalgebras}. We denote this set by \defn{$\SMT_{A_k}(\lambda)$}.

A standard multiset tableau is \defn{matching} if the first row contains sets
of size less than or equal to $2$ and all other rows contain only sets of size
$1$. In \cref{lemma:tableauxdesc}, we show these are the multiset tableaux
that correspond to matching diagrams by our insertion algorithm.
Two sets $S$ and $S'$ are \defn{non-crossing}
if there do not exist elements $a,b \in S$ and $c,d \in S'$ such that
either $a<c<b<d$ or $c<a<d<b$. We say that $c \in [k]$
is \defn{between} a set $S$ if there exist $a,b \in S$ such that $a<c<b$.
We call a standard multiset tableau \defn{planar} if it has two rows,
if the sets in the first row are pairwise non-crossing, and if no element belonging
to one of the sets in the second row is between any set in the tableau
(apart from the set containing the element).
In \cref{lemma:tableauxdesc}, we show these are the multiset tableaux
that correspond to planar diagrams by our insertion algorithm.

\begin{lem}
\label{lemma:tableauxdesc}
Let $k$ be any positive integer, $\lambda$ a partition of an integer $n$ with
$n \geqslant 2k$, and $A_k$ one of the subalgebras of $P_k(n)$ defined in
\cref{tab:characterisation_subalgebras}.
If we apply the insertion procedure of \cref{thm:settableaux} to the
diagrams spanning $A_k$, then the resulting standard multiset
tableaux are characterized by the properties listed in \cref{tab:characterisation_subalgebras}.
\end{lem}

In addition, we obtain the following corollary of \cref{thm:settableaux}
and \cref{lemma:tableauxdesc}.

\begin{cor}
\label{alg-dim}
If $n \geqslant 2k$, then for each subalgebra $A_k$ of the partition algebra
$P_k(n)$, we have
 \[
     \dim(A_k) = \sum_{\lambda \vdash n} \big(\# \SMT_{A_k}(\lambda)\big)^2.
 \]
 The explicit formulas are summarized in \cref{tab:dimensions}.
\end{cor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{From standard multiset tableaux to Bratteli diagrams}
\label{section.bratteli}
Let $A_k$ denote one of the subalgebras from \cref{lemma:tableauxdesc}.
We establish a bijection between the standard multiset tableaux for
$A_k$ and the paths in the Bratteli diagram for $A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots$.

A \defn{Bratteli diagram} associated to a tower of algebras
$A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots$
is an infinite $\NN$-graded graph defined as follows.
The vertices at level $k \in \NN$ are in bijection with the isomorphism classes
of the irreducible representations of $A_k$; if the irreducible representations
are parameterized by some index set, then we label the vertices by the elements
of the index set. Note that it is possible that vertices at different levels
carry the same label (this happens for some of the index sets listed in
\cref{tab:dimensions}), but the associated representations are
different.
The edges in the graph connect vertices of level $k$ with vertices at level $k+1$:
the number of edges from
the vertex associated with an irreducible $A_{k}$-representation $V$
to
the vertex associated with an irreducible $A_{k+1}$-representation $V'$
is the multiplicity of
$V$ in the restriction of $V'$ to $A_{k}$.

In all the examples we consider, there is exactly one irreducible
$A_0$-representation and it is of dimension $1$. It follows from an induction
argument that the dimension of an irreducible representation $V$ is equal to
the number of paths in the Bratteli diagram from the unique level-$0$ vertex to
the vertex associated with $V$.

By \defn{branching rule}, we mean any combinatorial description of the edge
multiplicities in the Bratteli diagram in terms of the index sets of the
irreducible representations.
\begin{remark}
A proof that the planar algebra $P\!P_k(n)$ is isomorphic to the Temperley--Lieb algebra $T\!L_{2k}(n)$
can be found in \cite[Section 1]{HalRam}. Consequently, the branching rule for $P\!P_k(n)$
is obtained by a repeated application of the branching rule for $T\!L_{2k}(n)$.

Paths in the Bratteli diagram are often called updown tableaux or oscillating
tableaux in the literature; see \cite{HalLew} and the references therein.
\end{remark}

\begin{prop}\label{prop:onestep}
Let $k$ be a positive integer and $\lambda$ a partition of $n \geqslant 2k$.
There is a bijection
\[
    \phi \colon \SMT(\lambda, k) \to
    \Big\{ \big(S, \tau\big) ~\Big|~
    S \in \SMT(\mu, k-1), \,
    \tau \rightarrow \mu, \,
    \tau \rightarrow \lambda\Big\}~.
\]
\end{prop}

This correspondence is particularly useful because it respects the properties
characterizing the tableaux in $\SMT_{A_k}(\lambda)$ (see \cref{tab:characterisation_subalgebras}).

\begin{example}\label{ex:brauertab} Consider the following tableau in $\SMT((n-3,2,1), 9)$,
\squaresize=12pt
\[
    T=\raisebox{-.2in}{\tiny{ \young{7\cr 5 & 8 \cr & & & \compactcdots& & 12 & 46 & 39 \cr}}}~,
\]
in particular, it is an element of $\SMT_{B_9(n)}((n-3,2,1))$.
To compute $\phi(T) = (S, \tau)$, we remove the cell labelled $\{3,9\}$
and insert $\{3\}$ in the second row, obtaining
\[
    S=\raisebox{-.25in}{\tiny{ \young{7\cr 5\cr 3 & 8 \cr & & & \compactcdots& & 12 & 46\cr}}}
\]
where $S \in \SMT_{B_8(n)}((n-4,2,1,1))$ and $\tau = (n-4,2,1)$.
\cref{prop:onestep} also states that $T$ can be recovered from
$S$ and the partitions $\tau = (n-4,2,1)$ and $\lambda = (n-3, 2, 1)$.
\end{example}

Now we are ready for the main result of this section, which states that the standard multiset tableaux
in $\SMT_{A_k}(\lambda)$ encode the branching rule for the subalgebra $A_k$.

\begin{thm}\label{th:edges}
Let $A_k$ be a subalgebras of $P_k(n)$ defined in \cref{tab:characterisation_subalgebras}
with $n \geqslant 2k$, and $\lambda,\mu \vdash n$.
\begin{enumerate}[noitemsep]
    \item
        If $T \in \SMT_{A_{k}}(\lambda)$ and $\phi(T)= (S, \tau)$, then
        $S \in \SMT_{A_{k-1}}(\mu)$.

    \item
        For each $S \in \SMT_{A_{k-1}}(\mu)$,
        the number of $T \in \SMT_{A_{k}}(\lambda)$
        such that $\phi(T) = (S,\tau)$ for some partition $\tau$
        is equal to the number of edges from $\o\mu$ to $\o\lambda$ in the Bratteli diagram
        for the tower of algebras $A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots$.
\end{enumerate}
\end{thm}

The map $\phi$ from \cref{prop:onestep} allows us to establish
a bijection between standard multiset tableaux and \emph{vacillating tableaux}.
A \defn{vacillating tableau} is a sequence partitions satisfying the condition
$\lambda^{(r)} \vdash n$ and $\lambda^{(r+\frac{1}{2})} \vdash n-1$
with $\lambda^{(r)} \leftarrow \lambda^{(r+\frac{1}{2})}$
and $\lambda^{(r+\frac{1}{2})} \rightarrow \lambda^{(r+1)}$
for $0 \leqslant r < k$ \cite{HalLew, BH}.
A different bijection appears in \cite{BH}. The bijection we provide here is
compatible with the families of tableaux for each of the subalgebras and the
Bratteli diagrams for those subalgebras.

\begin{prop}
\label{prop:bijection-with-vacillating-tableaux}
For each family of subalgebras $A_k$ in \cref{tab:characterisation_subalgebras}
and for each $\lambda$ a partition of $n\geqslant 2k$,
there is a bijection between $\SMT_{A_k}(\lambda)$ and
the set of vacillating tableaux of the form
$\left((n) = \lambda^{(0)}, \lambda^{(\frac{1}{2})}, \lambda^{(1)}, \lambda^{(1\frac{1}{2})},
    \ldots,\lambda^{(k-\frac{1}{2})}, \lambda^{(k)} = \lambda\right)$,
where $\o{\lambda^{(0)}} \Rightarrow \o{\lambda^{(1)}} \Rightarrow \cdots \Rightarrow \o{\lambda^{(k)}}$
is a path in the Bratteli diagram for the tower of
algebras $A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots$.
\end{prop}

What we have presented in this section completes the connection
between the results in \cite{HJ} and those in \cite{HalLew}.
The insertion presented in \cref{thm:settableaux} is a correspondence
between diagrams and pairs of standard multiset tableaux that motivates the tableaux that arise in the paper \cite{HJ}.  \cref{th:edges} then provides a correspondence
between standard multiset tableaux and paths in the Bratteli diagram.

Since the dimensions of the irreducibles are equal to the number of
paths in the Bratteli diagram, it follows that the number of tableaux
of a given shape is equal to the dimension of the irreducible representation.
This establishes the following result, which can also be proven by enumerating
the tableaux in \cref{lemma:tableauxdesc} by a purely combinatorial
argument and verifying that the values agree with the formulas in \cref{tab:dimensions}.
\begin{cor}
\label{irred-dim}
Let $n \geqslant 2k$ and $\lambda \vdash n$.
For each of the algebras $A_k$ described in \cref{tab:dimensions},
let $V^{\o\lambda}_{A_k}$ be the irreducible $A_k$-representation
indexed by $\o\lambda$. Then
\[
\dim\Big(V^{\o\lambda}_{A_k}\Big) = \# \SMT_{A_k}(\lambda).
\]
\end{cor}

\begin{remark}
Benkart and Halverson~\cite{BH} give a bijection between standard multiset tableaux and
vacillating tableaux that is different from the correspondence that we have just
described.  Their bijection does not behave well under restriction to all of the subalgebras
$A_k$ and the corresponding standard multiset tableaux in $\SMT_{A_k}(\lambda)$.
\end{remark}

\acknowledgements{The authors would like to thank BIRS and AIM for the opportunity to collaborate in Banff and 
San Jos\'e, which greatly facilitated the work on this project. We thank Tom Halverson for sharing an early version
 of~\cite{Halverson.2019} with us.}

\begin{table}[b]
\caption{\small Properties characterizing the standard multiset tableaux in $\SMT_{A_k}(\lambda)$.}
\label{tab:characterisation_subalgebras}
\scalebox{.85}{
\centering
\renewcommand{\arraystretch}{1.2}
\begin{tabular}{l>{\raggedright}p{50mm}p{30mm}p{35mm}}
    \toprule
    & & \multicolumn{2}{c}{properties characterizing $\SMT_{A_k}$} \\ \cmidrule(lr){3-4}
    Subalgebra $A_k$ of $P_k(n)$ & diagrams spanning $A_k$ & sizes of entries \newline in first row & other properties \\
    \midrule
Partition algebra $P_k(n)$ & all diagrams& ---           & ---      \\
Quasi-partition algebra    $Q\!P_k(n)$       & no isolated blocks                 & not $1$ & ---      \\
Group algebra  $\mathbb{C}S_k$ & permutations                & $0$           & matching \\
Brauer algebra  $B_k(n)$        & perfect matchings           & $0$, $2$      & matching \\
Rook algebra    $R_k(n)$        & partial permutations        & $0$, $1$      & matching \\
Rook-Brauer algebra    $R\!B_k(n)$     & matchings                   & $0$, $1$, $2$ & matching \\ \midrule
Planar algebra    $P\!P_k(n)$     & planar diagrams             & ---           & planar   \\
Temperley-Lieb algebra    $T\!L_k(n)$     & planar perfect matchings    & $0$, $2$      & matching \emph{\&} planar \\
Motzking algebra    $M_k(n)$        & planar matchings            & $0$, $1$, $2$ & matching \emph{\&} planar \\
Planar rook algebra    $P\!R_k(n)$     & planar partial permutations & $0$, $1$      & matching \emph{\&} planar \\
    \bottomrule
\end{tabular}}
\end{table}

\begin{table}[b]
\captionof{table}{\small Index sets and dimensions of irreducible representations for $A_k$ in \autoref{tab:characterisation_subalgebras}.}
\label{tab:dimensions}
\scalebox{.82}{
\centering
\renewcommand{\arraystretch}{1.5}
\begin{tabular} {lccc}
\toprule
Subalgebra $A_k$ & Dimension of $A_k$ & Index set for irreducibles  & Dimension of irreducible $V^\lambda_{A_k}$\\ \midrule
$P_k(n)$  & $B_{2k}$ &$\{ \lambda \mid \lambda \vdash m,\ 0 \leqslant m \leqslant k\}$ &$f^{{\lambda}} \sum\limits_{i=|\lambda|}^{k} \smallbinom{k}{i} \smallstirling{i}{\!|\lambda|\!} B_{k-i}$\\
$Q\!P_k(n)$ \footnotesize \cite{DO, BHH} & $1+\sum\limits_{j=1}^{2k} (-1)^{j-1} B_{2k-j}$ &$\{ \lambda \mid \lambda \vdash m, 0 \leqslant m \leqslant k\}$ & $f^{{\lambda}} \sum\limits_{\ell=0}^{k}  \sum\limits_{i=|\lambda|}^{\ell} (-1)^{k-\ell} \smallbinom{k}{\ell}  \smallbinom{\ell}{i} \smallstirling{i}{\!|\lambda|\!} B_{\ell-i}$\\
$\mathbb{C} S_k$    & $k!$ &$\{ \lambda \mid \lambda \vdash k\}$ & $f^{\lambda}$ \\
$B_k(n)$ \footnotesize \cite{Brauer, Wenzl} & $(2k-1)!! $ & $\{ \lambda \mid \lambda \vdash k-2r, 0 \leqslant 2r \leqslant k\}$ & $f^{{\lambda}} \smallbinom{k}{|{\lambda}|} (k-|{\lambda}|-1)!!$\\
$R_k(n)$ \footnotesize \cite{Solomon} & $\sum\limits_{i=0}^k \smallbinom{k}{i}^2 i!$&$\{ \lambda \mid \lambda \vdash m, 0 \leqslant m \leqslant k\}$ & $f^{{\lambda}} \smallbinom{k}{|{\lambda}|}$\\
$T\!L_k(n)$ \footnotesize \cite{Jones1, West} & $\frac{1}{k+1} \smallbinom{2k}{k}$&$\{ (k-2r) \mid 0 \leqslant 2r \leqslant k\}$ & $\smallbinom{k}{ (k-m)/2} -\smallbinom{k}{ (k-m)/2-1}$\\
$M_k(n)$ \footnotesize \cite{BH-motzkin} & $\sum\limits_{i=0}^k\frac{1}{i+1} \smallbinom{2i}{i} \smallbinom{2k}{2i}$ &$\{(m) \mid 0 \leqslant m \leqslant k\}$ & $\sum\limits_{i=0}^{\lfloor\frac{k-m}{2}\rfloor} \smallbinom{{k}}{{m+2i}} \Big(\!\smallbinom{{m+2i}}{ {i}} -\smallbinom{{m+2i}}{{i-1}}\!\Big)$\\
$P\!R_k(n)$ \footnotesize \cite{FHH} & $\smallbinom{2k}{k}$ &$\{(m) \mid 0 \leqslant m \leqslant k\}$ & $\smallbinom{k}{ m}$\\
$P\!P_k(n)$ \footnotesize \cite{Jones} & $\frac{1}{2k+1}\smallbinom{4k}{2k}$&$\{(m) \mid 0 \leqslant m \leqslant k\}$ & $\smallbinom{2k }{ k-m} -\smallbinom{2k}{ k-m-1}$\\
\bottomrule
\end{tabular}}
\end{table}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography


\end{document}
