%% 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[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

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

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{question}[theorem]{Question}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
%%
%\usepackage{todonotes}
%\usepackage{lipsum}
\usepackage{tikz}
	\usetikzlibrary{intersections}
	\usetikzlibrary{calc}
	\tikzstyle{fnode}=[fill=black,draw=black,circle,scale=\s]
	\tikzstyle{edge}=[black,thick,rounded corners]
	\tikzstyle{back}=[black,very thick,dashed]
	\def\ss{\scriptstyle}
	\def\rd{\textcolor{red}}
	\def\bl{\textcolor{blue}}
	\pgfdeclarelayer{background}
	\pgfsetlayers{background,main}
\usepackage{subcaption}
	\captionsetup{labelfont=rm}
% \usepackage[pagebackref,colorlinks=true,
% 	urlcolor=blue!20!black,
% 	citecolor=green!50!black]{hyperref}
% % \usepackage[nobysame]{amsrefs}

%%
\newcommand{\henri}[1]{\todo[size=\tiny,color=green!30]{#1 \\ \hfill --- H.}}
\newcommand{\thomas}[1]{\todo[size=\tiny,color=red!30]{#1 \\ \hfill --- T.}}
\newcommand{\defn}[1]{{\color{green!50!black}\emph{#1}}}
\newcommand{\ie}{\textit{i.e.}}
\newcommand{\defs}{\overset{\mathsf{def}}{=}}
%%
\newcommand{\bubcov}{\lessdot_{\mathsf{bub}}}
\newcommand{\bubless}{<_{\mathsf{bub}}}
\newcommand{\bubleq}{\leq_{\mathsf{bub}}}
\newcommand{\indel}{\rightarrow}
\newcommand{\shufless}{<_{\mathsf{shuf}}}
\newcommand{\shufleq}{\leq_{\mathsf{shuf}}}
\newcommand{\compleq}{\leq_{\mathsf{comp}}}
\newcommand{\compcov}{\lessdot_{\mathsf{comp}}}
\newcommand{\sindel}{\hookrightarrow}
\newcommand{\transpose}{\Rightarrow}
\newcommand{\lnk}{\mathsf{lk}}
\newcommand{\dlt}{\mathsf{del}}

%\newcommand{\add}[1]{{\color{orange!80!black}#1}}

\newcommand{\ncm}[3]{
	%Parameter 1: scaling
	%Parameter 2: marked circles
	%Parameter 3: edges
	\begin{tikzpicture}
		\def\dx{#1};
		%%
		\filldraw[fill=white,draw=black](0*\dx,0*\dx) -- (1*\dx,2*\dx) -- (2*\dx,0*\dx) -- (0*\dx,0*\dx);
		%%
		\coordinate (r1) at (.5*\dx,.33*\dx);
		\coordinate (r2) at (1.5*\dx,.33*\dx);
		\coordinate (r3) at (1*\dx,1.33*\dx);
		%%
		\draw(r1) node[circle,draw=red,scale=7*\dx]{};
		\draw(r2) node[circle,draw=red,scale=7*\dx]{};
		\draw(r3) node[circle,draw=blue,scale=7*\dx]{};
		%%draw edges
		\foreach \a/\b in {#3}{
			\draw[edge](r\a) -- (r\b);
		}
		%%fill selected vertices
		\foreach \a in {#2}{
			\ifthenelse{\equal{\a}{3}}{
				\draw(r3) node[circle,fill=blue,scale=7*\dx]{};
			}{
				\draw(r\a) node[circle,fill=red,scale=7*\dx]{};
			}
		}
	\end{tikzpicture}
}
\newcommand{\ncb}[3]{
	%Parameter 1: scaling
	%Parameter 2: marked circles
	%Parameter 3: edges
	\begin{tikzpicture}
		\def\dx{#1};
		%%
		\filldraw[fill=white,draw=black](0*\dx,0*\dx) -- (.85*\dx,1.67*\dx) -- (2.15*\dx,1.67*\dx) -- (3*\dx,0*\dx) -- (0*\dx,0*\dx);
		%%
		\coordinate (r1) at (.5*\dx,.33*\dx);
		\coordinate (r2) at (1.5*\dx,.33*\dx);
		\coordinate (r3) at (2.5*\dx,.33*\dx);
		\coordinate (r4) at (1*\dx,1.33*\dx);
		\coordinate (r5) at (2*\dx,1.33*\dx);
		%%
		\draw(r1) node[circle,draw=red,scale=7*\dx]{};
		\draw(r2) node[circle,draw=red,scale=7*\dx]{};
		\draw(r3) node[circle,draw=red,scale=7*\dx]{};
		\draw(r4) node[circle,draw=blue,scale=7*\dx]{};
		\draw(r5) node[circle,draw=blue,scale=7*\dx]{};
		%%draw edges
		\foreach \a/\b in {#3}{
			\draw[edge](r\a) -- (r\b);
		}
		%%fill selected vertices
		\foreach \a in {#2}{
			\ifthenelse{\equal{\a}{4} \OR \equal{\a}{5}}{
				\draw(r\a) node[circle,fill=blue,scale=7*\dx]{};
			}{
				\draw(r\a) node[circle,fill=red,scale=7*\dx]{};
			}
		}
	\end{tikzpicture}
}

%%words
\def\abf{\mathbf{a}}\def\bbf{\mathbf{b}}\def\cbf{\mathbf{c}}\def\rbf{\mathbf{r}}\def\sbf{\mathbf{s}}\def\ubf{\mathbf{u}}\def\vbf{\mathbf{v}}\def\wbf{\mathbf{w}}\def\xbf{\mathbf{x}}\def\ybf{\mathbf{y}}\def\zbf{\mathbf{z}}
\def\Acal{\mathcal{A}}\def\Bcal{\mathcal{B}}\def\Ecal{\mathcal{E}}\def\Fcal{\mathcal{F}}\def\Gcal{\mathcal{G}}\def\Lcal{\mathcal{L}}\def\Ocal{\mathcal{O}}\def\Scal{\mathcal{S}}\def\Tcal{\mathcal{T}}\def\Ucal{\mathcal{U}}\def\Vcal{\mathcal{V}}
\def\hookra{\hookrightarrow}\def\pr{\prime}\def\ra{\rightarrow}\def\setm{\setminus}\def\wtil{\widetilde}
%%
\newcommand{\invset}{\mathsf{Inv}}
\newcommand{\Shuf}{\mathsf{Shuf}}
\newcommand{\Tri}{\mathsf{Tri}}
\newcommand{\ShufPoset}{\textbf{\textsf{Shuf}}}
\newcommand{\Bub}{\textsf{\textbf{Bub}}}
\newcommand{\Hoch}{\textbf{\textsf{Hoch}}}
\newcommand{\indeg}{\mathsf{in}}
\newcommand{\indeld}{\mathsf{in_{\sindel}}}
\newcommand{\transd}{\mathsf{in_{\transpose}}}
%%
%% define your title in the usual way
\title{Shuffle Lattices and Bubble Lattices}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[T.~McConville and H.~M\"uhle]{Thomas McConville\thanks{\href{mailto:tmcconvi@kennesaw.edu}{tmcconvi@kennesaw.edu}}\addressmark{1} \and Henri M{\"u}hle\thanks{\href{mailto:henri.muehle@tu-dresden.de}{henri.muehle@tu-dresden.de}. Received funding from the European Research Council (Grant Agreement no. 681988, CSP-Infinity.)}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Kennesaw State University, 30144 Kennesaw (GA), USA\\ \addressmark{2}Technische Universit{\"a}t Dresden, 01062 Dresden, Germany}

%% 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{C.~Greene introduced the shuffle lattice as an idealized model for DNA mutation and discovered remarkable combinatorial and enumerative properties of these structures. In this article we attempt an explanation of these properties from a lattice-theoretic point of view.  To that end, we introduce and study an order extension of the shuffle lattice, the \emph{bubble lattice}.  Intriguingly, most of the combinatorics of the bubble lattice can be encoded by means of two simplicial complexes, the \emph{noncrossing matching complex} and the \emph{noncrossing bipartite complex}.  We present an intriguing relationship between the $f$-vectors of these complexes and relate it to the rank-generating function of the shuffle lattice.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{shuffle words, insertion, deletion, transposition, noncrossing graphs}

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

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{bib_shuffle_fpsac.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

% \henri{Please check your contact information.}

\section{Introduction}

Motivated by an idealized model for mutations in DNA sequences, C.~Greene introduced the \emph{shuffle lattice}.  The ground set of this lattice is the set $\Shuf(m,n)$ of shuffles of order-preserving repetition-free words whose letters are taken from two disjoint, linearly ordered alphabets $X=\{x_{1},x_{2},\ldots,x_{m}\}$ and $Y=\{y_{1},y_{2},\ldots,y_{n}\}$.  The \emph{shuffle order} is determined by inserting letters of $Y$ or deleting letters of $X$ from any given word. In~\cite{greene:shuffle}, Greene studied this poset extensively and discovered several surprising enumerative relationships among its characteristic polynomial, its zeta polynomial and its rank-generating function.  Namely, each of these invariants occurs as a specialization of the same Jacobi polynomial. Greene's enumerative results were recovered in \cite{simion_stanley:shuffle} using algebraic methods, but the presence of the Jacobi polynomials remained mysterious.

In this abstract we seek to explain the enumerative relationships among the combinatorial invariants of the shuffle lattice using combinatorial lattice theory.  We introduce an alternate partial ordering on the set $\Shuf(m,n)$, which we call the \emph{bubble order}.  This is the extension of the shuffle order, where we also allow the exchange of adjacent letters from $X$ and $Y$.  The resulting \emph{bubble lattice} is indeed a lattice, and its combinatorial structure can be explained using two simplicial complexes: the \emph{noncrossing matching complex} and the \emph{noncrossing bipartite complex}.  In this abstract we state that the $f$-vectors of these simplicial complexes are related in an intriguing fashion and can be used to recover the rank-generating polynomial of the shuffle lattice.

This abstract is organized as follows: we start in Section~\ref{sec:preliminaries} with the recapitulation of the basic definitions as well as the formal introduction of the bubble lattice.  In Section~\ref{sec:covers}, we characterize the cover relation in the bubble lattice and introduce the noncrossing matching complex.  In Section~\ref{sec:lattice}, we sketch the proof that the bubble lattice is in fact a lattice and define the noncrossing bipartite complex.  In Section~\ref{sec:enumeration}, we conduct a refined face-enumeration in the noncrossing matching and noncrossing bipartite complex, and relate the resulting formulas to the rank-generating function of the shuffle lattice.  Due to the space limitations, we have most often omitted proofs of our statements, and refer the interested reader to the full version of this abstract~\cites{mcconville:bubbleI,mcconville:bubbleII}.

\section{Basics}
    \label{sec:preliminaries}
\subsection{Shuffle Words}

For nonnegative integers $m$ and $n$, we consider two disjoint sets of letters: 
\[
	X = \{x_{1},x_{2},\ldots,x_{m}\}\quad\text{and}\quad Y=\{y_{1},y_{2},\ldots,y_{n}\}.
\]
A word over the disjoint union $X\uplus Y$ is \defn{simple} if it does not contain duplicate letters. The \defn{support} of a word is the set of letters it contains.
The empty word is denoted by $\epsilon$ and we usually (at least in the examples) write the letters of $X$ in red and the letters of $Y$ in blue.

A \defn{subword} of a simple word $\wbf=w_{1}w_{2}\cdots w_{k}$ is any word of the form $w_{i_{1}}w_{i_{2}}\cdots w_{i_{\ell}}$ with $1\leq i_{1}<i_{2}<\cdots<i_{\ell}\leq k$.  For $i\in[k]\defs\{1,2,\ldots,k\}$ we write $\wbf_{\widehat{\imath}}$ for the subword of $\wbf$ obtained by deleting the letter $w_{i}$.  

If $\ubf,\vbf$ are simple words, then the \defn{restriction} of $\ubf$ to $\vbf$, denoted by $\ubf_{\vbf}$, is the subword of $\ubf$ formed by the common letters of $\ubf$ and $\vbf$.  For instance, if $\ubf=\rd{x_1}\bl{y_1}\rd{x_2x_3}\bl{y_3}$ and $\vbf=\rd{x_3}\bl{y_1}\rd{x_4}$, then the restriction of $\ubf$ to $\vbf$ is $\ubf_{\vbf} = \bl{y_1}\rd{x_3}$.

Our main interest lies in \emph{order-preserving} simple words.  That means, if we define 
\begin{displaymath}
	\xbf\defs x_{1}x_{2}\cdots x_{m}\quad\text{and}\quad\ybf\defs y_{1}y_{2}\cdots y_{n},
\end{displaymath}
then we consider the set of simple words $\wbf$ with the property that $\wbf_{\xbf}$ is a subword of $\xbf$ and $\wbf_{\ybf}$ is a subword of $\ybf$.  We call such words \defn{shuffle words}
% \henri{I'd prefer to use the term ``shuffle words'' rather than ``word shuffles''.  What do you think?} 
of $\xbf$ and $\ybf$, and we write $\Shuf(m,n)$ for the set of all shuffle words.  It is easy to see that the number of shuffle words depends only on the cardinalities of $X$ and $Y$, and not on the concrete elements of $X$ and $Y$.

\subsection{Operations on Shuffle Words}

Let $\ubf=u_{1}u_{2}\cdots u_{k}\in\Shuf(m,n)$.  Lemma~4.6 in \cite{greene:shuffle} states that $\ubf$ is uniquely determined by its \defn{interface}, \ie~the set of letters $x\in X$, $y\in Y$ for which there exists $i\in[k-1]$ such that $u_{i}=y$ and $u_{i+1}=x$, and its \defn{residue}, \ie~the letters of $\ubf$ which are not in the interface.  This motivates the following two operations on $\Shuf(m,n)$.  

An \defn{indel} is a relation $\ubf\indel\ubf_{\widehat{\imath}}$ if $u_{i}\in X$ or $\ubf_{\widehat{\imath}}\indel\ubf$ if $u_{i}\in Y$.  In other words, an indel of $\ubf$ is a shuffle word obtained from $\ubf$ by either \underline{in}serting a letter of $\ybf$ or \underline{del}eting a letter of $\xbf$.  A \defn{(forward) transposition} swaps two letters $u_{i}$ and $u_{i+1}$ if $u_{i}\in X$ and $u_{i+1}\in Y$.
In this situation, we write $\ubf\transpose\ubf'$, where $\ubf'=u_{1}u_{2}\cdots u_{i-1}u_{i+1}u_{i}u_{i+2}\cdots u_{k}$.  Drawing inspiration from the analogous situation for permutations, we define the \defn{inversion set} of $\ubf$ by
\begin{displaymath}
	\invset(\ubf) \defs \bigl\{(x_{s},y_{t})\mid\;\text{there exist}\;i<j\;\text{such that}\;u_{i}=y_{t}\;\text{and}\;u_{j}=x_{s}\bigr\}.
\end{displaymath}

Now we use indels and transpositions to define two partial orders on $\Shuf(m,n)$.  The \defn{shuffle order}, denoted by $\shufleq$, is the reflexive and transitive closure of indels, and the \defn{bubble order}, denoted by $\bubleq$, is the reflexive and transitive closure of indels and transpositions\footnote{The name ``bubble order'' is to emphasize that this is an order extension of the shuffle order in which we have to bubble sort the words before we can perform an indel.}.  We write $\ShufPoset(m,n)\defs\bigl(\Shuf(m,n),\shufleq\bigr)$ and $\Bub(m,n)\defs\bigl(\Shuf(m,n),\bubleq\bigr)$ for the corresponding partially ordered sets (\defn{posets}).  Figure~\ref{fig:shuffle_21} shows $\ShufPoset(2,1)$ and Figure~\ref{fig:bubble_21} shows $\Bub(2,1)$.  The poset $\ShufPoset(m,n)$ was intensively studied in \cite{greene:shuffle}, while the poset $\Bub(m,n)$ is new.  The main purpose of this abstract is to exhibit several remarkable structural and enumerative correspondences between these two posets and introduce some new combinatorial structures arising in the context of shuffle words.

\begin{figure}
	\centering
	\begin{subfigure}[t]{.45\textwidth}
		\centering
		\begin{tikzpicture}\small
			\def\x{1.5};
			\def\y{1.5};
			\def\s{1};
			%%
			\coordinate(n1) at (3*\x,1*\y);
			\coordinate(n2) at (1*\x,2*\y);
			\coordinate(n3) at (2*\x,2*\y);
			\coordinate(n4) at (3*\x,2*\y);
			\coordinate(n5) at (4*\x,2*\y);
			\coordinate(n6) at (5*\x,2*\y);
			\coordinate(n7) at (1*\x,3*\y);
			\coordinate(n8) at (2*\x,3*\y);
			\coordinate(n9) at (3*\x,3*\y);
			\coordinate(n10) at (4*\x,3*\y);
			\coordinate(n11) at (5*\x,3*\y);
			\coordinate(n12) at (3*\x,4*\y);
            %%
			\draw(n1) -- (n2);
			\draw(n1) -- (n3);
			\draw(n1) -- (n4);
			\draw(n1) -- (n5);
			\draw(n1) -- (n6);
			\draw(n2) -- (n8);
			\draw(n2) -- (n7);
			\draw(n2) -- (n9);
			\draw(n3) -- (n9);
			\draw(n3) -- (n10);
			\draw(n4) -- (n7);
			\draw(n4) -- (n11);
			\draw(n5) -- (n8);
			\draw(n5) -- (n10);
			\draw(n5) -- (n11);
			\draw(n6) -- (n9);
			\draw(n6) -- (n11);
			\draw(n7) -- (n12);
			\draw(n8) -- (n12);
			\draw(n9) -- (n12);
			\draw(n10) -- (n12);
			\draw(n11) -- (n12);
			%%
			\draw(n1) node[fill=white,scale=\s,inner sep=.5pt]{$\rd{x_1x_2}$};
			\draw(n2) node[fill=white,scale=\s,inner sep=.5pt]{$\rd{x_1}$};
			\draw(n3) node[fill=white,scale=\s,inner sep=.5pt]{$\rd{x_1x_2}\bl{y_1}$};
			\draw(n4) node[fill=white,scale=\s,inner sep=.5pt]{$\bl{y_1}\rd{x_1x_2}$};
			\draw(n5) node[fill=white,scale=\s,inner sep=.5pt]{$\rd{x_2}$};
			\draw(n6) node[fill=white,scale=\s,inner sep=.5pt]{$\rd{x_1}\bl{y_1}\rd{x_2}$};
			\draw(n7) node[fill=white,scale=\s,inner sep=.5pt]{$\bl{y_1}\rd{x_1}$};
			\draw(n8) node[fill=white,scale=\s,inner sep=.5pt]{$\epsilon$};
			\draw(n9) node[fill=white,scale=\s,inner sep=.5pt]{$\rd{x_1}\bl{y_1}$};
			\draw(n10) node[fill=white,scale=\s,inner sep=.5pt]{$\rd{x_2}\bl{y_1}$};
			\draw(n11) node[fill=white,scale=\s,inner sep=.5pt]{$\bl{y_1}\rd{x_2}$};
			\draw(n12) node[fill=white,scale=\s,inner sep=.5pt]{$\bl{y_1}$};
		\end{tikzpicture}
		\caption{The shuffle poset $\ShufPoset(2,1)$.}
		\label{fig:shuffle_21}
	\end{subfigure}
	\hspace*{1cm}
	\begin{subfigure}[t]{.45\textwidth}
		\centering
		\begin{tikzpicture}\small
			\def\x{1.25};
			\def\y{1};
			\def\s{1};
			%%
			\draw(3*\x,1*\y) node[scale=\s,inner sep=.5pt](n1){$\rd{x_1x_2}$};
			\draw(2*\x,2*\y) node[scale=\s,inner sep=.5pt](n2){$\rd{x_1x_2}\bl{y_1}$};
			\draw(2*\x,3*\y) node[scale=\s,inner sep=.5pt](n3){$\rd{x_1}\bl{y_1}\rd{x_2}$};
			\draw(3*\x,3*\y) node[scale=\s,inner sep=.5pt](n4){$\rd{x_1}$};
			\draw(7*\x,3*\y) node[scale=\s,inner sep=.5pt](n5){$\rd{x_2}$};
			\draw(2*\x,4*\y) node[scale=\s,inner sep=.5pt](n6){$\rd{x_1}\bl{y_1}$};
			\draw(4*\x,4*\y) node[scale=\s,inner sep=.5pt](n7){$\bl{y_1}\rd{x_1x_2}$};
			\draw(6*\x,4*\y) node[scale=\s,inner sep=.5pt](n8){$\rd{x_2}\bl{y_1}$};
			\draw(4*\x,5*\y) node[scale=\s,inner sep=.5pt](n9){$\bl{y_1}\rd{x_1}$};
			\draw(6*\x,5*\y) node[scale=\s,inner sep=.5pt](n10){$\bl{y_1}\rd{x_2}$};
			\draw(7*\x,5*\y) node[scale=\s,inner sep=.5pt](n11){$\epsilon$};
			\draw(6*\x,6*\y) node[scale=\s,inner sep=.5pt](n12){$\bl{y_1}$};
			%%
			\draw(n1) -- (n2);
			\draw(n1) -- (n4);
			\draw(n1) -- (n5);
			\draw(n2) -- (n3);
			\draw(n2) -- (n8);
			\draw(n3) -- (n6);
			\draw(n3) -- (n7);
			\draw(n4) -- (n6);
			\draw(n4) -- (n11);
			\draw(n5) -- (n8);
			\draw(n5) -- (n11);
			\draw(n6) -- (n9);
			\draw(n7) -- (n9);
			\draw(n7) -- (n10);
			\draw(n8) -- (n10);
			\draw(n9) -- (n12);
			\draw(n10) -- (n12);
			\draw(n11) -- (n12);
		\end{tikzpicture}
		\caption{The bubble poset $\Bub(2,1)$.}
		\label{fig:bubble_21}
	\end{subfigure}
	\caption{Two posets of shuffle words.}
\end{figure}

\section{Covering Pairs and the Noncrossing Matching Complex}
    \label{sec:covers}
We first describe the ``local structure'' of $\Bub(m,n)$.  To that end, we study the \defn{covering pairs} in $\Bub(m,n)$, \ie~the relations $\ubf\bubless\vbf$ such that there exists no $\wbf$ with $\ubf\bubless\wbf\bubless\vbf$.  We write $\ubf\bubcov\vbf$ in that event.

While it is easily checked that every transposition corresponds to a covering pair in $\Bub(m,n)$, the same is not necessarily true for indels. In fact, let $\ubf=\rd{x_1x_2}\bl{y_1}$ and $\vbf=\rd{x_1}\bl{y_1}$.  Then, $\ubf\indel\vbf$, because we delete the letter $\rd{x_2}$.  However, this is not a covering pair, because the word $\wbf=\rd{x_1}\bl{y_1}\rd{x_2}$ lies strictly between $\ubf$ and $\vbf$, see Figure~\ref{fig:bubble_21}.  In fact, we have $\ubf\transpose\wbf\indel\vbf$.  In some sense, transpositions are prioritized over deletions.

Let $\ubf=u_{1}u_{2}\cdots u_{k}$. Recall that for $i\in[k]$ we denote by $\ubf_{\widehat{\imath}}$ the word obtained by deleting the letter $u_{i}$.  Then, $\ubf_{\widehat{\imath}}\indel\ubf$ if $u_{i}$ is in $\ybf$ and $\ubf\indel\ubf_{\widehat{\imath}}$ if $u_{i}$ is in $\xbf$.  We define a new relation $\sindel$ on $\Shuf(m,n)$ by setting
\begin{displaymath}
	\vbf\sindel\vbf'\quad\text{if and only if}\quad
		\begin{cases}
			\vbf=\ubf\;\text{and}\;\vbf'=\ubf_{\widehat{\imath}} & \text{if}\;u_{i},u_{i+1}\in X,\\
			\vbf=\ubf_{\widehat{\imath}}\;\text{and}\;\vbf'=\ubf & \text{if}\;u_{i},u_{i+1}\in Y.
	    \end{cases}
\end{displaymath}
In both cases, if $i=k$, then we just have to check the condition for $u_{k}$.  We call $\sindel$ a \defn{right indel}, because the inserted (resp. deleted) letter needs to be as far right as possible.  Clearly, $\ubf\sindel\vbf$ implies $\ubf\indel\vbf$, but the converse is not true.  
% is pushed as far right as possible.  
For instance, $\rd{x_1}\bl{y_2}\rd{x_2}\bl{y_4}\indel\rd{x_1}\bl{y_2y_4}\indel\bl{y_1}\rd{x_1}\bl{y_2y_4}$ are not right indels, because in the first indel, the deleted letter $\rd{x_2}$ is neither at the end of the word nor followed by another letter from $X$.  In the second indel, the inserted letter $\bl{y_1}$ ends up before a letter from $X$.

\begin{lemma}\label{lem:bubble_covers}
	For $\ubf,\vbf\in\Shuf(m,n)$ we have $\ubf\bubcov\vbf$ if and only if either $\ubf\transpose\vbf$ or $\ubf\sindel\vbf$.
\end{lemma}

The definition of $\sindel$ and $\transpose$ implies that there are essentially three different types of covering pairs.  We use this to define the following labeling of the covering pairs of $\Bub(m,n)$:
\begin{equation}\label{eq:bubble_labeling}
	\lambda(\ubf,\vbf) \defs 
	\begin{cases}
		x & \text{if}\;\ubf\sindel\vbf, \ubf_{\ybf}=\vbf_{\ybf},\ubf_{\xbf}\setminus\vbf_{\xbf}=\{x\},\\
		y & \text{if}\;\ubf\sindel\vbf, \ubf_{\xbf}=\vbf_{\xbf},\vbf_{\ybf}\setminus\ubf_{\ybf}=\{y\},\\
		(x,y) & \text{if}\;\ubf\transpose\vbf, \invset(\vbf)\setminus\invset(\ubf)=\bigl\{(x,y)\bigr\}.
	\end{cases}
\end{equation}
For $\vbf\in\Shuf(m,n)$, let
\begin{displaymath}
	\lambda_{\downarrow}(\vbf) \defs \bigr\{\lambda(\ubf,\vbf)\mid \ubf\sindel \vbf \mbox{ or }\ubf\transpose\vbf \bigl\}.
\end{displaymath}
Figure~\ref{fig:bubble_21_labeled} shows $\Bub(2,1)$ with this labeling.

\begin{figure}
	\centering
	\begin{subfigure}[t]{.45\textwidth}
		\centering
		\begin{tikzpicture}\small
			\def\x{1.25};
			\def\y{1};
			\def\s{1};
			%%
			\draw(3*\x,1*\y) node[scale=\s,inner sep=.5pt](n1){$\rd{x_1x_2}$};
			\draw(2*\x,2*\y) node[scale=\s,inner sep=.5pt](n2){$\rd{x_1x_2}\bl{y_1}$};
			\draw(2*\x,3*\y) node[scale=\s,inner sep=.5pt](n3){$\rd{x_1}\bl{y_1}\rd{x_2}$};
			\draw(3*\x,3*\y) node[scale=\s,inner sep=.5pt](n4){$\rd{x_1}$};
			\draw(7*\x,3*\y) node[scale=\s,inner sep=.5pt](n5){$\rd{x_2}$};
			\draw(2*\x,4*\y) node[scale=\s,inner sep=.5pt](n6){$\rd{x_1}\bl{y_1}$};
			\draw(4*\x,4*\y) node[scale=\s,inner sep=.5pt](n7){$\bl{y_1}\rd{x_1x_2}$};
			\draw(6*\x,4*\y) node[scale=\s,inner sep=.5pt](n8){$\rd{x_2}\bl{y_1}$};
			\draw(4*\x,5*\y) node[scale=\s,inner sep=.5pt](n9){$\bl{y_1}\rd{x_1}$};
			\draw(6*\x,5*\y) node[scale=\s,inner sep=.5pt](n10){$\bl{y_1}\rd{x_2}$};
			\draw(7*\x,5*\y) node[scale=\s,inner sep=.5pt](n11){$\epsilon$};
			\draw(6*\x,6*\y) node[scale=\s,inner sep=.5pt](n12){$\bl{y_1}$};
			%%
			\draw(n1) -- (n2) node[midway,fill=white,inner sep=.2pt,scale=.67]{$y_{1}$};
			\draw(n1) -- (n4) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{2}$};
			\draw(n1) -- (n5) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{1}$};
			\draw(n2) -- (n3) node[midway,fill=white,inner sep=.2pt,scale=.67]{$(x_{2},y_{1})$};
			\draw(n2) -- (n8) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{1}$};
			\draw(n3) -- (n6) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{2}$};
			\draw(n3) -- (n7) node[midway,fill=white,inner sep=.2pt,scale=.67]{$(x_{1},y_{1})$};
			\draw(n4) -- (n6) node[midway,fill=white,inner sep=.2pt,scale=.67]{$y_{1}$};
			\draw(n4) -- (n11) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{1}$};
			\draw(n5) -- (n8) node[midway,fill=white,inner sep=.2pt,scale=.67]{$y_{1}$};
			\draw(n5) -- (n11) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{2}$};
			\draw(n6) -- (n9) node[midway,fill=white,inner sep=.2pt,scale=.67]{$(x_{1},y_{1})$};
			\draw(n7) -- (n9) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{2}$};
			\draw(n7) -- (n10) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{1}$};
			\draw(n8) -- (n10);
				\draw(6*\x,4.7*\y) node[fill=white,inner sep=.2pt,scale=.67]{$(x_{2},y_{1})$};
			\draw(n9) -- (n12) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{1}$};
			\draw(n10) -- (n12) node[midway,fill=white,inner sep=.2pt,scale=.67]{$x_{2}$};
			\draw(n11) -- (n12) node[midway,fill=white,inner sep=.2pt,scale=.67]{$y_{1}$};
		\end{tikzpicture}
		\caption{The poset $\Bub(2,1)$ labeled by $\lambda$.}
		\label{fig:bubble_21_labeled}
	\end{subfigure}
	\hspace*{1cm}
	\begin{subfigure}[t]{.45\textwidth}
		\centering
		\begin{tikzpicture}
			\def\x{1};
			\def\y{1};
			%%
			\coordinate(m1) at (1*\x,1*\y);
			\coordinate(m2) at (3*\x,1*\y);
			\coordinate(m3) at (5*\x,1*\y);
			\coordinate(m4) at (2*\x,3*\y);
			\coordinate(m5) at (4*\x,3*\y);
			%%
			\draw(m1) -- (m4);
			\draw(m2) -- (m4);
			\draw(m2) -- (m5);
			\draw(m3) -- (m5);
			\draw(m4) -- (m5);
			%%
			\draw(m1) node[inner sep=.2pt]{\ncm{.5}{2,3}{2/3}};
			\draw(m2) node[inner sep=.2pt]{\ncm{.5}{3}{}};
			\draw(m3) node[inner sep=.2pt]{\ncm{.5}{1,3}{1/3}};
			\draw(m4) node[inner sep=.2pt]{\ncm{.5}{1}{}};
			\draw(m5) node[inner sep=.2pt]{\ncm{.5}{2}{}};
			%%
			\begin{pgfonlayer}{background}
				\fill[white!50!gray](3*\x,1*\y) -- (2*\x,3*\y) -- (4*\x,3*\y) -- (3*\x,1*\y);
			\end{pgfonlayer}
		\end{tikzpicture}
		\caption{The noncrossing matching complex $\Gamma(2,1)$.  The gray triangle indicates a two-dimensional face. In each node, the vertex at the top represents $y_{1}$, and the two vertices at the bottom represent $x_{1}$ and $x_{2}$.}
		\label{fig:bubble_21_matching_complex}
	\end{subfigure}
	\caption{The noncrossing matching complex of a bubble lattice.}
	\label{fig:bubble_noncrossing_matching}
\end{figure}

We now construct a simplicial complex whose faces are in bijection with the shuffle words in $\Shuf(m,n)$.  Recall that $X=\{x_1,\ldots,x_m\}$ and $Y=\{y_1,\ldots,y_n\}$, and define $\Tcal\defs X\uplus Y\uplus(X\times Y)$.
We call the elements of $X\uplus Y$ \defn{loops} and elements of $X\times Y$ \defn{edges}.  Then a loop $z$ and an edge $\{x,y\}$ are \defn{crossing} if $z=x$ or $z=y$.  Two edges $(x_{s_{1}},y_{t_{1}})$ and $(x_{s_{2}},y_{t_{2}})$ are \defn{crossing} if $s_{1}<s_{2}$ and $t_{1}>t_{2}$.  Two elements of $\Tcal$ are \defn{noncrossing} if they do not cross in one of the mentioned ways.  The \defn{noncrossing matching complex} $\Gamma\defs\Gamma(m,n)$ is the abstract simplicial complex on $\Tcal$ whose faces are collections of pairwise noncrossing elements of $\Tcal$.  The term ``crossing'' is motivated by the following graphical representation of $\Gamma$.  We draw vertices labeled by $x_1,x_2,\ldots,x_m$ on a horizontal line and vertices labeled by $y_1,y_2,\ldots,y_n$ on another horizontal line such that the line containing the $y$'s is above the line containing the $x$'s.  An edge $(x_{s},y_{t})$ is then illustrated by connecting the vertices $x_s$ and $y_t$.  Then, two edges are crossing if and only if their corresponding lines intersect.

The noncrossing matching complex recovers essential information on the bubble lattice.

\begin{proposition}\label{prop:bubble_join_complex}
    The map $\lambda_{\downarrow}\colon\Shuf(m,n)\to\Gamma(m,n)$ is a bijection.
\end{proposition}
\begin{proof}[Proof sketch]
    It is straightforward to verify that for every $\vbf\in\Shuf(m,n)$, the set of labels $\lambda_{\downarrow}(\vbf)$ consists of mutually noncrossing elements of $\Tcal$.

    Since any $\vbf\in\Shuf(m,n)$ is uniquely determined by its interface and its residue, it is clear that the assignment $\vbf\mapsto\lambda_{\downarrow}(\vbf)$ is a bijection from $\Shuf(m,n)$ to (the set of faces of) $\Gamma(m,n)$.
\end{proof}

% \begin{remark}
%     We state below in Proposition~\ref{prop:bubble_lattice} that $\Bub(m,n)$ is a lattice for all $m,n\geq 0$ and in the full version of this abstract we prove that $\Bub(m,n)$ is semidistributive.  With this additional information, Proposition~\ref{prop:bubble_join_complex} together with \cite[Lemma~19]{barnard:canonical}\footnote{\add{In the arxiv version of \cite{barnard:canonical} this is Lemma~3.3.}} implies that $\Gamma(m,n)$ is the \defn{canonical join complex} of $\Bub(m,n)$.
% \end{remark}

We now prove that $\Gamma(m,n)$ has another intriguing topological property: it is (non-pure) vertex decomposable in the sense of \cites{bjorner:shellable,provan:decompositions}.  Let us briefly recall the necessary definitions and fix a simplicial complex $\Delta$ with vertex set $M$.  For $F\in\Delta$, the \defn{link} of $F$ in $\Delta$ is
\begin{equation*}
	\lnk_{\Delta}(F) \defs \bigl\{G\in\Delta\mid F\cap G=\emptyset\;\text{and}\;F\cup G\in\Delta\bigr\}.
\end{equation*}
The \defn{deletion} of $F$ in $\Delta$ is
\begin{equation*}
	\dlt_{\Delta}(F) \defs \bigl\{G\in\Delta\mid F\not\subseteq G\bigr\}.
\end{equation*}

A vertex $v\in M$ is a \defn{shedding vertex} if both the link $\lnk_{\Delta}(v)$ and the deletion $\dlt_{\Delta}(v)$ are vertex decomposable and the complexes $\lnk_{\Delta}(v)$ and $\dlt_{\Delta}(v)$ do not share facets.  A simplicial complex $\Delta$ is \defn{vertex decomposable} if it is a simplex or contains a shedding vertex.  A simplicial complex $\Delta$ is \defn{shellable} if there exists a total order $\prec$ on the facets of $\Delta$ such that for every two facets $F,G$ with $F\prec G$ there exists a facet $H\prec G$ such that $F\cap G\subseteq H\cap G$ and $\dim H\cap G=\dim\Delta-1$.  Such a total order (if it exists) is a \defn{shelling order} of $\Delta$.  By \cite[Theorem~11.3]{bjorner:shellable}, every vertex-decomposable complex is shellable.

\begin{proposition}\label{prop:ncm_vertex_decomposable}
	The noncrossing matching complex $\Gamma(m,n)$ is vertex decomposable, and therefore shellable.
\end{proposition}
\begin{proof}[Proof sketch]
    The proof proceeds by induction on $m+n$.  The induction base is trivial for $n=0$, since $\Gamma(m,0)$ is a simplex.  For $n=1$, the claim can be deduced from the results of \cite{muehle:hochschild}, where it was shown that a simplicial complex isomorphic to $\Gamma(m,1)$ is vertex decomposable.  For $n>1$, we consider the vertex $v=(x_{s},y_{t})$ for $s\in[m]$ and $t\in[n]$ and show that it is a shedding vertex of $\Gamma(m,n)$.  Indeed, the link $\lnk_{\Gamma(m,n)}(v)$ is isomorphic to the join $\Gamma(m_{1},n_{1})*\Gamma(m_{2},n_{2})$, for appropriate choices of $m_{1},n_{1},m_{2},n_{2}$.  By successively deleting vertices $(x_{s},y_{t'})$ for $t'\in[n]$ we may show that $v$ satisfies the remaining properties.  
\end{proof}

\section{Lattice Structure and the Noncrossing Bipartite Complex}
    \label{sec:lattice}
Now we move to the ``global structure'' of $\Bub(m,n)$.  Recall that a \defn{lattice} is a poset in which every two elements have a least upper bound and a greatest lower bound.

\begin{proposition}\label{prop:bubble_lattice}
	For $m,n\geq 0$, the poset $\Bub(m,n)$ is a lattice.
\end{proposition}
\begin{proof}[Proof sketch]
    It is straightforward to verify that $\Bub(m,n)$ is isomorphic to the dual poset of $\Bub(n,m)$.  Therefore, it remains to establish the existence of joins in $\Bub(m,n)$.  In order to explicitly construct the join of $\ubf,\vbf\in\Shuf(m,n)$, we first determine the letters of $X$ contained in both $\ubf$ and $\vbf$, and then we determine the letters of $Y$ which are contained in $\ubf$ or $\vbf$.  These letters form the support of several shuffle words, and we choose the minimal shuffle word from this set which satisfies the ``disorder'' introduced by both $\ubf$ and $\vbf$, \ie~which letters from $Y$ must necessarily appear before which letters of $X$.
\end{proof}

\begin{example}\label{ex:bubble_joins}
	Let $m=n=5$ and consider $\ubf=\rd{x_2x_4}\bl{y_1y_4}\rd{x_5}\bl{y_5}$ and $\vbf=\rd{x_3}\bl{y_1y_3}\rd{x_4x_5}$. Then, we consider all words in $\Shuf(m,n)$ using the letters $\{\rd{x_4},\rd{x_5}\}$ and $\{\bl{y_1},\bl{y_3},\bl{y_4},\bl{y_5}\}$.  The minimal element with these letters is clearly $\widetilde{\wbf}=\rd{x_4x_5}\bl{y_1y_3y_4y_5}$.  We observe that $\rd{x_{5}}$ appears after $\bl{y_{1}}$ and $\bl{y_{4}}$ in $\ubf$ and after $\bl{y_{1}}$ and $\bl{y_{3}}$ in $\vbf$.  Moreover, $\rd{x_{4}}$ also appears after $\bl{y_{1}}$ and $\bl{y_{3}}$ in $\vbf$.  Therefore, the join of $\ubf$ and $\vbf$ is $\wbf = \bl{y_1y_3}\rd{x_4}\bl{y_4}\rd{x_5}\bl{y_5}$.
\end{example}

% \begin{remark}
%     In the full version of this article, we prove that $\Bub(m,n)$ has some remarkable lattice-theoretic properties: it is semidistributive and trim.  Due to space limitations, we cannot go into further details here.
% \end{remark}

In the remainder of this section, we present a geometric interpretation of $\Bub(m,n)$.  More precisely, we construct a certain simplicial complex with the property that the $1$-skeleton of its dual polytope can be oriented in such a way that it agrees with the Hasse diagram of $\Bub(m,n)$.

Let $r\defs m+n$. We introduce two new letters $x_0$ and $y_0$ and define $\wtil{\xbf}\defs x_0x_1\cdots x_m$ and $\wtil{\ybf}\defs y_0y_1\cdots y_n$. Let $\wtil{X}\defs X\uplus\{x_0\}$ and $\wtil{Y}\defs Y\uplus\{y_0\}$ be the supports of $\wtil{\xbf}$ and $\wtil{\ybf}$, respectively. Consider a multigraph $\wtil{G}=\wtil{G}(m,n)$ with vertex set $\wtil{X}\uplus\wtil{Y}$ and edge set $\Ucal=\Lcal\uplus\Ecal$ where
\begin{displaymath}
    \Lcal \defs \bigl\{ \{z\} \mid z\in X\uplus Y \bigr\}, \quad\text{and}\quad \Ecal \defs \bigl\{ \{x,y\} \mid x\in \wtil{X},\ y\in \wtil{Y} \bigr\} \setm \{ \{x_0,y_0\} \}.
\end{displaymath}
In other words, $\wtil{G}$ is formed by deleting the edge $\{x_0,y_0\}$ from the complete bipartite graph with independent sets $\wtil{X}$ and $\wtil{Y}$, then adding a loop at each vertex except $x_0$ and~$y_0$.

We say that edges $\{x_{s_1},y_{t_1}\}$ and $\{x_{s_2},y_{t_2}\}$ are \defn{crossing} if $s_1<s_2$ and $t_1>t_2$. A loop $\{z\}$ and an edge $\{x,y\}$ are \defn{crossing} if $z=x$ or $z=y$. Any two elements of $\Ucal$ that are not crossing in one of these two ways are said to be \defn{noncrossing}.

The \defn{noncrossing bipartite complex} $\Delta\defs\Delta(m,n)$ is the abstract simplicial complex with ground set $\Ucal$ whose faces are collections of pairwise noncrossing elements. See Figure~\ref{fig:bnc_21} for an illustration of $\Delta(2,1)$.  By construction, the noncrossing matching complex $\Gamma(m,n)$ is a subcomplex of $\Delta(m,n)$.

\begin{figure}
	\begin{subfigure}[t]{.45\textwidth}
		\centering
		\begin{tikzpicture}
			\def\x{4};
			\def\s{3};
			%%
			\coordinate(n1) at (1*\x,1*\x);
			\coordinate(n2) at (2.5*\x,1*\x);
			\coordinate(n3) at (1.85*\x,1.4*\x);
			\coordinate(n4) at (1.65*\x,1.2*\x);
			\coordinate(n5) at (1.75*\x,.25*\x);
			\coordinate(n6) at (1.75*\x,1.75*\x);
			\coordinate(n7) at (1.4*\x,.8*\x);
			\coordinate(n8) at (1.9*\x,.8*\x);
			%%
			\draw[back](n1) -- (n4);
			\draw[back](n4) -- (n5);
			\draw[back](n4) -- (n6);
			\draw[back](n2) -- (n4);
			%%
			\draw(n4) node[inner sep=.2pt]{\ncb{.45}{2,5}{2/5}};
            %%
			\draw[edge](n1) -- (n5);
			\draw[edge](n1) -- (n6);
			\draw[edge](n1) -- (n7);
			\draw[edge](n2) -- (n3);
			\draw[edge](n2) -- (n5);
			\draw[edge](n2) -- (n6);
			\draw[edge](n2) -- (n8);
			\draw[edge](n3) -- (n6);
			\draw[edge](n3) -- (n7);
			\draw[edge](n3) -- (n8);
			\draw[edge](n5) -- (n7);
			\draw[edge](n5) -- (n8);
			\draw[edge](n6) -- (n7);
			\draw[edge](n7) -- (n8);
			%%
			\draw(n1) node[inner sep=.2pt]{\ncb{.45}{1,5}{1/5}};
			\draw(n2) node[inner sep=.2pt]{\ncb{.45}{2,4}{2/4}};
			\draw(n3) node[inner sep=.2pt]{\ncb{.45}{3,4}{3/4}};
			\draw(n5) node[inner sep=.2pt]{\ncb{.45}{3}{}};
                \draw(n5)++(0,-.17*\x) node{};
			\draw(n6) node[inner sep=.2pt]{\ncb{.45}{3,5}{3/5}};
			\draw(n7) node[inner sep=.2pt]{\ncb{.45}{2}{}};
			\draw(n8) node[inner sep=.2pt]{\ncb{.45}{5}{}};
		\end{tikzpicture}
		\caption{The noncrossing bipartite complex $\Delta(2,1)$.}
		\label{fig:bnc_21}
	\end{subfigure}
	\hspace*{1cm}
	\begin{subfigure}[t]{.45\textwidth}
		\centering
		\begin{tikzpicture}
			\def\x{4};
			\def\s{3};
			%
			\coordinate(n1) at (1*\x,1*\x);
			\coordinate(n2) at (1.75*\x,1*\x);
			\coordinate(n3) at (1.5*\x,1.5*\x);
			\coordinate(n4) at (2.15*\x,1.15*\x);
			\coordinate(n5) at (2.5*\x,1.5*\x);
			\coordinate(n6) at (1.75*\x,1.75*\x);
			\coordinate(n7) at (2.15*\x,1.9*\x);
			\coordinate(n8) at (1*\x,2*\x);
			\coordinate(n9) at (1.45*\x,2*\x);
			\coordinate(n10) at (2.25*\x,2.25*\x);
			\coordinate(n11) at (1.5*\x,2.5*\x);
			\coordinate(n12) at (2.5*\x,2.5*\x);
            %
			\draw[edge](n1) -- (n2);
			\draw[back](n1) -- (n3);
			\draw[edge](n1) -- (n8);
			\draw[edge](n2) -- (n4);
			\draw[edge](n2) -- (n6);
			\draw[back](n3) -- (n5);
			\begin{pgfonlayer}{background}
				\draw[back](n3) -- (n11);
			\end{pgfonlayer}
			\draw[edge](n4) -- (n5);
			\draw[edge](n4) -- (n7);
			\draw[edge](n5) -- (n12);
			\draw[edge](n6) -- (n7);
			\draw[edge](n7) -- (n10);
			\draw[edge](n8) -- (n9);
			\draw[edge](n8) -- (n11);
			\draw[edge](n9) -- (n6);
			\draw[edge](n9) -- (n10);
			\draw[edge](n10) -- (n12);
			\draw[edge](n11) -- (n12);
			%
			\draw(n1) node[inner sep=.2pt]{\ncb{.45}{1,2,3,5}{1/5}};
				\draw(n1)++(0*\x,-.15*\x) node[scale=.75]{$\bl{y_{1}}$};
			\draw(n2) node[inner sep=.2pt]{\ncb{.45}{2,3,5}{}};
				\draw(n2)++(0*\x,-.15*\x) node[scale=.75]{$\epsilon$};
			\draw(n3) node[inner sep=.2pt]{\ncb{.45}{1,2,3,5}{1/5,2/5}};
				\draw(n3)++(0*\x,-.15*\x) node[scale=.75]{$\bl{y_{1}}\rd{x_{1}}$};
			\draw(n4) node[inner sep=.2pt]{\ncb{.45}{2,3,4,5}{2/4}};
				\draw(n4)++(0*\x,-.15*\x) node[scale=.75]{$\rd{x_{1}}$};
			\draw(n5) node[inner sep=.2pt]{\ncb{.45}{2,3,4,5}{2/4,2/5}};
				\draw(n5)++(0*\x,-.15*\x) node[scale=.75]{$\rd{x_{1}}\bl{y_{1}}$};
			\draw(n6) node[inner sep=.2pt]{\ncb{.45}{2,3,4,5}{3/4}};
				\draw(n6)++(0*\x,-.15*\x) node[anchor=west,scale=.75]{$\rd{x_{2}}$};
			\draw(n7) node[inner sep=.2pt]{\ncb{.45}{2,3,4,5}{2/4,3/4}};
				\draw(n7)++(0*\x,-.15*\x) node[anchor=west,scale=.75]{$\rd{x_{1}x_{2}}$};
			\draw(n8) node[inner sep=.2pt]{\ncb{.45}{1,2,3,5}{1/5,3/5}};
				\draw(n8)++(0*\x,-.15*\x) node[anchor=east,scale=.75]{$\bl{y_{1}}\rd{x_{2}}$};
			\draw(n9) node[inner sep=.2pt]{\ncb{.45}{2,3,4,5}{3/4,3/5}};
				\draw(n9)++(0*\x,-.15*\x) node[anchor=east,scale=.75]{$\rd{x_{2}}\bl{y_{1}}$};
			\draw(n10) node[inner sep=.2pt]{\ncb{.45}{2,3,4,5}{2/4,3/4,3/5}};
				\draw(n10)++(-.05*\x,-.15*\x) node[anchor=west,scale=.75]{$\rd{x_{1}x_{2}}\bl{y_{1}}$};
			\draw(n11) node[inner sep=.2pt]{\ncb{.45}{1,2,3,5}{1/5,2/5,3/5}};
				\draw(n11)++(0*\x,-.15*\x) node[anchor=west,scale=.75]{$\bl{y_{1}}\rd{x_{1}}\rd{x_{2}}$};
			\draw(n12) node[inner sep=.2pt]{\ncb{.45}{2,3,4,5}{2/4,2/5,3/5}};
				\draw(n12)++(0*\x,-.15*\x) node[anchor=west,scale=.75]{$\rd{x_{1}}\bl{y_{1}}\rd{x_{2}}$};
		\end{tikzpicture}
		\caption{The dual polytope of $\Delta(2,1)$.}
		\label{fig:bnc_21_dual}
	\end{subfigure}
	\caption{The noncrossing bipartite complex and its dual polytope.  These are two-dimensional polytopes realized in a three-dimensional space.  We have drawn a projection where hidden edges are dashed.}
	\label{fig:bnc_21_main}
\end{figure}

Let $\wbf=w_1 w_2\cdots w_k\in\Shuf(m,n)$. We let $\wtil{\wbf}=w_{-1}w_0w_1\cdots w_k$ where $w_{-1}=x_0$ and $w_0=y_0$, and define $\phi(\wbf)$ to be the following $r$-element subset of $\Ucal$:
\begin{itemize}
    \item if $z\in X\uplus Y$ is not in the support of $\wbf$, then $\{z\}\in\phi(\wbf)$;
    \item if $w_j\in X$ and $i=\max\{ i'<j \mid w_{i'}\in \wtil{Y}\}$, then $\{w_j,w_i\}\in \phi(\wbf)$;
    \item if $w_j\in Y$ and $i=\max\{i' < j \mid w_{i'} \in \wtil{X}\}$, then $\{w_i,w_j\}\in\phi(\wbf)$.
\end{itemize}

For example, if $m=n=3$, then
\begin{displaymath}
    \phi(\rd{x_2}\bl{y_1y_2}\rd{x_3}) = \bigl\{ \{\rd{x_1}\},\ \{\bl{y_3}\},\ \{\rd{x_2},\bl{y_0}\},\ \{\rd{x_2},\bl{y_1}\},\ \{\rd{x_2},\bl{y_2}\},\ \{\rd{x_3},\bl{y_2}\} \bigr\}.
\end{displaymath}

\begin{proposition}\label{prop:phi_noncrossing}
    The map $\phi$ is a bijection from $\Shuf(m,n)$ to the set of facets of $\Delta(m,n)$.
\end{proposition}

By construction, $\phi(\wbf)$ contains $r=m+n$ elements.  Thus, Proposition~\ref{prop:phi_noncrossing} implies that $\Delta(m,n)$ is a pure simplicial complex of dimension $r-1$.  The next two lemmas establish that the $1$-skeleton of the dual of $\Delta(m,n)$ can be oriented in such a way that one obtains the Hasse diagram of $\Bub(m,n)$.  This is illustrated in Figure~\ref{fig:bnc_21_dual}, which shows the dual of $\Delta(m,n)$.  The vertices of this dual polytope (which are the facets of $\Delta(m,n)$) are labeled by their corresponding shuffle words under the map $\phi^{-1}$.  It is left to the reader to recover the orientation of the $1$-skeleton of this polytope that recovers the bubble lattice $\Bub(m,n)$; see also Figure~\ref{fig:bubble_21}.

\begin{lemma}\label{lem:interval}
    For any $\sigma\in\Delta(m,n)$, the set of shuffle words $\wbf\in\Shuf(m,n)$ with $\sigma\subseteq\varphi(\wbf)$ is a closed interval of $\Bub(m,n)$.
\end{lemma}

\begin{lemma}\label{lem:ridges}
    For shuffle words $\ubf,\vbf$, we have $\dim \phi(\ubf)\cap \phi(\vbf) = r-2$ if and only if either $\ubf\bubcov\vbf$ or $\vbf\bubcov \ubf$.
\end{lemma}

We conclude this section with the fact that $\Delta(m,n)$ is shellable.
% a remarkable topological property of $\Delta(m,n)$: it is a shellable simplicial complex.  

\begin{proposition}
    Any linear extension of $\Bub(m,n)$ induces a shelling order on the facets of $\Delta(m,n)$.  Consequently, $\Delta(m,n)$ is shellable.
\end{proposition}
\begin{proof}[Proof sketch]
    Fix a linear extension $\prec$ of $\bubleq$ and pick $\ubf,\vbf\in\Shuf(m,n)$ with $\ubf\prec\vbf$.  
%     Without loss of generality, 
    By abuse of notation, we use the same symbol $\prec$ for the total order on the facets of $\Delta(m,n)$ induced via the map $\phi$.  We thus have $\phi(\ubf)\prec\phi(\vbf)$.  Now, $\ubf\bubless\vbf$ and we consider $\sigma=\phi(\ubf)\cap\phi(\vbf)$.  By Lemma~\ref{lem:interval}, any $\wbf\in\Shuf(m,n)$ with $\sigma\subseteq\phi(\wbf)$ must belong to the closed interval $[\ubf,\vbf]$ in $\Bub(m,n)$.  In particular, we may choose $\wbf$ such that $\ubf\bubleq\wbf\bubcov\vbf$, which then implies $\phi(\wbf)\prec\phi(\vbf)$.  But then we have $\sigma\subseteq\phi(\wbf)\cap\phi(\vbf)$ and with Lemma~\ref{lem:ridges} we get $\dim\phi(\wbf)\cap\phi(\vbf)=r-2=\dim\Delta(m,n)-1$.  Thus $\prec$ is a shelling order of $\Delta(m,n)$.
\end{proof}

\section{Enumerative Properties}
    \label{sec:enumeration}
Let us now turn to some enumerative aspects of the simplicial complexes $\Gamma(m,n)$ and $\Delta(m,n)$.  In general, the \defn{$f$-vector} of a simplicial complex $\Delta$ is the sequence 
\begin{displaymath}
	f_{\Delta}\defs(f_{-1},f_{0},f_{1},\ldots), 
\end{displaymath}
where $f_{i}$ counts the $i$-dimensional faces of $\Delta$.

We start by computing a refined variant of the $f$-vector of the noncrossing matching complex $\Gamma(m,n)$.  We define the \defn{in-degree} of $\ubf\in\Shuf(m,n)$ by
\begin{displaymath}
	\indeg(\ubf) \defs \bigl\lvert\bigl\{\ubf'\in\Shuf(m,n)\mid \ubf'\bubcov\ubf\bigr\}\bigr\rvert.
\end{displaymath}
By Proposition~\ref{prop:bubble_join_complex}, $\indeg(\ubf)$ describes the size of the corresponding face $\lambda_{\downarrow}(\ubf)$ of $\Gamma(m,n)$.  By Lemma~\ref{lem:bubble_covers}, a covering pair in $\Bub(m,n)$ can either correspond to an indel or to a transposition.  We thus define the \defn{indel-degree} of $\ubf$ by
\begin{displaymath}
	\indeld(\ubf) \defs \bigl\lvert\bigl\{\ubf'\in\Shuf(m,n)\mid \ubf'\sindel\ubf\bigr\}\bigr\rvert,
\end{displaymath}
and the \defn{transpose-degree} of $\ubf$ by
\begin{displaymath}
  \transd(\ubf) \defs \bigl\lvert\bigl\{\ubf'\in\Shuf(m,n)\mid \ubf'\transpose\ubf\bigr\}\bigr\rvert.
\end{displaymath}
Evidently, $\indeg(\ubf) = \indeld(\ubf) + \transd(\ubf)$.

\begin{lemma}\label{lem:bubble_refined_indegree}
  The number of elements $\ubf\in\Shuf(m,n)$ with $\transd(\ubf)=a$ and $\indeld(\ubf)=b$ is $\binom{m}{a}\binom{n}{a}\binom{m+n-2a}{b}$.
\end{lemma}
\begin{proof}[Proof sketch]
    Any $\ubf\in\Shuf(m,n)$ is determined by its interface, \ie~pairs $(x_{s},y_{t})$ where $y_{t}$ immediately precedes $x_{s}$.  Choosing an interface consisting of $a$ such pairs can be done in $\binom{m}{a}\binom{n}{a}$ ways and each such pair is the label of a covering pair corresponding to a transposition.  Any letter of $X$ not in the support of $\ubf$ is the label of a covering pair corresponding to an indel and any letter of $Y$ in the support of $\ubf$, but not part of a pair in the interface, is the label of a covering pair corresponding to an indel.  Clearly, these letters can be obtained in $\binom{m+n-2a}{b}$ ways.
\end{proof}

We may thus compute the \defn{$H$-triangle} of $\Bub(m,n)$, defined by
\begin{displaymath}
	H_{m,n}(p,q) \defs \sum_{\ubf\in\Shuf(m,n)}p^{\indeg(\ubf)}q^{\indeld(\ubf)}.
\end{displaymath}

\begin{proposition}\label{prop:bubble_h_triangle}
	For $m,n\geq 0$, we have
	\begin{displaymath}
		H_{m,n}(p,q) = \sum_{a\geq 0} \binom{m}{a}\binom{n}{a}p^a(1+pq)^{m+n-2a}.
	\end{displaymath}
\end{proposition}
The $f$-vector of $\Gamma(m,n)$ is then obtained as the coefficient sequence of $H_{m,n}(p,1)$.

\begin{remark}
	Somewhat surprisingly, the polynomial $H_{m,n}(p,1)$ appears already in \cite[Corollary~4.8]{greene:shuffle} and was used to establish the rank symmetry of $\ShufPoset(m,n)$ and for showing its decomposition into symmetrically placed Boolean lattices.
\end{remark}

% \begin{remark}
% 	Perhaps even more surprisingly, the evaluation $H_{m,n}(2,0)$ yields
% 	\begin{displaymath}
% 		H_{m,n}(2,0) = \sum_{a\geq 0} \binom{m}{a}\binom{n}{a}2^a,
% 	\end{displaymath}
% 	which is the defining formula for the \defn{Delannoy numbers}; see \cite{banderier:why}.  These numbers count, for instance, lattice paths in an $m\times n$-rectangle using north, northeast or east steps.
% \end{remark}

Next, we wish to describe the $f$-polynomial of the noncrossing bipartite complex $\Delta(m,n)$.  To that end, we define the \defn{$F$-triangle} by
\begin{displaymath}
    F_{m,n}(p,q) \defs \sum_{\sigma\in\Delta(m,n)}p^{\lvert \sigma\cap\Ecal\rvert}q^{\lvert\sigma\cap\Lcal\rvert}.
\end{displaymath}
More precisely, the variable $p$ keeps track of the number of edges per face and the variable $q$ keeps track of the number of loops per face.  The $f$-vector of $\Delta(m,n)$ is obtained from the coefficient sequence of $F_{m,n}(p,p)$.  It is not immediately obvious, but follows for instance from the next result that the $h$-vector of $\Delta(m,n)$ is obtained from the coefficient sequence of $H_{m,n}(p,1)$.
% In fact, we may go one step further and define the \defn{extended} $F$-triangle
% \begin{displaymath}
%     F_{m,n}(p;q_{x_{1}},q_{x_{2}},\ldots,q_{y_{n}}) \defs \sum_{\sigma\in\Delta(m,n)}p^{\lvert \sigma\cap\Ecal\rvert}\prod_{\{z\}\in\sigma}q_{z},
% \end{displaymath}
% which distinguishes the various loops.

Our main result relates the $F$- and the $H$-triangle associated with $\Bub(m,n)$ by an explicit variable substitution.  This establishes a remarkable connection between the $f$-vectors of the noncrossing matching and the noncrossing bipartite complex.%\henri{What is the confidence level? ;)}

\begin{theorem}\label{thm:extendedFH}
    For $m,n\geq 0$, we have
    \begin{displaymath}
        H_{m,n}(p,q) = (p-1)^{m+n} F_{m,n}\left(\frac{1}{p-1},\frac{1+p(q-1)}{p-1}\right).
    \end{displaymath}
    Equivalently, we have
    \begin{displaymath}
        F_{m,n}(p,q) = p^{m+n} H_{m,n}\left(\frac{p+1}{p},\frac{q+1}{p+1}\right).
    \end{displaymath}
\end{theorem}
\begin{proof}[Proof sketch]
	Using the shellability of $\Delta(m,n)$ and the fact that $\Bub(m,n)$ is obtainable from an orientation of the $1$-skeleton of the dual of $\Delta(m,n)$ we may relate the reverse $h$-vector of $\Delta(m,n)$ to the $f$-vector of $\Gamma(m,n)$.  Some explicit computation then yields the result. 
\end{proof}


\begin{example}
    By inspection of Figure~\ref{fig:bubble_21_labeled}, we compute
    \begin{displaymath}
        H_{2,1}(p,q) = p^{3}q^{3} + 3p^{2}q^{2} + 2p^{2}q + 3pq + 2p + 1 = (1+pq)^{3} + 2p(1+pq)
    \end{displaymath}
    in accordance with Proposition~\ref{prop:bubble_h_triangle}.  The evaluation $H_{2,1}(p,1)$ has the coefficient sequence $(1,5,5,1)$ which agrees with the $f$-vector of $\Gamma(2,1)$, see Figure~\ref{fig:bubble_21_matching_complex}.  By Theorem~\ref{thm:extendedFH}, we get
    \begin{displaymath}
        F_{2,1}(p,q) = 3p^{3} + 5p^{2}q + 3pq^{2} + q^{3} + 7p^{2} + 8pq + 3q^{2} + 5p + 3q + 1.
    \end{displaymath}
    The evaluation $F_{2,1}(p,p)$ has the coefficient sequence $(12,18,8,1)$, which is the (reverse) $f$-vector of $\Delta_{2,1}$, see Figure~\ref{fig:bnc_21}.
%     This complex has eight vertices, $18$ edges and $12$ facets.
\end{example}

Lastly, we state a relation of the $F$- and $H$-triangle associated with $\Bub(m,n)$ with a natural polynomial associated with the shuffle lattice $\ShufPoset(m,n)$.  Recall that the \defn{M{\"o}bius function} of a finite poset $\mathbf{P}=(P,\leq)$ is defined for all $x,y\in P$ by
\begin{displaymath}
    \mu_{\mathbf{P}}(x,y) \defs \begin{cases}1 & \text{if } x=y,\\-\sum_{x<z\leq y}\mu_{\mathbf{P}}(x,z) & \text{if } x<y,\\0 & \text{otherwise}.\end{cases}
\end{displaymath}
It was shown in \cite{greene:shuffle} that $\ShufPoset(m,n)$ is a graded poset.  If we denote by $\mathsf{rk}$ the rank function and by $\mu$ the M{\"o}bius function of the \emph{shuffle} poset $\ShufPoset(m,n)$, then the \defn{$M$-triangle} of $\ShufPoset(m,n)$ is
\begin{displaymath}
    M_{m,n}(p,q) \defs \sum_{\ubf,\vbf\in\Shuf(m,n)}\mu(\ubf,\vbf)p^{\mathsf{rk}(\ubf)}q^{\mathsf{rk}(\vbf)}.
\end{displaymath}

The second main outcome of this abstract is the following conjectural relation of the $M$-triangle with the $F$- and $H$-triangle.
%\henri{Should we state this as a conjecture?}.

\begin{conjecture}\label{conj:FHM}
    For $m,n\geq 0$, we have
    \begin{align*}
        M_{m,n}(p,q) & = (1-q)^{m+n}H_{m,n}\left(\frac{q(p-1)}{1-q},\frac{p}{p-1}\right)\\
        & = (pq-1)^{m+n}F_{m,n}\left(\frac{1-q}{pq-1},\frac{1}{pq-1}\right).
    \end{align*}
\end{conjecture}

\begin{example}
    It can be verified directly in Figure~\ref{fig:shuffle_21} that
    \begin{displaymath}
        M_{2,1}(p,q) = p^{3}q^{3} - 5p^{2}q^{3} + 5p^{2}q^{2} + 7pq^{3} - 12pq^{2} - 3q^{3} + 5pq + 7q^{2} - 5q + 1,
    \end{displaymath}
    which confirms Conjecture~\ref{conj:FHM} in this case.
\end{example}


We wish to end this abstract with the following observation.  The structural and enumerative relationships between the bubble lattice and the shuffle lattice as well as the noncrossing matching and the noncrossing bipartite complex that we have outlined here is completely analogous to the relationship between remarkable, important structures associated with a finite irreducible Coxeter group $W$ and a Coxeter element $c\in W$.  More precisely, the analogous structures in this setting are the \emph{$c$-Cambrian lattice} and the \emph{$c$-noncrossing partition lattice}, as well as the \emph{canonical join complex} of the $c$-Cambrian lattice and the \emph{$c$-cluster complex}.  $F$-, $H$- and $M$-triangles associated with these structures were defined in \cite{chapoton:enumerative,chapoton:sur} and they exhibit \emph{the same} relations as the ones stated in Theorem~\ref{thm:extendedFH} and Conjecture~\ref{conj:FHM}.

Other structures exhibiting a similar behavior were studied for instance in \cite{ceballos:fh,garver.mcconville:triangles}.  This indicates that there should exist a more general setting of which all these structures are concrete examples.


% \acknowledgements{}

%% 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}
