# Locally uniform random permutations with large increasing subsequences

Victor Dubach

► To cite this version:

Victor Dubach. Locally uniform random permutations with large increasing subsequences. Combinatorial Theory, 2023, 3 (3), 10.5070/C63362784. hal-04443244

HAL Id: hal-04443244

https://hal.science/hal-04443244v1

Submitted on 24 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Title

Locally uniform random permutations with large increasing subsequences

Permalink

https://escholarship.org/uc/item/74p4n0rz

Journal

Combinatorial Theory, 3(3)

ISSN

2766-1334

Author

Dubach, Victor

Publication Date

2023

DOI

10.5070/C63362784

Supplemental Material

https://escholarship.org/uc/item/74p4n0rz#supplemental

Copyright Information

Copyright 2023 by the author(s). This work is made available under the terms of a Creative Commons Attribution License, available at https://creativecommons.org/licenses/by/4.0/

Peer reviewed
# LOCALLY UNIFORM RANDOM PERMUTATIONS WITH LARGE INCREASING SUBSEQUENCES

Victor Dubach¹

¹Institut Élie Cartan de Lorraine, Université de Lorraine, Nancy, France
victor.dubach@univ-lorraine.fr

Submitted: Jan 23, 2023; Accepted: Aug 1, 2023; Published: Dec 22, 2023

© The author. Released under the CC BY license (International 4.0).

**Abstract.** We investigate the maximal size of an increasing subset among points randomly sampled from certain probability densities. Kerov and Vershik's celebrated result states that the largest increasing subset among $N$ uniformly random points on $[0, 1]^2$ has size asymptotically $2\sqrt{N}$. More generally, the order $\Theta(\sqrt{N})$ still holds if the sampling density is continuous. In this paper we exhibit two sufficient conditions on the density to obtain a growth rate equivalent to any given power of $N$ greater than $\sqrt{N}$, up to logarithmic factors. Our proofs use methods of slicing the unit square into appropriate grids, and investigating sampled points appearing in each box.

**Keywords.** Random permutations, longest increasing subsequences, permutons

**Mathematics Subject Classifications.** 60C05, 05A05

# 1. Introduction

## 1.1. Random permutations sampled from a pre-permuton

We start by defining the model of random permutations studied in this paper. Consider points $X_1, \dots, X_N$ in the unit square $[0, 1]^2$ whose $x$-coordinates and $y$-coordinates are all distinct. One can then define a permutation $\sigma$ of size $N$ in the following way: for any $i, j \in [1, N]$, let $\sigma(i) = j$ whenever the point with $i$-th lowest $x$-coordinate has $j$-th lowest $y$-coordinate. We denote by $\text{Perm}(X_1, \dots, X_N)$ this permutation; see Figure 1.1 for an example. Now suppose $\mu$ is a probability measure on $[0, 1]^2$ and $X_1, \dots, X_N$ are random i.i.d. points distributed under $\mu$: the random permutation $\text{Perm}(X_1, \dots, X_N)$ is then denoted by $\text{Sample}_N(\mu)$. To ensure this permutation is well defined, we suppose that the marginals of $\mu$ have no atom so that $X_1, \dots, X_N$ have almost surely distinct $x$-coordinates and $y$-coordinates. We call such a measure a *pre-permuton*; see Section 2.4 for discussion around this name.
<figure><img src="image_2.png" /><figcaption>Figure 1.1: A family of points and its associated permutation, written in one-line notation $\sigma = \sigma(1)\sigma(2)\dots\sigma(N)$. Here we have $\sigma(1) = 2$ because the leftmost point is second from the bottom; and so on.</figcaption></figure>

Notice that permutations sampled from the uniform measure on $[0, 1]^2$ are uniformly random. The model of random permutations previously defined thus generalizes the uniform case while allowing for new tools in a geometric framework, as illustrated in [AD95] (see also [Kiw06] for a variant with uniform involutions). This observation motivates the study of such models, as done for example in [DZ95] or [Sjö23].

In the present paper we are interested in pre-permutons that are absolutely continuous with respect to Lebesgue measure on $[0, 1]^2$, and denote by $\mu_\rho$ the pre-permuton having density $\rho$. Following [Sjö23] we call the permutations sampled under $\mu_\rho$ locally uniform. This name is easily understood when $\rho$ is continuous, since the measure $\mu_\rho$ can then locally be approximated by a uniform measure.

## 1.2. Growth speed of the longest increasing subsequence

Let $\sigma$ be a permutation of size $N$. An increasing subsequence of $\sigma$ is a sequence of indices $i_1 < \dots < i_k$ such that $\sigma(i_1) < \dots < \sigma(i_k)$. The maximal length of such a sequence is called (length of the) longest increasing subsequence of $\sigma$ and denoted by $\text{LIS}(\sigma)$. Ulam formulated in the 60's the following question: let us write (here and throughout this paper), for all $N \in \mathbb{N}^*$,

$$ \ell_N := \mathbb{E}[\text{LIS}(\sigma_N)] \text{ where } \sigma_N \text{ is a uniformly random permutation of size } N, \quad (1.1) $$

then what can we say about the asymptotic behavior of $\ell_N$ as $N \to \infty$? The study of longest increasing subsequences has since then been a surprisingly fertile research subject with unexpected links to diverse areas of mathematics; see [Rom15] for a review. A solution to Ulam's problem was found by Vershik and Kerov; using objects called Young diagrams through Robinson-Schensted's correspondence, they obtained the following:
**Theorem 1.1 ([VK77]).** For each integer $N$, let $\sigma_N$ be a uniform permutation of size $N$. Then:

$$ \frac{1}{\sqrt{N}} \mathrm{LIS}(\sigma_N) \xrightarrow[N \to \infty]{2} $$

in probability and $L^1$-norm. In particular, writing $\ell_N := \mathbb{E}[\mathrm{LIS}(\sigma_N)]$:

$$ \frac{1}{\sqrt{N}} \ell_N \xrightarrow[N \to \infty]{2}. $$

The asymptotic behavior of the longest increasing subsequence in the uniform case is now well understood with concentration inequalities [Fri91, Tal95] and an elegant asymptotic development [BDJ99]. Note that the concentration inequalities later recalled in Theorems 2.5 and 2.7 can be used to recover Theorem 1.1 from the first moment convergence.

It is then natural to try and generalize Theorem 1.1 to $\mathrm{LIS}(\mathrm{Sample}_N(\mu))$ for appropriate pre-permutons $\mu$. One of the first advances on this question was obtained by Deuschel and Zeitouni who proved:

**Theorem 1.2 ([DZ95], Theorem 2).** If $\rho$ is a $C_b^1$, bounded below probability density on $[0, 1]^2$ then:

$$ \frac{1}{\sqrt{N}} \mathrm{LIS}(\mathrm{Sample}_N(\mu_\rho)) \xrightarrow[N \to \infty]{K_\rho} $$

in probability, for some positive constant $K_\rho$ defined by a variational problem.

This $\sqrt{N}$ behavior holds more generally when the sampling density is continuous, as we prove in Section 3:

**Proposition 1.3.** Let $f$ be a continuous probability density on $[0, 1]^2$. Then:

$$ \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_N(\mu_f))] = \Theta_{N \to \infty} (\sqrt{N}). $$

These results, as well as most of the literature on the subject, are restricted to the case of a pre-permuton with “regular”, bounded density. The goal of this paper is to investigate the asymptotic behavior of $\mathrm{LIS}(\mathrm{Sample}_N(\mu_\rho))$ when $\rho$ is a probability density on $[0, 1]^2$ satisfying certain types of divergence. We state in Section 2.2 sufficient conditions on $\rho$ for the quantity $\mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_N(\mu_\rho))]$ to be equivalent to any given power of $N$ (between $N^{1/2}$ and $N$), up to logarithmic factors. We then present in Section 2.3 a few concentration inequalities for $\mathrm{LIS}(\mathrm{Sample}_N(\mu_\rho))$, explaining why we can focus on the asymptotic behavior of the mean.

Similar asymptotics of $\mathrm{LIS}$ can also be obtained under certain regimes of Mallows random permutations, see [BP15, Theorem 1.2]. However such models are quite different from the model of sampled permutations studied here: in the regime $n(1 - q_n) \to +\infty$ of [BP15], Mallows permutations converge to the permuton that puts uniform mass along the diagonal of the unit square.

Lastly, it might be worth pointing out that growth rates found in this paper can be seen as “intermediate” in the theory of pre-permutons. Indeed, we previously explained how the $\sqrt{N}$ behavior corresponds to a “regular” case. In a forthcoming paper we study under which condition the sampled permutation's longest increasing subsequence behaves linearly in $N$:
**Proposition 1.4** ([Dub23]). Let $\mu$ be a pre-permuton and define

$$ \widetilde{\text{LIS}}(\mu) := \max_A \mu(A) $$

where the maximum is taken over all increasing subsets of $[0, 1]^2$, in the sense that any pair of its points is $\prec$-ordered with the notation of Section 2.1. Then the function $\widetilde{\text{LIS}}$ is upper semi-continuous on pre-permutons and satisfies

$$ \frac{1}{N}\text{LIS}(\text{Sample}_N(\mu)) \xrightarrow[N \to \infty]{\phantom{=} } \widetilde{\text{LIS}}(\mu) \quad \text{almost surely.} $$

# 2. Our results

## 2.1. Some notation

Throughout the paper, the only order on the plane we consider is the partial order $\prec$ defined by:

$$ \text{for all } (x_1, y_1), (x_2, y_2) \in \mathbb{R}^2, \quad (x_1, y_1) \prec (x_2, y_2) \text{ if and only if } x_1 < x_2 \text{ and } y_1 < y_2. $$

We also write $\text{dist}$ for the $L^1$-distance in the plane, namely:

$$ \text{for all } (x_1, y_1), (x_2, y_2) \in \mathbb{R}^2, \quad \text{dist}((x_1, y_1), (x_2, y_2)) := |x_1 - x_2| + |y_1 - y_2|, $$

and we denote by $\Delta$ the diagonal of the unit square $[0, 1]^2$. We use the symbols $\mathbb{N}$ for the set of non-negative integers and $\mathbb{N}^*$ for the set of positive integers.

Consider points $X_1, \dots, X_N$ in the unit square $[0, 1]^2$ whose x-coordinates and y-coordinates are all distinct. Then the quantity $\text{LIS}(\text{Perm}(X_1, \dots, X_N))$ is easily read on the visual representation: it is the maximum size of an increasing subset of these points, i.e. the maximum number of points forming an up-right path. For this reason and to simplify notation, we write $\text{LIS}(X_1, \dots, X_N)$ for this quantity.

If $(a_n), (b_n)$ are two sequences of positive real numbers, we write $a_n \sim b_n$ when they are asymptotically equivalent i.e. $a_n/b_n \to 1$. We use the symbols $\tilde{O}, \tilde{\Theta}, \tilde{\Omega}$ for asymptotic comparisons up to logarithmic factors: write $a_n = \tilde{O}(b_n)$ as $n \to \infty$ when there exist constants $c_1 > 0$ and $c_2 \in \mathbb{R}$ such that for some integer $n_0$:

$$ \text{for all } n \ge n_0, \quad a_n \le c_1 \log(n)^{c_2} b_n. $$

We also write $a_n = \tilde{\Omega}(b_n)$ when $b_n = \tilde{O}(a_n)$, and $a_n = \tilde{\Theta}(b_n)$ when simultaneously $a_n = \tilde{O}(b_n)$ and $a_n = \tilde{\Omega}(b_n)$. When these asymptotic comparisons hold with no logarithmic factor, we use the symbols $O, \Theta, \Omega$.

## 2.2. First moment asymptotics of the longest increasing subsequence

Our main results are two conditions on the divergence of the pre-permuton density that imply a large growth rate for the longest increasing subsequences in the sampled permutations. First
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>Figure 2.1: Representation of the divergent densities studied in this paper. On the left, a representation of the density appearing in Theorem 2.2 with $\frac{\beta}{\beta-1} = 3$. Bright yellow indicates a high value while dark blue indicates a low value. On the right, the 3D graph of a function satisfying the hypothesis of Theorem 2.3 with $\alpha = -0.5$.</figcaption></figure>

we study densities diverging at a single point (see the left-hand side of Figure 2.1) and then we study densities diverging along the diagonal (see the right-hand side of Figure 2.1).

The first natural type of divergence to consider is a divergence at a single point. Suppose this happens at the north-east corner, in a radial way around this point. We show in this case that longest increasing subsequences behave similarly to the continuous density case, up to a logarithmic factor.

**Theorem 2.1.** Suppose the density $\rho$ is continuous on $[0, 1]^2 \setminus \{(1, 1)\}$ and satisfies

$$ \rho(x, y) = \Theta(d^{\alpha}) \quad \text{as} \quad (x, y) \to (1, 1) $$

where $d := \text{dist}((x, y), (1, 1))$, for some $\alpha > -2$. Then:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_\rho))] = \tilde{\Theta}_{N \to \infty} (\sqrt{N}). $$

Note that the condition $\alpha > -2$ is necessary for integrability. In order to see long increasing subsequences appear in the sampled permutations, we can “pinch” the density along the diagonal when approaching the north-east corner. This will force sampled points to concentrate along the diagonal, thus likely forming increasing subsequences, and allow for sharper divergence exponents.

**Theorem 2.2.** Suppose the density $\rho$ is continuous on $[0, 1]^2 \setminus \{(1, 1)\}$ and satisfies

$$ \rho(x, y) = \Theta \left( d^{\frac{\beta}{1-\beta}} \exp \left( -c|x-y|d^{\frac{\beta}{1-\beta}} \right) \right) \quad \text{as} \quad (x, y) \to (1, 1) $$

where $d := \text{dist}((x, y), (1, 1))$, for some $\beta \in ]1, 2[$ and $c > 0$. Then:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_\rho))] = \tilde{\Theta}_{N \to \infty} (N^{1/\beta}). $$
Note that when $\beta$ varies between 1 and 2, the exponent $\frac{\beta}{1-\beta}$ varies between $-\infty$ and $-2$. Note also that such densities exist by integrability of the estimate.

Instead of a divergence at a single point, we may also study a type of divergence along an increasing curve. This can be done with a power function and provides a different condition from Theorem 2.2 to obtain a behavior equivalent to any given power of $N$ (between $N^{1/2}$ and $N$), up to a logarithmic factor.

**Theorem 2.3.** Suppose the density $\rho$ is continuous on $[0, 1]^2 \setminus \Delta$ and satisfies

$$ \rho(x, y) = \Theta(|x - y|^{\alpha}) \quad \text{as} \quad |x - y| \to 0 $$

for some $\alpha \in ]-1, 0[$. Then:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_\rho))] = \tilde{\Theta}_{N \to \infty}(N^{1/(\alpha+2)}). $$

While these previous assumptions are all quite intuitive to consider, Theorem 2.3 is of a somewhat other nature than Theorems 2.1 and 2.2. As explained in Section 2.5, their proofs also work differently and illustrate slightly distinct techniques which might have broader applications.

The study of densities in Theorems 2.1 and 2.2 relies on a family of reference pre-permutons (permutons actually, see Section 2.4) that we now introduce. Fix two parameters $\beta > 1$ and $\gamma \in \mathbb{R}$. Define for any positive integer $k \ge 1$:

$$ u_k := \frac{1}{Z_{\beta, \gamma}} k^{-\beta} \log(k+1)^{\gamma} \quad \text{where} \quad Z_{\beta, \gamma} := \sum_{k \ge 1} k^{-\beta} \log(k+1)^{\gamma}. $$

For all $n \ge 0$, set $S_n := \sum_{k=1}^n u_k$ and consider the sequence of disjoint boxes $C_n := [S_{n-1}, S_n]^2$, $n \in \mathbb{N}^*$, covering the diagonal in an increasing manner. We can then define a probability density on the unit square by

$$ \rho_{\beta, \gamma}^{\rightarrow} := \sum_{k \ge 1} u_k^{-1} \mathbf{1}_{C_k} $$

and we write $\mu_{\beta, \gamma}^{\rightarrow}$ for the (pre-)permuton having density $\rho_{\beta, \gamma}^{\rightarrow}$ with respect to Lebesgue measure on $[0, 1]^2$. See Figure 2.2 for a representation.

**Proposition 2.4.** Let $\gamma \ge 0$. If $\beta \in ]1, 2[$ then:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_{\beta, \gamma}^{\rightarrow}))] = \tilde{\Theta}_{N \to \infty}(N^{1/\beta}). $$

If $\beta \ge 2$ then:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_{\beta, \gamma}^{\rightarrow}))] = \tilde{\Theta}_{N \to \infty}(\sqrt{N}). $$

In Section 5 we use Proposition 2.4 to prove Theorems 2.1 and 2.2 by comparing the densities involved. The parameter $\beta$ allows $\rho_{\beta, \gamma}^{\rightarrow}$ to have similar asymptotics to the density $\rho$ in Theorem 2.1 or 2.2, while the parameter $\gamma$ allows to slightly modify the size of the boxes so that they cover the divergence of $\rho$ adequately. When $\gamma = 0$, we drop this subscript and simply write $\rho_{\beta}^{\rightarrow}$.
<figure><img src="image_5.png" /><figcaption>Figure 2.2: A representation of the permuton $\mu_{\beta, \gamma}$. Bright yellow indicates a high value while dark blue indicates a low value of the density.</figcaption></figure>

## 2.3. Concentration around the mean

In this paper we only investigate the mean of $\text{LIS}(\text{Sample}_N(\mu))$. The reason for this is that we can easily deduce asymptotic knowledge of the random variable itself from well known concentration inequalities. In our case it is sufficient to use what is usually referred to as Azuma's or McDiarmid's inequality, found in [McD89, Lemma 1.2] and whose origin goes back to [Azu67]. One of its most common use is for the chromatic number of random graphs, but it is also well adapted to the study of longest increasing subsequences as illustrated in [Fri91].

**Theorem 2.5 (McDiarmid's inequality).** Let $N \in \mathbb{N}^*$, $X_1, \dots, X_N$ be independent random variables with values in a common space $\mathcal{X}$ and $f: \mathcal{X}^N \to \mathbb{R}$ be a function satisfying the bounded differences property: for all $i \in [1, N]$ and $x_1, \dots, x_N, y_i \in \mathcal{X}$,

$$|f(x_1, \dots, x_i, \dots, x_N) - f(x_1, \dots, y_i, \dots, x_N)| \le c$$

for some constant $c > 0$. Then for any positive number $\lambda > 0$:

$$\mathbf{P} \left( |f(X_1, \dots, X_N) - \mathbb{E}[f(X_1, \dots, X_N)]| > \lambda \right) \le 2 \exp \left( \frac{-2\lambda^2}{Nc^2} \right).$$

We can apply this to $\text{LIS}(X_1, \dots, X_N)$ where $X_1, \dots, X_N$ are i.i.d. points distributed under $\mu$, noticing that changing the value of a single point changes the size of the largest increasing subset by at most 1.

**Corollary 2.6.** Let $\mu$ be a pre-permuton. Then for any $N \in \mathbb{N}^*$ and $\lambda > 0$:

$$\mathbf{P} \left( |\text{LIS}(\text{Sample}_N(\mu)) - \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu))]| > \lambda \right) \le 2 \exp \left( \frac{-2\lambda^2}{N} \right).$$

This concentration inequality is especially useful when $\mathbb{E}[\text{LIS}(\text{Sample}_N(\mu))]$ is of order greater than $\sqrt{N}$, which is for example the case in Theorem 2.2 when $\beta \in ]1, 2[$. Corollary 2.6 then implies that the variable is concentrated around its mean in the sense that

$$\frac{\text{LIS}(\text{Sample}_N(\mu))}{\mathbb{E}[\text{LIS}(\text{Sample}_N(\mu))]} \xrightarrow{N \to \infty} 1$$
in probability. Moreover $\text{LIS}(\text{Sample}_N(\mu))$ admits a median of order $\tilde{\Theta}(N^{1/\beta})$, and an analogous remark holds for Theorem 2.3. One could then apply the following sharper concentration inequality:

**Theorem 2.7** (Talagrand's inequality for longest increasing subsequences). Let $\mu$ be a pre-permuton. For any $N \in \mathbb{N}^*$, denote by $M_N$ a median of $L_N := \text{LIS}(\text{Sample}_N(\mu))$. Then for all $\lambda > 0$:

$$ \mathbf{P}(L_N \ge M_N + \lambda) \le 2 \exp\left(\frac{-\lambda^2}{4(M_N + \lambda)}\right) \quad \text{and} \quad \mathbf{P}(L_N \le M_N - \lambda) \le 2 \exp\left(\frac{-\lambda^2}{4M_N}\right). $$

See [Tal95, Theorem 7.1.2] for the original reference in the case of uniform permutations. The proof works the same for random permutations sampled from pre-permutons. See also [Kiw06, Theorem 5] for a nice application to longest increasing subsequences in random involutions.

## 2.4. Discussion

**Improvements.** Several hypotheses made in the theorems simplify the calculations but are not crucial to the results. For instance Theorems 2.1 and 2.2 could be generalized by replacing the north-east corner with any point in the unit square and the diagonal with any local increasing curve passing through that point, under appropriate hypotheses. A similar remark holds for Theorem 2.3. We could also state Proposition 2.4 for general $\gamma \in \mathbb{R}$, but prefer restricting ourselves to the case $\gamma \ge 0$ since this is all we need for the proofs of Theorems 2.1 and 2.2 and it requires a bit less work.

The necessity of logarithmic factors in our estimates remains an open question. We believe our results could be sharpened in this direction, but our techniques do not seem sufficient to this aim.

**Links to permuton and graphon theory.** When $\mu$ is a probability measure on $[0, 1]^2$ whose marginals are uniform, we call it a *permuton* as in [GGKK15]. The theory of permutons was introduced in [HKM+13] and is now widely studied [KP13, Muk16, BBF+18, BBF+22]. It serves as a scaling limit for random permutations and is directly related to the study of pattern occurrences (see e.g. [HKM+13, Definition 1.5] or [BBF+20, Theorem 2.5]). One of its fundamental results is that for any permuton $\mu$, the sequence $(\text{Sample}_N(\mu))_{N \in \mathbb{N}^*}$ almost surely converges in some sense to $\mu$.

Reading this paper does not require any prior knowledge about the literature on permutons: it is merely part of our motivation for the study of models $\text{Sample}_N(\mu)$. Notice however that considering pre-permutons instead of permutons is nothing but a slight generalization. Indeed, one can associate to any pre-permuton $\mu$ a unique permuton $\hat{\mu}$ such that random permutations sampled from $\mu$ or $\hat{\mu}$ have the same law (see e.g. [BDMW23, Remark 1.2]).

This paper was partly motivated by [McK19], where an analogous problem is tackled for graphons. The theory of graphons for the study of dense graph sequences is arguably the main inspiration at the origin of permuton theory, and there exist numerous bridges between them [GGKK15, BBD+22]. For instance the longest increasing subsequence of permutations
corresponds to the clique number of graphs. In [DHM17] the authors exhibit a wide family of graphons bounded away from 0 and 1 whose sampled graphs have logarithmic clique numbers, thus generalizing this property of Erdős-Rényi random graphs. In some sense this is analogous to Deuschel and Zeitouni's result on permutations (Theorem 1.2 here). In [McK19] the author studies graphons allowed to approach the value 1, and proves in several cases that clique numbers behave as a power of N; the results of the present paper are counterparts for permutations.

## 2.5. Proof method and organization of the paper

The proofs of Theorems 2.1 and 2.2 rely on bounding the density of interest on certain appropriate areas with other densities which are easier to study. This general technique is developed in Section 3 where we prove two lemmas of possible independent interest.

Section 4 is devoted to our reference permutations, which are the main ingredient when bounding general densities. The idea for the proof of Proposition 2.4 is that points sampled from $\mu_{\beta, \gamma}^{\uparrow}$ are uniformly sampled on each box $C_n$. We can thus use Theorem 1.1 on each box containing enough points, the latter property being studied through appropriate concentration inequalities on binomial variables.

We then prove Theorems 2.1 and 2.2 in Section 5, using all the previously developed tools.

Finally, we prove Theorem 2.3 in Section 6. This proof does not use the previous techniques and rather uses a grid on the unit square that gets thinner as $N \to \infty$. The main idea is to bound the number of points appearing in any increasing sequence of boxes. The sizes of the boxes are chosen so that a bounded number of points appear in each box, and concentration inequalities are used to make sure such approximations hold simultaneously on every box.

## 3. Bounds on LIS from bounds on the density

One of the main ideas for the proofs of Theorems 2.1 and 2.2 is to deduce bounds on the order of LIS from bounds on the sampling density. We state here two useful lemmas to this aim.

**Lemma 3.1.** Suppose $f, g$ are two probability densities on $[0, 1]^2$ such that $f \ge \varepsilon g$ for some $\varepsilon > 0$. Then:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_f))] = \Omega \left( \mathbb{E}[\text{LIS}(\text{Sample}_{\lfloor \varepsilon N \rfloor}(\mu_g))] \right). $$

Likewise, if $f \le Mg$ for some $M > 0$ then

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_f))] = O \left( \mathbb{E}[\text{LIS}(\text{Sample}_{\lfloor MN \rfloor}(\mu_g))] \right). $$

*Proof.* Let us deal with the first assertion of the lemma. We can write

$$ f = \varepsilon g + (1 - \varepsilon)h $$

for some other probability density $h$ on the unit square. The idea is to use a coupling between those densities. Let $N \in \mathbb{N}^*$ and $B_1, \dots, B_N$ be i.i.d. Bernoulli variables of parameter $\varepsilon$,
$Y_1, \dots, Y_N$ be i.i.d. random points distributed under density $g$, and $Z_1, \dots, Z_N$ be i.i.d. random points distributed under density $h$, all independent. Then define for all $i$ between 1 and $N$:

$$X_i := Y_i B_i + Z_i (1 - B_i).$$

It is clear that $X_1, \dots, X_N$ are distributed as $N$ i.i.d. points under density $f$. Let $I$ be the set of indices $i$ for which $B_i = 1$. Then

$$\mathrm{LIS}(X_1, \dots, X_N) \geq \mathrm{LIS}(Y_i, i \in I).$$

Hence, if $S_N$ denotes an independent binomial variable of parameter $(N, \varepsilon)$:

$$\mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_N(\mu_f))] \geq \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{S_N}(\mu_g))] \\ \geq \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{[\epsilon N]}(\mu_g))] \mathbf{P}(S_N \geq \epsilon N)$$

where the latter is bounded away from 0. This concludes the proof of the first assertion. The second one is a simple rewriting of it. $\square$

**Lemma 3.2.** Suppose $f, g, h$ are probability densities on $[0, 1]^2$ such that $f \leq c_1g + c_2h$ for some $c_1, c_2 > 0$. Then

$$\mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_N(\mu_f))] = \mathop{O}\limits_{N \to \infty} \left( \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{[MN]}(\mu_g))] + \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{[MN]}(\mu_h))] \right)$$

for some constant $M > 0$.

*Proof.* First write $c_1g + c_2h = M(\lambda g + (1 - \lambda)h)$ with appropriate $M > 0$ and $\lambda \in ]0, 1[$. Applying Lemma 3.1 gives us:

$$\mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_N(\mu_f))] = \mathop{O}\limits_{N \to \infty} \left( \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{[MN]}(\mu_{\lambda g+(1-\lambda)h}))] \right).$$

We once again use a coupling argument. Let $N \in \mathbb{N}^*$ and $B_1, \dots, B_{[MN]}$ be i.i.d. Bernoulli variables of parameter $\lambda$, $Y_1, \dots, Y_{[MN]}$ be i.i.d. random points distributed under density $g$, and $Z_1, \dots, Z_{[MN]}$ be i.i.d. random points distributed under density $h$, all independent. Then define for all integer $i$ between 1 and $[MN]$:

$$X_i := Y_i B_i + Z_i (1 - B_i).$$

It is clear that $X_1, \dots, X_{[MN]}$ are distributed as $[MN]$ i.i.d. points under density $\lambda g + (1 - \lambda)h$. Moreover

$$\mathrm{LIS}(X_1, \dots, X_{[MN]}) \leq \mathrm{LIS}(Y_1, \dots, Y_{[MN]}) + \mathrm{LIS}(Z_1, \dots, Z_{[MN]})$$

whence

$$\mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{[MN]}(\mu_{\lambda g+(1-\lambda)h}))] \\ \leq \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{[MN]}(\mu_g))] + \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{[MN]}(\mu_h))]$$

This concludes the proof. $\square$
Before moving on, we explain how to deduce Proposition 1.3 from Lemma 3.1.

*Proof of Proposition 1.3.* Since $f$ is continuous on $[0, 1]^2$, there exists $M > 0$ satisfying $f \le M$. Using Theorem 1.1 and Lemma 3.1 we get:

$$ \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_N(\mu_f))] = O(\ell_{[MN]}) = O(\sqrt{N}) $$

as $N \to \infty$, where $\ell$ is defined in (1.1). Then, $f$ also being non-zero, there exists $\varepsilon > 0$ and a square box $C$ contained in $[0, 1]^2$ such that $f \ge \varepsilon$ on $C$. Since random points uniformly sampled in $C$ yield uniformly random permutations, Theorem 1.1 and Lemma 3.1 imply:

$$ \begin{aligned} \mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_N(\mu_f))] &= \Omega(\mathbb{E}[\mathrm{LIS}(\mathrm{Sample}_{[\varepsilon\mathrm{Leb}(C)N]}(\mathrm{Leb}_C))]) \\ &= \Omega(\ell_{[\varepsilon\mathrm{Leb}(C)N]}) = \Omega(\sqrt{N}) \end{aligned} $$

as $N \to \infty$, where $\mathrm{Leb}(C)$ denotes the Lebesgue measure of $C$. We have thus proved the desired estimate. $\square$

Similar techniques of coupling were already present at least in [DZ95, Lemma 7] for locally uniform permutations, and in [MS11, Lemma 4.2, Corollary 4.3] for Mallows permutations. In the context of these articles, comparison with a uniform density on small boxes was possible. Here, to take into account the divergent behavior of our densities, we either use a global comparison with the density $\rho_{\beta, \gamma}^{\uparrow}$ to prove Theorems 2.1 and 2.2, or make the size of the boxes depend on the number of sampled points to prove Theorem 2.3.

# 4. Study of reference permutations

## 4.1. Preliminaries

The proof of Proposition 2.4 hinges on the estimation of binomial variables. We thus state a concentration inequality usually referred to as Bernstein's inequality. If $S_n$ denotes a binomial variable of parameter $(n, p)$, then:

**Lemma 4.1.** For all $t > 0$:

$$ \mathbf{P}(|S_n - np| \ge t) \le 2 \exp \left( - \frac{t^2/2}{np(1-p) + t/3} \right). $$

See [Ben62, Equation (8)] for an easy-to-find reference and discussion on improvements, or [Ber27] for the original one.

Now let us recall some asymptotics related to the sequence $(u_k)_{k \in \mathbb{N}^*}$ introduced in Section 2.2. A short proof is included for completeness.

**Lemma 4.2.** For any $\beta > 1$ and $\gamma \in \mathbb{R}$ we have

$$ \sum_{k \ge n} k^{-\beta} \log(k+1)^{\gamma} \sim_{n \to \infty} \frac{n^{1-\beta}}{\beta-1} \log(n)^{\gamma}. $$
Moreover for any $\beta' < 1$:

$$ \sum_{k=1}^{n} k^{-\beta'} \log(k+1)^{\gamma} \underset{n \to \infty}{\sim} \frac{n^{1-\beta'}}{1-\beta'} \log(n)^{\gamma}. $$

*Proof.* First use the integral comparison:

$$ \sum_{k \ge n} k^{-\beta} \log(k+1)^{\gamma} \underset{n \to \infty}{\sim} \int_{n}^{+\infty} x^{-\beta} \log(x+1)^{\gamma} dx $$

and then an elementary integration by parts

$$ \int_{n}^{+\infty} x^{-\beta} \log(x+1)^{\gamma} dx = \frac{n^{1-\beta}}{\beta-1} \log(n+1)^{\gamma} - \int_{n}^{+\infty} \frac{x^{1-\beta}}{1-\beta} \frac{\gamma}{x+1} \log(x+1)^{\gamma-1} dx \\ = \frac{n^{1-\beta}}{\beta-1} \log(n+1)^{\gamma} + \frac{\gamma}{\beta-1} \int_{n}^{+\infty} \frac{x^{1-\beta}}{x+1} \log(x+1)^{\gamma-1} dx. $$

However, the following holds:

$$ \int_{n}^{+\infty} \frac{x^{1-\beta}}{x+1} \log(x+1)^{\gamma-1} dx = o \left( \int_{n}^{+\infty} x^{-\beta} \log(x+1)^{\gamma} dx \right) \quad \text{as } n \to \infty. $$

This concludes the proof of the first assertion. The second one is completely similar. $\square$

## 4.2. Proof of Proposition 2.4

In this section we fix $\beta > 1$ and $\gamma \ge 0$ and prove Proposition 2.4. Consider $N \in \mathbb{N}^*$ and write

$$ L_N := \text{LIS} \left( \text{Sample}_N \left( \mu_{\beta, \gamma}^{\uparrow} \right) \right). $$

Let $X_1, \dots, X_N$ be i.i.d. random variables distributed under $\mu_{\beta, \gamma}^{\uparrow}$. For each $k \in \mathbb{N}^*$, define

$$ \mathcal{X}_{N,k} := \{X_1, \dots, X_N\} \cap C_k $$

and let $N_k$ be the cardinal of $\mathcal{X}_{N,k}$, i.e. the number of points appearing in box $C_k$. Each $N_k$ is a binomial variable of parameter $(N, u_k)$, and almost surely

$$ \sum_{k \ge 1} N_k = N. $$

Conditionally on $N_k$, the set $\mathcal{X}_{N,k}$ consists of $N_k$ uniformly random points in $C_k$. Moreover, almost surely:

$$ \text{LIS}(X_1, \dots, X_N) = \sum_{k \ge 1} \text{LIS}(\mathcal{X}_{N,k}) $$
thanks to the boxes being placed in an increasing fashion. Hence by taking expectation in the previous line, one obtains

$$ \mathbb{E}[L_N] = \sum_{k \ge 1} \mathbb{E}[\ell_{N_k}] $$

with the notation of (1.1). For some integer $k_N$ to be determined, we will use the following bounds:

$$ \sum_{k=1}^{k_N} \mathbb{E}[\ell_{N_k}] \le \mathbb{E}[L_N] \le \sum_{k=1}^{k_N} \mathbb{E}[\ell_{N_k}] + N \sum_{k>k_N} u_k \quad (4.1) $$

where the right hand side was obtained by simply bounding each $\ell_{N_k}$ for $k > k_N$ with $N_k$. Using Theorem 1.1, fix an integer $n_0$ such that

$$ \text{for all } n \ge n_0, \quad \sqrt{n} \le \ell_n \le 3\sqrt{n}. \quad (4.2) $$

The number $k_N$ appearing in Equation (4.1) must be chosen big enough for the bounds to be tight, but also small enough for (4.2) to be used. By applying Bernstein's inequality (Lemma 4.1) here with an appropriate choice of parameter, we obtain for any $N, k \in \mathbb{N}^*$:

$$ \mathbf{P}\left(\left|N_k - Nu_k\right| \ge \log(N)^2 \sqrt{Nu_k}\right) \le 2 \exp(-\psi_{N,k}) \\ \text{where } \psi_{N,k} := \frac{\log(N)^4 Nu_k/2}{Nu_k(1-u_k) + \log(N)^2 \sqrt{Nu_k}/3}. \quad (4.3) $$

We will investigate the term $\psi_{N,k}$ later on, and obtain the simple upper bound (4.5) for adequate values of $k$. To apply (4.2) and (4.3) we are looking, for each positive integer $N$, for $k_N$ satisfying

$$ \text{for any } k \in [1, k_N], \quad Nu_k - \log(N)^2 \sqrt{Nu_k} \ge n_0. \quad (4.4) $$

**Lemma 4.3.** Condition (4.4) holds true for some $k_N = \Theta(N^{4-4/\beta})$.

From now on, we choose $k_N$ as in Lemma 4.3 (note that $k_N$ may be zero for small values of $N$). The proof of this lemma is postponed to the end of this section. Now, let us study the probability error term in (4.3). For any positive integer $k$ lower than or equal to $k_N$, one of the following holds:

* If $Nu_k(1-u_k) \ge \log(N)^2 \sqrt{Nu_k}/3$ then

$$ \psi_{N,k} \ge \frac{\log(N)^4 Nu_k/2}{2Nu_k(1-u_k)} \ge \frac{\log(N)^4}{4}. $$

* Otherwise

$$ \psi_{N,k} \ge \frac{\log(N)^4 Nu_k/2}{2 \log(N)^2 \sqrt{Nu_k}/3} = \frac{3}{4} \log(N)^2 \sqrt{Nu_k} \ge \frac{3}{4} \log(N)^2 \sqrt{n_0} $$

where we used Equation (4.4) in the last inequality.

Hence there exists a constant $\delta > 0$ such that, for all $N \in \mathbb{N}^*$:

$$ \sup_{1 \le k \le k_N} \exp(-\psi_{N,k}) \le \exp(-\delta \log(N)^2). \quad (4.5) $$

To study the bounds of (4.1), we distinguish between the cases $\beta \in ]1, 2[$ and $\beta \ge 2$.
**First suppose $\beta \in ]1, 2[$.** Let us begin with the upper bound of (4.1). On the one hand:

$$N \sum_{k > k_N} u_k = \Theta(N k_N^{1-\beta} \log(k_N)^{\gamma}) = \Theta(\log(N)^{4-4/\beta+\gamma} N^{1/\beta}) \quad (4.6)$$

as $N \to +\infty$, using Lemmas 4.2 and 4.3. On the other hand for each $k \in ]1, k_N]$:

$$\begin{aligned} \mathbb{E}[\ell_{N_k}] &= \mathbb{E}[\ell_{N_k} \mathbf{1}_{|N_k - N u_k| < \log(N)^2 \sqrt{N u_k}}] + \mathbb{E}[\ell_{N_k} \mathbf{1}_{|N_k - N u_k| \ge \log(N)^2 \sqrt{N u_k}}] \\ &\le 3\sqrt{N u_k + \log(N)^2 \sqrt{N u_k}} + N \mathbf{P}(|N_k - N u_k| \ge \log(N)^2 \sqrt{N u_k}) \\ &\le 3\sqrt{N u_k} + 3 \log(N) (N u_k)^{1/4} + 2N \exp(-\delta \log(N)^2) \end{aligned}$$

where we used Equations (4.2) to (4.5), and the inequality $\sqrt{a+b} \le \sqrt{a} + \sqrt{b}$ for any $a, b \ge 0$. Summing and using Lemmas 4.2 and 4.3, we get

$$\begin{aligned} \sum_{k=1}^{k_N} \mathbb{E}[\ell_{N_k}] &\le 3\sqrt{N} \sum_{k=1}^{k_N} \sqrt{u_k} + 3 \log(N) N^{1/4} \sum_{k=1}^{k_N} u_k^{1/4} + 2Nk_N \exp(-\delta \log(N)^2) \quad (4.7) \\ &= 3\sqrt{N} \Theta(k_N^{1-\beta/2} \log(k_N)^{\gamma/2}) + 3 \log(N) N^{1/4} \Theta(k_N^{1-\beta/4} \log(k_N)^{\gamma/4}) + o(1) \\ &= \Theta(\log(N)^{2-4/\beta+\gamma/2} N^{1/\beta}). \end{aligned}$$

as $N \to +\infty$. This last upper bound along with (4.6) yields, in (4.1):

$$\mathbb{E}[L_N] = O(\log(N)^{4-4/\beta+\gamma} N^{1/\beta}) \quad \text{as } N \to \infty. \quad (4.8)$$

Now let us turn to the lower bound of (4.1), for which the calculations are simpler. For any $k \in ]1, k_N]$:

$$\mathbb{E}[\ell_{N_k}] \ge \mathbb{E}[\ell_{N_k} \mathbf{1}_{|N_k - N u_k| < \log(N)^2 \sqrt{N u_k}}] \ge \sqrt{n_0} (1 - 2 \exp(-\psi_{N,k}))$$

using Equations (4.2) to (4.4). Then by summing and using Lemma 4.3 and Eq. (4.5):

$$\mathbb{E}[L_N] \ge k_N \sqrt{n_0} (1 - 2 \exp(-\delta \log(N)^2)) = \Omega(\log(N)^{-4/\beta} N^{1/\beta})$$

as $N \to +\infty$. This lower bound, along with (4.8), concludes the proof of Proposition 2.4 when $\beta \in ]1, 2[$.

**Now suppose $\beta \ge 2$.** The upper bound is very similar to the case $\beta \in ]1, 2[$, but with the appropriate asymptotics. Namely for any $\beta' \ge 1$ and $\gamma' \ge 0$ one has:

$$\sum_{k=1}^{n} k^{-\beta'} \log(k+1)^{\gamma'} = O(\log(n)^{1+\gamma'}) \quad \text{as } n \to \infty. \quad (4.9)$$

On the one hand (4.6) still holds and we can thus write

$$N \sum_{k > k_N} u_k = \tilde{O}(\sqrt{N}) \quad \text{as } N \to \infty. \quad (4.10)$$
On the other hand the first line of (4.7) is still valid and we obtain, as $N \to \infty$:

$$
\begin{align*}
\sum_{k=1}^{k_N} \mathbb{E}[\ell_{N_k}] &\le 3\sqrt{N} \sum_{k=1}^{k_N} \sqrt{u_k} + 3 \log(N) N^{1/4} \sum_{k=1}^{k_N} u_k^{1/4} + 2Nk_N \exp(-\delta \log(N)^2) \\
&\le \sqrt{N} O(\log(N)^{1+\gamma/2}) + o(1) \\
&\quad + \log(N) N^{1/4} \max\left(O(\log(N)^{1+\gamma/4}), \Theta(k_N^{1-\beta/4} \log(k_N)^{\gamma/4})\right) \\
&= O\left(\log(N)^{1+\gamma/2} \sqrt{N}\right) \\
&\quad + \max\left(O\left(\log(N)^{2+\gamma/4} N^{1/4}\right), \Theta\left(\log(N)^{2-4/\beta+\gamma/4} N^{1/\beta}\right)\right) \\
&= \tilde{O}\left(\sqrt{N}\right)
\end{align*}
$$

using Lemma 4.3 and Eq. (4.9) and distinguishing between the cases $\beta \ge 4$ and $\beta < 4$ on the
second line. Along with (4.10), this yields the desired upper bound when injected in (4.1).

The lower bound, on the contrary, requires no calculation. Indeed, bound below $\rho_{\beta,\gamma}^{\uparrow}$ by $u_1 f$
where $f$ denotes the uniform density on the square $C_1$. Since permutations sampled from the
density $f$ are uniform, we deduce from Theorem 1.1 and Lemma 3.1 that

$$
\mathbb{E} \left[ \text{LIS} \left( \text{Sample}_N \left( \mu_{\beta, \gamma}^{\uparrow} \right) \right) \right] = \Omega_{N \to \infty} \left( \ell_{\lfloor u_1 N \rfloor} \right) = \Omega_{N \to \infty} \left( \sqrt{N} \right).
$$

All that is left for the proof of Proposition 2.4 to be complete is the previously announced
lemma about $k_N$.

*Proof of Lemma 4.3.* Let $N \in \mathbb{N}^*$. For each integer $k$:

$$
\[
Nu_k - \log(N)^2 \sqrt{Nu_k} \ge n_0 \iff \begin{cases} Nu_k \ge n_0; \\ Nu_k - n_0 \ge \log(N)^2 \sqrt{Nu_k}; \end{cases}
\]
\[
\iff \begin{cases} Nu_k \ge n_0; \\ N^2 u_k^2 + n_0^2 - 2Nu_k n_0 \ge \log(N)^4 Nu_k; \end{cases}
\]
\[
\iff \begin{cases} u_k \ge n_0/N; \\ N^2 u_k^2 - N(2n_0 + \log(N)^4) u_k + n_0^2 \ge 0. \end{cases}
\]
$$

This last polynomial in the variable $u_k$ has discriminant $\Delta_N = N^2 (\log(N)^8 + 4n_0 \log(N)^4) \ge 0$.
Let $x_N$ be its greatest root. Then

$$
x_N = \frac{N (2n_0 + \log(N)^4) + \sqrt{\Delta_N}}{2N^2} \underset{N \to \infty}{\sim} \frac{\log(N)^4}{N}.
$$

A sufficient condition for $Nu_k - \log(N)^2 \sqrt{Nu_k} \ge n_0$ to hold is $u_k \ge \max(n_0/N, x_N)$. However

$$
u_k = \frac{1}{Z_{\beta, \gamma}} k^{-\beta} \log(k+1)^{\gamma} \ge c_0 k^{-\beta}
$$

for $c_0 := \log(2)^\gamma / Z_{\beta,\gamma}$, so a sufficient condition is

$$
k \le c_0^{1/\beta} \max(n_0/N, x_N)^{-1/\beta}.
$$

Hence the announced estimate for $k_N$.

<figure><img src="image_6.png" /></figure>
# 5. Study of densities diverging at a single point

## 5.1. Lower bound of Theorem 2.2

This bound is quite direct thanks to Lemma 3.1 and the previous study of $\mu_{\beta}^{\uparrow}$. We will use the notation of Section 2.2 with the same $\beta$ as in Theorem 2.2 and $\gamma = 0$. Studying $\rho$ on the boxes $(C_n)_{n \in \mathbb{N}^*}$ will be enough to obtain the desired lower bound. Fix $\varepsilon > 0$ and some rank $m_0 \in \mathbb{N}^*$ such that

$$ \text{for all } n \ge m_0 \text{ and } (x, y) \in C_n, \quad \rho(x, y) \ge \varepsilon d^{\frac{\beta}{1-\beta}} \exp \left( -c|x-y|d^{\frac{\beta}{1-\beta}} \right). $$

Recall the notation $d := \text{dist}((x, y), (1, 1))$ for $(x, y) \in [0, 1]^2$ and write $R_n := \sum_{k>n} u_k$ for any nonnegative integer $n$. Note that, for $(x, y) \in C_n$:

$$ 2R_n \le d \le 2R_{n-1} \quad \text{where} \quad R_{n-1}, R_n = \Theta_{n \to \infty} (n^{1-\beta}) $$

by Lemma 4.2, and

$$ |x - y| \le u_n = \Theta_{n \to \infty} (n^{-\beta}). $$

As a consequence, for potentially different values of $\varepsilon > 0$ and $m_0 \in \mathbb{N}^*$ we get

$$ \text{for all } n \ge m_0 \text{ and } (x, y) \in C_n, \quad \rho(x, y) \ge \varepsilon \rho_{\beta}^{\uparrow}(x, y). $$

Write $g$ for the probability density on $\cup_{n \ge m_0} C_n$ proportional to $\rho_{\beta}^{\uparrow}$. Then by Lemma 3.1:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_{\rho}))] = \Omega_{N \to \infty} (\mathbb{E}[\text{LIS}(\text{Sample}_{\lfloor \varepsilon N \rfloor}(\mu_g))]). $$

Moreover we can obtain

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_g))] = \tilde{\Theta}_{N \to \infty} (N^{1/\beta}) $$

with the same proof as for the reference permutation $\mu_{\beta}^{\uparrow}$ (start every index at $m_0$ instead of 1). Finally:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_{\rho}))] = \tilde{\Omega}_{N \to \infty} (N^{1/\beta}). $$

## 5.2. Upper bound of Theorem 2.2

This bound is more subtle than the previous one. Indeed, long increasing subsequences could appear outside of the boxes used in Section 5.1. Our solution comes in two steps: first consider slightly bigger boxes, and then add an overlapping second sequence of boxes to make sure a whole neighborhood of the diagonal is covered.

We will mainly use the notation of Section 2.2 with the number $\beta$ considered in Theorem 2.2 and any negative number $\gamma < 1 - \beta$. In addition to the boxes $(C_n)_{n \in \mathbb{N}^*}$, define for all $n \in \mathbb{N}^*$:

$$ D_{n+1} := \left[ S_n - \frac{u_{n+1}}{2}, S_n + \frac{u_{n+1}}{2} \right]^2 \quad \text{and} \quad E_n := [S_{n-1}, 1]^2 \setminus ([S_n, 1]^2 \cup C_n \cup D_{n+1}), $$
<figure><img src="image_7.png" /><figcaption>Figure 5.1: The several areas used to study density $\rho$ in the upper bound of Theorem 2.2.</figcaption></figure>

and their unions:

$$E := \bigcup_{n \ge 1} E_n, \quad C := \bigcup_{n \ge 1} C_n, \quad D := \bigcup_{n \ge 1} D_{n+1}.$$

See Figure 5.1 for a visual representation. Notice how these three areas cover the whole unit square. Let us check that $\rho$ is small outside the diagonal neighborhood $C \cup D$:

for all $n \in \mathbb{N}^*$ and $(x, y) \in E_n$, $|x - y| \ge u_{n+1}/2$ and $R_n \le \text{dist}((x, y), (1, 1)) \le 2R_{n-1}$ where $R_n := \sum_{k>n} u_k$. Then using Lemma 4.2, we get as $n \to \infty$ uniformly in $(x, y) \in E_n$:

$$|x - y| = \Omega (n^{-\beta} \log(n)^{\gamma}) \quad \text{and} \quad \text{dist}((x, y), (1, 1)) = \Theta (n^{1-\beta} \log(n)^{\gamma}).$$

Our hypothesis on $\rho$ now rewrites

$$\begin{aligned}
\rho(x, y) &= O \left( \left( n^{1-\beta} \log(n)^{\gamma} \right)^{\frac{\beta}{1-\beta}} \exp \left( -\Omega \left( n^{-\beta} \log(n)^{\gamma} \left( n^{1-\beta} \log(n)^{\gamma} \right)^{\frac{\beta}{1-\beta}} \right) \right) \right) \\
&= O \left( n^{\beta} \log(n)^{\frac{\gamma\beta}{1-\beta}} \exp \left( -\Omega \left( \log(n)^{\frac{\gamma}{1-\beta}} \right) \right) \right) \\
&= o(1)
\end{aligned}$$

since $\frac{\gamma}{1-\beta} > 1$ by choice of $\gamma$. In particular $\rho$ is bounded on $E$, and it remains to study it on areas $C$ and $D$. Using Lemma 4.2 and bounding the exponential term by 1, we get as $n \to \infty$ uniformly in $(x, y) \in C_n \cup D_{n+1}$:

$$\rho(x, y) = O \left( n^{\beta} \log(n)^{\frac{\gamma\beta}{1-\beta}} \right).$$

Consequently

$$\int_{C_n} \rho(x, y)dxdy = O \left( n^{-2\beta} \log(n)^{2\gamma} n^{\beta} \log(n)^{\frac{\gamma\beta}{1-\beta}} \right) = O \left( n^{-\beta} \log(n)^{\gamma(2-\frac{\beta}{\beta-1})} \right) \quad \text{as } n \to \infty$$
and likewise

$$ \int_{D_{n+1}} \rho(x, y)dxdy = O \left( n^{-\beta} \log(n)^{\gamma(2-\frac{\beta}{\beta-1})} \right) \quad \text{as } n \to \infty. $$

Define $\gamma' := \gamma \left(2 - \frac{\beta}{\beta-1}\right) > 0$. The previous calculations show that we can find a bound

$$ \rho \le M(f + g + h) $$

for some $M > 0$, $f$ the uniform density on $[0, 1]^2$, $g$ a probability density on $C$ attributing uniform mass proportional to $n^{-\beta} \log(n+1)^{\gamma'}$ to each $C_n$, and $h$ a probability density on $D$ attributing uniform mass proportional to $n^{-\beta} \log(n+1)^{\gamma'}$ to each $D_{n+1}$. Thus by Lemma 3.2 it suffices to bound the quantities

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_f))], \quad \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_g))], \quad \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_h))]. $$

The first term is nothing but the uniform case, so it behaves as $\Theta(\sqrt{N})$. Let us turn to the second term. Since the sampled permutations of our reference permutations only depend on the masses attributed to each box and not the sizes of these boxes, sampled permutations from $\mu_g$ have the same law as sampled permutations from $\mu_{\beta, \gamma'}$ (see Section 2.4; $\mu_{\beta, \gamma'}$ is the permutation associated to the pre-permutation $\mu_g$). Hence by Proposition 2.4, this term behaves as $\tilde{\Theta}(N^{1/\beta})$. The third term is handled in the same way. Finally:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_\rho))] = \tilde{O}_{N \to \infty}(N^{1/\beta}). $$

### 5.3. Proof of Theorem 2.1

This section is devoted to the proof of Theorem 2.1. We thus consider $\alpha > -2$ and suppose $\rho$ is as in the theorem. Since we want an upper bound on the longest increasing subsequences, we need to find appropriate areas to bound $\rho$ on. For this define $\beta > 1$ by

$$ -\alpha = 2 - \frac{1}{\beta - 1} \quad \text{i.e.} \quad \alpha(1 - \beta) + 1 - 2\beta = -2. \qquad (5.1) $$

We use the notation of Section 2.2 for this value of $\beta$ and $\gamma = 0$. We shall bound $\rho$ on the boxes $(C_n)_{n \in \mathbb{N}^*}$ as well as on the adjacent rectangles:

$$ \text{for all } n \in \mathbb{N}^*, \quad D_n^{(1)} := [S_{n-1}, S_n] \times [S_n, 1] \quad \text{and} \quad D_n^{(2)} := [S_n, 1] \times [S_{n-1}, S_n]. $$

The sequences $(C_n)_{n \in \mathbb{N}^*}$, $(D_n^{(1)})_{n \in \mathbb{N}^*}$, $(D_n^{(2)})_{n \in \mathbb{N}^*}$ form a partition of the unit square. As in the upper bound of Theorem 2.2, we need to compute the masses attributed by $\rho$ to each of these boxes. For this notice that

$$ \text{for all } n \in \mathbb{N}^* \text{ and } (x, y) \in C_n \cup D_n^{(1)} \cup D_n^{(2)}, \quad R_n \le \text{dist}((x, y), (1, 1)) \le 2R_{n-1} $$
where $R_n := \sum_{k>n} u_k$. Hence

$$ \int_{C_n} \rho(x, y)dxdy = \Theta(n^{\alpha(1-\beta)}n^{-2\beta}) = \Theta(n^{-3}) \quad \text{as } n \to \infty $$

and

$$ \text{for } i = 1, 2, \quad \int_{D_n^{(i)}} \rho(x, y)dxdy = \Theta(n^{\alpha(1-\beta)}n^{-\beta}n^{1-\beta}) = \Theta(n^{-2}) \quad \text{as } n \to \infty $$

by (5.1). Using Lemma 3.2, it suffices to bound the quantities

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_f))], \quad \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_g))], \quad \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_h))] $$

where $f$ is the probability density on $C$ attributing uniform mass proportional to $n^{-3}$ to each $C_n$ and $g$ (resp. $h$) is the probability density on $D^{(1)}$ (resp. $D^{(2)}$) attributing uniform mass proportional to $n^{-2}$ to each $D_n^{(1)}$ (resp. $D_n^{(2)}$). Considering the reference permutation $\mu_3^\perp$ of parameter $(3, 0)$, Proposition 2.4 tells us

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_3^\perp))] = \tilde{\Theta}_{N \to \infty}(\sqrt{N}). $$

Since $\mu_3^\perp$ attributes the same masses to the boxes of its support as density $f$ attributes to its own, sampled permutations from both pre-permutons have same law (the same remark as in the upper bound of Theorem 2.2 holds; $\mu_3^\perp$ is the permutation associated to the pre-permuton $\mu_f$). Consequently:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_f^\perp))] = \tilde{\Theta}_{N \to \infty}(\sqrt{N}). $$

The case of density $g$ is similar but with a slight alteration. Indeed, considering the reference permutation $\mu_2^\perp$ of parameter $(2, 0)$, Proposition 2.4 tells us

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_2^\perp))] = \tilde{\Theta}_{N \to \infty}(\sqrt{N}). \qquad (5.2) $$

Note that $\mu_2^\perp$ attributes the same masses to the boxes of its support as density $g$ attributes to its own. A key difference here is that the rectangle boxes $D_n^{(1)}$ are not placed increasingly inside the unit square, so sampled permutations from permutation $\mu_2^\perp$ and density $g$ do not have the same law. To work around this problem, we can use an appropriate coupling. Take random i.i.d. points $X_1, \dots, X_N$ distributed under density $g$. Consider, for each $n \in \mathbb{N}^*$, the affine transformation $a_n$ mapping $D_n^{(1)}$ to $C_n$ and assemble them into a function $a$ from $\cup_{n \ge 1} D_n^{(1)}$ to $\cup_{n \ge 1} C_n$. Then the image points $a(X_1), \dots, a(X_N)$ are i.i.d. under the measure $\mu_2^\perp$. Moreover, each increasing subset of $\{X_1, \dots, X_N\}$ is mapped to an increasing subset of $\{a(X_1), \dots, a(X_N)\}$. This coupling argument shows that $\text{LIS}(\text{Sample}_N(\mu_g))$ is stochastically dominated by $\text{LIS}(\text{Sample}_N(\mu_2^\perp))$, and (5.2) then implies:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_g))] = \tilde{\mathcal{O}}_{N \to \infty}(\sqrt{N}). $$
Density $h$ is handled in the same way. Hence:

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_\rho))] = \tilde{O}\left(\sqrt{N}\right). $$

To conclude the proof of Theorem 2.1, the lower bound is obtained as a direct consequence of Lemma 3.1 using the uniform case (see the proof of Proposition 1.3).

# 6. Study of densities diverging along the diagonal

## 6.1. Lower bound of Theorem 2.3

From now on we consider a density $\rho$ satisfying the hypothesis of Theorem 2.3 for some exponent $\alpha \in ]-1, 0[$. As explained in Section 2.5, the idea is to slice the unit square into small boxes and investigate the number of sampled points appearing in appropriate increasing sequences of boxes. Let $N \in \mathbb{N}^*$ and take random i.i.d. points $X_1, \dots, X_N$ distributed under the density $\rho$. Set

$$ b_N := \lfloor N^{1/(\alpha+2)} \rfloor, $$

and define a family of $b_N^2$ identical boxes by

$$ \text{for all } (i, j) \in [1, b_N]^2, \quad C_{i,j} := \left[ \frac{(i-1)}{b_N}, \frac{i}{b_N} \right] \times \left[ \frac{(j-1)}{b_N}, \frac{j}{b_N} \right]. $$

This covering of the unit square will be useful for the upper bound, while the lower bound aimed for in this section only requires using the increasing sequence of boxes $(C_{k,k})_{k \in [1, b_N]}$. More precisely, we make use of the inequality

$$ \text{LIS}(X_1, \dots, X_N) \ge \sum_{k=1}^{b_N} \mathbf{1}_{N_k \ge 1} \qquad (6.1) $$

where each $N_k$ denotes the number of points among $X_1, \dots, X_N$ in $C_{k,k}$. Thanks to the hypothesis made on $\rho$, we can fix $\delta, \varepsilon > 0$ such that

$$ \text{for all } (x, y) \in [0, 1]^2 \text{ satisfying } |x - y| < \delta, \quad \rho(x, y) \ge \varepsilon |x - y|^\alpha. $$

Now suppose $N$ is large enough to have $b_N^{-1} < \delta$ and compute, for any $k \in [1, b_N]$:

$$ \begin{aligned} m_k &:= \int_{C_{k,k}} \rho(x, y) dx dy \ge \int_{C_{k,k}} \varepsilon |x - y|^\alpha dx dy = \varepsilon \int_0^{b_N^{-1}} dx \int_{-x}^{b_N^{-1} - x} dz |z|^\alpha \\ &= \varepsilon \int_0^{b_N^{-1}} dx \left( \frac{x^{\alpha+1}}{\alpha+1} + \frac{(b_N^{-1} - x)^{\alpha+1}}{\alpha+1} \right) = \frac{2\varepsilon}{(\alpha+1)(\alpha+2)} b_N^{-(\alpha+2)} = \Omega_{N \to \infty} \left( \frac{1}{N} \right). \end{aligned} $$

Hence there exists $\eta > 0$ such that for all $N \in \mathbb{N}^*$ and $k \in [1, b_N]$, $m_k \ge \frac{\eta}{N}$. Since $N_k$ follows a binomial law of parameter $(N, m_k)$, we deduce:

$$ \mathbf{P}(N_k = 0) = (1 - m_k)^N \le (1 - \eta/N)^N \xrightarrow{N \to \infty} e^{-\eta} < 1. $$
Consequently there exists $p_0 > 0$ such that for any large enough $N \in \mathbb{N}^*$ and all $k \in [1, b_N]$, $\mathbf{P}(N_k \ge 1) \ge p_0$. Hence for large enough $N$, using Equation (6.1):

$$ \mathbb{E}[\text{LIS}(\text{Sample}_N(\mu_\rho))] \ge \mathbb{E}\left[\sum_{k=1}^{b_N} \mathbf{1}_{N_k \ge 1}\right] \ge \sum_{k=1}^{b_N} p_0 = p_0 b_N = \frac{\Omega}{N \to \infty} (N^{1/(\alpha+2)}). $$

## 6.2. Upper bound of Theorem 2.3

We use the same notation as in the previous section, but this time we investigate the whole grid $(C_{i,j})_{i,j \in [1, b_N]}$. Say a sequence of distinct boxes $\mathcal{C} = (C_{i_1,j_1}, \dots, C_{i_n,j_n})$ is increasing whenever

$$ \text{for all } k \in [1, n-1], \quad i_k \le i_{k+1} \text{ and } j_k \le j_{k+1}. $$

When this happens, one has $n < 2b_N$. Indeed, when browsing the sequence, each coordinate increases at most $b_N - 1$ times.

Write $\mathcal{X} := \{X_1, \dots, X_N\}$. Then, for any box $C$, denote by $\mathcal{X}_C$ the set of points in $\mathcal{X}$ appearing in $C$ and, for any increasing sequence of boxes $\mathcal{C}$, denote by $\mathcal{X}_C$ the set of points in $\mathcal{X}$ appearing in some box of $\mathcal{C}$. We aim to make use of the inequality

$$ \text{LIS}(\mathcal{X}) \le \sup_{C \text{ increasing sequence of boxes}} |\mathcal{X}_C| \qquad (6.2) $$

since the family of boxes occupied by an increasing subset of points necessarily rearranges as an increasing sequence of boxes. Now, thanks to the hypothesis made on $\rho$, let $M > 0$ be such that

$$ \text{for all } (x, y) \in [0, 1]^2, \quad \rho(x, y) \le M|x - y|^\alpha. $$

Since this latter function puts more mass on the diagonal boxes than the outside ones, we have for any $i, j \in [1, b_N]$:

$$ \begin{aligned} \int_{C_{i,j}} \rho(x, y)dxdy \le \int_{C_{i,j}} M|x - y|^\alpha dxdy &\le M \int_0^{b_N^{-1}} \int_0^{b_N^{-1}} |x - y|^\alpha dxdy \\ &= \frac{2M}{(\alpha + 1)(\alpha + 2)} b_N^{-(\alpha + 2)} = \mathcal{O}_N(1/N). \end{aligned} $$

Thus there exists $M' > 0$ such that, for large enough $N$, each variable $|\mathcal{X}_{C_{i,j}}|$ is stochastically dominated by the law $\text{Bin}(N, M'/N)$. Additionally Lemma 4.1 gives, denoting by $S_N$ a random variable of law $\text{Bin}(N, M'/N)$:

$$ \mathbf{P}\left(|S_N - M'| \ge \log(N)^2 \sqrt{M'}\right) \le 2 \exp(-\psi_N) \\ \text{where } \psi_N = \frac{\log(N)^4 M'/2}{M'(1 - M'/N) + \log(N)^2 \sqrt{M'}/3} = \mathcal{O}_N(\log(N)^2). $$

This inequality, along with the aforementioned stochastic domination, implies that for large enough $N$:

$$ \mathbf{P}\left(\forall (i, j), |\mathcal{X}_{C_{i,j}}| \le M' + \log(N)^2 \sqrt{M'}\right) \ge 1 - 2b_N^2 \exp(-\psi_N). $$
Hence, using the fact that an increasing sequence of boxes contains at most $2b_N$ boxes:

$$ P \left( \text{for any increasing sequence of boxes } C, |\mathcal{X}_C| \le 2b_N \left( M' + \log(N)^2 \sqrt{M'} \right) \right) \\ \ge 1 - 2b_N^2 \exp(-\psi_N) $$

and then, by Equation (6.2):

$$ P \left( \text{LIS}(\mathcal{X}) \le 2b_N \left( M' + \log(N)^2 \sqrt{M'} \right) \right) \ge 1 - 2b_N^2 \exp(-\psi_N). $$

To conclude the proof of Theorem 2.3, it suffices to write:

$$ \mathbb{E} [ \text{LIS}(\text{Sample}_N(\mu_\rho)) ] \le 2b_N \left( M' + \log(N)^2 \sqrt{M'} \right) + 2b_N^2 N \exp(-\psi_N) = \tilde{O} \left( N^{1/(\alpha+2)} \right). $$

## Acknowledgements

The author would like to express his sincere thanks to Valentin Féray for his constant support and enlightening discussions, as well as all members of IECL who contribute to a prosperous environment for research in mathematics.

## References

[AD95] David J. Aldous and Persi Diaconis. Hammersley's interacting particle process and longest increasing subsequences. *Probability Theory and Related Fields*, 103(2):199-213, 1995. doi:10.1007/BF01204214.

[Azu67] Kazuoki Azuma. Weighted sums of certain dependent random variables. *Tohoku Mathematical Journal*, 19(3):357-367, 1967. doi:10.2748/tmj/1178243286.

[BBD$^{+22}$] Frédérique Bassino, Mathilde Bouvel, Michael Drmota, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot. Linear-sized independent sets in random cographs and increasing subsequences in separable permutations. *Combinatorial Theory*, 2(3), 2022. doi:10.5070/C62359179.

[BBF$^{+18}$] Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, and Adeline Pierrot. The Brownian limit of separable permutations. *The Annals of Probability*, 46(4):2134-2189, 2018. doi:10.1214/17-AOP1223.

[BBF$^{+20}$] Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot. Universal limits of substitution-closed permutation classes. *Journal of the European Mathematical Society*, 22(11):3565-3639, 2020. doi:10.4171/JEMS/993.

[BBF$^{+22}$] Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, Mickaël Maazoun, and Adeline Pierrot. Scaling limits of permutation classes with a finite specification: A dichotomy. *Advances in Mathematics*, 405:108513, 2022. doi:10.1016/j.aim.2022.108513.
[BDJ99] Jinho Baik, Percy Deift, and Kurt Johansson. On the distribution of the length of the longest increasing subsequence of random permutations. *Journal of the American Mathematical Society*, 12(4):1119–1178, 1999. doi:10.1090/S0894-0347-99-00307-0.

[BDMW23] Jacopo Borga, Sayan Das, Sumit Mukherjee, and Peter Winkler. Large deviation principle for random permutations. *International Mathematics Research Notices*, 2023. doi:10.1093/imrn/rnad096.

[Ben62] George Bennett. Probability inequalities for the sum of independent random variables. *Journal of the American Statistical Association*, 57(297):33–45, 1962. doi:10.1080/01621459.1962.10482149.

[Ber27] Sergueï N. Bernstein. Probability theory. *GOS. Publishing house*, 15:83, 1927.

[BP15] Nayantara Bhatnagar and Ron Peled. Lengths of monotone subsequences in a Malows permutation. *Probability Theory and Related Fields*, 161(3):719–780, 2015. doi:10.1007/s00440-014-0559-7.

[DHM17] Martin Doležal, Jan Hladky, and András Máthé. Cliques in dense inhomogeneous random graphs. *Random Structures and Algorithms*, 51(2):275–314, 2017. doi:10.1002/rsa.20715.

[Dub23] Victor Dubach. Increasing subsequences of linear size in random permutations and the robinson-schensted tableaux of permutons. 2023. arXiv:2307.05768.

[DZ95] Jean-Dominique Deuschel and Ofer Zeitouni. Limiting curves for I.I.D. records. *The Annals of Probability*, 23:852–878, 1995. doi:10.1214/aop/1176988293.

[Fri91] Alan Frieze. On the length of the longest monotone subsequence in a random permutation. *The Annals of Applied Probability*, 1(2):301–305, 1991. doi:10.1214/aoap/1177005939.

[GGKK15] Roman Glebov, Andrzej Grzesik, Tereza Klimošová, and Daniel Král. Finitely forcible graphons and permutons. *Journal of Combinatorial Theory, Series B*, 110:112–135, 2015. doi:10.1016/j.jctb.2014.07.007.

[HKM$^{+}$13] Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balázs Ráth, and Rudini Menezes Sampaio. Limits of permutation sequences. *Journal of Combinatorial Theory, Series B*, 103(1):93–113, 2013. doi:10.1016/j.jctb.2012.09.003.

[Kiw06] Marcos Kiwi. A concentration bound for the longest increasing subsequence of a randomly chosen involution. *Discrete Applied Mathematics*, 154(13):1816–1823, 2006. doi:10.1016/j.dam.2006.03.025.

[KP13] Daniel Král and Oleg Pikhurko. Quasirandom permutations are characterized by 4-point densities. *Geometric and Functional Analysis*, 23(2):570–579, 2013. doi:10.1007/s00039-013-0216-9.

[McD89] Colin McDiarmid. *On the method of bounded differences*. London Mathematical Society Lecture Note Series. Cambridge University Press, 1989. doi:10.1017/CBO9781107359949.008.
[McK19] Gweneth McKinley. Superlogarithmic cliques in dense inhomogeneous random graphs. *SIAM Journal on Discrete Mathematics*, 33(3):1772–1800, 2019. doi: 10.1137/19M1249540.

[MS11] Carl Mueller and Shannon Starr. The length of the longest increasing subsequence of a random mallows permutation. *Journal of Theoretical Probability*, 26(2):514–540, 2011. doi:10.1007/s10959-011-0364-5.

[Muk16] Sumit Mukherjee. Fixed points and cycle structure of random permutations. *Electronic Journal of Probability*, 21:1–18, 2016. doi:10.1214/16-EJP4622.

[Rom15] Dan Romik. *The Surprising Mathematics of Longest Increasing Subsequences*. Institute of Mathematical Statistics Textbooks (4). Cambridge University Press, 2015. doi:10.1017/CBO9781139872003.

[Sjö23] Jonas Sjöstrand. Monotone subsequences in locally uniform random permutations. *Annals of Probability*, 51(4):1502–1547, 2023. doi:10.1214/23-AOP1624.

[Tal95] Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. *Publications mathématiques de l'IHÉS*, 81:73–205, 1995. doi: 10.1007/BF02699376.

[VK77] Anatoli M. Vershik and Sergueï V. Kerov. Asymptotics of the Plancherel measure of the symmetric group and the limit form of Young tableaux. *Doklady akademii nauk*, 233(6):1024–1027, 1977.