%% 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]{FPSAC2020}
\articlenumber{64}
%% 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}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}

\usepackage{verbatim}
\usepackage{stmaryrd}
%\usepackage{authblk}
\usepackage{multirow}
\usepackage{mathrsfs}

\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usepackage{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

\addbibresource{references.bib}

\usepackage{graphicx}
\usetikzlibrary{backgrounds,fit,decorations.pathreplacing}
\usetikzlibrary{arrows,shapes,positioning}
\usetikzlibrary{calc,through,backgrounds,chains}
\usetikzlibrary{arrows,shapes,snakes,automata,backgrounds,petri}

\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\G}{\mathbb{G}}





\newcommand{\barn}[1]{\bar{#1}}
\newcommand{\wil}[1]{\widetilde{#1}}
\newcommand{\ds}[1]{\displaystyle{#1}}

\newcommand{\mc}[1]{\mathcal{#1}} % short for mathcal
\newcommand{\ms}[1]{\mathscr{#1}} % short for mathscript
\newcommand{\mf}[1]{\mathfrak{#1}} % short for mathfrak
\newcommand{\mbf}[1]{\mathbf{#1}} % short for math bold face
\newcommand{\mb}[1]{\mathbb{#1}} % short for mathblackboard
\newcommand{\mt}[1]{\text{#1}}
\newcommand{\BM}[1]{\overline{\text{B}}_{#1}}



 \def \bb{ \atopwithdelims \llbracket \rrbracket}



%\usepackage{lipsum}

%% define your title in the usual way
\title{The Bruhat--Chevalley--Renner Order on the Set Partitions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Mahir Bilen Can\thanks{\href{mailto:mahirbilencan@gmail.com} {mahirbilencan@gmail.com}. Partially supported by a grant from Louisiana Board of Regents}\addressmark{1} \and Yonah Cherniavsky%\thanks{\href{mailto:email}{email}.}
\addressmark{2}}


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Tulane University, New Orleans, LA, USA\\ 
\addressmark{2}Department of Mathematics, Ariel University, Ariel, Israel}

%% 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 define combinatorially a partial order on the set partitions 
and show that it is equivalent to the Bruhat--Chevalley--Renner
order on the upper triangular matrices. 
By considering subposets consisting of set partitions with 
a fixed number of blocks, we introduce and investigate 
``Stirling posets''. As we show, the Stirling posets have a hierarchy 
and they glue together to give the whole set partition poset.
Moreover, we show that they (Stirling posets) are 
graded and EL-shellable. 
We offer various reformulations of their length functions
and determine the recurrences for their length generating series.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Borel monoid, Stirling numbers}

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


This extended abstract is based on our article~\cite{CC}, where one can find the complete proofs of our theorems.

Let $n$ be a nonnegative integer. 
A collection $S_1,\dots, S_r$ of non-empty subsets 
of an $n$-element set $S$ is said to 
be a set partition of $S$ if $S_i$'s ($i=1,\dots, r$) are mutually disjoint
and $\cup_{i=1}^r S_i = S$. In this case,
$S_i$'s are called the blocks of the partition.
If $n>0$ and $S=\{1,\dots, n\}$, the collection of all 
set partitions of $S$ is denoted by $\Pi_n$. 
We will often drop set parentheses and commas and just put 
vertical bars between blocks. 
If $B_1,\dots, B_k$ are the blocks of a set 
partition $\pi$ from $\Pi_n$, then the {\em standard form}
of $\pi$ is defined as $B_1|B_2|\cdots |B_k$, where 
we assume that $\min B_1 <\cdots < \min B_k$
and the elements of each block are listed in increasing order. 
For example, 
$\pi = 136 | 2459 | 78$ is a set partition from $\Pi_9$. 

The set $\Pi_n$ is known to be a host to many interesting 
algebraic and combinatorial structures. Among 
these structures is the following well-studied partial ordering: let $A$
and $A'$ be two set partitions of $S$.
$A$ is said to {\em refine} $A'$ if each block of $A$ 
is contained in some block of $A'$. 
This ``refinement ordering'' makes 
$\Pi_n$ into a lattice,
called the partition lattice, 
and by a result of Pudlak and Tuma~\cite{PudlakTuma}
it is known that every lattice is isomorphic to a sublattice of $\Pi_n$
for some $n$. 

A property that is shared
by all partition lattices is that their order complexes have the homotopy
type of a wedge of spheres. This important combinatorial topological property is 
seen by analyzing the labelings of the covering relations 
of the refinement ordering. Indeed, it follows as a consequence
of the fact that the refinement ordering is an ``edge lexicographically 
shellable'' (EL-shellable for short) poset as shown by Gessel 
(mentioned in~\cite{Bjorner80}) and by Wachs in~\cite{Wachs}. We postpone the proper
definition of EL-shellability to our preliminaries section but 
let us only mention very briefly that the property of EL-shellability
of a graded poset is a way of linearly ordering 
the maximal faces of the associated order complex,
say $F_1,\cdots,F_m$, in such a way that $F_k \cap \left( \cup_{i=1}^{k-1} F_i \right)$
is a nonempty union of maximal proper faces of $F_k$ ($k=2,\dots, m$).
Having this property immediately implies a plethora of results 
on the topology of the underlying poset, such as Cohen--Macaulayness. 
It is also helpful for better understanding the M\"obius function 
of the poset. 


Our purpose in this paper is to present 
another natural partial ordering on $\Pi_n$ 
and to show that our poset is EL-shellable as well. 
To define our ordering, we start with defining 
its most basic ingredient, namely the ``arc-diagram.''
It is customary to call a linearly ordered poset a {\em chain}. 
We identify chains by their Hasse diagrams, 
and we draw them in an unorthodox way, horizontally, by placing the smallest 
entry on the left and connecting the vertices by arcs.
For example, in \cref{F:chain1}, we depict the chain on 9 vertices,
where each arc represents a covering relation.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.75]
\node[below=.05cm] at (0,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (0) at (0,0) {};
\node[below=.05cm] at (1,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (1,0) {};
\node[below=.05cm] at (2,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (2,0) {};
\node[below=.05cm] at (3,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (3,0) {};
\node[below=.05cm] at (4,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (4,0) {};
\node[below=.05cm] at (5,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (5,0) {};
\node[below=.05cm] at (6,0) {$7$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (6) at (6,0) {};
\node[below=.05cm] at (7,0) {$8$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (7) at (7,0) {};
\node[below=.05cm] at (8,0) {$9$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (8) at (8,0) {};
\draw[color=black] (0) to [out=60,in=120] (1);
\draw[color=black] (1) to [out=60,in=120] (2);
\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (3) to [out=60,in=120] (4);
\draw[color=black] (4) to [out=60,in=120] (5);
\draw[color=black] (5) to [out=60,in=120] (6);
\draw[color=black] (6) to [out=60,in=120] (7);
\draw[color=black] (7) to [out=60,in=120] (8);
\end{tikzpicture}
\caption{A chain on 9 vertices.}
\label{F:chain1}
\end{center}
\end{figure}






\begin{defn}
By a {\em labeled chain} we mean a chain whose vertices are labeled by distinct numbers. 
An {\em arc-diagram on $n$ vertices} is a disjoint union of labeled chains where the labels are from $\{1,\dots,n\}$
and each label $i\in \{1,\dots, n\}$ is used exactly once. 
We depict an example in \cref{F:introexample}.  
\end{defn}

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.75]
\node[below=.05cm] at (0,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (0) at (0,0) {};
\node[below=.05cm] at (1,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (1,0) {};
\node[below=.05cm] at (2,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (2,0) {};
\node[below=.05cm] at (3,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (3,0) {};
\node[below=.05cm] at (4,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (4,0) {};
\node[below=.05cm] at (5,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (5,0) {};
\node[below=.05cm] at (6,0) {$7$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (6) at (6,0) {};
\node[below=.05cm] at (7,0) {$8$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (7) at (7,0) {};
\node[below=.05cm] at (8,0) {$9$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (8) at (8,0) {};
\draw[color=black] (6) to [out=120,in=60] (2);
\draw[color=black] (7) to [out=120,in=60] (0);
\draw[color=black] (4) to [out=120,in=60] (1);
\draw[color=black] (5) to [out=120,in=60] (4);
\draw[color=black] (8) to [out=120,in=60] (5);
\end{tikzpicture}
\caption{An arc-diagram on 9 vertices}
\label{F:introexample}
\end{center}
\end{figure}





It is easy to see that the arc-diagrams 
on $n$ vertices are in bijection with the 
elements of $\Pi_n$. Indeed, the map 
that is defined by grouping the labels 
of a chain into a set extends to define
a bijection from arc-diagrams to the 
set partitions. 
For example, under this bijection, 
the arc-diagram in \cref{F:introexample} 
corresponds to the set partition $18|2569|37|4$ 
in $\Pi_9$. In the light of this bijection,
from now on, we will work with 
the arc-diagrams instead of set partitions.
Let us use the notation $\mc{A}_n$ to denote 
the set of all arc-diagrams on $n$ vertices. 
The goal of our article is to endow $\mc{A}_n$ 
with a partial order and to use it to investigate 
certain subposets of $\mc{A}_n$. 
In particular, we will focus on the subposets
$\mc{A}_{n,k}\subset \mc{A}_n$, where the elements of 
$\mc{A}_{n,k}$ have exactly $k$ chains. 
We will call these subposets as the title of our paper~\cite{CC},
namely, the Stirling posets. 



Next we proceed to define the partial order that we will 
use throughout the paper. 
Let $A$ be an arc-diagram. We will identify
the vertices of $A$ with their labels. 
An {\em arc} in $A$ is a covering relation
in any of the labeled chains in $A$. 
If the arc denoted by $\alpha$ 
is a covering relation between the
vertices $i$ and $j$, then we write $\alpha = \{i,j\}$. 
In practice (while drawing the diagrams) we will 
always think of an arc as the graph of a 
connected concave down path in $\R^2$.
From this point of view, 
one of our most crucial conventions is that the arcs
of $A$ do not intersect each other if
they do not have to. We illustrate 
what we mean here in \cref{F:conventions}. 
If there is no possibility of continuously 
deforming two arcs $\alpha_1$ and $\alpha_2$ 
so that they do not intersect in $\R^2$, then 
they are said to {\em cross} each other. 
Otherwise, we call them {\em non-crossing} arcs.





\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.75]

\begin{scope}[xshift=-3.5cm]
\node[below=.05cm] at (0,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (0,0) {};
\node[below=.05cm] at (1,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (1,0) {};
\node[below=.05cm] at (2,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (2,0) {};
\node[below=.05cm] at (3,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (3,0) {};
\node[below=.05cm] at (4,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (4,0) {};
\draw[color=black] (1) to [out=60,in=120] (5);
\draw[color=black] (2) to [out=60,in=120] (3);
\node at (2,-1.25) {This is an arc-diagram.};

\end{scope}


\begin{scope}[xshift=3.5cm]
\node[below=.05cm] at (0,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (0,0) {};
\node[below=.05cm] at (1,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (1,0) {};
\node[below=.05cm] at (2,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (2,0) {};
\node[below=.05cm] at (3,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (3,0) {};
\node[below=.05cm] at (4,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (4,0) {};
\node[below=.05cm] at (1.5,3) {};
\draw[color=black] (1) to [out=60,in=120] (5);
\draw[color=black] (1,0)  ..controls (1.5,3) .. (2,0);
 \node at (2,-1.25) {This is not an arc-diagram.};

\end{scope}
\end{tikzpicture}
\caption{Conventions.}
\label{F:conventions}
\end{center}
\end{figure}

 
Before we proceed to explain our ordering on 
the arc-diagrams we will introduce a very useful 
function which will eventually lead us 
to a grading on our poset. 
This function is defined on all of the 
set of vertices, arcs, and chains of the arc-diagram. 
We will occasionally call a pair of non-crossing arcs
nested if both of the starting and the ending vertices
of one of the arcs stay below the other arc. 
 
\begin{defn}\label{depth}
Let $A$ be an arc-diagram and let $\alpha$ be 
a vertex, or an arc, or a chain from $A$. 
The depth of $\alpha$, denoted by $depth(\alpha)$ 
is the total number of arcs ``above'' $\alpha$. 
\end{defn}
Let us be more specific about what we mean by 
the word ``above'' in \cref{depth}: If 
$\alpha$ is a chain where $i$ is its leftmost 
vertex and $j$ is its rightmost vertex, then an arc $\{r,s\}$ 
is said to be above $\alpha$ if $r<i$ and $s>j$. 
For an example, see \cref{F:firstexample},
where every arc is of depth 0 and the vertex $4$
has depth 3.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.75]

\node[below=.05cm] at (0,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (0,0) {};
\node[below=.05cm] at (1,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (1,0) {};
\node[below=.05cm] at (2,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (2,0) {};
\node[below=.05cm] at (3,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (3,0) {};
\node[below=.05cm] at (4,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (4,0) {};
\node[below=.05cm] at (5,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (6) at (5,0) {};
\node[below=.05cm] at (6,0) {$7$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (7) at (6,0) {};
\draw[color=black] (1) to [out=60,in=120] (5);
\draw[color=black] (2) to [out=60,in=120] (6);
\draw[color=black] (3) to [out=60,in=120] (7);
 
\end{tikzpicture}
\caption{$depth(\{2,6\})=0$.}
\label{F:firstexample}
\end{center}
\end{figure}
Obviously, for every arc-diagram the depths of 
the first and the last vertices are zero, that is,  
$depth(1)=depth(n)=0$. 
Another simple observation that will be useful 
in what follows is that if an arc-diagram $A$ on 
$n$ vertices has $k$ arcs, 
then $A$ has exactly $n-k$ chains.
In this regard, let us point out that the number of set 
partitions in $\Pi_n$ with $k$ blocks,
hence the number of arc-diagrams in $\mc{A}_n$ 
with $k$ chains, is given by the Stirling numbers of the second kind;
it is easy to calculate these numbers by using the simple recurrence, 
$S(n,k) = S(n-1,k-1) +  kS(n-1,k)$.




Let $A$ and $B$ be two arc-diagrams on $n$ vertices. 
$B$ is said to cover $A$, and denoted by $A\prec B$, 
if it is obtained from $A$ by one of the following 
three operations:


\textbf{Rule 1. The shortening of an arc of $A$.} 
With this operation, we move exactly one endpoint
of an arc to another vertex so that the 
resulting arc is shortened as minimally as possible 
but the number of crossings does not change.
For example, see \cref{F:shortening}, where we
depict two examples. On the left, 
the left endpoint of the arc $\{1,4\}$ is moved to the 
nearest available position, which is the vertex $3$. 
Indeed, there is already an arc which emanates to the right 
from the vertex $2$.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.6]

\begin{scope}[xshift=-7.5cm]
\node[below=.05cm] at (-5,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-5,0) {};
\node[below=.05cm] at (-4,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-4,0) {};
\node[below=.05cm] at (-3,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (-3,0) {};
\node[below=.05cm] at (-2,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (-2,0) {};
\node[below=.05cm] at (-1,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (-1,0) {};
\draw[color=black] (1) to [out=60,in=120] (5);
\draw[color=black] (2) to [out=60,in=120] (3);
\node at (0,0) {$\preceq$};
\node[below=.05cm] at (1,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (1,0) {};
\node[below=.05cm] at (2,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (2,0) {};
\node[below=.05cm] at (3,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (3,0) {};
\node[below=.05cm] at (4,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (4,0) {};
\node[below=.05cm] at (5,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (5,0) {};
\draw[color=black] (1) to [out=60,in=120] (4);
\draw[color=black] (2) to [out=60,in=120] (3);
\end{scope}

\begin{scope}[xshift=7.5cm]
\node[below=.05cm] at (-4,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-4,0) {};
\node[below=.05cm] at (-3,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-3,0) {};
\node[below=.05cm] at (-2,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (-2,0) {};
\node[below=.05cm] at (-1,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (-1,0) {};
\draw[color=black] (1) to [out=60,in=120] (4);
\draw[color=black] (2) to [out=60,in=120] (3);
\node at (0,0) {$\preceq$};
\node[below=.05cm] at (1,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (1,0) {};
\node[below=.05cm] at (2,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (2,0) {};
\node[below=.05cm] at (3,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (3,0) {};
\node[below=.05cm] at (4,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (4,0) {};
\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\end{tikzpicture}
\caption{Two examples for shortening.}
\label{F:shortening}
\end{center}
\end{figure}





\textbf{Rule 2. Deleting a crossing.}
With this operation, we interchange
the rightmost endpoints of two crossing arcs
so that they become a pair of 
non-crossing and nested arcs;
we require in this operation that 
only one crossing is deleted as a result of 
this operation. 
For example, in \cref{F:interchanging},
the endpoints of $\{1,5\}$ and $\{2,6\}$ 
are interchanged. 
%Here we delete the crossing between the arcs $(1,5)$ and $(2,6)$.  
%We swap their endpoints getting instead of them the arcs $(1,6)$ and $(2,5)$.
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.75]


\node[below=.05cm] at (-7,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-7,0) {};
\node[below=.05cm] at (-6,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-6,0) {};
\node[below=.05cm] at (-5,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (-5,0) {};
\node[below=.05cm] at (-4,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (-4,0) {};
\node[below=.05cm] at (-3,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (-3,0) {};
\node[below=.05cm] at (-2,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (6) at (-2,0) {};
\node[below=.05cm] at (-1,0) {$7$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (7) at (-1,0) {};
\draw[color=black] (1) to [out=60,in=120] (5);
\draw[color=black] (2) to [out=60,in=120] (6);
\draw[color=black] (3) to [out=60,in=120] (7);
 
\node at (0,0) {$\preceq$};

\node[below=.05cm] at (1,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (12) at (1,0) {};
\node[below=.05cm] at (2,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (22) at (2,0) {};
\node[below=.05cm] at (3,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (32) at (3,0) {};
\node[below=.05cm] at (4,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (42) at (4,0) {};
\node[below=.05cm] at (5,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (52) at (5,0) {};
\node[below=.05cm] at (6,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (62) at (6,0) {};
\node[below=.05cm] at (7,0) {$7$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (72) at (7,0) {};
\draw[color=black] (12) to [out=60,in=120] (62);
\draw[color=black] (22) to [out=60,in=120] (52);
\draw[color=black] (32) to [out=60,in=120] (72);
 
 
 
\end{tikzpicture}
\caption{Interchanging two endpoints.}
\label{F:interchanging}
\end{center}
\end{figure}


As a non-example, we consider 
$A=\{1,4\}\{2,5\}\{3,6\}$, which has three crossings. 
The removal of the crossing between $\{1,4\}$ and $\{3,6\}$
according to the rule that we described in the previous paragraph 
gives $A'=\{1,6\}\{2,5\}\{3,4\}$, which has no crossings. 



\textbf{Rule 3. Adding a new arc.}
With this operation, a new arc is introduced between two
vertices in such a way that the new arc is not under any other (older) arcs
and the endpoints of the new arc are as far from each other as possible.  
In \cref{F:adding} we depict two examples. In 
the former one the new arc is $\{1,6\}$ and in the latter the
new arc is $\{3,6\}$. 
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.5]

\begin{scope}[xshift=-7.5cm]

\node[below=.05cm] at (-6,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-6,0) {};
\node[below=.05cm] at (-5,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-5,0) {};
\node[below=.05cm] at (-4,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (-4,0) {};
\node[below=.05cm] at (-3,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (-3,0) {};
\node[below=.05cm] at (-2,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (-2,0) {};
\node[below=.05cm] at (-1,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (6) at (-1,0) {};

\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (3) to [out=60,in=120] (4);
%\draw[color=black] (3) to [out=60,in=120] (7);
 
\node at (0,0) {$\preceq$};

\node[below=.05cm] at (1,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (12) at (1,0) {};
\node[below=.05cm] at (2,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (22) at (2,0) {};
\node[below=.05cm] at (3,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (32) at (3,0) {};
\node[below=.05cm] at (4,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (42) at (4,0) {};
\node[below=.05cm] at (5,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (52) at (5,0) {};
\node[below=.05cm] at (6,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (62) at (6,0) {};

\draw[color=black] (12) to [out=60,in=120] (62);
\draw[color=black] (22) to [out=60,in=120] (32);
\draw[color=black] (32) to [out=60,in=120] (42);
 
\end{scope}



\begin{scope}[xshift=7.5cm]

\node[below=.05cm] at (-6,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-6,0) {};
\node[below=.05cm] at (-5,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-5,0) {};
\node[below=.05cm] at (-4,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (-4,0) {};
\node[below=.05cm] at (-3,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (-3,0) {};
\node[below=.05cm] at (-2,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (5) at (-2,0) {};
\node[below=.05cm] at (-1,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (6) at (-1,0) {};

\draw[color=black] (1) to [out=60,in=120] (4);
\draw[color=black] (2) to [out=60,in=120] (3);
%\draw[color=black] (3) to [out=60,in=120] (7);
 
\node at (0,0) {$\preceq$};

\node[below=.05cm] at (1,0) {$1$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (12) at (1,0) {};
\node[below=.05cm] at (2,0) {$2$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (22) at (2,0) {};
\node[below=.05cm] at (3,0) {$3$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (32) at (3,0) {};
\node[below=.05cm] at (4,0) {$4$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (42) at (4,0) {};
\node[below=.05cm] at (5,0) {$5$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (52) at (5,0) {};
\node[below=.05cm] at (6,0) {$6$};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (62) at (6,0) {};

\draw[color=black] (12) to [out=60,in=120] (42);
\draw[color=black] (22) to [out=60,in=120] (32);
\draw[color=black] (32) to [out=60,in=120] (62);

\end{scope}
\end{tikzpicture}
\caption{Two examples of adding a new arc.}
\label{F:adding}
\end{center}
\end{figure}



From now on we will call the set $\mc{A}_n$ together 
with the transitive closure of the covering relations 
we just defined the {\em arc-diagram poset} and denote it by $(\mc{A}_n,\preceq)$.


Next, we define our first combinatorial
statistic.
\begin{defn}\label{D:statdd}
Let $A$ be an arc-diagram on $n$ vertices 
$v_1,\dots, v_n$ and with $k$ arcs 
$\alpha_1$, $\alpha_2$,...,$\alpha_k$. 
We define the depth-index of $A$, denoted by $\mathtt{t}(A)$ by the formula 
\[
\mathtt{t}(A)=\sum_{i=1}^k (n-i)
-\sum_{j=1}^n depth(v_j)+\sum_{m=1}^k depth(\alpha_m).
\]
\end{defn}


One of the main results of our paper is the following statement.  



\begin{thm}\label{T:main1}
For every positive integer $n$,
the arc-diagrams poset $(\mc{A}_n,\preceq)$  
is a bounded, graded, and an EL-shellable 
poset. The depth-index function is  
the grading of $\mc{A}_n$.  
\end{thm}




The proof of our theorem is at least as interesting as its statement. 
To explain it, we venture outside of combinatorics.
Here we assume some familiarity with elementary algebraic geometry. 
Let $\mt{Mat}_n$ denote the linear algebraic monoid of $n\times n$ 
matrices defined over $\C$. The group of invertible elements,
also called the {\em unit group}, of $\mt{Mat}_n$ is the 
general linear group of invertible $n\times n$ matrices. 
The (standard) Borel subgroup of $\mt{GL}_n$, denoted by $\mt{B}_n$,
is the subgroup $\mt{B}_n\subset \mt{GL}_n$ 
consisting of upper triangular matrices only. 
Then the doubled Borel group $\mt{B}_n\times \mt{B}_n$ acts on 
matrices via 
\begin{align}\label{A:BxB action}
(b_1,b_2) \cdot x  = b_1 x b_2^{-1}\qquad (b_1,b_2\in \mt{B}_n,\ x \in \mt{Mat}_n)
\end{align}
Clearly, $\mt{GL}_n$ is stable under this action. 
By the special case of an important result of Renner~\cite{Renner86},  
it is known that the action \eqref{A:BxB action} has finitely many orbits
and moreover the orbits of the action are parametrized 
by a finite inverse semigroup:
$\mt{Mat}_n = \bigsqcup_{\sigma \in R_n} \mt{B}_n \sigma \mt{B}_n$,
where $R_n$ is the finite monoid consisting of $n\times n$ 0/1 
matrices with at most one 1 in each row and each column.
The monoid $R_n$ is called the rook monoid; its elements are called rooks.
(The nomenclature comes from the fact that 
the elements of $R_n$ are in bijection with the 
non-attacking rook placements on an $n\times n$ chessboard.)
The Bruhat--Chevalley--Renner ordering on $R_n$
is the partial ordering that is defined by 
\begin{align}\label{A:BCR}
\sigma \leq \tau \iff  \mt{B}_n \sigma \mt{B}_n \subseteq  \overline{\mt{B}_n \tau \mt{B}_n}
\end{align}
for $\sigma,\tau \in R_n$. This poset structure on $R_n$ is well studied,~\cite{CanRenner}. 
It is known that $(R_n,\leq)$ is a graded, bounded, EL-shellable poset, see~\cite{Can19}. 


Towards a proof of \cref{T:main1},  
we make use of an important algebraic submonoid of $\mt{Mat}_n$; 
it is the closure in Zariski topology of the Borel subgroup $\mt{B}_n$ in
$\mt{Mat}_n$. We will call $\BM{n}$ the (standard) Borel submonoid. 
The first systematic study of the theory of Borel submonoids
as a part of more general but interrelated theory of parabolic monoids is undertaken 
by Putcha in~\cite{Putcha06}. Here we are focusing on one extreme case only. 

The Borel submonoid $\BM{n}$ consists of all upper triangular $n\times n$ 
matrices with complex entries. To see this, we use the standard 
(semidirect product) decomposition $\mt{B}_n = \mt{T}_n \mt{U}_n$, 
where $\mt{T}_n$ is the maximal torus consisting of invertible diagonal 
matrices and $\mt{U}_n$ is the unipotent subgroup consisting of 
upper triangular unipotent matrices. It is easy to check that 
$\mt{U}_n$ is already closed in $\mt{Mat}_n$, therefore, 
the Borel submonoid is determined (generated) by its
submonoids $\overline{\mt{T}}_n$ and $\mt{U}_n$. 
Here, $\overline{\mt{T}}_n$ is the diagonal submonoid consisting 
of all diagonal matrices. Note that $\overline{\mt{T}}_n$ is an affine 
toric variety and there is a one-to-one correspondence 
between the cones of its defining ``fan'' and its set of idempotents.
(An idempotent in a monoid is an element $e$ such that $e^2 = id$.)





Let $M$ be a monoid and let $1_M$ denote its neutral element. 
For us, a submonoid $N$ in a monoid $M$
is a subsemigroup $N\subset M$ such that $1_M\in N$.
In particular, $1_M$ is the identity element in $N$. 
Now, $\BM{n}$ is a submonoid of $\mt{Mat}_n$. 
Moreover, since it is closed under the two sided
action of $\mt{B}_n$, 
it has the induced Bruhat--Chevalley--Renner decomposition
\begin{align}\label{A:Rennerdecomposition}
\BM{n}=  \bigsqcup_{\sigma \in B_n} \mt{B}_n \sigma \mt{B}_n.
\end{align}
Here, $B_n$ is the set of all $n\times n$ rooks 
which are upper triangular in shape. 
Note that $B_n$ is a submonoid of $R_n$ according
to our definition. We call it the {\em upper triangular rook monoid}
(on $n$ letters). 
In \cref{F:B3}, we depict the induced Bruhat--Chevalley--Renner ordering on $B_3$. 

\begin{figure}[htp]
\begin{center}

\scalebox{.68}{
\begin{tikzpicture}[scale=.75]

\begin{scope}[shift={(0,30)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (2);
\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}



\begin{scope}[shift={(-8,25)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (2);
\draw[color=black] (2) to [out=60,in=120] (3);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}


\begin{scope}[shift={(0,25)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (2);
%\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(8,25)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
%\draw[color=black] (1) to [out=60,in=120] (2);
\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(-8,20)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (2);
\draw[color=black] (2) to [out=60,in=120] (4);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(0,20)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (4);
\draw[color=black] (2) to [out=60,in=120] (3);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(8,20)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (3);
%\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(-14,15)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (2);
%\draw[color=black] (2) to [out=60,in=120] (3);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(-5,15)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
%\draw[color=black] (1) to [out=60,in=120] (2);
\draw[color=black] (2) to [out=60,in=120] (3);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(5,15)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (3);
%\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (2) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(14,15)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
%\draw[color=black] (1) to [out=60,in=120] (2);
%\draw[color=black] (2) to [out=60,in=120] (3);
\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}


\begin{scope}[shift={(-5,10)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (3);
%\draw[color=black] (2) to [out=60,in=120] (3);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(5,10)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
%\draw[color=black] (1) to [out=60,in=120] (2);
\draw[color=black] (2) to [out=60,in=120] (4);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(0,5)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
\draw[color=black] (1) to [out=60,in=120] (4);
%\draw[color=black] (2) to [out=60,in=120] (3);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}

\begin{scope}[shift={(0,0)}]
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (-1.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (-.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (.5,0) {};
\node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (1.5,0) {};
%\draw[color=black] (1) to [out=60,in=120] (2);
%\draw[color=black] (2) to [out=60,in=120] (3);
%\draw[color=black] (3) to [out=60,in=120] (4);
\end{scope}


\draw[-, ultra thick] (-8,25) to (0,30);
\draw[-, ultra thick] (0,25) to (0,30);
\draw[-, ultra thick] (8,25) to (0,30);
\draw[-, ultra thick] (8,20) to (8,25);
\draw[-, ultra thick] (8,20) to (0,25);

\draw[-, ultra thick] (0,20) to (8,25);
\draw[-, ultra thick] (0,20) to (-8,25);
\draw[-, ultra thick] (-8,20) to (0,25);
\draw[-, ultra thick] (-8,20) to (-8,25);

\draw[-, ultra thick] (14,15) to (8,20);
\draw[-, ultra thick] (5,15) to (8,20);
\draw[-, ultra thick] (5,15) to (0,20);
\draw[-, ultra thick] (5,15) to (-8,20);
\draw[-, ultra thick] (-5,15) to (0,20);
\draw[-, ultra thick] (-14,15) to (-8,20);

\draw[-, ultra thick] (5,10) to (14,15);
\draw[-, ultra thick] (5,10) to (5,15);
\draw[-, ultra thick] (5,10) to (-5,15);

\draw[-, ultra thick] (-5,10) to (5,15);
\draw[-, ultra thick] (-5,10) to (-5,15);
\draw[-, ultra thick] (-5,10) to (-14,15);
\draw[-, ultra thick] (0,5) to (-5,10);
\draw[-, ultra thick] (0,5) to (5,10);
\draw[-, ultra thick] (0,0) to (0,5);


\end{tikzpicture}
}
\end{center}
\caption{Bruhat--Chevalley--Renner order on $\mc{A}_4$.}
\label{F:B3}
\end{figure}




Another subsemigroup that is very useful for our purposes
is the semigroup of all nilpotent rooks from $B_n$,
which we call the \emph{standard nilpotent rook semigroup}, denoted by $B_n^{nil}$. 
In fact, for $n>0$, 
it is not difficult to see that $(B_n^{nil},\leq)$ is isomorphic, 
as a poset, to the upper triangular rook monoid $(B_{n-1},\leq)$. 
By going through the same vein, we observe that the 
semigroup of nilpotent elements in $\BM{n}$ is isomorphic, as an algebraic variety, to $\BM{n-1}$. 







The sets of idempotents of the monoids $\BM{n}$ and $\overline{\mt{T}}_n$ are the same; 
they consist of $n\times n$ diagonal matrices with 0/1 entries. 
Let us denote this common set of idempotents by $E_n$. 
It is not difficult to see that $E_n$ is a Boolean lattice 
with respect to the ordering
$$
e\leq f \iff e f = fe =e\ \hspace{.5cm} (e,f\in E_n).
$$
In particular, $E_n$ has $2^{n}$ elements. 
We denote by $E_{n,k}$ the set of idempotents from $E_n$ 
whose matrix rank is $k$ and we define the following subvariety 
the Borel monoid:
\begin{align}\label{D:Stirlingmonoid}
\mt{B}_{n,k} :=  \bigcup_{e\in E_{n,k}} \overline{\mt{B}_n e \mt{B}_n}.
\end{align}
Notice that, except for $k\in \{0,n\}$, the variety 
$\mt{B}_{n,k}$ is not irreducible.
Obviously, $\mt{B}_{n,n}$ is equal to $\BM{n}$
and $\mt{B}_{n,0} = \overline{\mt{B}_n \cdot \mathbf{0} \cdot \mt{B}_n} =\{ \mathbf{0}\}$.




Next, we list some important properties of our varieties $\mt{B}_{n,k}$ and the corresponding posets $B_{n,k}$.
\begin{enumerate}
\item For $k=0,\dots, n$, the number of irreducible components of $\mt{B}_{n,k}$
is ${n \choose k}$ and they are all equal dimensional.
\item $\mt{B}_{n,k}$'s form a flag 
$\{ \mathbf{0}\} = \mt{B}_{n,0} \subset \mt{B}_{n,1} \subset \cdots \subset \mt{B}_{n,n-1} \subset 
\mt{B}_{n,n} = \BM{n}$.
\item Each $\mt{B}_{n,k}$ ($k=0,\dots, n$) has the structure of an algebraic 
semigroup.
\item Each $\mt{B}_{n,k}$ ($k=0,\dots, n$)
has a Renner decomposition 
\begin{align}\label{A:RennerStirlingdecomposition}
\mt{B}_{n,k}=  \bigsqcup_{\sigma \in B_{n,k}} \mt{B}_n \sigma \mt{B}_n,
\end{align}
where $B_{n,k}$ is a finite subsemigroup of $B_n$ and it consists of 
rooks whose matrix rank is at most $k$. 
Moreover, with respect to induced Bruhat--Chevalley--Renner ordering
the poset $(B_{n,k},\leq )$ is a 
union of lower intervals of equal lengths in $B_n$.
\item The subsemigroups $B_{n,k}\subset B_n$ form a 
flag $\{\mathbf{0}\}\subset B_{n,1}\subset \cdots \subset B_{n,n}=B_n$
and moreover the number of elements of $B_{n,k}\setminus B_{n,k-1}$ is 
given by the Stirling number $S(n+1,n+1-k)$. 
\item The Bruhat--Chevalley--Renner ordering
restricted to the subsets of the form $B_{n,k}\setminus B_{n,k-1}$
(for $k=1,\dots, n$) is graded
with a minimum and there are ${n \choose k}$ maximal elements. 
Each maximal interval in this poset is an interval in $B_n$,
therefore, it is an EL-shellable poset. 
\end{enumerate}


As an application of our study of the 
Bruhat--Chevalley--Renner ordering on $B_{n,k}$'s 
we will prove the following theorem, which, in turn, 
will give us the proof of \cref{T:main1}. 
Indeed, the poset $(B_n^{nil},\leq)$ is a lower interval
in the rook monoid, and $R_n$ is known
to be an EL-shellable poset. 

\begin{thm}\label{T:Borelmonoid}
The arc-diagram poset $(\mc{A}_n,\preceq)$ is isomorphic to $(B_n^{nil},\leq)$, hence, it is a bounded, graded, and EL-shellable poset.
\end{thm}




Next, we show that the arc-diagram poset is a 
disjoint union of EL-shellable subposets, 
which are not necessarily intervals. The cardinalities of 
these subposets will be given by the Stirling numbers of 
the second kind. 


\begin{thm}\label{T:Borelmonoid2}
If $\mc{A}_{n,k}$ denotes the set of arc-diagrams 
with $n-k$ chains, then $(\mc{A}_{n,k},\preceq)$
is a graded EL-shellable poset with a unique minimum
and ${n-1 \choose k}$ maximum elements. 
\end{thm}




\begin{defn}
The $(n,k)$-th Stirling poset is the poset $(\mc{A}_{n,k},\preceq)$. 
By abusing notation, we will denote it by $\mc{A}_{n,k}$. 
\end{defn}


To contrast $\mc{A}_{n,k}$ with the corresponding subposet 
in the refinement ordering on set partitions, 
let us mention that any two unequal set partitions of $\{1,\dots, n\}$
with the same number of blocks are not comparable. 
In other words, the collection of 
arc-diagrams with the same number of chains do not form an interesting 
poset with respect to refinement ordering.  
On the other hand, similarly to the refinement ordering,
in $(\mc{A}_n,\preceq)$, the Stirling subposets have a hierarchy in the 
sense that $\mc{A}_{n,k}$ lies above $\mc{A}_{n,k-1}$. Indeed,  
if $x$ and $y$ are two maximal elements from $\mc{A}_{n,k}$
and $\mc{A}_{n,k-1}$, respectively, then $\mathtt{t}(x) - \mathtt{t}(y) = n-k$.
From a similar vein, if $x_0$ and $y_0$ denotes, respectively, 
the minimum elements of $\mc{A}_{n,k}$ and $\mc{A}_{n,k-1}$, 
then $\mathtt{t}(x_0)-\mathtt{t}(y_0) = k$. 
%\vspace{.5cm}
It is not difficult to verify that when $k=1$, $\mc{A}_{n,1}$ is 
the ``fish net'' as in \cref{F:fishnet},
hence every interval in $\mc{A}_{n,1}$ is a lattice. 
As $k$ increases, $\mc{A}_{n,k}$ becomes 
more complicated. 
Nevertheless, it is a pleasantly 
surprising fact that $\mc{A}_{n,2}$ 
is a lattice as well. 
The smallest integer $n$ for which $\mc{A}_{n,k}$
has a non-lattice subinterval is $n=5$ (and $k=3$).
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.45]

\begin{scope}[xshift=-12cm, yshift=8cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (1,0) to [out=60,in=120] (2,0);
\end{scope}


\begin{scope}[xshift=-4cm, yshift=8cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (0,0) to [out=60,in=120] (1,0);
%\draw[thick,blue,-] (0,0) ..controls  (.5,.5) .. (1,0);
\end{scope}

\begin{scope}[xshift=4cm, yshift=8cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (-1,0) to [out=60,in=120] (0,0);
%\draw[thick,blue,-] (-1,0) ..controls  (-.5,.5) .. (0,0);
\end{scope}
\begin{scope}[xshift=12cm, yshift=8cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (-2,0) to [out=60,in=120] (-1,0);
%\draw[thick,blue,-] (-2,0) ..controls  (-1.5,.5) .. (-1,0);
\end{scope}
%%

\begin{scope}[xshift=-8cm, yshift=4cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (0,0) to [out=60,in=120] (2,0);
%\draw[thick,blue,-] (0,0) ..controls  (1,1) .. (2,0);
\end{scope}
\begin{scope}[xshift=0cm, yshift=4cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (-1,0) to [out=60,in=120] (1,0);
%\draw[thick,blue,-] (-1,0) ..controls  (0,1) .. (1,0);
\end{scope}
\begin{scope}[xshift=8cm, yshift=4cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (-2,0) to [out=60,in=120] (0,0);
%\draw[thick,blue,-] (-2,0) ..controls  (-1,1) .. (0,0);
\end{scope}
%%

\begin{scope}[xshift=-4cm, yshift=0cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (-1,0) to [out=60,in=120] (2,0);
%\draw[thick,blue,-] (-1,0) ..controls  (.5,1.25) .. (2,0);
\end{scope}
\begin{scope}[xshift=4cm, yshift=0cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (-2,0) to [out=60,in=120] (1,0);
%\draw[thick,blue,-] (-2,0) ..controls  (-.5,1.25) .. (1,0);
\end{scope}
%%

\begin{scope}[xshift=0cm, yshift=-4cm]
\node at (-2,0) {$\bullet$}; 
\node at (-1,0) {$\bullet$}; 
\node at (0,0) {$\bullet$}; 
\node at (1,0) {$\bullet$}; 
\node at (2,0) {$\bullet$}; 
\draw[color=black] (-2,0) to [out=60,in=120] (2,0);
%\draw[thick,blue,-] (-2,0) ..controls  (0,1.25) .. (2,0);
\end{scope}

\draw[black,-] (-12, 8) to (0,-4);
\draw[black,-] (12, 8) to (0,-4);
\draw[black,-] (-4, 8) to (4,0);
\draw[black,-] (4, 8) to (-4,0);
\draw[black,-] (4, 8) to (8,4);
\draw[black,-] (-4, 8) to (-8,4);
 
\end{tikzpicture}
\end{center}
\caption{The Stirling poset $\mc{A}_{5,1}$.}
\label{F:fishnet}
\end{figure}





\begin{thm}\label{T:(n,2) is boolean}
Let $B(n-1)$ denote the Boolean lattice of all subsets of $\{1,\dots, n-1\}$.
Then, for every integer $n \geq 2$, the $(n,2)$-th Stirling poset
$\mc{A}_{n,2}$ is isomorphic to the ``topless'' poset $B(n-1) \setminus \{\{1,\dots, n-1\}\}$.
\end{thm}









Next, we will discuss the length generating function 
of the $(n,k)$-th Stirling poset. Let us denote by $\mathtt{t}_k$
the length function on $\mc{A}_{n,k}$.
Clearly, $\mathtt{t}_k$ is equal to an appropriate shift of $\mathtt{t}$. More precisely, 
let $A$ be an element from $\mc{A}_{n,k}$.  
If we view $A$ as an element of $\mc{A}_n$, then 
it is clear that $\mathtt{t}(A)=\mathtt{t}_k(A) + {k\choose 2}$
since the unique minimum of $\mc{A}_{n,k}$ has depth-index ${k \choose 2}$.  
To be able to treat all length generating functions $\mathtt{t}_k$ ($k=0,\dots, n$) together, 
we define 
\begin{align}\label{A:analog of stirling}
{n \bb k} := \sum_{A \in \mc{A}_{n,k}} q^{\mathtt{t}(A)}.
\end{align}
Obviously, \eqref{A:analog of stirling} is a $q$-analog of the Stirling numbes of the second kind.


\begin{thm}\label{T:gen func}
For positive integers $n$ and $k$ such that $0\leq k \leq n+1$
the following recurrence holds true:
\begin{align*}
{n+1 \bb k} = q^{k} {n \bb k} + [n+1-k]_q q^{k} {n\bb k-1},
\end{align*}
where $[k]_q$ is the polynomial $1+q+\cdots + q^{k-1}$. 
The initial conditions are ${m \bb 0 } = 1$ for all $m\in \N$.
In addition, we assume that 
$
{m \bb k } = 0\; \text{ if $k<0$ or $k > m$.}
$
\end{thm}


It turns out that our depth-index function is closely related to another well-studied statistic called the intertwining 
number of a set partition, see~\cite{CCR}.
Also, there are various $(p,q)$-analogs of Stirling numbers of the second kind, see~\cite{WachsWhite}. 
It would be interesting to study these $(p,q)$-analogs as well as other poset 
theoretic properties of the set-partitions poset under the refinement ordering 
in relation with our Stirling posets and Borel monoids.


In this paper, we considered the Borel submonoid of $\mt{Mat}_n$, which is a
$\mt{GL}_n\times \mt{GL}_n$-equivariant embedding of the symmetric space $(\mt{GL}_n\times \mt{GL}_n)/\textrm{diag}(\mt{GL}_n)$. 
By using other embeddings of other symmetric spaces, one can build varieties that are similar to Borel monoids having analogous combinatorial properties. 
For example, let $\mt{Sym}_n$ denote the space of $n\times n$ symmetric matrices.
We view $\mt{Sym}_n$ as a $\mt{GL}_n$-equivariant embedding of $\mt{GL}_n/\mt{O}_n$ in $\mt{Mat}_n$. 
Then we have the Borel monoid-like subvariety $\mt{C}_n:=\overline{ \{ b b^T: b \in \mt{B}_n \}}$ in $\mt{Sym}_n$;
it is equal to the Zariski closure of the orbit of the identity element $1\in \mt{Sym}_n$ under the congruence action of 
$\mt{B}_n$ on $\mt{Sym}_n$. It is known that the inclusion posets of $\mt{B}_n$-orbit closures 
in symmetric matrices, as well as in skew-symmetric matrices are EL-shellable, see~\cite{CCT1,CCT2,CT}. 



%Finally, a reference to equation~\eqref{eqn:eq1}. And a reference to \cref{fig:plot}.

%\acknowledgements{\lipsum[20]}

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

%\bibliography{references.bib}
%\bibliographystyle{plain}


\printbibliography


\end{document}
