# Power-law bounds for increasing subsequences in Brownian separable permutons
and homogeneous sets in Brownian cographons

Jacopo Borga Stanford University William Da Silva University of Vienna Ewain
Gwynne University of Chicago

###### Abstract

The Brownian separable permutons are a one-parameter family – indexed by
$p\in(0,1)$ – of universal limits of random constrained permutations. We show
that for each $p\in(0,1)$, there are explicit constants
$1/2<\alpha_{*}(p)\leq\beta^{*}(p)<1$ such that the length of the longest
increasing subsequence in a random permutation of size $n$ sampled from the
Brownian separable permuton is between $n^{\alpha_{*}(p)-o(1)}$ and
$n^{\beta^{*}(p)+o(1)}$ with probability tending to 1 as $n\to\infty$. In the
symmetric case $p=1/2$, we have $\alpha_{*}(p)\approx 0.812$ and
$\beta^{*}(p)\approx 0.975$. We present numerical simulations which suggest
that the lower bound $\alpha_{*}(p)$ is close to optimal in the whole range
$p\in(0,1)$.

Our results work equally well for the closely related Brownian cographons. In
this setting, we show that for each $p\in(0,1)$, the size of the largest
clique (resp. independent set) in a random graph on $n$ vertices sampled from
the Brownian cographon is between $n^{\alpha_{*}(p)-o(1)}$ and
$n^{\beta^{*}(p)+o(1)}$ (resp. $n^{\alpha_{*}(1-p)-o(1)}$ and
$n^{\beta^{*}(1-p)+o(1)}$) with probability tending to 1 as $n\to\infty$.

Our proofs are based on the analysis of a fragmentation process embedded in a
Brownian excursion introduced by Bertoin (2002). We expect that our techniques
can be extended to prove similar bounds for uniform separable permutations and
uniform cographs.

Figure 1:  Top: The diagram of three large permutations (in black) sampled
from the Brownian separable permuton with parameter $p=0.2,0.5,0.9$ (from left
to right). In red we highlighted one longest increasing subsequence. Bottom:
The adjacency matrix of three large graphs (ones are plotted in black) sampled
from the Brownian cographon with parameter $p=0.2,0.5,0.9$ (from left to
right). In red we highlighted one largest homogeneous set. In the first two
samples it is an independent set, while in the third case it is a clique.

###### Contents

  1. 1 Introduction
    1. 1.1 Brownian separable permuton results
    2. 1.2 Brownian cographon results
    3. 1.3 Conjectures and potential extensions
    4. 1.4 Proof techniques and ordered subsets of the signed Brownian excursion
  2. 2 Preliminary results
    1. 2.1 Brownian excursions
    2. 2.2 Sampling permutations and graphs from the Brownian separable permutons and the Brownian cographs
    3. 2.3 Fragmentation processes and the tagged fragment in a Brownian excursion
  3. 3 Estimates for the lower bound
    1. 3.1 Embedding the selection rule in the tagged cell
    2. 3.2 First moment estimate
    3. 3.3 Two-point function estimate
  4. 4 Lower bound for sequences sampled from the Brownian separable permutons
  5. 5 Estimates for the upper bound
    1. 5.1 The two main estimates
    2. 5.2 Proofs of the two main estimates
  6. 6 Upper bound for sequences sampled from the Brownian separable permutons
  7. A Numerical simulations

Acknowledgments. We thank four anonymous referees for helpful comments on an
earlier version of this article. We thank Jean Bertoin for some helpful
discussion on Lévy and fragmentation processes and Valentin Féray for some
helpful discussion on the problems investigated in this paper. We are also
grateful to Arka Adhikari, Élie Aïdékon, Omer Angel, Matija Bucic, Amir Dembo
and Lucas Teyssier for interesting discussions. E.G. was partially supported
by a Clay research fellowship. W.D.S. acknowledges the support of the two
Austrian Science Fund (FWF) grants on “Scaling limits in random conformal
geometry” (DOI: 10.55776/P33083) and “Emergent branching structures in random
geometry” (DOI: 10.55776/ESP534).

##  1 Introduction

The length of the longest increasing subsequence in a random permutation and
the size of the largest homogeneous set (i.e. a clique or an independent set)
in a random graph are two of the classical problems at the interface of
combinatorics and probability theory, with connections to several other areas
of mathematics.

In this paper, we investigate these classical problems in the setting of
universal Brownian-type permutations and graphs, i.e. for the _Brownian
separable permutons_ [BBF+18, BBF+20] and the _Brownian cographons_ [BBF+22a,
Stu21]. These objects are the universal limits of various random permutations
and graph families.

In the following sections, we first discuss our results on permutations
(Section 1.1) and then on graphs (Section 1.2). In both sections, we briefly
review the literature around the questions addressed in this paper. We then
present two conjectures and some potential extensions of our work (Section
1.3). Here, we also discuss a few open problems and additional motivation for
our work coming from random geometry and the study of planar maps. Finally, we
give an overview of the techniques used to establish our main results,
explaining how they can potentially be used to answer similar questions in the
continuum setting (Section 1.4).

###  1.1 Brownian separable permuton results

####  1.1.1 Permutons and the Brownian separable permutons

A Borel probability measure $\mu$ on the unit square $[0,1]^{2}$ is a permuton
if both of its marginals are uniform, that is,
$\mu([a,b]\times[0,1])=\mu([0,1]\times[a,b])=b-a$ for all $0\leq a<b\leq 1$.
To a permutation $\sigma$, we can associate a permuton $\mu_{\sigma}$ which is
equal to $n$ times the Lebesgue measure on the union of the squares
$\\{[\frac{i-1}{n},\frac{i}{n}]\times[\frac{\sigma(i)-1}{n},\frac{\sigma(i)}{n}]:i\in[n]\\}.$
For a sequence of permutations $\\{\sigma_{n}\\}_{n\in\mathbbm{N}}$, we say
that $\sigma_{n}$ converges in the permuton sense to a limiting permuton $\mu$
if the permutons $\mu_{\sigma_{n}}$ converge weakly to $\mu$. The set of
permutons equipped with the topology of weak convergence of measures is a
compact metric space. The theory of permutons has seen many recent
developments at the interface between discrete mathematics, probability
theory, and statistics, see for instance, [Grü22] for a survey.

We now recall the construction, due to Maazoun [Maa20], of the Brownian
separable permuton with parameter $p\in[0,1]$ in terms of a Brownian excursion
with i.i.d. coin flips. Under $\mathbb{P}$, we call signed excursion a pair
$(\mathfrak{e},\mathfrak{s},p)$ consisting of a Brownian (normalized)
excursion $\mathfrak{e}$, together with an independent sequence $\mathfrak{s}$
of i.i.d. $p$-coins $\\{\oplus,\ominus\\}$, i.e.
$\mathbb{P}(\oplus)=p=1-\mathbb{P}(\ominus)$. One should think of the sequence
$\mathfrak{s}$ as being indexed by the local minima of $\mathfrak{e}$.111For
the technicalities involved in indexing an i.i.d. sequence by this random
countable set, see [Maa20, Section 2.2].

We define the following random relation
$\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ on $[0,1]$: conditional on
$\mathfrak{e}$, if $x,y\in[0,1]$, with $x<y$, and $\min_{[x,y]}\mathfrak{e}$
is reached at a unique point which is a strict local minimum
$\ell_{x,y}\in(x,y)$ then

$\begin{cases}x\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}y,&\quad\text{if}\quad\mathfrak{s}(\ell_{x,y})=\oplus,\\\
y\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}x,&\quad\text{if}\quad\mathfrak{s}(\ell_{x,y})=\ominus.\\\
\end{cases}$ (1.1)

Standard properties of the Brownian excursion ensure the existence of a random
subset $\mathcal{R}_{\mathfrak{e}}\subset[0,1]$ such that the complement has
a.s. Hausdorff dimension $1/2$ – i.e.
$\mathbb{P}(\dim([0,1]\setminus\mathcal{R}_{\mathfrak{e}})=1/2)=1$, where
$\dim(\cdot)$ denotes the Hausdorff dimension of a set – and for every
$x,y\in\mathcal{R}_{\mathfrak{e}}$ with $x<y$, $\min_{[x,y]}\mathfrak{e}$ is
reached at a unique point which is a strict local minimum. In particular, the
restriction of $\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ to
$\mathcal{R}_{\mathfrak{e}}$ is a total order (see 2.1 below). Setting

$\psi_{\mathfrak{e},\mathfrak{s},p}(t)\coloneqq\operatorname{Leb}\mathopen{}\mathclose{{}\left(\big{\\{}x\in[0,1]|x\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}t\big{\\}}}\right),\quad\forall
t\in[0,1],$ (1.2)

then the (biased) Brownian separable permuton is the push-forward of the
Lebesgue measure on $[0,1]$ via the mapping
$(\mathbb{I},\psi_{\mathfrak{e},\mathfrak{s},p})$, where $\mathbb{I}$ denotes
the identity. That is,

$\bm{\mu}_{p}(\cdot)\coloneqq(\mathbb{I},\psi_{\mathfrak{e},\mathfrak{s},p})_{*}\operatorname{Leb}(\cdot)=\operatorname{Leb}\mathopen{}\mathclose{{}\left(\\{t\in[0,1]|(t,\psi_{\mathfrak{e},\mathfrak{s},p}(t))\in\cdot\,\\}}\right).$
(1.3)

Heuristically, $\psi_{\mathfrak{e},\mathfrak{s},p}$ is the _continuum
permutation_ of the elements in the interval $[0,1]$ induced by the order
$\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ and $\bm{\mu}_{p}$ is the
diagram of $\psi_{\mathfrak{e},\mathfrak{s},p}$. We stress that $\bm{\mu}_{p}$
is a _random_ permuton.

The Brownian separable permutons were first introduced while studying random
separable permutations [BBF+18], i.e. permutations avoiding the patterns
$2413$ and $3142$ (see the Wikipedia page on separable permutations for
further details and many properties of these permutations). The authors of the
latter paper showed that uniform random separable permutations converge in
distribution to $\bm{\mu}_{1/2}$ when the size of the permutations tends to
infinity. Later, it has been proved that this convergence result is in some
sense universal: uniform permutations in proper substitution-closed classes
[BBF+20, BBFS20] or classes having a finite combinatorial specification for
the substitution decomposition [BBF+22b] converge in distribution (under some
technical assumptions) to $\bm{\mu}_{p}$, where the parameter $p$ depends on
the chosen class. These papers initiated a line of research around random
Brownian fractal-type permutons, see for instance [Bor23, BGS22].

####  1.1.2 The length of the longest increasing subsequence

There is a vast literature devoted to the asymptotic behavior of the length of
the longest increasing subsequence $\operatorname{LIS}(\sigma_{n})$ for
various types of large random permutations $\sigma_{n}$. For uniform random
permutations $\sigma_{n}$, the study of $\operatorname{LIS}(\sigma_{n})$ was
initiated in the 1960s by Ulam [Ula61]. In this case, one has
$\operatorname{LIS}(\sigma_{n})\sim 2\sqrt{n}$ [Ham72, VK77, LS77, AD95]. The
strongest known result is due to Dauvergne and Virág [DV21], who showed that
the scaling limit of the longest increasing subsequence in a uniform
permutation is the _directed geodesic_ of the _directed landscape_. The study
of $\operatorname{LIS}(\sigma_{n})$ is connected with many other problems in
combinatorics and probability theory, such as last passage percolation and
random matrix theory; see the book of Romik [Rom15] for an overview. In recent
years, many extensions beyond uniform permutations have been considered, for
instance:

  * •

when $\sigma_{n}$ is a uniform pattern-avoiding permutation [DHW03, MY17,
MY20, BBD+22];

  * •

when $\sigma_{n}$ follows the _Mallows distribution_ , or is a product of such
random permutations [MS13, BP15, BB17, Zho23];

  * •

when $\sigma_{n}$ is conjugacy-invariant with few cycles, in particular
_Ewens-distributed_ [SK18];

  * •

when $\sigma_{n}$ is sampled222A precise definition of what it means to sample
a permutation from a measure is given in Section 1.1.3. from a probability
measure of the unit square $[0,1]^{2}$ having a density which satisfies
certain regularity/divergence conditions [DZ95, DZ99, Dub23].

  * •

when $\sigma_{n}$ is sampled from a random Brownian-type permuton, such as the
Brownian separable permutons [BBD+22] or the _skew Brownian permutons_
[BGS22].

To the best of our knowledge, the only papers proving non-trivial power-law
bounds for the length of the longest increasing subsequence are the recent
work of Dubach [Dub23] and the works on the Mallows model of Bhatnagar and
Peled, and Zhong [BP15, Zho23]. Dubach [Dub23] built a family of permutons
$\mu_{\alpha}$ for $1/2<\alpha<1$, with a density satisfying certain types of
divergence, and which have the interesting property that a sequence of random
permutations sampled from $\mu_{\alpha}$ has a longest increasing subsequence
with growth rate equivalent to $n^{\alpha}$. On the other hand, the authors of
[BP15, Zho23] looked at random permutations $\sigma_{n}$ distributed according
to the Mallows distribution with respect to various distances. They showed
that rescaling the so-called _scale parameter_ $\beta$ with $n$ in a specific
way (made explicit in the papers), one obtains that
$\operatorname{LIS}(\sigma_{n})$ is of order $n^{\alpha}$ for some
$1/2<\alpha<1$ (and in some cases they prove exact limit theorems).

####  1.1.3 Main results

Given a permuton $\mu$, sample $n$ independent points $Z_{1},\dots,Z_{n}$ in
the unit square $[0,1]^{2}$ according to $\mu$. These $n$ points induce a
random permutation $\sigma$: for any $i,j\in[n]:=\\{1,\dots,n\\}$, let
$\sigma(i)=j$ if the point with $i$-th lowest $x$-coordinate has $j$-th lowest
$y$-coordinate (this is well-defined since the marginals of a permutons are
uniform and so almost surely there are no points with the same $x$\- or
$y$-coordinates). We denote this permutation by $\operatorname{Perm}(\mu,n)$
and call it the random permutation induced by the permuton $\mu$ of size $n$.

This definition can be naturally extended to the case of random permutons. For
more details, see e.g. [Bor21, Section 2.1]. It is important to note that
$\operatorname{Perm}(\mu,n)$ converges in distribution in the permuton sense
to $\mu$ when $n$ tends to infinity, as shown in [BBF+20, Lemma 2.3].

Recall that $\operatorname{LIS}(\cdot)$ denotes the length of the longest
increasing subsequence in a permutation. Let $p\in(0,1)$ and recall that
$\bm{\mu}_{p}$ is the Brownian separable permuton of parameter $p$. We
restrict our analysis to the case $p\in(0,1)$, since the cases when $p=0$ and
$p=1$ are degenerate: the Brownian separable permutons $\bm{\mu}_{0}$ (resp.
$\bm{\mu}_{1}$) is the Lebesgue measure on the decreasing (resp. increasing)
diagonal of the unit square.

We are interested in studying
$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))$. See Figure 1 for
some simulations. The results of [BBD+22] show that the following convergence
holds in probability for all $p\in(0,1)$,

$\frac{\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))}{n}\to 0.$

It is simple to show that
$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))$ is bounded below by
$\sqrt{n}$ with high probability (see the discussion below Theorem 1.7 in
[BBD+22]). Our first main result shows that
$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))$ has an asymptotic
behavior that is strictly different from the two bounds above.

######  Theorem 1.1.

There exist two explicit functions $\alpha_{*}:(0,1)\to(1/2,1)$ and
$\beta^{*}:(0,1)\to(1/2,1)$ such that for all $p\in(0,1)$,

  * •

$1/2<\alpha_{*}(p)\leq\beta^{*}(p)<1$;

  * •

for each $\alpha<\alpha_{*}(p)$ and each $\beta>\beta^{*}(p)$, it holds with
probability tending to one as $n\to\infty$ that

$n^{\alpha}\leq\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))\leq
n^{\beta}.$

See Figure 2 for a plot of the graphs of the two functions $\alpha_{*}(p)$ and
$\beta^{*}(p)$ from 1.1 and a table of some of their values. See also Remark
1.2 at the end of this section for explicit formulas for these two functions.

Numerical values for $\alpha_{*}(p)$ and $\beta^{*}(p)$
---
$p$ |  $\alpha_{*}(p)$ |  $\beta^{*}(p)$
0.1 |  0.584 |  0.959
0.2 |  0.653 |  0.963
0.3 |  0.712 |  0.967
0.4 |  0.765 |  0.971
0.5 |  0.812 |  0.975
0.6 |  0.855 |  0.980
0.7 |  0.895 |  0.985
0.8 |  0.932 |  0.991
0.9 |  0.967 |  0.996

Figure 2:  Left: The plot of our bounds from 1.1 as functions of $p\in(0,1)$:
$\alpha_{*}(p)$ is in blue and $\beta^{*}(p)$ is in red. Right: Some numerical
values of the bounds $\alpha_{*}(p)$ and $\beta^{*}(p)$.

We expect that
$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))=n^{d(p)+o(1)}$ with
probability tending to 1 as $n\to\infty$, for some exponent
$d(p)\in[\alpha_{*}(p),\beta^{*}(p)]$. Numerical simulations suggest that
$d(p)$ should be very close to $\alpha_{*}(p)$ for all $p\in(0,1)$. See 1.5
below for a more precise statement and Appendix A for more details on the
numerical simulations.

We also expect that it is possible to transfer the bounds of 1.1 to uniform
separable permutations, see the text just before 1.6 for further discussion.

1.1 shows that the exponent $d(p)$ is strictly bigger than $1/2$ and strictly
smaller than $1$ for all $p\in(0,1)$. Note that the results (and techniques)
in [BBD+22] are insufficient to establish either of the two bounds. Indeed,
their results show that
$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))$ is sublinear in $n$
but, for instance, they do not exclude a potential behavior such as
$n/\log(n)$.

Note also that our results give the first proof that the growth rate of
$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))$ depends on $p$, at
least to some extent. This is because $\alpha_{*}(p)>\beta^{*}(\widetilde{p})$
when $p$ is close to 1 and $\widetilde{p}$ is close to zero.

We conclude this section by giving the explicit description of the functions
$\alpha_{*}(p)$ and $\beta^{*}(p)$.

######  Remark 1.2.

For all $p\in(0,1)$,

$\alpha_{*}(p)=1-\lambda_{\ast}(p),$

where $\lambda_{\ast}(p)$ is the only positive solution (see Remark 3.2 for
further explanations) to the equation
$\Phi^{\mathsf{S}}(-\lambda_{\ast}(p))=-2(1-p)\sqrt{\frac{2}{\pi}}$, with

$\Phi^{\mathsf{S}}(q)=\int_{0}^{\infty}(1-\mathrm{e}^{-qx})(\mathds{1}_{x\in(0,\log
2]}+p\mathds{1}_{x\in(\log
2,+\infty)})\frac{2\,\mathrm{e}^{x}\mathrm{d}x}{\sqrt{2\pi(\mathrm{e}^{x}-1)^{3}}}.$

Note that $\alpha_{*}(0^{+})=1/2$ and $\alpha_{*}(1^{-})=1$, and
$\alpha_{*}(p)$ is strictly increasing in $p\in(0,1)$. In the symmetric case
($p=1/2$), we get $\alpha_{*}(1/2)\approx 0.812$. On the other hand, for all
$p\in(0,1)$,

$\beta^{*}(p)=1-\lambda^{*}(p),$

where
$\lambda^{*}(p)=\sup_{\beta\in(0,\log(2)),\delta>0}\min\mathopen{}\mathclose{{}\left\\{\beta\delta\,,\,\sup_{\gamma<0}\\{\gamma\delta+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)\\}}\right\\}$
and $\kappa^{*}_{\gamma,r}(p)$ is the only _positive_ solution (see the
discussion below (5.5) for further explanations) to the equation

$\Phi(-\kappa^{*}_{\gamma,r}(p))-2(1-p)(1-\mathrm{e}^{\gamma})\sqrt{\frac{2}{\pi}}\frac{r^{-1}-2}{\sqrt{r^{-1}-1}}=0,$
(1.4)

where $\Phi(q)=2\sqrt{2}\frac{\Gamma(q+1/2)}{\Gamma(q)}$. See Section 1.4 for
some explanations on the origin of the latter expressions.

###  1.2 Brownian cographon results

####  1.2.1 Graphons and the Brownian cographons

A graphon is an equivalence class of measurable functions
$W:[0,1]^{2}\to\\{0,1\\}$ which are symmetric (i.e. $W(x,y)=W(y,x)$ for all
$x,y\in[0,1]$), under the equivalence relation $\sim$, where $W\sim U$ if
there exists an invertible, measurable, Lebesgue measure preserving function
$\phi:[0,1]\to[0,1]$ such that $W(\phi(x),\phi(y))=U(x,y)$ for almost every
$x,y\in[0,1].$

Intuitively, a graphon is a continuous analog of the adjacency matrix of a
graph, viewed up to relabeling its continuous vertex set. To every graph $G$
with $n$ labeled vertices, one can naturally associate a corresponding
graphon:

$\displaystyle W_{G}:$ $\displaystyle[0,1]^{2}\to\\{0,1\\},$
$\displaystyle(x,y)\mapsto\,\,\,A_{\lceil nx\rceil,\lceil ny\rceil},$

where $A$ is the adjacency matrix of the graph $G$. Note that any relabeling
of the vertices of $G$ gives the same graphon $W_{G}$, and so the definition
extends to unlabeled graphs. It is possible to define the so-called _cut
metric_ , first on functions and then on graphons. The cut metric induces a
notion of convergence for graphons (and so for graphs). Roughly speaking, the
graphon convergence is the convergence of the rescaled adjacency matrix with
respect to the cut metric. Graphon convergence has been first studied in
[BCL+08] and developed into a vast topic in graph combinatorics, see [Lov12]
for an overview of this field of research.

Given the signed excursion $(\mathfrak{e},\mathfrak{s},p)$ introduced in
Section 1.1.1, the Brownian cographon $\bm{W}_{p}$ of parameter $p\in[0,1]$ is
defined (following [BBF+22a]) as the equivalence class of random functions

$\displaystyle\bm{W}_{p}:$ $\displaystyle[0,1]^{2}\to\\{0,1\\},$ (1.5)
$\displaystyle(x,y)\mapsto\,\,\,\mathds{1}_{\mathfrak{s}(\ell_{x,y})=\oplus},$

where, as in Section 1.1.1, if $(x,y)\in\mathcal{R}_{\mathfrak{e}}^{2}$ and
$x<y$, we denote by $\ell_{x,y}\in[x,y]$ the unique strict local minimum
$\min_{[x,y]}\mathfrak{e}$. If $x$ or $y$ is not in
$\mathcal{R}_{\mathfrak{e}}$ then we arbitrarily set
$\mathfrak{s}(\ell_{x,y})=\oplus$. This choice does not change the law of
$\bm{W}_{p}$ because a.s.
$\operatorname{Leb}([0,1]^{2}\setminus\mathcal{R}_{\mathfrak{e}}^{2})=0$. We
stress the fact that $\bm{W}_{p}$ is a _random_ graphon.

A cograph is a graph avoiding the path with four vertices as induced subgraph
(see the Wikipedia page for several other equivalent characterizations of
cographs and their computational properties). The Brownian cographon
$\bm{W}_{1/2}$ has been proven to be the limit in the graphon sense of uniform
random cographs when the number of vertices tends to infinity [BBF+22a,
Stu21]. Some first universality results for the Brownian cographons have been
recently established in [Len23], but we expect more to come.

####  1.2.2 The size of the largest homogeneous set

An independent set of a graph $G$ is a subset of its vertices such that every
two distinct vertices in the subset are not adjacent, while a clique of a
graph $G$ is a subset of its vertices such that every two distinct vertices in
the subset are adjacent. For a graph $G$, a subset of its vertices is called
homogeneous if it is either an independent set or a clique. The _Erdős–Hajnal
conjecture_ [EH77, EH89] states that every $H$-free graph of size $n$ (i.e. a
graph avoiding a given subgraph $H$ as induced subgraph) has a homogeneous set
of polynomial size333We recall that every graph of size $n$ has a homogeneous
set of size $\log(n)$, and this is optimal up to a constant. Determining the
optimal constant $C$ such that every graph of size $n$ has a homogeneous set
of size at least $C\log(n)$ is equivalent to the computation of diagonal
Ramsey numbers, see [CGMS23] for the best-known bounds. in $n$, i.e. of size
$c\cdot n^{\alpha(H)}$ for some $\alpha(H)\in(0,1]$. This conjecture is still
open, see [Chu14] for a survey and [BNSS23] for the best-known bound.

We emphasize that cographs play a key role in this conjecture. Indeed, since a
homogeneous set in a graph induces a cograph, and all cographs of size $n$
have a homogeneous set of size at least $\sqrt{n}$ [EH89], then the
Erdős–Hajnal conjecture takes the following equivalent form: Every $H$-free
graph of size $n$ contains a cograph of polynomial size as an induced
subgraph. In fact, this reformulation is one of the most classical ways to
attack the conjecture, see for instance [EH89].

Our motivations for studying homogeneous sets in the Brownian cographons are
multiple. Specifically, they come from the above reformulation of the
Erdős–Hajnal conjecture, from its probabilistic version [LRS+10, KMRS14]
discussed below, from the recent graphon convergence results towards the
Brownian cographons mentioned earlier, and from the recent developments in
[BBD+22], also explained below.

The authors of [LRS+10, KMRS14] established that for a large family of graphs
$H$, a uniformly random $H$-free graph with $n$ vertices has with high
probability a homogeneous set of _linear size_. We highlight that here the
homogeneous set has linear size and not only polynomial size as in the
original version of Erdős–Hajnal conjecture (i.e. $\alpha(H)$=1). When this
holds, the graph $H$ is said to have the asymptotic linear Erdős-Hajnal
property (see [KMRS14] for a precise definition). [KMRS14, Section 5] asked
whether a uniform random cograph with $n$ vertices has the asymptotic linear
Erdős-Hajnal property.444Indeed, cographs do not fit into the results of
[LRS+10, KMRS14]. This question was answered negatively in [BBD+22, Theorem
1.2], where it was shown that the maximal size of a homogeneous set
$\operatorname{LHS}(G_{n})$ in a uniform random cograph $G_{n}$ with $n$
vertices converges to zero in probability when divided by $n$. The authors
left open the question of finding the exact order of magnitude of
$\operatorname{LHS}(G_{n})$ (see [BBD+22, Remark 1.5]), pointing out that
$\sqrt{n}$ is a trivial lower bound. Also in this setting, the results of
[BBD+22] do not exclude a potential behavior such as $n/\log(n)$. The latter
behavior is not entirely unexpected. Indeed, as pointed out in [KMRS14,
Section 1.2], $n/\log(n)$ is the asymptotic behavior for
$\operatorname{LHS}(\widetilde{G}_{n})$ when $\widetilde{G}_{n}$ is a uniform
graphs avoiding the path $P_{3}$ with three vertices (recall that cographs are
graph avoiding the path $P_{4}$ with four vertices), and for instance graphs
avoiding $P_{3}$ and $P_{4}$ have the same (exceptional) _coloring number_
555The _coloring number_ of a graph (see [LRS+10, Definition 2]) should not be
confused with its _chromatic number_. $2$; see [LRS+10, Section 1, p. 4] for
further details.

Our results in the next section imply explicit power-law bounds for the analog
of $\alpha(H)$ for graphs sampled from the Brownian cographons (1.3 and 1.4),
and we expect that the same bounds can be proven for uniform cographs (Section
1.3). The latter result would distinguish the behavior of
$\operatorname{LHS}(\cdot)$ on uniform cographs and uniform graphs avoiding
$P_{3}$.

####  1.2.3 Main results

Given a graphon $W$, we can consider the random graph induced by $W$ of size
$n$, denoted by $\operatorname{Graph}(W,n)$ and defined as follows: consider
$n$ vertices $\\{v_{1},v_{2},\dots,v_{n}\\}$ and, let $(U_{1},\ldots,U_{n})$
be $n$ i.i.d. uniform random variables in $[0,1]$. We connect the vertices
$v_{i}$ and $v_{j}$ with an edge if and only if $W(U_{i},U_{j})=1$. This
definition can be naturally extended to the case of random graphons (see
[BBF+22a, Section 3.2] for further details). Note that
$\operatorname{Graph}(W,n)$ converges in distribution to $W$ when $n$ tends to
infinity, as shown in [BBF+22a, Lemma 3.9].

Recall that $\operatorname{LHS}(\cdot)$ denotes the size of the largest
homogeneous set in a graph. We also denote by $\operatorname{LIN}(\cdot)$ the
size of the largest independent set in a graph and by
$\operatorname{LCL}(\cdot)$ the size of the largest clique in a graph (the
latter two quantities are usually denoted by $\alpha(\cdot)$ and
$\omega(\cdot)$ in the literature, but we preferred to adopt a different
notation since it is more consistent with the one used in Section 1.1 for
permutations). See Figure 1 for some simulations of the largest homogeneous
set in $\operatorname{Graph}(\bm{W}_{p},n)$.

######  Theorem 1.3.

Let $p\in(0,1)$ and $\bm{W}_{p}$ be the Brownian cographon of parameter $p$.
Let $\alpha_{*}(p)$ and $\beta^{*}(p)$ be as in 1.1. Then

  * •

for each $\alpha<\alpha_{*}(p)$ and each $\beta>\beta^{*}(p)$ it holds with
probability tending to one as $n\to\infty$ that

$n^{\alpha}\leq\operatorname{LCL}(\operatorname{Graph}(\bm{W}_{p},n))\leq
n^{\beta};$

  * •

for each $\overline{\alpha}<\alpha_{*}(1-p)$ and each
$\overline{\beta}>\beta^{*}(1-p)$ it holds with probability tending to one as
$n\to\infty$ that

$n^{\overline{\alpha}}\leq\operatorname{LIN}(\operatorname{Graph}(\bm{W}_{p},n))\leq
n^{\overline{\beta}}.$

In this paper, we will prove 1.1 and derive 1.3 from it (see Section 2.2 for
further explanations). We point out that one can equivalently directly prove
1.3 and then derive 1.1, i.e. the two theorems are equivalent. We opted for
the first strategy since we found slightly simpler to phrase some
combinatorial constructions in term of permutations rather than graphs.

As in the case of 1.1, we expect that it is possible to transfer the bounds in
1.3 to uniform cographons. See the text just before 1.6 for further
discussion.

We have the following immediate consequence of 1.3.

######  Corollary 1.4.

Let $p\in(0,1)$ and $\bm{W}_{p}$ be the Brownian cographon of parameter $p$.
Let $\alpha_{*}(p)$ and $\beta^{*}(p)$ be as in 1.1, then for each
$\widetilde{\alpha}<\alpha_{*}(\widetilde{p})$ and each
$\widetilde{\beta}>\beta^{*}(\widetilde{p})$ with
$\widetilde{p}=\max\\{p,1-p\\}$, it holds with probability tending to one as
$n\to\infty$ that

$n^{\widetilde{\alpha}}\leq\operatorname{LHS}(\operatorname{Graph}(\bm{W}_{p},n))\leq
n^{\widetilde{\beta}}.$

Note that our results in 1.3 also complement the results of McKinley [McK19],
where the author constructed certain graphons $W_{\alpha}$ such that the size
of the largest clique $\operatorname{LCL}(\operatorname{Graph}(W_{\alpha},n))$
behaves like $n^{\alpha}$ for all $\alpha\in(0,1)$.

###  1.3 Conjectures and potential extensions

The results in Theorems 1.1 and 1.3 establish upper and lower bounds for the
polynomial growth of the longest increasing subsequence in permutations
sampled from the Brownian separable permutons and for the largest clique and
independent set in graphs sampled from the Brownian cographons. We expect the
existence of a deterministic _critical exponent_ for these quantities (_c.f._
2.2).

######  Conjecture 1.5.

For all $p\in(0,1)$ there exists $d(p)\in[\alpha_{*}(p),\beta^{*}(p)]$ such
that with probability tending to 1 as $n\to\infty$

$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))=n^{d(p)+o(1)},$
$\operatorname{LCL}(\operatorname{Graph}(\bm{W}_{p},n))=n^{d(p)+o(1)}\qquad\text{and}\qquad\operatorname{LIN}(\operatorname{Graph}(\bm{W}_{p},n))=n^{d(1-p)+o(1)}.$

As already mentioned, numerical simulations suggest that $d(p)$ should be very
close to $\alpha_{*}(p)$ for all $p\in(0,1)$. See Appendix A for more details.
Various heuristic arguments indicate that our lower bound $\alpha_{*}(p)$
should _not_ be sharp for all $p\in(0,1)$, i.e. it should hold that
$\alpha_{*}(p)<d(p)$ for all $p\in(0,1)$.

We expect that our estimates for longest increasing subsequences and largest
homogeneous sets from Theorems 1.1 and 1.3 in the case when $p=1/2$ can be
transferred to the setting of uniform separable permutations and uniform
cographs, respectively. To explain how this might be accomplished, we recall
that both uniform separable permutations and uniform cographs can be encoded
by random walk excursions with i.i.d. steps and some collections of random
signs $\oplus/\ominus$, in a similar way as the Brownian separable permutons
and the Brownian cographons can be encoded by a signed Brownian excursion.

The _KMT coupling theorem_ [KMT75, Zai98] states that one can construct a
random walk with i.i.d. steps and a standard Brownian motion on the same
probability space in such a way that with high probability, the difference of
their values at each time $n$ is $O(\log n)$. To transfer our bounds to the
setting of uniform separable permutons and uniform graphons, a natural
approach would be to couple the encoding walks for (the infinite-volume
version of) the discrete models with the encoding Brownian motion for (the
infinite-volume version of) the Brownian models via KMT. One could then use
the coupling to transfer estimates for Brownian motion to estimates for random
walk, and finally use local absolute continuity arguments to transfer from an
unconditioned walk to a random walk excursion. We point out that a similar
approach has been used to prove estimates for random planar maps in [GHS20].
However, we expect the above KMT coupling argument to require a fair amount of
technical work, so we do not carry it out in this paper.

It would also be interesting to deal with the discrete models themselves to
come up with power-law bounds (or, even better, with the exact exponents) for
the length of the longest increasing sequence in uniform separable
permutations and the size of the largest homogeneous set in uniform cographs.

In fact, we expect an even stronger relationship between discrete and
continuum models.

######  Conjecture 1.6.

Let $d(1/2)\in[\alpha_{*}(1/2),\beta^{*}(1/2)]$ be as in 1.5. Let $\sigma_{n}$
and $G_{n}$ be a uniform separable permutation and a uniform separable cograph
of size $n$, respectively. Then the following holds with probability tending
to 1 as $n\to\infty$:

$\operatorname{LIS}(\sigma_{n})=n^{d(1/2)+o(1)}\qquad\text{and}\qquad\operatorname{LHS}(G_{n})=n^{d(1/2)+o(1)}.$

It also seems possible that our methods could be extended to some models of
uniform permutations in substitution-closed classes which are well-behaved
with respect to the substitution decomposition [BBF+20, BBFS20] and to uniform
graphs in some classes of graphs which are closed under the substitution
operation at the core of the modular decomposition [BBF+22a].

####  1.3.1 Skew Brownian permuton and random planar maps

We now explain certain connections with other models of random permutations,
with random geometry, and with the study of planar maps.

Recently, the first author of this paper constructed in [Bor23] a two-
parameter family of universal random permutons $\bm{\mu}_{\rho,q}$ – indexed
by $(\rho,q)\in(-1,1]\times[0,1]$ and called _skew Brownian permutons_ – and
showed that they are the limits of various models of random permutations
[BM22, Bor22]. Additionally, skew Brownian permutons are connected with
multiple models of decorated planar maps and SLE-decorated Liouville quantum
gravity spheres (see [Bor23, Section 1.5]).

As shown in [Bor23, Theorem 1.12], the Brownian separable permutons
$\bm{\mu}_{p}$ studied in this paper coincide with the skew Brownian permutons
$\bm{\mu}_{1,1-p}$. The skew Brownian permuton $\bm{\mu}_{-1/2,1/2}$ is the
_Baxter permuton_ [BM22], i.e. the permuton limit of uniform Baxter
permutations. Additionally, in [Bor23, Section 1.6, Item 6] it is conjectured
that $\bm{\mu}_{-1,q}:=\lim_{\rho\to-1}\bm{\mu}_{\rho,q}$ are the Mallows
permutons [Sta09, SW18], i.e. the permuton limits of Mallows permutations. In
particular, $\lim_{\rho\to-1}\bm{\mu}_{\rho,1/2}$ should be the uniform
Lebesgue measure on $[0,1]^{2}$, i.e. the permuton limit of uniformly random
permutations.666Recall from [Sta09] that the Mallows permutons
$(\nu(\beta))_{\beta\in\mathbb{R}}$ describe the permuton limit of $q$-Mallows
distributed permutations of size $n$ when $q$ scales as $1-\frac{\beta}{n}$.
To the best of our knowledge, there are no available conjectures for the exact
relation between the $\beta$-parameter for the Mallows permutons $\nu(\beta)$
and the $q$-parameter for the permutons
$\bm{\mu}_{-1,q}:=\lim_{\rho\to-1}\bm{\mu}_{\rho,q}$, apart from the specific
case $\bm{\mu}_{-1,1/2}=\nu(0)$, where we recall that $\nu(0)$ coincides with
the uniform Lebesgue measure on $[0,1]^{2}$. See Figure 3 for a schematic
summary.

Combining the results of this paper with the fact that it is known that the
length of the longest increasing subsequence in Mallows permutations
behaves777Note that this result is true in the regime when Mallows
permutations exhibit a nontrivial permuton limit (i.e. when $q$ scales as
$1-\frac{\beta}{n}$), which is the regime of interest to us. like $\sqrt{n}$
[MS13], we propose the following conjecture. Recall the exponent $d(p)$ from
1.5.

######  Conjecture 1.7.

For all $(\rho,q)\in[-1,1]\times(0,1)$, let $\bm{\mu}_{\rho,q}$ be the skew
Brownian permuton. There exists a function
$\ell(\rho,q):[-1,1]\times(0,1)\to[1/2,1)$ such that with probability tending
to 1 as $n\to\infty$,

$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{\rho,q},n))=n^{\ell(\rho,q)+o(1)}.$

Moreover, $\ell(-1,q)=1/2$ for all $q\in(0,1)$,
$\ell(1,q)=d(1-q)\in[\alpha_{*}(1-q),\beta^{*}(1-q)]$ for all $q\in(0,1)$, and
$\ell(\rho,q)$ is continuous, non-increasing in $q$ and non-decreasing in
$\rho$.

We point out that in [BGS22, Corollary 1.13] it was shown that
$\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{\rho,q},n))$ is sublinear
for all $(\rho,q)\in(-1,1)\times(0,1)$. The exponents $\ell(\rho,q)$ of 1.7
should also be related to certain directed metrics on random planar maps, see
[BGS22, Remark 1.15] for further details. In Figure 3, we summarize various
models of random permutations and random planar maps which are connected with
the skew Brownian permutons.

Figure 3:  The diagram shows the range of values
$(\rho,q)\in[-1,1]\times(0,1)$ for the parameters of the skew Brownian
permutons. At the bottom, in green, we have the Mallows permutons. At the top,
in red, we have the Brownian separable permutons. In blue, close to the
center, we have the Baxter permuton. Various models of random permutations
which are known to converge in the permuton sense to the skew Brownian
permutons are indicated between rounded parentheses. Finally, various models
of planar maps which are connected to the skew Brownian permutons are
indicated between squared parentheses.

###  1.4 Proof techniques and ordered subsets of the signed Brownian excursion

Recall that we will derive 1.3 from 1.1, so here we focus on the latter
theorem. Our results in 1.1 follow – after some non-trivial arguments in
Sections 4 and 6 – from some preliminary estimates on the probability of
certain events (introduced in the next two sections) related to the signed
Brownian excursion $(\mathfrak{e},\mathfrak{s},p)$.

####  1.4.1 Strategy for the proof of the lower bound

We say that a subset $O\subset[0,1]$ is ordered w.r.t.
$\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ if the usual order on $O$
coincides with $\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ on
$O\cap\mathcal{R}_{\mathfrak{e}}$.

To obtain the lower bound in 1.1, we first define in (1.6) a selection rule
$\mathsf{S}$ which determines a large subset $\mathcal{S}\subset[0,1]$ ordered
w.r.t. $\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$. Here, _large_ refers
to a good notion of size, which we could, e.g., take to be Hausdorff
dimension.

To define the selection rule $\mathsf{S}$, we explore the signed excursion
$(\mathfrak{e},\mathfrak{s},p)$ by heights. We call branching height a height
which corresponds to a local minimum of $\mathfrak{e}$: a branching height is
said to be positive or negative according to the sign $\oplus$ or $\ominus$ of
the corresponding symbol in $\mathfrak{s}$. We denote by
$\mathcal{B}_{\oplus}$ and $\mathcal{B}_{\ominus}$ the set of positive and
negative branching heights respectively, and we set
$\mathcal{B}=\mathcal{B}_{\oplus}\cup\mathcal{B}_{\ominus}$. Each branching
height $b=\mathfrak{e}(t_{b})$ results in one sub-excursion of $\mathfrak{e}$
over an interval $(a,c)\subset[0,1]$ splitting into two sub-excursions over
the intervals $(a,t_{b})$ and $(t_{b},c)$ for some $t_{b}\in(a,c)$. See the
red excursions and red intervals in Figure 4.

Figure 4:  A sketch for the notation introduced in Section 1.4.1.

Note that the _optimal_ selection rule to find the largest ordered subset of
$[0,1]$ w.r.t. $\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ can be
informally read as follows. Whenever we hit a positive branching height, we
keep both intervals $(a,t_{b})$ and $(t_{b},c)$ and carry on the exploration
in both components of $\mathfrak{e}$. On the other hand, when reaching a
negative branching height, one needs to discard one of the intervals
$(a,t_{b})$ and $(t_{b},c)$ (because in this case, by definition (1.1),
$y\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}x$ for almost all
$x\in(a,t_{b})$ and $y\in(t_{b},c)$), keeping only the one with the largest
ordered subset.

The main issue with the previous considerations is the heavily non-Markovian
nature of the selection rule at negative branching heights: in order to pick
one of $(a,t_{b})$ or $(t_{b},c)$ over the other, one a priori needs to look
into the whole future and see which one of them has the largest ordered
subset. Our approach is to replace this selection rule by a Markovian rule.
More precisely, we consider the following selection rule $\mathsf{S}$:

“Whenever reaching a negative branching height, we discard the smaller (1.6)
(in terms of Lebesgue measure) interval between $(a,t_{b})$ and $(t_{b},c)$.”

We then want to show that the selection rule $\mathsf{S}$ does not discard too
many points, in a sense made precise in the next two paragraphs.

One essential tool in our proof is the analysis of a natural _fragmentation
process_ [Ber06], or more precisely of a _self-similar interval fragmentation
process_ , embedded in the Brownian excursion $\mathfrak{e}$ (see (2.1) below
for a precise definition). A key player in the description of such processes
is the so-called tagged fragment, which in our case, consists in looking at
the duration of the excursion at height $h\geq 0$ straddling a uniform point
$U$ in $(0,1)$. See the green excursion and green interval in Figure 4.
[Ber02, Section 4] describes the law of the tagged fragment as a stochastic
process with time parameter $h\geq 0$: it is an explicit _positive self-
similar Markov process with index $-\frac{1}{2}$_, see 2.3 for a precise
statement.

######  Remark 1.8.

The specific expressions for our bounds $\alpha_{*}(p)$ and $\beta^{*}(p)$ in
Remark 1.2 are related to the expression of some Laplace exponents of the
fragmentation process mentioned above, see for instance (3.3) below.

In order to show that the selection rule $\mathsf{S}$ does not discard too
many points, we proceed as follows:

  1. (a)

we first estimate the probability that the tagged fragment corresponding to
$U$ survives _long enough_ , in the sense that it reaches some small value
$\varepsilon$ before it (possibly) gets discarded by $\mathsf{S}$. In 3.1, we
show that the latter probability is asymptotically
$c\,\varepsilon^{\lambda_{\ast}(p)}$, for some positive constant $c>0$ (recall
from Remark 1.2 that $\lambda_{*}(p)=1-\alpha_{*}(p)$).

  2. (b)

Then in 3.4, we extend this estimate to a so-called _two-point function
estimate_ : we show that the probability that two tagged fragments
corresponding to two independent uniform points $U$ and $V$ in $(0,1)$ both
survive until they get smaller than $\varepsilon$ is asymptotically
$c^{\prime}\,\varepsilon^{2\lambda_{\ast}(p)}$, for some (other) positive
constant $c^{\prime}>0$.

The above two estimates turn out to be enough to then deduce the lower bound
in 1.1, as shown in Section 4.

######  Remark 1.9.

One can also introduce the set of survival times

$\mathcal{S}:=\\{t\in[0,1],\;t\;\text{is not in any sub-interval which is
discarded by }\mathsf{S}\\}.$

Plainly, $\mathcal{S}$ is a random set of fractal type and whose law depends
on the parameter $p\in(0,1)$ of the signs. Moreover, by construction, we have
the following immediate result: Almost surely, $\mathcal{S}$ is totally
ordered w.r.t. $\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$.

We believe that the first moment estimate in Item $(a)$ above, together with
an upgraded version of the two-point function estimate in Item $(b)$ above and
some energy method arguments (see for instance [MP10, Theorem 4.27]), would be
enough to prove the following result:

_For all $p\in(0,1)$, almost surely, the Hausdorff dimension of $\mathcal{S}$
is_

$\dim(\mathcal{S})=\dim(\mathcal{S}\cap\mathcal{R}_{\mathfrak{e}})=\alpha_{*}(p),$

_where $\alpha_{*}(p)$ is as in Remark 1.2. _

We expect the upgraded version of the two-point function estimate mentioned
above to require a fair amount of technical work, so we do not carry it out in
this paper.

####  1.4.2 Strategy for the proof of the upper-bound

Our strategy to prove the upper bound in 1.1 is in some sense to analyze the
_worst-case scenario_.

Recall the notation from the previous section. We pick (in a manner which is
allowed to depend on the signed excursion $(\mathfrak{e},\mathfrak{s},p)$,
plus possibly some additional independent information) an arbitrary subset
$O\subset[0,1]^{2}$ which is ordered w.r.t.
$\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$. For each branching height
$b\in\mathcal{B}_{\ominus}$, let $\eta_{b}$ be the _discarding rule_
corresponding to the set $O$, that is, $\eta_{b}$ is equal to $L$ (for _left_)
if $O$ intersects $(t_{b},c)$ and $\eta_{b}$ is equal to $R$ (for _right_) if
$O$ intersects $(a,t_{b})$ (we make an arbitrary choice if $O$ intersects
neither of the two intervals). Our goal is to show that
$(\eta_{b})_{b\in\mathcal{B}_{\ominus}}$ discards a large subset of $[0,1]$ so
that the complement is small. To do that, we upper-bound as $\varepsilon\to 0$
the following probability

$\mathbb{P}\mathopen{}\mathclose{{}\left((\eta_{b})_{b\in\mathcal{B}_{\ominus}}\text{
does not discard the fragment corresponding to }U\text{ before it gets smaller
than }\varepsilon}\right),$

where $U$ is a uniform point in $[0,1]$ independent from everything else. In
5.1, we show that the above probability is upper-bounded by
$c\cdot\varepsilon^{\lambda^{*}(p)}$ as $\varepsilon\to 0$ (recall from Remark
1.2 that $\lambda^{*}(p)=1-\beta^{*}(p)$). This is done in two main steps:

  * •

Fix $r\in(1/2,1)$. We say that a branching height $b\in\mathcal{B}_{\ominus}$
whose corresponding excursion interval $(a,c)$ contains $U$ is _balanced_ (at
scale $r$) if $\max\\{t_{b}-a,c-t_{b}\\}\leq r(c-a)$, i.e. the sub-excursions
to the left and right of the local minimum time $t_{b}$ are of comparable time
duration (recall Figure 4). The first step, which is carried out in 5.4, is to
upper-bound the probability that $(\eta_{b})_{b\in\mathcal{B}_{\ominus}}$ does
not discard $U$ before reaching the $m$-th smallest balanced branching height.
In particular, we will show that this probability is upper-bounded by $r^{m}$.

  * •

The second step, which is carried out in 5.5, is to upper-bound the
probability that the fragment corresponding to $U$ at the $m$-th balanced
branching height has duration smaller than $\varepsilon$.

We then optimize over the parameters $r$ and $m$.

Finally, we transfer this estimate to the discrete setting in Section 6
(obtaining the upper bound in 1.1), as follows. First, we sample a permutation
$\operatorname{Perm}(\bm{\mu}_{p},n)$ from the Brownian separable permuton
$\bm{\mu}_{p}$. Then, we consider the discarding rule
$(\eta_{b})_{b\in\mathcal{B}_{\ominus}}$ corresponding to the points of the
longest increasing subsequence in $\operatorname{Perm}(\bm{\mu}_{p},n)$ (if
there are multiple ones, we choose one arbitrarily). That is, at each
branching height $b\in\mathcal{B}_{\ominus}$ we discard the interval not
containing points of the longest increasing subsequence (we make an arbitrary
choice if the longest increasing subsequence intersects neither of the two
intervals). We then conclude using the estimates above.

######  Remark 1.10.

As in Remark 1.9, we expect that one can extend the arguments discussed above
to obtain the following result:

_Fix $p\in(0,1)$. Almost surely, every set $O\subset[0,1]$ such that
$O\cap\mathcal{R}_{\mathfrak{e}}$ is totally ordered w.r.t.
$\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ satisfies_

$\dim(O)\leq\beta^{*}(p),$

_where $\beta^{*}(p)$ is as in Remark 1.2. _

However, there are some technical arguments involved in transferring from an
estimate for a uniform time $U\in[0,1]$ to a bound for Hausdorff dimension, so
for the sake of brevity we do not prove the above statement in this paper.

##  2 Preliminary results

In this section we gather some preliminary results that are used later in the
paper. In Section 2.1 we discuss some classical properties of Brownian
excursions. In Section 2.2 we explain an equivalent way to sample permutations
and graphs from the Brownian separable permutons and the Brownian cographs and
how to derive 1.3 from 1.1. Finally, in Section 2.3, we properly introduce
fragmentation processes and the tagged fragment in a Brownian excursion.

###  2.1 Brownian excursions

We collect some standard properties of a Brownian excursion $\mathfrak{e}$ and
the order $\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ introduced in (1.1)
that will be used frequently (and sometimes tacitly) in the paper.

Conditioning on $\mathfrak{e}$, we say that $t\in[0,1]$ is regular for
$\mathfrak{e}$ if it is _not_ a one-sided local minimum of $\mathfrak{e}$,
that is, $t\in[0,1]$ is regular for $\mathfrak{e}$ if

$\forall\varepsilon>0,\,\exists\,t_{1}\in(t-\varepsilon,t),t_{2}\in(t,t+\varepsilon)\text{
such that
}\mathfrak{e}(t_{1})<\mathfrak{e}(t)\;\text{and}\;\mathfrak{e}(t_{2})<\mathfrak{e}(t).$

We denote by $\mathcal{R}_{\mathfrak{e}}$ the (random) set of regular points
of $\mathfrak{e}$.

######  Lemma 2.1.

Fix $p\in(0,1)$. Let $\mathfrak{e}$ be a (normalized) Brownian excursion and
$\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ be the relation introduced in
(1.1). Then, almost surely, the following assertions hold.

  1. (a)

All local minima of $\mathfrak{e}$ are strict local minima (hence countable),
they all have different heights, and they are dense in $[0,1]$.

  2. (b)

Local minima never split the excursion into two sub-excursions with equal
durations.

  3. (c)

For every $x,y\in\mathcal{R}_{\mathfrak{e}}$ with $x<y$, it holds that
$\min_{[x,y]}\mathfrak{e}$ is reached at a unique point which is a strict
local minimum.

  4. (d)

The relation $\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ restricted to
$\mathcal{R}_{\mathfrak{e}}$ is a total order.

  5. (e)

$\dim([0,1]\setminus\mathcal{R}_{\mathfrak{e}})=1/2$, where $\dim(\cdot)$
denotes the Hausdorff dimension of a set.

###### Proof.

The first two items are classical properties of Brownian excursions (see for
instance [RY13, Chapter XII]). Then Item (c) follows from the previous
properties and the definition of regular points.

Item (d) is [Maa20, Lemma 2.5]. Note that the latter lemma states our claim
only for a set of Lebesgue measure one (instead of
$\mathcal{R}_{\mathfrak{e}}$), but the proof of the lemma proves exactly our
claim.

Finally, we prove Item (e). This result is classical in the probabilistic
literature, and we include a proof only for the sake of completeness. Let $t$
be a time which is not regular for $\mathfrak{e}$. Then either there is a
rational $q<t$ such that $\mathfrak{e}$ attains a running minimum at time $t$
when run forward started from time $q$; or there exists a rational $q>t$ such
that $\mathfrak{e}$ attains a running minimum at time $t$ when run backward
started from time $q$. For each rational time $q$, the set of times at which
$\mathfrak{e}$ attains a running minimum when run forward (resp. backward)
from time $q$ has a.s. Hausdorff dimension 1/2 (by local absolute continuity
between the Brownian excursion and Brownian motion). Therefore the result
follows from the countable stability of Hausdorff dimension. ∎

###  2.2 Sampling permutations and graphs from the Brownian separable
permutons and the Brownian cographs

Recall from Section 1.1.3 that given the Brownian separable permuton
$\bm{\mu}_{p}$, the permutation $\operatorname{Perm}(\bm{\mu}_{p},n)$ is
obtained as follows: conditioning on $\bm{\mu}_{p}$, sample $n$ independent
points $Z_{1},\dots,Z_{n}$ in the unit square $[0,1]^{2}$ with distribution
$\bm{\mu}_{p}$. These $n$ points induce a random permutation
$\sigma_{n}=\operatorname{Perm}(\bm{\mu}_{p},n)$: for any
$i,j\in[n]:=\\{1,\dots,n\\}$, let $\sigma_{n}(i)=j$ if the point with $i$-th
lowest $x$-coordinate has $j$-th lowest $y$-coordinate. It is simple to
realize that the previous permutation can be equivalently obtained as follows:
sample $n$ independent uniform points $(U_{i})_{i\leq n}$ on $[0,1]$. Then
$\sigma_{n}$ is the permutation induced by the order of the points
$(U_{i})_{i\leq n}$ with respect to the order
$\vartriangleleft_{\mathfrak{e},\mathfrak{s},p}$ introduced in (1.1).
Equivalently, for $i<j$,

$\displaystyle\sigma_{n}(i)<\sigma_{n}(j)\quad\text{if and only
if}\quad\mathfrak{s}(\ell_{\bar{U}_{i},\bar{U}_{j}})=\oplus,$

where $(\bar{U}_{i})_{i\leq n}$ is the re-arrangement of $(U_{i})_{i\leq n}$
in increasing order and
$\ell_{\bar{U}_{i},\bar{U}_{j}}\in[\bar{U}_{i},\bar{U}_{j}]$ is the unique
strict local minimum $\min_{[\bar{U}_{i},\bar{U}_{j}]}\mathfrak{e}$. Recall
from 2.1 that almost surely, for every $x,y\in\mathcal{R}_{\mathfrak{e}}$ with
$x<y$, the minimum $\min_{[x,y]}\mathfrak{e}$ is reached at a unique point
which is a strict local minimum and $\mathcal{R}_{\mathfrak{e}}$ has Lebesgue
measure one, so the previous quantities are almost surely well-defined.
Therefore, when convenient, we will denote
$\sigma_{n}=\operatorname{Perm}(\bm{\mu}_{p},n)$ also by
$\sigma_{n}=\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U_{i})_{i\leq n})$.

Recall now that given the Brownian cographon $\bm{W}_{p}$ introduced in (1.5),
we can consider the random graph induced by $\bm{W}_{p}$ of size $n$, denoted
by $\operatorname{Graph}(\bm{W}_{p},n)$ and defined as follows: consider $n$
vertices $\\{v_{1},v_{2},\dots,v_{n}\\}$, and let $(U_{1},\ldots,U_{n})$ be
$n$ i.i.d. uniform random variables in $[0,1]$, independent of $\bm{W}_{p}$.
We connect the vertices $v_{i}$ and $v_{j}$ with an edge if and only if
$\bm{W}_{p}(U_{i},U_{j})=1$. Equivalently, from the definition in (1.5), we
connect the vertices $v_{i}$ and $v_{j}$ with an edge if and only if
$\mathfrak{s}(\ell_{U_{i},U_{j}})=\oplus$.

By comparing the above descriptions of $\operatorname{Perm}(\bm{\mu}_{p},n)$
and $\operatorname{Graph}(\bm{W}_{p},n)$ and noting that $\bm{\mu}_{1-p}$ has
the same law as $\bm{\mu}_{p}$ when we exchange all the $\oplus$ and $\ominus$
signs in the collection of signs $\mathfrak{s}$, we immediately obtain the
following result.

######  Lemma 2.2.

Fix $p\in(0,1)$. Let $\bm{\mu}_{p}$ be the Brownian separable permuton of
parameter $p$ and let $\bm{W}_{p}$ be the Brownian cographon of parameter $p$.
Then

$\operatorname{LCL}(\operatorname{Graph}(\bm{W}_{p},n))\stackrel{{\scriptstyle
d}}{{=}}\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{p},n))\quad\text{ and
}\quad\operatorname{LIN}(\operatorname{Graph}(\bm{W}_{p},n))\stackrel{{\scriptstyle
d}}{{=}}\operatorname{LIS}(\operatorname{Perm}(\bm{\mu}_{1-p},n)).$

As a consequence of 2.2, we see that 1.3 follows immediately from 1.1. We also
recall that 1.4 is an immediate consequence of 1.3. Hence, in the rest of the
paper we will focus on the proof of 1.1.

###  2.3 Fragmentation processes and the tagged fragment in a Brownian
excursion

As already mentioned in Section 1.4, our point of view bears close connections
with Bertoin’s fragmentation processes [Ber06], which in fact come in as one
of the main tools for the derivation of the exponent bounds $\alpha_{*}(p)$ an
$\beta^{*}(p)$. Such processes describe the behavior of a system of masses
which fall apart randomly over time in a Markovian way. In this paper we will
be interested in one particular example of so-called self-similar interval
fragmentation $\mathfrak{F}_{0}=(\mathfrak{F}_{0}(h),h\geq 0)$ defined from a
normalized Brownian excursion $\mathfrak{e}$ as

$\mathfrak{F}_{0}(h):=\\{s\in(0,1),\;\mathfrak{e}(s)>h\\},\quad h\geq 0.$
(2.1)

See Figure 5 for an illustration. It is clear that $\mathfrak{F}_{0}$ is a
nested family of open sets in $(0,1)$. Moreover, Brownian scaling implies that
$\mathfrak{F}_{0}$ also enjoys a self-similarity property: for all $r>0$, the
process $(r\mathfrak{F}_{0}(r^{-1/2}h),h\geq 0)$ has the law of the process
(2.1) defined from a Brownian excursion conditioned to have duration $r$. We
will denote by $\mathfrak{F}$ the collection of _lengths_ of intervals in
$\mathfrak{F}_{0}$. The process $\mathfrak{F}$ has been first introduced in
[Ber02], where it was proved to a be essentially a variant of the
Aldous–Pitman fragmentation [AP98].

Figure 5:  A sketch for the notation introduced for the self-similar interval
fragmentation $\mathfrak{F}_{0}=(\mathfrak{F}_{0}(h),h\geq 0)$. In red we
highlighted the intervals in $\mathfrak{F}_{0}(h)$ and the corresponding sub-
excursions of $\mathfrak{e}$ above level $h$. The interval $I^{t}(h)$ in
$\mathfrak{F}_{0}(h)$ containing $t$ has length $F^{t}(h)$ in $\mathfrak{F}$.

A key player in the description of such processes is the so-called tagged
fragment, which in our case consists in targeting the fragment straddling a
uniform point in $(0,1)$. For $t\in(0,1)$, we denote by $I^{t}(h)$, $h\geq 0$,
the interval in $\mathfrak{F}_{0}(h)$ which contains $t$, and we set
$I^{t}(h)=\emptyset$ if $t$ is not contained in any interval of
$\mathfrak{F}_{0}(h)$ (equivalently, $\mathfrak{e}(t)\leq h$). We further
write $F^{t}(h)$ for the length of the interval $I^{t}(h)$, and
$h^{t}=\mathfrak{e}(t)$ for its absorption time at $0$, i.e. the first height
$h$ such that $I^{t}(h)=\emptyset$. The tagged cell for the fragmentation, or
simply tagged fragment, is then given by

$F^{U}=(F^{U}(h),0\leq h<h^{U}),\quad\text{where $U$ is uniform in $(0,1)$,
independent from $\mathfrak{e}$.}$ (2.2)

Then [Ber02, Section 4] gives the law of $F^{U}$. Let us recall for
completeness that if $(X,P_{x})$ is a positive Markov process which under
$P_{x}$ starts at $x>0$, we say that $X$ is self-similar with index $\alpha$
if, for all $r>0$, the process $(rX(r^{\alpha}s),s\geq 0)$ under $P_{x}$ has
the law $P_{rx}$.

######  Proposition 2.3 ([Ber02, Section 4]).

The process $F^{U}$ is a positive self-similar Markov process with index
$-\frac{1}{2}$. It can be further written in the Lamperti representation as

$F^{U}(h)=\exp(-\xi_{\rho(h)}),\quad 0\leq h<h^{U},$

where $\rho(h)$ is the (Lamperti) time-change

$\rho(h):=\inf\mathopen{}\mathclose{{}\left\\{u>0,\;\int_{0}^{u}\mathrm{e}^{-\frac{1}{2}\xi_{r}}\mathrm{d}r>h}\right\\},\quad
0\leq h<h^{U},$ (2.3)

and $\xi$ is a subordinator with Laplace exponent

$\Phi(q):=-\log\mathbb{E}[\mathrm{e}^{-q\xi_{1}}]=\int_{0}^{\infty}(1-\mathrm{e}^{-qx})\frac{2\mathrm{e}^{x}}{\sqrt{2\pi(\mathrm{e}^{x}-1)^{3}}}\,\mathrm{d}x,\quad
q>-\frac{1}{2}.$ (2.4)

That is, $\xi$ has no killing, no drift, and Lévy measure
$\Lambda(\mathrm{d}x):=\frac{2\mathrm{e}^{x}\mathrm{d}x}{\sqrt{2\pi(\mathrm{e}^{x}-1)^{3}}}$
on $(0,+\infty)$.

######  Remark 2.4.

One can calculate that $\Phi(q)=2\sqrt{2}\frac{\Gamma(q+1/2)}{\Gamma(q)}$ (see
[Ber02, Equation (12)]). Note also that $\Phi(q)$ is increasing in $q$,
$\Phi(0)=0$, $\lim_{q\to(-1/2)^{+}}\Phi(q)=-\infty$ and
$\lim_{q\to+\infty}\Phi(q)=+\infty$. The fact that
$\Phi(q)=2\sqrt{2}\frac{\Gamma(q+1/2)}{\Gamma(q)}$, together with [KRŞ17,
Section 2.3] for instance, implies that $F^{U}$ has the law of the
$\frac{1}{2}$–stable (decreasing) subordinator conditioned to be absorbed
continuously at $0$.

The reason why $F^{U}$ plays a special part in the description of
$\mathfrak{F}$ is that it governs the behavior of the size of a _typical_
fragment in $\mathfrak{F}$.

We end this section with a technical lemma for subordinators which will be
relevant in later sections.

######  Lemma 2.5.

Let $\eta$ be a subordinator with Laplace exponent
$\Psi(q):=-\log\mathbb{E}[\mathrm{e}^{-q\eta_{1}}]$, and $a\geq 0$. Assume
that that there exists $a_{\ast}>0$ such that $\Psi$ extends (analytically) to
a neighborhood to the left of $0$ containing $-a_{\ast}$, $\Psi(-a_{\ast})=-a$
and $\Psi^{\prime}(-a_{\ast})<\infty$. For $x>0$, define the first passage
time of $\eta$ across $x$,

$S_{x}:=\inf\\{s>0,\;\eta_{s}>x\\}.$

Then for all $b\geq 0$, there exists a constant $c=c(a,b)\in(0,1)$ such that,

$\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-aS_{x}-b\eta_{S_{x}}}}\right]\underset{x\to\infty}{\sim}c\,\mathrm{e}^{-(a_{\ast}+b)x}.$
(2.5)

Moreover, for all $b>-a_{\ast}$, we have the upper-bound

$\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-aS_{x}-b\eta_{S_{x}}}}\right]\leq\mathrm{e}^{-(a_{\ast}+b)x},\quad\text{for
all }x>0.$ (2.6)

###### Proof.

The result is a consequence of exponential tilting. Since
$\Psi(-a_{\ast})=-a$, the process

$M^{a}_{s}:=\mathrm{e}^{a_{\ast}\eta_{s}-as},\quad s\geq 0,$

is a martingale. Let $\mathbb{P}^{a}$ denote the tilted probability measure
with respect to the martingale $M^{a}$. This is the measure defined from
Kolmogorov’s extension theorem by
$\mathrm{d}\mathbb{P}^{a}=M^{a}_{s}\cdot\mathrm{d}\mathbb{P}$ on
$\sigma(\eta_{r},r\leq s)$ for all $s\geq 0$. Plainly, under $\mathbb{P}^{a}$,
$\eta$ is a Lévy process with Laplace exponent
$\Psi^{a}(q)=\Psi(q-a_{\ast})+a$. We claim that by an optional stopping type
argument, we have

$\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-aS_{x}-b\eta_{S_{x}}}}\right]=\mathbb{E}^{a}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-(a_{\ast}+b)\eta_{S_{x}}}}\right]\quad\text{if
$b\geq 0$},$ (2.7)

and

$\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-aS_{x}-b\eta_{S_{x}}}}\right]\leq\mathbb{E}^{a}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-(a_{\ast}+b)\eta_{S_{x}}}}\right]\quad\text{if
$-a_{\ast}<b<0$},$ (2.8)

where $\mathbb{E}^{a}$ denotes expectation with respect to $\mathbb{P}^{a}$.
Indeed, since subordinators are transient (see for instance [Ber96, Chapter
III]), $S_{x}$ is a.s. finite, whence a.s.

$\lim_{n\to\infty}\mathrm{e}^{-(a_{\ast}+b)\eta_{n\wedge
S_{x}}}=\mathrm{e}^{-(a_{\ast}+b)\eta_{S_{x}}}\quad\text{and}\quad\lim_{n\to\infty}\mathrm{e}^{-a(n\wedge
S_{x})-b\,\eta_{n\wedge S_{x}}}=\mathrm{e}^{-aS_{x}-b\,\eta_{S_{x}}}.$

Moreover, since $a_{\ast}+b\geq 0$, by dominated convergence (the domination
is straightforward once we remark that under $\mathbb{P}^{a}$, $\eta$ is still
a subordinator, so that $\eta_{n\wedge S_{x}}\geq 0$),

$\mathbb{E}^{a}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-(a_{\ast}+b)\eta_{S_{x}}}}\right]=\lim_{n\to\infty}\mathbb{E}^{a}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-(a_{\ast}+b)\eta_{n\wedge
S_{x}}}}\right]=\lim_{n\to\infty}\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-a(n\wedge
S_{x})-b\,\eta_{n\wedge S_{x}}}}\right].$ (2.9)

For $a\geq 0$ and $b\geq 0$, another application of dominated convergence
gives the claim in (2.7). For $a\geq 0$ and $-a_{\ast}<b<0$, we note that by
Fatou’s lemma

$\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-aS_{x}-b\eta_{S_{x}}}}\right]=\mathbb{E}\mathopen{}\mathclose{{}\left[\liminf_{n\to\infty}\mathrm{e}^{-a(n\wedge
S_{x})-b\,\eta_{n\wedge
S_{x}}}}\right]\leq\liminf_{n\to\infty}\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-a(n\wedge
S_{x})-b\,\eta_{n\wedge
S_{x}}}}\right]\stackrel{{\scriptstyle\eqref{eq:first_step_lim}}}{{=}}\mathbb{E}^{a}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-(a_{\ast}+b)\eta_{S_{x}}}}\right],$

which is the claim in (2.8).

First of all, the inequality (2.6) is a trivial consequence of (2.7) and
(2.8), together with the observation that $\eta_{S_{x}}\geq x$. We now prove
the claim in (2.5). Since by assumption
$\mathbb{E}^{a}[\eta_{1}]=(\Psi^{a})^{\prime}(0)=\Psi^{\prime}(-a_{\ast})<\infty$,
by the renewal theorem [BVHS99, Theorem 1], $\eta_{S_{x}}-x$ converges in
distribution under $\mathbb{P}^{a}$ to a limiting non-degenerate random
variable as $x\to\infty$. Therefore

$\mathbb{E}^{a}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-(a_{\ast}+b)\eta_{S_{x}}}}\right]\underset{x\to\infty}{\sim}c\,\mathrm{e}^{-(a_{\ast}+b)x},$

for some constant $c\in(0,1)$. The statement of the lemma then follows from
(2.7). ∎

######  Remark 2.6.

The constant $c$ can be made explicit from [BVHS99, Theorem 1].

##  3 Estimates for the lower bound

The main goal of this section is to provide first and second moment estimates
involving our selection rule $\mathsf{S}$ defined in (1.6), which will be
later used in Section 4 to lower bound the length of the longest increasing
subsequence in permutations sampled from the Brownian separable permutons.
More precisely, we provide in 3.1 asymptotics as $\varepsilon\to 0$ for the
probability that the tagged fragment (2.2) survives (in the sense of
$\mathsf{S}$) until getting smaller than $\varepsilon$, and similar estimates
in 3.4 for the two-point function.

###  3.1 Embedding the selection rule in the tagged cell

Recall from Section 1.4.1 the following setup. Every local minimum
$t_{b}\in(0,1)$ of the Brownian excursion $\mathfrak{e}$ corresponds to a so-
called branching height $b=\mathfrak{e}(t_{b})$ and comes with a $\oplus$ or
$\ominus$ sign given by $\mathfrak{s}$. We denote by $\cal B_{\oplus}$ and
$\cal B_{\ominus}$ the sets of branching heights respectively associated with
$\oplus$ and $\ominus$ signs. Each branching height $b$ is splitting one
interval $(a,c)$ into the two sub-intervals $(a,t_{b})$ and $(t_{b},c)$ (see
Figure 4, p. 4). Our selection rule $\sf S$ is to discard at each _negative_
branching height the smaller of the two intervals $(a,t_{b})$ and $(t_{b},c)$
in terms of Lebesgue measure. In this paragraph we embed this strategy in the
fragmentation $\mathfrak{F}$ and the tagged fragment $F^{U}$ introduced in
(2.2). For a right-continuous non-negative process $X$, we introduce the
notation $\Delta X(t):=X(t)-X(t^{-})$ for its possible jump at time $t$.
Recall that the branching heights of $\mathfrak{e}$ are encoded by jumps in
the fragmentation process $\mathfrak{F}$. One can therefore enforce the
selection rule $\mathsf{S}$ in the tagged fragment $F^{U}$ by killing it at
the first _negative_ branching height $h$ in $(\mathfrak{e},\mathfrak{s},p)$
where the size of the other fragment, which is $-\Delta F^{U}(h)$, is larger
than $F^{U}(h)$; _c.f._ Figure 6. Moreover, note that in the notation of 2.3,
whenever $F^{U}(h)<-\Delta F^{U}(h)$, then after time-change we have that
$\Delta\xi_{\rho(h)}>\log 2$. Based on this, we set

$H^{U}_{\mathsf{S}}:=\inf\\{h\in\mathcal{B}_{\ominus},\;-\Delta
F^{U}(h)>F^{U}(h)\\},$ (3.1)

and $\overline{F}^{U}(h):=F^{U}(h)\mathds{1}_{h<H^{U}_{\mathsf{S}}}$, $h\geq
0$.

Figure 6:  A sketch explaining how we enforce the selection rule $\mathsf{S}$
in the tagged fragment $F^{U}$: at the first negative height when the fragment
$-\Delta F^{U}(h)$ is larger than the tagged fragment $F^{U}(h)$, we kill the
process $F^{U}$ at zero, i.e. with the notation in (3.1), we are considering
the process $\overline{F}^{U}(h)=F^{U}(h)\mathds{1}_{h<H^{U}_{\mathsf{S}}}$.

This also motivates the introduction of two new processes $\chi$ and
$\overline{\xi}$ describing the previous construction at the level of the Lévy
process $\xi$ in Proposition 2.3. For any jump time $s>0$ of $\xi$, the
variable $\chi_{s}$ encodes the $\oplus$ or $\ominus$ sign in $\mathfrak{s}$
attached to the branching height $\rho^{-1}(s)$ of $\mathfrak{e}$. More
precisely, conditional on $\xi$, for each $s>0$ such that $\Delta\xi_{s}>0$,
let $\chi_{s}=1$ or $\chi_{s}=0$ with probability $p$ and $1-p$ respectively
(for other times we send $\chi_{s}:=\lozenge$ to a cemetery state). We take
the random variables $\\{\chi_{s}:\Delta\xi_{s}>0\\}$ to be conditionally
independent given $\xi$.

One can then implement the strategy $\mathsf{S}$ on $\xi$, obtaining a new
process $\overline{\xi}$ which is a killed version of $\xi$. Informally
$\overline{\xi}$ is constructed as follows: let $s>0$ be a jump time for
$\xi$. If $\chi_{s}=1$, we do nothing. Otherwise $\chi_{s}=0$: then we kill
$\overline{\xi}$ (i.e. we set $\overline{\xi}_{s}=\infty$) if, and only if,
$\Delta\xi_{s}>\log 2$. More precisely, let $\xi^{\mathsf{S}}$ be a Lévy
process with intensity measure on $(0,+\infty)$.

$\Lambda^{\mathsf{S}}(\mathrm{d}x):=\Lambda(\mathrm{d}x)|_{x\in(0,\log
2]}+p\Lambda(\mathrm{d}x)|_{x\in(\log 2,+\infty)}=(\mathds{1}_{x\in(0,\log
2]}+p\mathds{1}_{x\in(\log
2,+\infty)})\frac{2\,\mathrm{e}^{x}\mathrm{d}x}{\sqrt{2\pi(\mathrm{e}^{x}-1)^{3}}}.$
(3.2)

We also set

$\Phi^{\mathsf{S}}(q):=\int_{0}^{\infty}(1-\mathrm{e}^{-qx})\Lambda^{\mathsf{S}}(\mathrm{d}x),\quad
q>-\frac{1}{2},$ (3.3)

for the Laplace exponent of $\xi^{\mathsf{S}}$. One may write
$\xi=\xi^{\mathsf{S}}+\xi^{\mathsf{K}}$, where $\xi^{\mathsf{K}}$ is an
independent Lévy process with Lévy measure supported on $(\log 2,+\infty)$

$\Lambda^{\mathsf{K}}(\mathrm{d}x):=(1-p)\Lambda(\mathrm{d}x)|_{x\in(\log
2,+\infty)}=\frac{2(1-p)\,\mathrm{e}^{x}\mathrm{d}x}{\sqrt{2\pi(\mathrm{e}^{x}-1)^{3}}}.$

In this description, as a result of the thinning operation (see888Informally,
the thinning operation is the operation which allows one to select some points
in a Poisson point process according to some random rule, obtaining a new
Poisson point process with some “thinned” intensity measure. e.g. [BBK20,
Section 2.2.2]), $\overline{\xi}$ has the law of $\xi^{\mathsf{S}}$ killed at
the first time $T$ when $\xi^{\mathsf{K}}$ has a jump. Note also that, in
light of 2.3, one has that
$\overline{F}^{U}(h)=\exp(-\overline{\xi}_{\rho(h)})$ for all $h\geq 0$.
Additionally, $\Lambda^{\mathsf{K}}$ has finite total mass, so that $T$ is an
exponential random variable with parameter

$\lambda(p)=\int_{\log
2}^{\infty}\Lambda^{\mathsf{K}}(\mathrm{d}x)=2(1-p)\sqrt{\frac{2}{\pi}}.$
(3.4)

There is a natural correspondence between $T$ and $H^{U}_{\mathsf{S}}$, which
is just given by a Lamperti time-change (recall (2.3)).

###  3.2 First moment estimate

Our first estimate in this subsection concerns the probability that the
fragment targeted at the uniform point $U$ survives _long enough_ , in the
sense that it reaches some small value before it gets (possibly) discarded.
Let $\varepsilon>0$, and

$H^{U}_{\varepsilon}:=\inf\\{h>0,\;F^{U}(h)<\varepsilon\\}.$ (3.5)

Recalling the height $H_{\mathsf{S}}^{U}$ from (3.1), we also introduce the
event

$\mathcal{E}_{\varepsilon}^{U}:=\mathopen{}\mathclose{{}\left\\{H^{U}_{\varepsilon}<H^{U}_{\mathsf{S}}}\right\\},$
(3.6)

i.e., the event that the fragment targeted at the uniform point $U$ gets
smaller than $\varepsilon$ before it gets (possibly) discarded.

We fix $p\in(0,1)$ for the rest of the section. All the constants appearing in
the next propositions depend on $p$, even if not explicitly stated.

######  Proposition 3.1.

Let $\lambda_{\ast}(p)$ be the only positive solution to the equation
$\Phi^{\mathsf{S}}(-\lambda_{\ast}(p))=-\lambda(p)$, with $\Phi^{\mathsf{S}}$
as in (3.3) and $\lambda(p)$ as in (3.4). The probability of
$\mathcal{E}_{\varepsilon}^{U}$ satisfies

$\mathbb{P}(\mathcal{E}_{\varepsilon}^{U})\leq\varepsilon^{\lambda_{\ast}(p)},\quad\text{for
all }\varepsilon>0.$ (3.7)

Moreover, there exists a constant $c>0$ such that

$\mathbb{P}\big{(}\mathcal{E}_{\varepsilon}^{U}\big{)}\underset{\varepsilon\to
0}{\sim}c\,\varepsilon^{\lambda_{\ast}(p)}.$ (3.8)

######  Remark 3.2.

We emphasize that the exponent $\lambda_{\ast}(p)$ is the same as the one
appearing in Remark 1.2 (see also that remark for some particular values of
$\lambda_{\ast}(p)$). Since $\Phi^{\mathsf{S}}$ is continuous on
$(-1/2,+\infty)$ with $\Phi^{\mathsf{S}}(0)=0$ and
$\Phi^{\mathsf{S}}(q)\to-\infty$ as $q\to(-1/2)^{+}$, it is plain that
$\lambda_{\ast}(p)\in(0,\frac{1}{2})$. See the left-hand side of Figure 2 for
the graph of
$\alpha_{*}(p)\stackrel{{\scriptstyle\eqref{eq:alpha_lam}}}{{=}}1-\lambda_{\ast}(p)$
for $p\in(0,1)$, obtained by solving numerically the equation
$\Phi^{\mathsf{S}}(-\lambda_{\ast}(p))=-\lambda(p)$.

###### Proof of 3.1.

The Lamperti representation provides a natural point of view to address this
question (see for instance [CM18, Section 2.3] where a similar approach was
used in a different context). Recall the subordinators $\xi^{\mathsf{S}}$ and
$\xi^{\mathsf{K}}$ and the time $T$ introduced just above (3.4). Note that

$\mathbb{P}\big{(}\mathcal{E}_{\varepsilon}^{U}\big{)}=\mathbb{P}\big{(}H^{U}_{\varepsilon}<H^{U}_{\mathsf{S}}\big{)}=\mathbb{P}\big{(}T_{-\log\varepsilon}<T\big{)},$
(3.9)

where $T_{x}:=\inf\\{s>0,\;\xi^{\mathsf{S}}_{s}>x\\}$ is the first passage
time of $\xi^{\mathsf{S}}$ above $x>0$. Now since $T$ is an exponential random
variable with parameter $\lambda(p)$ (see (3.4)), by the independence of
$\xi^{\mathsf{S}}$ and $\xi^{\mathsf{K}}$ (and so of $T_{-\log\varepsilon}$
and $T$),

$\mathbb{P}\big{(}T_{-\log\varepsilon}<T\big{)}=\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-\lambda(p)T_{-\log\varepsilon}}}\right].$
(3.10)

3.1 is then a consequence of 2.5. First, note that for all $q<1/2$,
$(\Phi^{\mathsf{S}})^{\prime}(-q)<\infty$ as is easily seen from (3.2) and
(3.3). Applying the aforementioned lemma for $a=\lambda(p)>0$ and $b=0$, we
obtain from (3.9) and (3.10) that

$\mathbb{P}(\mathcal{E}_{\varepsilon}^{U})\leq\varepsilon^{\lambda_{\ast}(p)},$

for all $\varepsilon>0$, and

$\mathbb{P}\big{(}\mathcal{E}_{\varepsilon}^{U}\big{)}\underset{\varepsilon\to
0}{\sim}c\,\varepsilon^{\lambda_{\ast}(p)},$

for some constant $c>0$, where $\lambda_{\ast}(p)$ is the positive solution to
the equation $\Phi^{\mathsf{S}}(-\lambda_{\ast}(p))=-\lambda(p)$. This proves
(3.7) and (3.8). ∎

We conclude this section with the following moment estimate.

######  Proposition 3.3.

Let $\zeta\geq 0$. There exists a constant $c=c(\zeta)>0$ such that

$\mathbb{E}\mathopen{}\mathclose{{}\left[F^{U}(H^{U}_{\varepsilon})^{\zeta}\cdot\mathds{1}_{\mathcal{E}_{\varepsilon}^{U}}}\right]\underset{\varepsilon\to
0}{\sim}c\,\varepsilon^{\zeta+\lambda_{\ast}(p)},$ (3.11)

where $\lambda_{\ast}(p)$ is the positive solution to
$\Phi^{\mathsf{S}}(-\lambda_{\ast}(p))=-\lambda(p)$. Moreover, if
$\zeta>-\lambda_{*}(p)$,

$\mathbb{E}\mathopen{}\mathclose{{}\left[F^{U}(H^{U}_{\varepsilon})^{\zeta}\cdot\mathds{1}_{\mathcal{E}_{\varepsilon}^{U}}}\right]\leq\varepsilon^{\zeta+\lambda_{\ast}(p)},\quad\text{for
all }\varepsilon>0.$

###### Proof.

Using the description in 2.3, together with the notation at the beginning of
this subsection, we have that

$\mathbb{E}\mathopen{}\mathclose{{}\left[F^{U}(H^{U}_{\varepsilon})^{\zeta}\cdot\mathds{1}_{\mathcal{E}_{\varepsilon}^{U}}}\right]=\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-\zeta\xi^{\mathsf{S}}_{T_{-\log\varepsilon}}}\cdot\mathds{1}_{T_{-\log\varepsilon}<T}}\right],$

where we recall that $T_{x}=\inf\\{s>0,\;\xi^{\mathsf{S}}_{s}>x\\}$ and $T$ is
the exponential random variable with parameter
$\lambda(p)=2(1-p)\sqrt{\frac{2}{\pi}}$ introduced in (3.4). Moreover, $T$ is
independent of $\xi^{\mathsf{S}}$, so that

$\mathbb{E}\mathopen{}\mathclose{{}\left[F^{U}(H^{U}_{\varepsilon})^{\zeta}\cdot\mathds{1}_{\mathcal{E}_{\varepsilon}^{U}}}\right]=\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{-\zeta\xi^{\mathsf{S}}_{T_{-\log\varepsilon}}-\lambda(p)T_{-\log\varepsilon}}}\right].$

An application of 2.5 (with $a=\lambda(p)>0$ and $b=\zeta>-\lambda_{*}(p)$)
yields the desired estimates. ∎

###  3.3 Two-point function estimate

We now consider two independent uniform points $U$ and $V$ in $(0,1)$ also
independent from all the other random quantities. Recall from (3.6) the
notation $\mathcal{E}^{U}_{\varepsilon}$ and $\mathcal{E}^{V}_{\varepsilon}$
respectively for the events that the fragments containing $U$ and $V$ survive
in the strategy $\mathsf{S}$ (defined in (1.6)) until getting smaller than
$\varepsilon>0$. We are interested in the correlation between the two events
$\mathcal{E}^{U}_{\varepsilon}$ and $\mathcal{E}^{V}_{\varepsilon}$. The aim
of this section is to prove the following second moment estimate, which should
be compared to 3.1.

######  Proposition 3.4.

There exists a constant $c>0$ such that

$\mathbb{P}\mathopen{}\mathclose{{}\left(\mathcal{E}^{U}_{\varepsilon}\cap\mathcal{E}^{V}_{\varepsilon}}\right)\underset{\varepsilon\to
0}{\sim}c\,\varepsilon^{2\lambda_{\ast}(p)},$

where $\lambda_{\ast}(p)$ is the only positive solution to the equation
$\Phi^{\mathsf{S}}(-\lambda_{\ast}(p))=-\lambda(p)$, with $\Phi^{\mathsf{S}}$
as in (3.3).

###### Proof.

Introduce, for $\varepsilon>0$, the event that $U$ and $V$ split before
reaching $\varepsilon$, namely

$\mathcal{G}_{\varepsilon}^{U,V}:=\mathopen{}\mathclose{{}\left\\{I^{U}(H_{\varepsilon}^{U})\neq
I^{V}(H_{\varepsilon}^{V})}\right\\}.$

Let $\varepsilon>0$. We split the event
$\mathcal{E}^{U}_{\varepsilon}\cap\mathcal{E}^{V}_{\varepsilon}$ according to
$\mathcal{G}_{\varepsilon}^{U,V}$ and its complement.

We first deal with the two-point function on the event
$(\mathcal{G}_{\varepsilon}^{U,V})^{c}$. In this case, we condition on
$(\mathfrak{e},\mathfrak{s},U)$ to obtain

$\mathbb{P}\mathopen{}\mathclose{{}\left(\mathcal{E}^{U}_{\varepsilon}\cap\mathcal{E}^{V}_{\varepsilon}\cap(\mathcal{G}_{\varepsilon}^{U,V})^{c}}\right)=\mathbb{P}\mathopen{}\mathclose{{}\left(\mathcal{E}^{U}_{\varepsilon}\cap\\{V\in
I^{U}(H_{\varepsilon}^{U})\\}}\right)=\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{\mathcal{E}^{U}_{\varepsilon}}\cdot\mathbb{P}\mathopen{}\mathclose{{}\left(V\in
I^{U}(H_{\varepsilon}^{U})|(\mathfrak{e},\mathfrak{s},U)}\right)}\right].$
(3.12)

We now argue conditionally on $(\mathfrak{e},\mathfrak{s},U)$. Since
$H_{\varepsilon}^{U}$ is a stopping time for the filtration
$\sigma(I^{U}(h^{\prime}),h^{\prime}\leq h)$, defined for all $h>0$, and $V$
is independent of $(\mathfrak{e},\mathfrak{s},U)$, we a.s. have
$\mathbb{P}\mathopen{}\mathclose{{}\left(V\in
I^{U}(H_{\varepsilon}^{U})|(\mathfrak{e},\mathfrak{s},U)}\right)=F^{U}(H_{\varepsilon}^{U})$.
Plugging this identity into (3.12), we infer that

$\mathbb{P}\mathopen{}\mathclose{{}\left(\mathcal{E}^{U}_{\varepsilon}\cap\mathcal{E}^{V}_{\varepsilon}\cap(\mathcal{G}_{\varepsilon}^{U,V})^{c}}\right)=\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{\mathcal{E}_{\varepsilon}^{U}}\cdot
F^{U}(H_{\varepsilon}^{U})}\right].$

Using 3.3, we therefore conclude that there exists a constant $c_{1}>0$ such
that

$\mathbb{P}\mathopen{}\mathclose{{}\left(\mathcal{E}^{U}_{\varepsilon}\cap\mathcal{E}^{V}_{\varepsilon}\cap(\mathcal{G}_{\varepsilon}^{U,V})^{c}}\right)\underset{\varepsilon\to
0}{\sim}c_{1}\varepsilon^{1+\lambda_{\ast}(p)}.$ (3.13)

We next deal with the two-point function on the event
$\mathcal{G}_{\varepsilon}^{U,V}$. Remark that this event can be rephrased as
the existence of a branching height $a\leq H_{\varepsilon}^{U}\wedge
H_{\varepsilon}^{V}$ separating $U$ and $V$. We note that $a$ is a stopping
time with respect to the filtration
$\sigma(I^{U}(h^{\prime}),I^{V}(h^{\prime})\,,\,h^{\prime}\leq h)$, defined
for all $h>0$. Moreover, given $I^{U}(a)$, the law of $U$ is uniform in
$I^{U}(a)$ (and the same applies to $V$). Therefore, by conditioning at height
$a$ and using the branching property of excursions above $a$,

$\mathbb{P}\Big{(}\mathcal{E}_{\varepsilon}^{U}\cap\mathcal{E}_{\varepsilon}^{V}\cap\mathcal{G}^{U,V}_{\varepsilon}\Big{)}\\\
=\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{\\{a<H^{U}_{\mathsf{S}}\wedge
H^{V}_{\mathsf{S}}\wedge H^{U}_{\varepsilon}\wedge
H^{V}_{\varepsilon}\\}}\cdot\mathbb{P}_{F^{U}(a)}\big{(}\mathcal{E}_{\varepsilon}^{\widetilde{U}}\big{)}\cdot\mathbb{P}_{F^{V}(a)}\big{(}\mathcal{E}_{\varepsilon}^{\widetilde{V}}\big{)}}\right],$
(3.14)

where $\mathbb{P}_{\ell}$ describes the law of a Brownian excursion with
duration $\ell>0$, and conditionally on $F^{U}(a)$ and $F^{V}(a)$,
$\widetilde{U},\widetilde{V}$ are independent and uniform in $(0,F^{U}(a))$
and $(0,F^{V}(a))$ respectively. By Brownian scaling, for $\ell>0$ we have

$\mathbb{P}_{\ell}\big{(}\mathcal{E}_{\varepsilon}^{\widetilde{U}}\big{)}=\mathbb{P}\big{(}\mathcal{E}_{\varepsilon/\ell}^{U^{\prime}}\big{)}\quad\text{and}\quad\mathbb{P}_{\ell}\big{(}\mathcal{E}_{\varepsilon}^{\widetilde{V}}\big{)}=\mathbb{P}\big{(}\mathcal{E}_{\varepsilon/\ell}^{V^{\prime}}\big{)},$

with $U^{\prime},V^{\prime}$ uniform in $(0,1)$. Equation (3.14) now boils
down to

$\mathbb{P}\Big{(}\mathcal{E}_{\varepsilon}^{U}\cap\mathcal{E}_{\varepsilon}^{V}\cap\mathcal{G}^{U,V}_{\varepsilon}\Big{)}=\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{\\{a<H^{U}_{\mathsf{S}}\wedge
H^{V}_{\mathsf{S}}\wedge H^{U}_{\varepsilon}\wedge
H^{V}_{\varepsilon}\\}}\cdot\mathbb{P}\mathopen{}\mathclose{{}\left(\mathcal{E}_{\varepsilon/F^{U}(a)}^{U^{\prime}}\,\middle|\,F^{U}(a)}\right)\cdot\mathbb{P}\mathopen{}\mathclose{{}\left(\mathcal{E}_{\varepsilon/F^{V}(a)}^{V^{\prime}}\,\middle|\,F^{V}(a)}\right)}\right].$
(3.15)

We now take $\varepsilon\to 0$. We claim that for some constant $c_{2}>0$,

$\mathbb{P}\Big{(}\mathcal{E}_{\varepsilon}^{U}\cap\mathcal{E}_{\varepsilon}^{V}\cap\mathcal{G}^{U,V}_{\varepsilon}\Big{)}\underset{\varepsilon\to
0}{\sim}c_{2}\,\varepsilon^{2\lambda_{\ast}(p)}\cdot\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{\\{a<H^{U}_{\mathsf{S}}\wedge
H^{V}_{\mathsf{S}}\\}}F^{U}(a)^{-\lambda_{\ast}(p)}F^{V}(a)^{-\lambda_{\ast}(p)}}\right].$
(3.16)

Indeed, from (3.8) in 3.1, we know that there exists a constant $c>0$ such
that
$\mathbb{P}\big{(}\mathcal{E}_{\varepsilon/F^{U}(a)}^{U^{\prime}}\big{|}F^{U}(a)\big{)}\underset{\varepsilon\to
0}{\sim}c\cdot(\varepsilon/F^{U}(a))^{\lambda_{\ast}(p)}$ and likewise
$\mathbb{P}\big{(}\mathcal{E}_{\varepsilon/F^{V}(a)}^{V^{\prime}}\big{|}F^{V}(a)\big{)}\underset{\varepsilon\to
0}{\sim}c\cdot(\varepsilon/F^{V}(a))^{\lambda_{\ast}(p)}$. The result then
follows from (3.15) provided we can apply dominated convergence. We now
justify that we can apply it.

First of all, recall from (3.7) that we have, for all $\varepsilon>0$, the
upper-bounds

$\mathbb{P}\big{(}\mathcal{E}_{\varepsilon/F^{U}(a)}^{U^{\prime}}\big{|}F^{U}(a)\big{)}\leq(\varepsilon/F^{U}(a))^{\lambda_{\ast}(p)}\quad\text{and}\quad\mathbb{P}\big{(}\mathcal{E}_{\varepsilon/F^{V}(a)}^{V^{\prime}}\big{|}F^{V}(a)\big{)}\leq(\varepsilon/F^{V}(a))^{\lambda_{\ast}(p)}.$

The domination will therefore follow if we prove that

$\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{\\{a<H^{U}_{\mathsf{S}}\wedge
H^{V}_{\mathsf{S}}\\}}F^{U}(a)^{-\lambda_{\ast}(p)}F^{V}(a)^{-\lambda_{\ast}(p)}}\right]<\infty.$
(3.17)

To do so, we argue conditionally on $F^{U}$, by first noting that one can
construct $F^{V}(a)$ from $F^{U}$ as follows. Recall that $a$ corresponds to
the branching height separating $U$ and $V$, hence $F^{V}(a)$ is equal to the
length of the interval not containing $U$ split by the jump of $F^{U}$ at
height $a$, that is $F^{V}(a)=-\Delta F^{U}(a)$ (recall Figure 6, p. 6). Now
observe that given some fixed jump time $h$ of $F^{U}$, the probability that
the branching height $a$ is equal to $h$ is given by the probability that $V$
belongs to the interval corresponding to the fragment $-\Delta F^{U}(h)$. In
other words, conditionally on $F^{U}$, using the independence of $V$ and $U$,
one can build $F^{V}(a)$ by selecting the jump $-\Delta F^{U}(h)$ of $F^{U}$
at time $h$ with probability $-\Delta F^{U}(h)$. By removing the indicator and
conditioning (3.17) on $F^{U}$, one therefore gets

$\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{a<H_{\mathsf{S}}^{U}\wedge
H_{\mathsf{S}}^{V}}(F^{U}(a)F^{V}(a))^{-\lambda_{\ast}(p)}}\right]\\\
\leq\mathbb{E}\mathopen{}\mathclose{{}\left[\sum_{0<h<h^{U}}(F^{U}(h))^{-\lambda_{\ast}(p)}(-\Delta
F^{U}(h))^{1-\lambda_{\ast}(p)}}\right].$

Using the Lamperti representation from 2.3, and noting that $-\Delta
F^{U}(h)=\mathrm{e}^{-\xi_{b^{-}}}(1-\mathrm{e}^{-\Delta\xi_{b}})$ with
$b=\rho(h)$, this becomes

$\displaystyle\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{a<H_{\mathsf{S}}^{U}\wedge
H_{\mathsf{S}}^{V}}(F^{U}(a)F^{V}(a))^{-\lambda_{\ast}(p)}}\right]$
$\displaystyle\leq\mathbb{E}\mathopen{}\mathclose{{}\left[\sum_{b>0}\mathrm{e}^{\lambda_{\ast}(p)\xi_{b}}\mathrm{e}^{-(1-\lambda_{\ast}(p))\xi_{b^{-}}}(1-\mathrm{e}^{-\Delta\xi_{b}})^{1-\lambda_{\ast}(p)}}\right]$
$\displaystyle=\mathbb{E}\mathopen{}\mathclose{{}\left[\sum_{b>0}\mathrm{e}^{-(1-2\lambda_{\ast}(p))\xi_{b^{-}}}\mathrm{e}^{\lambda_{\ast}(p)\Delta\xi_{b}}(1-\mathrm{e}^{-\Delta\xi_{b}})^{1-\lambda_{\ast}(p)}}\right].$

Then an application of the compensation formula for $\xi$ (see e.g. [Kyp14,
Theorem 4.4]) provides

$\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{a<H_{\mathsf{S}}^{U}\wedge
H_{\mathsf{S}}^{V}}(F^{U}(a)F^{V}(a))^{-\lambda_{\ast}(p)}}\right]\\\
\leq\mathbb{E}\mathopen{}\mathclose{{}\left[\int_{0}^{\infty}\mathrm{e}^{-(1-2\lambda_{\ast}(p))\xi_{b}}\mathrm{d}b}\right]\cdot\int_{0}^{\infty}\Lambda(\mathrm{d}x)\mathrm{e}^{\lambda_{\ast}(p)x}(1-\mathrm{e}^{-x})^{1-\lambda_{\ast}(p)}.$

On the one hand, since $\lambda_{\ast}(p)<1/2$, it is clear from the
expression of $\Lambda$ in 2.3 that the second integral is finite. On the
other hand, the first expectation is simply

$\mathbb{E}\mathopen{}\mathclose{{}\left[\int_{0}^{\infty}\mathrm{e}^{-(1-2\lambda_{\ast}(p))\xi_{b}}\mathrm{d}b}\right]=\int_{0}^{\infty}\mathrm{e}^{-b\Phi(1-2\lambda_{\ast}(p))}\mathrm{d}b.$

As $\lambda_{\ast}(p)<1/2$, the observation that
$\Phi(1-2\lambda_{\ast}(p))>0$ concludes the proof of (3.17). The domination
is thus established, which proves (3.16).

3.4 finally follows from the two asymptotics (3.13) and (3.16). ∎

##  4 Lower bound for sequences sampled from the Brownian separable permutons

The main goal of this section is to prove the lower bound in 1.1. As already
pointed out in Remark 1.2, $\alpha_{*}(p)>1/2$ for all $p\in(0,1)$ (indeed,
$\alpha_{*}(0^{+})=1/2$ and $\alpha_{*}(1^{-})=1$, and $\alpha_{*}(p)$ is
strictly increasing in $p\in(0,1)$). Hence, it is enough to prove the lower
bound in the second item in the theorem statement. This is done in the
following proposition.

######  Proposition 4.1.

Fix $p\in(0,1)$ and let $\alpha_{*}(p)=1-\lambda_{*}(p)$ be as in Remark 1.2.
Let $\sigma_{n}$ be a random permutation of size $n\in\mathbb{N}$ sampled from
the Brownian separable permuton $\bm{\mu}_{p}$. Then for all
$\alpha<\alpha_{*}(p)$, the following convergence in probability holds

$\frac{\operatorname{LIS}(\sigma_{n})}{n^{\alpha}}\to\infty.$ (4.1)

###### Proof.

Fix $n\in\mathbb{N}$ and set $\varepsilon=1/n$. Let $(U_{i})_{i\leq n}$ be a
sequence of i.i.d. uniform random variables in $(0,1)$, independent of all the
other random quantities, and recall from Section 2.2 that
$\sigma_{n}=\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U_{i})_{i\leq n})$.
Recall also the event $\mathcal{E}_{\varepsilon}^{U}$ from (3.6), and
introduce
$S_{n}:=\sum_{i=1}^{n}\mathds{1}_{\mathcal{E}_{\varepsilon}^{U_{i}}}$. Thanks
to 3.1, there exist two constants $c,C>0$ such that, for $n$ large enough,

$\mathbb{E}[S_{n}]=\sum_{i=1}^{n}\mathbb{P}(\mathcal{E}_{\varepsilon}^{U_{i}})\in(c\cdot
n^{\alpha_{*}(p)},C\cdot n^{\alpha_{*}(p)}),$ (4.2)

where we used that $\varepsilon=1/n$ and $\alpha_{*}(p)=1-\lambda_{\ast}(p)$.
Moreover, from 3.4, if $U$ and $V$ are independent uniform random variables in
$(0,1)$ also independent of all the other random quantities, there exists
another constant $c>0$ such that, for $\varepsilon=1/n$ small enough,

$\mathbb{P}\bigg{(}\mathcal{E}_{\varepsilon}^{U}\cap\mathcal{E}_{\varepsilon}^{V}\bigg{)}\leq
c\cdot\varepsilon^{2\lambda_{\ast}(p)}=c\cdot n^{2\alpha_{*}(p)-2}.$ (4.3)

Using (4.2) and (4.3) we deduce that for $n$ large enough,

$\mathbb{E}[S_{n}^{2}]=\sum_{i,j=1}^{n}\mathbb{P}(\mathcal{E}_{\varepsilon}^{U_{i}}\cap\mathcal{E}_{\varepsilon}^{U_{j}})\leq
c\cdot n^{2\alpha_{*}(p)},$ (4.4)

for some (other) constant $c>0$. The Paley–Zygmund inequality with the bounds
in (4.2) and (4.4) implies that there exist two (other) constants $c,q>0$ such
that for $n$ large enough,

$\mathbb{P}(S_{n}\geq c\cdot n^{\alpha_{*}(p)})\geq q.$ (4.5)

Now, recalling that
$S_{n}=\sum_{i=1}^{n}\mathds{1}_{\mathcal{E}_{\varepsilon}^{U_{i}}}$, denote
by $\\{U^{*}_{\ell},\ell\in[S_{n}]\\}$ the $S_{n}$ random variables among
$\\{U_{i},i\leq n\\}$ such that $\mathcal{E}_{\varepsilon}^{U^{*}_{\ell}}$
occurs. We now want to extract a large subset
$\\{U^{*}_{\ell},\ell\in\Lambda\\}$ of $\\{U^{*}_{\ell},\ell\in[S_{n}]\\}$
such that the corresponding intervals
$\\{I^{U^{*}_{\ell}}_{\varepsilon},\ell\in\Lambda\\}$ are disjoint (recall
that $I^{t}_{\varepsilon}:=I^{t}(H^{t}_{\varepsilon})$ denotes the largest
interval containing $t$ of size smaller than $\varepsilon$ in the
fragmentation process). The reason to be interested in such a large subset
resides in the following result.

######  Lemma 4.2.

Almost surely, if $\\{I^{U^{*}_{\ell}}_{\varepsilon},\ell\in\Lambda\\}$ are
disjoint, then the permutation
$\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U^{*}_{\ell})_{\ell\in\Lambda})$
is increasing.

###### Proof of 4.2.

Assume that $\\{I^{U^{*}_{\ell}}_{\varepsilon},\ell\in\Lambda\\}$ are disjoint
and recall that for all $\ell$, the variable $U^{*}_{\ell}$ is chosen so that
$\mathcal{E}^{U^{*}_{\ell}}_{\varepsilon}$ occurs. By definition of
$\mathcal{E}^{U}_{\varepsilon}$ in (3.6), if $\mathcal{E}^{U}_{\varepsilon}$
occurs then the interval $I^{U}_{\varepsilon}$ containing $U$ is not discarded
by the selection rule $\mathsf{S}$. Now suppose for a contradiction that there
exist two variables $U^{*}_{\ell_{1}}$ and $U^{*}_{\ell_{2}}$, with
$U^{*}_{\ell_{1}}<U^{*}_{\ell_{2}}$ and $\ell_{1},\ell_{2}\in\Lambda$, such
that the two corresponding values in
$\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U^{*}_{\ell})_{\ell\in\Lambda})$
form an inversion. Since $I^{U^{*}_{\ell_{1}}}_{\varepsilon}$ and
$I^{U^{*}_{\ell_{2}}}_{\varepsilon}$ are disjoint, there must exist (by 2.1) a
local minimum of $\mathfrak{e}$ at some height $h=\mathfrak{e}(t)$ which
separates $U^{*}_{\ell_{1}}$ and $U^{*}_{\ell_{2}}$, in particular $t\notin
I^{U^{*}_{\ell_{1}}}_{\varepsilon}\cup I^{U^{*}_{\ell_{2}}}_{\varepsilon}$,
$F^{U^{*}_{\ell_{1}}}(h^{-})\geq\varepsilon$ and
$F^{U^{*}_{\ell_{2}}}(h^{-})\geq\varepsilon$. See Figure 7. Moreover, the sign
corresponding to such a local minimum must be a $\ominus$ (since we assumed
that the two elements corresponding to $U^{*}_{\ell_{1}}$ and
$U^{*}_{\ell_{2}}$ in
$\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U^{*}_{\ell})_{\ell\in\Lambda})$
form an inversion). We deduce that either $U^{*}_{\ell_{1}}$ or
$U^{*}_{\ell_{2}}$ must be discarded by $\mathsf{S}$ at height $h$. Since
$F^{U^{*}_{\ell_{1}}}(h^{-})\geq\varepsilon$ and
$F^{U^{*}_{\ell_{2}}}(h^{-})\geq\varepsilon$, this contradicts the fact that
$\mathcal{E}^{U^{*}_{\ell_{1}}}_{\varepsilon}$ and
$\mathcal{E}^{U^{*}_{\ell_{2}}}_{\varepsilon}$ occur. ∎

Figure 7:  An illustration explaining the proof of 4.2.

In order to guarantee that the size of $\Lambda$ (and hence the size of the
increasing permutation
$\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U^{*}_{\ell})_{\ell\in\Lambda})$)
is large, we also need the following estimate.

######  Lemma 4.3.

Let $\varepsilon=1/n$ and fix $\zeta>0$. There exist two constants
$c_{1},c_{2}>0$ (which may depend on $\zeta$ but not on $n$) such that

$\mathbb{P}\mathopen{}\mathclose{{}\left(\forall
i\in[n],\;\\#\\{j\in[n],\,U_{j}\in
I^{U_{i}}_{\varepsilon}\\}<n^{\zeta}}\right)\geq
1-c_{1}n\cdot\exp(-c_{2}n^{\zeta}),\qquad\text{for all }n\geq 1.$

###### Proof of 4.3.

This is a standard binomial concentration argument. Let $\varepsilon=1/n$ and
fix $\zeta>0$. We recall that the number of uniform variables among
$(U_{i})_{i\leq n}$ which fall in some prescribed interval $A$ follows a
binomial distribution $\text{Bin}(n,|A|)$ with success probability $|A|$. Note
that for all $n\geq 1$,

$\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left(\forall
i\in[n],\,\\#\\{j\in[n],\,U_{j}\in
I^{U_{i}}_{\varepsilon}\\}<n^{\zeta}}\right)$ $\displaystyle\geq
1-\sum_{i=1}^{n}\mathbb{P}\big{(}\\#\\{j\in[n]\setminus\\{i\\},\,U_{j}\in
I^{U_{i}}_{\varepsilon}\\}\geq n^{\zeta}-1\big{)}$ $\displaystyle\geq
1-\sum_{i=1}^{n}\mathbb{P}(\text{Bin}(n-1,\varepsilon)\geq n^{\zeta}-1),$

where in the last inequality we used that by definition
$|I^{U_{i}}_{\varepsilon}|=F^{U_{i}}(H_{\varepsilon}^{U_{i}})\leq\varepsilon$.
Now recalling that $\varepsilon=1/n$, we get by Chernov’s bound that

$\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left(\forall
i\in[n],\,\\#\\{j\in[n],\,U_{j}\in
I^{U_{i}}_{\varepsilon}\\}<n^{\zeta}}\right)$ $\displaystyle\geq
1-c_{1}n\cdot\min_{\gamma>0}\\{\exp(-\gamma
n^{\zeta})\mathbb{E}[\exp(\gamma\text{Bin}(n-1,1/n))]\\}$
$\displaystyle=1-c_{1}n\cdot\min_{\gamma>0}\\{\exp(-\gamma
n^{\zeta})(1-1/n+\exp(\gamma)/n)^{n-1}\\}$ $\displaystyle\geq
1-c_{1}n\cdot\exp(-c_{2}n^{\zeta}),$ (4.6)

where $c_{1},c_{2}>0$ are two constants. ∎

Note that on the event $\mathopen{}\mathclose{{}\left\\{S_{n}\geq c\cdot
n^{\alpha_{*}(p)}}\right\\}\cap\mathopen{}\mathclose{{}\left\\{\forall
i\in[n],\;\\#\\{j\in[n],\,U_{j}\in
I^{U_{i}}_{\varepsilon}\\}<n^{\zeta}}\right\\}$, we can extract a subset
$\\{U^{*}_{\ell},\ell\in\Lambda\\}$ of $\\{U^{*}_{\ell},\ell\in[S_{n}]\\}$
such that the corresponding intervals
$\\{I^{U^{*}_{\ell}}_{\varepsilon},\ell\in\Lambda\\}$ are disjoint and the
size of $\Lambda$ is large, in the sense that $\\#\Lambda\geq c\cdot
n^{\alpha_{*}(p)-\zeta}$. Hence, on this event, thanks to 4.2, we have that
$\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U^{*}_{\ell})_{\ell\in\Lambda})$
is an increasing subsequence in
$\sigma_{n}=\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U_{i})_{i\leq n})$
of size at least $c\cdot n^{\alpha_{*}(p)-\zeta}$.

Using (4.5) and 4.3, we deduce that for all $\zeta>0$ there exist two (other)
constants $c,q>0$ (which may depend on $\zeta$) such that,

$\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma_{n})\geq
c\cdot n^{\alpha_{*}(p)-\zeta}}\right)\geq q,\qquad\text{for all }n\geq 1.$
(4.7)

Note that this estimate holds for all $n\geq 1$ since we are allowed to choose
a (possibly smaller) constant $c>0$.

The rest of the proof is devoted to upgrading (4.7) by proving that for all
$\zeta>0$ there exists (another) constant $c>0$ (which may depend on $\zeta$)
such that

$\lim_{n\to\infty}\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma_{n})\geq
c\cdot n^{\alpha_{*}(p)-\zeta}}\right)=1.$ (4.8)

To do this, we use a zero-one law type argument. Recall the signed excursion
$(\mathfrak{e},\mathfrak{s},p)$ and the definition of the tagged fragment from
2.3. Given a branching height $h>0$, recall that $\mathfrak{s}(h)$ is the
corresponding sign. For $\delta>0$, let

$H=H(\delta):=\inf\mathopen{}\mathclose{{}\left\\{h>0\,\middle|\;\mathfrak{s}(h)=\oplus,\,\,\min\\{F^{U}(h^{-})-F^{U}(h),F^{U}(h)\\}\geq\delta,\,\,F^{U}(h)>1/2}\right\\},$
(4.9)

with the convention that $\inf\emptyset=\infty$. We claim the following.

######  Lemma 4.4.

For every $\varepsilon^{\prime}>0$, there exists $\delta>0$ such that
$\mathbb{P}(H<\infty)\geq 1-\varepsilon^{\prime}$.

###### Proof of 4.4.

Fix $\varepsilon^{\prime}>0$. It suffices to show that a.s. there exists a
random $\delta>0$ such that $H(\delta)<\infty$. Indeed, by the continuity of
the probability for increasing families of events, this implies that there is
some deterministic $\delta$ such that $\mathbb{P}(H(\delta)<\infty)\geq
1-\varepsilon^{\prime}$.

Recall that from 2.3 we have that $F^{[U]}(h)=\exp(-\xi_{s})$ with
$s=\rho(h)$. Since $\xi$ is a subordinator with Levy measure
$\Lambda(0,\infty)=\infty$, then $F^{U}(h)$ does not immediately jump below
$1/2$ (by right-continuity of $F^{U}(h)$), and it has infinitely many downward
jumps in every non-trivial interval of times (because
$\Lambda(0,\infty)=\infty$; see e.g. [Ber96, Section I.5]). Hence there are
infinitely many $h>0$ such that $\min\\{F^{U}(h^{-})-F^{U}(h),F^{U}(h)\\}>0$
and $F^{U}(h)>1/2$. Since the signs $\mathfrak{s}$ at different branching
heights are i.i.d., a.s. there exists $h>0$ satisfying the conditions of the
previous sentence such that $\mathfrak{s}(h)=\oplus$. We then take
$\delta:=\min\\{F^{U}(h^{-})-F^{U}(h),F^{U}(h)\\}$ for the latter choice of
$h$. ∎

We now fix $\varepsilon^{\prime}>0$ and take $\delta>0$ so that
$\mathbb{P}(H<\infty)\geq 1-\varepsilon^{\prime}$. When $H<\infty$, by the
definition of $H$ in (4.9), the sign of the branching height $H$ is
$\mathfrak{s}(H)=\oplus$ and $H$ splits $I^{U}(H)$ into the two intervals $L$
and $R$ with
$\min\\{|L|,|R|\\}=\min\\{F^{U}(H^{-})-F^{U}(H),F^{U}(H)\\}\geq\delta$, and
none of them is discarded by the selection rule $\mathsf{S}$ (recall how the
selection rule $\mathsf{S}$ works from (1.6)). When $H=\infty$, we set
$L=R=\emptyset$. With the convention that
$\operatorname{Perm}(\mathfrak{e},\mathfrak{s},\emptyset)$ is the empty
permutation, we set

$\sigma^{L}_{n}:=\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U_{i})_{i\leq
n}\cap
L)\qquad\text{and}\qquad\sigma^{R}_{n}:=\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U_{i})_{i\leq
n}\cap R),$

and observe that $|\sigma^{L}_{n}|=\\#\big{(}(U_{i})_{i\leq n}\cap L\big{)}$
and $|\sigma^{R}_{n}|=\\#\big{(}(U_{i})_{i\leq n}\cap R\big{)}$. We have the
following bound on the size of the two permutations.

######  Lemma 4.5.

For all $\delta>0$, there exists two constants $c_{1},c_{2}>0$ (which may
depend on $\delta$ but not on $n$) such that

$\mathbb{P}\mathopen{}\mathclose{{}\left(\min\\{|\sigma^{L}_{n}|,|\sigma^{R}_{n}|\\}\geq\delta
n/3\,\middle|\,H<\infty}\right)\geq 1-c_{1}\exp(-c_{2}n),\qquad\text{for all
}n\geq 1.$

###### Proof of 4.5.

The proof uses standard binomial concentration arguments. Fix $\delta>0$. We
have that

$\mathbb{P}\mathopen{}\mathclose{{}\left(\min\\{|\sigma^{L}_{n}|,|\sigma^{R}_{n}|\\}\geq\delta
n/3\,\middle|\,H<\infty}\right)=1-\mathbb{P}\mathopen{}\mathclose{{}\left(\min\\{|\sigma^{L}_{n}|,|\sigma^{R}_{n}|\\}<\delta
n/3\,\middle|\,H<\infty}\right)\\\ \geq
1-\mathbb{P}\mathopen{}\mathclose{{}\left(|\sigma^{L}_{n}|<\delta
n/3\,\middle|\,H<\infty}\right)-\mathbb{P}\mathopen{}\mathclose{{}\left(|\sigma^{R}_{n}|<\delta
n/3\,\middle|\,H<\infty}\right)\geq
1-2\mathbb{P}\mathopen{}\mathclose{{}\left(\text{Bin}(n,\delta)<\delta
n/3}\right),$

where the first inequality is a union bound, and the last inequality comes
from the fact that $\min\\{|L|,|R|\\}\geq\delta$ when $H<\infty$. Standard
binomial concentration bounds (as in (4)) then provide the existence of two
constants $c_{1},c_{2}>0$ such that

$\mathbb{P}\mathopen{}\mathclose{{}\left(\min\\{|\sigma^{L}_{n}|,|\sigma^{R}_{n}|\\}\geq\delta
n/3\,\middle|\,H<\infty}\right)\geq 1-c_{1}\exp(-c_{2}n),\quad\text{for all
}n\geq 1,$

which is our claim. ∎

We now conclude the proof of 4.1. By standard self-similarity properties of
the Brownian excursion $\mathfrak{e}$, under the conditional law given
$(|L|,|R|,|\sigma^{L}_{n}|,|\sigma^{R}_{n}|)$, the permutations
$\sigma^{L}_{n}$ and $\sigma^{R}_{n}$ have the same law as two independent
copies of $\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U_{i})_{i\leq n})$
but of size $|\sigma^{L}_{n}|$ and $|\sigma^{R}_{n}|$ and defined in terms of
two independent excursions of duration $|L|$ and $|R|$, respectively. Taking
$c>0$ as in (4.7), and setting

$G:=\\{H<\infty,\,\min\\{|\sigma^{L}_{n}|,|\sigma^{R}_{n}|\\}\geq\delta
n/3\\},$

we get that

$\displaystyle\mathbb{P}\mathopen{}\mathclose{{}\left(\\{\operatorname{LIS}(\sigma^{L}_{n})\geq
c(\delta
n/3)^{\alpha_{*}(p)-\zeta}\\}\cup\\{\operatorname{LIS}(\sigma^{R}_{n})\geq
c(\delta n/3)^{\alpha_{*}(p)-\zeta}\\}}\right)$ (4.10)
$\displaystyle=1-\mathbb{E}\mathopen{}\mathclose{{}\left[\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma^{L}_{n})<c(\delta
n/3)^{\alpha_{*}(p)-\zeta}\,\middle|\,|L|,|\sigma^{L}_{n}|}\right)\cdot\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma^{R}_{n})<c(\delta
n/3)^{\alpha_{*}(p)-\zeta}\,\middle|\,|R|,|\sigma^{R}_{n}|}\right)}\right]$
$\displaystyle\geq
1-\mathbb{E}\mathopen{}\mathclose{{}\left[\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma^{L}_{n})<c|\sigma^{L}_{n}|^{\alpha_{*}(p)-\zeta}\,\middle|\,|L|,|\sigma^{L}_{n}|}\right)\cdot\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma^{R}_{n})<c|\sigma^{R}_{n}|^{\alpha_{*}(p)-\zeta}\,\middle|\,|R|,|\sigma^{R}_{n}|}\right)\cdot\mathds{1}_{G}}\right]-\mathbb{P}(G^{c}),$

where in the last inequality we used that on the event $G$ we have that
$\min\\{|\sigma^{L}_{n}|,|\sigma^{R}_{n}|\\}\geq\delta n/3$. Now, observe that
by Brownian scaling,

$\mathopen{}\mathclose{{}\left(\sigma_{n}^{L}\,\middle|\,|L|,|\sigma^{L}_{n}|}\right)\stackrel{{\scriptstyle
d}}{{=}}\mathopen{}\mathclose{{}\left(\operatorname{Perm}\mathopen{}\mathclose{{}\left(\mathfrak{e},\mathfrak{s},(\overline{U}_{i})_{i\leq|\sigma^{L}_{n}|}}\right)\,\middle|\,|\sigma^{L}_{n}|}\right),$

where $(\overline{U}_{i})_{i}$ is a new sequence of i.i.d. uniform random
variables in $(0,1)$, independent of all other quantities. Recalling that
$\sigma_{n}=\operatorname{Perm}(\mathfrak{e},\mathfrak{s},(U_{i})_{i\leq n})$,
we get that almost surely, for all $n\geq 1$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma^{L}_{n})<c\cdot|\sigma^{L}_{n}|^{\alpha_{*}(p)-\zeta}\,\middle|\,|L|,|\sigma^{L}_{n}|}\right)\cdot\mathds{1}_{G}=\mathbb{P}\Big{(}\operatorname{LIS}(\sigma_{|\sigma^{L}_{n}|})<c\cdot{|\sigma^{L}_{n}|}^{\alpha_{*}(p)-\zeta}\,\Big{|}\,|\sigma^{L}_{n}|\Big{)}\cdot\mathds{1}_{G}\leq
1-q,$

where the last inequality follows from the bound in (4.7) (recall that we
chose the same constant $c>0$ as in (4.7)). Noting that the same argument
holds with $R$ instead of $L$, we conclude from (4.10) that, for all $n\geq
1$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(\\{\operatorname{LIS}(\sigma^{L}_{n})\geq
c\cdot(\delta
n/3)^{\alpha_{*}(p)-\zeta}\\}\cup\\{\operatorname{LIS}(\sigma^{R}_{n})\geq
c\cdot(\delta n/3)^{\alpha_{*}(p)-\zeta}\\}}\right)\geq
1-(1-q)^{2}-\mathbb{P}(G^{c}).$

Claims 4.4 and 4.5 imply that, for each large enough $n$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(\\{\operatorname{LIS}(\sigma^{L}_{n})\geq
c\cdot(\delta
n/3)^{\alpha_{*}(p)-\zeta}\\}\cup\\{\operatorname{LIS}(\sigma^{R}_{n})\geq
c\cdot(\delta n/3)^{\alpha_{*}(p)-\zeta}\\}}\right)\geq
1-(1-q)^{2}-2\varepsilon^{\prime}.$

Since if $\operatorname{LIS}(\sigma^{L}_{n})\geq c(\delta
n/3)^{\alpha_{*}(p)-\zeta}$ or $\operatorname{LIS}(\sigma^{R}_{n})\geq
c(\delta n/3)^{\alpha_{*}(p)-\zeta}$ then $\operatorname{LIS}(\sigma_{n})\geq
c(\delta n/3)^{\alpha_{*}(p)-\zeta}$, the last estimate implies that for each
large enough $n$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma_{n})\geq
c\cdot(\delta/3)^{\alpha_{*}(p)-\zeta}\cdot
n^{\alpha_{*}(p)-\zeta}}\right)\geq 1-(1-q)^{2}-2\varepsilon^{\prime},$

where we recall that $\varepsilon^{\prime}$ and $\delta$ were fixed right
after the statement of 4.4. By possibly choosing a smaller constant $c$, we
deduce that for each $\varepsilon^{\prime}>0$ there exists a constant
$c(\varepsilon^{\prime})>0$ such that

$\mathbb{P}\mathopen{}\mathclose{{}\left(\operatorname{LIS}(\sigma_{n})\geq
c(\varepsilon^{\prime})\cdot n^{\alpha_{*}(p)-\zeta}}\right)\geq
1-(1-q)^{2}-2\varepsilon^{\prime},\qquad\text{for all }n\geq 1.$ (4.11)

Now, set

$q^{*}:=\sup\mathopen{}\mathclose{{}\left\\{r\in[0,1]\,\middle|\,\text{there
exists }c(r)>0\text{ s.t. }\mathbb{P}(\operatorname{LIS}(\sigma_{n})\geq
c(r)\cdot n^{\alpha_{*}(p)-\zeta})\geq r\text{ for all }n\geq 1}\right\\},$

and note that $q^{*}>0$ thanks to (4.7). The two bounds in (4.7) and (4.11)
and our definition of $q^{*}$ show that if $q<q^{*}$, then $1-(1-q)^{2}\leq
q^{*}$. Taking $q\to q^{*}$, we get $1-q^{*}\leq(1-q^{*})^{2}$. Noting that
the only strictly positive solution of the latter inequality is $q^{*}=1$, we
conclude the proof of (4.8).

Since (4.8) holds for any arbitrary $\zeta>0$, we deduce the convergence in
(4.1). ∎

##  5 Estimates for the upper bound

In this section we prove two fundamental estimates (see Propositions 5.4 and
5.5 below) that will be later used in Section 6 to upper bound the length of
the longest increasing subsequence in permutations sampled from the Brownian
separable permutons.

###  5.1 The two main estimates

Recall from Section 1.4.1 that $\mathcal{B}_{\ominus}$ and
$\mathcal{B}_{\oplus}$ stand for the collections of negative and positive
branching heights in the signed excursion $(\mathfrak{e},\mathfrak{s},p)$
respectively, i.e. the collection of heights corresponding to the local minima
of $\mathfrak{e}$ decorated by a $\ominus$–sign and a $\oplus$–sign
respectively. Moreover
$\mathcal{B}=\mathcal{B}_{\oplus}\cup\mathcal{B}_{\ominus}$. Recall also that
$I^{t}(h)$, $h\geq 0$, denotes the open interval which contains $t$ in the
interval fragmentation $\mathfrak{F}_{0}(h)$ introduced in (2.1). We set
$I^{t}(h^{-})$ to be equal to the interior of $\bigcap_{\ell<h}I^{t}(\ell)$.

Of particular importance will be the case of negative branching heights
$\mathcal{B}_{\ominus}$, for which we introduce the following additional
notation. Since $\mathfrak{e}$ has almost surely distinct local minima (2.1),
almost surely, for all $b\in\mathcal{B}_{\ominus}$, there is a unique time
$t_{b}\in[0,1]$ when $\mathfrak{e}$ has a local minimum with
$b=\mathfrak{e}(t_{b})$. We define

$(\ell_{b},r_{b}):=I^{t_{b}}(b^{-}),\qquad
L_{b}:=(\ell_{b},t_{b}),\qquad\text{and}\qquad R_{b}:=(t_{b},r_{b}),$ (5.1)

i.e. $L_{b}$ and $R_{b}$ are the two intervals in which the interval
$I^{t_{b}}(b^{-})$ is split at the branching height $b$. Finally, given
$t\in[0,1]$, we also denote by $\mathcal{B}^{t}_{\ominus}$ the collection of
negative branching heights $b\in\mathcal{B}_{\ominus}$ such that
$t\in(\ell_{b},r_{b})$. See Figure 8 for an illustration.

Figure 8:  A sketch for the notation introduced in Section 5.1.

We now introduce a particular type of sequences; the motivation will be
clarified right after their definition. Fix $p\in(0,1)$, i.e. fix the
parameter for the signs of the signed excursion
$(\mathfrak{e},\mathfrak{s},p)$. Conditioning on
$(\mathfrak{e},\mathfrak{s})$, let $\mathcal{D}$ (for _discarding rules_ , see
explanations below) be the set of sequences
$\eta=\\{\eta_{b}\\}_{b\in\mathcal{B}_{\ominus}}$, with
$\eta_{b}\in\\{L_{b},R_{b},\diamond\\}$, such that $\eta_{b}=\diamond$ if and
only if there exists $b^{\prime}\in\mathcal{B}_{\ominus}$ with $b^{\prime}<b$
such that $t_{b}\in\eta_{b^{\prime}}$.

Note that given $(\mathfrak{e},\mathfrak{s})$, we can think of
$\eta=\\{\eta_{b}\\}_{b\in\mathcal{B}_{\ominus}}$ as a deterministic
discarding rule, where each $\eta_{b}$ determines which side of the interval
$(\ell_{b},r_{b})$ we are going to discard (the case $\eta_{b}=\diamond$
corresponds to the case when the interval $(\ell_{b},r_{b})$ is contained in
an interval that was already discarded at some smaller negative branching
height).

We introduce some notation. Given $t\in[0,1]$ and
$b\in\mathcal{B}^{t}_{\ominus}$, we say that $\eta_{b}$ does not discard $t$
if $t\notin\eta_{b}$. We want to estimate the probability of the following
events defined for all $t\in(0,1)$ and $\varepsilon\in(0,1)$,

$E_{\varepsilon}^{t}=E_{\varepsilon}^{t}(\eta):=\mathopen{}\mathclose{{}\left\\{\eta_{b}\text{
does not discard }t\text{ for all }b\in\mathcal{B}^{t}_{\ominus}\text{ such
that }F^{t}(b)\geq\varepsilon}\right\\}.$ (5.2)

More precisely, we are interested in the case when $t$ is a uniform point $U$
in $(0,1)$ independent of all other random quantities. The ideas used in this
section to estimate the probability of the above event will then play a key
role in Section 6.

Recall the subordinator $\xi$ introduced in 2.3. In this section we use the
decomposition $\xi=\xi^{\oplus}+\xi^{\ominus}$, where $\xi^{\oplus}$ (resp.
$\xi^{\ominus}$) is the process determined by the jumps of $\xi$ corresponding
to the local minima of $\mathfrak{e}$ decorated by $\oplus$–signs (resp.
$\ominus$–signs). Then, arguing as in (3.2), the process $\xi^{\ominus}$ is a
Lévy process with intensity measure on $(0,+\infty)$

$\Lambda^{\ominus}(\mathrm{d}x):=(1-p)\Lambda(\mathrm{d}x)=\frac{2(1-p)\,\mathrm{e}^{x}\mathrm{d}x}{\sqrt{2\pi(\mathrm{e}^{x}-1)^{3}}}.$
(5.3)

Now recall from Remark 1.2 the definition of $\lambda^{*}(p)=1-\beta^{*}(p)$
as

$\lambda^{*}(p)=\sup_{\beta\in(0,\log(2)),\delta>0}\min\mathopen{}\mathclose{{}\left\\{\beta\delta\,,\,\sup_{\gamma<0}\\{\gamma\delta+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)\\}}\right\\},$
(5.4)

and note that for all $\gamma<0$ and all $r\in(1/2,1)$, by simple
calculations, the equation (1.4) satisfied by $\kappa^{*}_{\gamma,r}(p)$ can
be rephrased more conveniently as

$\Phi(-\kappa^{*}_{\gamma,r}(p))=-(1-\mathrm{e}^{\gamma})\Lambda^{\ominus}\big{(}-\log(r),-\log(1-r)\big{)},$
(5.5)

where we recall from Remark 2.4 that
$\Phi(q)=2\sqrt{2}\frac{\Gamma(q+1/2)}{\Gamma(q)}$. Note that the above
equation has a unique positive solution because as explained in Remark 2.4,
the function $\Phi(\cdot)$ is increasing, $\Phi(0)=0$,
$\lim_{q\to(-1/2)^{+}}\Phi(q)=-\infty$ and
$-(1-\mathrm{e}^{\gamma})\Lambda^{\ominus}\big{(}-\log(r),-\log(1-r)\big{)}<0$
for all $\gamma<0$ and all $r\in(1/2,1)$.

We are going to prove (after stating and proving two additional complementary
lemmas) the following upper bound for the probability of the event
$E_{\varepsilon}^{U}$ introduced in (5.2).

######  Proposition 5.1.

Fix $p\in(0,1)$. Let $\eta\in\mathcal{D}$ be a discarding rule chosen in a
$(\mathfrak{e},\mathfrak{s})$–measurable manner. Then,

$\mathbb{P}(E_{\varepsilon}^{U})\leq
2\,\varepsilon^{\lambda^{*}(p)},\quad\text{for all }\varepsilon\in(0,1).$

The following two results complement the bound obtained in the above
proposition.

######  Lemma 5.2.

For all $p\in(0,1)$, we have that $\lambda^{*}(p)>0$.

###### Proof of 5.2.

Fix $p\in(0,1)$. Recall the definition of $\lambda^{*}(p)$ from (5.4). We show
that there exist $\beta\in(0,\log(2))$ and $\delta>0$ such that
$\sup_{\gamma<0}\\{\gamma\delta+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)\\}>0$,
then the desired result follows. Fix any $\gamma_{0}<0$ and
$\beta_{0}\in(0,\log(2))$. Note that since
$\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)$ is defined as the only positive
solution to (5.5) with $r=\mathrm{e}^{-\beta}$, we have that
$\kappa^{*}_{\gamma_{0},\mathrm{e}^{-\beta_{0}}}(p)>0$. Therefore there always
exists $\delta>0$ small enough such that
$\gamma_{0}\delta+\kappa^{*}_{\gamma_{0},\mathrm{e}^{-\beta_{0}}}(p)>0$. This
concludes the proof. ∎

######  Lemma 5.3.

The supremum in (5.4) is attained, i.e. there exist
$\beta=\beta(p)\in(0,\log(2))$ and $\delta=\delta(p)>0$ such that

$\lambda^{*}(p)=\min\mathopen{}\mathclose{{}\left\\{\beta\delta\,,\,\sup_{\gamma<0}\\{\gamma\delta+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)\\}}\right\\}.$

###### Proof.

To see this, let

$\mu(\delta,\beta):=\min\mathopen{}\mathclose{{}\left\\{\beta\delta\,,\,\sup_{\gamma<0}\\{\gamma\delta+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)\\}}\right\\},\quad\delta>0,\;\beta\in(0,\log(2)),$

and $\delta_{n}>0,\beta_{n}\in(0,\log 2)$ define two sequences such that
$\mu(\delta_{n},\beta_{n})\to\lambda^{*}(p)$ as $n\to\infty$. Our argument is
to show that we can extract from $(\delta_{n},n\in\mathbb{N})$ and
$(\beta_{n},n\in\mathbb{N})$ converging subsequences with limits in
$(0,\infty)$ and $(0,\log(2))$ respectively (note that the extremities of the
intervals are excluded).

First of all,
$\mu(\delta_{n},\beta_{n})\leq\beta_{n}\delta_{n}\leq\delta_{n}\log(2)$, and
since $\mu(\delta_{n},\beta_{n})\to\lambda^{*}(p)>0$ (see 5.2), it must be the
case that $(\delta_{n},n\in\mathbb{N})$ is bounded away from $0$. Secondly, it
is fairly easy to see that $(\beta_{n},n\in\mathbb{N})$ is bounded away from
$\log(2)$. In fact, for all $n\in\mathbb{N}$,
$\mu(\delta_{n},\beta_{n})\leq\sup_{\gamma<0}\\{\gamma\delta_{n}+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta_{n}}}(p)\\}\leq\sup_{\gamma<0}\kappa^{*}_{\gamma,\mathrm{e}^{-\beta_{n}}}(p)$.
But note that for all $r\in(1/2,1)$,
$\sup_{\gamma<0}\kappa^{*}_{\gamma,r}(p)=\kappa^{*}_{\infty,r}(p)$, where
$\kappa^{*}_{\infty,r}(p)$ is the unique positive solution to

$\Phi(-\kappa^{*}_{\infty,r}(p))=-\Lambda^{\ominus}\big{(}-\log(r),-\log(1-r)\big{)}.$

It is clear that $\kappa^{*}_{\infty,r}(p)\to 0$ as $r\to 1/2$. Therefore,
$\beta_{n}\to\log(2)$ (up to extraction) would imply
$\mu(\delta_{n},\beta_{n})\leq\kappa^{*}_{\infty,\mathrm{e}^{-\beta_{n}}}(p)\to
0$ as $n\to\infty$. This contradicts $\lambda^{*}(p)>0$.

Next, we claim that $(\beta_{n},n\in\mathbb{N})$ is bounded away from $0$.
Suppose that this is not the case; without loss of generality we can assume
that $\beta_{n}\to 0$. Take $n$ large enough so that
$\mu(\delta_{n},\beta_{n})\geq\frac{\lambda^{*}(p)}{2}$. The bound
$\frac{\lambda^{*}(p)}{2}\leq\mu(\delta_{n},\beta_{n})\leq\beta_{n}\delta_{n}$
shows that $\delta_{n}\to\infty$. Then, for all $n$, we pick $\gamma_{n}<0$
such that,

$\gamma_{n}\delta_{n}+\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p)\geq\frac{1}{2}\sup_{\gamma<0}\\{\gamma\delta_{n}+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta_{n}}}(p)\\}.$
(5.6)

This is possible since
$\sup_{\gamma<0}\\{\gamma\delta_{n}+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta_{n}}}(p)\\}\geq\mu(\delta_{n},\beta_{n})\geq\frac{\lambda^{*}(p)}{2}>0$.
We first remark that, since
$\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p)\leq\frac{1}{2}$ (recall
that $\lim_{q\to(-1/2)^{+}}\Phi(q)=-\infty$),

$\gamma_{n}\delta_{n}\stackrel{{\scriptstyle\eqref{eq: def
gamma_n}}}{{\geq}}\frac{1}{2}\Big{(}\sup_{\gamma<0}\\{\gamma\delta_{n}+\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p)\\}-1\Big{)}\geq\frac{1}{2}\Big{(}\frac{\lambda^{*}(p)}{2}-1\Big{)},$
(5.7)

and hence $\gamma_{n}\to 0$ because $\gamma_{n}<0$, $\delta_{n}\to\infty$ and
$\frac{1}{2}\Big{(}\frac{\lambda^{*}(p)}{2}-1\Big{)}\geq-\frac{1}{2}$. Now by
definition of $\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p)$,

$\Phi(-\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p))=-(1-\mathrm{e}^{\gamma_{n}})\Lambda^{\ominus}\big{(}\beta_{n},-\log(1-\mathrm{e}^{-\beta_{n}})\big{)}.$

A simple integral estimate shows that, as $n\to\infty$,
$\Lambda^{\ominus}\big{(}\beta_{n},-\log(1-\mathrm{e}^{-\beta_{n}})\big{)}\sim
c/\sqrt{\beta_{n}}$ for some positive constant $c$, whence
$\Phi(-\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p))\sim
c\gamma_{n}/\sqrt{\beta_{n}}$ as $n\to\infty$. Note that by the inequality
$\frac{\lambda^{*}(p)}{2}\leq\mu(\delta_{n},\beta_{n})\leq\beta_{n}\delta_{n}$
and the fact that $\gamma_{n}<0$,

$\frac{\gamma_{n}}{\sqrt{\beta_{n}}}\geq\sqrt{\frac{2}{\lambda^{*}(p)}}\cdot\gamma_{n}\sqrt{\delta_{n}}\stackrel{{\scriptstyle\eqref{eq:
lb
gammadelta}}}{{\geq}}\frac{1}{2}\sqrt{\frac{2}{\lambda^{*}(p)}}\cdot\frac{\frac{\lambda^{*}(p)}{2}-1}{\sqrt{\delta_{n}}}.$

Since $\gamma_{n}<0$, this entails $\gamma_{n}/\sqrt{\beta_{n}}\to 0$ and
hence $\Phi(-\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p))\to 0$.
Therefore $\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p)\to 0$. But this
is a contradiction: indeed,

$\frac{\lambda^{*}(p)}{2}\leq\mu(\delta_{n},\beta_{n})\leq\sup_{\gamma<0}\\{\gamma\delta_{n}+\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p)\\}\stackrel{{\scriptstyle\eqref{eq:
def
gamma_n}}}{{\leq}}2\gamma_{n}\delta_{n}+2\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p)\leq
2\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p),$ (5.8)

so that we would have $\lambda^{*}(p)=0$.

Finally, we prove that $(\delta_{n},n\in\mathbb{N})$ is upper bounded using a
similar argument. We argue by contradiction, assuming that
$\delta_{n}\to\infty$ (this is possible up to extraction). We first use the
inequality
$\mu(\delta_{n},\beta_{n})\leq\sup_{\gamma<0}\\{\gamma\delta_{n}+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta_{n}}}(p)\\}$
for all $n\in\mathbb{N}$, and we consider $\gamma_{n}<0$ as in (5.6). Now the
same argument as in (5.7) shows that $\gamma_{n}\to 0$. Since we know from the
previous paragraph that $(\beta_{n},n\in\mathbb{N})$ is bounded away from $0$,
we deduce that, as $n\to\infty$,

$\Phi(-\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}(p))=-(1-\mathrm{e}^{\gamma_{n}})\Lambda^{\ominus}\big{(}\beta_{n},-\log(1-\mathrm{e}^{-\beta_{n}})\big{)}\longrightarrow
0.$

Therefore $\kappa^{*}_{\gamma_{n},\mathrm{e}^{-\beta_{n}}}\to 0$ and we
conclude as in (5.8) that this is impossible.

We have proved that $(\delta_{n},n\in\mathbb{N})$ is upper bounded and bounded
away from $0$, and that $(\beta_{n},n\in\mathbb{N})$ is bounded away both from
$\log(2)$ and $0$. We may now conclude the proof. Up to extraction, we can
assume that $(\delta_{n},n\in\mathbb{N})$ and $(\beta_{n},n\in\mathbb{N})$
converge to $\delta_{\infty}\in(0,\infty)$ and $\beta_{\infty}\in(0,\log(2))$
respectively. Taking a limit, we finally get
$\lambda^{*}(p)=\underset{n\to\infty}{\lim}\mu(\delta_{n},\beta_{n})=\mu(\delta_{\infty},\beta_{\infty})$,
which proves our statement. ∎

We now turn to the proof of 5.1. We highlight that the two main estimates used
in this proof will be also used in Section 6.

###### Proof of 5.1.

For a constant $r\in(1/2,1)$, we consider the sequence of branching heights
defined for all $m>0$ by

$\tau_{m}^{U}=\tau_{m}^{U}(r):=\text{$m$-th smallest
$b\in\mathcal{B}^{U}_{\ominus}$ such that
$\frac{\max\\{|L_{b}|,|R_{b}|\\}}{|L_{b}|+|R_{b}|}\leq r$}.$ (5.9)

The random variables $\tau_{m}^{U}$ are a.s. well defined for all
$m\in\mathbb{N}$, because we claim that there are infinitely many branching
heights $b\in\mathcal{B}^{U}_{\ominus}$ such that
$\max\\{|L_{b}|,|R_{b}|\\}\leq r(|L_{b}|+|R_{b}|)$. Indeed, we first note that
$\max\\{|L_{b}|,|R_{b}|\\}\leq r(|L_{b}|+|R_{b}|)$ if and only if
$\max\\{\mathrm{e}^{-\xi^{\ominus}_{s^{-}}}-\mathrm{e}^{-\xi^{\ominus}_{s}},\mathrm{e}^{-\xi^{\ominus}_{s}}\\}\leq
r\cdot\mathrm{e}^{-\xi^{\ominus}_{s^{-}}}$, where $s=\rho(b)$, and that this
is equivalent to $\Delta\xi^{\ominus}_{s}\in(-\log(r),-\log(1-r))$. Since the
number of jumps of the process $\xi^{\ominus}$ by time $t$ and with sizes in
$(-\log(r),-\log(1-r))$ forms a Poisson process with mean
$\Lambda^{\ominus}(-\log(r),-\log(1-r))\cdot t$ (see e.g. [Ber96, Section
I.5]), letting $t\to\infty$ we get the claim.

We also set for all $m>0$

$A^{U}_{m}=A^{U}_{m}(r):=\\{\eta_{b}\text{ does not discard }U\text{ for all
}b\in\mathcal{B}^{U}_{\ominus}\text{ such that }b\leq\tau^{U}_{m}\\},$ (5.10)

and we claim that for all $r\in(1/2,1)$, $m>0$ and $\varepsilon\in(0,1)$,

$E_{\varepsilon}^{U}\subseteq\mathopen{}\mathclose{{}\left(A^{U}_{m}\cap\mathopen{}\mathclose{{}\left\\{F^{U}(\tau_{m}^{U})\geq\varepsilon}\right\\}}\right)\cup\mathopen{}\mathclose{{}\left\\{F^{U}(\tau_{m}^{U})<\varepsilon}\right\\}.$
(5.11)

Indeed, if $E_{\varepsilon}^{U}$ occurs – i.e. $\eta_{b}$ does not discard $U$
for all $b\in\mathcal{B}^{U}_{\ominus}$ such that $F^{U}(b)\geq\varepsilon$ –
and $F^{U}(\tau_{m}^{U})\geq\varepsilon$, then $F^{U}(b)\geq\varepsilon$ for
all $b\in\mathcal{B}^{U}_{\ominus}$ such that $b\leq\tau_{m}^{U}$. Hence
$\eta_{b}$ must not discard $U$ for all for all
$b\in\mathcal{B}^{U}_{\ominus}$ such that $b\leq\tau_{m}^{U}$, which is the
event $A^{U}_{m}$.

As a consequence, for all $r\in(1/2,1)$, $m>0$ and $\varepsilon\in(0,1)$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(E_{\varepsilon}^{U}}\right)\leq\mathbb{P}\mathopen{}\mathclose{{}\left(A^{U}_{m}}\right)+\mathbb{P}\mathopen{}\mathclose{{}\left(F^{U}\big{(}\tau_{m}^{U}\big{)}<\varepsilon}\right).$
(5.12)

In the next two crucial propositions (whose proofs are postponed to Section
5.2), we upper-bound the two terms on the right-hand side of the last
equation. Later, we will choose some specific values for the constants
$r\in(1/2,1)$ and $m>0$ which will optimize our upper-bound.

######  Proposition 5.4.

For all $r\in(1/2,1)$, $m>0$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(A^{U}_{m}}\right)\leq r^{m}.$

######  Proposition 5.5.

For all $r\in(1/2,1)$, $m>0$ and $\varepsilon\in(0,1)$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(F^{U}\big{(}\tau^{U}_{m}\big{)}<\varepsilon}\right)\leq\inf_{\gamma<0}\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{-\gamma
m}\cdot\varepsilon^{\kappa^{*}_{\gamma,r}(p)}}\right\\},$

where $\kappa^{*}_{\gamma,r}(p)$ was defined in (5.5).

We now conclude the proof of 5.1. Combining the estimates in the last two
propositions with (5.12), we get that for all $r\in(1/2,1)$, $m>0$ and
$\varepsilon\in(0,1)$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(E_{\varepsilon}^{U}}\right)\leq
r^{m}+\inf_{\gamma<0}\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{-\gamma
m}\cdot\varepsilon^{\kappa^{*}_{\gamma,r}(p)}}\right\\}.$

Setting $r=\mathrm{e}^{-\beta}$ with $\beta\in(0,\log(2))$ and
$m=\delta\log(1/\varepsilon)$ with $\delta>0$, we deduce that for all
$\varepsilon\in(0,1)$

$\mathbb{P}\mathopen{}\mathclose{{}\left(E_{\varepsilon}^{U}}\right)\leq\varepsilon^{\beta\delta}+\inf_{\gamma<0}\mathopen{}\mathclose{{}\left\\{\varepsilon^{\gamma\delta+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)}}\right\\}\leq
2\,\varepsilon^{\min\\{\beta\delta\,,\,\sup_{\gamma<0}\\{\gamma\delta+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)\\}\\}}.$

In particular, for all $\varepsilon\in(0,1)$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(E_{\varepsilon}^{U}}\right)\leq
2\,\varepsilon^{\lambda^{*}(p)},$

where we recall from (5.4) that

$\lambda^{*}(p)=\sup_{\beta\in(0,\log(2)),\delta>0}\min\mathopen{}\mathclose{{}\left\\{\beta\delta\,,\,\sup_{\gamma<0}\\{\gamma\delta+\kappa^{*}_{\gamma,\mathrm{e}^{-\beta}}(p)\\}}\right\\}.$

This concludes the proof of 5.1. ∎

An immediate consequence of the last proof and Lemmas 5.2 and 5.3 is the
following result, which contains the key estimates for the results in Section
6.

######  Corollary 5.6.

Fix $p\in(0,1)$. Let $\eta\in\mathcal{D}$ be a discarding rule chosen in a
$(\mathfrak{e},\mathfrak{s})$–measurable manner and $U$ be a uniform random
variable in $(0,1)$ independent of all other random quantities. Recall the
definitions of $\tau^{U}_{m}$ and $A^{U}_{m}$ from (5.9) and (5.10).

There exist a choice of $r=r(p)\in(1/2,1)$ and $\delta=\delta(p)>0$ such that
for all $\varepsilon\in(0,1)$, setting $m=\delta\log(1/\varepsilon)$, we have
that

$\mathbb{P}\mathopen{}\mathclose{{}\left(A^{U}_{m}}\right)\leq
2\,\varepsilon^{\lambda^{*}(p)},$

and that

$\mathbb{P}\mathopen{}\mathclose{{}\left(F^{U}\big{(}\tau^{U}_{m}\big{)}<\varepsilon}\right)\leq
2\,\varepsilon^{\lambda^{*}(p)},$

where $\lambda^{*}(p)>0$ is defined as in Equation 5.4.

###  5.2 Proofs of the two main estimates

In this section we prove the two propositions that we left behind in the
previous section, i.e. Propositions 5.4 and 5.5. For convenience, we recall at
the beginning of each proof what is the statement that we need to prove.

###### Proof of 5.4.

Recall that $\eta\in\mathcal{D}$ is a discarding rule chosen in a
$(\mathfrak{e},\mathfrak{s})$–measurable manner. Also recall from (5.10) that
for all $m>0$,

$A^{U}_{m}=A^{U}_{m}(r):=\\{\eta_{b}\text{ does not discard }U\text{ for all
}b\in\mathcal{B}^{U}_{\ominus}\text{ such that }b\leq\tau^{U}_{m}\\},$ (5.13)

where $\tau_{m}^{U}=\tau_{m}^{U}(r)$ was defined in (5.9). We want to prove
that for all $r\in(1/2,1)$, $m>0$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(A^{U}_{m}}\right)\leq r^{m}.$ (5.14)

Setting

$B^{U}_{m}=B^{U}_{m}(r):=\\{\eta_{b}\text{ does not discard }U\text{ for all
}b\in\mathcal{B}^{U}_{\ominus}\text{ such that }b<\tau^{U}_{m}\\},$

(note that the inequality is strict here), we have that

$A^{U}_{m}=B^{U}_{m}\cap\mathopen{}\mathclose{{}\left\\{\eta_{\tau_{m}^{U}}\text{
does not discard }U}\right\\}.$ (5.15)

We consider the following filtration, defined for all $m>0$ by

$\mathcal{F}_{m}:=\sigma\mathopen{}\mathclose{{}\left(\mathfrak{e},\mathfrak{s},(I^{U}(h))_{h<\tau^{U}_{m+1}},(\tau^{U}_{s})_{s\leq
m+1}}\right).$

We emphasize that, importantly, the interval $I^{U}(h)$ at level
$h=\tau_{m+1}^{U}$ is not included in the definition of $\mathcal{F}_{m}$. Fix
$m>0$. Note that:

  * •

$B^{U}_{m}$ is $\mathcal{F}_{m-1}$–measurable.

  * •

$I^{U}((\tau^{U}_{m})^{-})$ is $\mathcal{F}_{m-1}$–measurable because by
definition it is equal to the interior of the decreasing intersection
$\bigcap_{h<\tau^{U}_{m}}I^{U}(h)$.

  * •

$L_{\tau_{m}^{U}}$ and $R_{\tau_{m}^{U}}$ are $\mathcal{F}_{m-1}$–measurable
because $\tau_{m}^{U}$ is $\mathcal{F}_{m-1}$–measurable and
$L_{\tau_{m}^{U}}$ and $R_{\tau_{m}^{U}}$ are a deterministic function of
$\tau_{m}^{U}$ and $\mathfrak{e}$.

  * •

$|I^{U}((\tau^{U}_{m})^{-})|=|L_{\tau_{m}^{U}}|+|R_{\tau_{m}^{U}}|$.

  * •

Conditioning on $\mathcal{F}_{m-1}$, $U$ is uniform in
$I^{U}((\tau^{U}_{m})^{-})$ because $I^{U}(h)$ at level $h=\tau_{m}^{U}$ is
not included in the definition of $\mathcal{F}_{m-1}$.

  * •

Conditioning on $\mathcal{F}_{m-1}$, the probability that $U$ falls in
$L_{\tau_{m}^{U}}$ (resp. $R_{\tau_{m}^{U}}$) is therefore
$\frac{|L_{\tau_{m}^{U}}|}{|L_{\tau_{m}^{U}}|+|R_{\tau_{m}^{U}}|}$ (resp.
$\frac{|R_{\tau_{m}^{U}}|}{|L_{\tau_{m}^{U}}|+|R_{\tau_{m}^{U}}|}$).

The above observations entail that, almost surely, for all $m>0$,

$\displaystyle\mathds{1}_{B^{U}_{m}}\,\mathbb{E}$
$\displaystyle\mathopen{}\mathclose{{}\left[\mathds{1}_{\\{\eta_{\tau_{m}^{U}}\text{
does not discard }U\\}}\middle|\mathcal{F}_{m-1}}\right]$
$\displaystyle=\mathds{1}_{B^{U}_{m}}\,\mathbb{P}\mathopen{}\mathclose{{}\left(U\text{
is not in the interval discarded by
}\eta_{\tau_{m}^{U}}\middle|\mathcal{F}_{m-1}}\right)$
$\displaystyle=\mathds{1}_{B^{U}_{m}}\,\mathopen{}\mathclose{{}\left(\frac{|L_{\tau_{m}^{U}}|}{|L_{\tau_{m}^{U}}|+|R_{\tau_{m}^{U}}|}\delta_{\\{\eta_{\tau_{m}^{U}}=R_{\tau_{m}^{U}}\\}}+\frac{|R_{\tau_{m}^{U}}|}{|L_{\tau_{m}^{U}}|+|R_{\tau_{m}^{U}}|}\delta_{\\{\eta_{\tau_{m}^{U}}=L_{\tau_{m}^{U}}\\}}}\right)$
$\displaystyle\leq\mathds{1}_{B^{U}_{m}}\,\frac{\max\\{|L_{\tau_{m}^{U}}|,|R_{\tau_{m}^{U}}\\}|}{|L_{\tau_{m}^{U}}|+|R_{\tau_{m}^{U}}|}\leq\mathds{1}_{B^{U}_{m}}\,r,$
(5.16)

where the last inequality follows by definition of $\tau_{m}^{U}$. Note also
that in the second equality of the above equation we used that if $\eta_{b}$
does not discard $U$ for all $b\in\mathcal{B}^{U}_{\ominus}$ such that
$b<\tau_{m}^{U}$ (which is the event $B^{U}_{m}$) then
$\eta_{\tau_{m}^{U}}\neq\diamond$ by the definition of discarding rule.
Therefore, we get that for all $m>0$,

$\mathbb{P}(A^{U}_{m})\stackrel{{\scriptstyle\eqref{eq:simply_event}}}{{=}}\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{B^{U}_{m}}\mathds{1}_{\\{\eta_{\tau_{m}^{U}}\text{
does not discard
}U\\}}}\right]=\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{B^{U}_{m}}\mathbb{E}\Big{(}\mathds{1}_{\\{\eta_{\tau_{m}^{U}}\text{
does not discard }U\\}}\Big{|}\mathcal{F}_{m-1}\Big{)}}\right]\\\
\stackrel{{\scriptstyle\eqref{eq: sec 4 uniform re-
sampling}}}{{\leq}}r\cdot\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{B^{U}_{m}}}\right]\leq
r\cdot\mathbb{E}\mathopen{}\mathclose{{}\left[\mathds{1}_{B^{U}_{m-1}}\mathds{1}_{\\{\eta_{\tau_{m-1}^{U}}\text{
does not discard
}U\\}}}\right]\stackrel{{\scriptstyle\eqref{eq:simply_event}}}{{=}}r\cdot\mathbb{P}(A^{U}_{m-1}),$

where in the second equality we used that $\mathds{1}_{B_{m}}$ is
$\mathcal{F}_{m-1}$–measurable. Iterating the same argument, we retrieve
(5.14). ∎

###### Proof of 5.5.

We want to prove that for all $r\in(1/2,1)$, $m>0$ and $\varepsilon\in(0,1)$,

$\mathbb{P}\mathopen{}\mathclose{{}\left(F^{U}\big{(}\tau^{U}_{m}\big{)}<\varepsilon}\right)\leq\inf_{\gamma<0}\mathopen{}\mathclose{{}\left\\{\mathrm{e}^{-\gamma
m}\cdot\varepsilon^{\kappa^{*}_{\gamma,r}(p)}}\right\\},$

where $\kappa^{*}_{\gamma,r}(p)$ was defined in (5.5). We fix $r\in(1/2,1)$,
$m>0$ and $\varepsilon\in(0,1)$. Let

$\mathcal{J}^{U}_{\varepsilon,r}=\mathopen{}\mathclose{{}\left\\{b\in\mathcal{B}^{U}_{\ominus}\;\middle|\;F^{U}(b^{-})\geq\varepsilon\text{
and }\frac{\max\\{|L_{b}|,|R_{b}|\\}}{|L_{b}|+|R_{b}|}\leq r}\right\\}.$

We start by noticing that
$\\{F^{U}(\tau^{U}_{m})<\varepsilon\\}\subseteq\\{\\#\mathcal{J}^{U}_{\varepsilon,r}\leq
m\\}$. By Chernoff bound, for all $\gamma<0$, we have

$\mathbb{P}\mathopen{}\mathclose{{}\left(F^{U}\big{(}\tau^{U}_{m}\big{)}<\varepsilon}\right)\leq\mathbb{P}\mathopen{}\mathclose{{}\left(\\#\mathcal{J}^{U}_{\varepsilon,r}\leq
m}\right)\leq\mathrm{e}^{-\gamma
m}\mathbb{E}\mathopen{}\mathclose{{}\left[\mathrm{e}^{\gamma\\#\mathcal{J}^{U}_{\varepsilon,r}}}\right].$
(5.17)

Fix $\gamma<0$. Recall the notation