# Density Maximizers of Layered Permutations

Adam Kabela, Daniel Král, Jonathan A Noel, Théo Pierron

► To cite this version:

Adam Kabela, Daniel Král, Jonathan A Noel, Théo Pierron. Density Maximizers of Layered Permutations. The Electronic Journal of Combinatorics, 2022, 29 (3), 10.37236/10781. hal-03773074

HAL Id: hal-03773074

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

Submitted on 13 Mar 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
# Density Maximizers of Layered Permutations*

Adam Kabela†

Faculty of Applied Sciences
University of West Bohemia
Czech Republic

kabela@kma.zcu.cz

Daniel Král’

Faculty of Informatics
Masaryk University
Czech Republic

dkral@fi.muni.cz

Jonathan A. Noel‡

Department of Mathematics and Statistics
University of Victoria
Canada

noelj@uvic.ca

Théo Pierron†

LIRIS UMR CNRS
Université Lyon 1
France

theo.pierron@univ-lyon1.fr

Submitted: Oct 7, 2021; Accepted: Aug 9, 2022; Published: Sep 9, 2022

© The authors. Released under the CC BY-ND license (International 4.0).

## Abstract

A permutation is layered if it contains neither 231 nor 312 as a pattern. It is known that, if $\sigma$ is a layered permutation, then the density of $\sigma$ in a permutation of order $n$ is maximized by a layered permutation. Albert, Atkinson, Handley, Holton and Stromquist [Electron. J. Combin. 9 (2002), #R5] claimed that the density of a layered permutation with layers of sizes $(a, 1, b)$ where $a, b \ge 2$ is asymptotically maximized by layered permutations with a bounded number of layers, and conjectured that the same holds if a layered permutation has no consecutive layers of size one and its first and last layers are of size at least two.

We show that, if $\sigma$ is a layered permutation whose first layer is sufficiently large and second layer is of size one, then the number of layers tends to infinity in every sequence of layered permutations asymptotically maximizing the density of $\sigma$. This disproves the conjecture and the claim of Albert et al. We complement this result

<footnote>*The first, second and fourth authors were supported by the MUNI Award in Science and Humanities of the Grant Agency of Masaryk University. The first author was also supported by the project GA20-09525S of the Czech Science Foundation. The third author was supported by the Leverhulme Trust Early Career Fellowship ECF-2018-534.</footnote>

<footnote>†Previous affiliation: Faculty of Informatics, Masaryk University, Czech Republic.</footnote>

<footnote>‡Previous affiliation: Mathematics Institute and DIMAP, University of Warwick, United Kingdom.</footnote>
by giving sufficient conditions on a layered permutation to have asymptotic or exact
maximizers with a bounded number of layers.

**Mathematics Subject Classifications:** 05A05

# 1 Introduction

We study permutations maximizing the density of a given pattern. A *permutation* is a bijective function $\pi$ from $[n]$ to $[n]$ (we use $[n]$ to denote the set of the first $n$ positive integers); the *order* of a permutation $\pi$, denoted by $|\pi|$, is the size $n$ of its domain. If $\pi$ is a permutation of order $n$, then the permutation *induced* by $m$ points $i_1 < \dots < i_m$ of $[n]$ is the unique permutation $\sigma : [m] \to [m]$ such that $\sigma(j) < \sigma(j')$ if and only if $\pi(i_j) < \pi(i_{j'})$ for all $j, j' \in [m]$. The *density* of a permutation $\sigma$ in a permutation $\pi$ of order $n \ge |\sigma|$, denoted by $d(\sigma, \pi)$, is the probability that $|\sigma|$ randomly chosen distinct points of $[n]$ induce $\sigma$; in this context, the permutation $\sigma$ is often referred to as a *pattern* and one may speak about permutations containing or avoiding a specific pattern.

The problem of maximizing the density of a permutation $\sigma$ can be traced back to the
work of Galvin, Kleitman, Stromquist and Wilf in the early 1990s (cf. [22]). The packing
density of a permutation $\sigma$ is the limit of the maximum density of $\sigma$ in a permutation
$\pi$ of order $n$ for $n \to \infty$; an averaging argument implies that the limit exists as the
quantity is non-increasing with $n$ (see, e.g., [1, Proposition 1.1]). It is easy to see that the
packing density of the permutation 12, and more generally $12 \cdots k$ for every $k \ge 2$, is 1
(we write $\sigma(1) \cdots \sigma(m)$ to represent the permutation $\sigma$ of order $m$). For the permutation
132, Galvin, Kleitman and Stromquist (independently and unpublished) showed that the
packing density is $2\sqrt{3} - 3$; a sketch of a proof can be found in [20, Example 2.4.2]. See
e.g. [14, 17] for additional results.

In this paper, we are interested in the structure of permutations maximizing the density of a layered permutation: a permutation $\sigma$ of order $m$ is *layered* if $[m]$ can be partitioned to intervals $I_1, \dots, I_k$ such that $\sigma$ restricted to each $I_j, j \in [k]$, is decreasing, and $\sigma(x) < \sigma(x')$ for any $x \in I_j$ and $x' \in I_{j'}$ such that $1 \le j < j' \le k$ (we assume that the intervals are indexed in the order that they follow in $[m]$). The intervals $I_1, \dots, I_k$ are referred to as *layers* of $\sigma$ and layers of size one as *singletons*. We also refer to $\sigma$ as the layered permutation with layers of sizes $(|I_1|, \dots, |I_k|)$. It is not hard to show that a permutation is layered if and only if it avoids the patterns 231 and 312; we refer to [4, 8, 15, 19, 21] for additional results on layered permutations. If $\sigma$ is a layered permutation, then for every $n \ge |\sigma|$, there exists a layered permutation of order $n$ that maximizes the density of $\sigma$ among all permutations of order $n$ [1, 3, 18], and if no layer of $\sigma$ is a singleton, then every permutation of order $n$ that maximizes the density of $\sigma$ is layered [1]; we also refer to [16] for a comprehensive treatment of maximizing the density of layered permutations.

To state our results, we need to fix some notation. Given a permutation $\sigma$, a permuta-
tion $\pi$ of order at least $|\sigma|$ is $\sigma$-optimal if $\pi$ is a permutation of order $|\pi|$ with the largest
density of $\sigma$ among all permutations of order $|\pi|$. In particular, the results of the previous
paragraph say that if $\sigma$ is a layered permutation, then there exists a layered $\sigma$-optimal
permutation of every order $n \ge |\sigma|$, and if each layer of $\sigma$ has size at least two, then every
$\sigma$-optimal permutation is layered. Following the terminology of Warren [20], we say that a sequence $(\pi_n)_{n \in \mathbb{N}}$ of permutations is *near-$\sigma$-optimal* if the orders of $\pi_n$ tend to infinity and the density of $\sigma$ in $\pi_n$ converges to the packing density of $\sigma$. Observe that for every layered permutation $\sigma$, there exists a near-$\sigma$-optimal sequence of layered permutations.

Our central focus is on the question of whether the number of layers in a near-$\sigma$-optimal sequence of layered permutations must grow to infinity for a given layered permutation $\sigma$. For example, if $\sigma$ is a layered permutation in which the first or last layer is a singleton, then the number of layers in any near-$\sigma$-optimal sequence of layered permutations grows to infinity [1, Proposition 2.10]. On the other hand, if $\sigma$ has layers of sizes $(a, b)$ for $a, b \ge 2$, then there exists a near-$\sigma$-optimal sequence of layered permutations where the number of layers is bounded [16]; more generally, Albert et al. [1] showed the following.

**Theorem 1** (Albert et al. [1, Theorem 2.7]). If $\sigma$ is a layered permutation such that each layer of $\sigma$ has size at least two, then there exist a near-$\sigma$-optimal sequence $(\pi_n)_{n \in \mathbb{N}}$ and an integer $K \in \mathbb{N}$ such that each $\pi_n$ has at most $K$ layers.

Albert et al. [1] also stated a conjecture generalizing Theorem 1. We remark that the conjecture is stated in [1] in terms of layered permutations of “bounded-type.” In [1, p. 13], it is said that “the bounded case corresponds precisely to when $p_s = \delta(\sigma)$ for some index $s$” (in the notation of [1]). This is equivalent to the existence of a near-$\sigma$-optimal sequence with a bounded number of layers, and so their conjecture is equivalent to the following.

**Conjecture 1** (Albert et al. [1, Conjecture 2.9]). If $\sigma$ is a layered permutation with layers of sizes $(\ell_1, \dots, \ell_k)$ such that $\ell_1 > 1$, $\ell_k > 1$ and no two consecutive layers of $\sigma$ have size one, then there exist a near-$\sigma$-optimal sequence $(\pi_n)_{n \in \mathbb{N}}$ of layered permutations and an integer $K \in \mathbb{N}$ such that each $\pi_n$ has at most $K$ layers.

As evidence for Conjecture 1, Albert et al. [1] stated the following proposition without proof and claimed that it follows by an argument similar to the proof of [1, Theorem 2.7].

**Proposition 2** (Albert et al. [1, Proposition 2.8]). If $\sigma$ is a layered permutation with layers of sizes $(a, 1, b)$ where $a > 1$ and $b > 1$, then there exists a near-$\sigma$-optimal sequence $(\pi_n)_{n \in \mathbb{N}}$ of layered permutations and $K \in \mathbb{N}$ such that each $\pi_n$ has at most $K$ layers.

Our first result is a counterexample to Conjecture 1, which also provides a counterexample to Proposition 2.

**Theorem 3.** For every $k \in \mathbb{N}$ and $\ell_1, \dots, \ell_k$, there exists $n_0$ such that if $n \ge n_0$ and $\sigma$ is the layered permutation with layers of sizes $(n, 1, \ell_1, \dots, \ell_k)$, then the number of layers in the permutations of every near-$\sigma$-optimal sequence of layered permutations tends to infinity.

In particular, we show (see the discussion at the end of Section 3), that the layered permutation with three layers of sizes (13, 1, 2) satisfies the conclusion of Theorem 3, and hence it fails to satisfy the conclusion of Proposition 2 despite satisfying its hypothesis. We remark that Proposition 2 was used in the paper of Hästö [7] for layered permutations
with layers of sizes $(k, 1, k)$ for $k \ge 2$. Fortunately, while Proposition 2 is false in general, its conclusion holds for this family of permutations. This is a special case of our positive results (Theorems 4 and 5) stated below.

We state and prove some of our results using the language from the theory of permutation limits which was introduced by Hoppen et al. [9, 10] and applied in various problems concerning permutations e.g. [2, 5, 6, 11, 12]. At the center of this theory is the notion of a *permuton*, which is an analytic representation of a large permutation. The link between the finite and limit settings is presented in Section 2. In particular, we show that the existence of a near-$\sigma$-optimal sequence of layered permutations with bounded number of layers is equivalent to the existence of a $\sigma$-optimal layered permuton with a bounded number of layers.

To complement the negative result of Theorem 3, we offer two sufficient conditions on a layered permutation $\sigma$ for the existence of a near-$\sigma$-optimal sequences whose elements are layered permutations with a bounded number of layers. In fact, in some cases, we can obtain a seemingly stronger conclusion that the number of layers in any $\sigma$-optimal permutation is bounded by a universal constant depending on $\sigma$ only. In Section 5, we ask whether these properties are, in fact, equivalent. We remark that the importance of the presence of layers of size one in relation to the existence of large $\sigma$-optimal permutations with a bounded number of layers is consistent with additional results on layered permutations, cf. [1, 7, 16, 19, 21].

**Theorem 4.** Let $\sigma$ be a layered permutation with layers of sizes $(\ell_1, \dots, \ell_k)$ and $k \ge 2$. If $\ell_1 \ge 2$, $\ell_k \ge 2$ and $\ell_i + \ell_{i+1} \ge \max\{\ell_1, \ell_k\} + 1$ for every $i \in [k-1]$, then every $\sigma$-optimal layered permuton has finitely many layers.

**Theorem 5.** Let $\sigma$ be a layered permutation with layers of sizes $(\ell_1, \dots, \ell_k)$ and $k \ge 2$. If $\ell_1 = \ell_k \ge 2$ and every two consecutive layers of $\sigma$ contain a layer of size $\ell_1 = \ell_k$, then there exists an integer $K \in \mathbb{N}$ such that the number of layers of any $\sigma$-optimal layered permutation is at most $K$.

## 2 Permutation limits

In this section, we introduce notions from the theory of permutation limits used throughout the paper, and establish a link between the number of layers of a pattern maximizer in the limit and finite settings. Recall that the density of a permutation $\sigma$ in a permutation $\pi$ of order $n \ge |\sigma|$ is the probability that $|\sigma|$ randomly chosen distinct elements of $\pi$ induce $\sigma$. A sequence $(\pi_n)_{n \in \mathbb{N}}$ of permutations is *convergent* if their orders $|\pi_n|$ tend to infinity and $d(\sigma, \pi_n)$ converges for every permutation $\sigma$. By compactness, every sequence of permutations with orders tending to infinity has a convergent subsequence.

Limits of convergent sequences of permutations can be represented by an analytic object, which we now introduce; a more thorough introduction can be found in [9, 10], also see [11] where the limit object was viewed as the measure for the first time. A *permuton* is a probability measure $\Pi$ on the $\sigma$-algebra of Borel subsets from $[0, 1]^2$ that
has uniform marginals, i.e.,

$$ \Pi([a, b] \times [0, 1]) = \Pi([0, 1] \times [a, b]) = b - a $$

for all $0 \le a \le b \le 1$. If $\Pi$ is a permutation, then a $\Pi$-random permutation $\sigma$ of order $m$ is obtained by sampling $m$ points according to $\Pi$, sorting them according to their $x$-coordinates, say $(x_1, y_1), \dots, (x_m, y_m)$ for $x_1 < \dots < x_m$ (note that the $x$-coordinates are pairwise distinct with probability one), and defining $\sigma$ so that $\sigma(i) < \sigma(j)$ if and only if $y_i < y_j$ for $i, j \in [m]$. The density of a permutation $\sigma$ in a permutation $\Pi$, denoted by $d(\sigma, \Pi)$, is the probability that a $\Pi$-random permutation of order $|\sigma|$ is $\sigma$.

We say that a permutation $\Pi$ is a *limit* of a convergent sequence $(\pi_n)_{n \in \mathbb{N}}$ of permutations if

$$ d(\sigma, \Pi) = \lim_{n \to \infty} d(\sigma, \pi_n) $$

for every permutation $\sigma$. Every convergent sequence of permutations has a limit and this limit is unique. On the other hand, a sequence of $\Pi$-random permutations with increasing orders is convergent and has $\Pi$ as its limit with probability one.

Recall that the *support* of a measure on a set $X$ is the set of all points $x \in X$ such that every open set containing $x$ has a positive measure. A permutation $\Pi$ is *layered* if there exists a (not necessarily finite) collection $\mathcal{J}$ of internally disjoint closed subintervals of $[0, 1]$ such that $(x, y)$ lies in the support of $\Pi$ if $x$ belongs to an interval $[a, b] \in \mathcal{J}$ and $y = b - (x - a)$, i.e., the support of $\Pi$ is a union of intervals with slope $-1$ centered along the main diagonal of the square $[0, 1]^2$ such that their projections on the horizontal axis are internally disjoint. Observe that the collection $\mathcal{J}$ (if it exists) is uniquely determined by the permutation $\Pi$. We will also refer to intervals in $\mathcal{J}$ as the *layers* of the permutation $\Pi$, those with positive length as *non-trivial layers*, and those with length zero as *trivial layers*. The number of layers of a layered permutation $\Pi$ is the cardinality of $\mathcal{J}$; note that the number of layers of a layered permutation may be (countably or uncountably) infinite. For example, the permutation supported on the line $y = x$ is layered with uncountably many trivial layers. On the other hand, the permutation supported on the line $y = 1 - x$ has only one layer. An example of a layered permutation with countably many layers is the permutation with layers $[1 - 2^{-k+1}, 1 - 2^{-k}]$, $k \in \mathbb{N}$, and $[1, 1]$ (note that the point $(1, 1)$ indeed belongs to the support). See Figure 1 for the visualization of the three examples of layered permutations that we have just given and some additional examples of layered permutations. Observe that if the number of layers is finite, then each layer is non-trivial. Analogously to the finite case, a permutation $\Pi$ is layered if and only if $d(231, \Pi) = 0$ and $d(312, \Pi) = 0$; in particular, this can be derived from Lemma 6 proven below.

The lemma that we now state provides a key link between layered permutations and layered permutations. We remark that it is not hard to construct a convergent sequence of layered permutations such that the number of their layers tends to infinity but the limit permutation has a finite number of layers; for example, consider the sequence $\pi_1, \pi_2, \dots$ such that $\pi_n$ consists of one layer of length $n^2$ and $n$ singleton layers.

**Lemma 6.** Let $(\pi_n)_{n \in \mathbb{N}}$ be a convergent sequence of permutations and let $\Pi$ be its limit permutation. If the permutation $\pi_n$ is layered for every $n \in \mathbb{N}$, then $\Pi$ is layered. Moreover,
<figure><img src="image_2.png" /><figcaption>Figure 1: Examples of layered permutations. The support of each of the permutations is drawn in the square [0, 1]². The origin of the coordinate system is in the bottom left corner.</figcaption></figure>

if there exists $k \in \mathbb{N}$ such that the number of layers of each $\pi_n$ is at most $k$, then the number of layers of $\Pi$ is at most $k$.

<figure><img src="image_3.png" /><figcaption>Figure 2: The support of the layered permutation associated with the permutation 43215687 as in the proof of Lemma 6. The origin of the coordinate system is in the bottom left corner.</figcaption></figure>

*Proof.* We first associate each permutation $\pi_n$ with a permutation $\Pi_n$ as follows (see Figure 2 for an example): the permutation $\Pi_n$ is the unique (layered) permutation such that its support is the union

$$ \bigcup_{i \in [\pi_n]} \left\{ \left( \frac{i-1+t}{|\pi_n|}, \frac{\pi_n(i)-t}{|\pi_n|} \right), t \in [0, 1] \right\}. $$

Informally speaking, the permutation $\Pi_n$ is the unique layered permutation with the layers of the same relative size and order as in the permutation $\pi_n$. Observe that the number of layers of each $\Pi_n$ is finite.

For $n \in \mathbb{N}$ and $i \in \mathbb{N}$, let $J_{n,i}$ be the $i$-th longest layer of the permutation $\Pi_n$ if $i$ is at most the number of layers of $\Pi_n$ (order layers of the same length arbitrarily); we set $J_{n,i}$ to be $[1, 1]$ if $i$ exceeds the number of layers of the permutation $\Pi_n$. Consider an increasing sequence $(n_k)_{k \in \mathbb{N}}$ such that for every $i \in \mathbb{N}$, the sequences $(\min J_{n_k,i})_{k \in \mathbb{N}}$ and $(\max J_{n_k,i})_{k \in \mathbb{N}}$, i.e., the sequences of the left and right end points of intervals $J_{n_k,i}$, converge; the sequence $(n_k)_{k \in \mathbb{N}}$ exists by compactness. For $i \in \mathbb{N}$, let $a_i$ and $b_i$ be the limits of the sequences $(\min J_{n_k,i})_{k \in \mathbb{N}}$ and $(\max J_{n_k,i})_{k \in \mathbb{N}}$, and we define $\Pi$ to be the unique layered permutation whose support is the closure of the set containing all points $(x, y)$ such that

* either $x$ is contained in a non-trivial interval $[a_i, b_i]$ for some $i \in \mathbb{N}$ and $y = b_i - (x - a_i)$, or

* $x$ is not contained in any interval $[a_i, b_i]$ and $y = x$.
We will show that the permutation $\Pi$ is the limit permutation of the sequence $(\pi_n)_{n \in \mathbb{N}}$.

As the first step to show that $\Pi$ is the limit of $(\pi_n)_{n \in \mathbb{N}}$, we observe that

$$|d(\sigma, \Pi_n) - d(\sigma, \pi_n)| \le \frac{|\sigma|^2}{|\pi_n|} \qquad (1)$$

for every permutation $\sigma$. Indeed, if $|\sigma| \le |\pi_n|$, then the probability that $|\sigma|$ randomly chosen points of $\pi_n$ induce $\sigma$ is equal to the probability that the $\Pi_n$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on no two of the $|\sigma|$ points defining the $\Pi_n$-random permutation being chosen from the same interval $[(i-1)/|\pi_n|, i/|\pi_n|]$ for any $i \in [|\pi_n|]$. Since the probability that two of the $|\sigma|$ points defining the $\Pi_n$-random permutation are chosen from the same interval $[(i-1)/|\pi_n|, i/|\pi_n|]$ for some $i \in [|\pi_n|]$ is at most $\binom{|\sigma|}{2}|\pi_n|^{-1}$, the estimate (1) follows.

We next establish that

$$\lim_{k \to \infty} d(\sigma, \Pi_{n_k}) = d(\sigma, \Pi) \qquad (2)$$

for every permutation $\sigma$. By [13, Theorem 21], (2) is equivalent to

$$\lim_{k \to \infty} \Pi_{n_k}(R) = \Pi(R) \qquad (3)$$

for every rectangle $R = [x_1, x_2] \times [y_1, y_2] \subseteq [0, 1]^2$. Observe that it is sufficient to establish (3) for rectangles $R = [0, x] \times [0, y] \subseteq [0, 1]^2$ only. Fix $x$ and $y$ and assume that $x \le y$. We distinguish two cases. If $x$ is an internal point of an interval $[a_i, b_i]$ (see Figure 3), then

$$\Pi(R) = \max\{a_i, x - \max\{b_i - y, 0\}\}. \qquad (4)$$

<figure><img src="image_4.png" /><figcaption>Figure 3: Illustration of the formula (4) for $[a_i, b_i] = [0.2, 0.8]$. For $x \in \{0.3, 0.4, 0.5, 0.6\}$ and $y = 0.65$, the rectangle $R$ is drawn by the dotted lines.</figcaption></figure>

Note that $x$ is an internal point of the interval $J_{n_k,i}$ for all sufficiently large $n_k$ and for all such $n_k$, it holds that

$$\Pi_{n_k}(R) = \max\{\min J_{n_k,i}, x - \max\{\max J_{n_k,i} - y, 0\}\}.$$

Hence, the identity (3) follows. On the other hand, if $x$ is not an internal point of an interval $[a_i, b_i]$ for any $i \in \mathbb{N}$, then $\Pi(R)$ and $\Pi_{n_k}(R)$ differ by at most the length of the interval $J_{n_k,i}$ that contains $x$ as an internal point if such an interval exists, and $\Pi(R)$ and $\Pi_{n_k}(R)$ are equal if there is no such interval. Since the lengths of the intervals $J_{n_k,i}$ containing $x$ as an internal point must tend to zero (otherwise, $x$ would be an internal
point of an interval $[a_i, b_i]$ for some $i$), the identity (3) also follows in this case. Since the case $x > y$ is analogous, (3) holds for every rectangle $R = [0, x] \times [0, y] \subseteq [0, 1]^2$. The identity (2) now follows.

The estimate (1) and the identity (2) imply that the permutation $\Pi$ is the limit permutation of the sequence $(\pi_{n_k})_{k \in \mathbb{N}}$. Since the sequence $(\pi_n)_{n \in \mathbb{N}}$ is convergent, $\Pi$ is also its limit permutation. The uniqueness of the limit permutation now yields the first part of the lemma. For the second part, suppose that the number of layers of each permutation $\pi_n$ is at most $k$. This implies that $J_{n_k, i} = [1, 1]$ for all $i > k$ and so $\Pi$ has at most $k$ layers. $\square$

A permutation $\Pi$ is $\sigma$-optimal if the density of $\sigma$ in $\Pi$ is equal to the packing density of $\sigma$. Recall that, for every layered permutation $\sigma$ and every $n \ge |\sigma|$, there exists a $\sigma$-optimal layered permutation $\pi_n$ of order $n$. By compactness, the sequence $(\pi_n)_{n \in \mathbb{N}}$ has a convergent subsequence. By Lemma 6, the limit $\Pi$ of this subsequence is a layered permutation and, by the definition of limit permutations, the density of $\sigma$ in $\Pi$ is equal to the packing density. Therefore, every layered permutation $\sigma$ has a $\sigma$-optimal layered permutation $\Pi$. Moreover, the density of $\sigma$ in $\Pi$ is the maximum possible density of $\sigma$ in any permutation: if there was a permutation $\Pi'$ with a higher density of $\sigma$, then a sequence of $\Pi'$-random permutations of increasing orders would give a sequence of permutation with the density of $\sigma$ converging to a higher density than the packing density of $\sigma$. Also note that if $\Pi$ is a $\sigma$-optimal permutation with $k$ layers, then a sequence of $\Pi$-random permutations of increasing orders is near-$\sigma$-optimal (with probability one) and each of its elements has at most $k$ layers (since every $\Pi$-random permutation has at most $k$ layers).

### 3 Maximizers with infinitely many layers

This section is devoted to proving Theorem 3. By Lemma 6, Theorem 3 is implied by the next theorem, which is the limit version of Theorem 3.

**Theorem 7.** For every $k \in \mathbb{N}$ and $\ell_1, \dots, \ell_k$, there exists $n_0$ such that if $\sigma$ is the layered permutation with layers of sizes $(n, 1, \ell_1, \dots, \ell_k)$ where $n \ge n_0$, then every $\sigma$-optimal layered permutation has an infinite number of layers.

*Proof.* Fix $k$ and $\ell_1, \dots, \ell_k$ for the proof and set $L = 1 + \ell_1 + \dots + \ell_k$. We choose the exact value of $n_0$ at the end of the proof; until then, we will only need that $n_0 \ge L$. Fix $n \ge n_0$, i.e., the order of $\sigma$ is $n+L$, and consider any $\sigma$-optimal layered permutation $\Pi$. Suppose, for the sake of contradiction, that $\Pi$ has finitely many layers. Let $K$ be the number of layers of $\Pi$ and $x_i$ the length of the $i$-th layer, $i \in [K]$. Note that all layers of $\Pi$ are non-trivial and that $\Pi$ must have at least as many layers as $\sigma$; so, $K \ge k+2$. Observe that

$$d(\sigma, \Pi) = A \left( \sum_{1 \le a < b < i_1 < \dots < i_k \le K} x_a^n x_b \prod_{j=1}^{k} x_{i_j}^{\ell_j} \right) \quad (5)$$

where

$$A = \frac{(n+L)!}{n! \prod_{j=1}^{k} (\ell_j)!}.$$
<figure><img src="image_5.png" /><figcaption>Figure 4: The permutons $\Pi'$, $\Pi_y$, $\Pi_{x_2}$, $\Pi^+$ and $\Pi^*$ from the proof of Theorem 7. The symbol $\Pi^-$ in the figure represents the part of the permuton $\Pi$ not including the first and second layer, and $\Lambda$ represents a scaled down copy of the permuton $\Lambda$.</figcaption></figure>

As we will consider several modifications of the permuton $\Pi$, the following shorthands for various quantities will be useful when calculating the density of $\sigma$ in the modified permutons:

$$ \Sigma_0 = \sum_{3 \le a < b < i_1 < \dots < i_k \le K} x_a^n x_b \prod_{j=1}^{k} x_{i_j}^{\ell_j}, $$

$$ \Sigma_1 = \sum_{3 \le b < i_1 < \dots < i_k \le K} x_b \prod_{j=1}^{k} x_{i_j}^{\ell_j}, \text{ and} $$

$$ \Sigma_2 = \sum_{3 \le i_1 < \dots < i_k \le K} \prod_{j=1}^{k} x_{i_j}^{\ell_j}. $$

Observe that $\Sigma_0 \le \Sigma_1 \le \Sigma_2 \le 1$ and $\Sigma_2 > 0$ because $K \ge k + 2$. Also note that

$$ d(\sigma, \Pi) = A(x_1^n x_2 \Sigma_2 + x_1^n \Sigma_1 + x_2^n \Sigma_1 + \Sigma_0). \qquad (6) $$

We will next consider five permutons obtained by modifying $\Pi$, relate the density of $\sigma$ in them to the density in $\Pi$ and use this to derive some properties of $\Pi$; the five permutons that we consider are visualized in Figure 4.

We start by showing that $x_1 \ge nx_2$; the argument is split into two claims.

**Claim 7.1.** $x_1 \ge x_2$.

*Proof of Claim 7.1.* We consider the layered permuton $\Pi'$ obtained from $\Pi$ by swapping the first two layers, i.e., the first layer of $\Pi'$ has length $x_2$, the second has length $x_1$, and the $i$-th has length $x_i$ for $i = 3, \dots, K$. Observe that

$$ d(\sigma, \Pi') - d(\sigma, \Pi) = A(x_2^n x_1 - x_1^n x_2) \Sigma_2. $$

Since $\Pi$ is $\sigma$-optimal, $A > 0$ and $\Sigma_2 > 0$, we conclude that $x_1 \ge x_2$. $\square$

**Claim 7.2.** $x_1 \ge nx_2$.
Proof of Claim 7.2. For $y \in [0, x_2)$, we consider the layered permutation $\Pi_y$ whose first layer has length $x_1 + y$, the second layer $x_2 - y$, and the $i$-th $x_i$ for $i = 3, \dots, K$; in particular, $\Pi_0$ is just the permutation $\Pi$.

Let $h(y)$ be the density of $\sigma$ in the permutation $\Pi_y$ (the density is viewed as a function of $y$), i.e.,

$$h(y) = d(\sigma, \Pi_y) = A((x_1 + y)^n(x_2 - y)\Sigma_2 + (x_1 + y)^n\Sigma_1 + (x_2 - y)^n\Sigma_1 + \Sigma_0).$$

Observe that

$$\frac{\partial h}{\partial y} = A(n(x_1 + y)^{n-1}(x_2 - y)\Sigma_2 - (x_1 + y)^n\Sigma_2 + n(x_1 + y)^{n-1}\Sigma_1 - n(x_2 - y)^{n-1}\Sigma_1),$$

and that the value of the derivative of $h$ for $y = 0$ is

$$A(nx_1^{n-1}x_2 - x_1^n)\Sigma_2 + A(nx_1^{n-1} - nx_2^{n-1})\Sigma_1.$$

By Claim 7.1, the second term in the above expression is non-negative. Therefore, the derivative of $h$ at $y = 0$ is bounded below by

$$A(nx_1^{n-1}x_2 - x_1^n)\Sigma_2.$$

Since $\Pi$ is $\sigma$-optimal, the derivative of $h$ at $y = 0$ must be non-positive. Therefore, $x_1 \ge nx_2$. $\square$

We next bound $\Sigma_1$ from above as follows.

**Claim 7.3.** $\Sigma_1 \le \frac{x_1}{n}$.

Proof of Claim 7.3. We consider the layered permutation $\Pi_{x_2}$ obtained from $\Pi$ by merging its first and second layer; formally, the permutation $\Pi_{x_2}$ is the layered permutation such that its first layer has length $x_1 + x_2$ and the $(i-1)$-th layer $x_i$ for $i = 3, \dots, K$. The notation comes from Claim 7.2 as $\Pi_{x_2}$ is the limit permutation of $\Pi_y$ for $y \to x_2$. Observe that the difference

$$d(\sigma, \Pi_{x_2}) - d(\sigma, \Pi) = A(((x_1 + x_2)^n - x_1^n - x_2^n)\Sigma_1 - x_1^n x_2 \Sigma_2) \\ \ge A(nx_1^{n-1}x_2\Sigma_1 - x_1^n x_2 \Sigma_2)$$

must be non-positive since the permutation $\Pi$ is $\sigma$-optimal. We use $A > 0$ and $\Sigma_2 \le 1$ to obtain that $nx_1^{n-1}x_2\Sigma_1 \le x_1^n x_2$, which yields the bound in the inequality from the claim. $\square$

Let $\sigma'$ be the layered permutation obtained from $\sigma$ by removing its first layer, i.e., $\sigma'$ is the layered permutation with layers of sizes $(1, \ell_1, \dots, \ell_k)$. The next two claims bound $d(\sigma, \Pi)$ and $x_1$ using the assumption that there exists a layered permutation $\Lambda$ with a certain density of $\sigma'$.
**Claim 7.4.** For any layered permuton $\Lambda$, we have

$$d(\sigma, \Pi) \geq \binom{n+L}{n} \left(\frac{n}{n+L}\right)^n \left(\frac{L}{n+L}\right)^L d(\sigma', \Lambda).$$

*Proof of Claim 7.4.* We consider the layered permuton $\Pi^+$ obtained from $\Lambda$ by adding a long first layer and rescaling. Specifically, the first layer of the permuton $\Pi^+$ is $[0, n/(n+L)]$ and if $[a, b]$ is a layer of $\Lambda$, then $[(n+aL)/(n+L), (n+bL)/(n+L)]$ is a layer of $\Pi^+$. Since the density of $\sigma$ in $\Pi^+$ is at least

$$\binom{n+L}{n} \left(\frac{n}{n+L}\right)^n \left(\frac{L}{n+L}\right)^L d(\sigma', \Lambda)$$

and the permuton $\Pi$ is $\sigma$-optimal, the claim follows. □

Our final claim is the following.

**Claim 7.5.** For any layered permuton $\Lambda$ with $d(\sigma', \Lambda) > 0$, we have

$$x_1 \leq \left( \frac{A}{\binom{n+L}{n} n^{n-L} d(\sigma', \Lambda)} \right)^{1/L}.$$

*Proof of Claim 7.5.* We consider the layered permuton $\Pi^*$ obtained from $\Pi$ by replacing the second layer with a scaled copy of $\Lambda$, i.e., the $i$-th layer of $\Pi$ for $i = 1, 3, \dots, K$ is also a layer of $\Pi^*$ and if $[a, b]$ is a layer of $\Lambda$, then $[x_1 + ax_2, x_1 + bx_2]$ is a layer of $\Pi^*$. We use that the second layer of $\sigma$ has size one and derive that

$$d(\sigma, \Pi^*) - d(\sigma, \Pi) \geq \binom{n+L}{n} x_1^n x_2^L d(\sigma', \Lambda) - A x_2^n \Sigma_1$$

where the first term of right side accounts for the probability that a $\Pi^*$-random permutation is $\sigma$, its first layer is contained in the first layer of $\Pi^*$ and its remaining layers in the layers of the scaled down copy of $\Lambda$, and the second term accounts for the probability that a $\Pi$-random permutation is $\sigma$ and its first layer is contained in the second layer of $\Pi^*$.

Since $\Pi$ is $\sigma$-optimal, it holds that

$$\binom{n+L}{n} x_1^n x_2^L d(\sigma', \Lambda) \leq A x_2^n \Sigma_1,$$

and since $\Sigma_1 \leq 1$, we get

$$\binom{n+L}{n} x_1^n d(\sigma', \Lambda) \leq A x_2^{n-L}.$$

Using the assumption that $n \geq L$ and Claim 7.2, we derive that $x_1^{n-L} \geq (nx_2)^{n-L}$ and eventually obtain

$$\binom{n+L}{n} x_1^L n^{n-L} d(\sigma', \Lambda) \leq A,$$

which yields the desired inequality. □
We next use (6) and $\Sigma_0 \le \Sigma_1 \le \Sigma_2 \le 1$ to get that

$$d(\sigma, \Pi) \le A(x_1^n x_2 + x_1^n + x_2^n + \Sigma_1).$$

Combining this with Claims 7.1 and 7.3 and the fact that $x_2 \le 1$ yields

$$d(\sigma, \Pi) \le A \left( 3x_1^n + \frac{x_1}{n} \right). \qquad (7)$$

We next show that there exists $d_0 > 0$ such that $d(\sigma, \Pi) \ge d_0$ for all $n$. Observe that

$$\lim_{n \to \infty} \binom{n+L}{n} \left(\frac{n}{n+L}\right)^n \left(\frac{L}{n+L}\right)^L = \lim_{n \to \infty} \frac{L^L}{L!} \left(1 - \frac{L}{n+L}\right)^n = \frac{L^L}{e^L L!}.$$

We fix any layered permuton $\Lambda$ such that $d(\sigma', \Lambda) > 0$ and obtain using Claim 7.4 that the packing density of $\sigma$ for any sufficiently large $n$ is at least $\frac{L^L}{2e^L L!}d(\sigma', \Lambda)$; the existence of $d_0$ now follows.

We next estimate the right side of (7). Observe that $A = \frac{(n+L)!}{n! \prod_{j=1}^k (\ell_j!)} = \Theta(n^L)$ while $x_1 = O(n^{-\frac{n}{L}})$ by Claim 7.5. We conclude that the right side of (7) tends to 0, and choose $n_0$ in such a way that $n_0 \ge L$ and the inequality (7) does not hold for any $n \ge n_0$. This finishes the proof of the theorem. $\square$

The argument presented in Theorem 7 can actually be used to obtain reasonably small bounds on $n_0$. For example, consider the case when $k=1$ and $\ell_1=2$, which means that $\sigma$ is the layered permutation with layers with sizes $(n, 1, 2)$ and $\sigma'$ is the layered permutation with layers of sizes $(1, 2)$, i.e., $\sigma' = 132$. Since the packing density of $\sigma'$ is $2\sqrt{3}-3$, we can fix a permuton $\Lambda$ such that $d(\sigma', \Lambda) = 2\sqrt{3}-3$. As

$$A = \frac{(n+3)!}{n! \cdot 2} = 3 \binom{n+3}{n},$$

we get using Claims 7.4 and 7.5 that

$$d(\sigma, \Pi) \ge \binom{n+3}{n} \left(\frac{n}{n+3}\right)^n \left(\frac{3}{n+3}\right)^3 (2\sqrt{3}-3)$$

and

$$x_1 \le \sqrt[3]{\frac{3}{n^{n-3}(2\sqrt{3}-3)}}$$

for any $\sigma$-optimal permuton $\Pi$ where $x_1$ is the length of the first layer of $\Pi$. We show that it is possible to set $n_0 = 13$. Observe that $(n+3) \le 16n/13$ since $n \ge 13$. It follows that

$$d(\sigma, \Pi) \ge \binom{n+3}{n} \left(\frac{1}{e^3}\right) \left(\frac{3 \cdot 13}{16n}\right)^3 (2\sqrt{3}-3) > 0.33 \binom{n+3}{n} \frac{1}{n^3}.$$
On the other hand, we obtain using $n \ge 13$ and $x_1 \le 1$ that

$$A \left( 3x_1^n + \frac{x_1}{n} \right) \le 3 \binom{n+3}{n} \left( \frac{3}{13^7 (2\sqrt{3}-3)n^3} + \frac{1}{n} \sqrt[3]{\frac{3}{13^4 (2\sqrt{3}-3)n^6}} \right) < 0.19 \binom{n+3}{n} \frac{1}{n^3}.$$

It follows that the inequality (7) in the proof of Theorem 7 does not hold for any $n \ge 13$ and so every $\sigma$-optimal layered permuton has infinitely many layers for every $n \ge 13$.

# 4 Maximizers with finitely many layers

This section is devoted to the proofs of Theorems 4 and 5. We start with proving three lemmas needed to prove Theorem 4. Given a layered permuton $\Pi$, we say that a non-trivial interval $[a, b]$ is a segment of $\Pi$ if it can be written as a union of (possibly infinitely many) layers of $\Pi$.

**Lemma 8.** Let $\sigma$ be a layered permutation of order at least two with $k$ layers and without consecutive singleton layers. If $\Pi$ is a $\sigma$-optimal layered permuton, then every segment $[a, b]$ of $\Pi$ contains a layer of $\Pi$ of length at least $\frac{b-a}{|\sigma|^2 k |\sigma|}$.

*Proof.* Suppose, for contradiction, that there exists a $\sigma$-optimal layered permuton $\Pi$ with a segment $[a, b]$ such that the length of every layer of $\Pi$ contained in $[a, b]$ is strictly less than $\frac{b-a}{|\sigma|^2 k |\sigma|}$. Let $\Pi'$ be the layered permuton obtained by replacing the layers of $\Pi$ in the segment $[a, b]$ with $k$ layers, each of length $(b-a)/k$. Using that $\sigma$ has no two consecutive singleton layers, we argue that $d(\sigma, \Pi') > d(\sigma, \Pi)$.

Given $|\sigma|$ points sampled according to $\Pi$, let $E_n$ be the event that exactly $n$ of the sampled points have their $x$-coordinate in $[a, b]$; analogously, $E'_n$ is the event that exactly $n$ of the sampled points according to $\Pi'$ have their $x$-coordinate in $[a, b]$. Note that, since $\Pi$ and $\Pi'$ have uniform marginals, it holds that $P(E_n) = P(E'_n)$ for all $n = 0, \dots, |\sigma|$.

Observe that the probability that a $\Pi$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on $E_0 \cup E_1$ is equal to the probability that a $\Pi'$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on $E'_0 \cup E'_1$. We next analyze the probabilities that a $\Pi$-random permutation of order $|\sigma|$ is $\sigma$ and a $\Pi'$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on a particular choice of $|\sigma| - n$ points outside the segment $[a, b]$ for $n \ge 2$. Since the permutons $\Pi$ and $\Pi'$ agree outside the segment $[a, b]$, the probability distributions of the events that we condition on are the same. For a fixed choice of $|\sigma| - n$ points outside the segment $[a, b]$, if the probability that a $\Pi'$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on the choice of the $|\sigma| - n$ points is zero, then the probability that a $\Pi$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on the same choice of the points is also zero. Otherwise, the probability that a $\Pi'$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on the choice of the $|\sigma| - n$ points is at least $k^{-n}$ and the probability that a $\Pi$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on the choice of the $|\sigma| - n$ points is at least $k^{-n}$.
conditioned on the same choice of the points is at most

$$ \left(\frac{|\sigma|}{2}\right) \left(\frac{1}{|\sigma|^2 k^{|\sigma|}}\right) < \frac{k^{-|\sigma|}}{2}. \qquad (8) $$

The estimate (8) follows from the fact that $\sigma$ does not have two consecutive singleton layers and so if the $\Pi$-random permutation is $\sigma$ and $n \ge 2$ points are sampled from the segment $[a, b]$, then at least two points of $\sigma$ must come from the same layer contained in the segment $[a, b]$. The probability of this event happening is upper bounded by the left side of (8). Hence, the probability that a $\Pi$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on $E_2 \cup \cdots \cup E_{|\sigma|-1}$ is at most the probability that a $\Pi'$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on $E'_2 \cup \cdots \cup E'_{|\sigma|-1}$ (note that the inequality is strict whenever the former probability is non-zero), and the probability that a $\Pi$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on $E_{|\sigma|}$ is strictly smaller than the probability that a $\Pi'$-random permutation of order $|\sigma|$ is $\sigma$ conditioned on $E'_{|\sigma|}$ (as these two probabilities are non-zero). This contradicts the assumption that the permutation $\Pi$ is $\sigma$-optimal. $\square$

A simple consequence of Lemma 8 is the following.

**Lemma 9.** Let $\sigma$ be a layered permutation of order at least two without consecutive singleton layers. For every $\sigma$-optimal permutation $\Pi$, the set of all $x \in [0, 1]$ such that $[x, x]$ is a layer of $\Pi$ has measure zero.

*Proof.* Let $X$ be the set of all $x \in [0, 1]$ such that $[x, x]$ is a layer of $\Pi$. Observe that $X$ is closed, and so it is measurable. Let $k$ be the number of layers of $\sigma$ and define $r = |\sigma|^2 k^{|\sigma|}$.

By applying Lemma 8 to the segment $[0, 1]$, we see that $\Pi$ has a layer $I_1$ of length at least $1/r$. Let $I_0 = [0, \min I_1]$ and $I_2 = [\max I_1, 1]$. If $I_0$ is non-trivial, then it is a segment of $\Pi$ and we can apply Lemma 8 to it; similarly, if $I_2$ is non-trivial, we can apply Lemma 8 to it. In general, for a finite sequence $i_1, i_2, \dots, i_t \in \{0, 2\}$, we recursively define $I_{i_1, \dots, i_t, 0}$, $I_{i_1, \dots, i_t, 1}$ and $I_{i_1, \dots, i_t, 2}$ to be internally disjoint intervals whose union is $I_{i_1, \dots, i_t}$ such that if $I_{i_1, \dots, i_t}$ is a segment, then $I_{i_1, \dots, i_t, 1}$ is a layer of $\Pi$ of length at least $|I_{i_1, \dots, i_t}|/r$. If $I_{i_1, \dots, i_t}$ is trivial, we set $I_{i_1, \dots, i_t, 0} = I_{i_1, \dots, i_t, 1} = I_{i_1, \dots, i_t, 2} = I_{i_1, \dots, i_t}$. For $t \ge 1$, let

$$ S_t = \bigcup_{i_1, \dots, i_t \in \{0, 2\}} I_{i_1, \dots, i_t}, $$

and observe that $X \subseteq \bigcap_{t=1}^{\infty} S_t$. However, for each $t \ge 1$, the measure of $S_{t+1}$ is at most $\frac{r-1}{r}$ times the measure of $S_t$. We conclude that the set $X$ has measure zero. $\square$

Our next lemma deals specifically with the classes of permutations considered in Theorem 4.

**Lemma 10.** Let $\varepsilon > 0$ and let $\sigma$ be a layered permutation with $k \ge 2$ layers of sizes $(\ell_1, \dots, \ell_k)$ such that $\ell_1 \ge 2$, $\ell_k \ge 2$ and $\ell_i + \ell_{i+1} \ge \max\{\ell_1, \ell_k\} + 1$ for every $i \in [k-1]$. If $\Pi$ is a $\sigma$-optimal layered permutation with at least $2k-3$ layers of length at least $\varepsilon$, then every segment $[a, b]$ of $\Pi$ that has at least two layers has a layer of length at least $(\varepsilon/4)^{|\sigma|}/k$.
*Proof.* Suppose, for the sake of contradiction, that $\Pi$ is a $\sigma$-optimal permuton that has $2k-3$ layers of length at least $\varepsilon$ and a segment $[a, b]$ with at least two layers such that every layer contained in $[a, b]$ has length less than $(\varepsilon/4)^{|\sigma|}/k$.

Let $\mathcal{I}$ be the set of all non-trivial layers of $\Pi$ contained in $[a, b]$. Since the set $\mathcal{I}$ is countable, we can index the elements of $\mathcal{I}$ by $I_j$ for $j \in S$, where $S$ is either equal $\mathbb{N}$ or $[n]$ for some $n \in \mathbb{N}$. For $j \in S$, let $z_j$ be the length of $I_j$. Since $\ell_i + \ell_{i+1} \ge \max\{\ell_1, \ell_k\} + 1 \ge 3$, the permutation $\sigma$ has no consecutive singleton layers and so Lemma 9 yields that $\sum_{j \in S} z_j = b - a$.

Consider a permuton $\Pi'$ obtained from $\Pi$ by replacing the segment $[a, b]$ with a single layer. We will show that $d(\sigma, \Pi') > d(\sigma, \Pi)$, contradicting that the permuton $\Pi$ is $\sigma$-optimal. Since the permuton $\Pi$ has $2k-3$ layers each of length at least $\varepsilon$ and none of these layers is contained in the segment $[a, b]$ (since each layer of the segment is shorter than $(\varepsilon/4)^{|\sigma|}/k$), there are $k-1$ layers of length at least $\varepsilon$ contained in $[0, a]$ or there are $k-1$ layers of length at least $\varepsilon$ contained in $[b, 1]$. Since the two cases are completely symmetric, we analyze in detail the former case only.

Let $\sigma'$ be the permutation obtained from $\sigma$ by removing its last layer, i.e., $\sigma'$ is the layered permutation with layers of sizes $(\ell_1, \dots, \ell_{k-1})$. Let $p$ be the probability that a $\Pi$-random permutation of order $|\sigma'|$ is $\sigma'$ and the $x$-coordinates of all of its points belong to $[0, a]$. Observe that $p \ge \varepsilon^{|\sigma'|} > \varepsilon^{|\sigma|}$. Note that $p$ is also equal to the probability that a $\Pi'$-random permutation of order $|\sigma'|$ is $\sigma'$ and the $x$-coordinates of all of its points belong to $[0, a]$. The probability that a $\Pi'$-random permutation of order $|\sigma|$ is $\sigma$ and its last layer is sampled from $[a, b]$ is

$$ \binom{|\sigma|}{\ell_k} p(b-a)^{\ell_k} = \binom{|\sigma|}{\ell_k} p \left( \sum_{j \in S} z_j \right)^{\ell_k}. $$

Similarly, for $j \in S$, the probability that a $\Pi$-random permutation of order $|\sigma|$ is $\sigma$, its last layer is sampled from $I_j$, and all of its other layers are sampled from $[0, a]$ is equal to

$$ \binom{|\sigma|}{\ell_k} p z_j^{\ell_k}. $$

For $i \in [k-1]$, the probability that a $\Pi$-random permutation is $\sigma$ and its $i$-th layer is sampled from the segment $[a, b]$ and no other layer is sampled from the segment $[a, b]$ is at most the probability that a $\Pi'$-random permutation is $\sigma$ and its $i$-th layer is sampled from the segment $[a, b]$ and no other layer is sampled from the segment $[a, b]$. Finally, for $i \in [k-1]$, the probability that a $\Pi$-random permutation is $\sigma$ and its $i$-th and $(i+1)$-th layers are both sampled from the segment $[a, b]$ (note that these events are not disjoint for different $i$'s as more than two layers can be sampled from $[a, b]$) is at most

$$ \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} \binom{|\sigma|}{\ell_i} \binom{|\sigma| - \ell_i}{\ell_{i+1}} z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \le 2^{2|\sigma|} \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}}. $$
Using the fact that $z_j < (\varepsilon/4)^{|\sigma|}/k$ for all $j \in S$, it follows that

$$
\begin{align*}
d(\sigma, \Pi') - d(\sigma, \Pi) &\ge \binom{|\sigma|}{\ell_k} p \left( \left( \sum_{j \in S} z_j \right)^{\ell_k} - \sum_{j \in S} z_j^{\ell_k} \right) - 2^{2|\sigma|} \sum_{i \in [k-1]} \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \\
&\ge \varepsilon^{|\sigma|} \left( \left( \sum_{j \in S} z_j \right)^{\ell_k} - \sum_{j \in S} z_j^{\ell_k} \right) - 4^{|\sigma|} \sum_{i \in [k-1]} \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \\
&\ge \varepsilon^{|\sigma|} \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} \left( z_{j_1}^{\ell_k-1} z_{j_2} + z_{j_1} z_{j_2}^{\ell_k-1} \right) - 4^{|\sigma|} \sum_{i \in [k-1]} \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \\
&> 4^{|\sigma|} \left( k \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} \left( z_{j_1}^{\ell_k} z_{j_2} + z_{j_1} z_{j_2}^{\ell_k} \right) - \sum_{i \in [k-1]} \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \right) \\
&\ge 4^{|\sigma|} \sum_{i \in [k-1]} \sum_{\substack{j_1, j_2 \in S \\ j_1 < j_2}} \left( z_{j_1}^{\ell_k} z_{j_2} + z_{j_1} z_{j_2}^{\ell_k} - z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \right).
\end{align*}
$$

Since it holds $\ell_i + \ell_{i+1} \ge \ell_k + 1$ for every $i \in [k-1]$ by the hypothesis, we get that the following holds for all $i \in [k-1]$ and $j_1, j_2 \in S$:

$z_{j_1}^{\ell_k} z_{j_2} \ge z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \text{ if } z_{j_1} \ge z_{j_2}, \text{ and}$

$z_{j_1} z_{j_2}^{\ell_k} \ge z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \text{ if } z_{j_2} \ge z_{j_1}.$

This yields that

$z_{j_1}^{\ell_k} z_{j_2} + z_{j_1} z_{j_2}^{\ell_k} > z_{j_1}^{\ell_i} z_{j_2}^{\ell_{i+1}} \ge 0.$

It follows that $d(\sigma, \Pi') - d(\sigma, \Pi) > 0$, which contradicts the assumption that the permuton $\Pi$ is $\sigma$-optimal. $\square$

We are now ready to prove Theorem 4.

*Proof of Theorem 4.* Assume, for the sake of contradiction, that there exists a $\sigma$-optimal layered permuton $\Pi$ with infinitely many layers, and let $\varepsilon$ be the length of its $(2k-3)$-th longest layer; note that $\varepsilon > 0$ by Lemma 9. By Lemma 10, every segment $[a, b]$ of $\Pi$ is either a layer of $\Pi$ or it contains a layer of length at least $(\varepsilon/4)^{|\sigma|}/k$. This implies that the number of layers of $\Pi$ is finite, in particular, the permuton $\Pi$ has no trivial layers, and that the number of layers of $\Pi$ is at most $2\lfloor k(4/\varepsilon)^{|\sigma|} \rfloor + 1$; this contradicts the assumption that $\Pi$ has infinitely many layers. $\square$

We next turn our attention to proving Theorem 5, which will follow from the next two lemmas.
**Lemma 11.** Let $\sigma$ be a layered permutation with $k$ layers and without consecutive singleton layers. Then every $\sigma$-optimal permutation has at least $k$ layers of length at least $\frac{1}{|\sigma|^3 k^2 |\sigma| + 1}$.

*Proof.* Let $\Pi$ be a $\sigma$-optimal layered permutation. Clearly, $\Pi$ has at least $k$ layers as otherwise $d(\sigma, \Pi) = 0$. Since the packing density of $\sigma$ is at least $k^{-|\sigma|}$, it holds that $d(\sigma, \Pi) \ge k^{-|\sigma|}$.

Let $r$ be the sum of the lengths of the $k-1$ largest layers of $\Pi$. Observe that $d(\sigma, \Pi) \le |\sigma|(1-r)$ (because every $\Pi$-random permutation that is $\sigma$ contains a point outside of the $k-1$ largest layers of $\Pi$), which implies that $\frac{1}{|\sigma| |k| |\sigma|} \le 1-r$. Let $[a, b]$ be the longest segment of $\Pi$ which does not contain any of the $k-1$ longest layers, and note that its length is at least $(1-r)/k$. By Lemma 8, this segment contains a layer of length at least

$$ \left( \frac{1-r}{k} \right) \left( \frac{1}{|\sigma|^2 k^{|\sigma|}} \right) \ge \frac{1}{|\sigma|^3 k^{2|\sigma|+1}}. $$

The statement of the lemma now follows.

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

The second lemma needed to prove Theorem 5 is the following.

**Lemma 12.** Let $\sigma$ be a layered permutation with layers of sizes $(\ell_1, \dots, \ell_k)$ and $k \ge 2$ such that $\ell_1 = \ell_k \ge 2$ and every two consecutive layers of $\sigma$ contain a layer of size $\ell_1 = \ell_k$. For every $C \in (0, 1)$, there exists $c \in (0, C)$ such that the following holds for every layered permutation $\pi$ of order at least $|\sigma|C^{-1}$ that has at least $k$ layers of size at least $C|\pi|$. If $\pi$ contains two consecutive layers of size at most $c|\pi|$ and $\pi'$ is a permutation obtained from $\pi$ by merging any two such layers, then $d(\sigma, \pi') \ge d(\sigma, \pi)$. In addition, if the merged layer has size at least $\ell_1$, then $d(\sigma, \pi') > d(\sigma, \pi)$.

*Proof.* Fix a permutation $\sigma$ with the properties given in the statement of the lemma and $C \in (0, 1)$. We prove that the statement of the lemma holds for $c \in (0, C)$, which is determined at the very end of the proof and which depends on $\sigma$ and $C$ only. Let $\pi$ be a permutation with the properties given in the statement of the lemma, let $\pi_a$ and $\pi_{a+1}$ be the layers of $\pi$ that are merged to obtain $\pi'$, and let $\alpha, \beta \in (0, 1)$ be such that $|\pi_a| = \alpha|\pi|$ and $|\pi_{a+1}| = \beta|\pi|$. In addition, for $i \in [1, k]$, let $p_i$ be the number of occurrences of the layered permutation with layers $(\ell_1, \dots, \ell_i)$ in $\pi$ before $\pi_a$, and let $q_i$ be the number of occurrences of the layered permutation with layers $(\ell_i, \dots, \ell_k)$ after $\pi_{a+1}$; and let $p_0 = q_{k+1} = 1$.

We next count the occurrences of $\sigma$ in $\pi$ and $\pi'$ similarly to the proofs of Claim 7.3 and Lemma 10. Considering which layers of $\sigma$ are sampled from $\pi_a$ and $\pi_{a+1}$, we rewrite $\binom{|\pi|}{|\sigma|} (d(\sigma, \pi') - d(\sigma, \pi))$ as

$$ \sum_{i=1}^{k} p_{i-1} q_{i+1} \left( \binom{|\pi_a|+|\pi_{a+1}|}{\ell_i} - \binom{|\pi_a|}{\ell_i} - \binom{|\pi_{a+1}|}{\ell_i} \right) - \sum_{i=1}^{k-1} p_{i-1} q_{i+2} \binom{|\pi_a|}{\ell_i} \binom{|\pi_{a+1}|}{\ell_{i+1}}. \quad (9) $$

First note that if $|\pi_a| + |\pi_{a+1}| \le \ell_1$, then the second sum is zero as $\ell_i = \ell_1$ or $\ell_{i+1} = \ell_1$ for every $i \in [1, k-1]$. So, if $|\pi_a| + |\pi_{a+1}| \le \ell_1$, then the conclusion of the lemma follows
since it holds that

$$ \left( \begin{array}{c} |\pi_a| + |\pi_{a+1}| \\ \ell_i \end{array} \right) \ge \left( \begin{array}{c} |\pi_a| \\ \ell_i \end{array} \right) + \left( \begin{array}{c} |\pi_{a+1}| \\ \ell_i \end{array} \right) $$

for every $i \in [k]$. Hence, we will assume that $|\pi_a| + |\pi_{a+1}| \ge \ell_1 + 1$ in the rest of the proof.

We next give a lower bound on the first sum in (9). We say that a layer of $\pi$ is big if its size is at least $C|\pi|$; note that $C|\pi| \ge |\sigma|$. Let $j$ be such that there are at least $j-1$ big layers before the layer $\pi_a$, at least $k-j$ big layers after the layer $\pi_{a+1}$, and $\ell_j = \ell_1$. It follows that

$$ p_{j-1}q_{j+1} \ge \prod_{i \ne j} \left( \begin{array}{c} C|\pi| \\ \ell_i \end{array} \right) \ge \prod_{i \ne j} \left( \frac{C|\pi|}{\ell_i} \right)^{\ell_i} = (C|\pi|)^{|\sigma|-\ell_1} \prod_{i \ne j} \ell_i^{-\ell_i} $$

Since the first sum in (9) is at least its $j$-th term, we obtain that the first sum in (9) is at least

$$ \begin{aligned} & (C|\pi|)^{|\sigma|-\ell_1} \prod_{i \ne j} \ell_i^{-\ell_i} \left( \begin{array}{c} (|\pi_a| + |\pi_{a+1}|) - (|\pi_a|) - (|\pi_{a+1}|) \\ \ell_1 \end{array} \right) \\ & \ge (C|\pi|)^{|\sigma|-\ell_1} \prod_{i \ne j} \ell_i^{-\ell_i} \times \frac{2|\pi_a||\pi_{a+1}|}{\ell_1(\ell_1-1)} \left( \frac{|\pi_a| + |\pi_{a+1}| - 2}{\ell_1 - 2} \right) \\ & > (C|\pi|)^{|\sigma|-\ell_1} \prod_{i \ne j} \ell_i^{-\ell_i} \times \frac{2|\pi_a||\pi_{a+1}|}{\ell_1^2} \left( \frac{|\pi_a| + |\pi_{a+1}| - 2}{\ell_1} \right)^{\ell_1-2} \\ & \ge (C|\pi|)^{|\sigma|-\ell_1} \prod_{i \ne j} \ell_i^{-\ell_i} \times \frac{2|\pi_a||\pi_{a+1}|}{\ell_1^2} \left( \frac{|\pi_a| + |\pi_{a+1}|}{3\ell_1} \right)^{\ell_1-2} \\ & \ge A|\pi|^{|\sigma|} \alpha\beta (\alpha + \beta)^{\ell_1-2} \ge A|\pi|^{|\sigma|} (\alpha^{\ell_1-1}\beta + \alpha\beta^{\ell_1-1}) \end{aligned} $$

where $A = \frac{2C^{|\sigma|-\ell_1}}{(3\ell_1)^{\ell_1} \prod_{i \in [k]} \ell_i^{\ell_i}}$ (note that $A$ depends on $\sigma$ and $C$ only).

We next find an upper bound on the second sum in (9). Let $i \in [1, k-1]$, and observe that $p_{i-1}q_{i+2}$ is at most the number of ways of choosing $|\sigma| - \ell_i - \ell_{i+1}$ points from a permutation of order $|\pi| - |\pi_a| - |\pi_{a+1}|$, i.e., $p_{i-1}q_{i+2} \le \binom{|\pi| - |\pi_a| - |\pi_{a+1}|}{|\sigma| - \ell_i - \ell_{i+1}}$. Therefore, the $i$-th summand of the second sum in (9) is at most

$$ \begin{aligned} & \left( \begin{array}{c} |\pi| - |\pi_a| - |\pi_{a+1}| \\ |\sigma| - \ell_i - \ell_{i+1} \end{array} \right) \left( \begin{array}{c} |\pi_a| \\ \ell_i \end{array} \right) \left( \begin{array}{c} |\pi_{a+1}| \\ \ell_{i+1} \end{array} \right) \\ & \le \left( \frac{e(|\pi| - |\pi_a| - |\pi_{a+1}|)}{|\sigma| - \ell_i - \ell_{i+1}} \right)^{|\sigma|-\ell_i-\ell_{i+1}} \left( \frac{e|\pi_a|}{\ell_i} \right)^{\ell_i} \left( \frac{e|\pi_{a+1}|}{\ell_{i+1}} \right)^{\ell_{i+1}} \\ & \le B|\pi|^{|\sigma|} (1 - \alpha - \beta)^{|\sigma|-\ell_i-\ell_{i+1}} \alpha^{\ell_i} \beta^{\ell_{i+1}} \\ & \le B|\pi|^{|\sigma|} \alpha^{\ell_i} \beta^{\ell_{i+1}} \le B|\pi|^{|\sigma|} (\alpha^{\ell_1} \beta + \alpha \beta^{\ell_1}) \end{aligned} $$

where $B = \max_{i \in [k]} \frac{e^{|\sigma|}}{\ell_i^{\ell_i} \ell_{i+1}^{\ell_{i+1}} (|\sigma|-\ell_i-\ell_{i+1})^{|\sigma|-\ell_i-\ell_{i+1}}}$ (again $B$ depends on $\sigma$ only).
We combine the bounds on the first and the second sum in (9) to obtain that

$$ 
\begin{aligned}
d(\sigma, \pi') - d(\sigma, \pi) &> \left(\frac{|\pi|}{|\sigma|}\right)^{-1} |\pi|^{\sigma} \left(A(\alpha^{\ell_1-1}\beta + \alpha\beta^{\ell_1-1}) - kB(\alpha^{\ell_1}\beta + \alpha\beta^{\ell_1})\right) \\
&> \left(\frac{|\sigma|!}{|\pi|^{\sigma|\sigma|}}\right) |\pi|^{\sigma} \left(A(\alpha^{\ell_1-1}\beta + \alpha\beta^{\ell_1-1}) - kB(\alpha^{\ell_1}\beta + \alpha\beta^{\ell_1})\right) \\
&> A(\alpha^{\ell_1-1}\beta + \alpha\beta^{\ell_1-1}) - kB(\alpha^{\ell_1}\beta + \alpha\beta^{\ell_1}).
\end{aligned}
$$

Hence, the lemma holds with $c = \min\{A/kB, C\}/2$. □

We are now ready to prove Theorem 5.

*Proof of Theorem 5.* Fix a layered permutation $\sigma$ of order $m$ and with layers of sizes $(\ell_1, \dots, \ell_k)$, $k \ge 2$, such that $\ell_1 = \ell_k \ge 2$ and every two consecutive layers of $\sigma$ contain a layer of size $\ell_1 = \ell_k$. In particular, $\sigma$ does not have consecutive singleton layers. Apply Lemma 12 with $C = \frac{1}{2m^3k^{2m+1}}$ to get a constant $c \in (0, C)$.

For the sake of contradiction, suppose that for every $n \in \mathbb{N}$ there exists a $\sigma$-optimal permutation $\pi_n$ with at least $n$ layers. Without loss of generality, we can assume also assume that $|\pi_n| \ge |\sigma|/C$ for every $n$ and that the sequence $(\pi_n)_{n \in \mathbb{N}}$ is convergent (as any sequence of permutations with increasing orders has a convergent subsequence), and let $\Pi$ be the limit permuton of $(\pi_n)_{n \in \mathbb{N}}$. Note that the permuton $\Pi$ is layered (by Lemma 6) and the density of $\sigma$ in $\Pi$ is the packing density of $\sigma$. Lemma 11 implies that the permuton $\Pi$ has $k$ layers of length at least $2C$. Hence, there exists $n_0 \in \mathbb{N}$ such that every permutation $\pi_n$, $n \ge n_0$, has $k$ layers of size at least $C|\pi_n|$ (cf. the proof of Lemma 6).

For $n \ge n_0$, define $\pi'_n$ to be a layered permutation obtained from the permutation $\pi_n$ by successively merging pairs of consecutive layers of size at most $c|\pi_n|$ as long as two consecutive layers of size at most $c|\pi_n|$ exist. Observe that the number of layers of $\pi'_n$ is at most $\lfloor 2/c \rfloor + 1$. By Lemma 12, it holds that $d(\sigma, \pi'_n) \ge d(\sigma, \pi_n)$, and since $\pi_n$ is a $\sigma$-optimal permutation, it actually holds that $d(\sigma, \pi'_n) = d(\sigma, \pi_n)$. So, Lemma 12 yields that no layer of $\pi'_n$ obtained by merging two or more layers of $\pi_n$ has size at least $\ell_1$. It follows that the number of layers of $\pi_n$ is at most $(\lfloor 2/c \rfloor + 1)(\ell_1 - 1)$, which is impossible if $n > (\lfloor 2/c \rfloor + 1)(\ell_1 - 1)$. The statement of the theorem follows. □

# 5 Conclusion

We conclude with five open problems focusing on the nature of the layered maximizers for a layered permutation $\sigma$. The first question asks whether the existence of near-$\sigma$-optimal sequence of layered permutations with a bounded number of layers implies that all $\sigma$-optimal layered permutations have a bounded number of layers.

**Problem 1.** Is there a layered permutation $\sigma$ such that there exists a near-$\sigma$-optimal sequence of layered permutations with a bounded number of layers but for every $k \in \mathbb{N}$ there exists a $\sigma$-optimal layered permutation (of some order) with at least $k$ layers?
In principle, the existence of a σ-optimal layered permutation with a bounded number of layers might depend on the order of a host permutation for some layered permutations σ.

**Problem 2.** Is there a layered permutation σ and an integer m such that for infinitely many $n \in \mathbb{N}$, there exists a σ-optimal layered permutation of order n with at most m layers, and still for every $k \in \mathbb{N}$, there exists $n \in \mathbb{N}$ such that every σ-optimal layered permutation of order n has at least k layers?

A σ-optimal permutation for a layered permutation σ need not be layered in general. For example, Albert et al. [1, Remark 2.3] observed that, for $\sigma = 43215$, the permutation

$$16, 15, \dots, 2, 1, 17, 19, 20, 18$$

is σ-optimal, but not layered. However, we do not know whether there exists such an example in the limit setting.

**Problem 3.** Is there a layered permutation σ such that there exists a σ-optimal permutation that is not layered?

The final two problems are limit analogues of Problem 1.

**Problem 4.** Is there a layered permutation σ such that there exist both a σ-optimal permutation with finitely many layers and a σ-optimal permutation with infinitely many layers?

**Problem 5.** Is there a layered permutation σ such that every σ-optimal permutation has finitely many layers but there exist σ-optimal permutations with an arbitrarily large number of layers?

## Acknowledgements

We thank the anonymous referee for their helpful comments.

## References

[1] M. H. Albert, M. D. Atkinson, C. C. Handley, D. A. Holton and W. Stromquist: *On packing densities of permutations*, Electron. J. Combin. **9** (2002), #R5.

[2] J. Balogh, P. Hu, B. Lidický, O. Pikhurko, B. Udvari and J. Volec: *Minimum number of monotone subsequences of length 4 in permutations*, Combin. Probab. Comput. **24** (2015), 658–679.

[3] R. W. Barton: *Packing densities of patterns*, Electron. J. Combin. **11**(1) (2004), #R80.

[4] J. d. O. Bastos and L. N. Coregliano: *Packing densities of layered permutations and the minimum number of monotone sequences in layered permutations*, Discrete Math. Theor. Comput. Sci. **18**(2) (2016).
[5] T. Chan, D. Král', J. A. Noel, Y. Pehova, M. Sharifzadeh and J. Volec: *Character-ization of quasirandom permutations by a pattern sum*, Random Struct. Algor. **57** (2020), 920–939.

[6] 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.

[7] P. A. Hästö: *The packing density of other layered permutations*, Electron. J. Combin. **9**(2) (2002–3), #R1.

[8] M. Hildebrand, B. E. Sagan and V. R. Vatter: *Bounding quantities related to the packing density of $1(l+1)l \cdots 2$, Adv. in Appl. Math.* **33** (2004), 633–653.

[9] C. Hoppen, Y. Kohayakawa, C. G. T. de A. Moreira and R. M. Sampaio: *Limits of permutation sequences through permutation regularity*, arXiv:1106.1663 (2011).

[10] C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Ráth and R. Menezes Sampaio: *Limits of permutation sequences*, J. Comb. Theory, Ser. B **103** (2013), 93–113.

[11] D. Král' and O. Pikhurko: *Quasirandom permutations are characterized by 4-point densities*, Geom. Funct. Anal. **23** (2013), 570–579.

[12] M. Kurečka: *Lower bound on the size of a quasirandom forcing set of permutations*, Combin. Probab. Comput. **31** (2022), 304–319.

[13] P.-L. Méliot: *A survey of the theory of graphons and permutons*, unpublished manuscript available at http://www.imo.universite-paris-saclay.fr/~meliot/surveys/graphon_survey.pdf.

[14] J. S. Myers: *The minimum number of monotone subsequences*, Electron. J. Combin. **9** (2002–3), #R4.

[15] C. B. Presutti: *Determining lower bounds for packing densities of non-layered patterns using weighted templates*, Electron. J. Combin. **15** (2008), #R50.

[16] A. L. Price: *Packing densities of layered patterns*, Ph.D. thesis, University of Pennsylvania (1997).

[17] J. Sliačan and W. Stromquist: *Improving bounds on packing densities of 4-point permutations*, Discrete Math. Theor. Comput. Sci. **19** (2017), #3, 18pp.

[18] W. Stromquist: *Packing layered posets into posets* (1993), unpublished manuscript available at http://walterstromquist.com/POSETS.DOC.

[19] D. Warren: *Optimal packing behavior of some 2-block patterns*, Ann. Comb. **8** (2004), 355–367.

[20] D. Warren: *Optimizing the packing behavior of layered permutation patterns*, Ph.D. thesis, University of Florida (2005).

[21] D. Warren: *Packing densities of more 2-block patterns*, Adv. in Appl. Math. **36** (2006), 202–211.

[22] H. S. Wilf: *The patterns of permutations*, Discrete Math. **257** (2002), 575–583.