Cycles in random meander systems

Vladislav Kargin111email<EMAIL_ADDRESS>current address: 4400 Vestal
Pkwy East, Department of Mathematics, Binghamton University, Binghamton,
13902-6000, USA

Abstract:

> A meander system is a union of two arc systems that represent non-crossing
> pairings of the set $[2n]=\\{1,\ldots,2n\\}$ in the upper and lower half-
> plane. In this paper, we consider random meander systems. We show that for a
> class of random meander systems, – for simply-generated meander systems, –
> the number of cycles in a system of size $n$ grows linearly with $n$ and
> that the length of the largest cycle in a uniformly random meander system
> grows at least as $c\log n$ with $c>0$. We also present numerical evidence
> suggesting that in a simply-generated meander system of size $n$, (i) the
> number of cycles of length $k\ll n$ is $\sim nk^{-\beta}$, where
> $\beta\approx 2$, and (ii) the length of the largest cycle is $\sim
> n^{\alpha}$, where $\alpha$ is close to $4/5$. We compare these results with
> the growth rates in other families of meander systems, which we call rainbow
> meanders and comb-like meanders, and which show significantly different
> behavior.

##  1\. Setup: Random meander systems

Let $P=\\{(a_{1},b_{1}),\ldots,(a_{n},b_{n})\\}$ be a pairing on the set
$[2n]=\\{1,\ldots,2n\\}$. Pairing $P$ is called non-crossing (“NC”) if there
are no $\alpha<\beta<\gamma<\delta$ such that $\alpha$ is paired with $\gamma$
and $\beta$ with $\delta$. A non-crossing pairing can be realized by a family
of $n$ non-intersecting plane arcs which connect $2n$ points
$(1,0),(2,0)\ldots,(2n,0)\in\mathbb{R}^{2}$ and which are all in the upper
(or, alternatively, all in the lower) half-plane.

Let two non-crossing pairings $P_{1}$ and $P_{2}$ of $[2n]$ be realized by
arcs in the upper and lower half-plane, respectively. We call the resulting
system of curves a meander system $M=(P_{1},P_{2})$. (Sometimes we shorten
“meander system” to m.s.) The pairings $P_{1}$ and $P_{2}$ are called the
upper and lower pairings of $M$, respectively.

A cycle of a meander system is one of its connected components.

A meander system $M$ with only one cycle is called a (closed) meander.
Meanders have first appeared in Poincare’s research on dynamical systems on
surfaces, and the study of meanders was made popular by V. I. Arnold ([3], see
also a review in [18]). The problem of meander enumeration is still not solved
although there are very precise predictions based on numerics and on the
conformal field theory in physics ([10]). Recently, some research appeared on
meander enumeration in situations, where the combinatorial complexity of the
upper and lower pairings is constrained ([4]).

In this paper, we consider meander systems that can have more than one cycle.
In particular, we consider a random meander system $M_{n}$ and study basic
statistical properties of its cycles as $n\to\infty$.

We are mostly interested in the situation when a meander system $M_{n}$ is
chosen with equal probability from all meander systems on $[2n]$. This is
equivalent to choosing upper and lower pairings independently and with the
uniform distribution.

We consider meander systems with other distributions as well, in particular
simply generated, random comb-like, and random rainbow m.s. They will be
defined later and will be used for comparison with the results for uniformly
distributed m.s. When we say “a random meander system” without qualification
we mean a uniformly distributed m.s.

Figure 1. A meander system on $2\times 30$ points with $8$ cycles.

Notation The notation $g_{n}=O(f_{n})$ means that
$\limsup_{n\to\infty}|g_{n}/f_{n}|<\infty$; and $g_{n}=o(f_{n})$ means that
$\lim_{n\to\infty}|g_{n}/f_{n}|=0$. We write $f_{n}=\Omega(g_{n})$ as meaning
the same thing as $g_{n}=O(f_{n})$, and we write $f_{n}\sim g_{n}$ to denote
that $f_{n}=g_{n}(1+o(1))$. The notation $f_{n}\ll g_{n}$ means that
$f_{n}=g_{n}o(1)$, and $f_{n}\approx g_{n}$ means $\log f_{n}\sim\log g_{n}$.

The remainder of the paper is organized as follows. Section 2 discusses the
number of cycles in random meander systems. Section 3 is about the length of
the largest cycle in a random m.s. Section 4 provides some additional
numerical evidence and concludes with remarks. And Appendix provides proofs
which were relegated from the main body of the paper.

##  2\. Number of cycles

###  2.1. Random meander systems with the uniform distribution

Numerics suggest that when the number of points $2n$ grows, the number of
cycles $c(M_{n})$ in a random meander system $M_{n}$ converges in distribution
to a Gaussian limit,

$\displaystyle\frac{c(M_{n})-an}{b\sqrt{n}}\to\mathcal{N}(0,1),$

for some positive constants $a$ and $b$ (with $a\approx 0.23$ and $b\approx
0.42$.) This limiting behavior is not easy to prove, and we are only going to
show that the expectation of $c(M_{n})$ grows at least linearly with $n$.

A related study [12] considers the enumeration of meander systems that have
the number of cycles $c(M_{n})=n-r$, where $r\geq 0$ is a fixed integer. Their
formulas imply that the probability of a random m.s. with $c(M_{n})=n-r$ is
exponentially small $\sim c_{r}n^{3/2+r}4^{-n}$.

In order to prove that the number of cycles grows at least linearly, we are
going to count the number of special cycles which we call “ringlets”. A
ringlet $\mathfrak{O}_{x}$, $1\leq x\leq 2n-1$, is a connected component that
consists of arcs that connect $x$ and $(x+1)$ both in upper and lower
pairings. For example, there are $5$ ringlets in Figure 1.

######  Theorem 2.1.

Let $M_{n}$ be a (uniformly distributed) random m.s. on $2n$ points, and let
$c_{o}(M_{n})$ denote the total number of ringlets in $M_{n}$. Then,
$\mathbb{E}c_{o}(M_{n})>(n+1)/8$. Moreover, for $n\to\infty$,

$\displaystyle\mathbb{E}c_{o}(M_{n})\sim\frac{n}{8}.$

Since the number of cycles greater than the number of ringlets, Theorem 2.1
immediately implies the desired result about the number of cycles.

######  Corollary 2.2.

Suppose $M_{n}$ is a random meander system on $2n$ points, and let $c(M_{n})$
denote the number of cycles of $M_{n}$. Then,

$\displaystyle\mathbb{E}\,c(M_{n})>\frac{n+1}{8}$

###### Proof of Theorem 2.1.

Let $I_{x}^{u}$ be the indicator of the event that the upper pairing contains
the pair $(x,x+1)$. Define indicator $I^{l}_{x}$ similarly for the lower
pairing. Then, $I^{u}_{x}I^{l}_{x}$ is the indicator for the event that the
meander system contains the ringlet $\mathfrak{O}_{x}$. We write,

$\displaystyle\mathbb{E}c_{o}(M_{n})=\mathbb{E}\sum_{x=1}^{2n-1}I^{u}_{x}I^{l}_{x}=\sum_{x=1}^{2n-1}\mathbb{E}(I^{u}_{x})\mathbb{E}(I^{l}_{x})=\sum_{x=1}^{2n-1}p_{n}(x)^{2},$

where $p_{n}(x)$ is the probability that arc $(x,x+1)$ is in the random NC
pairing of $[2n]$.

The number of all non-crossing pairing is the Catalan number
$C_{n}=\binom{2n}{n}/(n+1)$, and the number of non-crossing pairings of the
set $[2n]\backslash\\{x,x+1\\}$ is the Catalan number $C_{n-1}$. (The arc from
$x$ to $x+1$ does not create any additional obstructions to non-crossing
pairings of this set.) Hence,

$\displaystyle p_{n}(x)=\frac{C_{n-1}}{C_{n}}=\frac{n+1}{2(2n-1)}.$

Therefore,

$\displaystyle\mathbb{E}c_{o}(M_{n})=\sum_{x=1}^{2n-1}\Big{(}\frac{n+1}{2(2n-1)}\Big{)}^{2}=\frac{1}{8}\frac{(n+1)^{2}}{n-\frac{1}{2}}>\frac{n+1}{8}.$

It is also clear from this formula that $\mathbb{E}c_{o}(M_{n})\sim n/8$. ∎

The proof gives an asymptotic expression for the expected number of ringlets,
$\mathbb{E}c_{o}(M_{n})\sim n/8$. One can further estimate the expected number
of cycles for other shapes and show that these expected numbers grow linearly
with $n$. The calculations increase in difficulty when the shapes become more
complex.

For example, consider a subclass of all cycles of half-length 2, which we call
staples, where upper staple $[x,y]$, with $x<y-1$, is a cycle that consists of
two pairs, $(x,x+1)$ and $(y,y+1)$, in the lower pairing, and two pairs,
$(x,y+1)$ and $(x+1,y)$, in the upper pairing. A lower staple is defined
similarly by exchanging the roles of lower and upper pairings.

The following proposition is proved in the appendix.

######  Proposition 2.3.

Let $M_{n}$ be a random m.s. on $2n$ points, and let $c_{st}(M_{n})$ denote
the total number of lower and upper staples in $M_{n}$. Then, for
$n\to\infty$,

$\displaystyle\mathbb{E}c_{st}(M_{n})\sim\frac{n}{32}.$

For another example, all cycles of half-length 1 are rings: A ring of radius
$r$ is a cycle that consists of a pair $(x,y)$ present both in the upper and
lower pairings, with $y-x=2r+1$. (A ringlet is a ring of radius $r=0$.)

The following result gives an estimate on the expected number of rings. It is
proved in the appendix.

######  Proposition 2.4.

Let $M_{n}$ be a random m.s. on $2n$ points and let $c_{O}(M_{n})$ denote the
number of rings in $M_{n}$. Then, for $n\to\infty$,

$\displaystyle\mathbb{E}c_{O}(M_{n})\sim
n\Big{(}\frac{2}{\pi}-\frac{1}{2}\Big{)}.$

Numerically, $\mathbb{E}c_{O}(M_{n})\sim(n/8)\times 1.092958$, so the rings of
radius $\geq 1$ (“non-ringlet” rings) are responsible for only $\approx 9.3\%$
of all rings in a random meander system.

Before proceeding further, let us introduce some additional definitions.

The support $(x_{1}<x_{2}<\ldots<x_{2k})$ of a cycle $\mathcal{C}$ in a m.s.
$M$ is the intersection of the cycle with the line $y=0$.

The half-length of a cycle $\mathcal{C}$ with support $(x_{1},\ldots,x_{2k})$
is the number $k$.

Two cycles $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ are topologically
equivalent if there is an homeomorphism of the plane that maps
$\mathcal{C}_{1}$ to $\mathcal{C}_{2}$ and maps the upper and lower half-
planes to themselves. In this case we say that they have the same shape.

For example, all rings are topologically equivalent. All cycles of half-length
2 are topologically equivalent to an upper or a lower staple. An upper and a
lower staples have different shapes because the reflection across the line
$y=0$ (or a rotation by the angle $\pi$ around a point on this line) does not
preserve the upper and lower half-planes.

The shape of a cycle $\mathcal{C}$ can be defined in purely combinatorial
terms. If $(x_{1}<x_{2}<\ldots<x_{2k})$ is the support of $\mathcal{C}$, then
an oriented path along $\mathcal{C}$ in the clockwise direction starting from
$x_{1}$ gives a sequence in which the points of the support are visited. This
sequence determines a permutation $\pi\in S_{2k}$: $(x_{1}\to x_{\pi(1)}\to
x_{\pi\circ\pi(1)}\to\ldots\to x_{\pi^{2k-1}(1)}\to x_{1})$.

This permutation is invariant under the homeomorphisms of the plane that
preserve the upper and lower half-planes, and it determines the shape of the
cycle.

We will label the shape of a cycle by this permutation.

For example, the shape of any ring is $\pi=(12)$, the shape of an upper staple
is $(1432)$, the shape of a lower staple is $(1234)$. Note that by the
connectedness of the cycle $\mathcal{C}$, the permutation is a “cycle”
permutation in $S_{2k}$, (where $k$ is the half-length of $\mathcal{C}$).
However, the non-crossing condition rules out some of the cycles in $S_{2k}$.
For example, $(1324)$ is not possible. In fact, it is clear that the shape
permutations can be put in a bijection with “proper” meanders on the set
$[2k]$, that is, with meander systems that consist of only one connected
component.

Let $f_{n}\gtrsim g_{n}$ mean that there is a sequence $\varepsilon_{n}\to 0$,
such that $f_{n}\geq g_{n}(1+\varepsilon_{n})$ for all $n$. Similarly
$f_{n}\lesssim g_{n}$ means that there is $\varepsilon_{n}\to 0$ such that
$f_{n}\leq g_{n}(1+\varepsilon_{n})$ for all $n$.

######  Theorem 2.5.

Let $c_{k,\pi}(M_{n})$ be the number of cycles of half-length $k$ with shape
$\pi\in S_{2k}$ which occur in a (uniformly distributed) random m.s. $M_{n}$
on $2n$ points. Then, for every $k\geq 1$,

$\displaystyle\mathbb{E}c_{k,\pi}(M_{n})\gtrsim 2n\times 16^{-k},$

In the proof we use the concept of a cluster cycle.

######  Definition 2.6.

A cluster cycle of half-length $k$ is a cycle of half-length $k$ with support
$(x+1,x+2,\ldots,x+2k)$ for some $x\in\\{0,\ldots,2n-2k\\}$.

In other words, a cluster cycle has no gaps in its support. For example, a
ringlet is a cluster cycle, while all other rings with radius $k\geq 1$ are
not cluster cycles.

###### Proof of Theorem 2.5.

Instead of counting all cycles of half-length $k$ that have shape $\pi$, we
will compute the expected number of all cluster cycles with these half-length
and shape. Call this number $c_{k,\pi}^{(cl)}(M_{n})$. Let
$\mathcal{C}_{x,\pi}$ be the cluster cycle with shape $\pi$ supported on
$(x+1,x+2,\ldots,x+2k)$ where $0\leq x\leq 2n-2k$. Let $I_{x,\pi}$ be the
indicator of the event that a random m.s. contains cycle
$\mathcal{C}_{x,\pi}$. Then, we have
$\mathbb{E}c_{k,\pi}(M_{n})\geq\mathbb{E}c_{k,\pi}^{(cl)}(M_{n})$, and

(1)
$\displaystyle\mathbb{E}c_{k,\pi}^{(cl)}(M_{n})=\sum_{x=0}^{2n-2k}\mathbb{E}(I_{x,\pi})$
$\displaystyle=\sum_{x=0}^{2n-2k}\Big{(}\frac{C_{n-k}}{C_{n}}\Big{)}^{2}=(2n-2k+1)\Big{(}\frac{C_{n-k}}{C_{n}}\Big{)}^{2}\sim
2n16^{-k}.$

where the second equality follows because $\mathbb{E}(I_{x,\pi})$ is the
probability that the random m.s. contains $\mathcal{C}_{x,\pi}$ and this
probability is $C_{n-k}^{2}/C_{n}^{2}$. Indeed, there are exactly
$C_{n-k}^{2}$ possible ways to arrange the upper and lower non-crossing
pairings of the residual set $\\{1,\ldots,x,x+2k+1,\ldots,2n\\}$ and every of
these pairings remains non-crossing if we add the pairings from the cycle
$\mathcal{C}_{x,\pi}$. (Here we use the fact that $\mathcal{C}_{x,\pi}$ is a
cluster cycle.) Therefore, the probability is $C_{n-k}^{2}/C_{n}^{2}$.

The asymptotic (1) for $c_{k,\pi}^{(cl)}(M_{n})$ implies the statement of the
theorem. ∎

We have seen that the count of rings is dominated by ringlets. So, in general
we can ask the question if the count of cycles is dominated by cluster cycles.
We can use the asymptotic in the proof of Theorem 2.5 to obtain an upper bound
on the expected number of cluster cycles.

The number of possible shapes of a cycle with the half-length $2k$ equals the
number of “proper” meanders, that is, the meander systems with only one cycle.
Let $R_{k}$ denote the number of proper meanders on the set $[2k]$. (We use
the notation $R_{k}$ instead of more traditional $M_{k}$ to avoid the
confusion with our notation for meander systems.) For these numbers, it is
known that they are super-additive: $R_{k}R_{l}\leq R_{k+l}$. By Fekete’s
lemma, this implies the existence of the limit

$\displaystyle R=\lim_{k\to\infty}(R_{k})^{1/k}=\sup_{k>1}(R_{k})^{1/k}.$

In particular, by the second equality,

(2) $R_{k}\leq R^{k},\text{ for all }k\geq 1.$

In [18], Lando and Zvonkin calculated the growth rate for a related class of
irreducible meander systems and conjectured that for proper meanders,
$R=12.26\ldots$. In [10], it is conjectured that $R_{k}\sim ck^{-\alpha}R^{k}$
with an explicit formula for $\alpha>0$. Theoretical bounds for $R$ have been
given in [18] and [1]. In particular, the lower and upper bounds $11.380\leq
R\leq 12.901\ldots$ are given in [1].

With respect to numerical evidence, Table 1 in [19] lists meander numbers up
to $R_{14}=61606881612$ (with a reference to calculations by Reeds and Shepp).
These numbers are confirmed in [11]. In [15] and [16], the calculations have
been extended to $R_{24}$ by using a different method. Table 1 in [16] gives
$R_{24}=794337831754564188184$.

Figure 2. This plot shows $8\overline{Y_{k}}/n$, where $\overline{Y}_{k}$ is
the average number of cycles of half-length $k$ in a random meander of half-
length $n=10^{5}$. The averaging is done over a sample of $1000$ random
meanders. For the prediction curve, $8\overline{Y_{k}}/n$ is set equal to
$k^{-2}$. The upper and lower plots have linear and logarithmic scales along
the $x$-axis, respectively.

######  Proposition 2.7.

Let $c_{k}^{(cl)}(M_{n})$ be the number of cluster cycles of half-length $k$
in a random m.s. $M_{n}$ on $2n$ points. Then, for every $k>0$,

$\displaystyle\mathbb{E}c_{k}^{(cl)}(M_{n})\lesssim 2n\gamma^{-k},$

where $\gamma=1.2402\ldots$.

###### Proof.

We have

$\displaystyle c_{k}^{(cl)}(M_{n})=\sum_{\pi}c_{k,\pi}^{(cl)}(M_{n}).$

The number of shapes of half-length $k$ is equal $R_{k}$, and for every fixed
$k\geq 1$ we use asymptotic (1) in order to find that

$\displaystyle\mathbb{E}c_{k}^{(cl)}(M_{n})\sim R_{k}2n16^{-k}.$

By using the exact upper bound on the number of meanders $R_{k}$ (2), we have
that for every fixed $k\geq 1$,

$\displaystyle\mathbb{E}c_{k}^{(cl)}(M_{n})\lesssim
2n\Big{(}\frac{16}{12.901}\Big{)}^{-k}=2n(1.2402...)^{-k}.$

∎

From numerics, however, it appears that for a wide range of $k$, the function
$\mathbb{E}c_{k}(M_{n})$ (the expected number of cycles of half-length $k$)
does not exhibit exponential decline in $k$. Instead, it appears that for
large $n$ and slowly growing $k_{n}\ll n$, this function can be more
accurately described as $cnk_{n}^{-\beta}$ where $\beta\approx 2$. (For larger
values of $k$ it appears that $\beta$ becomes smaller but the decline is still
polynomial, not exponential.) This suggests that for large $k$ non-cluster
cycles play a significant role. See Figure 2 for an illustration. In this
illustration $n=10^{5}$ and the largest cycle is expected to be of order
$10^{4}$.

###  2.2. Simply generated random meander systems

In this section we describe an extension of Theorem 2.1 to a more general
class of distributions on meander systems. The results are similar to the case
of the uniform distribution and are not used later. While we provide all
necessary definitions, the reader unfamiliar with simply generated trees can
safely skip this section.

In order to define simply generated m.s., we recall a bijection between NC
pairings on $2n$ points and the set of rooted planar trees on $n+1$ vertices.

We denote this bijection as $\beta:\mathcal{T}_{n+1}\to\mathcal{P}_{n}$, where
$\mathcal{T}_{n+1}$ is the set of all rooted planar trees on $n+1$ vertices,
and $\mathcal{P}_{n}$ is the set of non-crossing pairings of $[2n]$.

Figure 3. A bijection between NC pairings and planar trees.

The bijection is illustrated in Figure 3.222Formally, a tree is mapped to a
Dyck walk path and then the path is mapped to an NC pairing. Both maps are
standard, see, for example, note I.48 on p.77 in [8]. It preserves the
internal structure of pairings and trees in the sense that a pair in a pairing
corresponds to an edge of the corresponding tree. (The edge crosses the arc of
the corresponding pair.) If we identify the tree edge $(u,v)$ from parent $u$
to its child $v$ with vertex $v$, then we obtain a bijection between pairs of
a pairing and non-root vertices of the corresponding planar tree. In
particular, every pair $(x,x+1)$ corresponds to a tree leaf. More generally, a
pair $(x,x+2k+1)$ corresponds to a vertex of out-degree $k$.

Now, recall the definition of simply-generated random rooted planar trees
$\mathcal{T}_{n}$ on $n$ vertices. Let $w_{0}>0,w_{1},w_{2},\ldots$ be a
sequence of non-negative numbers (“weights”). Define the weight of a tree $T$
as

$\displaystyle w(T)=\prod_{d=0}^{\infty}w_{d}^{N_{d}(T)},$

where $N_{d}(T)$ denote the number of vertices of out-degree $d$ in the tree
$T$.

A simply-generated random tree with weight sequence
$w=(w_{0},w_{1},w_{2},\ldots)$ is a tree in $\mathcal{T}_{n}$ chosen at random
with probability $w(T)/Z_{n}$, where $Z_{n}=\sum_{T\in\mathcal{T}_{n}}w(T)$.

The uniform distribution on planar random trees corresponds to the weight
sequence $w_{i}=1$ for all $i$ (and to equivalent weight sequences). Simply
generated trees can be alternatively defined in terms of Galton-Watson trees
conditioned to have a fixed number of vertices. See [14] for an overview of
these topics.

######  Definition 2.8.

Let $\vec{w}=(w_{0}>0,w_{1},w_{2},\ldots)$ and
$\vec{w}^{\prime}=(w^{\prime}_{0}>0,w^{\prime}_{1},w^{\prime}_{2},\ldots)$ be
two sequences of non-negative weights, and let $(T_{n},T^{\prime}_{n})$ be two
independent simply generated trees on $n+1$ vertices with weight sequences
$\vec{w}$ and $\vec{w}^{\prime}$, respectively. Then, a simply generated
meander system on 2n points is the pair $(P_{n},P^{\prime}_{n})$, where
$P_{n}$ and $P^{\prime}_{n}$ are non-crossing partitions of $[2n]$ obtained by
the bijection $\beta$ from the trees $T_{n}$ and $T^{\prime}_{n}$,
respectively.

We call the simply generated meander system symmetric if the weight sequences
for the upper and lower pairings are the same, $\vec{w}^{\prime}=\vec{w}$.

For example, a random meander system with the uniform distribution is a
symmetric simply generated m.s. with weights
$\vec{w}^{\prime}=\vec{w}=(1,1,1,\ldots)$.

For a weight sequence $(w_{0},w_{1},\ldots)$, let
$\theta(t):=\sum_{k=0}^{\infty}w_{k}t^{k}$, and let $\rho$ be the radius of
convergence for this series. Define
$\psi(t):=\frac{t\theta^{\prime}(t)}{\theta(t)}$. One can check that $\psi(t)$
is a non-decreasing function on $[0,\rho)$. Define

$\displaystyle\tau=\begin{cases}\inf\\{t:\psi(t)=1\\},&\text{ if
}\sup_{t\uparrow\rho}\psi(t)\geq 1,\\\ \rho,&\text{ otherwise.}\end{cases}$

######  Theorem 2.9.

Let $M_{n}$ be a symmetric simply generated meander system on $2n$ points, and
let $c(M_{n})$ denote the number of connected components of $M_{n}$. Then,

$\displaystyle\mathbb{E}\,c(M_{n})\gtrsim\frac{1}{2}\Big{(}\frac{w_{0}}{\theta(\tau)}\Big{)}^{2}n.$

Remark: For non-symmetric meander systems the result of Theorem 2.9 is also
likely to hold, with a suitable modification on the coefficient before $n$.
However, in order to use our method, one needs the asymptotic equidistribution
property of the pairs $(x,x+1)$ in interval $[1,2n]$, for either lower or
upper NC pairing, and this property is not obvious in the general, non-uniform
case.

###### Proof of Theorem 2.9.

Let $c_{o}(M_{n})$ denote the number of ringlets in the meander system
$M_{n}$. Obviously, $c(M_{n})\geq c_{o}(M_{n})$ and it is enough to give a
lower bound for $\mathbb{E}\,c_{o}(M)$.

As in the proof of Theorem 2.1,

$\displaystyle\mathbb{E}c_{o}(M_{n})$
$\displaystyle=\sum_{x=1}^{2n-1}p_{n}(x)^{2},$

where $p_{n}(x)$ is the probability that $(x,x+1)$ is in a given random NC
pairing of $[2n]$.

The sum $\sum_{x=1}^{2n-1}p_{n}(x)$ equals the expected number of pairs of the
form $(x,x+1)$ in a random pairing. The pairs of this form are mapped to
leaves of the corresponding tree by the bijection $\beta^{-1}$ . Hence,
$\sum_{x=1}^{2n-1}p_{n}(x)=\mathbb{E}N_{0}(T_{n})$, where $N_{0}(T_{n})$
denotes the number of leaves in a tree $T_{n}$.

By Theorem 7.11 in [14], we have that $N_{0}(T_{n})/n$ converges in
probability to $\pi_{0}=w_{0}/\theta(\tau)$, which by dominated convergence
implies that $\mathbb{E}\big{[}N_{0}(T_{n})/n\big{]}\to\pi_{0}$, that is,
$\mathbb{E}N_{0}(T_{n})=\sum_{x=1}^{2n-1}p_{n}(x)\sim\pi_{0}n$.

Then, by the Cauchy-Schwarz inequality,

$\displaystyle(2n-1)\sum_{x=1}^{2n-1}p_{n}(x)^{2}\geq\Big{(}\sum_{x=1}^{2n-1}p_{n}(x)\Big{)}^{2}=(\mathbb{E}N_{0}(T_{n}))^{2}\sim\Big{(}\frac{w_{0}n}{\theta(\tau)}\Big{)}^{2}.$

This implies that

$\displaystyle\mathbb{E}c_{o}(M_{n})\gtrsim\frac{1}{2}\Big{(}\frac{w_{0}}{\theta(\tau)}\Big{)}^{2}n.$

∎

###  2.3. Random rainbow m.s.

There is another method to introduce a probability measure on a subset of
meander systems, which have recently appeared in the literature. A rainbow
pairing of the set $[2m]$ is the pairing
$P_{1}(m)=\\{(1,2m),(2,2m-1),\ldots,(m,m+1)\\}$. Its geometric representation
consists of $m$ arcs that look like a rainbow. A shifted rainbow pairing is a
pairing of the set $\\{k,k+1,\ldots,2m+k-1\\}$, for some $k\in\mathbb{N}$,
which is defined as
$P_{k}(m)=\\{(k,2m+k-1),(k+1,2m+k-2),\ldots,(m+k-1,m+k)\\}$.

Figure 4. A rainbow meander system with parameters $\alpha=[15,5,11]$ and
$\beta=[18,13]$.

A rainbow meander system
$M_{n}(\alpha_{1},\ldots,\alpha_{s}|\beta_{1},\ldots,\beta_{t})$ has the upper
and lower pairings which are unions of shifted rainbow pairings,
$P_{u}=\cup_{i=1}^{s}P_{r_{i}}(\alpha_{i})$, where
$r_{i}=1+2\sum_{j=1}^{i-1}\alpha_{j}$, and
$P_{l}=\cup_{i=1}^{t}P_{r^{\prime}_{i}}(\beta_{i})$, where
$r^{\prime}_{i}=1+2\sum_{j=1}^{i-1}\beta_{j}$. It is required that
$\sum_{i=1}^{s}\alpha_{i}=\sum_{i=1}^{t}\beta_{i}=n$. See illustration in
Figure 4.

A random rainbow meander system of type $(s,t)$ on the set $[2n]$ is a rainbow
m.s. $M_{n}(\vec{\alpha}|\vec{\beta})$, where integer vectors
$\vec{\alpha}=(\alpha_{1},\ldots,\alpha_{s})$ and
$\vec{\beta}=(\beta_{1},\ldots,\beta_{t})$ are taken uniformly and
independently in the simplices $\sum_{i=1}^{s}\alpha=n$, $\alpha_{i}\geq 1$
and $\sum_{i=1}^{t}\beta_{i}=n$, $\beta_{i}\geq 1$, respectively.

The constraint $\sum_{i=1}^{s}\alpha_{i}=n$ implies that random variables
$\alpha_{i}$ are not independent. A simpler random system relaxes this
constraint by allowing a random number of points $2n$. Namely, a relaxed
rainbow meander system of type $(s,1)$ and size $N$ is a rainbow m.s.
$M_{N}(\vec{\alpha}|\beta)$ where coordinates of the vector
$\vec{\alpha}=(\alpha_{1},\ldots,\alpha_{s})$ are taken independently and
uniformly in the set $[N]$, and $\beta=\sum_{i=1}^{s}\alpha_{s}$.

Explicit formulas for the number of cycles in a rainbow meander system are
known only for meander systems of type $(2,1)$ and $(3,1)$, that is, only for
meander systems that have one rainbow at the bottom and two or three rainbows
at the top. In those cases, they are

(3) $c(M)=\gcd(\alpha_{1},\alpha_{2}),$

and

(4) $c(M)=\gcd(\alpha_{1}+\alpha_{2},\alpha_{2}+\alpha_{3}),$

respectively. (See [7].)

######  Theorem 2.10.

Let $M_{2,N}$ be a relaxed random rainbow meander of type $(2,1)$ and size
$N$. Then for the number of cycles $c(M_{2,N})$, the following equations hold:

$\displaystyle\mathbb{P}\Big{(}c(M_{2,N})=x\Big{)}$
$\displaystyle=\frac{6}{\pi^{2}}\frac{1}{x^{2}}+O\Big{(}\frac{\log(N/x)}{Nx}\Big{)},$
$\displaystyle\mathbb{E}\Big{(}c(M_{2,N})\Big{)}$
$\displaystyle=\frac{6}{\pi^{2}}\log
N+C+O\Big{(}\frac{\log(N)}{\sqrt{N}}\Big{)},$
$\displaystyle\mathbb{E}\Big{(}c(M_{2,N})^{2}\Big{)}$
$\displaystyle=\frac{N}{3}\Big{(}\frac{2\zeta(2)}{\zeta(3)}-1\Big{)}+O(\log
N),$

where $\zeta(z)$ is Riemann’s zeta function.

###### Proof.

For $c(M_{2,N})$, the formula (3) is applicable, in which $\alpha_{1}$ and
$\alpha_{2}$ are taken uniformly and independently at random from interval
$[N]$. Then, all claims of the theorem follow from the classical results for
the greatest common divisor of two random integers. See, for example, [6]. ∎

This result shows that the number of cycles in a random rainbow m.s. of type
$(2,1)$ behaves very differently than in a general random m.s. First of all,
the probability that a rainbow m.s. has some fixed small number of cycles
converges to a positive number as the size of m.s. grow. For example, the
probability that the m.s. has only one cycle converges to $\frac{6}{\pi^{2}}$.
This is dramatically different from the situation for general random m.s.,
where this probability is exponentially small in the size of the m.s.

Second, the expected number of cycles is logarithmic in $N$, while in a
general random m.s. this quantity is linear in the size of the system $n$.
This suggests that a typical rainbow m.s. has a small number of long cycles,
in contrast to a typical general m.s. where it has a large number of small
cycles.

Finally, the variance of the number of cycles is of order $N$, which implies
that with some small probability a rainbow m.s. of type $(2,1)$ still can have
a large number of small cycles.

For random rainbow m.s. of higher types, the question about the distribution
of the number of cycles is more difficult. Even for the type $(3,1)$, for
which an explicit formula (4) is available, the calculation of the
distribution of the $\gcd(\alpha_{1}+\alpha_{2},\alpha_{2}+\alpha_{3})$ is
difficult. The numerical evaluations show that the law in this case is the
same as for the type $(2,1)$:
$\mathbb{P}\Big{(}c(M_{3,N})=x\Big{)}\sim\frac{6}{\pi^{2}}\frac{1}{x^{2}}$ for
large $N$.

In a recent paper, [4], it was shown that if a m.s. $M_{N}$ is taken uniformly
at random among all meander systems with the length of at most $2N$ and with
the total of $p\geq 4$ leaves in the trees corresponding to the upper and
lower pairings of $M_{N}$, then

$\displaystyle\mathbb{P}\Big{(}c(M_{N})=1\Big{)}\sim\frac{1}{2}\Big{(}\frac{2}{\pi^{2}}\Big{)}^{p-3}\binom{2p-4}{p-2},$

when $N\to\infty$. For $p=4$, this expression agrees with the numerical
evaluation for the rainbow m.s. of type $(3,1)$, mentioned in the previous
paragraph. Unfortunately, the method in [4] does not generalize immediately to
probabilities $\mathbb{P}\Big{(}c(M_{N})=x\Big{)}$ for $x>1$.

##  3\. The largest cycle

Figure 5. The length of the largest cycle normalized by dividing it by
$n^{4/5}$, where $n$ is the half-length of the meander system. The horizontal
axis shows the half-size of the meander $n$, $10\leq n\leq 2000$. The plotted
half-size of the largest cycle is the average over a sample of $4000$
independent uniformly distributed meander systems.

For random rainbow m.s. of size $n$ and type $(2,1)$, and more generally of
type $(s,t)$, the results in Theorem 2.10 and in [4] show that the probability
that a meander system has a single cycle converges to a positive number as
$n\to\infty$. In particular, this implies that the expected size of the
largest cycle is $\Omega(n)$. For random meander systems with uniform
distribution the situation is different.

Figure 5 shows results of numerical simulations for random meander systems of
size $n$. They suggest that the largest cycle in a random m.s. of half-size
$n$ has length around $n^{4/5}$.

This behavior is surprising. Usually, when we consider a random system in
which a concept of a “cycle” is well-defined, we encounter a dichotomy between
the expected number of cycles and the length of the largest cycle. For
example, for a random permutation in the permutation group $S_{n}$, the
expected number of cycles is $\sim\log n$ and the expected length of the
largest cycle is proportional to $n$. For a random partition of the set
$[n]=\\{1,\ldots,n\\}$, the expected number of blocks is $\sim n/\log n$ while
the expected length of the largest block is proportional to $\log n$.

In contrast, for random meander systems, Theorem 2.1 establishes that the
number of cycles grows at a rate proportional to $n$. However, numeric
simulations suggest that the expected largest cycle length also grows at a
polynomial rate, as $n^{\alpha}$, where $\alpha$ is close to $4/5$.

Figure 6. An illustration of the bijection between comb-like meander systems
and non-crossing partitions

This behavior becomes even more surprising if we compare it with that of
another type of random meander systems, comb-like meander systems. These
systems have the lower non-crossing pairing $[(1,2)(3,4),\ldots,(2n-1,2n)]$.
It is not difficult to see that these meander systems can be bijectively
mapped to non-crossing (“NC”) partitions, in such a way that cycles of a
meander system correspond to blocks of the image partition. This bijection is
illustrated in Figure 6.

Due to this bijection, the comb-like meander systems is much easier to
analyze. In particular, from the result about non-crossing partitions, it
follows that the expected number of cycles is $(n+1)/2$, its variance $\sim
n/8$, and that the number of cycles is asymptotically normal for large $n$.

Moreover, by using another bijection, from NC partitions to rooted planar
trees, it is not difficult to prove that the distribution of cycle lengths is
geometric, meaning that for large $n$, the expected number of cycles of half-
length $l$ is $\sim n/2^{l+1}$. One can also calculate the covariances between
numbers of cycles with half-length $l$ and $l^{\prime}$, and prove some limit
distribution theorems for these numbers. (See [17] for corresponding results
for non-crossing partitions.)

For the largest block in a non-crossing partition, we have the following
result.

######  Theorem 3.1.

Let $L_{n}$ denote the size of the largest block in a uniformly distributed
random NC partition of $[n]$. Then, as $n\to\infty$,

$\displaystyle\frac{L_{n}}{\log_{2}n}\stackrel{{\scriptstyle\scriptscriptstyle\mathbb{P}}}{{\longrightarrow}}1,$

where the convergence is in probability.

Note that $\log_{2}n\approx 1.443\log n$, and therefore the largest block in
an NC partition is on average shorter than in a usual set partition where it
is around $e\log n\approx 2.718\log n$.

######  Corollary 3.2.

Let $M_{n}$ be a uniformly distributed random comb-like meander on $2n$
points. Then, the length of the largest cycle in $M_{n}$ is $\sim 2\log_{2}n$
in probability.

Figure 7. The largest cycle length in a random comb-like m.s. normalized by
dividing it by $\log_{2}n$, where $n$ is the half-length of the meander
system. The horizontal axis shows the half-size of the random m.s. $n$,
$10\leq n\leq 2000$. The plotted largest cycle length is the average over a
sample of $4000$ independent comb-like m.s.

This result is illustrated by a plot in Figure 7. Note especially that the
normalization in this plot is different from the normalization in Figure 5.
Here the length of the cycle is divided by $\log_{2}n$, while in Figure 5 it
was divided by $n^{4/5}$.

Figure 8. A bijection between NC partitions and rooted planar trees. This
example shows a partition of $[n]=[10]$ with $b=4$ blocks mapped to a tree on
$n+1=11$ vertices with $b=4$ internal vertices, and $7$ leaves.

###### Proof of Theorem 3.1.

It is easy to map bijectively NC partitions to rooted ordered trees. This can
be done either as in [17] or as indicated in Figure 8. These bijections have
the property that a block of size $k$ corresponds to a vertex of out-degree
$k$.

Then we can use a result about the distribution of the maximum out-degree in a
uniformly distributed random tree.

In particular, Theorem 19.3 for simply generated trees in Janson [14] implies
that

$\displaystyle\frac{L_{n}}{\log n}\to\frac{1}{\log(\rho/\tau)}=\frac{1}{\log
2},$

since for uniformly distributed trees, the weights are $w_{k}=1$, the radius
of the convergence of the weight-generating function $\rho=1$, and the
parameter $\tau=1/2$. ∎

By Example 19.17 in [14], the distribution of the largest degree in a uniform
random tree can be approximated by the distribution of a maximum of i.i.d
geometric random variables with parameter $p=1/2$. This can be translated in
terms of the largest cycle length in a comb-like meander. However, even when
$n\to\infty$, there is no limiting distribution and the behavior of the
maximum depends on how the binary expansion of $n$ looks like. (There is a
significant difference between such cases as $n=2^{k}$ and $n=2^{k}-1$.)
Still, it is possible to formulate the following result.

(We use notation $\lfloor t\rfloor$ for the largest integer $\leq t$, and
$\\{t\\}=t-\lfloor t\rfloor$ for the fractional part of $t$. )

######  Theorem 3.3.

Let $L_{n}$ denote the largest cycle half-length in a uniformly distributed
random comb-like meander system on $2n$ points. Let
$\alpha(n)=2^{\\{\log_{2}n\\}}\in[1,2)$. Then, as $n\to\infty$,

$\displaystyle\mathbb{P}\Big{[}L_{n}-\lfloor\log_{2}n\rfloor\leq
x\Big{]}=\exp\Big{(}-\alpha(n)2^{-(x+1)}\Big{)}\Big{(}1+O\big{(}n^{-1}\log^{2}n\big{)}\Big{)}.$

So, apart from the factor of $\alpha(n)$, the limiting distribution is the
double exponential distribution, that often arises in the study of extreme
value distributions.

This result can be proved by using the relation to geometric random variables
(see Example 19.17 in [14]). We give a direct proof using generating functions
in Appendix.

Now let us return from comb-like meanders to the case, in which both the upper
and lower NC pairings are random. As seen in Figure 5, numerical simulations
suggest that the growth in the largest cycle length is approximately
$n^{\alpha}$ with $\alpha\approx 4/5$. The theorem below shows rigorously that
the growth is at least logarithmic.

######  Theorem 3.4.

Let $L_{n}$ be the largest cycle half-length in a uniformly distributed random
meander system of half-length $n$. Then, for all sufficiently large $n$,

$\displaystyle\mathbb{E}L_{n}\geq 0.8384\log_{2}n.$

For the proof we need a couple of lemmas.

######  Lemma 3.5.

Suppose $k_{n}$ is an integer valued non-negative function of $n$ and $1\ll
k_{n}\ll n$. Then

(5) $\displaystyle\Big{(}\frac{C_{n-k_{n}}}{C_{n}}\Big{)}^{2}$
$\displaystyle=2^{-4k_{n}}\bigg{(}1+3\frac{k_{n}}{n}+O\Big{[}\big{(}\frac{k_{n}}{n}\big{)}^{2}\Big{]}\bigg{)}$
(6)
$\displaystyle\Big{(}\frac{C_{n-2k_{n}}}{C_{n}}\Big{)}^{2}-\Big{(}\frac{C_{n-k_{n}}}{C_{n}}\Big{)}^{4}$
$\displaystyle=2^{-8k_{n}}\bigg{(}3\Big{(}\frac{k_{n}}{n}\Big{)}^{2}+O\Big{[}\big{(}\frac{k_{n}}{n}\big{)}^{3}\Big{]}\bigg{)}$

###### Proof.

We use the asymptotic expansion for the Catalan numbers:

$\displaystyle C_{n}=\frac{4^{n}}{\sqrt{\pi
n^{3}}}\bigg{(}1-\frac{9}{8}n^{-1}+\frac{145}{128}n^{-2}+\frac{1155}{1024}n^{-3}+O\big{(}n^{-4}\big{)}\bigg{)},$

see Figure VI.3 on p. 384 in [8].

Then, we have

$\displaystyle\frac{C_{n-k_{n}}}{C_{n}}=2^{-2k_{n}}\bigg{[}\frac{1}{(1-k_{n}/n)^{3/2}}\frac{1-\frac{9}{8}\frac{1}{1-k_{n}/n}n^{-1}+\frac{145}{128}\frac{1}{(1-k_{n}/n)^{2}}n^{-2}+O(n^{-3})}{1-\frac{9}{8}n^{-1}+\frac{145}{128}n^{-2}+O(n^{-3})}\bigg{]}.$

By expanding this expression in powers of $k_{n}/n$ and $n^{-1}$, we obtain
the asymptotic series for this ratio. Then, formulas (5) and (6) can be
obtained by manipulating this asymptotic series. ∎

Let $I_{x}$ be the indicator of the event that a random meander system
contains a cluster cycle $C_{x}$ with support $(x+1,x+2,\ldots,x+2k)$. (Recall
that by Definition 2.6 cluster cycles have no gaps in their support.) Then we
have

(7)
$\mathbb{E}I_{x}=M_{k}\Big{(}\frac{C_{n-k}}{C_{n}}\Big{)}^{2}\mathbbm{1}_{0\leq
x\leq 2n-2k}.$

where $M_{k}$ is the number of proper meanders of half-length $k$. Similarly,
if $\max(x,y)\leq 2n-2k$, then

(8) $\mathbb{E}(I_{x}I_{y})=\begin{cases}\mathbb{E}I_{x},&\text{ if }x=y,\\\
0,&\text{ if }x\neq y\text{ and }|x-y|<2k,\\\
M_{k}^{2}\Big{(}\frac{C_{n-2k}}{C_{n}}\Big{)}^{2},&\text{ if }|x-y|\geq
2k.\end{cases}$

If $\max(x,y)>2n-2k$, then $\mathbb{E}(I_{x}I_{y})=0$.

Let $\mathcal{C}\ell_{n}(k)$ denote the number of cluster cycles of half-
length $k$ in a random meander system of half-length $n$. We aim to prove the
following lemma.

######  Lemma 3.6.

Let $1\ll k_{n}\ll n$. Then, for $n\to\infty$,

(9)
$\mathbb{E}\mathcal{C}\ell_{n}(k_{n})\sim\mathbb{V}\mathrm{ar}\big{(}\mathcal{C}\ell_{n}(k_{n})\big{)}\sim
2nM_{k_{n}}2^{-4{k_{n}}},$

###### Proof.

By formula (7), we have

$\displaystyle\mathbb{E}\mathcal{C}\ell_{n}(k_{n})$
$\displaystyle=\sum_{x=0}^{2n-2k_{n}}\mathbb{E}I_{x}=\sum_{x=0}^{2n-2k}M_{k_{n}}\Big{(}\frac{C_{n-k_{n}}}{C_{n}}\Big{)}^{2}\sim
2nM_{k_{n}}2^{-4k_{n}},$

where in the last step we used (5). For the variance we have:

$\displaystyle\mathbb{V}\mathrm{ar}\Big{(}\mathcal{C}\ell_{n}(k_{n})\Big{)}=\mathbb{E}\Big{(}\mathcal{C}\ell_{n}(k_{n})^{2}\Big{)}-\Big{(}\mathbb{E}\mathcal{C}\ell_{n}(k_{n})\Big{)}^{2}=\sum_{x,y=0}^{2n-2k_{n}}\Big{[}\mathbb{E}(I_{x}I_{y})-\mathbb{E}I_{x}\mathbb{E}I_{y}\Big{]}.$

The double sum over $x$ and $y$ can be split in 3 cases, according to whether
(i) $x=y$, or (ii) $x\neq y$ and $|x-y|<2k_{n}$, or (iii) $|x-y|\geq 2k_{n}$.
In the first case, the number of terms is $\sim 2n$, in case (ii) it is $\sim
4k_{n}\times 2n$ and in the last case it is $\sim 4n^{2}$. By using formulas
in (5), (6), (7), (8), we write:

$\displaystyle\mathbb{V}\mathrm{ar}\Big{(}\mathcal{C}\ell_{n}(k_{n})\Big{)}$
$\displaystyle\sim
2n\Big{[}M_{k_{n}}2^{-4k_{n}}-\big{(}M_{k_{n}}2^{-4k_{n}}\big{)}^{2}\Big{]}-8k_{n}n\Big{[}\big{(}M_{k_{n}}2^{-4k_{n}}\big{)}^{2}\Big{]}$
$\displaystyle+4n^{2}\Big{[}3\big{(}\frac{k_{n}}{n}\big{)}^{2}\big{(}M_{k_{n}}2^{-4k_{n}}\big{)}^{2}\Big{]}$
$\displaystyle\sim 2nM_{k_{n}}2^{-4k_{n}},$

where we used the rigorous bound that $M_{k}\leq 13^{k}$ for sufficiently
large $k$, which implies that $k_{n}M_{k_{n}}2^{-4k_{n}}\ll 1$. In addition,
for the last term we used that $k_{n}\ll n$. ∎

###### Proof of Theorem 3.4.

In order to prove that $\mathbb{E}L_{n}\geq c\log_{2}n$, it is enough to show
that for all sufficiently large $n$, with probability $\geq 1/2$, there is a
cycle of length $\geq 2c\log_{2}n$. We will show a stronger statement that
with probability $\geq 1/2$ (and all sufficiently large $n$), there is a
cluster cycle of length $\geq 2c\log_{2}n$.

We use a well-known inequality (see Theorem 4.3.1 in [2]) that for a non-
negative integer-valued random variable $X$, it is true that

(10) $\mathbb{P}(X=0)\leq\frac{\mathbb{V}\mathrm{ar}(X)}{(\mathbb{E}X)^{2}}.$

We apply this inequality to $X=\mathcal{C}\ell_{n}(k_{n})$, with
$k_{n}=c\log_{2}n$. Then, by Lemma 3.6,

$\displaystyle\frac{\mathbb{V}\mathrm{ar}(X)}{(\mathbb{E}X)^{2}}=\Big{[}2nM_{k_{n}}2^{-4k_{n}}\Big{]}^{-1}=\frac{2^{4k_{n}}}{2nM_{k_{n}}}\leq
n^{4c-1-2.8073c}=n^{1.1927c-1},$

where we used a conservative estimate $M_{k_{n}}\geq
7^{k_{n}}=2^{2.8073k_{n}}$. Hence, for $c\leq 0.8384$, this ratio $\to 0$ as
$n\to\infty$. This implies that for $k_{n}\leq 0.8384\log_{2}n$, the
probability $\mathbb{P}\big{[}\mathcal{C}\ell_{n}(k_{n})\geq 1\big{]}\to 1$,
which completes the proof of the theorem. ∎

##  4\. Remarks.

1\. The behavior of the largest cycle length appears to be universal with
respect to a large set of models. Plots in Figure 9 illustrate that the
expected largest cycle length is proportional to $n^{4/5}$ not only for random
m.s. with the uniform distribution, but also for other random m.s., such as
simply-generated m.s. and semimeanders, in which the upper pairing is chosen
uniformly at random and the lower pairing is fixed to be the rainbow $(1,2n)$,
$(2,2n-1)$, …, $(n,n+1)$. Similar results are also observed for systems not
reported in Figure 9, in particular, for m.s. with weight sequence
$w_{0}=w_{k}=1$, $w_{i}=0$ for $i\neq k$, with $k=2,3,4$; and for m.s. for
which the weight sequence declines polynomially, $w_{k}=(k+1)^{-\beta}$, for
$\beta=2$.

Figure 9. Plots of the largest cycle length normalized by $n^{4/5}$, where $n$
is the half-size of the m.s. In this plot $10\leq n\leq 2000$ and each point
is the average of the largest cycle length over a sample of $4000$ independent
m.s. A random “semimeander” systems have its upper pairing chosen uniformly at
random while its lower pairing is the “rainbow”:
$[(1,2n),(2,2n-1),\ldots,(n,n+1)]$. The weighted meander system in this
example has weights $(1,1,1,0,\ldots)$. [It is more time consuming to generate
these m.s. so to save time they were generated for half-sizes
$\\{10,20,\ldots,2000\\}$ only.] Figure 10. The estimate of the standard
deviation of the largest cycle normalized by $n^{4/5}$, where $n$ is the half-
size of the meander system. In the plot $10\leq n\leq 2000$. The standard
deviation shown in the graph is the average over a sample of $4000$
independent random meander systems.

2\. The size of the largest cycle does not concentrate with the growth in $n$,
in the sense that the standard deviation of this random variable seems to grow
at the same rate ($n^{4/5}$) as the expectation. See an illustration in Figure
10.

Figure 11. The histogram of the largest cycle length normalized by $n^{4/5}$.
The meander system half-length $n=2000$ and the size of the sample used for
estimation is $10^{6}$.

3\. The distribution of the largest cycle is shown in Figure 11. Its skewness
$\approx 0.59$ and it appears as one of the usual extreme value distributions.

Figure 12. The histogram of the largest cycle spacings [normalized by $n$].
Each m.s. has half-length $n=2000$ and the sample size of m.s. used to build
the sample of largest cycle spacings is $5\times 10^{4}$. For comparison, a
histogram of spacings for independent random points is shown. It shows spacing
distribution for a matched sample of points which are equal in number to the
largest cycle length but are chosen uniformly at random on interval $[2n]$.

4\. The spacings in the support of the largest cycle also exhibit an
interesting structure. Spacings of size 1 (which occur when x and x + 1 are
both in the support of the cycle) take around $80\%$ of all spacings. Spacings
of size 3 are about $10\%$ of all spacings. (Spacings of size 2 are
impossible.) These percentages seem to be insensitive to the size of the
meander system. The distribution of spacings is shown in Figure 12. (Note the
logarithmic scale of $y$-axis.) The distribution of spacings in the largest
cycle differs significantly from the distribution of spacings in the case of
uniformly distributed points. In particular, there are significantly more
large spacings than one would expect in a sample of independent random points.

3\. The connected components of meander systems appears in other areas of
mathematics. For example, in [5], the number of connected components is used
to evaluate the index of seaweed Lie algebras. In [9], this quantity arises in
the connection with the trace of Temperley-Lieb matrices.

4\. The common meaning of the word ”meander” is a winding curve followed by a
river. So, it is perhaps relevant to mention that some scaling laws have been
experimentally discovered for the behavior of river flows. For example, in
1957, Hack studied the drainage system of rivers in the Shenandoah valley and
the adjacent mountains of Virginia, and formulated the law, which is now
called Hack’s law. Namely, there is a power law relation $l\sim a^{\beta}$,
with $\beta$ close to $0.6$, between the length $l$ of a longest stream in a
connected system of streams and the area of the basin that collects the
precipitation contributing to the stream through its tributaries. See a review
and some scaling arguments in [21] and a recent mathematical model in [22].

Hack’s law, however, reflects the behavior of random trees rather than that of
random meander systems. For random trees, related results are well-known. For
example, it is known that the height of a simply-generated random tree on $n$
vertices is proportional to $n^{1/2}$ (under mild conditions on the weight
sequence). (See, for example, [8] or [14].) In contrast, in the case of
meander systems, it is not clear which scaling mechanisms contribute to the
exponent $4/5$ observed in numerical experiments.

##  Appendix A Appendix

###### Proof of Proposition 2.3.

As in the proof of Theorem 2.1, we can use indicator functions to derive the
formula

(11) $\mathbb{E}c_{st}(M)=2\sum_{x,y\colon 1\leq x+1<y\leq
2n-2}p_{1}(x,y)p_{2}(x,y),$

where $p_{1}(x,y)$ is the probability that $(x,x+1)$ and $(y,y+1)$ are pairs
in a random pairing, and $p_{2}(x,y)$ is the probability that $(x,y+1)$ and
$(x+1,y)$ are pairs. The coefficient $2$ is because we count both upper and
lower staples.

For $p_{1}(x,y)$ we have

(12) $p_{1}(x,y)=\frac{C_{n-2}}{C_{n}}=\frac{1}{16}+O(n^{-1}),$

where $C_{i}$ are Catalan numbers and the constant in the O-term is uniform
over $x$ and $y$.

For $p_{2}(x,y)$, we look at staples of different length $k$ separately. (Here
the length of a staple with support $(x,x+1,y,y+1)$ is defined as
$k=(y-x)/2$.) For a staple of length $k$, we have

(13) $p_{2}(x,y)=\frac{C_{n-k-1}C_{k-1}}{C_{n}},$

which depends only on $k$ and $n$. Fix an $\varepsilon\in(5/6,1)$ and consider
the sums of probabilities $p_{2}(x,y)$ over all $x$ and $y$ that satisfy
additional conditions on length $k$.

$\displaystyle S_{1}$ $\displaystyle=\sum p_{2}(x,y),\text{ where $k\leq
n^{\varepsilon}$},$ $\displaystyle S_{2}$ $\displaystyle=\sum
p_{2}(x,y),\text{ where $n^{\varepsilon}<k\leq n-n^{\varepsilon}$},$
$\displaystyle S_{3}$ $\displaystyle=\sum p_{2}(x,y),\text{ where
$n-n^{\varepsilon}<k\leq n$}.$

For $S_{2}$ we use the asymptotic approximation to Catalan numbers, and make
the following estimate for each term in the sum,

$\displaystyle p_{2}(x,y)$
$\displaystyle\sim\frac{4^{n-k-1}}{\sqrt{\pi}(n-k-1)^{3/2}}\frac{4^{k-1}}{\sqrt{\pi}(k-1)^{3/2}}/\frac{4^{n}}{\sqrt{\pi}n^{3/2}}$
$\displaystyle=O\Big{(}n^{3/2(1-2\varepsilon)}\Big{)}=o(n^{-1}).$

Since the number of terms in the sum $S_{2}$ is no greater than $O(n^{2})$, we
conclude that $S_{2}=o(n)$.

For $S_{3}$, we can write the sum as follows,

$\displaystyle S_{3}$
$\displaystyle=\sum_{k=n-n^{\varepsilon}}^{n-1}\sum_{x=1}^{2n-2k-1}p_{2}(x,x+2k)$
$\displaystyle=O\Big{(}n^{\varepsilon}\sum_{k=n-n^{\varepsilon}}^{n-1}C_{n-k-1}\frac{C_{k-1}}{C_{n}}\Big{)},$

where we used formula (13) and the observations that $p_{2}(x,x+2k)$ does not
depend on $x$ and that the number of terms in the inner sum is $\leq
2n^{\varepsilon}$. We can continue by changing the summation index,

$\displaystyle S_{3}$
$\displaystyle=O\Big{(}n^{\varepsilon}\sum_{l=0}^{n^{\varepsilon}}C_{l}\frac{C_{n-l-2}}{C_{n}}\Big{)}$
$\displaystyle=O\Big{(}n^{\varepsilon}\sum_{l=0}^{\infty}C_{l}4^{-l}\Big{)}=O(n^{\varepsilon}),$

where the last line follows because the sum $\sum_{l=0}^{\infty}C_{l}4^{-l}$
is convergent.

Finally, we address the sum $S_{1}$,

$\displaystyle S_{1}$
$\displaystyle=\sum_{k=1}^{n^{\varepsilon}}\sum_{x=0}^{2n-2k}p(x,x+2k)$
$\displaystyle\sim
2n\sum_{k=1}^{n^{\varepsilon}}C_{k-1}\frac{C_{n-k-1}}{C_{n}}\sim
2n\sum_{k=1}^{n^{\varepsilon}}C_{k-1}4^{-(k+1)}$
$\displaystyle\sim\frac{n}{8}\sum_{l=0}^{\infty}C_{l}4^{-l}.$

The last sum can be calculated by noting that
$C_{l}=\frac{1}{2\pi}\int_{0}^{4}x^{l-\frac{1}{2}}\sqrt{4-x}\,dx$, which leads
to $\sum_{l=0}^{\infty}C_{l}4^{-l}=2$ and so $S_{1}\sim n/4$.

From the estimates on $S_{1}$, $S_{2}$, $S_{3}$, and formulas (11) and (12),
it follows that

$\displaystyle\mathbb{E}c_{st}(M)\sim
2\times\frac{1}{16}\frac{n}{4}=\frac{n}{32}.$

∎

###### Proof of Proposition 2.4.

We aim at estimating the sum

$\displaystyle\mathbb{E}c_{O}(M)=\sum_{x<y}p(x,y)^{2},$

where $p(x,y)$ is the probability that $(x,y)$ is a pair in a random pairing.
If $y-x$ is even this probability is zero, otherwise,

$\displaystyle p(x,x+2k+1)=\Big{[}\frac{C_{k}C_{n-k-1}}{C_{n}}\Big{]}^{2}.$

So we have

$\displaystyle\mathbb{E}c_{O}(M)$
$\displaystyle=\sum_{x=1}^{2n-1}\sum_{k=0}^{\lfloor(2n-x-1)/2\rfloor}\Big{[}\frac{C_{k}C_{n-k-1}}{C_{n}}\Big{]}^{2}$
$\displaystyle=\sum_{k=0}^{n-1}\sum_{x=0}^{2n-2k-1}\Big{[}\frac{C_{k}C_{n-k-1}}{C_{n}}\Big{]}^{2}$
$\displaystyle=\sum_{k=0}^{n-1}(2n-2k)\Big{[}\frac{C_{k}C_{n-k-1}}{C_{n}}\Big{]}^{2}$

Very similar to the previous proof, by using the asymptotic approximations for
the Catalan numbers, we can show that the main contribution is given by the
rings with radius $k<n^{\varepsilon}$, where $\varepsilon<1$ is appropriately
large. Then, we can apply asymptotic approximation to $C_{n-k-1}$ and write:

$\displaystyle\mathbb{E}c_{O}(M)$
$\displaystyle\sim\sum_{k=0}^{n^{\varepsilon}}(2n-2k)C_{k}^{2}4^{-2k-2}$
$\displaystyle\sim\frac{n}{8}\sum_{k=0}^{\infty}\big{[}C_{k}4^{-k}\big{]}^{2}=\Big{(}\frac{2}{\pi}-\frac{1}{2}\Big{)}n,$

where the proof of the last equality can be found in [18], see their
Proposition in Section 5.10. ∎

###### Proof of Theorem 3.3.

Because of the bijection between comb-like meanders and non-crossing
partitions, it is enough to prove the corresponding result about the largest
block in a non-crossing partition of $[n]$. First, we find the generating
function for NC partitions with blocks whose length is $\leq k$. The symbolic
formula for the class of these partitions is

$\displaystyle C^{(k)}=\varepsilon+SET_{1}(Z)\times
SEQ_{1}(C^{(k)})+\ldots+SET_{k}(Z)\times SEQ_{k}(C^{(k)}).$

Here $\varepsilon$ denotes the empty partition, $Z$ is an atom (that is, an
element of a partition), and $\mathrm{SET}_{k}(Z)\times\mathrm{SEQ}_{k}(C)$
corresponds to a block of size $k$ containing a marked element (“root”),
together with a sequence of NC partitions which are nested between the
elements of this block. See Figure 13 for illustration.

Figure 13. Construction of a non-crossing partition with a block of size 6

This leads to the following equation for the generating function:

$\displaystyle C^{(k)}(z)$
$\displaystyle=1+zC^{(k)}(z)+\ldots+\Big{[}zC^{(k)}(z)\Big{]}^{k}$
$\displaystyle=\frac{1-\Big{[}zC^{(k)}(z)\Big{]}^{k+1}}{1-zC^{(k)}(z)},$

or

$\displaystyle\Big{[}zC^{(k)}(z)\Big{]}^{k+1}-zC^{(k)}(z)^{2}+C^{(k)}(z)-1=0.$

The coefficient before $z^{n}$ in the power expansion of $C^{(k)}(z)$, denoted
$[z^{n}]C^{(k)}(z)$, equals the number of NC partitions of $[n]$, in which all
blocks have lengths $\leq k$. The total number of NC partitions of $[n]$ is
the Catalan number $C_{n}$. So, the probability that a random NC partition has
no block larger than $k$ is $[z^{n}]C^{(k)}(z)/C_{n}$, and we are left with
the task of evaluating the asymptotic of $[z^{n}]C^{(k)}(z)$.

Let us use the notation $y(z)=zC^{(k)}(z).$ Then the equation for $y(z)$ is
$y=G(z,y)$, where $G(z,y)=z+y^{2}-zy^{k+1}$.

Now, let us summarize some tools from the book by Flajolet and Sedgewick,
which allows us to write the asymptotic expressions for the coefficients of
$y(z)$.

We say that that a function of complex argument $y(z)$ is an analytic
generating function (analytic GF) if it is analytic at zero and if its
expansion,

(14) $y(z)=\sum_{n=0}^{\infty}y_{n}z^{n},$

have real non-negative coefficients $y_{0}=0$, $y_{n}\geq 0$.

######  Definition A.1.

An analytic GF $y(z)$ is said to have a stable dominant singularity333Flajolet
and Sedgewick say that $y(z)$ belongs to the smooth implicit-function schema.
at $z=r>0$, if there exists a bivariate function $G(z,w)$ such that

(15) $y(z)=G(z,y(z)),$

and $G(z,y(z))$ satisfies the following conditions:

  1. (A)

$G(z,w)=\sum_{m,n\geq 0}g_{m,n}z^{m}w^{n}$ is analytic in a domain $|z|<R$ and
$|w|<S$ for some $R,S>0$.

  2. (B)

Coefficients $g_{m,n}$ are non-negative reals, $g_{0,0}=0$, $g_{0,1}\neq 1$
and $g_{m,n}>0$ for some $m$ and for some $n\geq 2$.

  3. (C)

The singularity $r<R$ and there exists $s$ such that $0<s<S$ and that

(16) $\displaystyle G(r,s)$ $\displaystyle=s,$ (17) $\displaystyle G_{w}(r,s)$
$\displaystyle=1,$

The function $G(z,w)$ is called the characteristic function for $y(z)$ and the
system (16), (17) – the characteristic system.

The condition in (C) is aimed to ensure that $r$ is a singularity of $y(z)$
with $y(r)=s$. The conditions in (A) and (B), especially the non-negativity of
the coefficients, ensure that this singularity is a quadratic singularity with
the smallest absolute value among all singularities of $y(z)$ (which is why we
call it “the stable dominant singularity”). The following result has a long
history, - a weaker version can be found already in the classic book by Hille
[13], – Theorem 9.4.6 on p. 274 of volume I. In the form similar to the
following, it was proved by Meir and Moon in [20]. We give the formulation
from Flajolet-Sedgewick book [8], cf. Theorem VII.3 on p. 468.

######  Theorem A.2 (Meir - Moon).

Let $y(z)$ be an analytic GF that has a stable singularity at $r$ with the
characteristic function $G(z,w)$. Then the series in (14) converges at $z=r$
and

(18) $y(z)=s-\gamma\sqrt{1-z/r}+O(1-z/r),$

in a neighborhood of $z=r$, where $s=y(r)$ and

(19) $\gamma=\sqrt{\frac{2rG_{z}(r,s)}{G_{ww}(r,s)}}.$

We apply this result to $y(z)=zC^{(k)}(z)$. The singularity point
$\big{(}z_{0},y_{0}=y(z_{0})\big{)}$ solves the characteristic system:

$\displaystyle y$ $\displaystyle=z+y^{2}-zy^{k+1},$ $\displaystyle 1$
$\displaystyle=2y-(k+1)zy^{k}.$

The first equation of the system gives

$\displaystyle z=\frac{y(1-y)}{1-y^{k+1}},$

and after plugging this expression into the second equation we obtain:

$\displaystyle y=\frac{1}{2}\Big{[}1+ky^{k+1}-(k-1)y^{k+2}\Big{]}.$

The solution for this equation is

$\displaystyle
y_{0}=\frac{1}{2}+\frac{k+1}{2^{k+3}}+O\Big{(}\frac{k}{2^{2k}}\Big{)}.$

And then,

$\displaystyle
z_{0}=\frac{y_{0}(1-y_{0})}{1-y_{0}^{k+1}}=\frac{1}{4}\Big{(}1+\frac{1}{2^{k+1}}\Big{)}+O\Big{(}\frac{k^{2}}{2^{2k}}\Big{)},$

In order to apply Theorem A.2 we also compute

$\displaystyle\gamma=\sqrt{\frac{2z_{0}P_{z}(z_{0},y_{0})}{P_{yy}(z_{0},y_{0}}}=\frac{1}{2}+O\Big{(}\frac{k^{2}}{2^{k}}\Big{)}$

and conclude that

$\displaystyle y(z)=y_{0}-\gamma\sqrt{1-z/z_{0}}+O(1-z/z_{0}).$

Using the power expansion for the square root and Theorem VI.4 in [8] to
justify that the error term in the formula for $y(z)$ can be neglected, we
find that

$\displaystyle[z^{n}]y(z)=\gamma\Big{[}\frac{1}{2\sqrt{\pi}n^{3/2}}+O(n^{-5/2})\Big{]}\Big{(}\frac{1}{z_{0}}\Big{)}^{n}.$

For Catalan numbers (total number of NC partitions of $[n]$) we have the
asymptotic approximation

$\displaystyle C_{n}=4^{n}\Big{[}\frac{1}{\sqrt{\pi
n^{3/2}}}+O\Big{(}\frac{1}{n^{5/2}}\Big{)}\Big{]}.$

Hence we have the following estimate,

$\displaystyle\mathbb{P}\\{L_{n}\leq k\\}$
$\displaystyle=\frac{[z^{n}]C^{(k)}(z)}{C_{n}}=\frac{[z^{n+1}]y(z)}{C_{n}}$
$\displaystyle=4^{-(n+1)}z_{0}^{-(n+1)}\Big{(}1+O(n^{-1})+O(k^{2}/2^{k})\Big{)}.$
$\displaystyle=\Big{[}\Big{(}1+\frac{1}{2^{k+1}}\Big{)}+O\Big{(}\frac{k^{2}}{2^{2k}}\Big{)}\Big{]}^{-(n+1)}\Big{(}1+O(n^{-1})+O(k^{2}/2^{k})\Big{)}.$

If we use $k:=\lfloor\log_{2}n\rfloor+x$ and recall that we defined
$\alpha(n)=2^{\\{\log_{2}n\\}}$, then we find that
$2^{k+1}=2^{\lfloor\log_{2}n\rfloor+x+1}=2^{x+1}\frac{n}{\alpha(n)}$. Plugging
this into the previous expression, we find that

$\displaystyle\mathbb{P}\\{L_{n}\leq k\\}$
$\displaystyle=\Big{[}1+\alpha(n)2^{-(x+1)}\frac{1}{n}+O\Big{(}\frac{\log^{2}n}{n^{2}}\Big{)}\Big{]}^{-(n+1)}\Big{(}1+O\big{(}\frac{\log^{2}n}{n}\big{)}\Big{)}$
$\displaystyle=\exp\Big{(}-\alpha(n)2^{-(x+1)}\Big{)}\Big{(}1+O\big{(}n^{-1}\log^{2}n\big{)}\Big{)}.$

∎

## References

  * [1] M. H. Albert and M. S. Paterson.  Bounds for the growth rate of meander numbers.  Journal of Combinatorial Theory, Series A, 112:250–262, 2005.
  * [2] Noga Alon and Joel H. Spencer.  The Probabilistic Method.  John Wiley and Sons, Inc., second edition, 2000.
  * [3] V. I. Arnold.  The branched covering $CP^{2}\to S^{4}$, hyperbolicity and projective topology.  Sibirsk. Mat. Zh., 29(5):36 –47, 1988.
  * [4] Vincent Delecroix, Elise Goujard, Peter Zograf, and Anton Zorich.  Enumeration of meanders and Masur-Veech volumes.  arXiv: 1705.05190, March 2019.
  * [5] Vladimir Dergachev and Alexandre Kirillov.  Index of Lie algebras of seaweed type.  Journal of Lie Theory, 10(331-343), 2000.
  * [6] Persi Diaconis and Paul Erdös.  On the distribution of the greatest common divisor.  Institute of Mathematical Statistics Lecture Notes, 45:56–61, 2004\.
  * [7] Bernold Fiedler and Pablo Castaneda.  Rainbow meanders and Cartesian billiards.  Sao Paulo Journal of Mathematical Sciences, 6(2):247 – 275, 2012\.
  * [8] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2009.
  * [9] P. Di Francesco, O. Golinelli, and E. Guitter.  Meanders and the Temperley-Lieb algebra.  Communications in Mathematical Physics, 186(1):1 – 59, 1997.
  * [10] P. Di Francesco, O. Golinelli, and E. Guitter.  Meanders: exact asymptotics.  Nuclear Physics B, 570:699–712, 2000.
  * [11] Reinhard O. W. Franz and Berton A. Earnshaw.  A constructive enumeration of meanders.  Annals of Combinatorics, 6:7 – 17, 2002.
  * [12] Motohisa Fukuda and Ion Nechita.  Enumerating meandric systems with large number of loops.  Annales de l’Institut Henri Poincare D Combinatorics, Physics and their Interactions, 6(4):607–640, 2019.
  * [13] Einar Hille.  Analytic Function Theory, volume 1.  Ginn and Company, 1962.
  * [14] Svante Janson.  Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation.  Probability Surveys, 9:103–252, 2012.
  * [15] Iwan Jensen.  A transfer matrix approach to enumeration of plane meanders.  Journal of Physics A: Mathematical and General, 33:5953 – 5963, 2000.
  * [16] Iwan Jensen and Anthony J. Guttmann.  Critical exponents of plane meanders.  Journal of Physics A: Mathematical and General, 33:L187–L192, 2000\.
  * [17] Igor Kortchemski and Cyril Marzouk.  Simply-generated non-crossing partition.  Combinatorics, Probability and Computing, 26(4):560–592, 2017.
  * [18] S. K. Lando and A. K. Zvonkin.  Meanders.  Selecta Mathematica Sovietica, 11(2):117 – 144, 1992.
  * [19] S. K. Lando and A. K. Zvonkin.  Plane and projective meanders.  Tneortical Computer Science, 117:227–241, 1993.
  * [20] A. Meir and J. W. Moon.  On an asymptotic method in enumeration.  Journal of Combinatorial Theory, Series A, 51:77– 89, 1989.
  * [21] Riccardo Rigon, Ignacio Rodriguez-Iturbe, Amos Maritan, Achille Giacometti, David G. Tarboton, and Andrea Rinaldo.  On Hack’s law.  Water Resources Research, 32(11):3367 – 3374, November 1996.
  * [22] Rahul Roy, Kumarjit Saha, and Anish Sarkar.  Hack’s law in a drainage network model: A brownian web approach.  Annals of Applied Probability, 26(3):1807 – 1836, 2016.