remarkRemark hypothesisHypothesis claimClaim $k$-noncrossing RNA StructuresV.
Moulton and T. Wu ex_supplement

# Posets and Spaces of $k$-noncrossing RNA Structures ††thanks: Submitted to
the editors DATE.

Vincent Moulton School of Computing Sciences, University of East Anglia,
Norwich, U.K<EMAIL_ADDRESS>Taoyang Wu School of Computing Sciences,
University of East Anglia, Norwich, U.K<EMAIL_ADDRESS>
###### Abstract

RNA molecules are single-stranded analogues of DNA that can fold into various
structures which influence their biological function within the cell. RNA
structures can be modelled combinatorially in terms of a certain type of graph
called an RNA diagram. In this paper we introduce a new poset of RNA diagrams
$\mathcal{B}^{r}_{f,k}$, $r\geq 0$, $k\geq 1$ and $f\geq 3$, which we call the
Penner-Waterman poset, and, using results from the theory of
multitriangulations, we show that this is a pure poset of rank
$k(2f-2k+1)+r-f-1$, whose geometric realization is the join of a simplicial
sphere of dimension $k(f-2k)-1$ and an $\left((f+1)(k-1)-1\right)$-simplex in
case $r=0$. As a corollary for the special case $k=1$, we obtain a result due
to Penner and Waterman concerning the topology of the space of RNA secondary
structures. These results could eventually lead to new ways to study
landscapes of RNA $k$-noncrossing structures.

###### keywords:

RNA structures, $k$-noncrossing pseudoknots, Multitriangulations, Poset
topology

05C99, 06A99, 92D20

##  1 Introduction

Ribonucleic acid (RNA) is a single-stranded polymeric molecule that is
essential in various biochemical processes within the cell. The primary
structure of an RNA molecule is a linear sequence of four nucleotides, also
known as bases and usually denoted by A (adenine), C (cytosine), G (guanine)
and U (uracil). In nature, RNA molecules fold into structures which are
intimately related to their biological function. These structures arise from
the linear sequence folding back onto itself which is possible since the non-
adjacent bases A/U and G/C can form bonds or base-pairs. Motivated by this
phenomenon, there has been a great deal of interest in the prediction of RNA
structures [6], and also in understanding combinatorial properties of these
structures over the past three decades [3, 8, 13, 17, 19].

RNA structures are commonly represented by binary diagrams, simple graphs
drawn in the plane in which each base is represented by a vertex and the
underlying linear molecule is represented by a collection of edges along a
horizontal line. In addition, the base-pairs are represented by semi-circles
or arcs in the upper halfplane such that arcs do not connect the last and
first bases and no two arcs are incident with the same vertex (see e.g. Fig.
1(i)). In the special case where the diagram representing an RNA structure has
no intersecting arcs, the RNA structure is also known as a secondary
structure. RNA secondary structures are important as they often form a
backbone structure for an RNA molecule, and their nested structure facilitates
their prediction using free-energy models [6, pp. 1-31].

Figure 1:  (i) An RNA secondary structure with 9 bases (represented by black
vertices) and 3 base-pairs (represented by arcs). In this diagram, the arc
$(1,4)$ covers free sites 2 and 3, and the arc (6,8) is below the arc (5,9).
(ii) An RNA pseudoknot that is a $2$-noncrossing structure with 3 base-pairs.

In [13] Penner and Waterman introduce and study a certain space of RNA
secondary structures. In combinatorial language, this space can be considered
as the geometric realization of a certain finite poset $\mathcal{B}^{r}_{f}$
of RNA secondary structures for $r\geq 0$ and $f\geq 3$ whose definition we
now recall. We call a base in a diagram a free site if it is not contained in
any arc, and an arc $e$ tautological if either $e$ covers precisely one free
site or there exists an arc below $e$ that covers the same set of free sites
as $e$. The poset $\mathcal{B}^{r}_{f}$ then consists of all RNA secondary
structures whose diagrams have $f$ free sites and no more than $r$
tautological arcs. For example, the RNA secondary structure in Fig. 1(i) is in
$\mathcal{B}^{2}_{3}$. The poset relation on $\mathcal{B}^{r}_{f}$ is induced
by _arc suppression_ , that is, removal of an arc and the two sites which it
contains from a diagram (for the formal definition see Section 2.1). In Fig.
2(i) we present the Hasse diagram of the poset $\mathcal{B}^{0}_{4}$.

Figure 2:  (i) The Hasse diagram of the poset $\mathcal{B}^{0}_{4}$. (ii) The
geometric realization of the poset $\mathcal{B}^{0}_{4}$. Here the vertices
$x_{i}$ and $x_{ij}$ correspond to RNA secondary structures $S_{i}$, $S_{ij}$
with the same indices. (iii) The Hasse diagram of the poset $\mathcal{T}_{5}$,
whose elements are the triangulations of a pentagon. The poset isomorphism
between $\mathcal{B}^{0}_{4}$ and $\mathcal{T}_{5}$ mentioned in the text maps
each secondary structure in $\mathcal{B}^{0}_{4}$ to the triangulation in
$\mathcal{T}_{5}$ with the same indices.

Penner and Waterman show that the poset $\mathcal{B}^{0}_{f}$ is isomorphic to
what they call the arc poset $\mathcal{T}_{f+1}$ on a $(f+1)$-gon [13,
Proposition 3], whose elements can be considered as the set of triangulations
of a $(f+1)$-gon. This enables them to then show that the geometric
realization of the poset $\mathcal{B}^{0}_{f}$ is a topological sphere of
dimension $f-3$. For example, in Fig. 2(iii) the poset $\mathcal{T}_{5}$ is
pictured together with the geometrical realization of the poset
$\mathcal{B}^{0}_{4}$, which is the simplicial complex consisting of ten
1-simplices as pictured in Fig. 2 (ii). This complex is clearly homeomorphic
to a 1-dimensional sphere.

###  1.1 The Penner-Waterman poset

By definition, diagrams corresponding to structures in the poset
$\mathcal{B}^{r}_{f}$ contain no arcs that pairwise intersect. However, RNA
molecules can fold into structures whose corresponding diagrams contain pairs
of crossing arcs. In this case, the RNA structure is no longer a secondary
structure but what is commonly called an RNA pseudoknot. RNA pseudoknots are
wide-spread in nature and have important functions [3]. We are therefore
interested in how to extend Penner and Waterman’s analysis to these more
complicated structures.

To this end, we focus on a special type of pseudoknot called a _$k$
-noncrossing structure_ (see, e.g. [8]). This is an RNA structure whose
diagram does not contain $(k+1)$ arcs that are pairwise mutually crossing. See
Fig. 1(ii) for an example of $2$-noncrossing pseudoknot; among the three arcs
in the pseudoknot, only arcs $(1,4)$ and $(5,9)$ do not form a crossing pair.
Note that $k$-noncrossing structures are also called $(k+1)$-noncrossing
structures by some authors (e.g. [8]). RNA $k$-noncrossing structures have
been studied extensively in the past decade (see, e.g. [3], and the reference
therein), and they have interesting combinatorial properties (see, e.g. [17]).

Figure 3:  (i) A $3$-noncrossing diagram $S_{1}$ in $\mathcal{P}^{2}_{3,3}$,
which is not regular as $(1,7)$ and $(2,8)$ are two mutually crossing arcs
both incident with the interval consisting of the non-free sites $1$ and $2$.
(ii) A $2$-noncrossing diagram $S_{2}$ in $\mathcal{B}^{2}_{3,2}$ which is
regular and equivalent to $S_{1}$.

In this paper, we define and study a new poset $\mathcal{B}^{r}_{f,k}$ ($k\geq
1$, $f\geq 3$, $r\geq 0$) of binary RNA $k$-noncrossing structures whose
diagrams are regular and which contain exactly $f$ free sites and have
tautological number at most $r$. Intuitively, a regular diagram is one in
which there are no two crossing arcs that are both incident with the same
interval of non-free sites (see Fig. 3(ii) for an example and Section 3 for
the precise definition). We call the poset $\mathcal{B}^{r}_{f,k}$ the Penner-
Waterman poset since, as we shall see later,
$\mathcal{B}^{r}_{f,1}=\mathcal{B}^{r}_{f}$.

The two main results of this paper concern the Penner-Waterman poset. The
first gives the structure of the geometric realization of
$\mathcal{B}^{0}_{f,k}$ (see Section 2 for the definition of this term).

######  Theorem 1.1.

For two integers $k\geq 1$ and $f\geq 3$ with $f\geq 2k$, the geometric
realization of $\mathcal{B}^{0}_{f,k}$ is the join of a simplicial sphere of
dimension $k(f-2k)-1$ and an $\left((f+1)(k-1)-1\right)$-simplex.

An illustration of Theorem 1.1 is presented in Fig. 4 for a subposet of
$\mathcal{B}^{0}_{5,2}$ (the full poset is too large to include). Our second
main result concerns the structure of $\mathcal{B}_{f,k}^{r}$. Recall that
rank of a (finite) poset is the length of a maximum length in the poset, and
that the poset is pure in case all of its maximal chains have the same length.

######  Theorem 1.2.

For any $r\geq 0$, $f\geq 3$ and $k\geq 1$ with $f\geq 2k$, the Penner-
Waterman poset $\mathcal{B}_{f,k}^{r}$ is pure and of rank $k(2f-2k+1)+r-f-1$.

As a corollary, we also obtain an independent proof of Penner and Waterman’s
result mentioned above concerning the topology of $\mathcal{B}^{0}_{f}$.

Figure 4:  (i) The Hasse diagram of a subposet of $\mathcal{B}^{0}_{5,2}$.
(ii) The geometric realization of the subposet in (i), which is a simplicial
sphere of dimension one. Here the vertices $x_{i}$ and $x_{ij}$ correspond to
RNA secondary structures $S_{i}$, $S_{ij}$ with the same indices.

###  1.2 Outline of the proof of Theorems 1.1 and 1.2

As the proof of our main results is quite technical and involved (see Section
8), we now provide an overview to guide the reader through it. Our main tool
is the introduction of an algebraic relationship which associates a certain
type of symmetric integral matrix to $k$-noncrossing structure which we call
its block matrix. Intuitively, these matrices encode the incidence
relationship between blocks of an RNA structure, where a block is a maximal
interval of non-free sites. For instance, in the diagram $S_{1}$ in Fig. 3 the
interval consisting the of non-free sites $6$, $7$, and $8$ is a block; there
are two arcs between this block and the block consisting of the non-free sites
$1$ and $2$, which is encoded as an entry with value $2$ in the associated
block matrix. We took this approach since Penner and Waterman used rooted
fattrees to prove their results but, even though fattrees can be generalized
to fatgraphs (see e.g [14]), we could not find a way to utilize this
generalization in our proofs.

Figure 5: An outline of the proof of the main results. Here
$\mathcal{P}^{r}_{f,k}$ is the poset of proper $k$-noncrossing diagrams with
$f$ free sites whose tautology number is at most $r$. The Penner-Waterman
poset $\mathcal{B}^{r}_{f,k}$ contains all regular diagrams in
$\mathcal{P}^{r}_{f,k}$, and $\mathcal{M}^{r}_{f+1,k}$ is the poset consisting
of the block matrices of the diagrams in $\mathcal{B}^{r}_{f,k}$, which are
certain non-negative integral $k$-noncrossing matrices of order $f+1$. Next,
$\mathcal{S}_{f+1,k}$ is the poset of all (not necessarily binary)
$k$-noncrossing diagrams with $f+1$ free sites. Among the three poset
homomorphisms, $\rho$ is surjective whilst both $\sigma$ and $\tau$ are
isomorphisms.

Our proof proceeds as follows (see Fig. 5). The first goal is to show that
$\mathcal{B}^{r}_{f,k}$ is isomorphic to the poset $\mathcal{M}^{r}_{f+1,k}$
of a certain family of symmetric integral matrices of order $f+1$ (Theorem
7.1). To this end, we introduce the set $\mathcal{P}^{r}_{f,k}$ of proper
diagrams, a superset of $\mathcal{B}^{r}_{f,k}$ consisting of binary diagrams
in which each arc covers at least one, but not all of the free sites in the
diagram (see Fig. 3 for an example), and consider the map $\rho$ which takes
each diagram in $\mathcal{P}^{r}_{f,k}$ to its block matrix. To show that
$\rho$ is surjective, we begin by defining an equivalence relation $\sim$ on
$\mathcal{P}^{r}_{f,k}$, where $S\sim S^{\prime}$ holds for two proper
diagrams $S$ and $S^{\prime}$ if and only if there exists a bijection between
the arcs of $S$ to those of $S^{\prime}$ that preserves the free sites below
each arc. We then show that two proper diagrams are equivalent if and only if
they have the same block matrix (Theorem 5.9), and that there exists a unique
regular diagram within each equivalence class of $\sim$, namely the diagram
with the minimum number of crossing arc pairs among all proper diagrams within
that class (Theorem 6.7). Using a characterisation of integral matrices that
can be realized as the block matrix of a proper diagram (Theorem 7.4), we then
show that the collection of preimages $\\{\rho^{-1}({\bf M})\,:\,{\bf
M}\in{\mathcal{M}}^{r}_{f+1,k}\\}$ forms a partition of
$\mathcal{P}^{r}_{f,k}$, and that each preimage is precisely one of the
equivalence classes of $\sim$. From this it follows that $\rho$ is surjective
and, moreover, that its restriction to $\mathcal{B}^{r}_{f,k}$, denoted by
$\sigma$, is a poset isomorphism between $\mathcal{B}^{r}_{f,k}$ and
${\mathcal{M}}^{r}_{f+1,k}$ (Theorem 7.1).

Our second goal is to show that $\mathcal{B}^{0}_{f,k}$ is isomorphic to
$\mathcal{S}_{f+1,k}$, the poset of all (not necessarily binary)
$k$-noncrossing diagrams with $f+1$ free sites (Theorem 7.6). To do this, we
show that mapping a diagram in $\mathcal{S}_{f+1,k}$ to its adjacency matrix
gives a poset isomorphism $\tau$ from $\mathcal{S}_{f+1,k}$ to
$\mathcal{M}^{0}_{f+1,k}$ (Proposition 2.1). Composing $\sigma$ with the
inverse of the map $\tau$ in case $r=0$ then gives a poset isomorphism between
$\mathcal{B}^{0}_{f,k}$ and $\mathcal{S}_{f+1,k}$.

The proof of our main results is then completed by exploiting an interesting
connection between $\mathcal{S}_{f+1,k}$ and a certain poset of
multitriangulations of a polygon [15], as detailed in Lemma 8.3. Since the
topology of the poset of multitriangulations is well understood, this enables
us to obtain the topology of $\mathcal{B}^{0}_{f,k}$ in Theorem 1.1 and, as a
corollary, the fact that $\mathcal{B}^{r}_{f,k}$ is pure in Theorem 1.2.

###  1.3 Organization of the rest of the paper

In Section 2 we collect together some basic terminology and facts concerning
diagrams and simplicial complexes. We then introduce block matrices and
regular diagrams in Section 3, and the Penner-Waterman poset and
$\mathcal{M}^{r}_{f+1,k}$ in Section 4. In Section 5 we define the equivalence
relation $\sim$ on proper diagrams, and in Section 6 we show that there exists
a unique regular diagram within each equivalence class of $\sim$. In Section 7
we show that the map $\sigma$ is a poset isomorphism between the Penner-
Waterman poset $\mathcal{B}^{r}_{f,k}$ and the poset
$\mathcal{M}^{r}_{f+1,k}$, and that $\tau^{-1}\sigma$ gives a poset
isomorphism between $\mathcal{B}^{0}_{f,k}$ and $\mathcal{S}_{f+1,k}$. Then in
Section 8 we prove our main results by considering the above-mentioned
relationship between $\mathcal{S}_{f+1,k}$ and multitriangulations. In the
last section, we conclude with a brief discussion of some possible future
directions.

##  2 Preliminaries

###  2.1 Diagrams

In this paper, $n$ and $k$ are two positive integers with $n\geq 4$ and $k\geq
1$, unless stated otherwise.

Motivated by [7, 13], a molecule diagram, or just diagram, is a graph with
vertex set $\\{1,\dots,n\\}$, where each vertex is called a site. It consists
of base-pair arcs, which are of the form $(s_{1},s_{2})$ with
$1<s_{2}-s_{1}<n-1$, as well as $n-1$ backbone edges which are of the form
$\\{i,i+1\\}$ for $1\leq i\leq n-1$. In particular, the arc $(1,n)$ is not
allowed in any diagram. Note that the backbone edges play no part in our
results, but we include them as it is usual to do so in the definition of RNA
secondary structures. In particular, from now on all arcs that we consider
will be base-pair arcs. In figures of diagrams backbone edges are represented
by horizontal lines, and base-pairs by semi-circles in the upper-half plane
(see Fig. 6 for an example). The length and size of a diagram are the number
of vertices and arcs, respectively. A diagram is trivial if its size is zero,
and non-trivial otherwise.

Two sites $s$ and $s^{\prime}$ are adjacent if $|s-s^{\prime}|=1$ holds, and
when $s<s^{\prime}$, we denote the interval that contains all sites between
$s$ and $s^{\prime}$ by $[s,s^{\prime}]$. In case $(s_{1},s_{2})$ is an arc we
say that $s_{1}$ and $s_{2}$ are base-paired, and that $(s_{1},s_{2})$ is
supported by $s_{1}$ and $s_{2}$. Two arcs are adjacent if one of them is
supported by a site $s$ and the other by a site adjacent to $s$. A site $s$ is
called free if it does not support any arc, and it is covered by an arc
$(s_{1},s_{2})$ if $s_{1}<s<s_{2}$ holds. An arc is called degenerate if it
does not cover any free site, and tiny if it covers precisely one free site.

Figure 6: Two RNA diagrams: $S$ is $2$-noncrossing with length $9$ and size
$3$, and $S^{\prime}$ is binary $1$-noncrossing. Note that $S^{\prime}$ is
obtained from $S$ by suppressing the arc $(3,8)$.

A diagram $S$ is called binary if it is non-trivial and each site supports at
most one arc, and it is called proper if it is binary and each arc covers at
least one free site but no arc covers all of the free sites in $S$. Note that
a proper diagram has a length of at least four and contains at least two free
sites. Two arcs $(s_{1},s_{2})$ and $(s^{\prime}_{1},s^{\prime}_{2})$ in a
diagram are crossing if either $s_{1}<s^{\prime}_{1}<s_{2}<s^{\prime}_{2}$ or
$s^{\prime}_{1}<s_{1}<s^{\prime}_{2}<s_{2}$ holds. A diagram is a
$k$-noncrossing diagram if it does not contain $(k+1)$ mutually crossing arcs,
$k\geq 1$. Note that binary $1$-noncrossing diagrams are the RNA secondary
structures defined in the introduction (see e.g. [13]). Also, the parameter
$k$ in the definition of a $k$-noncrossing diagram is used in a way similar to
that in a $k$-triangulation (see Section 8 and, e.g. [21]). While some authors
may refer to it as a $(k+1)$-noncrossing diagram (see, e.g., [3]), all results
in this paper can be easily adapted by shifting parameter $k$ to $k+1$. In
Fig. 6 we present an example of a $2$-noncrossing diagram and a binary
$1$-noncrossing diagram. Two arcs are parallel if they cover the same set of
free sites. The concept of parallel arcs as defined here is a natural
generalization of that concept as defined in [13, p. 35] since an arc
$(s_{1},s_{2})$ in a binary $1$-noncrossing diagram is parallel to another arc
$(s^{\prime}_{1},s^{\prime}_{2})$ if and only if $s_{1}$ and $s_{2}$ are
adjacent to $s^{\prime}_{1}$ and $s^{\prime}_{2}$, respectively.

Given an arc $(s_{1},s_{2})$ in a diagram $S$, we can derive a new diagram
$S^{\prime}$ with one less arc by applying one of the following two operations
to $(s_{1},s_{2})$. The first operation is called deleting the arc, and
$S^{\prime}$ is obtained from $S$ by simply removing the arc $(s_{1},s_{2})$.
In this case, the length of $S^{\prime}$ is the same as that of $S$ while the
number of free sites could be the same, or increase by one or two. The second
operation is called suppressing the arc, and $S^{\prime}$ is obtained by
removing $(s_{1},s_{2})$ from $S$ as well as removing any newly resulting free
sites, and finally relabelling if necessary. Note that in this case the number
of free sites in $S^{\prime}$ is the same as that of $S$ while the length of
$S^{\prime}$ could be the same, or decrease by one or two. See Fig. 6 for an
example, where $S^{\prime}$ is obtained from $S$ by suppressing the arc
$(3,8)$ and the length of $S^{\prime}$ decreases by one since site $3$ is
removed from $S$ while site $8$ is kept. For technical reasons, we use the
convention that a sequence of operations could be an empty sequence.

The set $\mathcal{S}_{n}$ of non-trivial diagrams with length $n$ has a
natural poset structure under the relation $\subseteq$ which is defined as
follows: $S\subseteq S^{\prime}$ if $S$ and $S^{\prime}$ have the same length,
and each arc in $S$ is also an arc in $S^{\prime}$. Note that $S\subseteq
S^{\prime}$ holds if and only if $S$ can be obtained from $S^{\prime}$ by a
sequence of arc deletions. We let $\mathcal{S}_{n,k}$ denote the subposet of
$\mathcal{S}_{n}$ under $\subseteq$ that consists of all possible
$k$-noncrossing diagrams in $\mathcal{S}_{n}$. Note that $\mathcal{S}_{n,1}$
is precisely the poset of all secondary structures on linear molecules with
length $n$ as studied in [13, p. 33].

###  2.2 Simplicial complexes

We now review some facts concerning posets and simplicial complexes that we
will require later. More details can be found in [2] and the references
therein.

Let $P=(P,\leq)$ be a finite poset (partial ordered set). To ease the
notation, for two elements $x_{1},x_{2}$ in $P$ with $x_{1}\leq x_{2}$ and
$x_{1}\not=x_{2}$, we also write $x_{1}<x_{2}$, or equivalently,
$x_{2}>x_{1}$. A totally ordered subset $x_{0}<x_{1}<\cdots<x_{t}$ is called a
chain of length $t$. The rank of $P$ is the maximum chain length taken over
all chains in $P$. If all maximal chains have the same finite length then $P$
is called pure. For $x\in P$, the open interval $P_{>x}$ in $P$ is the set
$\\{y\in P\,:\,y>x\\}$. Suppose $Q=(Q,\preceq)$ is another poset. Then the
direct product $P\times Q$ of two posets is the Cartesian product set ordered
by $(x,y)\leq(x^{\prime},y^{\prime})$ if $x\leq x^{\prime}$ in $P$ and
$y\preceq y^{\prime}$ in $Q$. A map $f:P\to Q$ is a poset map if it is order-
preserving, that is, $x\leq y$ in $P$ implies $f(x)\preceq f(y)$ in $Q$. A
poset isomorphism is a bijective poset map.

A simplicial complex $\Delta$ on a finite vertex set $V$ is a collection of
nonempty subsets of $V$, where each subset is called a face of $\Delta$, such
that each nonempty subset of a face is also a face. The face poset
$\mathbf{F}(\Delta)=(\Delta,\subseteq)$ of $\Delta$ is the set of faces in
$\Delta$ ordered by inclusion. The dimension of a face is its cardinality (as
a set) minus one, and the dimension of $\Delta$ is the size of a maximum face
in $\Delta$. Note that, in line with usual conventions, the dimension of an
empty complex is $-1$. A face whose dimension is the same as that of $\Delta$
is known as a facet of $\Delta$. Following [2], a $d$-dimensional simplicial
complex is pure if every face is contained in a $d$-dimensional face. The
complex consisting of all nonempty subsets of a $(d+1)$-element set is called
the $d$-simplex. The geometric realization of a simplicial complex $\Delta$ is
denoted by $|\Delta|$. A simplicial $d$-sphere is a simplicial complex whose
geometric realization is homeomorphic to the $d$-dimensional sphere.

For two simplicial complexes $\Delta_{1}$ and $\Delta_{2}$ on two disjoint
vertex sets, their join is the complex
$\Delta_{1}*\Delta_{2}=\Delta_{1}\cup\Delta_{2}\cup\\{F_{1}\cup
F_{2}\,|\,F_{1}\in\Delta_{1}~{}\mbox{and}~{}F_{2}\in\Delta_{2}\\}$. Given two
nonempty spaces $X$ and $Y$, their join $X*Y$ is the quotient space of
$X\times Y\times I$ determined by the equivalence relation which identifies
$(x,y_{1},0)$ with $(x,y_{2},0)$ and $(x_{1},y,1)$ with $(x_{2},y,1)$ for all
$x,x_{1},x_{2}$ in $X$ and $y,y_{1},y_{2}$ in $Y$. The following relation
between the join operation on complexes and that of topological spaces is well
known (see, e.g. Eq.(9.5) in [2]) :

(1) $|\Delta_{1}*\Delta_{2}|\cong|\Delta_{1}|*|\Delta_{2}|$

where $\cong$ denotes homeomorphism.

Given a poset $P$, its order complex $\Delta(P)$ is a simplicial complex whose
vertices are the elements of $P$ and whose faces are the finite nonempty
chains of $P$. We shall use the following important link between direct
products of posets and the join operation (see Theorem 5.1 in [22], also
[16]): Given two posets $(P,\leq)$ and $(Q,\preceq)$ and $x\in P,y\in Q$, we
have

(2) $|(P\times Q)_{>(x,y)}|\cong|P_{>x}|*|Q_{\succ y}|.$

###  2.3 Adjacency matrices of diagrams

Let $m\geq 1$ be a positive integer. A nonnegative integral symmetric matrix
$\mathbf{M}=(x_{i,j})$ of order $m$ is a square matrix with $m$ rows and $m$
columns such that each entry $x_{i,j}$ is a nonnegative integer, and
$x_{i,j}=x_{j,i}$ holds for all $1\leq i,j\leq m$. If in addition each
$x_{i,j}$ is either $0$ or $1$, then $\mathbf{M}$ is a symmetric
$(0,1)$-matrix. Note that all matrices considered in this paper are symmetric
and nonnegative integral. A matrix is called trivial if all its elements are
zero, and non-trivial otherwise.

For a square matrix $\mathbf{M}=(x_{i,j})$ of order $m$, the diagonal elements
in $\mathbf{M}$ are the entries $x_{i,i}$ with $1\leq i\leq m$, and the semi-
diagonal elements are the superdiagonal entries $x_{i,i+1}$ with $1\leq i<m$
and the subdiagonal entries $x_{i,i-1}$ with $1<i\leq m$. Motivated by the
terminology used in [7], the two elements $x_{1,m}$ and $x_{m,1}$ are referred
to as the rainbow elements. Now, for four distinct integers $a,b,c,d$ we say
$\\{a,b\\}$ and $\\{c,d\\}$ are crossing if
$\min\\{a,b\\}<\min\\{c,d\\}<\max\\{a,b\\}<\max\\{c,d\\}$ or
$\min\\{c,d\\}<\min\\{a,b\\}<\max\\{c,d\\}<\max\\{a,b\\},$ two entries
$x_{i,j}$ and $x_{p,q}$ in $\mathbf{M}$ are crossing if the index pairs
$\\{i,j\\}$ and $\\{p,q\\}$ are crossing. If $\mathbf{M}$ does not contain
$(k+1)$ mutually crossing non-zero entries it will be referred to as a
$k$-noncrossing matrix.

A matrix $A=(a_{i,j})$ is dominated by another matrix $B=(b_{i,j})$, written
as $A\leq B$, if they have the same order $m$ and $a_{i,j}\leq b_{i,j}$ holds
for $1\leq i,j\leq m$. For $m\geq 4$, let $\mathcal{M}_{m}$ be the non-empty
set of symmetric non-trivial $(0,1)$-matrices of order $m$ in which all
diagonal, semi-diagonal and rainbow elements are zero. Then $\mathcal{M}_{m}$
is a poset under the relationship $\leq$, where $A\leq B$ holds for matrices
$A$ and $B$ in $\mathcal{M}_{m}$ if $A$ is dominated by $B$. For $m\geq 4$ and
$k\geq 1$, we let $\mathcal{M}_{m,k}$ be the subset of $\mathcal{M}_{m}$
consisting of all $k$-noncrossing matrices. Then $(\mathcal{M}_{m,k},\leq)$ is
a subposet of $(\mathcal{M}_{m},\leq)$.

Now, given a diagram $S$ with length $n$, we define its adjacency matrix
$\mathbf{A}(S)$ to be the symmetric $(0,1)$-matrix $(a_{i,j})$ of order $n$
such that $a_{i,j}$ is $1$ if either $(i,j)$ or $(j,i)$ is an arc. Note that
both of the two rainbow elements of $\mathbf{A}(S)$ must be zero because the
arc $(1,n)$ is not allowed in $S$ by definition. For example, the adjacency
matrix $\mathbf{A}(S^{\prime})=(a_{i,j})$ of the $1$-noncrossing diagram
$S^{\prime}$ in $\mathcal{S}_{8,1}$ that is depicted in Fig. 6 is the
symmetric $(0,1)$-matrix of order $8$ whose non-zero entries are
$a_{1,7},a_{7,1},a_{2,4}$ and $a_{4,2}$. This implies that
$\mathbf{A}(S^{\prime})$ is a matrix in $\mathcal{M}_{8,1}$.

As the last example indicates, a number of properties of a given diagram are
determined by its adjacency matrix. For instance, the number of arcs in $S$ is
half of the sum of the elements in $\mathbf{A}(S)$, and $S\subseteq
S^{\prime}$ if and only if $\mathbf{A}(S)$ is dominated by
$\mathbf{A}(S^{\prime})$. Moreover, the following result, whose proof is
routine, shows that the map that associates a diagram with its adjacency
matrix is in fact a poset isomorphism.

######  Proposition 2.1.

For $n\geq 4$, the map $S\to\mathbf{A}(S)$ is a poset isomorphism between
$(\mathcal{S}_{n},\subseteq)$ and $(\mathcal{M}_{n},\leq)$. In addition, its
restriction to $\mathcal{S}_{n,k}$ with $k\geq 1$ is a poset isomorphism
between $(\mathcal{S}_{n,k},\subseteq)$ and $(\mathcal{M}_{n,k},\leq)$.
$\square$

For later use, we let $\tau$ denote the map from
$(\mathcal{S}_{n,k},\subseteq)$ to $(\mathcal{M}_{n,k},\leq)$ that associates
a diagram with its adjacency matrix.

##  3 Block Matrices and Regular Diagrams

In this section we introduce and study a matrix which can be associated to a
diagram, called its block matrix, which contains information concerning the
structure of the diagram in a more condensed form than its adjacency matrix.
Moreover, we show that for a special family of binary diagrams which we will
call regular diagrams, they are $k$-noncrossing if and only if their block
matrices are $k$-noncrossing.

Given a diagram $S$ with length $n$, denote the number of free sites in $S$ by
$f=f_{S}\geq 0$. If $f>0$, we let $u_{1}<\dots<u_{f}$ denote the set of free
sites. Setting $u_{0}=0$ and $u_{f+1}=n+1$, then its $i$-th block
$B_{i}=B_{i}(S)$ $(1\leq i\leq f+1)$ consists of all (necessarily non-free)
sites $s$ in $S$ with $u_{i-1}<s<u_{i}$. In other words, each maximal interval
of non-free sites forms a block. For example, the interval consisting of the
non-free sites $1$, $2$, and $3$ is a block in the diagram in Fig. 7. Indeed,
the diagram contains four free sites and hence it has five blocks. Note that a
block can be the empty set, and that a diagram without any free sites has only
one block. If an arc $e$ is supported by a site in a block $B$, then we say
that $e$ and $B$ are incident. The block list of $S$, denoted by
$\mathcal{L}(S)$, is the list $(B_{1},\dots,B_{f+1})$ consisting of all blocks
of $S$ in the canonical order. The block matrix $\mathbf{B}(S)$ of $S$ is the
symmetric matrix with order $(f+1)$ in which the $(i,j)$-entry is the number
of arcs incident with both $B_{i}$ and $B_{j}$ (see Fig. 7 for an example).

Figure 7:  Example of a diagram and its block matrix: (i) a $4$-noncrossing
diagram $S$; (ii) the block matrix ${\bf B}(S)$ associated with $S$. Since $S$
contains four free sites: $4$, $6$, $11$, and $12$, it has five blocks:
$B_{1}=\\{1,2,3\\}$, $B_{2}=\\{5\\}$, $B_{3}=\\{7,8,9,10\\}$,
$B_{4}=\emptyset$, and $B_{5}=\\{13,14\\}$.

The number of crossings in a diagram $S$ is the total number of arc pairs in
$S$ that are crossing. Note that a diagram that is not $k$-noncrossing
contains a set of $k+1$ arcs that are pairwise mutually crossing, and hence
its number of crossings is at least $k(k+1)/2$. A crossing of two arcs $e_{1}$
and $e_{2}$ is called local if there exists a block $B$ of $S$ that contains
two sites $s_{1}$ and $s_{2}$ such that $e_{1}$ and $e_{2}$ are supported by
$s_{1}$ and $s_{2}$, respectively. A diagram is called regular if it is binary
and does not contain any local crossings. For example, the diagram in Fig. 7
is not regular because $(2,8)$ and $(3,9)$ are two local crossing arcs. On the
other hand, the diagram in Fig. 3(ii) is regular.

We now present two results relating properties of diagrams to those of their
block matrices. The first one collects together some facts and its
straightforward proof follows from the relevant definitions.

######  Lemma 3.1.

For a diagram $S$, the following statements hold:
(i) $S$ does not contain any degenerate arc if and only if all diagonal
elements in $\mathbf{B}(S)$ are zero.
(ii) $S$ does not contain any tiny arc if and only if all semi-diagonal
elements in $\mathbf{B}(S)$ are zero.
(iii) $S$ contains no parallel arcs if and only if $\mathbf{B}(S)$ is a
$(0,1)$-matrix.
(iii) If $S$ is binary, then $S$ is proper if and only if all diagonal and
rainbow elements in $\mathbf{B}(S)$ are zero.
(v) If $S$ is proper and contains neither tiny nor parallel arcs, then
$\mathbf{B}(S)$ is a non-trivial $(0,1)$-matrix in which all diagonal, semi-
diagonal and rainbow elements are zero. $\square$

The second result shows that the block matrix of a binary $k$-noncrossing
diagram is $k$-noncrossing.

######  Lemma 3.2.

The block matrix of a binary $k$-noncrossing diagram is $k$-noncrossing.

######  Proof 3.3.

For simplicity, put $t=k+1$. Suppose that $S$ is a binary $k$-noncrossing
diagram, and let $f$ be the number of free sites in $S$. Then the block matrix
$\mathbf{B}(S)$ of $S$ can be written as $(b_{i,j})_{1\leq i,j\leq f+1}$. In
addition, the list $\mathcal{L}(S)$ of the blocks contained in $S$ can be
written as $(B_{1},\dots,B_{f+1})$.

We shall establish the lemma by contradiction. To this end, assume that
$U=\\{b_{r_{1},c_{1}},\dots,b_{r_{t},c_{t}}\\}$ is a set of mutually crossing
non-zero entries contained in $\mathbf{B}(S)$. We claim that $S$ contains a
set of $t$ pairwise crossing arcs, which contradicts the fact that $S$ is
$k$-noncrossing.

Since entries in $U$ are mutually crossing, it follows that for $1\leq i<j\leq
t$, the integer pairs $\\{r_{i},c_{i}\\}$ and $\\{r_{j},c_{j}\\}$ are
crossing. Therefore, $\\{r_{1},c_{1},\dots,r_{t},c_{t}\\}$ is a set of $2t$
distinct integers. Since $\mathbf{B}(S)$ is symmetric, we may assume that
$r_{i}<c_{i}$ holds for $1\leq i\leq t$. In addition, relabelling the indices
if necessary, we may assume that $r_{1}<\cdots<r_{t}$.

Now for each $1\leq i\leq t$, since $b_{r_{i},c_{i}}>0$, we fix an arc
$e_{i}=(s_{i},s^{\prime}_{i})$ such that $s_{i}$ is contained in block
$B_{r_{i}}$ and $s^{\prime}_{i}$ is contained in block $B_{c_{i}}$. Then for
$1\leq i<j\leq t$, because $b_{r_{i},c_{i}}$ and $b_{r_{j},c_{j}}$ are
crossing in the matrix $\mathbf{B}(S)$, we have $r_{i}<r_{j}<c_{i}<c_{j}$, and
hence $s_{i}<s_{j}<s^{\prime}_{i}<s^{\prime}_{j}$. This implies $e_{i}$
crosses $e_{j}$, and hence $\\{e_{i}\\}_{1\leq i\leq t}$ is a set of $t$
mutually crossing arcs, as claimed.

Note that the converse of Lemma 3.2 does not hold in general. For instance,
the diagram $S$ in Fig. 7 is $4$-noncrossing while its block matrix
$\mathbf{B}(S)$ is $2$-noncrossing. However, the next result shows that the
converse does hold for regular diagrams.

######  Proposition 3.4.

Suppose that $S$ is a regular diagram. Then $S$ is $k$-noncrossing if and only
if $\mathbf{B}(S)$ is a $k$-noncrossing matrix.

######  Proof 3.5.

By Lemma 3.2 it follows that if $S$ is $k$-noncrossing, then $\mathbf{B}(S)$
is $k$-noncrossing.

To see that the converse holds, for simplicity, put $t=k+1$ and let $f$ be the
number of free sites in $S$. Then the block matrix $\mathbf{B}(S)$ can be
written as $(b_{i,j})_{1\leq i,j\leq f+1}$. In addition, the list
$\mathcal{L}(S)$ of the blocks contained in $S$ can be written as
$(B_{1},\dots,B_{f+1})$.

Now, suppose that $S$ contains a set $\\{(s_{i},s^{\prime}_{i})\\}_{1\leq
i\leq t}$ of mutually crossing arcs. Then it suffices to establish the claim
that $\mathbf{B}(S)$ must have $t$ mutually crossing non-zero elements.

By swapping the indices if necessary, we may assume that $s_{i}<s_{j}$ holds
for all $1\leq i<j\leq t$. For each non-free site $s$ in $S$, let $\alpha(s)$
be the index in $\\{1,\dots,f+1\\}$ such that $s$ is contained the block
$B_{\alpha(s)}$ of $S$. Note that for two non-free sites $s<s^{\prime}$, we
have $\alpha(s)\leq\alpha(s^{\prime})$. In addition, if $(s,s^{\prime})$ is an
arc in $S$, then $b_{\alpha(s),\alpha(s^{\prime})}\geq 1$.

Now, consider the set $U=\\{b_{\alpha(s_{i}),\alpha(s^{\prime}_{i})}\\}_{1\leq
i\leq t}$ of entries in $\mathbf{B}(S)$. Note first that each entry in $U$ is
non-zero. Moreover each pair of distinct elements in $U$ are crossing. Indeed,
fix two indices $i$ and $j$ with $1\leq i<j\leq t$. Since
$(s_{i},s^{\prime}_{i})$ and $(s_{j},s^{\prime}_{j})$ are crossing and
$s_{i}<s_{j}$, we have $s_{i}<s_{j}<s^{\prime}_{i}<s^{\prime}_{j}$, and hence
$\alpha(s_{i})\leq\alpha(s_{j})\leq\alpha(s^{\prime}_{i})\leq\alpha(s^{\prime}_{j})$.
Using the fact that $S$ is regular, we can further conclude that

$\alpha(s_{i})<\alpha(s_{j})<\alpha(s^{\prime}_{i})<\alpha(s^{\prime}_{j}),$

from which it follows that $\\{\alpha(s_{i}),\alpha(s^{\prime}_{i})\\}$ and
$\\{\alpha(s_{j}),\alpha(s^{\prime}_{j})\\}$ are two pairs of crossing
integers. Therefore $U$ consists of $t$ mutually crossing non-zero elements in
$\mathbf{B}(S)$, which completes the proof of the claim.

##  4 The Penner-Waterman Poset

In [13, p. 35] Penner and Waterman investigated the poset
$\mathcal{B}^{r}_{f}$ of RNA secondary structures mentioned in the
introduction. In this section we introduce and study a generalisation of their
poset for binary $k$-noncrossing diagrams.

To define this new poset we need some additional terminology. Given a non-
negative integral matrix $\mathbf{M}$ of order $m$, we let

(3) $\mathbf{r}(\mathbf{M})=\mathbf{p}(\mathbf{M})+\mathbf{q}(\mathbf{M}),$

be the tautology number of $\mathbf{M}$, where

(4) $\mathbf{p}(\mathbf{M})=\sum_{1\leq i<j\leq
m}\max\\{0,x_{i,j}-1\\}~{}~{}\mbox{and}~{}~{}\mathbf{q}(\mathbf{M})=\sum_{1\leq
i<m}x_{i,i+1}.$

In addition, given a diagram $S$, we define its tautology number to be
$\mathbf{r}(\mathbf{B}(S))$. In particular, if $S$ is $1$-noncrossing, then
$\mathbf{p}(\mathbf{B}(S))$ and $\mathbf{q}(\mathbf{B}(S))$ are the same as
the values $p(S)$ and $q(S)$ as defined in [13, p.35], respectively, and
$\mathbf{r}(\mathbf{B}(S))$ is the number of tautological arcs in $S$.
Moreover, $\mathbf{r}(\mathbf{B}(S))=0$ holds if and only if $S$ contains
neither tiny nor parallel arcs. Finally, for $r\geq 0,m\geq 4$, and $k\geq 1$,
we let $\mathcal{M}^{r}_{m,k}$ be the non-empty set of symmetric non-trivial
non-negative integral $k$-noncrossing matrices of order $m$ whose tautology
number is less than or equal to $r$ and in which all diagonal and rainbow
elements are zero. Clearly, we have
$\mathcal{M}^{r}_{m,k}\subseteq\mathcal{M}^{r+1}_{m,k}$ and
$\mathcal{M}^{r}_{m,k}\subseteq\mathcal{M}^{r}_{m,k+1}$. In particular, all
matrices in $\mathcal{M}^{0}_{m,k}$ are necessarily $(0,1)$-matrices and hence
we have $\mathcal{M}^{0}_{m,k}=\mathcal{M}_{m,k}$.

Now, we let $\mathcal{P}_{f,k}^{r}$ be the set of all proper $k$-noncrossing
diagrams $S$ with $f$ free sites and tautology number
$\mathbf{r}(\mathbf{B}(S))\leq r$, and $\mathcal{B}_{f,k}^{r}$ be the subset
consisting of all regular diagrams in ${\mathcal{P}}_{f,k}^{r}$. Note that for
the special case $k=1$, we have $\mathcal{P}_{f,1}^{r}=\mathcal{B}_{f,1}^{r}$,
which is the set $\mathcal{B}_{f}^{r}$ introduced in [13, p.35]. More
generally, we have $\mathcal{B}_{f,k}^{r}\subseteq\mathcal{P}_{f,k}^{r}$ in
view of the following observation.

######  Lemma 4.1.

A regular diagram is proper.

######  Proof 4.2.

Suppose that $S$ is a regular diagram. Denote the length of $S$ by $n$ and the
number of free sites in $S$ by $f$. Without loss of generality, we may assume
that $n\geq 4$ and $f\geq 1$ as otherwise the lemma clearly holds.

First we shall show that $S$ does not contain any degenerate arc. Suppose that
this is not the case. Then there exists a block $B$ of $S$ such that the set
$\Sigma(B)$ of arcs $(s,s^{\prime})$ in $S$ with $\\{s,s^{\prime}\\}\subseteq
B$ is not empty. Now fix an arc $e_{1}=(s_{1},s^{\prime}_{1})$ in $\Sigma(B)$
so that the distance $|s_{1}-s^{\prime}_{1}|$ is minimum over all arcs in
$\Sigma(B)$. We claim that $s_{1}$ and $s^{\prime}_{1}$ are adjacent, that is,
$s^{\prime}_{1}=s_{1}+1$, which leads to a contradiction because no arc in $S$
is supported by two adjacent sites.

Suppose the claim is not true, and consider the site $s_{2}:=s_{1}+1$. Then
$s_{2}$ is contained in $B$ with $s_{1}<s_{2}<s^{\prime}_{1}$. Let $e_{2}$ be
the arc supported by $s_{2}$ and denote the other site supporting $e_{2}$ by
$s^{\prime}_{2}$. Since $S$ is regular, $e_{1}$ and $e_{2}$ are not crossing,
it follows that $s_{1}\leq s^{\prime}_{2}\leq s^{\prime}_{1}$ and hence
$e_{2}\in\Sigma(B)$. Moreover, this implies that
$|s_{2}-s^{\prime}_{2}|<|s_{1}-s^{\prime}_{1}|$, a contradiction. Hence the
claim holds, and therefore $S$ does not contain any degenerate arc.

Let $\Sigma(S)$ be the set of the arcs in $S$ that cover all free sites of
$S$. It remains to prove that $\Sigma(S)$ is the empty set. Suppose this were
not the case. Then fix an arc $e_{3}=(s_{3},s^{\prime}_{3})$ in $\Sigma(S)$ so
that $s^{\prime}_{3}-s_{3}\geq s^{\prime}-s$ holds for each arc
$(s,s^{\prime})$ in $\Sigma(S)$. Since $[s_{3},s^{\prime}_{3}]$ contains all
free sites of $S$, it follows that $s_{3}$ is contained in $B_{1}(S)$, the
first block of $S$, and that $s^{\prime}_{3}$ is contained in $B_{f+1}(S)$,
the last block of $S$. Moreover, neither $1$ nor $n$ is a free site, and thus
site $1$ is contained in $B_{1}(S)$ and site $n$ is contained in $B_{f+1}(S)$.

Denote the site that is base-paired with $1$ by $s^{*}$. Then $s^{*}$ is not
contained in $B_{1}(S)$ as $S$ does not contain any degenerate arcs. In
addition, we know that $s^{*}$ is contained in $B_{f+1}(S)$ and $s^{*}\geq
s^{\prime}_{3}$ as otherwise $(1,s^{*})$ and $(s_{3},s^{\prime}_{3})$ are two
locally crossing arcs, a contradiction to the fact that $S$ is regular. This
implies that $s^{*}-1\geq s^{\prime}_{3}-s_{3}$, and hence
$s^{*}-1=s^{\prime}_{3}-s_{3}$ in view of the maximality of
$(s_{3},s^{\prime}_{3})$. It follows that $s_{3}=1$, and a similar argument
shows that $s^{\prime}_{3}=n$. Thus $(1,n)$ is an arc in $S$, a contradiction
to the fact that $1<|s-s^{\prime}|<n-1$ holds for every arc $(s,s^{\prime})$
in a diagram of length $n$. Therefore, $\Sigma(S)$ is the empty set, which
completes the proof.

Next, we say $S\preceq S^{\prime}$ holds for two diagrams $S$ and $S^{\prime}$
in $\mathcal{P}_{f,k}^{r}$ if $S$ can be obtained from $S^{\prime}$ by a
sequence of arc suppressions. Note that the relation $\preceq$ is distinct
from the poset relation $\subseteq$ as defined in Section 2.3. Moreover, it is
straightforward to see that $S\preceq S^{\prime}$ implies that $\mathbf{B}(S)$
is dominated by $\mathbf{B}(S^{\prime})$. We now show that
$(\mathcal{P}_{f,k}^{r},\preceq)$ and $(\mathcal{B}_{f,k}^{r},\preceq)$ are
finite posets.

######  Proposition 4.3.

For $f\geq 2,r\geq 0,k\geq 1$ with $f+r\geq 3$,
$(\mathcal{P}_{f,k}^{r},\preceq)$ is a non-empty finite poset. Furthermore,
$(\mathcal{B}_{f,k}^{r},\preceq)$ is a subposet of
$(\mathcal{P}_{f,k}^{r},\preceq)$.

######  Proof 4.4.

When $r\geq 1$, it is straightforward to see that the set
$\mathcal{B}_{f,k}^{r}$, and hence also the set $\mathcal{P}_{f,k}^{r}$,
contains a diagram with one tiny arc for $f\geq 2$ and $k\geq 1$. On the other
hand, when $f\geq 3$, both sets contain a diagram with one arc covering
precisely two free sites for $r\geq 0$ and $k\geq 1$. Therefore, we know that
both sets are non-empty for $f\geq 2,r\geq 0,k\geq 1$ with $f+r\geq 3$.

Since both sets are posets under the binary relation $\preceq$ and
$\mathcal{B}_{f,k}^{r}$ is a subset of $\mathcal{P}_{f,k}^{r}$, it suffices to
show that $\mathcal{P}_{f,k}^{r}$ is a finite set. This follows from the fact
that the number of free sites $f$ and the length $n$ of a proper diagram $S$
satisfy the following inequality:

(5) $n\leq{f+3\choose 2}+2\mathbf{p}(\mathbf{B}(S)).$

To establish the inequality in Eq. (5), note first that after removing all but
one arc from each parallel class of arcs, there exists at most one arc between
each pair of blocks in $S$. Then the inequality follows because $S$ contains
precisely $f$ free sites, the set of removed arcs contribute to at most
$2\mathbf{p}(\mathbf{B}(S))$ non-free sites in $S$, and the remaining arcs
contribute to at most ${f+1\choose 2}$ non-free sites.

Figure 8: A member of the infinite family of non-proper binary diagrams with
two free sites defined in the text for $t=4$.

For $f\geq 3,r\geq 0,k\geq 1$, we call poset $(\mathcal{B}_{f,k}^{r},\preceq)$
the Penner-Waterman poset. Note that it is important to consider proper
diagrams in the definition of the set $\mathcal{P}_{f,k}^{r}$. For example
there exists infinitely many binary $3$-noncrossing diagrams that have two
free sites and $\mathbf{r}(\mathbf{B}(S))=0$. In particular, for each positive
integer $t\geq 1$, let $S_{t}$ be the diagram with length $4t$ that contains
precisely all arcs of the form $(i,i+3)$ for every odd number $i$ with $1\leq
i\leq 4t-3$ (see Fig. 8 for the diagram with $t=2$). Then $S_{t}$ contains
precisely two free sites (the sites $2$ and $4t-1$), and it is $3$-noncrossing
with $\mathbf{p}(\mathbf{B}(S_{t}))=\mathbf{r}(\mathbf{B}(S_{t}))=0$.

##  5 An Equivalence Relation on Diagrams

In this section we present a characterization of the set of proper diagrams
that have the same block matrix. In particular, we first define a certain
equivalence relation $\sim$ on the set of proper diagrams, and then show that
two proper diagrams have the same block matrix if and only if they are
equivalent under $\sim$ (see Theorem 5.9).

We begin by defining $\sim$. Two proper diagrams $S$ and $S^{\prime}$ are
defined to be equivalent, denoted by $S\sim S^{\prime}$, if they have the same
length, and there exists a bijective map $\phi$ from the set of arcs in $S$ to
the set of arcs in $S^{\prime}$ that preserves free sites, that is, for each
arc $e$ in $S$, a free site $s$ in $S$ is covered by $e$ if and only if $s$ is
covered by $\phi(e)$ in $S^{\prime}$. See Fig. 9 for an example of two
equivalent diagrams $S_{1}^{\prime}$ and $S_{2}^{\prime}$. Note that in this
example there are two such bijective maps from the arc set of $S^{\prime}_{1}$
to that of $S^{\prime}_{2}$: one maps arc $e_{1}=(1,8)$ in $S_{1}^{\prime}$ to
arc $(1,8)$ in $S^{\prime}_{2}$ and the other maps $e_{1}$ to arc $(2,6)$. It
is straightforward to check that $\sim$ is an equivalence relation on the set
of proper diagrams, and that two equivalent diagrams have the same number of
arcs.

Figure 9: Two equivalent proper diagrams $S^{\prime}_{1}$ and $S^{\prime}_{2}$
related by a single swap ($S^{\prime}_{2}$ can be obtained from
$S^{\prime}_{1}$ by a swap $\epsilon[6]$ at site $6$).

We now want to better understand when two proper diagrams are equivalent. To
this end, we introduce a new operation on proper diagrams that preserves the
$\sim$ relation. Suppose that $s_{1}$ and $s_{2}=s_{1}+1$ are two adjacent
non-free sites in a proper diagram $S$ of length $n$, and denote the site
base-paired with $s_{i}$ by $r_{i}$ for $i=1,2$. A swap
$\epsilon=\epsilon[s_{1}]$ at $s_{1}$ generates a binary diagram $\epsilon(S)$
by replacing the two arcs supporting by $s_{1}$ and $s_{2}$ with two new arcs:
one is supported by $s_{1}$ and $r_{2}$, and the other by $s_{2}$ and $r_{1}$
(see Fig. 9 for an example). Since $S$ is proper, we have

$1<|s_{1}-r_{2}|<n-1~{}~{}\mbox{and}~{}~{}~{}1<|s_{2}-r_{1}|<n-1$

and hence $\epsilon(S)$ is a binary digram. Note also that swapping is an
involution, that is, swapping at $s_{1}$ twice results in the same diagram. We
now show that $\epsilon(S)$ is a proper diagram that is equivalent to $S$,
which has the same block matrix.

######  Lemma 5.1.

If $\epsilon$ is a swap on a proper diagram $S$, then $\epsilon(S)$ is a
proper diagram. Moreover, $\epsilon(S)\sim S$,
$\mathcal{L}(S)=\mathcal{L}(\epsilon(S))$, and
$\mathbf{B}(S)=\mathbf{B}(\epsilon(S))$.

######  Proof 5.2.

Denote the site at which $\epsilon$ swaps by $s_{1}$. Put $s_{2}=s_{1}+1$ and
$S^{\prime}=\epsilon(S)$. For $i=1,2$, let $e_{i}$ be the arc in $S$ supported
by $s_{i}$ and denote the other site supporting $e_{i}$ by $r_{i}$. We shall
assume that $e_{1}=(r_{1},s_{1})$ and $e_{2}=(s_{2},r_{2})$ since the other
cases in which $e_{1}=(s_{1},r_{1})$ or $e_{2}=(r_{2},s_{2})$ (or both) can be
established in a similar way.

Let $e^{\prime}_{1}=(r_{1},s_{2})$ and $e^{\prime}_{2}=(s_{1},r_{2})$. Then
$S^{\prime}$ is obtained from $S$ by replacing $e_{1}$ and $e_{2}$ by
$e^{\prime}_{1}$ and $e^{\prime}_{2}$. Note that the set of free sites covered
by $e_{1}$ (i.e., those in $[r_{1},s_{1}]$) is the same as the set covered by
$e^{\prime}_{1}$ (i.e., those in $[r_{1},s_{2}]$). Similarly, the set of sites
covered by $e_{2}$ is the same as that covered by $e^{\prime}_{2}$. Now let
$\phi$ be the map that maps $e_{i}$ to $e^{\prime}_{i}$ for $i=1,2$ and maps
each of the other arcs in $S$ to the same arc in $S^{\prime}$. Then $\phi$ is
a bijection preserving free sites, and so $S\sim S^{\prime}$.

Since $S$ and $S^{\prime}$ have the same length and the same set of free
sites, it follows that $\mathcal{L}(S)=\mathcal{L}(S^{\prime})$. In addition,
for two arbitrary blocks $B_{i}(S)$ and $B_{j}(S)$ in $S$, the number of arcs
between them is the same as that in $S^{\prime}$, and so
$\mathbf{B}(S)=\mathbf{B}(S^{\prime})$.

We now show that the swap operation can be used to convert a proper diagram
into a canonical form.

######  Lemma 5.3.

Suppose that $(s_{1},s_{2})$ is an arc in a proper diagram $S$, and
$s^{\prime}_{i}$ is a site in the block containing $s_{i}$ for $i=1,2$. Then
there exists a sequence of swaps $\epsilon_{1},\dots,\epsilon_{t}$ for some
$t\geq 0$ such that $(s^{\prime}_{1},s^{\prime}_{2})$ is an arc in the proper
diagram $\epsilon_{t}\epsilon_{t-1}\cdots\epsilon_{1}(S)$.

######  Proof 5.4.

Let $B_{i}$ and $B_{j}$ be the block containing $s_{1}$ and $s_{2}$,
respectively. Note that the lemma clearly holds when $s^{\prime}_{1}=s_{1}$
and $s^{\prime}_{2}=s_{2}$ (by taking an empty sequence with $t=0$). Hence in
the remainder of the proof we assume that either $s^{\prime}_{1}\not=s_{1}$ or
$s^{\prime}_{2}\not=s_{2}$.

Since $S$ is proper and $(s_{1},s_{2})$ is an arc, it follows
$B_{i}\not=B_{j}$, and hence $|s^{*}_{1}-s^{*}_{2}|>1$ for each site
$s^{*}_{1}$ in $B_{i}$ and $s^{*}_{2}$ in $B_{j}$. As the case
$s_{2}\not=s^{\prime}_{2}$ can be established in a similar manner, we assume
$s_{1}\not=s^{\prime}_{1}$. In addition, we further assume
$s_{1}<s^{\prime}_{1}$ as the proof of the other case $s_{1}>s^{\prime}_{1}$
is similar.

We now proceed by induction on
$d=|s_{1}-s^{\prime}_{1}|+|s_{2}-s^{\prime}_{2}|$. For the base case $d=1$ we
have $s^{\prime}_{1}=s_{1}+1$, and hence the lemma follows by taking $t=1$ and
$\epsilon_{1}=\epsilon[s_{1}]$.

Now suppose $d>1$ and the lemma holds for two arbitrary sites $s^{*}_{1}\in
B_{i}$ and $s^{*}_{2}\in B_{j}$ with
$0<|s_{1}-s^{*}_{1}|+|s_{2}-s^{*}_{2}|<d$. In particular, the lemma holds for
$s^{\prime\prime}_{1}=s^{\prime}_{1}-1$ and
$s^{\prime\prime}_{2}=s^{\prime}_{2}$. Therefore, there exists a sequence of
swaps $\epsilon_{1},\dots,\epsilon_{t}$ for some $t\geq 1$ such that
$(s^{\prime\prime}_{1},s^{\prime\prime}_{2})$ is an arc in the proper diagram
$S^{\prime\prime}=\epsilon_{t}\epsilon_{t-1}\cdots\epsilon_{1}(S)$. Since
$|s^{\prime\prime}_{1}-s^{\prime}_{1}|+|s^{\prime\prime}_{2}-s^{\prime}_{2}|=1$,
by the base case there exists a swap $\epsilon$ such that
$(s^{\prime}_{1},s^{\prime}_{2})$ is an arc in the proper diagram
$S^{\prime}=\epsilon(S^{\prime\prime})$. This completes the proof of the
induction step, and hence the lemma.

Using Lemma 5.3, we now show that two equivalent proper diagrams have the same
block list, which is a key step for establishing the main result in this
section. Note that the converse of this proposition clearly does not hold.

######  Proposition 5.5.

If $S$ and $S^{\prime}$ are two proper diagrams with $S\sim S^{\prime}$, then
$\mathcal{L}(S)=\mathcal{L}(S^{\prime})$.

######  Proof 5.6.

Since $S\sim S^{\prime}$, they have the same length, denoted by $n$, and also
the same size, denoted by $m$. Thus it suffices to show that $S$ and
$S^{\prime}$ have the same set of free sites.

We proceed by induction on $m$. The base cases $m=1$ follows by noting that
both $S$ and $S^{\prime}$ contain precisely the same set of non-free sites
with cardinality two. Now assume $m>1$ and that two equivalent proper diagrams
with at most $m-1$ arcs have the same set of free sites.

Since $S$ contains two or more arcs, at least one block in the list
$\mathcal{L}(S)$ is non-empty. Now let $B_{i}$ be the first non-empty block in
$\mathcal{L}(S)$, and denote the largest site in $B_{i}$ by $s_{1}$. Let
$s_{2}$ be the site so that $(s_{1},s_{2})$ is an arc in $S$ and denote the
(necessarily non-empty) block containing $s_{2}$ by $B_{j}$. Since $S$ is
proper, it follows that $j>i$. Let $s_{3}$ be the smallest site in $B_{j}$.

Since $S$ and $S^{\prime}$ are equivalent, there exists an arc
$(s^{\prime}_{1},s^{\prime}_{2})$ in $S^{\prime}$ such that the free sites in
$S$ contained in $[s_{1},s_{2}]$ are the same as those in $S^{\prime}$
contained in $[s^{\prime}_{1},s^{\prime}_{2}]$. Let $B^{\prime}_{k}$ and
$B^{\prime}_{l}$ be the blocks in $\mathcal{L}(S^{\prime})$ containing
$s^{\prime}_{1}$ and $s^{\prime}_{2}$, respectively. Since $s_{1}+1$ is the
smallest free site in $[s_{1},s_{2}]$ and $[s^{\prime}_{1},s^{\prime}_{2}]$
has the same set of free sites as that in $[s_{1},s_{2}]$, it follows that the
largest site in $B^{\prime}_{k}$ is $s_{1}$. Similarly, the smallest site in
$B^{\prime}_{l}$ is $s_{3}$.

By Lemma 5.3, there exists a (possibly empty) sequence of swaps
$\epsilon_{1},\dots,\epsilon_{t}$ for some $t\geq 0$ such that $(s_{1},s_{3})$
is an arc in $S^{*}=\epsilon_{t}\cdots\epsilon_{1}(S)$. Similarly, there
exists a (possibly empty) sequence of swaps
$\epsilon^{\prime}_{1},\dots,\epsilon^{\prime}_{t^{\prime}}$ for some
$t^{\prime}\geq 0$ such that $(s_{1},s_{3})$ is an arc in
$S^{\prime\prime}=\epsilon_{t^{\prime}}\cdots\epsilon_{1}(S^{\prime})$. By
Lemma 5.1 it follows that $S^{*}$ and $S^{\prime\prime}$ are two equivalent
proper diagrams. Consider the diagrams ${S}_{o}^{*}$ and
${S}_{o}^{\prime\prime}$ that are obtained from $S^{*}$ and $S^{\prime\prime}$
respectively by suppressing the arc $(s_{1},s_{3})$. Then ${S}_{o}^{*}$ and
${S}_{o}^{\prime\prime}$ are two equivalent proper diagrams with precisely
$m-1$ arcs. Now the induction assumption implies that ${S}_{o}^{*}$ and
${S}_{o}^{\prime\prime}$ have the same set of free sites, from which it
follows that $S$ and $S^{\prime}$ have the same set of free sites. This
completes the proof of the induction step and hence the proposition.

The next result shows that the blocks of a binary diagram are determined by
its block matrix (note that the converse clearly does not hold).

######  Lemma 5.7.

Suppose that $S$ and $S^{\prime}$ are two binary diagrams with
$\mathbf{B}(S)=\mathbf{B}(S^{\prime})$. Then $S$ and $S^{\prime}$ have the
same size and the same length. Furthermore, we have
$\mathcal{L}(S)=\mathcal{L}(S^{\prime})$.

######  Proof 5.8.

Let $(b_{i,j})_{1\leq i,j\leq(f+1)}$ be the elements in the block matrix
$\mathbf{B}=\mathbf{B}(S)=\mathbf{B}(S^{\prime})$, where $f+1$ is the order of
$\mathbf{B}$. Then both $S$ and $S^{\prime}$ contain $f$ free sites. Next, the
size of $S$ is $\sum_{1\leq i\leq j\leq f+1}b_{i,j}$, the same as that of
$S^{\prime}$. Note that for a binary diagram, the number of its size is half
of the difference between its length and the number of its free sites. Thus
$S$ and $S^{\prime}$ also have the same length. Finally, let
$(B_{1},\dots,B_{f+1})$ and $(B^{\prime}_{1},\dots,B^{\prime}_{f+1})$ be the
block lists of $\mathcal{L}(S)$ and $\mathcal{L}(S^{\prime})$, respectively.
Then for $1\leq i\leq f+1$, we have

$|B_{i}|=b_{i,i}+\sum_{1\leq j\leq f+1}b_{i,j}=|B^{\prime}_{i}|,$

from which $\mathcal{L}(S)=\mathcal{L}(S^{\prime})$ follows.

We now prove the main result of this section.

######  Theorem 5.9.

Suppose that $S$ and $S^{\prime}$ are two proper diagrams. Then

$\mathbf{B}(S)=\mathbf{B}(S^{\prime})~{}~{}\mbox{if and only if}~{}~{}~{}S\sim
S^{\prime}.$

######  Proof 5.10.

Suppose that $S$ and $S^{\prime}$ are two proper diagrams with
$\mathbf{B}(S)=\mathbf{B}(S^{\prime})$. Let $(b_{i,j})_{1\leq i,j\leq(f+1)}$
be the elements in the block matrix
$\mathbf{B}=\mathbf{B}(S)=\mathbf{B}(S^{\prime})$, where $f+1$ is the order of
$\mathbf{B}$. Denote the set of indices $(i,j)$ in $\mathbf{B}$ with
$b_{i,j}>0$ and $i\leq j$ by $U$.

By Lemma 5.7, $S$ and $S^{\prime}$ have the same number of arcs, denoted by
$m$, and the same length. Denoting the $f$ free sites of $S$ by
$s_{1}<\cdots<s_{f}$, then using Lemma 5.7 again we know that the free sites
of $S^{\prime}$ are also $s_{1},\dots,s_{f}$.

Now, the set $U$ induces a partition of the arcs in $S$ as follows. For each
$(i,j)$ in $U$, let $A_{i,j}$ be the set of arcs in $S$ between blocks
$B_{i}(S)$ and $B_{j}(S)$. Then $A_{i,j}$ and $A_{i^{\prime},j^{\prime}}$ are
disjoint for two distinct pairs $(i,j)$ and $(i^{\prime},j^{\prime})$ in $U$,
and the set of arcs in $S$ is the disjoint union $A_{i,j}$ over $U$ in view of
$\sum_{(i,j)\in U}b_{i,j}=m$. In other words, $\\{A_{i,j}\\}_{(i,j)\in U}$ is
a partition of the set of arcs in $S$. Similarly, let $A^{\prime}_{i,j}$ be
the set of arcs in $S^{\prime}$ between blocks $B_{i}(S^{\prime})$ and
$B_{j}(S^{\prime})$ so that $\\{A^{\prime}_{i,j}\\}_{(i,j)\in U}$ is a
partition of the set of arcs in $S^{\prime}$.

For every $(i,j)$ in $U$, and two arcs $(r,s)$ in $A_{i,j}$ and
$(r^{\prime},s^{\prime})$ in $A^{\prime}_{i,j}$, the set of free sites in
$[r,s]$ is $\\{s_{i+1},s_{i+2},\dots,s_{j-1}\\}$, which is also the set of
free sites in $[r^{\prime},s^{\prime}]$. Together with
$|A_{i,j}|=a_{i,j}=|A^{\prime}_{i,j}|$, this implies that we can fix a
bijection $\phi_{i,j}$ from $A_{i,j}$ to $A^{\prime}_{i,j}$ that preserves
free sites. Now let $\phi$ be the map from the arcs in $S$ to those in
$S^{\prime}$ such that $\phi$ is $\phi_{i,j}$ when restricted to $A_{i,j}$ for
each $(i,j)$ in $U$. Then $\phi$ is a bijection between the arcs in $S$ and
those in $S^{\prime}$ that preserves free sites. Hence $S\sim S^{\prime}$.

Conversely, suppose $S\sim S^{\prime}$. Denote the number of free sites in $S$
by $f$. Then we have $f\geq 1$ since $S$ is proper. By Proposition 5.5,
diagrams $S$ and $S^{\prime}$ have the same block list, and hence also the
same set of free sites, which we enumerate by $s_{1}<s_{2}<\cdots<s_{f}$. Thus
$\mathbf{B}(S)$ and $\mathbf{B}(S^{\prime})$ have the same order $f+1$.

Let $(b_{i,j})=\mathbf{B}(S)$ and $(b^{\prime}_{i,j})=\mathbf{B}(S^{\prime})$.
By Lemma 3.1 it follows that $b_{i,i}=b^{\prime}_{i,i}=0$ for $1\leq i\leq
f+1$. Now fix an arbitrary pair of indices $1\leq i<j\leq f+1$. It suffices to
show $b_{i,j}=b^{\prime}_{i,j}$. To see this, note that $b_{i,j}$ is the
number of arcs in $S$ between block $B_{i}(S)$ and $B_{j}(S)$, which is
precisely the number of arcs $(s_{1},s_{2})$ in $S$ such that the set of free
sites in $[s_{1},s_{2}]$ is $\\{s_{i},\dots,s_{j-1}\\}$. Since $S\sim
S^{\prime}$, there are precisely $b_{i,j}$ arcs
$(s^{\prime}_{1},s^{\prime}_{2})$ in $S^{\prime}$ such that the set of free
sites in $[s^{\prime}_{1},s^{\prime}_{2}]$ is $\\{s_{i},\dots,s_{j-1}\\}$.
This implies $b_{i,j}=b^{\prime}_{i,j}$, from which
$\mathbf{B}(S)=\mathbf{B}(S^{\prime})$ follows.

##  6 Canonical Representatives

In this section, we show that there exists a unique regular diagram within
each equivalence class of the equivalence relation $\sim$ on proper diagrams,
and that this regular diagram has the minimum number of crossing arc pairs
among all diagrams within that equivalence class (see Theorem 6.7).

To this end, first note that for a swap $\epsilon$ on a binary diagram $S$,
$S$ and $\epsilon(S)$ have the same number of non-local crossings. Moreover,
the number of local crossings in $\epsilon(S)$ either increases or decreases
by one. We therefore call a swap $\epsilon$ is called strict if $\epsilon(S)$
has one less crossing than $S$, or equivalently, $\epsilon(S)$ has one less
local crossing than $S$. For example, the swap illustrated in Fig. 9 is
strict.

Next, restricting the definition of regular, we call a block $B$ in a binary
diagram $S$ regular if $B$ does not contain two sites $s_{1}$ and $s_{2}$ for
which there exists a pair of crossing arcs $e_{1}$ and $e_{2}$ in $S$ that are
supported by $s_{1}$ and $s_{2}$, respectively. In particular, a binary
diagram $S$ is regular if and only if every block in $S$ is regular. The
following result shows that blocks in proper diagrams that are not regular
contain some special structures, which can be regarded as the ‘obstruction’ to
their being regular.

######  Lemma 6.1.

A non-regular block in a proper diagram is incident with two adjacent arcs
that are crossing.

######  Proof 6.2.

Suppose that $B$ is a non-regular block in a binary diagram $S$ and let $b$ be
the number of sites in $B$, so that $b\geq 2$. We establish the lemma by using
induction on $b$.

The base case is $b=2$, is straightforward to check. So assume that $b>2$ and
the lemma holds for all non-regular blocks containing at most $b-1$ sites.

Denote the sites in $B$ by $s_{1}<\dots<s_{b}$, enumerated from the smallest
to the largest. Moreover, for $1\leq i\leq b$, denote the site that is base-
paired with $s_{i}$ by $s^{\prime}_{i}$, and let $e_{i}$ be the arc supported
by $s_{i}$ and $s^{\prime}_{i}$. Let $\Sigma$ be the set of arcs which are
supported by at least one site in $B$. Consider the arc $e$ supported by
$s_{b}$ and put $\Sigma^{*}:=\Sigma\setminus\\{e\\}$. Then we have the
following two cases:

Case I: The arc set $\Sigma^{*}$ does not contain a pair of crossing arcs.

By assumption, it follows that $e_{b}$ crosses an arc $e_{i}$ for some $1\leq
i\leq b-1$. Now, assume $s_{b-1}<s^{\prime}_{b-1}$. Then the interval
$[s_{b-1},s^{\prime}_{b-1}]$ contains neither $s_{i}$ nor $s^{\prime}_{i}$ for
$1\leq i<b-1$. It follows that $s^{\prime}_{b}$ is not contained in
$[s_{b-1},s^{\prime}_{b-1}]$ as otherwise $e_{b}$ and $e_{i}$ are not crossing
for $1\leq i\leq b-1$, a contradiction. This implies that $e_{b}$ is crossing
with $e_{b-1}$.

So assume $s_{b-1}>s^{\prime}_{b-1}$. Then the interval
$[s^{\prime}_{b-1},s_{b-1}]$ contains both $s_{i}$ and $s^{\prime}_{i}$ for
$1\leq i<b-1$. It follows that $s^{\prime}_{b}$ is contained in
$[s^{\prime}_{b-1},s_{b-1}]$ as otherwise $e_{b}$ and $e_{i}$ are not crossing
for $1\leq i\leq b-1$, a contradiction. This again implies that $e_{b}$ is
crossing with $e_{b-1}$.

The induction step now follows immediately (note that the induction assumption
is not required for establishing this case).

Case II: The arc set $\Sigma^{*}$ contains a pair of crossing arcs.

Consider the proper diagram $S^{\prime}$ obtained from $S$ by suppressing the
arc $e_{b}$. Since $S$ is proper, there is a block $B^{\prime}$ in
$S^{\prime}$ that contains all the sites in $B$ other than $s_{b}$. Denote the
set of arcs which are supported by some site in $B^{\prime}$ by
$\Sigma^{\prime}$. Then $B^{\prime}$ is a non-regular block in $S^{\prime}$
with precisely $b-1$ sites. Thus by the induction assumption $B^{\prime}$ is
incident with a pair of adjacent crossing arcs $e$ and $e^{\prime}$ in
$S^{\prime}$. Since $e$ and $e^{\prime}$ are obtained from two adjacent
crossing arcs in $S$ that are incident with $B$, the induction step follows.

Remark: Using a more detailed analysis in Case II, the above argument can be
extended to show that the last lemma also holds for binary diagrams.

The last result enables us to show that each proper diagram can be converted
into a regular diagram within its equivalence class by applying a sequence of
strict swaps.

######  Proposition 6.3.

Given a proper diagram $S$, there exists a sequence of strict swaps
$\epsilon_{1},\dots,\epsilon_{t}$ for some $t\geq 0$ such that
$\epsilon_{t}\epsilon_{t-1}\cdots\epsilon_{1}(S)$ is a regular diagram that is
equivalent to $S$.

######  Proof 6.4.

If $S$ is regular, the proposition holds by taking $t=0$. Hence we may assume
in the remainder of the proof that $S$ is not regular. Let $b$ be the number
of arc pairs in $S$ that are locally crossing. Then we have $b\geq 1$ as $S$
is not regular. We now establish the proposition by using induction on $b$.

For the base case $b=1$, which implies that there exists a non-regular block
$B$ in $S$. By Lemma 6.1, there exist two adjacent sites $s_{1}$ and
$s_{2}=s_{1}+1$ in $B$ so that the arc $e_{1}$ supported by $s_{1}$ is
crossing with the arc $e_{2}$ supported by $s_{2}$. Since $S$ is proper, by
Lemma 5.1 we can apply a swap $\epsilon$ at $s_{1}$ to obtain a proper diagram
$S^{\prime}=\epsilon(S)$ with $S^{\prime}\sim S$. Since $e_{1}$ and $e_{2}$
are crossing, it is straightforward to check that diagram $S^{\prime}$
contains one less local crossing than that of $S$, and hence $S^{\prime}$ is
regular, completing the proof of the base case.

Now assume that $b>1$ and the lemma holds for each proper diagram $S$ which
contains at most $b-1$ local crossing arc pairs. An argument similar to the
base case shows that there exists a strict swap $\epsilon_{1}$ so that
$\epsilon_{1}(S)$ is a proper diagram which is equivalent to $S$ and which has
$b-1$ local crossing arc pairs. The proposition now follows by induction.

To illustrate the last result, note that the proper diagram $S_{1}$ in Fig. 3
can be converted to the regular diagram $S_{2}$ in Fig. 3 by three strict
swaps, consecutively acting on sites $1$, $6$ and $7$ (see Fig. 9 where
$\epsilon[1](S_{1})$ and $\epsilon[6]\epsilon[1](S_{1})$ are depicted as
$S^{\prime}_{1}$ and $S^{\prime}_{2}$, respectively).

Now we show that regular diagrams are unique within any equivalence class of
$\sim$.

######  Lemma 6.5.

If $S$ and $S^{\prime}$ are two regular diagrams with $S\sim S^{\prime}$, then
$S=S^{\prime}$.

######  Proof 6.6.

Let $S$ and $S^{\prime}$ be two regular diagrams with $S\sim S^{\prime}$. Then
they have the same length, denoted by $n$, and they contain the same number of
arcs, denoted by $m$. Without loss of generality, we may assume that $n\geq 4$
as otherwise the lemma clearly holds.

By Proposition 5.5 we have $\mathcal{L}(S^{\prime})=\mathcal{L}(S)$ (which we
shall denote by $\mathcal{L}$), and it contains $f+1$ blocks for some $f\geq
1$ as $S$ and $S^{\prime}$ are both proper in view of Lemma 4.1. Note that
this implies that $S$ and $S^{\prime}$ have the same set of free sites. Since
$S\sim S^{\prime}$, we can fix a bijection $\varphi$ that maps each arc $e$ in
$S$ to an arc $\varphi(e)$ such that a free site $s$ in $S$ is covered by $e$
if and only if $s$ is covered by $\varphi(e)$ in $S^{\prime}$.

We now prove the lemma by induction on $m$. The base case is $m=1$. Since $S$
and $S^{\prime}$ have length $n$ and have the same set of two non-free sites,
it follows that $S=S^{\prime}$ and hence the lemma follows. For induction
step, assume $m>1$ and the lemma holds for any two equivalent regular diagrams
with at most $m-1$ arcs.

Since $m>1$, there exist at least two non-free sites in $S$. Denote the first
non-free site in $S$ by $s_{1}$, and let $s_{2}$ be the site in $S$ so that
$(s_{1},s_{2})$ is an arc in $S$. Since $S$ and $S^{\prime}$ have the same set
of free sites, it follows that $s_{1}$ is also the first non-free site in
$S^{\prime}$. Let $s^{\prime}_{2}$ be the site in $S^{\prime}$ so that
$(s_{1},s^{\prime}_{2})$ is an arc in $S^{\prime}$. Denote the block
containing $s_{1}$ by $B_{i}$ and the one containing $s_{2}$ by $B_{j}$. Then
$1\leq i<j\leq f+1$ since $S$ is proper and $B_{i}$ is the first non-empty
block in $\mathcal{L}$. Moreover, if
$(s^{\prime\prime}_{1},s^{\prime\prime}_{2})$ is the arc in $S^{\prime}$ that
is the image of $(s_{1},s_{2})$ under $\varphi$, then $s^{\prime\prime}_{1}$
is contained in $B_{i}$ and $s^{\prime\prime}_{2}$ is contained in $B_{j}$
because $[s_{1},s_{2}]$ and $[s^{\prime\prime}_{1},s^{\prime\prime}_{2}]$
contain the same set of free sites (see Fig. 10 for an illustration of the
notation).

Figure 10: An illustration for one step in the proof Lemma 6.5. Note that $S$
and $S^{\prime}$ have the same set of blocks, among which only three are shown
here.

Next we shall show that $s^{\prime}_{2}$ is contained in $B_{j}$. Note that if
$s_{1}=s^{\prime\prime}_{1}$, then we have
$s^{\prime\prime}_{2}=s^{\prime}_{2}$, and hence $s^{\prime}_{2}$ is contained
in $B_{j}$. Therefore we only need to consider the case
$s_{1}\not=s^{\prime\prime}_{1}$. This implies that
$s_{1}<s^{\prime\prime}_{1}<s^{\prime}_{2}$ holds because $s_{1}$ is the first
non-free site and $B_{i}$ is the first non-empty block which contains $s_{1}$
and $s^{\prime\prime}_{1}$ but not $s_{2}$. In addition, let $B_{t}$ be the
block in $\mathcal{L}$ that contains $s^{\prime}_{2}$. Then we have $i<t\leq
f+1$ and so it remains to show $t=j$.

To this end, first note that if $t<j$, then
$s_{1}<s^{\prime\prime}_{1}<s^{\prime}_{2}<s^{\prime\prime}_{2}$ and hence
$(s_{1},s^{\prime}_{2})$ and $(s^{\prime\prime}_{1},s^{\prime\prime}_{2})$ are
two locally crossing arcs in $S^{\prime}$, a contradiction to the fact that
$S^{\prime}$ is regular. On the other hand, if $j<t$, then consider the arc
$(s^{*}_{1},s^{*}_{2})$ in $S$ such that $(s^{*}_{1},s^{*}_{2})$ is mapped to
$(s_{1},s^{\prime}_{2})$ by $\varphi$. Since $[s^{*}_{1},s^{*}_{2}]$ and
$[s_{1},s^{\prime}_{2}]$ contain the same set of free sites, it follows that
$s^{*}_{1}$ is contained in block $B_{i}$ and $s^{*}_{2}$ is contained in
block $B_{t}$. Note that we may further assume that $s_{1}<s^{*}_{1}$ because
otherwise we have $s_{1}=s^{*}_{1}$, and hence $s_{2}=s^{*}_{2}$, from which
$t=j$ follows. Together with $j<t$, this implies
$s_{1}<s^{*}_{1}<s_{2}<s^{*}_{2}$, and thus $(s_{1},s_{2})$ and
$(s^{*}_{1},s^{*}_{2})$ are two locally crossing arcs in $S$, a contradiction
to the fact that $S$ is regular (see Fig. 10 for an illustration of this
case). Therefore, we have $t=j$ and hence $s^{\prime}_{2}$ is contained in
$B_{j}$.

Our next step is to show that $(s_{1},s_{2})$ is an arc contained in
$S^{\prime}$. To this end, it suffices to show $s^{\prime}_{2}=s_{2}$. Denote
the number of sites in $B_{j}$ that are smaller than $s_{2}$ by $b$, and that
are smaller than $s^{\prime}_{2}$ by $b^{\prime}$. Moreover, let $r+1$ be the
smallest site in $B_{j}$, that is, $B_{j}$ contains $r+1$ but does not contain
$r$. Note that for each site $s_{3}$ in block $B_{j}$ with $s_{3}>s_{2}$,
there exists a site $s^{*}_{3}>s_{3}$ so that $(s_{3},s^{*}_{3})$ is an arc in
$S$ since otherwise $(s_{1},s_{2})$ and the arc supported by $s_{3}$ are local
crossing, a contradiction. Therefore, the number of arcs $(s,s^{*})$ in $S$
such that $r$ is the largest free site in $[s,s^{*}]$ is $b+1$. A similar
argument shows that the number of arcs $(s^{\prime},s^{\prime\prime})$ in
$S^{\prime}$ so that $r$ is the largest free site in
$[s^{\prime},s^{\prime\prime}]$ is $b^{\prime}+1$. Since $S$ is equivalent to
$S^{\prime}$, it follows that $b+1=b^{\prime}+1$ holds, and hence
$s^{\prime}_{2}=s_{2}$.

Noting that $(s_{1},s_{2})$ is a common arc in $S$ and $S^{\prime}$, we
finally consider the two diagrams $S_{o}$ and $S_{o}^{\prime}$ that are
obtained from $S$ and $S^{\prime}$ respectively by suppressing the arc
$(s_{1},s_{2})$. Then $S_{o}$ and $S^{\prime}_{o}$ are two equivalent regular
diagrams with $m-1$ arcs. By the induction assumption we have
$S_{o}=S^{\prime}_{o}$, and thus $S=S^{\prime}$. This completes the proof of
the induction step, from which the theorem follows.

We now prove the main result of this section.

######  Theorem 6.7.

Given a proper diagram $S$, there exists a unique regular diagram $S^{\prime}$
with $S\sim S^{\prime}$. Moreover, $S$ is regular if and only if the number of
crossings in $S$ has the minimal number of crossings in its equivalence class.

######  Proof 6.8.

By Proposition 6.3, there exists a regular diagram $S^{\prime}$ that is
equivalent to $S$. The uniqueness follows from Lemma 6.5.

It remains to show the second part of the theorem, that is, $S$ is regular if
and only if the number of crossings in $S$ is less than or equal to that in
each proper diagram $S^{\prime\prime}$ with $S^{\prime\prime}\sim S$.

First, suppose that $S$ is a regular diagram and assume that $S^{\prime}$ is a
proper diagram $S^{\prime\prime}$ with $S^{\prime\prime}\sim S$. By
Proposition 6.3 and the first part of the theorem, diagram $S$ can be obtained
from $S^{\prime\prime}$ by a sequence of strict swaps, and hence the number of
crossings contained in $S$ is less than or equal to that contained in
$S^{\prime\prime}$.

Conversely, suppose that the number of crossings in $S$ is less than or equal
to that in each proper diagram $S^{\prime\prime}$ with $S^{\prime\prime}\sim
S$. If $S$ is not regular, then by the first part of the theorem there exists
a regular diagram $S^{*}$ that is equivalent to $S$. By Proposition 6.3 and
the first part of the theorem, diagram $S^{*}$ can be obtained from $S$ by a
sequence of strict swaps, and hence the number of crossings contained in
$S^{*}$ is less than that contained in $S$, a contradiction. Therefore $S$ is
regular.

It is worth noting that combining Proposition 6.3 and Theorem 6.7 provides
another characterisation of equivalence between proper diagrams, in addition
to the one given in Theorem 5.9. The proof of this fact is straightforward and
hence omitted here.

######  Corollary 6.9.

Suppose that $S$ and $S^{\prime}$ are two proper diagrams. Then $S\sim
S^{\prime}$ if and only if there exists a sequence of swaps
$\epsilon_{1},\dots,\epsilon_{t}$ for some $t\geq 0$ such that
$S^{\prime}=\epsilon_{t}\epsilon_{t-1}\cdots\epsilon_{1}(S)$ $\square$

##  7 Poset Isomorphisms

In this section we study the two maps $\rho$ and $\sigma$ in Fig. 5 introduced
in Section 1.2. In particular, we will prove the following result:

######  Theorem 7.1.

For $f\geq 3$, $r\geq 0$, and $k\geq 1$, the map

$\displaystyle\rho:({\mathcal{P}}^{r}_{f,k},\preceq)\to(\mathcal{M}^{r}_{f+1,k},\leq)~{}:~{}~{}~{}S\mapsto\mathbf{B}(S)$

is a surjective poset homomorphism. Moreover, its restriction

$\displaystyle\sigma:(\mathcal{B}^{r}_{f,k},\preceq)\to(\mathcal{M}^{r}_{f+1,k},\leq)~{}:~{}~{}~{}S\mapsto\mathbf{B}(S)$

is a poset isomorphism.

Using this theorem, we shall also show that in the case $r=0$ the composition
$\tau^{-1}\sigma$ in Fig. 5 gives a poset isomorphism between
$(\mathcal{B}^{0}_{f,k},\preceq)$ and $(\mathcal{S}_{f+1,k},\subseteq)$ (see
Theorem 7.6 below).

We begin by introducing two types of operations on diagrams which are motived
by the construction in [13, Theorem 2]. Given a diagram $S$ with length $n\geq
2$, the first operation creates its dual diagram $S^{*}$ as follows. Denote
the set of free sites in $S$ by $F(S)$, and create a new set of sites $H(S)$
consisting of sites of the form $i+\frac{1}{2}$ for all $1\leq i<n$. Then
remove each site in $F(S)$, and label all newly created sites (i.e. those in
$H(S)$) and relabel all other sites if necessary to obtain a diagram with
length ${2n-1-|F(S)|}$ and $n-1$ free sites. To illustrate this process, in
Fig. 11 we depict the dual diagram $S^{*}$ of the diagram $S$ in Fig. 6.

Figure 11: Examples of dual and blow-up operations: (i) The dual of the
diagram $S$ in Fig. 6. (ii) The blow-up of the diagram in (i).

Since each arc $(i,j)$ in $S$ satisfies $1<|i-j|<n-1$, the dual diagram
$S^{*}$ contains no tiny arcs since each arc in $S^{*}$ covers at least two
free sites. Moreover, no arc in $S^{*}$ covers all of the free sites in
$S^{*}$. In addition, note that both $S$ and $S^{*}$ have the same size, that
is, the same number of arcs. The next technical lemma provides further
connection between a diagram and its dual.

######  Lemma 7.2.

Given a diagram $S$ with length $n\geq 2$, we have
$\mathbf{A}(S)=\mathbf{B}(S^{*})$.

######  Proof 7.3.

Without loss of generality, suppose that the size of $S$ is $m$ for some
$m\geq 1$ (as otherwise the lemma clearly follows). Let
$(a_{i,j})=\mathbf{A}(S)$ and $(b_{i,j})=\mathbf{B}(S^{*})$. By construction,
diagram $S^{*}$ has $f^{*}=n-1\geq 1$ free sites, and hence $(b_{i,j})$ has
order $n$, the same as that of $(a_{i,j})$. Moreover, since the number of arcs
in $S$ is $m$ and $\mathbf{B}(S^{*})$ is symmetric, it follows that the sum of
the elements $b_{i,j}$ in $\mathbf{B}(S^{*})$ is $2m$, which is the same as
the sum of the elements $a_{i,j}$ in $\mathbf{A}(S)$.

Because $\mathbf{A}(S)$ and $\mathbf{B}(S^{*})$ are two symmetric non-negative
integral matrices of order $n$ whose sum of entries is the same, it suffices
to show that for each $1\leq i\leq j\leq n$, we have $b_{i,j}\geq a_{i,j}$.
This is clearly the case if $a_{i,j}=0$ and hence we may assume that $i<j$ and
$a_{i,j}=1$, that is, $(i,j)$ is an arc in $S$. Now let $(s,s^{\prime})$ be
the arc in $S^{*}$ that is derived from $(i,j)$ in $S$. Let
$u^{*}_{t}~{}(1\leq t\leq f^{*})$ be the $t$-th free site in $S^{*}$ and put
$u_{0}^{*}=0$. By construction, site $s$ is between $u^{*}_{i-1}$ and
$u^{*}_{i}$, and hence is contained in block $B_{i}(S^{*})$. Similarly, we
know that site $s^{\prime}$ is contained in block $B_{j}(S^{*})$. Thus
$(s,s^{\prime})$ is an arc between $B_{i}(S^{*})$ and $B_{j}(S^{*})$, from
which we have $b_{i,j}\geq 1$, as required.

The second operation converts a non-binary diagram $S$ into a binary one
$\delta(S)$ as follows. Consider a site $s$ in a diagram $S$ supporting $b\geq
2$ arcs, that is, $s$ is base-paired with $b$ sites $s_{1}<s_{2}<\dots<s_{b}$.
The blow up at $s$ results in the diagram $\delta_{s}(S)$ that is obtained
from $S$ by replacing the site $s$ with $b$ new sites
$s^{\prime}_{1},s^{\prime}_{2},\dots,s^{\prime}_{b}$, and for $1\leq i\leq b$,
replacing the arc supported by $s$ and $s_{i}$ with a new arc supported by
$s^{\prime}_{i}$ and $s_{i}$. Finally all newly created sites are relabelled
by consecutive integers and all other sites are relabelled if necessary. Note
that each of the newly created sites supports precisely one arc, and hence the
number of sites in $\delta_{s}(S)$ that support at least two arcs is one less
than that in $S$. We now continue this process until a binary diagram, called
the blow up of $S$ and denoted by $\delta(S)$, is obtained. See Fig. 11 for an
example. Note that $\mathbf{B}(S)=\mathbf{B}(\delta(S))$.

Using the dual and blow up operations, we now present a characterisation of
matrices that can be realized as the block matrix of a proper diagram, which
will be key in proving Theorem 7.1.

######  Theorem 7.4.

Suppose that $\mathbf{M}$ is a symmetric non-negative non-trivial integral
matrix. Then there exists a proper diagram $S$ with $\mathbf{B}(S)=\mathbf{M}$
if and only if all diagonal and rainbow elements in $\mathbf{M}$ are zero.
Moreover, if $\mathbf{M}$ is a $(0,1)$-matrix, then $S$ contains no parallel
arcs.

######  Proof 7.5.

The “only if” direction follows from Lemma 3.1. To establish the “if”
direction, we shall first prove the following

Claim: Given a symmetric non-trivial $(0,1)$-matrix $(b_{i,j})=\mathbf{B}$ of
order $m\geq 1$ whose diagonal and rainbow elements are zero, there exists a
proper diagram $S$ containing no parallel arcs such that
$\mathbf{B}(S)=\mathbf{B}$.

Proof of the Claim: Since $\mathbf{B}$ is non-trivial, it contains at least
one non-zero element and hence by the assumptions of the claim we have $m\geq
3$.

Let $H=\\{1\leq i<m:b_{i,i+1}\geq 1\\}$ be the index set of the non-zero
superdiagonal elements in $\mathbf{B}$. Consider the matrix
$\mathbf{B}^{\prime}$ obtained from $\mathbf{B}$ by replacing both $b_{i,i+1}$
and $b_{i+1,i}$ with zero for each index $i$ in $H$. Then all diagonal, semi-
diagonal and rainbow elements in $\mathbf{B}^{\prime}$ are zero. By
Proposition 2.1, there exists a diagram $S^{\prime}$ with
$\mathbf{A}(S^{\prime})=\mathbf{B}^{\prime}$. Now let $S^{*}$ be the dual of
$S^{\prime}$, and let $\delta$ be the blow up of $S^{*}$ so that
$S^{\prime\prime}=\delta(S^{*})$ is a binary diagram. Then we have

$\mathbf{B}(S^{\prime\prime})=\mathbf{B}\left(\delta(S^{*})\right)=\mathbf{B}(S^{*})=\mathbf{A}(S^{\prime})=\mathbf{B}^{\prime},$

where the third equality follows from Lemma 7.2. Using Lemma 3.1 it follows
that $S^{\prime\prime}$ is a proper diagram containing neither tiny nor
parallel arcs.

Now for each index $i$ in $H$, insert a new site $a_{i}$ in block
$B_{i}(S^{\prime\prime})$ and a new site $a_{j}$ in block
$B_{i+1}(S^{\prime\prime})$, and add an arc between these two newly added
sites. Finally, relabel all the sites to obtain a diagram.

Let $S$ be the diagram resulting from $S^{\prime\prime}$ after performing the
above operation for each of the indices in $H$. Then, by construction, $S$ is
a proper diagram which has the same number of free sites as that of
$S^{\prime\prime}$, such that $S$ does not contain any parallel arcs.
Moreover, we have $\mathbf{B}(S)=\mathbf{B}$, from which the claim follows.
$\square$

Now we proceed to establish the “if” direction. To this end, assume that
$(x_{i,j})=\mathbf{M}$ is a symmetric non-negative non-trivial integral matrix
of order $m$ whose diagonal and rainbow elements are zero. Let
${\mathbf{M}}^{\prime}=(x^{\prime}_{i,j})$ be the maximal symmetric
$(0,1)$-matrix of order $m$ dominated by $\mathbf{M}$, that is, where
$x^{\prime}_{i,j}=1$ if and only if $x_{i,j}\geq 1$ holds. Then the diagonal
and rainbow elements in $\mathbf{M}^{\prime}$ are 0. By the Claim, there
exists a diagram $S^{\prime}$ with
$\mathbf{B}(S^{\prime})={\mathbf{M}}^{\prime}$. Let

$A=\\{(i,j)\,:\,1\leq i<j\leq
m~{}~{}\mbox{and}~{}~{}x_{i,j}-x^{\prime}_{i,j}\geq 1\\}$

be the set of positions above the diagonal in which the element in
$\mathbf{M}$ differs from that in $\mathbf{M}^{\prime}$.

For each position $(i,j)$ in $A$, put $t=x_{i,j}-x^{\prime}_{i,j}$. Then we
have $t\geq 1$. Now insert $t$ new sites $a_{1},\dots,a_{t}$ in block $B_{i}$
and $t$ new sites $b_{1},\dots,b_{t}$ in block $B_{j}$, relabel all of the
sites, and for $1\leq p\leq t$, add an arc between the two newly added sites
$a_{p}$ and $b_{p}$. Denote the resulting binary diagram obtained from
$S^{\prime}$ after completing the above operation for each position in $A$ by
$S$. Then by construction it follows that $S$ is binary diagram with
$\mathbf{B}(S)=\mathbf{M}$. By Lemma 3.1 we can further conclude that $S$ is a
proper diagram, from which the theorem follows.

Using this last result, we now prove Theorem 7.1.

Proof of Theorem 7.1: Given a diagram $S$ in $\mathcal{P}^{r}_{f,k}$, we first
show that $\mathbf{B}(S)$ is contained in ${\mathcal{M}}^{r}_{f+1,k}$. Indeed,
because $S$ contains $f$ free sites, the order of $\mathbf{B}(S)$ is $f+1$. As
$S$ is a proper diagram with at least one arc, $\mathbf{B}(S)$ is a non-
trivial symmetric non-negative integer matrix, and by Lemma 3.1 all diagonal
and rainbow elements in $\mathbf{B}(S)$ are zero. Since $S$ is
$k$-noncrossing, by Lemma 3.2 it follows that $\mathbf{B}(S)$ is also
$k$-noncrossing. Moreover, by $\mathbf{r}(\mathbf{B}(S))=\mathbf{r}(S)\leq r$
we have $\mathbf{B}(S)\in{\mathcal{M}}^{r}_{f+1,k}$, as claimed. Therefore,
$\rho$ is indeed a poset homomorphism from $(\mathcal{P}^{r}_{f,k},\preceq)$
to $({\mathcal{M}}^{r}_{f+1,k},\leq)$.

The next step is to show that the map $\rho$ is surjective. To this end, fix a
matrix $\mathbf{M}$ in ${\mathcal{M}}^{r}_{f+1,k}$. Since $\mathbf{M}$ is a
symmetric non-negative integer matrix whose diagonal and rainbow entries are
zero, by Theorem 7.4 there exists a proper diagram $S$ with
$\mathbf{B}(S)=\mathbf{M}$. Note that $S$ contains precisely $f$ free sites.
By Theorem 6.7, we may assume that $S$ is regular as otherwise we can replace
it with the regular diagram in its equivalence class. Since $\mathbf{B}(S)$ is
$k$-noncrossing and $S$ is regular, by Proposition 3.4 it follows that $S$ is
also $k$-noncrossing. Together with
$\mathbf{r}(S)=\mathbf{r}(\mathbf{B}(S))\leq r$, we conclude that $S$ is
contained in $\mathcal{P}^{r}_{f,k}$, and hence the map $\rho$ is surjective,
as required.

The last step is to show that map $\sigma$ is a poset isomorphism. Since
$\rho$ is surjective, by Theorems 5.9 and 6.7 it follows that map $\sigma$ is
a surjective poset homomorphism between $(\mathcal{B}_{f,k}^{r},\preceq)$ and
$(\mathcal{M}^{r}_{f+1,k},\leq)$. Moreover, this map is injective by Theorems
5.9 and 6.7. $\square$

Rephrased in our terminology, Penner and Waterman established a canonical
isomorphism between the poset $(\mathcal{B}^{0}_{f,1},\preceq)$, which
consists of binary $1$-noncrossing diagrams with $f$ free sites and containing
neither parallel nor tiny arcs, and the poset $(\mathcal{S}_{f+1,1},\leq)$,
which consists of all $1$-noncrossing diagrams with at least one arc and
length $f+1$ [13, Theorem 2]. We now conclude this section by using Theorem
7.1 to generalize this result to noncrossing diagrams (cf. Fig. 5).

######  Theorem 7.6.

For $f\geq 3$ and $k\geq 1$, the map

$\displaystyle\tau^{-1}\rho:({\mathcal{P}}^{0}_{f,k},\preceq)\to(\mathcal{S}_{f+1,k},\subseteq)~{}:~{}S\mapsto\mathbf{A}^{-1}(\mathbf{B}(S))$

is a surjective poset homomorphism. Moreover, its restriction to regular
diagrams

$\tau^{-1}\sigma:(\mathcal{B}^{0}_{f,k},\preceq)\to(\mathcal{S}_{f+1,k},\subseteq)~{}:~{}S\mapsto\mathbf{A}^{-1}(\mathbf{B}(S))$

is a poset isomorphism.

######  Proof 7.7.

This clearly follows from Proposition 2.1, Theorem 7.1, and the fact that
$\mathcal{M}_{f+1,k}=\mathcal{M}^{0}_{f+1,k}$.

Note that since $\mathcal{P}^{0}_{f,1}=\mathcal{B}^{0}_{f,1}$, the fact that
$\mathcal{P}^{0}_{f,1}$ and $\mathcal{S}_{f+1,1}$ are isomorphic [13, Theorem
2] is also a consequence of the last result.

##  8 Spaces of $k$-noncrossing Diagrams

In this section we prove our main results. We first investigate some
properties of the poset ${(\mathcal{S}_{m,k},\subseteq)}$, $m\geq 2k+1$, as
defined in Section 2.1. To do this we shall use a generalisation of
triangulations mentioned in the introduction called $k$-triangulations (also
known as multitriangulations) [5, 11, 21], whose definition we now recall.

Figure 12: Examples of diagrams and $k$-triangulations: (i)A diagram $S$ in
$\mathcal{S}_{6,2}$; (ii) A diagram $S_{1}$ in $\mathcal{S}^{*}_{6,2}$; (iii)
A diagram $S_{2}$ in $\mathcal{S}^{o}_{6,2}$. Note that both $S_{1}$ and
$S_{2}$ are also diagrams in $\mathcal{S}_{6,2}$. Moreover,
$\kappa(S)=(S_{1},S_{2})$ holds for the map $\kappa$ defined in the proof of
Lemma 8.1. (iv) A face $T$ in $\mathcal{T}_{6,2}$. It consists of diagonals
$1-4$ and $2-5$, both of which are $2$-relevant. Note that $\theta(T)=S_{2}$
holds for the map $\theta$ in Lemma 8.3.

Consider the convex $m$-gon with vertices $\\{1,2,\dots,m\\}$. A diagonal
between two vertices $i$ and $j$ in the $m$-gon, denoted by $i-j$, is called
$k$-relevant if the length of the shortest path between these two vertices in
the $m$-gon is greater than $k$, that is, $k<|i-j|<m-k$ holds (see Fig. 12(iv)
for an example). Clearly, each diagonal in a set of $(k+1)$ pairwise crossing
diagonals must be $k$-relevant. Denote the set of $k$-relevant diagonals in
the $m$-gon by $\Gamma_{m,k}$, so that each set of $(k+1)$ pairwise crossing
diagonals is a subset of $\Gamma_{m,k}$, and let $\mathcal{T}_{m,k}$ be the
simplicial complex with vertex set $\Gamma_{m,k}$ whose faces are the nonempty
subsets of $\Gamma_{m,k}$ which do not contain $(k+1)$ pairwise crossing
diagonals. A maximal face in $\mathcal{T}_{m,k}$ is called a $k$-triangulation
of the $m$-gon [21] . For example, the face depicted in Fig. 12(iv) is a
$2$-triangulation of the $6$-gon. Note that some authors use the term
$k$-triangulation in a slightly different way, allowing diagonals that are not
necessarily $k$-relevant (see, e.g. [15]).

Motivated by these definitions, we say an arc $e=(s,s^{\prime})$ in a diagram
with length $m$ is $k$-relevant if $k<|s-s^{\prime}|<m-k$. Let
$\mathcal{S}^{o}_{m,k}$ be the set containing all diagrams $S$ in
$\mathcal{S}_{m,k}$ such that every diagonal in $S$ is $k$-relevant, and
$\mathcal{S}^{*}_{m,k}$ denote the set consisting of all diagrams $S$ in
$\mathcal{S}_{m,k}$ in which no diagonal in $S$ is $k$-relevant. See Fig
12(ii-iii) for examples of diagrams in $\mathcal{S}^{*}_{6,2}$ and
$\mathcal{S}^{o}_{6,2}$. Note that $\mathcal{S}^{*}_{m,1}=\emptyset$ and
$\mathcal{S}^{o}_{m,1}=\mathcal{S}_{m,1}$. Moreover, $\mathcal{S}^{*}_{m,k}$
and $\mathcal{S}^{o}_{m,k}$ are two disjoint subposets of $\mathcal{S}_{m,k}$
under $\subseteq$.

The arc set of any diagram $S$ in $\mathcal{S}_{m,k}$ can be partitioned into
two subsets: the one that contains all $k$-relevant arcs in $S$ and the other
its complement. In order to deal with the case that one of these two subsets
is empty, we extend the posets $\mathcal{S}^{*}_{m,k}$ and
$\mathcal{S}^{o}_{m,k}$ by adding a new bottom element to each of them, which
we denote by $0^{*}$ and $0^{o}$, respectively. We denote these new posets by
$\mathcal{\hat{S}}^{*}_{m,k}$ and $\mathcal{\hat{S}}^{o}_{m,k}$, respectively.
Note that we are assuming that $0^{o}$ is distinct from $0^{*}$, and hence
$\mathcal{\hat{S}}^{*}_{m,k}$ and $\mathcal{\hat{S}}^{o}_{m,k}$ are disjoint.

The next lemma will allow us to reduce the problem of understanding the
topology of $|\Delta(\mathcal{S}_{m,k})|$ to that of understanding the
topology of $|\Delta(\mathcal{S}^{*}_{m,k})|$ and
$|\Delta(\mathcal{S}^{o}_{m,k})|$.

######  Lemma 8.1.

For $k\geq 1$ and $m\geq 2k+1$, the poset $\mathcal{S}_{m,k}$ is isomorphic to
the open interval
$(\mathcal{\hat{S}}^{*}_{m,k}\times\mathcal{\hat{S}}^{o}_{m,k})_{>(0^{*},0^{o})}$.
Moreover, we have

(6)
$|\Delta(\mathcal{S}_{m,k})|\cong|\Delta(\mathcal{S}^{*}_{m,k})|*|\Delta(\mathcal{S}^{o}_{m,k})|.$

######  Proof 8.2.

First, consider the map $\kappa_{*}$ that takes a diagram $S$ in
$\mathcal{S}_{m,k}$ to the diagram $\kappa_{*}(S)$ in
$\mathcal{\hat{S}}^{*}_{m,k}$ that consists of all arcs $e$ in $S$ such that
$e$ is not $k$-relevant. In case each of the arcs in $S$ is $k$-relevant, we
set $\kappa_{*}(S)=0^{*}$. Similarly, let $\kappa_{o}$ be the map that takes a
diagram $S$ in $\mathcal{S}_{m,k}$ to the diagram $\kappa_{o}(S)$ in
$\mathcal{\hat{S}}^{o}_{m,k}$ that consists of all $k$-relevant arcs in $S$ or
to $0^{o}$ if none of the arcs in $S$ is $k$-relevant. Then it is
straightforward to check that $\kappa_{*}$ and $\kappa_{o}$ are both poset
homomorphisms.

Now consider the map $\kappa$ that takes a diagram $S$ in $\mathcal{S}_{m,k}$
to $(\kappa_{*}(S),\kappa_{o}(S))$. See Fig. 12(i-iii) for an example in which
$\kappa(S)=(S_{1},S_{2})$. Then $\kappa$ is a poset homomorphism from
$\mathcal{S}_{m,k}$ to
$\mathcal{\hat{S}}^{*}_{m,k}\times\mathcal{\hat{S}}^{o}_{m,k}$. Moreover,
since $S$ contains at least one arc, it follows that
$(\kappa_{*}(S),\kappa_{o}(S))\not=(0^{*},0^{o})$.

On the other hand, given a pair
$(S_{1},S_{2})\in\mathcal{\hat{S}}^{*}_{m,k}\times\mathcal{\hat{S}}^{o}_{m,k}$
that is distinct from $(0^{*},0^{o})$, we consider the necessarily non-trivial
diagram $S$ that is obtained by taking the union of the arcs in $S_{1}$ and
$S_{2}$. Then $S$ is a diagram in $\mathcal{S}_{m,k}$ since $S_{1}$ contains
no $k$-relevant arc, and hence no arc in $S_{1}$ can be contained in a set of
$(k+1)$ pairwise crossing arcs. Furthermore, by construction we have
$\kappa(S)=(S_{1},S_{2})$. Therefore $\kappa$ is a surjective poset
homomorphism from $\mathcal{S}_{m,k}$ to
$(\mathcal{\hat{S}}^{*}_{m,k}\times\mathcal{\hat{S}}^{o}_{m,k})_{>(0^{*},0^{o})}$.
Note that given two distinct diagrams $S$ and $S^{\prime}$ in
$\mathcal{S}_{m,k}$, there exists at least one arc that is contained in one
but not both diagrams, and hence $\kappa(S)\not=\kappa(S^{\prime})$ follows.
This implies that $\kappa$ is also injective, and thus $\kappa$ is an
isomorphism.

Finally, we have

$\displaystyle|\Delta(\mathcal{S}_{m,k})|$ $\displaystyle\cong$
$\displaystyle|\Delta\big{(}(\mathcal{\hat{S}}^{*}_{m,k}\times\mathcal{\hat{S}}^{o}_{m,k})_{>(0^{*},0^{o})}\big{)}|\cong|\Delta\big{(}(\mathcal{\hat{S}}^{*}_{m,k})_{\supset\,0^{*}}\big{)}|*|\Delta\big{(}(\mathcal{\hat{S}}^{o}_{m,k})_{\supset\,0^{o}}\big{)}|$
$\displaystyle\cong$
$\displaystyle|\Delta(\mathcal{S}^{*}_{m,k})|*|\Delta(\mathcal{S}^{o}_{m,k})|.$

Here the second $\cong$ follows from Eq. (2), and the third $\cong$ follows
from the fact that $(\mathcal{\hat{S}}^{*}_{m,k})_{\supset\,0^{*}}$ and
$(\mathcal{\hat{S}}^{o}_{m,k})_{\supset\,0^{o}}$ are isomorphic to
$\mathcal{{S}}^{*}_{m,k}$ and $\mathcal{{S}}^{o}_{m,k}$, respectively.

In view of the last lemma, the topology of $|\Delta(\mathcal{S}_{m,k})|$ is
determined by the topology of $|\Delta(\mathcal{S}^{*}_{m,k})|$ and
$|\Delta(\mathcal{S}^{o}_{m,k})|$. It is straightforward to see that
$|\Delta(\mathcal{S}^{*}_{m,k})|$ is a simplex of dimension $m(k-1)-1$. To
obtain the topology of $|\Delta(\mathcal{S}^{o}_{m,k})|$, we define a natural
map $\theta$ which takes any face $T$ in the face poset
$\mathbf{F}(\mathcal{T}_{m,k})$ of $\mathcal{T}_{m,k}$ with diagonal set
$\\{i_{1}-j_{1},\cdots,i_{t}-j_{t}\\}$ to the diagram ${\theta}(T)$ in
$\mathcal{S}^{o}_{m,k}$ with arc set
$\\{(i_{1},j_{1}),\cdots,(i_{t},j_{t})\\}$. For example, $\theta$ maps the
face in Fig. 4(v) to the diagram in Fig. 4(iii). We now show that this yields
a poset isomorphism.

######  Lemma 8.3.

For two integers $k\geq 1$ and $m\geq 4$ with $m\geq 2k+1$, the map $\theta$
induces a poset isomorphism from the face poset
$\mathbf{F}(\mathcal{T}_{m,k})$ to $\mathcal{S}^{o}_{m,k}$. Moreover, the
simplicial complex $\Delta(\mathcal{S}^{o}_{m,k})$ is a simplicial sphere of
dimension $k(m-2k-1)-1$.

######  Proof 8.4.

It is straightforward to verify that $\theta$ is indeed a poset isomorphism.
Therefore $\Delta(\mathcal{S}^{o}_{m,k})$ is isomorphic to
$\Delta(\mathbf{F}(\mathcal{T}_{m,k}))$. Note that
$\Delta(\mathbf{F}(\mathcal{T}_{m,k}))$ is the (first) barycentric subdivision
of $\mathcal{T}_{m,k}$ and hence it is isomorphic to $\mathcal{T}_{m,k}$ (see,
e.g. [2, p. 1844]). The lemma now follows from the fact that
$\mathcal{T}_{m,k}$ is a simplicial sphere with dimension $k(m-2k-1)-1$ (see,
e.g. Statement 1.3 and Theorem 1.1 in [21]).

Since $\mathcal{S}_{m,1}=\mathcal{S}^{o}_{m,1}$ and $\mathcal{T}_{m,1}$ is the
arc poset $\mathcal{T}_{m}$ of triangulations of an $m$-gon mentioned in
Section 1, note that Lemmas 8.1 and 8.3 can be regarded as a generalization of
the result relating $1$-noncrossing diagrams to triangulations of a polygon as
stated in [13, Theorem 2 and Proposition 3].

We now determine the topology of $|\Delta({\mathcal{S}}_{m,k})|$. Note that
the fact that $|\Delta({\mathcal{S}}_{m,1})|$ is a topological sphere of
dimension $m-4$ as established in [13] is a special case of the following
result with $k=1$.

######  Proposition 8.5.

For any two integers $k\geq 1$ and $m\geq 4$ with $m\geq 2k+1$, the poset
$\mathcal{S}_{m,k}$ is pure and of rank $2k(m-k)-k-m$. Moreover,
$|\Delta(\mathcal{S}_{m,k})|$ is homeomorphic to the join of a simplicial
sphere of dimension $k(m-2k-1)-1$ and an $\left(m(k-1)-1\right)$-simplex.

######  Proof 8.6.

Since $\mathcal{S}^{o}_{m,k}$ and $\mathcal{S}^{*}_{m,k}$ are both pure, by
Lemma 8.1 it follows that the poset $\mathcal{S}_{m,k}$ is pure and of rank
$2k(m-k)-k-m$. The proposition now follows from Lemmas 8.1 and 8.3, and the
fact that $\Delta(\mathcal{S}^{*}_{m,k})$ is an $(m(k-1)-1)$-simplex.

Using Theorem 7.6 and Proposition 8.5, we immediately obtain our two main
results as stated in Section 1, the first of which follows immediately:

######  Theorem 1.1.

For two integers $k\geq 1$ and $f\geq 3$ with $f\geq 2k$,
$|\Delta(\mathcal{B}^{0}_{f,k})|$ is the join of a simplicial sphere of
dimension $k(f-2k)-1$ and an $\left((f+1)(k-1)-1\right)$-simplex. $\square$

######  Theorem 1.2.

For any $r\geq 0$, $f\geq 3$ and $k\geq 1$ with $f\geq 2k$, the poset
$(\mathcal{B}_{f,k}^{r},\preceq)$ is pure and of rank $k(2f-2k+1)+r-f-1$.

######  Proof 8.7.

By Proposition 8.5 and Theorem 7.6, we know that
$(\mathcal{B}^{0}_{f,k},\preceq)$ is pure and of rank $2k(f-k)+k-f-1$. Now
suppose that $S_{1}\prec\cdots\prec S_{t}$ is a maximal chain in
$\mathcal{B}_{f,k}^{r}$ for some $t>0$. Then we have $\mathbf{r}(S_{t})=r$
since otherwise there exists a diagram $S^{*}_{t}$ in $\mathcal{B}_{f,k}^{r}$
with $S_{t}\prec S^{*}_{t}$, a contradiction. Next, for each $1<i\leq t$,
diagram $S_{i}$ contains precisely one more arc than $S_{i-1}$. Thus we have
$t>r$. In addition, this maximal chain induces precisely one maximal chain
$S^{\prime}_{1}\prec\cdots\prec S^{\prime}_{t-r}$ in
$(\mathcal{B}^{0}_{f,k},\preceq)$ by removing all tiny arcs, and all but one
arc in each set of parallel arcs. Therefore, the length of each maximal chain
in $\mathcal{B}_{f,k}^{r}$ is precisely $r$ plus the length of a maximal chain
in $\mathcal{B}^{0}_{f,k}$, from which the theorem immediately follows.

##  9 Discussion

Using the topology of $|\Delta(\mathcal{B}^{0}_{f,1})|$ and the fact that the
natural inclusion $\mathcal{B}^{r}_{f,1}\subseteq\mathcal{B}^{r+1}_{f,1}$ is a
chain homotopy, in [13, Theorem 7] Penner and Waterman show that
$|\Delta(\mathcal{B}^{r}_{f,1})|$ has the homology of a $(f-3)$-dimensional
sphere for $f\geq 3$ and $r\geq 0$. It would therefore be of interest to see
whether or not the following holds: For any $r\geq 0$, $f\geq 3$ and $k\geq
1$, $|\Delta(\mathcal{B}_{f,k}^{r})|$ has the same homology as the join of a
simplicial sphere of dimension $k(f-2k)-1$ and an $((f+1)(k-1)-1)$-simplex.
One approach to try proving this would be to first understand whether or not
the natural inclusion $\mathcal{B}^{r}_{f,k}\subseteq\mathcal{B}^{r+1}_{f,k}$
is a chain homotopy.

Our results also lead to several interesting counting problems. For example,
can formulae be found for the number of elements in $\mathcal{B}_{f,k}^{r}$ or
$\mathcal{P}_{f,k}^{r}$? In addition, using Lemma 8.3 and [21, Theorem 1.2]
(see,also [9, 10]) we can give a formula for the number of facets in
$\Delta(\mathcal{S}^{o}_{m,k})$. It would be interesting to see whether
Theorem 7.6 and Lemma 8.1, could be used together with this formula to
determine the number of facets in $\Delta(\mathcal{B}^{0}_{f,k})$.

Finally, it could be of interest to investigate how the spaces studied here
might help to understand properties of structures of RNA molecules in more
practical applications. For example, although it is known that finding minimal
energy pseudoknots is NP-complete under typical RNA minimum free energy models
(see e.g. [1]), there are efficient algorithms for restricted classes of
pseudoknots (see e.g. [18]). Hence it could be worth investigating if there is
any relationship between the Penner-Waterman poset and collections of RNA
structures satisfying such restrictions, e.g. genus restricted structures [18]
or grammar-based structures (see e.g. [4, 12]). Note that multitriangulations
have connections with several combinatorial structures such as polyonimoes and
twisted surfaces [15], which indicates that there may be some interesting
relationships to uncover.

In another direction it could be interesting to see if our results might be
used to help define and study combinatorial landscapes of $k$-noncrossing RNA
structures. Combinatorial landscape theory involves the study of configuration
spaces (e.g. the space of RNA sequences with fixed length), that come equipped
with some notion of adjacency (e.g. RNA sequences differing in one nucleotide
are adjacent), on which some fitness map is defined that assigns a real number
to each element in the space (e.g. the energy of a minimum free energy
structure for an RNA sequence) [19]. This concept is useful in, for example,
combinatorial optimization where it can be used to design algorithms for
finding (locally) optimal elements in the underlying space. There is a natural
notion of adjacency for multitriangulations that is given in terms of
“flipping” around an edge in a multitriangulation to give another
multitriangulation (this generalizes the well-known notion of flippings in
triangulations – see e.g. [20]). Moreover, any two multitriangulations in
$\mathcal{T}_{m,k}$ can be converted from one to the other through a sequence
of flips (see e.g. [15] and the references therein). Thus, it would be
interesting to explore if these results coupled with our above observations
concerning multitriangulations might be used as a starting point for
investigating landscapes of $k$-noncrossing RNA structures.

## References

  * [1] T. Akutsu, Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots, Discrete Applied Mathematics, 104 (2000), pp. 45–62.
  * [2] A. Björner, Topological methods, Handbook of combinatorics, 2 (1995), pp. 1819–1872.
  * [3] W. Y. Chen, H. S. Han, and C. M. Reidys, Random k-noncrossing RNA structures, Proceedings of the National Academy of Sciences, 106 (2009), pp. 22061–22066.
  * [4] A. Condon, B. Davy, B. Rastegari, S. Zhao, and F. Tarrant, Classifying RNA pseudoknotted structures, Theoretical Computer Science, 320 (2004), pp. 35–50.
  * [5] A. Dress, J. H. Koolen, and V. Moulton, On line arrangements in the hyperbolic plane, European Journal of Combinatorics, 23 (2002), pp. 549–557.
  * [6] J. Gorodkin and W. L. Ruzzo, RNA sequence, structure, and function: computational and bioinformatic methods, Springer, 2014.
  * [7] F. W. Huang and C. M. Reidys, Shapes of topological RNA structures, Mathematical Biosciences, 270 (2015), pp. 57–65.
  * [8] E. Y. Jin, J. Qin, and C. M. Reidys, Combinatorics of RNA structures with pseudoknots, Bulletin of mathematical biology, 70 (2008), pp. 45–67.
  * [9] J. Jonsson, Generalized triangulations and diagonal-free subsets of stack polyominoes, Journal of Combinatorial Theory, Series A, 112 (2005), pp. 117–142.
  * [10] C. Krattenthaler, Growth diagrams, and increasing and decreasing chains in fillings of ferrers shapes, Advances in Applied Mathematics, 37 (2006), pp. 404–431.
  * [11] T. Nakamigawa, A generalization of diagonal flips in a convex polygon, Theoretical Computer Science, 235 (2000), pp. 271–282.
  * [12] M. E. Nebel and F. Weinberg, Algebraic and combinatorial properties of common RNA pseudoknot classes with applications, Journal of Computational Biology, 19 (2012), pp. 1134–1150.
  * [13] R. Penner and M. S. Waterman, Spaces of RNA secondary structures, Advances in Mathematics, 101 (1993), pp. 31–49.
  * [14] R. C. Penner, Moduli spaces and macromolecules, Bulletin of the American Mathematical Society, 53 (2016), pp. 217–268.
  * [15] V. Pilaud and F. Santos, Multitriangulations as complexes of star polygons, Discrete & Computational Geometry, 41 (2009), pp. 284–317.
  * [16] D. Quillen, Homotopy properties of the poset of nontrivial p-subgroups of a group, Advances in Mathematics, 28 (1978), pp. 101–128.
  * [17] C. Reidys, Combinatorial computational biology of RNA: pseudoknots and neutral networks, Springer Science & Business Media, 2010.
  * [18] C. M. Reidys, F. W. Huang, J. E. Andersen, R. C. Penner, P. F. Stadler, and M. E. Nebel, Topology and prediction of RNA pseudoknots, Bioinformatics, 27 (2011), pp. 1076–1085.
  * [19] C. M. Reidys and P. F. Stadler, Combinatorial landscapes, SIAM review, 44 (2002), pp. 3–54.
  * [20] D. D. Sleator, R. E. Tarjan, and W. P. Thurston, Rotation distance, triangulations, and hyperbolic geometry, Journal of the American Mathematical Society, 1 (1988), pp. 647–681.
  * [21] C. Stump, A new perspective on k-triangulations, Journal of Combinatorial Theory, Series A, 118 (2011), pp. 1794–1800.
  * [22] J. W. Walker, Canonical homeomorphisms of posets, European Journal of Combinatorics, 9 (1988), pp. 97–107.