# The Runsort Permuton

Noga Alon  Department of Mathematics, Princeton University, Princeton, NJ
08544, USA and Schools of Mathematics and Computer Science, Tel Aviv
University, Tel Aviv 69978, Israel<EMAIL_ADDRESS>,  Colin Defant
Department of Mathematics, Princeton University, Princeton, NJ 08540, USA
<EMAIL_ADDRESS>and  Noah Kravitz  Department of Mathematics, Princeton
University, Princeton, NJ 08540, USA<EMAIL_ADDRESS>
###### Abstract.

Suppose we choose a permutation $\pi$ uniformly at random from $S_{n}$. Let
$\mathsf{runsort}(\pi)$ be the permutation obtained by sorting the ascending
runs of $\pi$ into lexicographic order. Alexandersson and Nabawanda recently
asked if the plot of $\mathsf{runsort}(\pi)$, when scaled to the unit square
$[0,1]^{2}$, converges to a limit shape as $n\to\infty$. We answer their
question by showing that the measures corresponding to the scaled plots of
these permutations $\mathsf{runsort}(\pi)$ converge with probability $1$ to a
permuton (limiting probability distribution) that we describe explicitly. In
particular, the support of this permuton is $\\{(x,y)\in[0,1]^{2}:x\leq
ye^{1-y}\\}$.

##  1\. Introduction

Let $S_{n}$ denote the set of permutations of the set $[n]=\\{1,\ldots,n\\}$.
The _scaled plot_ of a permutation $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}$ is the
diagram showing the points $(i/n,\pi_{i}/n)$ for $i\in[n]$. The scaled plot of
$\pi$ is closely related to the probability measure $\gamma_{\pi}$ on the unit
square $[0,1]^{2}$ defined as follows. Consider a point $(x,y)\in[0,1]^{2}$.
If $(i-1)/n\leq x<i/n$ and $(\pi_{i}-1)/n\leq y<\pi_{i}/n$ for some $i\in[n]$,
then $\gamma_{\pi}$ has density $n$ at $(x,y)$; otherwise, $\gamma_{\pi}$ has
density $0$ at $(x,y)$. In other words, we divide $[0,1]^{2}$ into an $n\times
n$ grid of squares, each with side length $1/n$, and we assign each square a
constant density of either $n$ or $0$, according to whether or not the upper
right corner of the square is a point in the scaled plot of $\pi$.

Figure 1. On the left is the scaled plot of $\mathsf{runsort}(\pi)$, where
$\pi$ is a permutation chosen uniformly at random from $S_{50000}$. On the
right is the runsort permuton ${\bf R}$. The dark curve $\mathcal{C}$ is the
support of the singular continuous part of ${\bf R}$. Shading within the
region $\mathcal{C}^{+}$ indicates the density of the absolutely continuous
part of ${\bf R}$.

A _permuton_ is a probability measure $\gamma$ on the unit square $[0,1]^{2}$
that has uniform marginals, in the sense that
$\gamma([a,b]\times[0,1])=\gamma([0,1]\times[a,b])=b-a$ for all $0\leq a\leq
b\leq 1$. Note that if $\pi\in S_{n}$, then $\gamma_{\pi}$ is a permuton.
(This is why we chose to scale with density $n$.) There is a natural topology
on the space of permutons obtained by restricting the weak topology on
probability measures. This coincides with the topology induced by the metric
$\text{d}_{\square}$ defined by

$\text{d}_{\square}(\gamma_{1},\gamma_{2})=\sup_{B}\lvert\gamma_{1}(B)-\gamma_{2}(B)\rvert,$

where we take the supremum over all axis-parallel rectangles in the unit
square. There has been a great deal of recent interest in describing permutons
that arise as limits of large random permutations. Several results in this
area concern the interplay between random permutations and permutation
patterns [3, 8, 9, 10, 11, 16]. In a different direction, Dauvergne [6]
recently proved a beautiful result about permutons arising from random sorting
networks (see also [2, 7]). Our goal in this article is to describe the
permuton that emerges when we apply an operator called $\mathsf{runsort}$ to a
large random permutation.

An _ascending run_ of a permutation (henceforth called a _run_ for simplicity)
is a maximal consecutive increasing subsequence. For instance, the runs of
$351476298$ are $35$, $147$, $6$, $29$, and $8$. Given a permutation $\pi\in
S_{n}$, let $\mathsf{runsort}(\pi)$ be the permutation obtained by sorting the
runs of $\pi$ into lexicographic order. Equivalently, $\mathsf{runsort}$ sorts
the runs so that their smallest entries appear in increasing order. For
example, $\mathsf{runsort}(351476298)=147293568$. Note that $\mathsf{runsort}$
is an idempotent operator.

Motivated by the study of flattened partitions (see [5, 12, 13, 17]),
Alexandersson and Nabawanda [4] proved several interesting combinatorial
properties of $\mathsf{runsort}$. When they chose $\pi\in S_{n}$ (for large
$n$) uniformly at random and plotted the permutation $\mathsf{runsort}(\pi)$,
they observed that it tended to have a very distinctive shape (see the left
side of Figure 1). Furthermore, they noticed that the scaled plot of
$\mathsf{runsort}(\pi)$ appeared to be bounded by a certain enveloping curve,
and they asked if this curve approaches some limit curve as $n\to\infty$. In
this paper, we answer their question (in a strong form) by showing that
$\gamma_{\mathsf{runsort}(\pi)}$ converges with high probability to a specific
permuton.

Consider the curve

$\mathcal{C}=\\{(x,y)\in[0,1]^{2}:x=ye^{1-y}\\},$

and let

$\mathcal{C}^{+}=\\{(x,y)\in[0,1]^{2}:x<ye^{1-y}\\}$

be the region in the unit square above $\mathcal{C}$. We define the _runsort
permuton_ ${\bf R}$ to be the permuton given by

${\bf
R}(B)=\int_{B\cap\,\mathcal{C}^{+}}e^{y-1}\,dx\,dy+\int_{B\cap\,\mathcal{C}}(1-y)\,dy$

for every measurable set $B\subseteq[0,1]^{2}$. Thus, ${\bf R}$ is the sum of
its absolutely continuous part, which has support $\mathcal{C}^{+}$, and its
singular continuous part, which has support $\mathcal{C}$. One can easily
confirm by direct computation that ${\bf R}$ is in fact a permuton (and we
encourage the reader to do this).

Our main result is that ${\bf R}$ is the limiting distribution for the image
under $\mathsf{runsort}$ of a large random permutation.

######  Theorem 1.1 (Main Theorem).

Fix any $\varepsilon>0$, and choose $\pi^{(n)}$ uniformly at random from
$S_{n}$. Then $d_{\square}(\gamma_{\mathsf{runsort(}\pi^{(n)})},{\bf
R})<\varepsilon$ with probability tending to $1$ as $n\to\infty$.

In other words, if we randomly choose permutations $\pi^{(n)}$, then the
measures $\gamma_{\mathsf{runsort}(\pi^{(n)})}$ converge to $\bf R$ with
probability $1$.

We remark that a combination of absolutely continuous and singular continuous
parts, such as what ${\bf R}$ exhibits, seems to be rare in previous work on
permutons. In our setting, however, it is quite natural. As will become clear
later, the singular part comes from the first entries of the runs, and the
continuous part comes from the remaining entries. A random permutation in
$S_{n}$ has $(n+1)/2$ runs on average, and the reader can check that indeed
half of the total mass of ${\bf R}$ lies on the curve $\mathcal{C}$. More
surprising is that the pointwise density of ${\bf R}$ in $\mathcal{C}^{+}$
depends only on the vertical coordinate $y$. This “horizontal uniformity” is
not combinatorially obvious, and we do not know how to establish it directly
(that is, without recourse to the explicit characterization of ${\bf R}$).

In Section 2, we use martingale concentration inequalities to show that it
suffices to understand the expectation of
$\gamma_{\mathsf{runsort}(\pi^{(n)})}$. In Section 3, we treat the enveloping
curve $\mathcal{C}$ and determine the distribution of mass on it. Section 4 is
devoted to the density in the region $\mathcal{C}^{+}$. Section 5 concludes
the proof of Theorem 1.1. Finally, in Section 6, we briefly mention a possible
generalization of this type of question where our methods could be adapted.

###  1.1. Notation

We write $\pi_{i}$ for the $i$-th entry of a permutation $\pi$. We write
$\mathbb{P}[A]$ for the probability of an event $A$ and write $\mathbb{E}[X]$
for the expected value of a random variable $X$.

##  2\. Concentration of Distribution

Our task is to show that if $\pi$ is chosen randomly from $S_{n}$, then
$\gamma_{\mathsf{runsort}(\pi)}$ is suitably concentrated everywhere. The key
observation is that transposing two entries of $\pi$ has only a small effect
on $\gamma_{\mathsf{runsort}(\pi)}$, as long as $\pi$ does not have any
unusually long runs. In order to make this notion precise, we define the
following variant of $\mathsf{runsort}$: Let $\pi\in S_{n}$ be a permutation,
and let $A_{1},\ldots,A_{t}$ be the runs of $\pi$. We can break each run
$A_{k}$ into shorter subsequences $A_{k,1},\ldots,A_{k,t(k)}$, which we call
_segments_ , as follows: If $A_{k}$ has length smaller than $\log n$, then set
$t(k)=1$ and $A_{k,1}=A_{k}$; if $A_{k}$ has length greater than $\log n$,
then break it directly before every position (of $\pi$) that is an integer
multiple of $\lfloor\log n\rfloor$, so that $A_{k,\ell}$ has length exactly
$\lfloor\log n\rfloor$ for $1<\ell<t(k)$, and $A_{k,1}$ and $A_{k,t(k)}$ have
length at most $\lfloor\log n\rfloor$. We then define
$\overline{\mathsf{runsort}}(\pi)$ to be the permutation obtained by sorting
the runs $A_{k,\ell}$ into lexicographic order. Note that
$\mathsf{runsort}(\pi)=\overline{\mathsf{runsort}}(\pi)$ if all of the runs of
$\pi$ have length at most $\lfloor\log n\rfloor$; in particular, the following
lemma tells us that if $\pi$ is chosen randomly from $S_{n}$, then
$\mathsf{runsort}(\pi)=\overline{\mathsf{runsort}}(\pi)$ with probability
tending very quickly to $1$ as $n\to\infty$.

######  Lemma 2.1.

Suppose $\pi$ is chosen uniformly at random from $S_{n}$. If $n$ is
sufficiently large, then the probability that every run of $\pi$ has length at
most $\log n$ is at least $1-n^{-(\log\log n)/2}$.

###### Proof.

Let $T=\left\lfloor\log n\right\rfloor+1$. For each $i\in[n-T+1]$, the
probability that the entries of $\pi$ in positions $i,i+1,\ldots,i+T-1$ appear
in increasing order is $1/T!$. Therefore, the probability that there is a run
of $\pi$ of length at least $T$ is at most $(n-T+1)/T!$, which, by Stirling’s
Formula, is at most $n^{-(\log\log n)/2}$ for $n$ sufficiently large. ∎

######  Lemma 2.2.

Let $B=[x_{1},x_{2}]\times[y_{1},y_{2}]\subset[0,1]^{2}$ be a rectangle. Let
$\pi\in S_{n}$ be a permutation, and let $\pi^{\prime}=\pi\circ(i_{1}\,i_{2})$
be the permutation obtained from $\pi$ by swapping the entries in positions
$i_{1}$ and $i_{2}$ (that is, applying the transposition $(i_{1}\,i_{2})$).
Then
$|\gamma_{\overline{\mathsf{runsort}}(\pi)}(B)-\gamma_{\overline{\mathsf{runsort}}(\pi^{\prime})}(B)|\leq
20\log n/n$.

###### Proof.

We note that
$|\gamma_{\overline{\mathsf{runsort}}(\pi)}(B)-\gamma_{\overline{\mathsf{runsort}}(\pi^{\prime})}(B)|$,
viewed as a function of $x_{1},x_{2},y_{1},y_{2}$, clearly attains its maximum
value when $x_{1},x_{2},y_{1},y_{2}$ are all integer multiples of $1/n$, so it
suffices to prove the lemma when $B$ has this special form. In this case, we
discretize the problem by writing

(1) $\gamma_{\overline{\mathsf{runsort}}(\pi)}(B)=\frac{\\#\\{i:x_{1}n<i\leq
x_{2}n\text{ and }y_{1}n<\overline{\mathsf{runsort}}(\pi)_{i}\leq
y_{2}n\\}}{n}$

(since each point $(i,\overline{\mathsf{runsort}}(\pi)_{i})$ contributes mass
$1/n$ after rescaling), and likewise for
$\gamma_{\overline{\mathsf{runsort}}(\pi^{\prime})}(B)$. When we apply the
transposition $(i_{1}\,i_{2})$ to $\pi$, all but at most four of the segments
$A_{k,\ell}$ remain the same. Since each segment has length at most $\log n$,
we see that at most $4\log n$ entries are in these “affected” segments. It
follows that for each entry $j$ not in one of these affected runs, the
horizontal positions of $j$ in $\overline{\mathsf{runsort}}(\pi)$ and
$\overline{\mathsf{runsort}}(\pi^{\prime})$ differ by at most $4\log n$. In
particular, these horizontal positions are either both in the interval
$(x_{1}n,x_{2}n]$ or neither in this interval, unless the position in
$\overline{\mathsf{runsort}}(\pi)$ was within $4\log n$ of either $x_{1}n$ or
$x_{2}n$. So the change in the numerator on the right-hand side of (1) coming
from these entries is at most $16\log n$, and we must absorb an additional
error of $4\log n$ because we have no control over the positions of the
entries of the affected segments. ∎

(It is possible to replace the constant $20$ by $4$ in this lemma, but we do
not optimize this constant because it is irrelevant in what follows.)

We require the following martingale inequality from [14] (see also page 35 of
the book [15]).

######  Proposition 2.3 ([14, 15]).

Let $f:S_{n}\to\mathbb{R}$ be a function on permutations such that if
$\pi,\pi^{\prime}\in S_{n}$ differ by a transposition, then
$|f(\pi)-f(\pi^{\prime})|\leq z$. Then for $\pi\in S_{n}$ chosen uniformly at
random, we have

$\mathbb{P}[|f(\pi)-\mathbb{E}[f]|\geq cz]\leq 2e^{-c^{2}/(4n)}.$

We note that by following the standard proof of Azuma’s Inequality (see, e.g.,
[1, Theorem 7.2.1]) with the obvious modification needed to deal with
permutations, it is possible to improve the above exponent from $-c^{2}/(4n)$
to $-c^{2}/(2n)$, but this is not necessary for our applications.

Before applying this proposition, we fix a bit of notation. For $1\leq i,j\leq
n$, let $p_{n}(i,j)$ denote the probability that the entry $j$ is in the
$i$-th position of $\mathsf{runsort}(\pi)$ when $\pi\in S_{n}$ is chosen
uniformly at random. For
$B=[x_{1},x_{2}]\times[y_{1},y_{2}]\subseteq[0,1]^{2}$, let

$E_{n}(B)=\frac{1}{n}\sum_{\begin{subarray}{c}x_{1}n<i\leq x_{2}n,\\\
y_{1}n<j\leq y_{2}n\end{subarray}}p_{n}(i,j).$

Define the analogous quantities $\overline{p}_{n}(i,j)$ and
$\overline{E}_{n}(B)$ with $\mathsf{runsort}$ replaced by
$\overline{\mathsf{runsort}}$.

######  Lemma 2.4.

Fix any small $\varepsilon>0$, and suppose that $\pi\in S_{n}$ is chosen
uniformly at random. If $n$ is sufficiently large (as a function of
$\varepsilon$), then with probability at least $1-\varepsilon$, the
concentration inequality

$|\gamma_{\mathsf{runsort}(\pi)}(B)-E_{n}(B)|<\varepsilon$

holds simultaneously for all axis-parallel rectangles $B\subseteq[0,1]^{2}$.

###### Proof.

We make two reductions. First, write $B=[x_{1},x_{2}]\times[y_{1},y_{2}]$ and
define
$B^{\prime}=[x^{\prime}_{1},x^{\prime}_{2}]\times[y^{\prime}_{1},y^{\prime}_{2}]$
where $x^{\prime}_{1}=\lfloor nx_{1}\rfloor/n$, $x^{\prime}_{2}=\lfloor
nx_{2}\rfloor/n$, $y^{\prime}_{1}=\lfloor ny_{1}\rfloor/n$,
$y^{\prime}_{2}=\lfloor ny_{2}\rfloor/n$. Then $E_{n}(B)=E_{n}(B^{\prime})$
and

$|\gamma_{\mathsf{runsort}(\pi)}(B)-\gamma_{\mathsf{runsort}(\pi)}(B^{\prime})|\leq
2/n.$

Since this can be made smaller than $\varepsilon/3$, it suffices to show that

$|\gamma_{\mathsf{runsort}(\pi)}(B)-E_{n}(B)|<2\varepsilon/3$

for all $B$ whose vertices have coordinates that are integer multiples of
$1/n$. Note that in this case, the quantities $E_{n}(B)$ and
$\overline{E}_{n}(B)$ are precisely the expected values of
$\gamma_{\mathsf{runsort}(\pi)}(B)$ and
$\gamma_{\overline{\mathsf{runsort}}(\pi)}(B)$, respectively.

Second, we know from Lemma 2.1 that
$\mathsf{runsort}(\pi)=\overline{\mathsf{runsort}}(\pi)$ with probability at
least $1-n^{-(\log\log n)/2}$. In particular,
$|p_{n}(i,j)-\overline{p}_{n}(i,j)|\leq n^{-(\log\log n)/2}$ for all $i,j$, so
$|E_{n}(B)-\overline{E}_{n}(B)|\leq n\cdot n^{-(\log\log n)/2}$. We can make
this last quantity smaller than $\varepsilon/3$ by choosing $n$ large enough,
so it suffices to show that with probability at least $1-2\varepsilon/3$, the
inequality

$|\gamma_{\overline{\mathsf{runsort}}(\pi)}(B)-\overline{E}_{n}(B)|<\varepsilon/3$

holds simultaneously for all axis-parallel rectangles $B$ whose coordinates
are integer multiples of $1/n$.

For each such $B$ with coordinates that are integer multiples of $1/n$,
combining Lemma 2.2 and Proposition 2.3 (with $z=20\log n/n$ and
$c=\varepsilon n/60\log n$) gives that

$|\gamma_{\overline{\mathsf{runsort}}(\pi)}(B)-\overline{E}_{n}(B)|<\varepsilon/3$

with probability at least $1-e^{-\frac{\varepsilon^{2}n}{14400(\log n)^{2}}}$.
A union bound gives that with probability at least

$1-n^{4}e^{-\frac{\varepsilon^{2}n}{14400(\log n)^{2}}},$

the above inequality holds simultaneously for all $B$ with coordinates that
are integer multiples of $1/n$, and taking $n$ large guarantees that this
probability is at least $1-2\varepsilon/3$, as needed. ∎

This lemma tells us that it will suffice to work with the expectations
$E_{n}(B)$. In particular, we have reduced Theorem 1.1 to the following more
manageable-looking statement. For each $n$, define the probability measure
${\bf R}_{n}$ via ${\bf R}_{n}(B)=E_{n}(B)$ for all axis-parallel rectangles
$B\subseteq[0,1]^{2}$.

######  Theorem 2.5.

The measures ${\bf R}_{n}$ converge to ${\bf R}$ as $n$ goes to infinity.

##  3\. The Enveloping Curve

In this section, we address the “singular” behavior that comes from the first
entries of runs; as mentioned in the Introduction, this corresponds to the
mass in ${\bf R}$ that lies on the curve $\mathcal{C}$.

For $y\in[0,1]$ and $\pi\in S_{n}$, we let $L_{\pi}(y)$ denote the largest
position $i\in[n]$ such that $\pi_{i}\leq yn$ if $y\geq 1/n$, and we define
$L_{\pi}(y)=0$ if $y<1/n$. In other words, $L_{\pi}(y)$ is the smallest $i$
such that all of the entries up to $yn$ appear in the first $i$ positions.
Note that the curve $x=L_{\pi}(y)$ is the lower envelope of the scaled plot of
$\pi$. We start by computing the expected value of
$L_{\mathsf{runsort}(\pi)}(y)$ and $L_{\overline{\mathsf{runsort}}(\pi)}(y)$.

######  Proposition 3.1.

Fix $y\in[0,1]$, and suppose that $\pi\in S_{n}$ is chosen uniformly at
random. Then

$\mathbb{E}[L_{\mathsf{runsort}(\pi)}(y)]=nye^{1-y}+O(\log n)$

and

$\mathbb{E}[L_{\overline{\mathsf{runsort}}(\pi)}(y)]=nye^{1-y}+O(\log n).$

###### Proof.

We start with the first statement. For $j\in[n]$, define the random variable
$X_{j}$ by

$X_{j}(\pi)=\begin{cases}0,&\mbox{if $j$ is not the beginning of a run of
$\pi$};\\\ k,&\mbox{if $j$ is the beginning of a run of length $k$ of
$\pi$}.\end{cases}$

It follows from the definition of $\mathsf{runsort}$ that

$\sum_{j\leq yn}X_{j}(\pi)-m(\pi)<L_{\mathsf{runsort}(\pi)}(y)\leq\sum_{j\leq
yn}X_{j}(\pi),$

where $m(\pi)$ is the maximum length of a run in $\pi$. We know from Lemma 2.1
that $m(\pi)\leq\log n$ with probability at least $1-n^{-(\log\log n)/2}$.
Since $m(\pi)\leq n$ for all $\pi\in S_{n}$, we have

$\mathbb{E}[L_{\mathsf{runsort}(\pi)}(y)]\geq\sum_{j\leq
yn}\mathbb{E}[X_{j}(\pi)]-(1-n^{-(\log\log n)/2})\log n-n\cdot n^{-(\log\log
n)/2}.$

Hence,

$\mathbb{E}[L_{\mathsf{runsort}(\pi)}(y)]=\sum_{j\leq
yn}\mathbb{E}[X_{j}(\pi)]+O(\log n).$

Consider $j\in[n]$ with $j\leq yn$, and let $r$ be such that $\pi_{r}=j$. We
wish to estimate the probability that $X_{j}(\pi)\geq k+1$ for each $k\geq 0$.
If $k>\log n$, then $\mathbb{P}[X_{j}(\pi)\geq k+1]<n^{-(\log\log n)/2}$ by
Lemma 2.1 (and this contribution will turn out to be negligible). To handle
the case $k\leq\log n$, note that we have $X_{j}(\pi)\geq k+1$ if and only if
the following both hold:

  * •

Either $r=1$, or $2\leq r\leq n-k$ and $\pi_{r-1}>j$;

  * •

$j<\pi_{r+1}<\pi_{r+2}<\cdots<\pi_{r+k}$.

Therefore,

$\mathbb{P}[X_{j}(\pi)\geq k+1]=\frac{1}{n\cdot
k!}\cdot\frac{\binom{n-j}{k}}{\binom{n-1}{k}}+\frac{n-k-1}{n\cdot
k!}\cdot\frac{\binom{n-j}{k+1}}{\binom{n-1}{k+1}}.$

Note that the first term is at most $1/n$. To estimate the second term, we
write

$\displaystyle\frac{\binom{n-j}{k+1}}{\binom{n-1}{k+1}}$
$\displaystyle=\prod_{t=0}^{k}\frac{n-j-t}{n-1-t}$
$\displaystyle=\prod_{t=0}^{k}\left(1-\frac{j}{n}+\frac{n-j-
jt}{n(n-1-t)}\right)$
$\displaystyle=\left(1-\frac{j}{n}+O\left(\frac{t+1}{n}\right)\right)^{k+1}$
$\displaystyle=(1-j/n)^{k+1}+O((k+1)^{2}/n),$

where the last bound uses the fact that $k\leq\log n$. Combining these
estimates yields

$\displaystyle\mathbb{P}[X_{j}(\pi)\geq k+1]$
$\displaystyle=O(1/n)+\frac{1}{k!}(1-(k+1)/n)\left((1-j/n)^{k+1}+O((k+1)^{2}/n)\right)$
$\displaystyle=\frac{(1-j/n)^{k+1}}{k!}+O(1/n),$

again using $k\leq\log n$. So

$\displaystyle\mathbb{E}[X_{j}(\pi)]$
$\displaystyle=\sum_{k=0}^{n-1}\mathbb{P}[X_{j}(\pi)\geq k+1]$
$\displaystyle=\sum_{k=0}^{\left\lfloor\log
n\right\rfloor}\left(\frac{(1-j/n)^{k+1}}{k!}+O(1/n)\right)+O\left(n\cdot
n^{-(\log\log n)/2}\right)$
$\displaystyle=(1-j/n)(e^{1-j/n}+O(1/\left\lfloor\log n\right\rfloor!))+O(\log
n/n)+O\left(n\cdot n^{-(\log\log n)/2}\right)$
$\displaystyle=(1-j/n)e^{1-j/n}+O(\log n/n).$

Summing over $j\leq yn$ gives

$\displaystyle\sum_{j\leq yn}\mathbb{E}[X_{j}(\pi)]$
$\displaystyle=\sum_{j\leq yn}\left((1-j/n)e^{1-j/n}+O(\log n/n)\right)$
$\displaystyle=n\int_{0}^{y}(1-t)e^{1-t}\,dt+O(1)+O(\log n)$
$\displaystyle=nye^{1-y}+O(\log n),$

and we conclude that

$\mathbb{E}[L_{\mathsf{runsort}(\pi)}(y)]=nye^{1-y}+O(\log n).$

For the statement about $\mathbb{E}[L_{\overline{\mathsf{runsort}}(\pi)}(y)]$,
note that
$L_{\overline{\mathsf{runsort}}(\pi)}(y)=L_{\mathsf{runsort}(\pi)}(y)$ with
probability at least $1-n^{-(\log\log n)/2}$ by Lemma 2.1; when these
quantities do differ, they differ by at most $n$, and $n\cdot n^{-(\log\log
n)/2}$ can be absorbed into the error term. ∎

In order to apply Proposition 2.3, we need an analogue of Lemma 2.2. As in the
previous section, it is more convenient to work with
$\overline{\mathsf{runsort}}$.

######  Lemma 3.2.

Fix $y\in[0,1]$. Let $\pi\in S_{n}$ be a permutation, and let
$\pi^{\prime}=\pi\circ(i_{1}\,i_{2})$ be the permutation obtained from $\pi$
by swapping the entries in positions $i_{1}$ and $i_{2}$. Then

$|L_{\overline{\mathsf{runsort}}(\pi)}(y)-L_{\overline{\mathsf{runsort}}(\pi^{\prime})}(y)|\leq
9\log n.$

###### Proof.

Write $\\{A_{k,\ell}\\}$ and $\\{A^{\prime}_{k,\ell}\\}$ for the sets of
segments of $\pi$ and $\pi^{\prime}$, respectively. As in the proof of Lemma
2.2, we note that multiplying $\pi$ on the right by the transposition
$(i_{1}\,i_{2})$ affects at most four of the segments $A_{k,\ell}$, which
together contain at most $4\log n$ entries. In particular, for each entry $j$
not in one of these affected segments, the horizontal positions of $j$ in
$\overline{\mathsf{runsort}}(\pi)$ and
$\overline{\mathsf{runsort}}(\pi^{\prime})$ differ by at most $4\log n$.
Hence, the first $L_{\overline{\mathsf{runsort}}(\pi)}(y)+4\log n$ entries of
$\overline{\mathsf{runsort}}(\pi^{\prime})$ certainly contain all of the
entries up to $yn$ except for possibly some of the $4\log n$ entries in the
affected segments. These missing small entries (if any exist) are contained in
at most four segments $A^{\prime}_{k,\ell}$ of $\pi^{\prime}$, and these
segments must appear in $\overline{\mathsf{runsort}}(\pi^{\prime})$ directly
after the last run that includes all smaller entries. Since all runs have
length at most $\log n$, we see that all of the entries up to $yn$ are among
the first

$L_{\overline{\mathsf{runsort}}(\pi)}(y)+4\log n+\log n+4\log
n=L_{\overline{\mathsf{runsort}}(\pi)}(y)+9\log n$

entries of $\overline{\mathsf{runsort}}(\pi^{\prime})$; that is,
$L_{\overline{\mathsf{runsort}}(\pi^{\prime})}(y)\leq
L_{\overline{\mathsf{runsort}}(\pi)}(y)+9\log n$. By the same argument, we
have $L_{\overline{\mathsf{runsort}}(\pi)}(y)\leq
L_{\overline{\mathsf{runsort}}(\pi^{\prime})}(y)+9\log n$. ∎

Following the same strategy as in the previous section, we obtain a
concentration inequality for $L_{\mathsf{runsort}(\pi)}(y)$.

######  Lemma 3.3.

Fix $y\in[0,1]$, and suppose that $\pi\in S_{n}$ is chosen uniformly at
random. Then with probability at least $1-2n^{-(\log\log n)/2}$, we have the
concentration inequality

$|L_{\mathsf{runsort}(\pi)}(y)-nye^{1-y}|=O(\sqrt{n}(\log n)^{2}).$

###### Proof.

Applying Proposition 2.3 with $z=9\log n$ and $c=2\sqrt{n}\log n$ gives that
with probability at least $1-2e^{-(\log n)^{2}}$, the quantity
$L_{\overline{\mathsf{runsort}}(\pi)}(y)$ differs from its expectation by at
most $18\sqrt{n}(\log n)^{2}$. Plugging in the estimate from Proposition 3.1,
we have that

$|L_{\overline{\mathsf{runsort}}(\pi)}-nye^{1-y}|=O(\sqrt{n}(\log n)^{2})$

with probability at least $1-2e^{-(\log n)^{2}}$. Since
$\mathsf{runsort}(\pi)=\overline{\mathsf{runsort}}(\pi)$ with probability at
least $1-n^{-(\log\log n)/2}$ (by Lemma 2.1), we see that in fact
$|L_{\overline{\mathsf{runsort}}(\pi)}-nye^{1-y}|=O(\sqrt{n}(\log n)^{2})$
holds with probability at least

$1-2e^{-(\log n)^{2}}-n^{-(\log\log n)/2}>1-2n^{-(\log\log n)/2}.\qed$

When the entry $j=yn$ is the beginning of a run of $\pi$, the position of $j$
in $\mathsf{runsort}(\pi)$ is precisely $L_{\mathsf{runsort}(\pi)}(y)$. Thus,
the previous lemma tells us that in the scaled plot of
$\mathsf{runsort}(\pi)$, the beginnings of runs cluster around the curve
$\mathcal{C}$. To make this precise, let $q_{n}(i,j)$ denote the probability
that the entry $j$ is the beginning of a run of $\pi$ and is in the $i$-th
position of $\mathsf{runsort}(\pi)$ when $\pi\in S_{n}$ is chosen uniformly at
random. (Here, $q_{n}(i,j)$ differs from $p_{n}(i,j)$ in that the former looks
at only the first entry of each run and the latter looks at all entries.) We
obtain an estimate on the distribution of $q_{n}(i,j)$ for fixed $j$.

######  Lemma 3.4.

There exists a constant $C>0$ such that the following holds for all
$y\in[0,1]$:

$\left|\sum_{|i-nye^{1-y}|\leq C\sqrt{n}(\log
n)^{2}}q_{n}(i,yn)-(1-y+1/n)\right|\leq 2n^{-(\log\log n)/2}$

and

$\sum_{|i-nye^{1-y}|>C\sqrt{n}(\log n)^{2}}q_{n}(i,yn)\leq 2n^{-(\log\log
n)/2}.$

###### Proof.

Recall that the entry $yn$ is the beginning of a run of $\pi$ with probability
$(n-yn+1)/n$. This implies that $\sum_{i\in[n]}q_{n}(i,yn)=1-y+1/n$. Both
statements now follow from Lemma 3.3. ∎

Let us summarize in words what this lemma tells us about the contribution to
the measures ${\bf R}_{n}$ (and eventually also $\bf R$) from the beginnings
of runs: This contribution is concentrated close to the curve $\mathcal{C}$,
and the “weighting” in the $y$-direction is $(1-y)\,dy$. We will make these
observations precise in Section 5.

Finally, we record a version of this result that will be convenient in the
next section.

######  Lemma 3.5.

There exists a constant $C>0$ such that the following holds for all
$y\in[0,1]$: If $\ell>C\sqrt{n}(\log n)^{2}$ and $k\geq yn$ are integers, then
$q_{n}(nye^{1-y}-\ell,k)\leq 2n^{-(\log\log n)/2}.$

###### Proof.

This follows from Lemma 3.3 and the observation that $y\leq y^{\prime}$
implies that $L_{\mathsf{runsort}(\pi)}(y)\leq
L_{\mathsf{runsort}(\pi)}(y^{\prime})$ for every $\pi$. ∎

##  4\. The Interior Density

We now compute the limiting density for the non-singular part of the permuton.
Suppose that $\pi$ is a random permutation of length $n$. Recall that
$p_{n}(i,j)$ denotes the probability that the entry $j$ is in the $i$-th
position of $\mathsf{runsort}(\pi)$. In the previous section, we analyzed the
case where the entry $j$ is the beginning of a run of $\pi$, so we focus on
the remaining case: Let $p^{\prime}_{n}(i,j)=p_{n}(i,j)-q_{n}(i,j)$ denote the
probability that the entry $j$ is in the $i$-th position of
$\mathsf{runsort}(\pi)$ and is not the beginning of a run of $\pi$. We will be
interested in the situation where $i=xn$ and $j=yn$ for fixed $x,y\in(0,1)$,
where the point $(x,y)$ lies in $\mathcal{C}^{+}$ (i.e., strictly above
$\mathcal{C}$) and $n$ tends to infinity. By the results of the previous
section, we know that $p^{\prime}_{n}(i,j)$ is very close to $p_{n}(i,j)$ in
this regime. Whenever we use $xn$ or $yn$ as an input for a function that
takes integer values (such as $p_{n}$, $p_{n}^{\prime}$, or $q_{n}$), we
really mean $\left\lceil xn\right\rceil$ and $\left\lceil yn\right\rceil$; we
simply omit the ceiling symbols to avoid a typhoon of ceiling symbols.

Fix $n$ and $i,j\in[n]$ with $i>1$, and suppose that we obtain $\pi$ by first
picking a random permutation $\pi^{\prime}$ on $[n]\setminus\\{j\\}$ and then
inserting the entry $j$ in a random position. Let $k$ denote the entry in the
$(i-1)$-th position of $\mathsf{runsort}(\pi)$. The following two descriptions
define the same event:

  * •

The entry $j$ is in the $i$-th position of $\mathsf{runsort}(\pi)$ and is not
the beginning of a run of $\pi$.

  * •

$k<j$, and the entry $j$ was inserted directly after the entry $k$ in $\pi$.

The probability of the first bullet point occurring is (by definition)
$p^{\prime}_{n}(i,j)$, and the probability of the second bullet point
occurring is

$\frac{1}{n}\sum_{1\leq k<j}p_{n-1}(i-1,k)=\frac{1}{n}\left(1-\sum_{j\leq
k\leq n-1}p_{n-1}(i-1,k)\right).$

Putting these together, we find that

(2) $p^{\prime}_{n}(i,j)=\frac{1}{n}\left(1-\sum_{j\leq k\leq
n-1}p_{n-1}(i-1,k)\right).$

Since $p_{n}(i,j)$ and $p^{\prime}_{n}(i,j)$ are very close, we incur a very
small error if we replace $p_{n-1}(i-1,k)$ with $p^{\prime}_{n-1}(i-1,k)$ on
the right-hand side; we will address this carefully below. So, up to this
small error, $p^{\prime}_{n}(i,j)$ is equal to

$\frac{1}{n}\left(1-\sum_{j\leq k\leq n-1}p^{\prime}_{n-1}(i-1,k)\right).$

Note that we have the boundary conditions $p^{\prime}_{n}(1,j)=0$ for all $j$
and $p^{\prime}_{n}(i,n)=1/n$ for $1<i<n$. We now define the quantities
$\widetilde{p}_{n}(i,j)$ recursively via

$\widetilde{p}_{n}(i,j)=\frac{1}{n}\left(1-\sum_{j\leq k\leq
n-1}\widetilde{p}_{n-1}(i-1,k)\right),$

with the same boundary conditions $\widetilde{p}_{n}(1,j)=0$ and
$\widetilde{p}_{n}(i,n)=1/n$ for $1<i<n$. We will see that
$p^{\prime}_{n}(xn,yn)$ and $\widetilde{p}_{n}(xn,yn)$ are very close as long
as $n$ is sufficiently large (with respect to $(x,y)$).

By repeatedly applying the recurrence relation for $\widetilde{p}$, we can
express $\widetilde{p}_{n}(i,j)$ as a sum of terms involving
$\widetilde{p}_{n-i+1}(1,k)$ (for $j\leq k\leq n-i+1$) and
$\widetilde{p}_{n-r}(i-r,n-r)$ (for $i-r>1$ and $j\leq k\leq n-r$), together
with some constant terms:

  * •

The terms $\widetilde{p}_{n-i+1}(1,k)$ vanish by our boundary conditions.

  * •

Each term $\widetilde{p}_{n-r}(i-r,n-r)$ is equal to $1/(n-r)$ (by our
boundary conditions) and appears $\binom{n-j+r-1}{r-1}$ times (by stars and
bars), always weighted by $\frac{1}{n(n-1)\cdots(n-r+1)}$ and carrying the
sign $(-1)^{r}$. Here, $r$ ranges from $1$ to $\min\\{n-j,i-2\\}$; call the
latter quantity $M$.

  * •

Each constant term $\frac{(-1)^{s}}{n(n-1)\cdots(n-s)}$ appears
$\binom{n-j}{s}$ times, where $s$ ranges from $0$ to $M$.

Putting everything together, we arrive at the explicit formula

$\widetilde{p}_{n}(i,j)=\sum_{r=1}^{M}\frac{(-1)^{r}}{n(n-1)\cdots(n-r)}\binom{n-j+r-1}{r-1}+\sum_{s=0}^{M}\frac{(-1)^{s}}{n(n-1)\cdots(n-s)}\binom{n-j}{s}.$

We remark that the only dependence on $i$ is contained in the value of $M$. In
the regime $i\geq n-j+2$, we see that $M$ (and hence also
$\widetilde{p}_{n}(i,j)$) is completely independent of $i$; this is a hint of
the horizontal uniformity alluded to in the Introduction. For $i=xn$ and
$j=yn$ with $n$ tending to infinity, the second sum (call it $S_{2}$) will
contribute the main term, and the first sum (call it $S_{1})$ will contribute
a negligible error. Note that in this setting, $M$ is asymptotically a
positive constant multiple of $n$ (since $x,y\in(0,1)$).

We begin with the first sum. Expanding the binomial coefficient gives

$S_{1}=\sum_{r=1}^{M}\frac{(-1)^{r}}{(r-1)!}\cdot\frac{1}{n(n-1)}\cdot\frac{(n-j+r-1)(n-j+r-2)\cdots(n-j+1)}{(n-2)(n-3)\cdots(n-r)}.$

Writing $n-j=(1-y)n$, we estimate

$\frac{n-j+t}{n-r+t-1}=1-\frac{j}{n}+\frac{j(t-r-1)+n(r-1)}{n(n-r+t-1)}=(1-y)+O(r/n)$

uniformly in $n,r,t$ (so the implied constant depends only on $(x,y)$). Then

$\displaystyle S_{1}$
$\displaystyle=\frac{1}{n(n-1)}\sum_{r=1}^{M}\frac{(-1)^{r}}{(r-1)!}\left((1-y)^{r-1}+O\left(r2^{r-1}/n\right)\right)$
$\displaystyle=\frac{-e^{y-1}}{n^{2}}+O(1/n^{3}),$

which is $o(1/n)$.

Performing the analogous computation for the second sum, we find that

$\displaystyle S_{2}$
$\displaystyle=\sum_{s=0}^{M}\frac{(-1)^{s}}{s!}\cdot\frac{1}{n}\cdot\frac{(n-j)(n-j-1)\cdots(n-j-s+1)}{(n-1)(n-2)\cdots(n-s)}$
$\displaystyle=\frac{1}{n}\sum_{s=0}^{M}\frac{(-1)^{s}}{s!}((1-y)^{s}+O((s+1)2^{s+1}/n))$
$\displaystyle=\frac{e^{y-1}}{n}+O(1/n^{2}).$

In summary, we have established the following proposition.

######  Proposition 4.1.

Fix $x,y\in(0,1)$ such that $(x,y)\in\mathcal{C}^{+}$. Then

$\widetilde{p}_{n}(xn,yn)=\frac{e^{y-1}}{n}+O(1/n^{2}),$

where the implicit constant depends only on $(x,y)$.

It remains to bound the difference between $\widetilde{p}$ and $p^{\prime}$.
This consists of keeping track of the error terms $q=p-p^{\prime}$ when we
iterate the recurrence (2). At the $\ell$-th stage, the number of terms
$p_{n-\ell}$ is $\binom{(1-y)n}{\ell}$ (by stars and bars), and each such term
is scaled (up to a sign) by $\frac{1}{n(n-1)\cdots(n-\ell+1)}$. Let $Q$ be the
maximum of the error terms $q$ (which are certainly nonnegative). By the
triangle inequality, we may ignore the signs of the errors, and we find that

$|p^{\prime}_{n}(xn,yn)-\widetilde{p}_{n}(xn,yn)|\leq
Q\sum_{\ell=1}^{(1-y)n}\binom{(1-y)n}{\ell}\frac{1}{n(n-1)\cdots(n-\ell+1)}\leq
Q\sum_{\ell=1}^{(1-y)n}\frac{1}{\ell!}=O(Q).$

We now bound $Q$.

######  Lemma 4.2.

Fix $x,y\in(0,1)$ such that $(x,y)\in\mathcal{C}+$. If $n$ is sufficiently
large (depending on $(x,y)$), then the following holds: For all
$1\leq\ell\leq\min\\{xn-1,(1-y)n\\}$ and all $yn\leq k\leq n-\ell$, we have

$q_{n-\ell}(xn-\ell,k)\leq 2(yn)^{-(\log\log(yn))/2}.$

###### Proof.

We wish to apply Lemma 3.5 with $n$ replaced by $n-\ell$. Let
$\varepsilon=ye^{1-y}-x$ (which is strictly positive). First, we check that

$k\geq yn\geq y(n-\ell).$

Second, we wish to show that
$xn-\ell<(n-\ell)ye^{1-y}-C\sqrt{n-\ell}(\log(n-\ell))^{2}$ (where $C$ is the
constant from Lemma 3.5); this inequality rearranges to

$\varepsilon n+\ell(1-ye^{1-y})>C\sqrt{n-\ell}(\log(n-\ell))^{2}.$

The term $1-ye^{1-y}$ is nonnegative, and we see that the inequality holds as
long as $n$ is sufficiently large (depending on $y$ and $\varepsilon$). So we
can apply Lemma 3.5, which tells us that

$q_{n-\ell}(xn-\ell,k)\leq 2(n-\ell)^{-(\log\log(n-\ell))/2}.$

The right-hand side is an increasing function of $\ell$, so the bound
$\ell\leq(1-y)n$ gives the desired inequality. ∎

The previous lemma implies that $Q\leq 2(yn)^{-(\log\log(yn))/2}$ (which is
certainly $O(1/n^{2})$) for $n$ sufficiently large, so we can deduce the main
result of this section. (For $y=1$, recall from above that
$p^{\prime}_{n}(xn,n)=1/n$.)

######  Lemma 4.3.

Fix $x,y\in(0,1]$ such that $(x,y)\in\mathcal{C}^{+}$. Then

$p^{\prime}_{n}(xn,yn)=\frac{e^{y-1}}{n}+O(1/n^{2}),$

where again the implied constant depends only on $(x,y)$.

Let us summarize in words what this lemma tells us about the contribution to
the measures ${\bf R}_{n}$ (and eventually also ${\bf R}$) from the entries
that are not the beginnings of runs: In $\mathcal{C}^{+}$, this contribution
gives a density $e^{1-y}\,dx\,dy$ at the point $(x,y)$; note that this is
independent of $x$. We have said nothing about the contribution below
$\mathcal{C}$; that this contribution is $0$ follows quickly from Lemma 3.3,
but in fact we will give an alternative argument in the next section.

##  5\. Putting Everything Together

We finally prove Theorem 2.5, which implies Theorem 1.1. The main idea is that
we have already accounted for 100% of the mass of ${\bf R}$ in our discussions
in the previous two sections; this means that there will not be any mass below
the curve $\mathcal{C}$ and that we do not need to worry about additional
contributions very close to $\mathcal{C}$ from entries that are not the
beginnings of runs.

For each axis-parallel rectangle $B\subseteq[0,1]^{2}$, it follows from Lemmas
3.4 and 4.3 that

$\liminf_{n\to\infty}{\bf
R}_{n}(B)\geq\int_{B\cap\,\mathcal{C}^{+}}e^{y-1}\,dx\,dy+\int_{B\cap\,\mathcal{C}}(1-y)\,dy={\bf
R}(B).$

Now fix an axis-parallel rectangle $B_{1}\subseteq[0,1]^{2}$. Choose a tiling
of $[0,1]^{2}$ by axis-parallel rectangles $B_{1},\ldots,B_{5}$ (such a tiling
certainly exists). We have

$1=\limsup_{n\to\infty}{\bf
R}_{n}([0,1]^{2})=\sum_{a=1}^{5}\limsup_{n\to\infty}{\bf
R}_{n}(B_{a})\geq\sum_{a=1}^{5}\liminf_{n\to\infty}{\bf
R}_{n}(B_{a})\geq\sum_{a=1}^{5}{\bf R}(B_{a})={\bf R}([0,1]^{2})=1.$

These inequalities must all be equalities, so $\lim\limits_{n\to\infty}{\bf
R}_{n}(B_{1})$ exists and equals ${\bf R}(B_{1})$. As $B_{1}$ was arbitrary,
this completes the proof of Theorem 2.5.

##  6\. A Generalized Setting

In this brief concluding section, we mention a setting in which the ideas
presented earlier—especially those concerning the concentration inequalities
derived in Section 3—still hold.

The _standardization_ of a sequence of $n$ distinct integers is the
permutation in $S_{n}$ that has the same relative order as the sequence. For
example, the standardization of $4917$ is $2413$. Let
$\mathcal{F}\subseteq\bigcup_{n\geq 0}S_{n}$ be a family of permutations, and
let $\mathcal{F}_{n}=\mathcal{F}\cap S_{n}$. Assume that every permutation
obtained by taking the standardization of a prefix of a permutation in
$\mathcal{F}$ is also in $\mathcal{F}$. Let us also assume that $\mathcal{F}$
contains the permutation $1\in S_{1}$ and that there is some constant $c>1$
such that $\lvert\mathcal{F}_{n}\rvert<n!/c^{n}$ for all sufficiently large
$n$.

We can use the family $\mathcal{F}$ to split an arbitrary permutation $\pi\in
S_{n}$ into subsequences as follows. Let $\pi_{[a,b]}$ denote the subsequence
of $\pi$ consisting of entries in positions $a,a+1,\ldots,b$, and let
$\overline{\pi}_{[a,b]}$ be the standardization of $\pi_{[a,b]}$. Set
$k_{0}=1$. Then let $k_{1}$ be the smallest integer that is greater than
$k_{0}$ and satisfies $\overline{\pi}_{[k_{0},k_{1}]}\not\in\mathcal{F}$; we
make the convention that $k_{1}=n+1$ if $\pi\in\mathcal{F}$. If $k_{1}\neq
n+1$, let $k_{2}$ be the smallest integer that is greater than $k_{1}$ and
satisfies $\overline{\pi}_{[k_{1},k_{2}]}\not\in\mathcal{F}$; we make the
convention that $k_{2}=n+1$ if $\overline{\pi}_{[k_{1},n]}\in\mathcal{F}$.
Continue defining integers $k_{i}$ in this greedy fashion until reaching a
step at which $k_{r}=n+1$. Note that
$\overline{\pi}_{[k_{0},k_{1}-1]},\overline{\pi}_{[k_{1},k_{2}-1]},\ldots,\overline{\pi}_{[k_{r-1},k_{r}-1]}$
all belong to the family $\mathcal{F}$. Let us call the subsequences
$\pi_{[k_{0},k_{1}-1]},\pi_{[k_{1},k_{2}-1]},\ldots,\pi_{[k_{r-1},k_{r}-1]}$
the _$\mathcal{F}$ -runs_ of $\pi$. Define
$\mathcal{F}\text{-}\mathsf{sort}(\pi)$ to be the permutation obtained by
sorting the $\mathcal{F}$-runs of $\pi$ so that their minimal entries appear
in increasing order. Note that $\mathcal{F}\text{-}\mathsf{sort}$ is the same
as $\mathsf{runsort}$ when $\mathcal{F}$ is the family of increasing
permutations (consisting of one permutation of each length).

Figure 2. The scaled plots of
$\mathcal{F}^{\text{ddes}}\text{-}\mathsf{sort}(\pi)$ (left) and
$\mathcal{F}^{\text{val}}\text{-}\mathsf{sort}(\pi)$ (right), where $\pi$ is a
permutation chosen uniformly at random from $S_{50000}$.

Suppose $n$ is large. If we choose $\pi\in S_{n}$ uniformly at random, then
the minimal entries of the $\mathcal{F}$-runs of $\pi$ should concentrate
along a certain curve after we apply $\mathcal{F}\text{-}\mathsf{sort}$ to
$\pi$. It should be possible to make this concentration statement precise
using the ideas from Section 3; however, determining exactly what the curve is
could be very difficult. Here, we simply provide some images illustrating how
this phenomenon might look in specific examples.

A _double descent_ of a permutation $\pi\in S_{n}$ is an index
$i\in\\{2,\ldots,n-1\\}$ such that $\pi_{i-1}>\pi_{i}>\pi_{i+1}$. A _valley_
of $\pi$ is an index $i\in\\{2,\ldots,n-1\\}$ such that
$\pi_{i-1}>\pi_{i}<\pi_{i+1}$. Let $\mathcal{F}^{\text{ddes}}$ be the family
of permutations with no double descents, and let $\mathcal{F}^{\text{val}}$ be
the family of permutations with no valleys. Figure 2 shows the scaled plots of
$\mathcal{F}^{\text{ddes}}\text{-}\mathsf{sort}(\pi)$ and
$\mathcal{F}^{\text{val}}\text{-}\mathsf{sort}(\pi)$, where $\pi$ is a
permutation chosen uniformly at random from $S_{50000}$.

One possibility for future research is the characterization of the limiting
behavior of $\mathcal{F}\text{-}\mathsf{sort}(\pi)$ ($\pi\in S_{n}$ chosen
uniformly at random) for various specific choices of $\mathcal{F}$. Perhaps
even more interesting would be the determination of more general properties
such as the existence of a limiting permuton and conditions on $\mathcal{F}$
that guarantee some form of “horizontal uniformity.” One could also consider
the limiting behavior of $\mathsf{runsort}(\pi)$ when $\pi\in S_{n}$ is chosen
non-uniformly, e.g., according to the Mallows distribution.

## Acknowledgements

The first author is supported in part by NSF grant DMS–1855464, BSF grant
2018267, and the Simons Foundation. The second author is supported by an NSF
Graduate Research Fellowship (grant DGE–1656466) and a Fannie and John Hertz
Foundation Fellowship. The third author is supported by an NSF Graduate
Research Fellowship (grant DGE–2039656). We are grateful to Ryan Alweiss and
Peter Winkler for helpful conversations.

## References

  * [1] N. Alon and J. H. Spencer, _The Probabilistic Method, Fourth Edition_. Wiley (2016).
  * [2] O. Angel, A. Holroyd, D. Romik, and B. Virág, Random sorting networks. _Adv. Math._ , 215 (2007), 839–868.
  * [3] M. Atapour and N. Madras, Large deviations and ratio limit theorems for pattern-avoiding permutations. _Combin. Probab. Comput._ , 23 (2014), 161–200.
  * [4] P. Alexandersson and O. Nabawanda, Peaks are preserved under run-sorting. _Enumer. Combin. Appl._ , 2 (2022).
  * [5] D. Callan, Pattern avoidance in “flattened” partitions. _Discrete Math._ , 309 (2009), 4187–4191.
  * [6] D. Dauvergne, The Archimedean limit of random sorting networks. _Preprint_ arXiv:1802.08934 (2018).
  * [7] D. Dauvergne and B. Virág, Circular support in random sorting networks. _Trans. Amer. Math. Soc._ , 373 (2020), 1529–1553.
  * [8] T. Dokos and I. Pak, The expected shape of random doubly alternating Baxter permutations. _Online J. Anal. Comb._ , 9 (2014).
  * [9] R. Glebov, A. Grzesik, T. Klimošová, and D. Král’, Finitely forcible graphons and permutons. _J. Combin. Theory Ser. B_ , 110 (2015), 112–135.
  * [10] C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Ráth, and R. M. Sampaio, Limits of permutation sequences. _J. Combin. Theory Ser. B_ , 103 (2013), 93–113.
  * [11] R. Kenyon, D. Král’, C. Radin, P. Winkler, Permutations with fixed pattern densities. _Random Structures Algorithms_ , 56 (2020), 220–250.
  * [12] T. Mansour and M. Shattuck, Pattern avoidance in flattened permutations. _Pure Math. Appl. (PU.M.A.)_ , 22 (2011), 75–86
  * [13] T. Mansour, M. Shattuck, and S. Wagner, Counting subwords in flattened partitions of sets. _Discrete Math._ , 338 (2015), 1989–2005.
  * [14] B. Maurey, Construction de suites symétriques. _C. R. Math. Acad. Sci Paris, Sér. A_ , 288 (1979), 679–681.
  * [15] V. Milman and G. Schechtman, _Asymptotic Theory of Infinite Dimensional Normed Spaces_. Springer (2016).
  * [16] S. Miner and I. Pak, The shape of random pattern-avoiding permutations. _Adv. Appl. Math._ , 55 (2014), 86–130.
  * [17] O. Nabawanda, F. Rakotondrajao, and A. S. Bamunoba, Run distribution over flattened partitions. _J. Integer Seq._ , 23 (2020).