%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{20}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

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

\usepackage{stmaryrd}

\let\savelneq\lneq
\let\lneq\relax
\usepackage{mathabx}
\let\lneq\savelneq

\usepackage{scalerel}



%\newcommand{\abctree}{\raisebox{-1pt}{\scaleobj{1.5}{\Ydown}}}
%
%\newcommand{\abcntree}{\raisebox{-1pt}{\scaleobj{1.5}{\convolution}}}


\newtheorem{thm}{Theorem}

\newtheorem{theorem}[thm]{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{proposition}[thm]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{algorithm}[thm]{Algorithm}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{question}[thm]{Question}

\newtheorem*{bijectionExists}{\Cref{thm:bijectionExists}}
\newtheorem*{rjust}{\Cref{thm:rjust}}
\newtheorem*{psiAvoidance}{\Cref{thm:psiAvoidance}}
%\newtheorem*{omegaAvoidance}{\Cref{thm:omegaAvoidance}}



\numberwithin{thm}{section}


\newcommand{\Slide}{\mathrm{Slide}}
\newcommand{\slide}{\mathrm{slide}}
\newcommand{\Tour}{\mathrm{Tour}}
\newcommand{\Cat}{\mathrm{Cat}}
\newcommand{\Av}{\mathrm{Av}}
\newcommand{\tree}{\mathrm{tree}}
\newcommand{\z}{\mathrm{z}}
\newcommand{\rep}{\mathrm{LRep}}
\newcommand{\Int}{\mathrm{Int}}
\newcommand{\dom}{\mathrm{dom}}
\newcommand{\redd}{\mathrm{red}}
\newcommand{\last}{\mathrm{last}}
\newcommand{\PF}{\mathrm{PF}}
\newcommand{\CPF}{\mathrm{CPF}}
\newcommand{\rev}{\mathrm{rev}}

%\newcommand{\CC}{\mathbb{C}}
%\newcommand{\NN}{\mathbb{N}}
\newcommand{\PP}{\mathbb{P}}

\newcommand{\Mbar}{\overline{M}}
\newcommand{\kUnd}{\underline{k}}

\newcommand{\TRep}{\mathrm{TRep}}
\newcommand{\Slwk}{\Slide^\omega(\kUnd)}
\newcommand{\Slpk}{\Slide^\psi(\kUnd)}
\newcommand{\maxzero}{\mathrm{maxzero}}
\newcommand{\mintwo}{\mathrm{min_2}}
\newcommand{\sigmaT}{\hat{\sigma}}
\newcommand{\piT}{\hat{\pi}}

\newcommand{\starTree}{\raisebox{-1pt}{\scaleobj{1.5}{\Ydown}}}
\newcommand{\starThree}{\raisebox{-1pt}{\scaleobj{1.5}{\convolution}}}

\newcommand{\mbf}[1]{\mathbf{#1}}
%\newcommand{\asymbinom}{\genfrac{\langle}{\rangle}{0pt}{}}
%here is Maria's macro:
\def\asymbinom#1#2{\left<\genfrac{}{}{0pt}{}{#1}{#2}\right>}

\usepackage{tikz}


%% define your title in the usual way
\title[Insertion algorithms on trees arising from \texorpdfstring{$\Mbar_{0,n+3}$}{M-bar\_0,n+3}]{Insertion algorithms and pattern avoidance on trees arising in the Kapranov embedding of \texorpdfstring{$\Mbar_{0,n+3}$}{M-bar\_0,n+3}}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{\texorpdfstring{Andrew Reimer-Berg\thanks{\href{mailto:andrew.reimer-berg@colostate.edu}{andrew.reimer-berg@colostate.edu}. Partially supported by NSF DMS award number 2054391}\addressmark{1}}{Andrew Reimer-Berg}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Colorado State University}

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

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We answer a question of Gillespie, Griffin, and Levinson, that asks for a combinatorial bijection between two classes of trivalent trees, ``Slide trees'' and ``Tournament trees'' that are known via geometric arguments to be equinumerous. We define an insertion algorithm that gives a direct bijection between these two types of trees.  
	
	Secondly, we give a full classification of the Slide trees that are of caterpillar shape via pattern avoidance criteria.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{%algebraic combinatorics, 
	%algebraic geometry, 
	%enumerative combinatorics, 
	insertion algorithms,
	trees,
	pattern avoidance, 
	moduli spaces of curves}

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

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


\begin{document}
	
	\maketitle
	%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above
	
	\section{Introduction and Background}
	
	In this extended abstract, which summarizes the results in \cite{RB}, we establish a bijection between two sets of trees that naturally arise in the Kapranov embedding of the complex moduli space $\Mbar_{0,n+3}$.  The space $\Mbar_{0,n+3}$ consists of \textbf{stable genus $0$ curves with $n+3$ marked points} $a,b,c,1,2,\ldots,n$, consisting of one or more copies of $\PP^1$ joined at nodes in a tree structure, with at least $3$ nodes and marked points on each $\PP^1$.  For more details on the construction and properties of $\Mbar_{0,n+3}$, we refer the reader to \cite{Cavalieri16} or \cite[Chapter~1]{green_book}.
	
	Given a stable curve $C\in\Mbar_{0,n+3}$, we may also consider its \textbf{dual tree}. To form the dual tree to a curve, create a vertex for each component of $C$, as well as one for every marked point. Then, for each marked point, connect its vertex to the vertex corresponding to the component it is contained in. For each node, connect the vertices corresponding to the two components that intersect at that node. (See \Cref{fig:MbarEx}.) 
	
	\begin{figure}[bt]
		\centering
		\includegraphics%[scale=0.75]
		{MbarEx1.pdf}
		\hspace{2cm}
		%\includegraphics[scale=0.75]{MbarEx2.pdf}
		\includegraphics%[scale=0.75]
		{MbarEx3.pdf}
		\caption{An element of $\Mbar_{0,n+3}$ for $n=4$, along with its dual tree.}
		\label{fig:MbarEx}
	\end{figure}
	
	The space $\Mbar_{0,n+3}$ has an important stratification given by \textbf{boundary strata}. A stratum consists of all curves in $\Mbar_{0,n+3}$ that share a particular dual tree. 
	The interior $M_{0,n+3}$ is a single stratum, as all interior curves have the star graph as their dual tree.
	We now define forgetting maps on $\Mbar_{0,n+3}$. 
	
	\begin{definition}
		Define the \textbf{$n$th forgetting map} $\pi_n: \Mbar_{0,n+3}\to\Mbar_{0,n+2}$ as the map that forgets the marked point $n$. If this results in a component having less than three nodes plus marked points, we \textit{stabilize} by collapsing the unstable component.
	\end{definition}
	
	We define the Kapranov maps as follows.  The $i$th cotangent line bundle $\mathbb{L}_i$ is the line bundle whose fiber over $C\in\Mbar_{0,n+3}$ is the cotangent space of $C$ at the marked point $i$. The \textbf{$i$th psi class} $\psi_i$ is the first Chern class of $\mathbb{L}_i$. In other words, $\psi_i=c_1(\mathbb{L}_i)$.  The \textbf{$i$th omega class} $\omega_i$ is defined as the pullback of $\psi_i$ under the composition of forgetting maps that forget the marked points $i+1,\ldots,n$. 
	
	We make use of the corresponding maps to projective space, $|\psi_i|:\Mbar_{0,n+3}\to\PP^n$ and $|\omega_i|:\Mbar_{0,n+3}\to\PP^i$, given by $|\omega_i|=|\psi_i|\circ\pi_{i+1}\circ\cdots\circ\pi_n$.
	These can be combined to form the \textbf{total Kapranov map} $\Psi_n:\Mbar_{0,n+3}\to \PP^n\times\cdots\times\PP^n$ given by $$\Psi_n(C)=(|\psi_1|(C),|\psi_2|(C),\ldots,|\psi_n|(C)),$$
	and the
	\textbf{iterated Kapranov map} $\Omega_n: \Mbar_{0,n+3}\hookrightarrow\PP^1\times\PP^2\times\cdots\times\PP^n$ given by $$\Omega_n(C)=(|\omega_1|(C),|\omega_2|(C),\ldots, |\omega_n|(C)).$$
	
	
	Throughout, we let $\kUnd=(k_1,k_2,\ldots,k_n)$ be an $n$-tuple of nonnegative integers and assume it is a composition of $n$, that is, $k_1+k_2+\cdots+k_n=n$.
	
	\begin{definition}
		Consider the intersection between the image of $\Psi_n$ (resp. $\Omega_n$) with $n$ hyperplanes, where we choose $k_i$ general hyperplanes from the $i$th component of the product. Then, the \textbf{multidegree} of $\Psi_n$ (resp. $\Omega_n$) is the number of points in this intersection. This is denoted as $\deg_{\kUnd}(\Psi_n)$ (resp. $\deg_{\kUnd}(\Omega_n)$).
	\end{definition}
	
	It is known (see \cite{Cavalieri16}, for example) that when $\sum k_i=n$, $$\deg_{\kUnd}(\Psi_n)=\int_{\Mbar_{0,n+3}}\psi^{\kUnd}=\binom{n}{k_1,k_2,\ldots,k_n},$$ where $\psi^{\kUnd}$ denotes the product $\prod_i \psi_i^{k_i}$, and the right hand side denotes a multinomial coefficient.  Similarly, it is shown in \cite{CGM} that when $\sum k_i=n$, $$\deg_{\kUnd}(\Omega_n)=\int_{\Mbar_{0,n+3}}\omega^{\kUnd}=\asymbinom{n}{k_1,k_2,\ldots,k_n}.$$ 
	
	Other work studying the degrees of projective maps on moduli spaces of curves include \cite{silversmith21}, working in terms of cross-ratio degrees, and \cite{kapranovdegrees}, which works with more general pullbacks of $\psi$ classes.
	
	The coefficients in the third part of the above equality are the \textbf{asymmetric multinomial coefficients}, defined by $\asymbinom11=1$ and the recursion 
	\begin{equation}\asymbinom{n}{\kUnd}=\sum_{j=i+1}^{n}\asymbinom{n-1}{\kUnd^{(j)}}.\label{eq:recursion}\end{equation}  Above, the symbol $\kUnd^{(j)}$ is defined as follows.  Let $k_i$ be the rightmost 0 in $\kUnd$ (we set $i=0$ if there are no zeroes in $\kUnd$), and let $j>i$ be a positive integer. Define $\kUnd^{(j)}$ to be the composition of $n-1$ formed by decreasing $k_j$ by 1 and then removing the rightmost 0 (which is either in position $j$ or $i$) from the resulting tuple.
	
	\begin{example}
		We compute the coefficient $\asymbinom{4}{1,0,2,1}$: $$\asymbinom{4}{1,0,2,1} = \asymbinom{3}{1,1,1}+\asymbinom{3}{1,0,2}= 3!+\asymbinom{2}{1,1} = 3!+2!=8.$$
	\end{example}
	
	
	\begin{definition}
		Let $\kUnd=(k_1,k_2,\ldots,k_n)$ be a composition of $n$. We say that $\kUnd$ is \textbf{reverse-Catalan} if for all $i$, $k_{n-i+1}+\cdots+k_{n-1}+k_n\geq i$.
	\end{definition}
	
	\begin{proposition}[\cite{CGM}, Corollary 4.14]
		We have $\asymbinom{n}{\kUnd}\neq0$ if and only if $\kUnd$ is reverse Catalan.
		\label{prop:revCatalan}
	\end{proposition}
	
	Several recent papers \cite{CGM,GGL22,GGL23} have studied these asymmetric multinomial coefficients from geometric and combinatorial perspectives, and we summarize those results here.  
	
	
	\begin{proposition}[From \cite{CGM}, \cite{GGL23}, and \cite{GGL22}]
		\label{prop:combinedResults}
		Let $\kUnd$ be a composition of $n$. Then, $$\deg_{\kUnd}(\Omega_n)=\asymbinom{n}{\kUnd}= |\CPF(\kUnd)|=|\Tour(\kUnd)|=|\Slwk|,$$ where $\CPF(\kUnd)$, $\Tour(\kUnd)$, and $\Slwk$ are defined in the next section.
	\end{proposition}
	
	\subsection{Main results}
	
	The sets $\Tour(\kUnd)$ and $\Slwk$ are both sets of trivalent trees with leaves labeled by the set $\{a,b,c,1,2,\ldots,n\}$. Despite this similarity, finding a combinatorial bijection between these two sets has until now been an open question. (See Problem 6.1 in \cite{GGL22}).
	Our first main result constructs an explicit bijection between $\Tour(\kUnd)$ and $\Slwk$, thus proving combinatorially that $|\Tour(\kUnd)|=|\Slwk|$, a fact that was previously only known through geometric techniques.
	
	\begin{theorem}
		There is a combinatorial bijection between the sets $\Tour(\kUnd)$ and $\Slwk$.
		\label{thm:bijectionExists}
	\end{theorem}
	
	The set $\CPF(\kUnd)$ was the first combinatorial interpretation of asymmetric multinomial coefficients, in terms of \textit{parking functions} \cite{CGM}.  A bijection between $\Tour(\kUnd)$ and $\CPF(\kUnd)$ is given in \cite{GGL23}.  Both the parking functions and tournaments interpretations were shown to satisfy the asymmetric multinomial recursion \eqref{eq:recursion}.
	
	We similarly build our bijection recursively, with the main step being to show that $|\Slwk|$ also satisfies the same recursion. In particular, we build a bijection between $\Slwk$ and a disjoint union of slide sets for compositions $\kUnd^{(j)}$ of $n-1$, via an insertion algorithm on $\Slwk$.  Then, we can unwind the recursive algorithms for each of $\Slwk$ and $\Tour(\kUnd)$ to recover a full bijection.
	
	Our second main result is on caterpillar trees.  We say a trivalent tree is a \textbf{caterpillar tree} if its internal edges form a path (see \Cref{ex:slides} below).  We can form a word from a caterpillar tree by reading the slide labels defined in \Cref{sec:slides}, and obtain the following pattern avoidance condition that generalizes results in \cite{GGL22}.
	
	
	\begin{theorem}
		Let $\kUnd$ be a right-justified composition of $n$. Then, $\tree(w)$ is a valid slide tree if and only if $w\in\Av_{\kUnd}(2{-}1{-}2,\ 23{-}\overline{2}{-}1)$.  (See \Cref{sec:patterns}.)
		\label{thm:rjust}
	\end{theorem}
	
	Otherwise, the set of caterpillar trees can not be characterized solely by a pattern avoidance criterion.  We state the characterization result below and define the terms precisely in \Cref{sec:cats}.
	
	\begin{theorem}
		Let $\kUnd$ be a reverse-Catalan composition of $n$, and let $w$ be a word of content $\kUnd$. Then, $\tree(w)\in\Cat^\psi (\kUnd)$ (respectively, $\tree(w)\in\Cat^\omega (\kUnd)$) if and only if $w\in\Av_{\kUnd}(2{-}1{-}2, 23{-}\overline{2}{-}1)$ and $\TRep_w(i)+\ell_w(i)\geq \z(i)$ for all $i$ (respectively, $\rep_w(i)\geq \z(i)$ for all $i$).
		\label{thm:psiAvoidance}
	\end{theorem}
	
	
	
	
	
	
	We now precisely define some of the notions above.
	
	\subsection{Slide trees} \label{sec:slides}
	
	We recall one definition of $\Slpk$ and $\Slwk$ given in \cite{GGL22}, via an algorithm for determining whether a given tree is in a given slide set. Theorem 3.14 from \cite{GGL22} states that a tree $T$ is in $\Slwk$ (resp. $\Slpk$) precisely if it admits an $\omega$ (resp. $\psi$) $\kUnd$-slide labeling.  This is a labeling of the internal edges of $T$ using $k_i$ copies of $i$ for each $i$.
	
	\begin{definition}
		Define the $\omega$ (resp. $\psi$) $\kUnd$-slide labeling of a trivalent tree $T$ as the result of the following procedure, if it finishes. (Otherwise, the $\kUnd$-slide labeling does not exist.)
		\begin{enumerate}[nosep]\setcounter{enumi}{-1}
			\item Start with $\ell=n$, and all edges unlabeled.
			\item \textbf{Contract any labeled edges:} Contract any labeled edges of $T$.
			\item \textbf{Identify the next edge to label:} Let $\mbf e$ be the first unlabeled internal edge on the path from the leaf $\ell$ to $a$. (If no such edge exists, then the process terminates.) Let $v_\ell$ be the vertex adjacent to $\ell$, and $v_a$ be the other vertex of $\mbf e$.
			\item \textbf{Verify that label is valid:} Let $m_\ell$ be the smallest leaf label among all branches of $v_\ell$ not containing $a$ or $\ell$, and $m_a$ as the smallest leaf label among all branches of $v_a$ not containing $a$ or $\ell$.
			If $\ell\geq m_\ell\geq m_a$ (resp. $m_\ell\geq m_a$), then label $\mbf e$ with $\ell$. Otherwise, the process terminates.
			\item \textbf{Iterate:}  If $\ell$ has labeled fewer than $k_\ell$ edges, repeat this process with the same $\ell$. Otherwise, decrement $\ell$, and repeat steps 1--4 until every edge has been labeled.
		\end{enumerate}
		\label{def:k-slide}
	\end{definition}
	
	\begin{example}
		\label{ex:slides}
		Consider the tree below on the left. As we perform the first round of the $\omega$ $(0,0,1,2,1,2)$-slide algorithm, we have $\ell=6$, and try to label the edge on the left of the leaf 6. We have $m_\ell=2$ and $m_a=1$, so since $1<2<6$, we label this edge $\mbf 6$, as shown below on the left. Continuing this process, we end up with the labeling on the right.%, so this tree is an element of $\Slide^\omega(0,0,1,2,1,2)$.
		\begin{center}
			\includegraphics{SlideEx1.pdf}
			\hspace{0.5cm}
			\includegraphics{SlideEx2.pdf}
		\end{center}
	\end{example}
	
	
	As a consequence of \Cref{prop:revCatalan}, we know that $\Slwk$ is nonempty if and only if $\kUnd$ is reverse Catalan.   Note also that from the definitions of $\Slpk$ and $\Slwk$, we have $\Slwk\subseteq\Slpk$.
	
	In order to maintain clarity between edge and leaf labels, we use bolded labels for the edges of a tree and nonbolded labels for the leaves of a tree, like $\mbf x$ vs $x$.     We say that two leaves $i$ and $j$ of a tree are \textbf{adjacent} if there is a vertex $v$ that is connected by edges to both $i$ and $j$. One implication of the definition of slide trees is that the leaves $a$ and $b$ must always be adjacent. We will think of this structure consisting of $a$, $b$, and their common neighbor as the `root' of the tree, and will always draw $T$ so that the root is on the left-hand side of the picture. Then, \textbf{left} will be used to mean `towards the root', and \textbf{right} will be used to mean `away from the root'. We say `the branch starting at edge $\mbf e$' to refer to the collection of all edges and vertices (including $\mbf e$ itself) on the opposite side of $\mbf e$ as the root.
	
	\begin{example}
		Consider the tree $T$ below on the left, and let $\mbf e$ be the bolded edge. Then, the branch starting at $\mbf e$ is the branch below on the right.
		\begin{center}
			\begin{tikzpicture}
			\draw (0,0)--(3,0);
			\draw[very thick] (1,0)--(2,0);
			\draw (1,0)--(1,-1);
			\draw (1,-1)--(0.5,-1.5);
			\draw (1,-1)--(1.5,-1.5);
			\draw (2,0)--(2,-0.6);
			\draw (3,0)--(3.5,0.5);
			\draw (3,0)--(3.5,-0.5);
			\draw (0,0)--(-0.5,0.5);
			\draw (0,0)--(-0.5,-0.5);
			
			\node[anchor=south east] at (-0.5,0.5) {$a$};
			\node[anchor=north east] at (-0.5,-0.5) {$b$};
			\node[anchor=north east] at (0.5,-1.5) {$c$};
			\node[anchor=north west] at (1.5,-1.5) {$1$};
			\node[anchor=north] at (2,-0.6) {$2$};
			\node[anchor=south west] at (3.5,0.5) {$4$};
			\node[anchor=north west] at (3.5,-0.5) {$3$};
			\end{tikzpicture}
			\hspace{2cm}
			\begin{tikzpicture}
			\draw (1,0)--(3,0);
			\draw[very thick] (1,0)--(2,0);
			\draw (2,0)--(2,-0.6);
			\draw (3,0)--(3.5,0.5);
			\draw (3,0)--(3.5,-0.5);
			
			\node[anchor=north] at (2,-0.6) {$2$};
			\node[anchor=south west] at (3.5,0.5) {$4$};
			\node[anchor=north west] at (3.5,-0.5) {$3$};
			\node[white,anchor=north east] at (0.5,-1.5) {$c$};
			\node[white,anchor=north west] at (1.5,-1.5) {$1$};
			\end{tikzpicture}
		\end{center}
		\label{ex:branch}
	\end{example}
	
	Similarly, we can consider the maximal branch that contains some leaf $j$ but not some other leaf $i$. For example, in \Cref{ex:branch} above, the branch $B$ on the right is the maximal branch of $T$ that contains $3$, but not $1$, since adding any additional edges to $B$ would necessarily add the edge to the left of $\mbf e$, which would also add the leaves c and 1.
	
	
	\subsection{Pattern Avoidance}
	\label{sec:patterns}
	
	In this section, we define the variants of pattern avoidance that are used in this paper. For a summary of classical pattern avoidance, we refer the reader to \cite{bevanPPdefs}.  We first extend the ideas of classical pattern avoidance to where neither our word $\sigma$ nor our pattern $\tau$ are permutations. We denote the set of words with content $\kUnd$ that avoid a pattern or collection of patterns $\tau$ by $\Av_{\kUnd}(\tau)$.
	
	\begin{example}
		The word %$2\underline{466}53\underline{4}7$ contains $1221$. 
		$\sigma=24665347$ contains the pattern $\tau=1221$, since it contains the subword $4664$, which has the same relative order as $1221$. See \Cref{fig:permutations}.
	\end{example}
	
	Next, we define barred patterns. 
	
	\begin{definition}
		Let $\tau$ be a word where some letters are barred and others are unbarred. We call $\tau$ a \textbf{barred pattern}. We say that $\sigma$ \textbf{contains} $\tau$ if $\sigma$ has a subword with the same relative order as the non-barred letters of $\tau$ that does \textit{not} extend to a subword with the same relative order as all of $\tau$. Otherwise, $\sigma$ \textbf{avoids} $\tau$. 
		\label{def:barred}
	\end{definition}
	
	\begin{example}
		The word $\sigma=231456$ contains the barred pattern $\tau=23\overline{1}$. Although the length-2 subword $45$ of 231456 has the same relative order as $23$, it does not extend to a subword with relative order $231$.
		On the other hand, $\sigma=234561$ avoids the barred pattern $\tau=23\overline{1}$, since any subword with relative order $23$ can be extended, by adding the letter $1$ at the end, to a subword with relative order $231$. See \Cref{fig:permutations}.
	\end{example}
	
	Finally, we may also impose adjacency conditions on some entries of our pattern. Such patterns are called \textit{vincular} patterns.
	
	\begin{figure}[b]
		\centering
		\begin{tikzpicture}[scale=0.2, baseline=-\the\dimexpr\fontdimen22\textfont2\relax]
		\draw (0,0)--(10,0)--(10,9)--(0,9)--(0,0);
		\fill[black] (1.5,2.5) circle (0.25cm);
		\fill[black] (2.5,4.5) circle (0.25cm);
		\fill[black] (3.5,6.5) circle (0.25cm);
		\fill[black] (4.5,6.5) circle (0.25cm);
		\fill[black] (5.5,5.5) circle (0.25cm);
		\fill[black] (6.5,3.5) circle (0.25cm);
		\fill[black] (7.5,4.5) circle (0.25cm);
		\fill[black] (8.5,7.5) circle (0.25cm);
		\draw (2.5,4.5) circle (0.5cm);
		\draw (3.5,6.5) circle (0.5cm);
		\draw (4.5,6.5) circle (0.5cm);
		\draw (7.5,4.5) circle (0.5cm);
		\end{tikzpicture}
		\hspace{2cm}
		\begin{tikzpicture}[scale=0.2, baseline=-\the\dimexpr\fontdimen22\textfont2\relax]
		\draw (0,0)--(8,0)--(8,8)--(0,8)--(0,0);
		\fill[black] (1.5,2.5) circle (0.25cm);
		\fill[black] (2.5,3.5) circle (0.25cm);
		\fill[black] (3.5,1.5) circle (0.25cm);
		\fill[black] (4.5,4.5) circle (0.25cm);
		\fill[black] (5.5,5.5) circle (0.25cm);
		\fill[black] (6.5,6.5) circle (0.25cm);
		\end{tikzpicture}%\\[5pt]
		\hspace{1cm}
		\begin{tikzpicture}[scale=0.2, baseline=-\the\dimexpr\fontdimen22\textfont2\relax]
		\draw (0,0)--(8,0)--(8,8)--(0,8)--(0,0);
		\fill[black] (1.5,2.5) circle (0.25cm);
		\fill[black] (2.5,3.5) circle (0.25cm);
		\fill[black] (3.5,4.5) circle (0.25cm);
		\fill[black] (4.5,5.5) circle (0.25cm);
		\fill[black] (5.5,6.5) circle (0.25cm);
		\fill[black] (6.5,1.5) circle (0.25cm);
		\end{tikzpicture}
		\hspace{2cm}
		\begin{tikzpicture}[scale=0.2, baseline=-\the\dimexpr\fontdimen22\textfont2\relax]
		\draw (0,0)--(7,0)--(7,7)--(0,7)--(0,0);
		\fill[black] (1.5,3.5) circle (0.25cm);
		\fill[black] (2.5,2.5) circle (0.25cm);
		\fill[black] (3.5,5.5) circle (0.25cm);
		\fill[black] (4.5,4.5) circle (0.25cm);
		\fill[black] (5.5,1.5) circle (0.25cm);
		
		\draw (2.5,2.5) circle (0.5cm);
		\draw (3.5,5.5) circle (0.5cm);
		\draw (5.5,1.5) circle (0.5cm);
		\end{tikzpicture}%\\[5pt]
		\hspace{1cm}
		\begin{tikzpicture}[scale=0.2, baseline=-\the\dimexpr\fontdimen22\textfont2\relax]
		\draw (0,0)--(7,0)--(7,7)--(0,7)--(0,0);
		\fill[black] (1.5,4.5) circle (0.25cm);
		\fill[black] (2.5,3.5) circle (0.25cm);
		\fill[black] (3.5,1.5) circle (0.25cm);
		\fill[black] (4.5,5.5) circle (0.25cm);
		\fill[black] (5.5,2.5) circle (0.25cm);
		\end{tikzpicture}
		\caption{On the left, a word containing $1221$; in the middle, two permutations containing and avoiding $23\overline{1}$, respectively; on the right, two permutations containing and avoiding $23{-}1$, respectively.}
		\label{fig:permutations}
	\end{figure}
	
	\begin{definition}
		Let $\tau$ be a word of length $k$ with dashes between some entries. We call $\tau$ a \textbf{vincular pattern}. A word $\sigma$  \textbf{contains} $\tau$ if $\sigma$ contains a subword $\sigma'$ that has the same relative order as $\tau$, and for each $i\in[k-1]$, if the en entries $\tau_i,\tau_{i+1}$ in $\tau$ are not separated by a dash, then $\sigma'_i$ and $\sigma'_{i+1}$ come from adjacent entries $\sigma_j,\sigma_{j+1}$ in $\sigma$. Otherwise, we say $\sigma$ \textbf{avoids} the vincular pattern $\tau$.
		\label{def:vincular}
	\end{definition}
	
	In other words, to contain  a vincular pattern, we must have a consecutive subword with the relative order of the pattern, except that the dashes in the pattern indicate entries that need not come from consecutive letters of our word.
	
	\begin{example}
		The word %$\sigma=3\underline{25}4\underline{1}$ contains $\tau=23{-}1$:
		$\sigma=32541$ contains the pattern $\tau=23{-}1$, since it contains the subword $251$, where the 2 and 5 are adjacent, and 251 has the relative order 231.	
		
		On the other hand, although $\sigma=43152$ contains the classical pattern $\tau=231$ (consider the subword $352$), $\sigma$ avoids the vincular pattern $\tau=23{-}1$, since the 3 and 5 in $352$ (as well as the 4 and 5 of 452) are not adjacent.  See \Cref{fig:permutations}.
	\end{example}
	
	\section{The insertion algorithms}
	\label{sec:bijection}
	
	
	In this section, we now answer Problem  6.1 from \cite{GGL22}.
	We do so by showing that $\Slwk$ satisfies the same recursion as the asymmetric multinomial coefficients $\asymbinom{n}{\kUnd}$.
	This recurrence relation is given in Equation \ref{eq:recursion} and is discussed in more detail in \cite{CGM}. 
	
	
	\subsection{Preliminaries}
	
	Our insertion algorithms rely on a map $\last(T)$, which we now define.
	
	
	\begin{definition}
		For $\kUnd$ a composition of $n$, define $\maxzero(\kUnd)$ to be the largest $z\in[n]$ such that $k_z=0$. If $\kUnd=(1,1,\ldots,1)$, set $\maxzero(1,1,\ldots,1)=c$ or $\maxzero(1,1,\ldots,1)=0$ as appropriate.
		\label{def:maxzero}
	\end{definition}
	
	\begin{definition}
		Let $T\in\Slwk$, and $B$ be a branch of $T$. Let $i$ and $j$ be the smallest and second smallest leaves of $B$, respectively.  Then, define $\mintwo(B)$ to be the largest branch of $B$ containing $j$ but not $i$.
	\end{definition}
	
	
	\begin{definition}
		Define $\last:\Slwk\to[n]$ as follows:
		\begin{enumerate}[nosep]%[topsep=4pt,itemsep=0pt]
			\item For a given $T\in\Slwk$, let $B$ be the largest branch of $T$ that has $\maxzero(\kUnd)$ as its smallest leaf.
			\item If $B$ has at least two leaves, replace $B$ with $\mintwo(B)$.
			\item Repeat Step 2 until $B$ has a single leaf.
			\item Define $\last(T)$ to be the unique leaf of $B$.
		\end{enumerate}
		\label{def:last}
	\end{definition}
	
	
	\begin{lemma}
		For any $T\in\Slwk$, $\last(T)\gneq\maxzero(\kUnd)$.
		\label{lem:larger_than_zero}
	\end{lemma}
	
	\begin{lemma}
		The map $\last(T)$ returns a leaf $j$ adjacent to another leaf $i$ with $j>i$.
		\label{lem:largeleaf}
	\end{lemma}
	
	
	\subsection{The map \texorpdfstring{$\sigmaT_{i,j}$}{\sigmaT\_i,j}}
	
	In this and the following section, we define the two maps $\sigmaT_{i,j}$ and $\sigmaT_{j}$. 
	These maps take a slide tree $T$ and add an additional edge $j$ to create a larger slide tree. The map $\sigmaT_j$ corresponds to the case in Equation \ref{eq:recursion} where we delete a 1 in position $j$ of $\kUnd$, and $\sigmaT_{i,j}$ corresponds to the case where we subtract 1 from an entry greater than 1 in position $j$, and delete the rightmost zero in position $i<j$. We will also show that $\last(\sigmaT_\bullet(T))$ will always return the label of the edge added to $T$ by $\sigmaT_\bullet$. 
	
	\begin{definition}
		Let $\kUnd$ be a reverse-Catalan composition of $n$, $j$ and $i$ be integers such that $\maxzero(\kUnd)<i<j\leq n+1$, and $\kUnd'$ be the composition of $n+1$ obtained from $\kUnd$ by inserting a zero between $k_{i-1}$ and $k_i$, and then increasing the $j$th entry of the result by 1. Note that using the notation from Equation \ref{eq:recursion}, $\kUnd=\kUnd'^{(j)}$. We define the map $\sigmaT_{i,j}: \Slwk\to\Slide^\omega(\kUnd')$ as follows:
		\begin{enumerate}[nosep]%[topsep=4pt,itemsep=0pt]
			\item Given a tree $T\in\Slwk$, add 1 to all leaf (and edge) labels greater than or equal to $i$.
			\item On the path from $a$ to %the leaf 
			$j$, consider the maximal length decreasing sequences of edge labels. 
			\item Let $B_1,B_2,\ldots,B_l$ be the branches of $T$ off of this path that lie between these maximal length decreasing sequences, and $B_l$ the branch immediately next to leaf $j$. %(See \Cref{fig:sigmaEx} for an example.) 
			Note that some (or all) of these branches may consist of a single leaf, and there may be additional branches that connect to this path in the middle of a decreasing sequence.
			\item For $r\in[l]$, let $m_r$ be the minimal leaf of $B_r$.
			\item There are three possible cases for the relative ordering of $m_1,\ldots,m_l$, $i$, and $j$. For each case, we say how to get $\sigmaT_{i,j}(T)$:
			\begin{itemize}[topsep=4pt,itemsep=0pt]
				\item $m_l<i<j$ \textit{or} $m_{l-1}<i<j<m_l$: Replace the leaf $j$ by an edge labeled $\mbf{j}$ with leaves $j$ and $i$.
				\item $m_1<\cdots<m_{d-1}<i<m_d<\cdots<m_l<j$: Replace the leaf $m_d$ by $i$, $m_{d+1}$ by $m_d$, and so on, replace $m_l$ by $m_{l-1}$, and replace leaf $j$ by an edge $\mbf{j}$ with leaves $j$ and $m_l$.
				\item $m_1<\cdots<m_{d-1}<i<m_d<\cdots<j<m_l$: Replace the leaf $m_d$ by $i$, $m_{d+1}$ by $m_d$, and so on up to replacing $m_{l-1}$ with $m_{l-2}$, then replace leaf $j$ by an edge $\mbf{j}$ with leaves $j$ and $m_{l-1}$.
			\end{itemize}
			Note that the first case is actually subsumed by the second two cases, but we write it out separately for clarity.% and to make the proofs clearer.
		\end{enumerate}
		\label{def:sigmaIJ}
	\end{definition}
	
	\begin{example}
		We compute $\sigmaT_{3,7}(T)$, where $T\in\Slide^\omega(1,0,1,1,1,1,1,1,2,1,1,1,1)$ is the tree below on the left.
		The figure depicts $T$ after already incrementing by 1 all the leaf and edge labels greater than or equal to 3. Then, the maximal decreasing sequences of edge labels from $a$ to $7$ are $(14,5)$, $(6)$, $(13,10,7)$, and $(11,8)$. So, $l=4$ and the branches $B_1,B_2,B_3, B_4$ are as depicted. Their minimal leaves are $m_1=c$, $m_2=2$, $m_3=5$, and $m_4=8$. We have $c<2<(i=3)<5<(j=7)<8$, so $d=3$ and we are in the third case of step 5. Thus, we replace $5$ with $3$ and $7$ with an edge $\mbf{7}$ with leaves $7$ and $5$ to form $\sigmaT_{3,7}(T)\in \Slide^\omega(1,0,0,1,1,1,2,1,1,2,1,1,1,1)$ below on the right.
		\begin{center}
			\includegraphics[scale=.7]{SigmaExample.pdf}
			\hfil
			\includegraphics[scale=.7]{SigmaExDone.pdf}
		\end{center}
	\end{example}
	
	
	
	\begin{theorem}
		The map $\sigmaT_{i,j}$ is an injection.
	\end{theorem}
	
	
	Since $\sigmaT_{i,j}$ is an injection, there exists an inverse map $\piT_{i,j}$ from the image of $\sigmaT_{i,j}$ back to $\Slwk$. We do not define $\piT_{i,j}$ here for the sake of brevity, but refer the reader to \cite{RB} for the definition.
	
	
	\subsection{The map \texorpdfstring{$\sigmaT_{j}$}{\sigmaT\_j}}
	
	In this subsection, we define the other map from $\Slwk$ into $\Slide^\omega(\kUnd')$, along with its inverse. This one corresponds to the case in the asymmetric multinomial recursion where we decrement a 1 in position $j$, thus removing the 0 that then appears in that position.
	
	\begin{definition}
		Let $\kUnd$ be a reverse-Catalan composition of $n$, $j \in \mathbb{N}$ such that $\maxzero(\kUnd)<j\leq n+1$, and $\kUnd'$ be the composition of $n+1$ obtained from $\kUnd$ by inserting a 1 between $k_{j-1}$ and $k_j$. We define the map $\sigmaT_{j}: \Slwk\to\Slide^\omega(\kUnd')$ as follows:
		\begin{enumerate}[nosep]%[topsep=4pt,itemsep=0pt]
			\item Given a tree $T\in\Slwk$, add 1 to all leaf (and edge) labels greater than or equal to $j$.
			\item Consider the leaf $v=\last(T)$. By \Cref{lem:largeleaf}, it is at the end of an edge, adjacent to some other leaf $i<v$. There are three cases to  consider:
			\begin{itemize}[topsep=4pt,itemsep=0pt]
				\item $v<j$: Replace the leaf $v$ by an edge $\mbf{j}$ with leaves $j$ and $v$. The result is $\sigmaT_j(T)$.
				\item $i<j<v$: Replace the leaf $i$ by an edge labeled $\mbf{j}$ with leaves $j$ and $i$. The result is $\sigmaT_j(T)$.
				\item $j<i$: Continue on to step 3.
			\end{itemize}
			\item On the path from $a$ to $v$, consider the maximal length decreasing sequences of edge labels. 
			\item Let $B_1,B_2,\ldots,B_l$ be the branches away from this path between the maximal decreasing sequences, with $B_l$ the branch immediately next to leaf $v$.
			\item For $r\in[l]$, let $m_r$ be the minimal leaf of $B_r$.
			\item It can be shown that $c=m_1<m_2<\cdots<m_l$. Let $d$ be such that $m_{d}<j<m_{d+1}$.
			\item Replace the leaf $m_d$ by an edge $\mbf{j}$ with leaves $j$ and $m_d$. The result is $\sigmaT_{j}(T)$.
		\end{enumerate}
		\label{def:sigmaJ}
	\end{definition}
	
	\begin{example}
		Let $T\in\Slide^\omega(0,2,0,1,2,1)$ be the tree below on the left. We compute $\sigmaT_5(T)$. Since $\last(T)=6$, and $5<6$, we are in the third case of Step 2. Then, $l=5$, with $m_1=c$, $m_2=1$, $m_3=3$, $m_4=4$, and $m_4=6$ (Since we increment all labels that are at least 5). 
		Since $5$ is between 4 and 6, we attach an edge $\mbf5$ and leaf 5 to the leaf 4 to get the tree below on the right.
		\begin{center}
			\includegraphics{SigmajEx1.pdf}
			\hspace{1.25cm}
			\includegraphics{SigmajExDone.pdf}
		\end{center}
	\end{example}
	
	\begin{theorem}
		The map $\sigmaT_j$ is an injection.
	\end{theorem}
	
	
	Similarly to $\piT_{i,j}$, since $\sigmaT_j$ is an injection, there is also has an inverse map $\piT_j$ from the image of $\sigmaT_j$ back to $\Slwk$. Again, we do not define $\piT_{i,j}$ here, but refer the reader to \cite{RB} for its definition. 
	
	
	\subsection{Constructing the full bijection}
	
	So far, we have defined two maps $\sigmaT_{i,j}$ and $\sigmaT_{j}$. For any tree in their image, the function $\last()$ returns the value of the added edge:
	
	\begin{theorem}
		Let $T\in \Slwk$. If $T\in\sigmaT_{i,j}(\Slide^\omega(\kUnd'))$ or $T\in\sigmaT_{j}(\Slide^\omega(\kUnd'))$ for some $\kUnd'$, then $\last(T)=j$.
		\label{thm:lastadded}
	\end{theorem}
	
	We combine the maps $\sigmaT_{i,j}$ and $\sigmaT_{j}$ to construct a bijection between a disjoint union of slide sets for certain compositions of $n-1$ and $\Slwk$.
	Let $\kUnd$ be a composition of $n$ and $i=\maxzero(\kUnd)$. Then, define $$D^\omega(\kUnd):=\bigsqcup_{j=i+1}^n\Slide^\omega(\kUnd^{(j)}).$$
	We then define  $\Sigma_{\kUnd}:D^\omega(\kUnd)\to\Slwk$ by: $$\Sigma_{\kUnd}(T):=\begin{cases}\sigmaT_{i,j}(T) & \text{if }T\in\Slide^\omega(\kUnd^{(j)})\text{ with }k_j>1\\ \sigmaT_j(T) & \text{if }T\in\Slide^\omega(\kUnd^{(j)})\text{ with }k_j=1 \end{cases}.$$
	
	\begin{theorem}
		The map $\Sigma_{\kUnd}$ is a bijection.
	\end{theorem}
	
	
	
	This shows combinatorially that $\Slwk$ and $\asymbinom{n}{\kUnd}$ satisfy the same recurrence. Since $\Tour(\kUnd)$ satisfies this recurrence \cite{GGL23}, we get a bijection between $\Tour(\kUnd)$ and $\Slwk$ by unwinding this recurrence iteratively.
	
	\begin{bijectionExists}
		There is a combinatorial bijection between the sets $\Tour(\kUnd)$ and $\Slwk$.
	\end{bijectionExists}
	
	
	
	
	\section{Caterpillars}
	\label{sec:cats}
	
	Recall that a \textbf{caterpillar tree} is a trivalent tree whose edges form a path, as in \Cref{ex:slides}. 	The \textbf{word} of a caterpillar tree is formed by reading its slide labels from left to right.	Given a word $w$ of content $\kUnd$, there is at most one caterpillar $T\in\Cat^\psi(\kUnd)$ whose edges read off as $w$. 
	In \cite{RB}, we define a map $\tree(w)$ that, given a word, will return the caterpillar tree whose edge word is $w$, if such a tree exists.
	
	\begin{lemma}
		When $w\in\Av_{\kUnd}(2{-}1{-}2)$, $\tree(w)$  uses each leaf label $a,b,c,1,2,\ldots,n$ exactly once.
	\end{lemma}
	
	In other words, $\tree(w)$ is well-defined as a map from $\Av_{\kUnd}(2{-}1{-}2)$ to the set of leaf-labeled trivalent caterpillar trees using the labels $a,b,c,1, 2,\ldots,n$. 	If a word $w$ avoids the pattern $23{-}\overline{2}{-}1$, then whenever there are indices $i,j$ such that $i+1<j$ and $w_j<w_i<w_{i+1}$, there must be some index $k$ with $i+1<k<j$ such that $w_k=w_i$.
	
	\begin{lemma}
		Let $\tree(w)\in\Cat^\psi(\kUnd)$. Then, the word $w$ avoids the patterns $2{-}1{-}2$ and $23{-}\overline{2}{-}1$.
		\label{lem:avoids}
	\end{lemma}
	
	
	\subsection{Pattern avoidance results}
	\label{subsec:right-justified}
	In \cite{GGL22}, Gillespie, Griffin, and Levinson have shown that the set of caterpillar trees in $\Slide^\omega(1,1,\ldots,1)$ correspond precisely to the set of $23{-}1$ avoiding permutations. We give an analogous statement in the general case where $\kUnd\neq(1,1,\ldots,1)$, both for $\Slwk$ and for $\Slpk$. When $\kUnd$ is \textit{right-justified}, that is, when all entries of 0 precede all non-zero entries, this characterization can still be given in purely pattern avoidance terms.
	
	\begin{rjust}
		Let $\kUnd$ be a right-justified composition of $n$. Then, $\tree(w)$ is a valid slide tree if and only if $w\in\Av_{\kUnd}(2{-}1{-}2,\ 23{-}\overline{2}{-}1)$. 
	\end{rjust}
	
	
	\begin{example}
		The word $546643$, corresponding to the caterpillar tree in \Cref{ex:slides}, avoids the patterns $2{-}1{-}2$ and $23{-}\overline{2}{-}1$. The words $543664$ and $546633$, however, contain $2{-}1{-}2$ and $23{-}\overline{2}{-}1$, respectively.
	\end{example}
	
	For the non-right-justified case, define $z(i)$ to be the number of $j>i$ such that $k_j=0$.   Define $\ell_w(i)$ to be the total number of consecutive $i$'s in the rightmost consecutive sequence of $i$'s in $w$.  Define $\TRep_w(i)$ to be the total number of ``repeats'' right of the rightmost $i$, where a ``repeat'' is an extra instance of a given letter beyond the first occurrence (to the right of the $i$).  Similarly define $\rep_w(i)$ to be the number of repeats defined for $\TRep_w(i)$ that are larger than $i$. 
	
	
	\begin{psiAvoidance}
		Let $\kUnd$ be a reverse-Catalan composition of $n$, and let $w$ be a word of content $\kUnd$. Then, $\tree(w)\in\Cat^\psi (\kUnd)$ (respectively, $\tree(w)\in\Cat^\omega (\kUnd)$) if and only if $w\in\Av_{\kUnd}(2{-}1{-}2, 23{-}\overline{2}{-}1)$ and $\TRep_w(i)+\ell_w(i)\geq \z(i)$ for all $i$ (respectively, $\rep_w(i)\geq \z(i)$ for all $i$).
	\end{psiAvoidance}
	
	% \begin{omegaAvoidance}
	% 	Let $\kUnd$ be a reverse-Catalan composition, and let $w$ be a word of content $\kUnd$. Then, $\tree(w)\in\Cat^\omega (\kUnd)$ if and only if $w\in\Av_{\kUnd}(2{-}1{-}2,\ 23{-}\overline{2}{-}1)$ and $\rep_w(i)\geq \z(i)$ for all $i$.
	% \end{omegaAvoidance}
	
	\begin{example}
		The word $135366$ corresponds to a tree in $\Cat^\omega(1,0,2,0,1,2)$. The word $436632$ corresponds to a tree in $\Cat^\psi(0,1,2,1,0,2)\setminus\Cat^\omega(0,1,2,1,0,2)$, while $436631$ does not correspond to any caterpillar tree, since $\TRep_{436631}(1)=0$, $\ell_{436631}(1)=1$, and $z(1)=2$. Note that both $436632$ and $436631$ have the same relative ordering as $546643$ above.
	\end{example}
	
	
	
	\acknowledgements{We thank Maria Gillespie for her mentorship, and thank
		Vance Blankers, Renzo Cavalieri, Sean Griffin, Matt Larson, and Jake Levinson for their helpful conversations.}
	
	%% 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}
