# Operational Semantics with
Hierarchical Abstract Syntax Graphs111Extended abstract of invited talk

Dan R. Ghica Huawei Research, EdinburghUniversity of Birmingham, UK

###### Abstract

This is a motivating tutorial introduction to a semantic analysis of
programming languages using a graphical language as the representation of
terms, and graph rewriting as a representation of reduction rules. We show how
the graphical language automatically incorporates desirable features, such as
$\alpha$-equivalence and how it can describe pure computation, imperative
store, and control features in a uniform framework. The graph semantics
combines some of the best features of structural operational semantics and
abstract machines, while offering powerful new methods for reasoning about
contextual equivalence.

All technical details are available in an extended technical report by Muroya
and the author [DBLP:journals/corr/abs-1907-01257] and in Muroya’s doctoral
dissertation [koko].

##  1 Hierarchical abstract syntax graphs

Before proceeding with the business of analysing and transforming the source
code of a program, a compiler first parses the input text into a sequence of
atoms, the lexemes, and then assembles them into a tree, the Abstract Syntax
Tree (AST), which corresponds to its grammatical structure. The reason for
preferring the AST to raw text or a sequence of lexemes is quite obvious. The
structure of the AST incorporates most of the information needed for the
following stage of compilation, in particular identifying operations as nodes
in the tree and operands as their branches. This makes the AST algorithmically
well suited for its purpose. Conversely, the AST excludes irrelevant lexemes,
such as separators (white-space, commas, semicolons) and aggregators
(brackets, braces), by making them implicit in the tree-like structure. It is
always possible to recover the textual input, or rather an equivalent version
of it, from the AST via a process known as pretty-printing.

A fair question to ask is whether the AST can be improved upon as a
representation of program text, which captures grammatical structure while
discarding needless detail. In pretty-printing we know how irrelevant lexemes
can be manipulated to achieve a certain aesthetic effect. Redundant brackets
can be elided to reduce clutter, white-space can be added or removed to
improved alignment, and so on. Such details are accepted as irrelevant.

There is another, deeper level of detail in the text, which is irrelevant but
not always appreciated as such: variable names. Whereas we know, formally,
that bound variables can be systematically renamed ($\alpha$-equivalence) the
conventional AST will still remember their names, even though variable names
induce bureaucratic complications having to do with scope and shadowing.
Finally, there is yet another even deeper level of irrelevant detail in the
program text, the order in which variables are defined, absent define-use
dependencies between the definitions.

Consider the program text in Fig. LABEL:fig:cwb, in which def is a binder
associating a variable with a definition as text, akin to a macro, but
respecting variable scoping rules. Variable x in line 3 could be renamed, on
lines 3-5, to something else to avoid shadowing the variable with the same
name on line 1. Lines 1-2 and lines 3-4 can be swapped without changing the
result. But these facts are not immediate from examining its AST in Fig
LABEL:fig:ast (left).

⬇

1 def x = 0

2 def y = x + 1

3 def x = 2

4 def z = x + 3

5 y + z\end{lstlisting}

6 \caption{Bindings}

7 \label{fig:cwb}

8\end{wrapfigure}

9\begin{figure}

10\centering

11{\small

12\input{pics/ast.pdf_tex}

13\input{pics/asg.pdf_tex}

14}

15\caption{AST vs ASG for variable definition}

16\label{fig:ast}

17\end{figure}

18Unlike ASTs, an abstract syntax graphs (ASG) do not treat binders and
variables as nodes.

19Variables are instead represented as links, and binders assign target nodes
corresponding to their definitions to the variable links.

20The ASG of the code in Fig.~\ref{fig:cwb} is represented next to its AST in
Fig.~\ref{fig:ast}.

21To better understand the relation between the AST and the ASG, corresponding
nodes are coloured and the links are labelled with variable names.

22The colour and the labels are not part of the definition of the graph
structure, but are just used to aid understanding.

23The nodes corresponding to variable uses and definitions, left blank, are
not part of the ASG.

24It is thus immediately obvious that the ASG is, by construction, quotiented
both by $\alpha$-equivalence and by the order of non-interfering variable
bindings.

25This more general structural equivalence of lambda calculus terms has been
dubbed ‘‘graph equivalence" by Accattoli et.
al.~\cite{DBLP:conf/popl/AccattoliBKL14}.

26

27\begin{wrapfigure}{l}{0.35\textwidth}

28 \begin{lstlisting}[language=Python]

29 def x = 2

30 def z = x + 3

31 z + z\end{lstlisting}

32 \caption{Contraction}

33 \label{fig:con}

34\end{wrapfigure}

35ASGs are also helpful when variables are reused, as in the
Fig.~\ref{fig:con} example.

36The AST and the ASG are showed side-by-side in Fig.~\ref{fig:ast}, noting
that the links corresponding to the variable \texttt{z}, used twice, now both
point to its definition.

37This is why ASG are no longer trees, but directed acyclic graphs (DAGs).

38Formally, the ASGs are \textit{hypergraphs} with the links a graphical
representation of vertices and the nodes a graphical representation of
hyperedges.

39\begin{figure}

40 \centering

41 {\small

42 \input{pics/astcon.pdf_tex}

43 \input{pics/asgcon.pdf_tex}

44 }

45 \caption{AST vs ASG for contraction}

46 \label{fig:asg}

47\end{figure}

48

49To represent \textit{local} variable binding, as encountered in functions as
opposed to simple variable \textit{definition} discussed above, we note that
local variable binding is always associated with \textit{thunks}, i.e. code
with delayed execution.

50This is related to the fact that conventional programming languages use
normal-order reduction.

51In this evaluation strategy functions are considered values, i.e. there is
no evaluation ‘under the lambda’.

52In other words, functions are thunks and locally-bound variables will always
induce a thunk.

53Because thunks can be considered, operationally, as a single entity, it is
convenient to represent them in their ASG form as a single node, labeled by
the definition of the thunk, which is also an ASG.

54In other words, to model local variable binding in functions it is
convenient to use graphs labelled by graphs, which are, formally,
\textit{hierarchical} hypergraphs.

55

56To model variable behaviour in thunks correctly, our ASGs need to be
\textit{interfaced}, i.e. there needs to be a defined order on incoming links.

57If a thunk has $m$ bound variables and $n$ free variables then the first $m$
incoming links of the ASG used as its label represent the bound variables, in
the order in which they are bound.

58The last $n$ incoming links represent the free variables, in some specified
order.

59The node corresponding to the thunk will also have $n$ incoming links,
representing the definitions of its $n$ free variables, in an order consistent
with the order used by the label ASG.

60To make the correspondence more perspicuous we connect the links
corresponding to the free variables from the labelling ASG to those of the
node, as it causes no ambiguity.

61Fig.~\ref{fig:hasg} shows several examples for hierarchical ASGs and the
corresponding terms, with function application labelled as $@$.

62Note that thunks associated with lambda expressions are still explicitly
linked to a lambda-labelled node.

63This is because in a programming language thunks can be used for expressions
other than function definitions, as we shall see.

64\begin{figure}

65 \centering\small

66 \input{pics/hasg.pdf_tex}

67 \caption{Hierarchical ASGs}

68 \label{fig:hasg}

69\end{figure}

70

71\section{Operational semantics}

72

73

74The most widely used method for specifying programming languages is via
\textit{operational semantics} (OS).

75There are several versions of OS.

76We will focus on so-called \textit{structural} operational semantics (SOS)
in the style of Plotkin~\cite{DBLP:journals/jlp/Plotkin04a}, in which a
\textit{transition relation} is defined on \textit{configurations} consisting
of a term $t$ and some additional information (e.g. a program \textit{store},
$s, t$), so that the definition of the relation is inductive on the structure
of the term.

77

78\begin{wrapfigure}{r}{.35\textwidth}

79 \begin{gather*}

80 s,1+2\to s,3 \\\

81 \frac{s,e_1\to s’,e_1’}{s,e_1+e_2\to s’, e_1’+e_2}.

82 \end{gather*}

83 \caption{SOS (example rules)}

84 \label{fig:ltr}

85\end{wrapfigure}

86Typically the transition relation is written as $s,t\to s’, t’$.

87There are two kinds of rules, \textit{basic reductions} which perform
operations (e.g. first rule in Fig.~\ref{fig:ltr}) and \textit{simplification
steps} which seek redexes structurally in the program text according to the
evaluation strategy (second rule in Fig.~\ref{fig:ltr}).

88The latter are usually written in natural-deduction style.

89For example, the rule specifying that $+$ is evaluated left-to-right is the
second rule in Fig.~\ref{fig:ltr}.

90Note how the first operand $e_1$ is evaluated to $e_1’$ and, in the proces,
the store $s$ may change to $s’$.

91

92SOS can be naturally formulated on ASGs rather than on terms.

93Basic reductions correspond to graph rewrites and simplification steps to a
graph traversal algorithm which seeks the redexes.

94The basic reduction in Fig.~\ref{fig:ltr} is shown as a graph rewrite in
Fig.~\ref{fig:ltrg}, along with the rule for $\beta$-reduction.

95The former is quite obvious, but the latter is more interesting.

96It consists of the deletion of the abstraction-application pair, the
‘unboxing’ of the thunk by extracting the label of the thunk node and using it
in the top-level graph, the re-wiring of the bound variable, now open, to the
argument, and using the root node of $F$ as the overall root node.

97For the $\beta$ rule the graphs involved in the rewrite must also be
interfaced, with the interface nodes highlighted in grey.

98Also note that the rule is actually the \textit{small} $\beta$ rule used in
calculi of explicit substitution which reduces $(\lambda x.F)M$ to
$\mathtt{def}\ x=M\ \mathtt{in}\ F$~\cite{DBLP:journals/jfp/AbadiCCL91}.

99\begin{figure}

100 \centering

101 \small

102 \input{pics/ltrg.pdf_tex}

103 \caption{ASG rewrite as basic reductions}

104 \label{fig:ltrg}

105\end{figure}

106

107One aspect of the ASG-based evaluation which needs to be clearly explicated
is sharing.

108The DAG structure of the ASG can be refined by introducing special sharing
nodes, which, unlike operation nodes, would be allowed to have multiple
incoming links.

109Sharing nodes have a special behaviour during evaluation, managing the
process of systematic copying of sub-graphs.

110

111To evaluate an ASG in a way that is consistent with left-to-right call-by-
value the traversal is depth-first and left-to-right, without reaching inside
thunks, starting from the unique root.

112The current link in the traversal is called the \textit{focus}, and it can
move \textit{up} (i.e. away from the root) or \textit{down} (i.e. towards the
root).

113When the focus is moving up and it encounters a copy node it will copy the
node shared by the copy node, inserting further copy nodes on its outgoing
links.

114As the focus is moving down, whenever it passes a node which has an
associated rewrite rule it will exercise it, then change direction and move up
again (\textit{refocussing}).

115\begin{figure}[t]

116 \centering\small\input{pics/bigdiag.pdf_tex}

117 \caption{Evaluation of $(\lambda f x.f(fx)))(\lambda x.x+1, 2)$.}

118 \label{fig:exrew}

119\end{figure}

120

121In Fig.~\ref{fig:exrew} we show the key steps in the evaluation of the
expression $(\lambda f x.f(fx)))(\lambda x.x+1, 2)$.

122We use the labels of $\lambda2$ and $@2$ for definition and use of a
function with two arguments.

123Step (1) is reached after the focus moves along the path
$\mathit{abcbdefa}$, at which point the rewrite is performed, unboxing the
thunk and attaching the arguments to the nodes made available.

124Step (2) is simply rearranging the ASG in a more readable format.

125Step (3) is the copying of the node corresponding to the function $\lambda
x.x+1$ after the focus traverses path $ab$.

126Step (4) is the $\beta$ rewrite applied after the focus traverses path
$abcdb$.

127Step (5) is an arithmetic reduction, followed by another $\beta$ rewrite
and a final arithmetic reduction.

128

129The examples in this section (abstraction, application, arithmetic) deal
with what is usually deemed \textit{pure} functional programming, case in
which the configuration used by the SOS is the term itself.

130Expanding the SOS of a language to incorporate effects usually requires
revising the format of the configuration of the SOS, which in turn requires
reformulating the rules for the preexisting operations.

131This is a major fragility of the SOS approach, since the revision of the
format invalidates any technical results and require laborious re-
proving~\cite{DBLP:journals/entcs/GhicaT12}.

132ASGs can be enhanced with a single new node which will allow the
formulation of most known effects, namely an \textit{atom} node, in the sense
of~\cite{pitts_2013}.

133The ASG OS for a pure language then only differs from the ASG OS of an
impure language in that the atom nodes are not involved.

134The atom node, just like a sharing node, allows multiple incoming links.

135However, during evaluation, the atom node does not trigger a copying of the
node at the end of its outgoing link, but is instead treated as an endpoint by
the ASG traversal strategy.

136Indeed, just as computations are not performed inside of thunks they are
also not performed inside of the store.

137This insight, that the essence of effectful computation is the presence of
atoms in the OS is originally due to Pitts, but it turns out to be most
effective in ASG-based OS \cite{DBLP:conf/lics/Pitts96}.

138

139Fig~\ref{fig:asgr} shows the basic rule for assignment, with the atom
indicated as an unlabeled white node.

140The atom is made to point to the second operand of the assignment operator,
while the assignment operator itself reduces to the dummy value inhabiting the
unit type.

141In the process, whatever the atom was attached to before may become
inaccessible from the root of the ASG, therefore \textit{garbage.}

142Also note that the effect of the assignment is manifest only because other
parts of the ASG may point to the atom, a link which is persistent due to the
value-like behaviour of the atom.

143

144\begin{wrapfigure}{r}{.5\textwidth}

145 \centering\small

146 \input{pics/asgr.pdf_tex}

147 \caption{Assignment in ASG OS}

148 \label{fig:asgr}

149\end{wrapfigure}

150

151The SOS of a programming language can be further refined
(\textit{distilled}) into an abstract machine, which gives a more explicit
representation of the simplification rules via manipulation of
context~\cite{DBLP:journals/iandc/WrightF94}.

152From this point of view, the ASG representation of the SOS is already an
abstract machine, in the sense that it can give a cost-accurate model of
execution of the language.

153

154Another appealing feature of abstract machines is that they can model
control-transfer operations more conveniently that SOS.

155It is not impossible to use SOS for this, but the format of the transition
system needs to be significantly revised, making the transitions themselves
labelled~\cite{DBLP:journals/corr/SculthorpeTM16}.

156\begin{figure}

157 \centering\small

158 \input{pics/control.pdf_tex}

159 \caption{Control in ASG OS}

160 \label{fig:control}

161\end{figure}

162

163Since the ASG OS is formulated via arbitrary rewrites, control can be dealt
with in a straightforward way.

164Fig~\ref{fig:control} shows a labelled version of C-style
\textit{break/continue} statements.

165The operations involved are loop body definition ($l$), sequential
composition (;), break ($b$), and continue ($c$).

166The atom used as the first operand of $l$ becomes bound to the label which
is the bound argument of $M$, used to anchor a point in the ASG so that the
control operations of break or continue can determine where to jump to.

167If $M$ terminates normally then the whole cycle repeats.

168Unlike conventional C break and continue these variants are labelled, and
the labels are first-class citizens, i.e. they can be passed as arguments to
or returned from functions.

169

170An interactive evaluator for a variety of programming language features can
be found online.\footnote{\url{https://tnttodda.github.io/Spartan-
Visualiser/}}.

171

172\section{Reasoning}

173

174SOS was originally considered too ‘low level’ to reason about equivalence
in programming languages, at least in contrast with denotational semantics.

175However, SOS was considered more ‘high level’ than alternative operational
specifications of programming languages such as abstract machines.

176In time, a large variety of powerful techniques for reasoning with SOS-like
specifications proved that this is indeed a useful formalism for reasoning
about equivalence~\cite{DBLP:conf/ac/Pitts00} whereas abstract machines
remained useful due to their ability to model the cost of evaluation and as a
gateway to compiler development~\cite{leroy:inria-00070049}.

177The ASG OS seems to combine felicitously some of the best features of SOS
and abstract machines including, as we shall see, the ability to reason about
observational equivalence.

178

179In fact, the graph formulation of the OS makes it possible not just to
reason about equivalence, but to formulate a powerful characterisation theorem
which establishes equivalence by using some simpler combinatorial criteria.

180We must first ‘tame’ the OS by restricting ourselves to sets of rules which
are \textit{deterministic} and \textit{refocussing}.

181The first concept is the standard one.

182The second, initially formulated by Danvy et. al., means that following a
basic reduction the focus could be kept either at the point where the rewrite
occurs, or moved to the root of the graph, with equal
effect~\cite{DBLP:journals/tcs/DanvyMMZ12}.

183Indeed, all the rules we have presented in this tutorial are refocussing.

184

185Equivalences are also formulated graphically, as families of relations on
\textit{templates}, i.e. sets of graphs with the same interface.

186For a fixed abstract machine a template is said to be \textit{input-safe}
if evaluation from any input link preserves the relation.

187Note that, unlike a SOS, we can talk about the evaluation of an ASG which
is not a program, in fact not even a term, since evaluation is just a byword
for traversal and reduction.

188A template is said to be \textit{output-closed} if in the course of
evaluation no output link will ever be reached.

189Finally, a template is said to be \textit{robust} if it is preserved by all
rewrite rules of the language.

190The main theorem can be simply stated as:

191\\\\[2ex]

192\textbf{Theorem.}
(Characterisation~\cite[Sec.~6]{DBLP:journals/corr/abs-1907-01257}).
\textit{Robust templates induce observational equivalence. }

193\\\\[2ex]

194The conditions used to establish equivalence via the Characterisation
Theorem are all elementary and proved by case analysis.

195Moreover, the theorem allows for \textit{robust} proofs of equivalence in
the sense that they can withstand language extensions.

196For example we can prove the $\beta$ law for a pure language can be
extended to a language with imperative store just by showing that the
templates used in formulating the law are robust relative to the new rules for
variable creation, dereferencing, and assignment (Fig.~\ref{fig:asg}).

197Which happens to be the case.

198By contrast, conventional proofs of equivalence are fragile, and are
invalidated by even mild language extensions.

199

200\section{Related work}

201

202This is an elementary tutorial introduction and extended motivation for the
\textit{hypernet semantics} of programming
languages~\cite{DBLP:journals/corr/abs-1907-01257}, which is a streamlined and
generalised version of the \textit{Dynamic Geometry of Interaction (GoI)
Machine}~\cite{DBLP:journals/lmcs/MuroyaG19}.

203They are the outcome of an effort initially motivated by the understanding
of call-by-value and effectful computation from a GoI
perspective~\cite{DBLP:conf/csl/HoshinoMH14,DBLP:conf/popl/MuroyaHH16}.

204

205

206Graph-based intermediate representations (IR) are established in compiler
construction~\cite{DBLP:conf/irep/ClickP95} and in the formulation of abstract
machines for functional languages~\cite{DBLP:conf/fpca/JonesS89}.

207However, the origin of the approach describe here lies elsewhere, in
\textit{proof nets}, a graphical representation of proofs in Linear
Logic~\cite{DBLP:journals/tcs/Girard87} and especially in their generalisation
as \textit{interaction nets}~\cite{DBLP:conf/popl/Lafont90}.

208Interaction nets already exhibit the hierarchical structure we employ here,
which is used to model binding and higher-order structures.

209Hierarchical graphs are also used elsewhere in semantics, for example as
diagram languages of processes known as
\textit{bigraphs}~\cite{DBLP:journals/entcs/Milner08}.

210

211The connection between linear logic and its varieties and certain monoidal
categories kindled significant progress in diagrammatic
languages~\cite{Selinger2011}.

212For instance, traced monoidal categories, used as models of lambda calculus
with cyclic sharing~\cite{DBLP:conf/tlca/Hasegawa97}, led to the development
of a hierarchical graph syntax for
closures~\cite{DBLP:journals/entcs/SchweimeierJ99} remarkably similar to the
one described here.

213In terms of the treatment of graphs as combinatorial objects, much of the
literature considered them rather informally and a formalisation of proof nets
as hypergraphs was given much later~\cite{DBLP:journals/tcs/GuerriniMM01}.

214

215More recently, work by Accattoli has examined the interesting interplay
between term-based and graph-based formulations of the call-by-value lambda
calculus~\cite{DBLP:journals/tcs/Accattoli15}, even though his motivations are
somewhat different than ours, as illustrated by this quotation:

216\begin{quotation}\em

217 It is far from easy to realize an isomorphism

218 between terms and nets, as it is necessary

219 to take care of many delicate details about

220 weakenings, contractions, representation of

221 variables, administrative reduction steps,

222 and so on. [$\ldots$] More generally, such a strong

223 relationship turns the calculus into an

224 algebraic language for proof nets, providing

225 a handy tool to reason by structural

226 induction over proof nets.

227\end{quotation}

228In fact, a properly formalised graphical syntax can be just as powerful and
just as rigorous as an algebraic language.

229Moreover, the graphical language can be both simpler and better specified
than the term language, for example in the case of the calculus of explicit
substitutions, which lacks a proper formulation of
$\alpha$-equivalence~\cite{DBLP:conf/ictac/Accattoli18}.

230

231To conclude, we see the ASG operational semantics as a first step in an
exciting and potentially fruitful direction.

232Graphical languages are starting to emerge as a new and genuine formalism
which can give alternative, and sometimes improved, representations to
theories in fields as different as quantum
computation~\cite{coecke_kissinger_2017}, linear and affine
algebra~\cite{DBLP:conf/lics/BonchiPSZ19}, digital
circuits~\cite{DBLP:conf/csl/GhicaJL17}, signal
flow~\cite{DBLP:conf/popl/BonchiSZ15} and more.

233The motivations for this emergence are mixed, from the raw intuitive appeal
of visual representations to improved algorithmic properties.

234Examining how this methodology can be extended to programming languages is
an intriguing next step which brings together a number of existing ideas and
concepts and can unify existing gaps between semantics of programming
languages and compiler-related techniques.

235

236\bibliographystyle{eptcs}

237\bibliography{generic}

238\end{document}"


# An embedding of the skein action on set partitions into the skein action on
matchings

Jesse Kim  Department of Mathematics
University of California, San Diego
La Jolla, CA, 92093-0112, USA<EMAIL_ADDRESS>
###### Abstract.

Rhoades defined a skein action of the symmetric group on noncrossing set
partitions which generalized an action of the symmetric group on matchings.
The ${\mathfrak{S}}_{n}$-action on matchings is made possible via the Ptolemy
relation, while the action on set partitions is defined in terms of a set of
skein relations that generalize the Ptolemy relation. The skein action on
noncrossing set partitions has seen applications to coinvariant theory and
coordinate rings of partial flag varieties. In this paper, we will show how
Rhoades’ ${\mathfrak{S}}_{n}$-module can be embedded into the
${\mathfrak{S}}_{n}$-module generated by matchings, thereby explaining how
Rhoades’ generalized skein relations all arise from the Ptolemy relation.

##  1\. Introduction

This paper concerns an action of ${\mathfrak{S}}_{n}$ on the vector space
spanned by the set of noncrossing set partitions of $[n]:=\\{1,2,\dots,n\\}$
first defined by Rhoades [7]. This action is defined in terms of three skein
relations, the simplest of which is the Ptolemy relation shown below.

$\mapsto$$+$

The original motivation for defining this action was to give an algebraic
proof of certain cyclic sieving results on noncrossing set partitions, first
proven by Reiner, Stanton, and White [6] and Pechenik [4] via direct
enumeration. Rhoades’ action has since been found within coinvariant rings and
coordinate rings of certain partial flag varieties[1, 3], strengthening the
claim that it is an action worth studying in its own right. Rhoades’ action
generalizes a similar action on the vector space with basis given by
noncrossing matchings. This paper will show how Rhoades’ action can be found
within the action on noncrossing matchings and thereby explain how the three
skein relations all arise from the Ptolemy relation.

More precisely, let $M(n)$ denote the set of all matchings of $[n]$, i.e.
collections of disjoint size-two subsets of $[n]$. The symmetric group
${\mathfrak{S}}_{n}$ acts naturally on $M(n)$ as follows. If
$\sigma\in{\mathfrak{S}}_{n}$ and
$m=\\{\\{a_{1},b_{1}\\},\dots,\\{a_{k},b_{k}\\}\\}$ is a matching, then

(1.1) $\sigma\star
m=\\{\\{\sigma(a_{1}),\sigma(b_{1})\\},\dots,\\{\sigma(a_{k}),\sigma(b_{k})\\}\\}.$

We can extend this action to an action on $\mathbb{C}[M(n)]$, the
$\mathbb{C}$-vector space with basis given by matchings of $[n]$. For our
purposes, it will be more useful to consider a sign-twisted version of this
action, where

(1.2) $\sigma\circ
m=\mathrm{sign}(\sigma)\\{\\{\sigma(a_{1}),\sigma(b_{1})\\},\dots,\\{\sigma(a_{k}),\sigma(b_{k})\\}\\}.$

A matching is noncrossing if it does not contain two subsets $\\{a,c\\}$ and
$\\{b,d\\}$ with $a<b<c<d$. The action on matchings does not descend to an
action on $NCM(n)$, the set of all noncrosssing matchings of $[n]$, since
permuting elements in a noncrossing matching could introduce crossings.
However, we can linearize and define an action on $\mathbb{C}[NCM(n)]$, the
$\mathbb{C}$-vector space with basis given by noncrossing matchings of $[n]$.
For any noncrossing matching $m$ and adjacent transposition $s_{i}=(i,i+1)$,
define

(1.3) $s_{i}\cdot m=\begin{cases}s_{i}\circ m&s_{i}\circ m\textrm{ is
noncrossing}\\\ m+m^{\prime}&\textrm{otherwise}\end{cases}.$

Here $\circ$ denotes the action on all matchings and $m^{\prime}$ is the
matching where the subsets of $m$ containing $i$ and $i+1$, call them
$\\{i,a\\}$ and $\\{i+1,b\\}$ have been replaced with $\\{i,i+1\\}$ and
$\\{a,b\\}$ and all other subsets remain the same. In other words, $s_{i}\circ
m$, $m$, and $m^{\prime}$ form a trio of matchings that differ only in a
Ptolemy relation. There exists an ${\mathfrak{S}}_{n}$-equivariant linear
projection $p_{M}:\mathbb{C}[M(n)]\rightarrow\mathbb{C}[NCM(n)]$ given for any
matching $m$ by

(1.4) $m\mapsto w^{-1}\cdot(w\circ m),$

where $w$ is any permutation for which $w\circ m$ is noncrossing. The kernel
of this projection is spanned by sums of matchings which differ only by a
Ptolemy relation, i.e.

(1.5)
$\\{\\{a_{1},a_{2}\\},\\{a_{3},a_{4}\\},\\{a_{5},a_{6}\\},\dots,\\{a_{2k-1},a_{2k}\\}\\}\\\
+\\{\\{a_{1},a_{3}\\},\\{a_{2},a_{4}\\},\\{a_{5},a_{6}\\},\dots,\\{a_{2k-1},a_{2k}\\}\\}\\\
+\\{\\{a_{1},a_{4}\\},\\{a_{2},a_{3}\\},\\{a_{5},a_{6}\\},\dots,\\{a_{2k-1},a_{2k}\\}\\}$

for any distinct $a_{1},\dots,a_{2k}\in[n]$. This projection can be thought of
as a way to“resolve” crossings in a matching and obtain a sum of noncrossing
matchings.

Analogously, let $\Pi(n)$ denote the set of all set partitions of $[n]$, and
let $\mathbb{C}[\Pi(n)]$ be the $\mathbb{C}$-vector space with basis given by
$\Pi(n)$. We can define an action of ${\mathfrak{S}}_{n}$ on
$\mathbb{C}[\Pi(n)]$ analogous to the action on $\mathbb{C}[M(n)]$. A set
partition is noncrossing if there do not exist distinct blocks $A$ and $B$ and
elements $a,c\in A$, $b,d\in B$ with $a<b<c<d$. Let $NCP(n)$ denote the set of
all noncrossing set partitions, and let $\mathbb{C}[NCP(n)]$ be the
corresponding vector space. Rhoades [7] defined an action of
${\mathfrak{S}}_{n}$ on $\mathbb{C}[NCP(n)]$ as follows. For any noncrossing
set partition $\pi$ and adjacent transposition $s_{i}$,

$s_{i}\cdot\pi=\begin{cases}-\pi&i\textrm{ and }i+1\textrm{ are in the same
block of }\pi\\\ -\pi^{\prime}&\textrm{at least one of }i\textrm{ and
}i+1\textrm{ is in a singleton block of }\pi\\\ \sigma(\pi^{\prime})&i\textrm{
and }i+1\textrm{ are in different size 2 or larger blocks of }\pi\end{cases}$

where $\pi^{\prime}$ is the set partition obtained by swapping which blocks
$i$ and $i+1$ are in, and $\sigma$ is defined for any almost-noncrossing (i.e.
the crossing can be removed by a single adjacent transposition) partition
$\pi$ by $\sigma(\pi)=\pi+\pi_{2}-\pi_{3}-\pi_{4}$ where, if the crossing
blocks in $\sigma$ are $\\{i,a_{1},\dots,a_{k}\\}$ and
$\\{i+1,b_{1},\dots,b_{l}\\}$, then $\pi_{2},\pi_{3}$ and $\pi_{4}$ are
obtained from $\pi$ by replacing these blocks with

  * •

$\\{i,i+1\\}$ and $\\{a_{1},\dots,a_{k},b_{1},\dots,b_{l}\\}$ for $\pi_{2}$

  * •

$\\{i,i+1,a_{1},\dots,a_{k}\\}$ and $\\{b_{1},\dots,b_{l}\\}$ for $\pi_{3}$

  * •

$\\{i,i+1,b_{1},\dots,b_{l}\\}$ and $\\{a_{1},\dots,b_{k}\\}$ for $\pi_{3}$

when $k,l\geq 2$. If $k=1$ then $\pi_{4}=0$ instead and if $l=1$ then
$\pi_{3}=0$ instead. The sum of partitions given by $\sigma(\pi)$ is best
described with a picture, see Figure 1. The three possibilities (depending on
whether $k,l\geq 2$) are the three skein relations mentioned earlier.

$\mapsto$$+$$\mapsto$$+$$-$$\mapsto$$+$$-$$-$$\mapsto$$+$$\mapsto$$+$$-$$\mapsto$$+$$-$$-$
Figure 1. The three skein relations defining the action of
${\mathfrak{S}}_{n}$ on ${\mathbb{C}}[NCP(n)]$. The red vertices are adjacent
indices $i,i+1$ and the shaded blocks have at least three elements. The
symmetric 3-term relation obtained by reflecting the middle relation across
the $y$-axis is not shown.

A more detailed description of this action can be found in [7]. Rhoades showed
that we again have an ${\mathfrak{S}}_{n}$-equivariant linear projection
$p_{\Pi}:\mathbb{C}[\Pi(n)]\rightarrow\mathbb{C}[NCP(n)]$ given for any set
partition $\pi$ by

(1.6) $\pi\mapsto w^{-1}\cdot(w\circ\pi),$

where $w$ is any permutation for which $w\circ\pi$ (here $\circ$ denotes the
action of ${\mathfrak{S}}_{n}$ on all set partitions) is noncrossing. The
kernel of this projection is generated by the set of all elements of the form
$w\circ(s_{i}\circ\pi+\sigma(\pi))$ (the skein relations) for any permutation
$w$ and almost noncrossing set partition $\pi$.

Rhoades was able to determine the ${\mathfrak{S}}_{n}$-irreducible structure
of this module. In particular, the span of all singleton-free noncrossing set
partitions with exactly $k$ blocks is an ${\mathfrak{S}}_{n}$-irreducible of
shape $(k,k,1^{n-2k})$, and the span of all noncrossing set partitions with
exactly $s$ singletons and exactly $k$ non-singleton blocks is isomorphic to
an induction product of $S^{(k,k,1^{n-2k-s})}$ with the sign representation of
${\mathfrak{S}}_{s}$. Similarly, if we restrict the action on
$\mathbb{C}[NCM(n)]$ to the span of noncrossing perfect matchings, i.e.
noncrossing matchings of $[2n]$ with exactly $n$ pairs, then this action gives
a model for the ${\mathfrak{S}}_{n}$-irreducible of shape $(n,n)$ called the
$SL_{2}$-web basis. If we instead restrict to the span of noncrossing
matchings with exactly $k$ pairs, we get a submodule isomorphic to the
induction product of $S^{(k,k)}$ and a sign representation of
${\mathfrak{S}}_{n-2k}$. By the Pieri rule, this induction product is a direct
sum of three irreducible submodules, one of which is isomorphic to
$S^{(k,k,1^{n-2k})}$ appears in this induction product, so there exists a
unique embedding of $\mathbb{C}[NCP(n)_{0}]$, the span of all singleton-free
noncrossing set partitions in $\mathbb{C}[NCP(n)]$, into $\mathbb{C}[NCM(n)]$.
The main result of this paper explicitly describes the embedding as follows:

######  Theorem 1.1.

The linear map $f_{n}:\mathbb{C}[NCP(n)_{0}]\rightarrow\mathbb{C}[NCM(n)]$
defined by

$f_{n}(\pi)=\sum_{m\in M_{\pi}(n)}m$

is a ${\mathfrak{S}}_{n}$-equivariant embedding of vector spaces. Here
$M_{\pi}(n)$ is defined to be the set of all matchings $m$ in $M(n)$ for which
each block of $\pi$ contains exactly one pair in $m$.

For an example of this map, let $\pi=\\{\\{1,2,3\\},\\{4,5\\}\\}$ then

$f_{n}(\pi)=\\{\\{1,2\\},\\{4,5\\}\\}+\\{\\{1,3\\},\\{4,5\\}\\}+\\{\\{2,3\\},\\{4,5\\}\\}$

is a sum of 3 matchings in $\mathbb{C}[NCM(n)]$.

The rest of the paper is organized as follows. Section 2 will provide
necessary background information. Section 3 will prove our main result, the
embedding from $\mathbb{C}[NCP(n)]$ to $\mathbb{C}[NCM(n)]$. Section 4 will
determine the image of this embedding within $\mathbb{C}[NCM(n)]$.

##  2\. Background

###  2.1. ${\mathfrak{S}}_{n}$-representation theory

For $n\in\mathbb{Z}_{\geq 0}$, a partition of $n$ is a weakly decreasing
sequence $\lambda=(\lambda_{1},\lambda_{2},\dots,\lambda_{k})$ of positive
integers such that $\lambda_{1}+\cdots+\lambda_{k}=n$. Partitions of $n$ can
be represented by Young diagrams, which is an arrangement of square boxes into
$n$ left-justified rows, with the $i^{th}$ row containing $\lambda_{i}$ boxes.

Irreducible representations of the symmetric group ${\mathfrak{S}}_{n}$ are
naturally indexed by partitions of $n$. Let $S^{\lambda}$ denote the
${\mathfrak{S}}_{n}$-irreducible corresponding to partition $\lambda$. Given
two representations $V$ and $W$ of ${\mathfrak{S}}_{m_{1}}$ and
${\mathfrak{S}}_{m_{2}}$ respectively, with $m_{1}+m_{2}=n$, the induction
product $V\circ W$ is given by

$V\circ
W=\mathrm{Ind}_{{\mathfrak{S}}_{m_{1}}\times{\mathfrak{S}}_{m_{2}}}^{{\mathfrak{S}}_{n}}V\otimes
W$

where ${\mathfrak{S}}_{m_{1}}\times{\mathfrak{S}}_{m_{2}}$ is identified with
the parabolic subgroup of ${\mathfrak{S}}_{n}$ which permutes
$\\{1,\dots,m_{1}\\}$ and $\\{m_{1}+1,\dots,n\\}$ separately. When $V$ is an
irreducible representation $S^{\mu}$ for some partition $\mu$ of $m_{1}$ and
$W$ is a trivial representation of ${\mathfrak{S}}_{m_{2}}$, the Pieri rule
describes how to express $V\circ W$ in terms of irreducibles,

(2.1)
$S^{\mu}\circ\mathrm{triv}_{{\mathfrak{S}}_{m_{2}}}\cong\sum_{\lambda}S^{\lambda}$

where the sum is over all partitions $\lambda$ whose young diagram can be
obtained from that of $\mu$ by adding $m_{2}$ boxes, no two in the same
column. The dual Pieri rule describes the same when $W$ is a sign
representation instead of a trivial representation we again have

(2.2)
$S^{\mu}\circ\mathrm{sign}_{{\mathfrak{S}}_{m_{2}}}\cong\sum_{\lambda}S^{\lambda}$

but the sum is now over all partitions $\lambda$ whose young diagram can be
obtained from that of $\mu$ by adding $m_{2}$ boxes, no two in the same row.

###  2.2. Projections and their kernels

Here we provide justification for the two claims made in the introduction
regarding spanning sets for the kernels of the projection maps. The first such
claim is standard, while the second indirectly follows from results in [7]. We
include a proof of the first, the proof of the second is analogous.

######  Proposition 2.1.

The kernel of the projection
$p_{M}:\mathbb{C}[M(n)]\rightarrow\mathbb{C}[NCM(n)]$ is spanned by elements
of the form

(2.3)
$\\{\\{a_{1},a_{2}\\},\\{a_{3},a_{4}\\},\\{a_{5},a_{6}\\},\dots,\\{a_{2k-1},a_{2k}\\}\\}\\\
+\\{\\{a_{1},a_{3}\\},\\{a_{2},a_{4}\\},\\{a_{5},a_{6}\\},\dots,\\{a_{2k-1},a_{2k}\\}\\}\\\
+\\{\\{a_{1},a_{4}\\},\\{a_{2},a_{3}\\},\\{a_{5},a_{6}\\},\dots,\\{a_{2k-1},a_{2k}\\}\\}$

for any $a_{1},\dots,a_{2k}\in[n]$, i.e. sums of three matchings which differ
by a Ptolemy relation.

###### Proof.

Let $\beta$ denote the set of all elements of the form given in equation 2.3.
To see that the span of $\beta$ is contained in the kernel of $p_{M}$, note
that by the ${\mathfrak{S}}_{n}$-equivariance of $p_{M}$ it suffices to check
that applying $p_{M}$ gives 0 in the case where $a_{i}=i$ for all $i$. In this
case, we have

(2.4)
$p_{M}(\\{1,2/3,4/\cdots/2k-1,2k\\}+\\{1,3/2,4/\cdots/2k-1,2k\\}+\\{1,4/2,3/\cdots/2k-1,2k\\})\\\
=\\{1,2/3,4/\cdots/2k-1,2k\\}+(2,3)\cdot(-\\{1,2/3,4/\cdots/2k-1,2k\\})+\\{1,4/2,3/\cdots/2k-1,2k\\}\\\
=0$

To see that the kernel is contained in the span, note that since $p_{M}$ is a
projection, the kernel is spanned by $m-p_{M}(m)$ for any matching $m$. Let
$t$ denote the minimum number of transpositions $s_{i_{1}},\dots,s_{i_{t}}$
for which $(s_{i_{1}}\cdots s_{i_{t}})\star m$ is noncrossing, and let
$w=s_{i_{1}}\cdots s_{i_{t}}$. We will show by induction on $t$ that
$m-p_{M}(m)\in\textrm{span}(\beta)$. When $t=0$, then $m-p_{M}(m)=0$, so the
claim is true. Otherwise, assume the claim holds for $t-1$. We have
$m-p_{M}(m)=s_{i_{1}}\circ(s_{i_{1}}\circ m)-s_{i_{1}}\cdot
p_{M}(s_{i_{1}}\circ m)$. By our inductive hypothesis, $s_{i_{1}}\circ
m-p_{M}(s_{i_{1}}\circ m)$ lies in the span of $\beta$, so it suffices to
verify for any $b\in\beta$, that if we apply $s_{i_{1}}\circ(-)$ to every
crossing term of $b$ and apply either $s_{i_{1}}\cdot(-)$ or
$s_{i_{1}}\circ(-)$ to every noncrossing term of $b$, we remain in the span of
$\beta$. This is true because $\beta$ is closed under the $\circ$ action, and
for every noncrossing matching $m_{1}$, either

$s_{i_{1}}\circ m=s_{i_{1}}\cdot m$

or

$s_{i_{1}}\cdot m_{1}=s_{i_{1}}\circ m_{1}-(s_{i_{1}}\circ
m_{1}+m_{1}+m_{1}^{\prime})$

where $m_{1}^{\prime}$ is obtained by replacing the sets $\\{i,a\\}$ and
$\\{i+1,b\\}$ with the sets $\\{i,i+1\\}$ and $\\{a,b\\}$. In the second case,
$s_{i_{1}}\circ m_{1}+m_{1}+m_{1}^{\prime}$ is in $\beta$. ∎

######  Proposition 2.2.

The kernel of the projection
$p_{\Pi}:\mathbb{C}[\Pi(n)]\rightarrow\mathbb{C}[NCP(n)]$ is spanned by
elements of the form

$\displaystyle w\circ(s_{i}\circ\pi+\sigma(\pi))$

for any permutation $w$ and singleton-free almost noncrossing set partition
$\pi$, i.e. sums of set partitions which differ by a skein relation.

##  3\. The embedding

In order to prove that our map is an embedding, it will be helpful to
introduce a multiplicative structure to work with. To do so we will introduce
three graded commutative $\mathbb{C}$-algebras $R_{n}$, $A_{n}$, and $M_{n}$,
all with ${\mathfrak{S}}_{n}$-actions. If we forget the multiplicative
structure, the underlying ${\mathfrak{S}}_{n}$-modules of $R_{n}$, $A_{n}$,
and $M_{n}$ will contain a copy $\mathbb{C}[\Pi(n)]$, $\mathbb{C}[M(n)]$, and
$\mathbb{C}[NCM(n)]$ respectively. In the case of $M_{n}$, this copy will be
all of $M_{n}$. The structure of this proof is best explained via a
commutative diagram, see Figure 2. We will define a map
$h_{n}\circ\iota_{\Pi}:\mathbb{C}[\Pi(n)_{0}]\rightarrow M_{n}$, and show that
its kernel is equal to the kernel of $p_{\Pi}$. The desired embedding $f_{n}$
then follows from the first isomorphism theorem.

${R_{n}}$${A_{n}}$${M_{n}}$${\mathbb{C}[M(n)]}$${\mathbb{C}[NCM(n)]}$${\mathbb{C}[\Pi(n)_{0}]}$${\mathbb{C}[NCP(n)_{0}]}$$\scriptstyle{g_{n}}$$\scriptstyle{h_{n}}$$\scriptstyle{q}$$\scriptstyle{\cong}$$\scriptstyle{p_{M}}$$\scriptstyle{\iota_{M}}$$\scriptstyle{\iota_{\Pi}}$$\scriptstyle{p_{\Pi}}$$\scriptstyle{f_{n}}$
Figure 2. A commutative diagram of the maps used in the following proofs. All
maps shown are ${\mathfrak{S}}_{n}$-equivariant linear maps. Maps between
$R_{n}$, $A_{n}$, and $M_{n}$ are also morphisms of $\mathbb{C}$-algebras. The
desired embedding is shown as a dashed arrow.

We begin with the definition of $R_{n}$.

######  Definition 3.1.

Let $n\in\mathbb{N}$. Define $R_{n}$ to be the unital graded commutative
$\mathbb{C}$-algebra generated by nonempty subsets of $[n]$ where each
generator has degree $1$. Define a degree-preserving action of
${\mathfrak{S}}_{n}$ on $R_{n}$ by

$\pi\cdot\\{a_{1},\dots,a_{k}\\}=\mathrm{sign}(\pi)\\{\pi(a_{1}),\cdots,\pi(a_{k})\\}$

for any permutation $\pi\in{\mathfrak{S}}_{n}$ and generator
$\\{a_{1},\cdots,a_{k}\\}\in R_{n}$.

The ring $R_{n}$ can be thought of as the ring of multiset collections of
subsets of $[n]$ with multiplication given by union of collections and
addition purely formal. It is in this sense that it contains a copy of
$\mathbb{C}[\Pi(n)]$, as set partitions of $n$ are particular collections of
subsets of $[n]$. To be precise, there exists an ${\mathfrak{S}}_{n}$-module
embedding $\iota_{\Pi}:\mathbb{C}[\Pi(n)_{0}]\hookrightarrow R_{n}$, given by
sending any singleton-free set partiton $\pi$ to the product of its blocks.

The ring $A_{n}$ is a subring of $R_{n}$ designed to model matchings in much
the same way which $R_{n}$ models set partitions. It is defined as follows.

######  Definition 3.2.

Let $n\in\mathbb{N}$ and define $A_{n}$ to be the
${\mathfrak{S}}_{n}$-invariant subalgebra of $R_{n}$ generated by the size two
subsets of $[n]$. The subring $A_{n}$ is invariant under the
${\mathfrak{S}}_{n}$-action of $R_{n}$, and thus inherits a graded
${\mathfrak{S}}_{n}$-action from $R_{n}$.

Like $R_{n}$, the ring $A_{n}$ can be thought of as the ring of multiset
collections of size-two subsets of $[n]$. As matchings are particular
collections of size-two subsets of $[n]$, we again have an
${\mathfrak{S}}_{n}$-module embedding
$\iota_{M}:\mathbb{C}[M(n)]\hookrightarrow A_{n}$, given by

$\\{\\{a_{1},b_{1}\\},\dots,\\{a_{k},b_{k}\\}\\}\longmapsto\\{a_{1},b_{1}\\}\cdots\\{a_{k},b_{k}\\}$

for any matching $\\{\\{a_{1},b_{1}\\},\dots,\\{a_{k},b_{k}\\}\\})$.

Our final ring, $M_{n}$, is defined as a quotient of $A_{n}$ in the following
way.

######  Definition 3.3.

Define $I_{n}$ to be the ideal of $A_{n}$ generated by elements of the
following forms

  * •

$\\{a,b\\}\cdot\\{a,b\\}$

  * •

$\\{a,b\\}\cdot\\{a,c\\}$

  * •

$\\{a,b\\}\cdot\\{c,d\\}+\\{a,c\\}\cdot\\{b,d\\}+\\{a,d\\}\cdot\\{b,c\\}$

for any distinct $a,b,c,d\in[n]$. Then $I_{n}$ is a homogeneous
${\mathfrak{S}}_{n}$-invariant ideal of $A_{n}$, so define $M_{n}$ to be the
graded ${\mathfrak{S}}_{n}$-module $M_{n}:=A_{n}/I_{n}$. Let
$q:A_{n}\rightarrow M_{n}$ be the quotient map.

The first two types of elements listed in the definition of $I_{n}$ serve the
purpose of removing collections of size-two subsets which are not actually
matchings. The third is the Ptolemy relation used to define the action of
${\mathfrak{S}}_{n}$ on $\mathbb{C}[NCM(n)]$, so quotienting by this ideal
gives an ${\mathfrak{S}}_{n}$-module isomorphic to $\mathbb{C}[NCM(n)]$, as
per the following argument.

######  Proposition 3.4.

There is an ${\mathfrak{S}}_{n}$-module isomorphism from $\mathbb{C}[NCM(n)]$
to $M_{n}$, given by

$\\{\\{a_{1},b_{1}\\},\dots,\\{a_{k},b_{k}\\}\\}\longmapsto\\{a_{1},b_{1}\\}\cdots\\{a_{k},b_{k}\\}$

for any noncrossing matching
$\\{\\{a_{1},b_{1}\\},\dots,\\{a_{k},b_{k}\\}\\}$.

###### Proof.

Let $q:A_{n}\rightarrow M_{n}$ be the quotient map. Consider the map
$q\circ\iota_{M}:\mathbb{C}[M(n)]\rightarrow M_{n}$. The kernel of
$q\circ\iota_{M}$ is spanned by the elements of $\mathbb{C}[M(n)]$ which are
sent under $\iota_{M}$ to a multiple of
$\\{a,b\\}\cdot\\{c,d\\}+\\{a,c\\}\cdot\\{b,d\\}+\\{a,d\\}\cdot\\{b,c\\}$ for
some distinct $a,b,c,d\in[n]$. Therefore the kernel of $q\circ\iota_{M}$ is
equal to the kernel of $p_{M}$ by Proposition 2.1. The image of
$q\circ\iota_{M}$ is all of $M_{n}$. To see this, note that products of
generators of $A_{n}$ form a vector space basis for $A_{n}$, and every such
basis element is either in the image of $\iota_{M}$ or in $I_{n}$. We
therefore have

(3.1)
$\mathbb{C}[NCM(n)]\cong\mathbb{C}[M(n)]/\mathrm{ker}(p_{M})=\mathbb{C}[M(n)]/\mathrm{ker}(q\circ\iota_{M})\cong\mathrm{im}(q\circ\iota_{M})=M_{n}$

where the isomorphism on the left is induced by the map $p_{M}$ and the
isomorphism on the right is induced by the map $q\circ\iota_{M}$. Composing
these isomorphisms gives the stated map. ∎

The following definition is the key idea behind our main theorem.

######  Definition 3.5.

Let $n\in\mathbb{N}$. Define the $\mathbb{C}$-algebra map
$g_{n}:R_{n}\rightarrow A_{n}$ by

$g_{n}(A)=\sum_{\\{a,b\\}\subseteq A}\\{a,b\\}$

for generators $A\in R_{n}$. Singleton sets are sent to $0$ by $g_{n}$. Define
$h_{n}:=q\circ g_{n}$ where $q$ is the quotient map $A_{n}\rightarrow M_{n}$.

We give the definition in terms of $R_{n}$, $A_{n}$, and $M_{n}$ for
simplicity and ease of proofs later, but the map we really care about is
$h_{n}\iota_{\Pi}:\mathbb{C}[\Pi(n)]\rightarrow M_{n}$. Under this map, a set
partition $\pi$ is sent to the product of its blocks, then each block is sent
to the sum of all size-two subsets it contains. After distributing, we get a
sum of all ways to pick a size two subset from each block. Composing with the
isomorphism between $M_{n}$ and $\mathbb{C}[NCM(n)]$ we get the sum of all
matchings such that each block of $\pi$ contains exactly one pair of the
matching, as in Theorem 3.8.

The ${\mathfrak{S}}_{n}$-equivariance of $h_{n}$ is simple to check. We have
the following calculation.

######  Lemma 3.6.

Let $i,j\geq 2$ and let $p_{1},p_{2},\dots,p_{i}$ and
$q_{1},q_{2},\dots,q_{j}$ be in $[n]$. Then the element of $R_{n}$

$\displaystyle\kappa_{n}:=\\{p_{1},\dots,p_{i}\\}\cdot\\{q_{1},\dots,q_{j}\\}$
$\displaystyle-\\{p_{1},\cdots p_{i-1}\\}\cdot\\{q_{1},\cdots
q_{j},p_{i}\\}-\\{p_{1},\cdots p_{i},q_{j}\\}\cdot\\{q_{1},\cdots q_{j-1}\\}$
$\displaystyle+\\{p_{1},\cdots p_{i-1},q_{j}\\}\cdot\\{q_{1},\cdots
q_{j-1},p_{i}\\}+\\{p_{1},\cdots p_{i-1},q_{1},\cdots
q_{j-1}\\}\cdot\\{p_{i},q_{j}\\}$

lies in the kernel of $h_{n}$.

When $i,j>2$, the element $\kappa_{n}$ corresponds to the five-term skein
relation depicted in Figure 1. If either $i$ eqauls 2, then $\\{p_{1},\cdots
p_{i-1}\\}=\\{p_{1}\\}$ is a one element set and therefore sent to 0 by
$h_{n}$, removing the term containing $\\{p_{1}\\}$ corresponds to the four-
term skein relation depicted in Figure 1. Similarly, if $j$ equals 2 or $i$
and $j$ both equal two, removing the terms in $\kappa_{n}$ which are
individually sent to 0 corresponds to the four or three-term skein relation
depicted in Figure 1.

###### Proof.

Applying $h_{n}$ to $\kappa_{n}$ gives

$\displaystyle\sum_{\begin{subarray}{c}\\{a,b\\}\subseteq\\{p_{1},\dots,p_{i}\\}\\\
\\{c,d\\}\subseteq\\{q_{1},\dots,q_{j}\\}\end{subarray}}\\{a,b\\}\cdot\\{c,d\\}$
$\displaystyle-\sum_{\begin{subarray}{c}\\{a,b\\}\subseteq\\{p_{1},\dots,p_{i-1}\\}\\\
\\{c,d\\}\subseteq\\{q_{1},\dots,q_{j},p_{i}\\}\end{subarray}}\\{a,b\\}\cdot\\{c,d\\}-\sum_{\begin{subarray}{c}\\{a,b\\}\subseteq\\{p_{1},\dots,p_{i},q_{j}\\}\\\
\\{c,d\\}\subseteq\\{q_{1},\dots,q_{j-1}\\}\end{subarray}}\\{a,b\\}\cdot\\{c,d\\}$
$\displaystyle+\sum_{\begin{subarray}{c}\\{a,b\\}\subseteq\\{p_{1},\dots,p_{i-1},q_{j}\\}\\\
\\{c,d\\}\subseteq\\{q_{1},\dots,q_{j-1},p_{i}\\}\end{subarray}}\\{a,b\\}\cdot\\{c,d\\}+\sum_{\begin{subarray}{c}\\{a,b\\}\subseteq\\{p_{1},\dots,p_{i-1},q_{1},\cdots,q_{j-1}\\}\\\
\\{c,d\\}\subseteq\\{p_{i},q_{j}\\}\end{subarray}}\\{a,b\\}\cdot\\{c,d\\}$

Note that the pairs of sets defining the first and second summations in the
above expression differ only in the location of $p_{i}$, and similarly for the
third and fourth. Since these summations come with opposite signs, the
$\\{a,b\\},\\{c,d\\}$ terms in the above expression will cancel unless one of
$a,b,c,d$ is equal to $p_{i}$. Similarly, comparing the first and third sums
and the second and fourth sums we find cancellation unless at least one of
$a,b,c,d$ is equal to $q_{j}$. If the remaining two elements of $a,b,c,d$ are
both $p$’s or both $q$’s, then $\\{a,b\\}\cdot\\{c,d\\}$ also cancels.
Therefore we have

(3.2)
$h_{n}(\kappa_{n})=\sum_{\begin{subarray}{c}a\in\\{p_{1},\dots,p_{i-1}\\}\\\
b\in\\{q_{1},\dots,q_{j-1}\\}\end{subarray}}\\{a,p_{i}\\}\cdot\\{b,q_{j}\\}+\\{a,q_{j}\\}\cdot\\{b,p_{i}\\}+\\{a,b\\}\cdot\\{p_{i},q_{j}\\}$

which is manifestly a sum of the definining relations of $M_{n}$. ∎

The above calculation allows for the identification of the kernel of
$h\circ\iota_{\Pi}$ and $p_{\Pi}$ mentioned in the beginning of this section.

######  Proposition 3.7.

The kernel of $h\circ\iota_{\Pi}$ is generated by the set of all elements of
the form $w\circ(s_{i}\circ\pi+\sigma(\pi))$ (the skein relations) for any
permutation $w$ and singleton-free almost noncrossing set partition $\pi$.

###### Proof.

By Lemma 3.6, all such elements lie in the kernel. Since restricting
$\mathbb{C}[\Pi(n)_{0}]$ to noncrossing set partitions with exactly $k$ blocks
gives an irreducible submodule [7, Proposition 5.2], and each such irreducible
is sent to degree $k$ in $M_{n}$, it suffices to demonstrate that each
irreducible is not sent identically to 0. But for each noncrossing set
partition $\pi\in\Pi(n)_{0}$, $h_{n}\circ\iota(\pi)$ is a sum of noncrossing
matchings of $[n]$, which form a basis for $M_{n}$ by Proposition 3.4, and is
therefore nonzero. ∎

We can now prove our main result.

######  Theorem 3.8.

The linear map $f_{n}:\mathbb{C}[NCP(n)_{0}]\rightarrow\mathbb{C}[NCM(n)]$
defined by

$f_{n}(\pi)=\sum_{m\in M_{\pi}(n)}m$

is a ${\mathfrak{S}}_{n}$-equivariant embedding of vector spaces. Here
$M_{\pi}(n)$ is defined to be the set of all matchings $m$ in $M(n)$ for which
each block of $\pi$ contains exactly one pair in $m$.

###### Proof.

By Proposition 3.7 and Proposition 2.2, the kernel of $h\circ\iota_{\Pi}$ is
equal to the kernel of $p_{\Pi}$. So we have

(3.3)
$\mathbb{C}[NCP(n)_{0}]\cong\mathbb{C}[\Pi_{0}(n)]/\mathrm{ker}(p_{\Pi})=\mathbb{C}[\Pi(n)_{0}]/\mathrm{ker}(h\circ\iota_{\Pi})\cong\mathrm{im}(h\circ\iota_{\Pi})\subset
M_{n}\cong\mathbb{C}[NCM(n)]$

where the isomorphism on the left is induced by $p_{\Pi}$ and the isomorphism
on the right is induced by $h\circ\iota_{\Pi}$. Chasing these isomorphisms and
inclusions results in the map $f_{n}$. ∎

##  4\. The image

We have an embedding
$f_{n}:\mathbb{C}[NCP(n)_{0}]\hookrightarrow\mathbb{C}[NCM(n)]$, so it is a
natural question to ask for a description of the image of $f_{n}$ within
$\mathbb{C}[NCM(n)]$. Via the commutative diagram in Figure 2,we have an
isomorphism of images

(4.1) $\mathrm{im}(h_{n})\cong\mathrm{im}(f_{n}).$

So it is equivalent to describe the image of $h_{n}$, and the multiplicative
structure of $M_{n}$ will make describing the image of $h_{n}$ easier. This
section will show that the image of $h_{n}$ has a simple description, the
proof of which will require the following lemmas.

######  Lemma 4.1.

Let $A\subseteq[n]$. Then $h_{n}(A)^{2}=0$.

###### Proof.

Applying the definition of $h_{n}$ gives

(4.2) $h_{n}(A)^{2}=\sum_{\begin{subarray}{c}a,b\in[n]\\\ a\neq
b\end{subarray}}\sum_{\begin{subarray}{c}c,d\in[n]\\\ c\neq
d\end{subarray}}\\{a,b\\}\cdot\\{c,d\\}$

Using the defining relation of $M_{n}$ that

$\\{a,b\\}\cdot\\{a,c\\}=0$

we have

(4.3) $\sum_{\begin{subarray}{c}a,b\in[n]\\\ a\neq
b\end{subarray}}\sum_{\begin{subarray}{c}c,d\in[n]\\\ c\neq
d\end{subarray}}\\{a,b\\}\cdot\\{c,d\\}=\frac{1}{3}\sum_{\begin{subarray}{c}a,b,c,d\in[n]\\\
a,b,c,d\,\mathrm{distinct}\end{subarray}}\\{a,b\\}\cdot\\{c,d\\}+\\{a,c\\}\cdot\\{b,d\\}+\\{a,d\\}\cdot\\{b,c\\}.$

The right hand side of the above equation equals 0 because

$\\{a,b\\}\cdot\\{c,d\\}+\\{a,c\\}\cdot\\{b,d\\}+\\{a,d\\}\cdot\\{b,c\\}=0$

for any distinct $a,b,c,d\in[n]$. ∎

######  Lemma 4.2.

Let $A,B$ be disjoint subsets of $[n]$. Then

$h_{n}(A)\cdot\left(\sum_{\begin{subarray}{c}a\in A\\\ b\in
B\end{subarray}}\\{a,b\\}\right)=0.$

###### Proof.

Applying $h_{n}$ gives

$h_{n}(A)\cdot\left(\sum_{\begin{subarray}{c}a\in A\\\ b\in
B\end{subarray}}\\{a,b\\}\right)=\frac{1}{3}\sum_{a_{1},a_{2},a_{3}\in
A}\sum_{b\in
B}\\{a_{1},a_{2}\\}\cdot\\{a_{3},b\\}+\\{a_{1},a_{3}\\}\cdot\\{a_{2},b\\}+\\{a_{2},a_{3}\\}\cdot\\{a_{1},b\\}=0$

∎

######  Lemma 4.3.

Let $B_{1},\dots,B_{k}$ be the blocks of a singleton free set partition of
$[n]$. Then

$h_{n}\left(\prod_{i=1}^{k}B_{k}\right)=h_{n}\left([n]\cdot\prod_{i=1}^{k-1}B_{k}\right)$

###### Proof.

We have the following calculation:

$\displaystyle h_{n}\left([n]\cdot\prod_{i=1}^{k-1}B_{i}\right)$
$\displaystyle=\left(\sum_{\begin{subarray}{c}a,b\in[n]\\\ a\neq
b\end{subarray}}\\{a,b\\}\right)\cdot
h_{n}\left(\prod_{i=1}^{k-1}B_{i}\right)$
$\displaystyle=\left(\left(\sum_{i=1}^{k}h_{n}(B_{i})\right)+\left(\sum_{1\leq
i<j\leq k}\sum_{\begin{subarray}{c}a\in B_{i}\\\ b\in
B_{j}\end{subarray}}\\{a,b\\}\right)\right)\cdot
h_{n}\left(\cdot\prod_{i=1}^{k-1}B_{k}\right)$
$\displaystyle=h_{n}(B_{i})\cdot\left(\cdot\prod_{i=1}^{k-1}h_{n}(B_{i})\right)$

where the last line follows by the preceeding two lemmas, as every term in the
outer sum of

$\sum_{1\leq i<j\leq k}\sum_{\begin{subarray}{c}a\in B_{i}\\\ b\in
B_{j}\end{subarray}}\\{a,b\\}$

is annihilated by some term in the product

$\prod_{i=1}^{k-1}h_{n}(B_{k})$

and every term except the $i=k$ term in the sum

$\sum_{i=1}^{k}h_{n}(B_{i})$

is annihilated by some term in the product

$\prod_{i=1}^{k-1}h_{n}(B_{k}).$

∎

We can now describe the image of $h_{n}$.

######  Theorem 4.4.

Let $H_{n}$ be the ideal of $M_{n}$ generated by $h_{n}([n])$. Then

$\mathrm{im}(h_{n})=H_{n}.$

###### Proof.

It is immediate from Lemma 4.3 that the image of $h_{n}$ is contained in
$H_{n}$, so it suffices to show that

(4.4)
$\mathrm{dim}(H_{n})\leq\mathrm{dim}(\mathrm{im}(h_{n}))=\mathrm{dim}(\mathrm{im}(f_{n}))=\\#NCP(n)_{0}$

To bound the dimension of $H_{n}$, note that for any fixed $a\in[n]$,

$h_{n}([n])\cdot\left(\sum_{\begin{subarray}{c}b\in[n]\\\ b\neq
a\end{subarray}}\\{a,b\\}\right)=\frac{1}{3}\sum_{\begin{subarray}{c}b\in[n]\\\
b\neq a\end{subarray}}\sum_{\begin{subarray}{c}c\in[n]\\\ c\neq
a\end{subarray}}\sum_{\begin{subarray}{c}d\in[n]\\\ d\neq
a\end{subarray}}(\\{a,b\\}\cdot\\{c,d\\}+\\{a,c\\}\cdot\\{b,d\\}+\\{a,d\\}\cdot\\{b,c\\})=0$

so

$h_{n}([n])\cdot\\{1,a\\}=-h_{n}([n])\cdot\left(\sum_{\begin{subarray}{c}b\in[n]\\\
b\neq a,1\end{subarray}}\\{a,b\\}\right).$

Therefore $H_{n}$ is spanned by elements of the form

$h_{n}([n])\cdot\\{a_{1},a_{2}\\}\cdot\\{a_{3},a_{4}\\}\cdots\\{a_{2k-1},a_{2k}\\}$

where the sets $\\{a_{1},a_{2}\\},\dots,\\{a_{2k-1},a_{2k}\\}$ form a
noncrossing matching of $\\{2,\dots,n\\}$. These elements are not linearly
independent, however. Consider the element $\tilde{f}_{n}(\tilde{\pi})$ of
$M_{n}$ given by

$\tilde{f}_{n}(\tilde{\pi}):=\prod_{B\in\tilde{\pi}}h_{n}(B)$

for any singleton free noncrossing set partition $\tilde{\pi}$ of
$\\{2,\dots,n\\}$ (i.e. the “image of $f_{n}$” if such a set partition were in
the domain of $f_{n}$). Let $B_{1}$ be the block of $\tilde{\pi}$ containing
$2$, and let $\pi$ be the set partition of $[n]$ obtained by adding $1$ to
block $B_{1}$. We have

$\displaystyle h_{n}([n])\cdot\tilde{f}_{n}(\tilde{\pi})$
$\displaystyle=h_{n}([n])\cdot\prod_{B\in\tilde{\pi}}h_{n}(B)$
$\displaystyle=h_{n}(B_{1})\cdot h_{n}\left([n]\cdot\prod_{B\neq
B_{1}\in\pi}B\right)$ $\displaystyle=h_{n}(B_{1})\cdot
h_{n}\left(\prod_{B\in\pi}B\right)$
$\displaystyle=h_{n}(B_{1})h_{n}(B_{1}\cup\\{1\\})h_{n}\left(\prod_{B\neq
B_{1}\in\pi}B\right)$ $\displaystyle=0$

The third equality follows from Lemma 4.3 and the final equality follows from
the fact that

$h_{n}(B_{1})h_{n}(B_{1}\cup\\{1\\})=h_{n}(B_{1})^{2}+h_{n}(B_{1})\left(\sum_{b\in
B_{1}}\\{1,b\\}\right)=0$

which follows from Lemma 4.2 and Lemma 4.1. The collection of
$\tilde{f}_{n}(\tilde{\pi})$ for singleton-free noncrossing set partitions
$\pi$ of $\\{2,\dots,n\\}$ is linearly independent. To see this, note that any
linear relation among the $\tilde{f}_{n}(\tilde{\pi})$ would also be a linear
relation among $f_{n-1}(\pi)$ where $\pi$ is the set partition of $[n-1]$
obtained by decrementing the indices in $\tilde{\pi}$. But $f_{n-1}$ is an
embedding and singleton-free noncrossing set partitions are linearly
independent in $\mathbb{C}[NCP(n-1)_{0}]$. The dimension of $H_{n}$ is
therefore bounded by

(4.5) $\mathrm{dim}(H_{n})\leq\\#\\{\textrm{noncrossing matchings of
}\\{2,\dots,n\\}\\}\\\ -\\#\\{\textrm{singleton-free noncrossing set
partitions of }\\{2,\dots,n\\}\\}.$

Noncrossing matchings of $\\{2,\dots,n\\}$ are in bijection with noncrossing
set partitions of $[n]$ in which only the block containing $1$ may be a
singleton (though it may be larger). Given a noncrossing set partition, simply
take the matching that matches the largest and smallest element of each block
not containing $1$. Sinlgeton-free noncrossing set partitions of
$\\{2,\dots,n\\}$ are in bijection with set partitions of $[n]$ in which
$\\{1\\}$ is the unique singleton block. We therefore have

$\mathrm{dim}(H_{n})\leq\\#NCP(n)_{0}$

as desired. ∎

##  5\. Future directions

One of the goals motivating this paper is to find new combinatorially nice
bases for ${\mathfrak{S}}_{n}$-irreducibles which arise from existing bases in
an analogous way to the skein action. More specifically, suppose we have a
basis for $S^{\lambda}$ which is indexed by certain structures on the set
$[k]$, where $k=|\lambda|$ (e.g. noncrossing perfect matchings, in the case of
this paper). We can create a basis for the induction product of $S^{\lambda}$
with a sign representation of ${\mathfrak{S}}_{n-k}$ indexed by all ways to
put a certain structure on a $k$-element subset of $[n]$. The Pieri rule tells
us which ${\mathfrak{S}}_{n}$ irreducibles this decomposes into. In
particular, there will be one copy of $(\lambda,1^{n-k})$. How do we isolate
that irreducible?

It is optimistic to think that there will be a method that works in any sort
of generality, but perhaps analogs could be found in certain specific cases.
For example, an analog might exist for the $A_{2}$-web basis for $S^{(k,k,k)}$
introduced by Kuperberg [k]. The web basis consists of planar bipartite graphs
embedded in a disk with $n$ boundary vertices all of degree 1, interior
vertices are degree 3, all boundary vertices are part of the same bipartition,
and no cycles of length less than 6 exist. One potential candidate for a basis
for $S^{(k,k,k,1^{n-3k})}$ is as follows.

######  Conjecture 5.1.

Let $A$ be the set of all planar bipartite graphs embedded in a disk for which
the following conditions hold

  * •

There are $n$ vertices on the boundary of the disk, and there exists a
bipartition in which all of these vertices are in the same part.

  * •

Every interior vertex is connected to a boundary vertex

  * •

Every interior vertex in the same bipartition as the boundary vertices is
degree 3. These are called negative interior vertices

  * •

Every interior vertex not in the same bipartition as the boundary vertices is
degree at least 3. These are called positive interior vertices.

  * •

The number of positive interior vertices minus the number of negative interior
vertices is exactly $k$.

  * •

No cycles of length less than 6 exist.

Then $|A|$ is equal to the dimension of $S^{(k,k,k,1^{n-3k})}$.

The set $A$ can be thought of as consisting of webs for which the condition of
interior vertices being degree 3 has been partially relaxed. The conjecture
can be shown to hold for $k=2$ and any $n$, as well as $n=10,k=3$ via direct
enumeration. If the above conjecture is true, it suggests the following
question.

######  Question 5.2.

Does there exist a combinatorially nice action of ${\mathfrak{S}}_{n}$ on
$\mathbb{C}[A]$ which creates a ${\mathfrak{S}}_{n}$ module isomorphic to
$S^{(k,k,k,1^{n-3k})}$? If so, what does the unique embedding into
$S^{(k,k,k)}$ induced with a sign representation of ${\mathfrak{S}}_{n-3k}$
look like?

A positive answer to this question might help elucidate how to apply similar
methods more generally.

##  6\. Acknowledgements

We are very grateful to Brendon Rhoades for many helpful discussions and
comments on this project.

## References

  * [1] J. Kim and B. Rhoades. Set partitions, fermions, and skein relations. IMRN, 2022. arXiv:2109.06373
  * [2] G. Kuperberg, Spiders for rank 2 Lie algebras, Comm. Math. Phys. 180 (1996), no. 1, 109–151. arXiv:q-alg/9712003
  * [3] R. Patrias, O. Pechenik, and J. Striker. A web basis of invariant polynomials from noncrossing partitions. Preprint, 2021. arXiv:2112.05781
  * [4] O. Pechenik. Cyclic sieving of increasing tableaux and small Schröder paths. J. Comb. Theory, Ser. A, 125 (2014).
  * [5] K Petersen, P. Pylyavsky, B. Rhoades. Promotion and cyclic sieving via webs. J. Alg. Combinatoris, 30 (2009).
  * [6] V. Reiner, D. Stanton, and D. White. The cyclic sieving phenomenon. J. Comb. Theory, Ser. A, 108 (2004).
  * [7] B. Rhoades. A skein action of the symmetric group on noncrossing partitions. J. Algebraic Combin., 45 (1), (2017), 81–127.
  * [8] B. Sagan. The Symmetric Group, Springer, New York, 2001