# An example related to Whitney’s extension problem for
$L^{2,p}(\mathbb{R}^{2})$ when $1<p<2$

Jacob Carruth and Arie Israel

(December 2023)

###### Abstract

In this paper, we prove the existence of a bounded linear extension operator
$T:L^{2,p}(E)\rightarrow L^{2,p}(\mathbb{R}^{2})$ when $1<p<2$, where
$E\subset\mathbb{R}^{2}$ is a certain discrete set with fractal structure. Our
proof makes use of a theorem of Fefferman-Klartag [3] on the existence of
linear extension operators for radially symmetric binary trees.

##  1 Introduction

Let $\mathbb{X}(\mathbb{R}^{n})$ be a space of continuous, real-valued
functions on $\mathbb{R}^{n}$ equipped with a norm (or seminorm) $||\cdot||$.
For any subset $\Omega\subset\mathbb{R}^{n}$, define the trace norm (or
seminorm) of a continuous function $f:\Omega\rightarrow\mathbb{R}$ by

$||f||_{\mathbb{X}(\Omega)}=\inf\\{||F||:F|_{\Omega}=f\\}.$

The _trace space_ $\mathbb{X}(\Omega)$ is then defined to be the space of
continuous functions $f:\Omega\rightarrow\mathbb{R}$ with finite trace norm.

We say that a linear map
$T:\mathbb{X}(\Omega)\rightarrow\mathbb{X}(\mathbb{R}^{n})$ is a _linear
extension operator for $\mathbb{X}(\Omega)$_ provided that $(Tf)|_{\Omega}=f$
for all $f\in\mathbb{X}(\Omega)$. We say that _$\mathbb{X}(\Omega)$ admits a
bounded linear extension operator_ if there exists a constant $C$ (determined
only by the function space $\mathbb{X}(\mathbb{R}^{n})$) such that there
exists a bounded linear extension operator for $\mathbb{X}(\Omega)$ with
operator norm at most $C$. One formulation of the _Whitney extension problem_
for $\mathbb{X}(\mathbb{R}^{n})$ asks whether $\mathbb{X}(\Omega)$ admits a
bounded linear extension operator for every subset
$\Omega\subset\mathbb{R}^{n}$.

Let $\mathbb{X}(\mathbb{R}^{n})=L^{m,p}(\mathbb{R}^{n})$ denote the
(homogeneous) Sobolev space of all functions
$F:\mathbb{R}^{n}\rightarrow\mathbb{R}$ whose (distributional) partial
derivatives of order $m$ belong to $L^{p}(\mathbb{R}^{n})$, equipped with the
seminorm
$\|F\|_{L^{m,p}(\mathbb{R}^{n})}=\|\nabla^{m}F\|_{L^{p}(\mathbb{R}^{n})}$. We
assume that $\frac{n}{m}<p<\infty$, so that functions $F\in
L^{m,p}(\mathbb{R}^{n})$ are continuous – this ensures that the trace space
$L^{m,p}(\Omega)$ is well-defined for an arbitrary subset
$\Omega\subset\mathbb{R}^{n}$.

In [2], the second-named author, C. Fefferman, and G.K. Luli proved that
$L^{m,p}(\Omega)$ admits a bounded linear extension operator when $p>n$, with
operator norm at most a constant $C=C(m,n,p)$, for an arbitrary subset
$\Omega\subset\mathbb{R}^{n}$. When $p$ is in the range $\frac{m}{n}<p\leq n$,
however, it is unknown whether such an operator exists in general.

The first nontrivial case in this range is the space
$\mathbb{X}=L^{2,p}(\mathbb{R}^{2})$ for $1<p<2$ (when $p=2$, it is easy to
construct a bounded linear extension operator thanks to the Hilbert space
structure). In this paper, we construct a bounded linear extension operator
for $L^{2,p}(E)$ for a particular set $E\subset\mathbb{R}^{2}$ to be defined
below. This set $E$ appears to be exceptional. For a variety of sets
$\Omega\subset\mathbb{R}^{2}$ it is possible to construct a bounded linear
extension operator for $L^{2,p}(\Omega)$ by making certain analogies with the
case $p>2$. Our construction for $L^{2,p}(E)$, however, requires completely
new ideas.

We now define the set $E$. We introduce a real number $\varepsilon\in(0,1/2)$.
We assume that $\varepsilon$ is smaller than some absolute constant. For an
integer $L\geq 1$, we define

$\Delta=\varepsilon^{L}.$

The set $E$ is of the form

$E=E_{1}\cup E_{2},$

where

$\displaystyle
E_{1}=\\{(\Delta\mathbb{Z})\cap[-1,1]\\}\times\\{0\\}\;\mbox{and}$
$\displaystyle
E_{2}=\Big{\\{}(z,\Delta):z=\sum_{\ell=1}^{L}s_{\ell}\varepsilon^{\ell},s_{\ell}\in\\{-1,+1\\}\Big{\\}},$

Accordingly, $E_{1}$ is a set of equispaced $\Delta$-separated points on the
line $x_{2}=0$, and $E_{2}$ is a set of points of separation $\geq\Delta$ on
the line $x_{2}=\Delta$. For convenience, we assume that for every
$(x,\Delta)\in E_{2}$ we have $(x,0)\in E_{1}$. We can ensure this by, e.g.,
taking $\varepsilon=1/N$ for a large, positive integer $N$.

In this paper, we prove the following theorem.

######  Theorem 1.

Let $1<p<2$. There exists a bounded linear extension operator
$T:L^{2,p}(E)\rightarrow L^{2,p}(\mathbb{R}^{2})$, depending on $p$,
satisfying

$\|Tf\|_{L^{2,p}(\mathbb{R}^{2})}\leq C\|f\|_{L^{2,p}(E)}\;\text{for
any}\;f\in L^{2,p}(E)$

for some constant $C$ depending only on $p$.

We now say a bit about the construction of the operator $T$. We fix a square
$Q^{0}\subset\mathbb{R}^{2}$ containing $E$ with diameter $\sim 1$. Given
$f:E\rightarrow\mathbb{R}$, we will describe how to produce a function $F\in
L^{2,p}(Q^{0})$ satisfying $F|_{E}=f$ and having the property that

$||F||_{L^{2,p}(Q^{0})}\leq C||G||_{L^{2,p}(\mathbb{R}^{2})}$ (1)

for any $G\in L^{2,p}(\mathbb{R}^{2})$ for which $G|_{E}=f$. Once we
accomplish this, it is not difficult to deduce Theorem 1.

We first partition the square $Q^{\circ}$ into a Calderón-Zygmund
decomposition CZ, which is a finite family of dyadic squares $Q\subset Q^{0}$
with pairwise disjoint interiors. Our decomposition is a version of the
Whitney decomposition of $Q^{0}\setminus E$ truncated at scale $\sim\Delta$.
Briefly, every $Q\in\text{CZ}$ has sidelength
$\delta_{Q}\approx\Delta+\text{dist}(Q,E)$ and satisfies $\\#(1.1Q\cap E)\leq
1$. In particular, the smallest cubes in CZ have sidelength proportional to
$\Delta$ and distance to $E$ bounded by $C\Delta$ – see section 3 for further
details. Our function $F\in L^{2,p}(Q^{0})$ takes the form

$F(x)=\sum_{Q\in\text{CZ}}\theta_{Q}(x)\cdot P_{Q}(x),$ (2)

where $\\{\theta_{Q}\\}_{Q\in\text{CZ}}$ is a Whitney partition of unity
subordinate to CZ – more precisely, (1) $\sum_{Q}\theta_{Q}=1$ on $Q^{0}$, (2)
$\text{supp}(\theta_{Q})\subset 1.1Q$, and (3)
$|\nabla^{k}\theta_{Q}|\lesssim\delta_{Q}^{-k}$ for each $Q\in\text{CZ}$ – and
each $P_{Q}$ is an affine polynomial satisfying

$P_{Q}=f\mbox{ on }1.1Q\cap E.$ (3)

Using (3) and the support condition on $\theta_{Q}$, we see that the function
$F$ will satisfy $F|_{E}=f$. For each $Q\in\text{CZ}$, $P_{Q}$ is of the form

$P_{Q}(z)=L_{Q}(z)+\eta_{Q}\cdot
z^{(2)}\;\text{for}\;z=(z^{(1)},z^{(2)})\in\mathbb{R}^{2},$

where $\eta_{Q}$ is a real number and $L_{Q}$ is an affine polynomial
satisfying $\partial_{2}L_{Q}=0$. Due to the structure of the set $E_{1}$, our
hand is essentially forced when it comes to choosing the $L_{Q}$’s –
specifically, we demand that each $L_{Q}$ agrees with the function $f$ at two
suitably chosen points of the set $E_{1}$. The bulk of the work, then, is in
choosing the numbers $\\{\eta_{Q}\\}_{Q\in\text{CZ}}$ to ensure a certain
natural _compatibility condition_ on the family $\\{P_{Q}\\}_{Q\in\text{CZ}}$,
namely, the condition:

$\sum_{Q,Q^{\prime}\in\text{CZ},Q\leftrightarrow
Q^{\prime}}\delta_{Q}^{2-p}|\nabla P_{Q}-\nabla
P_{Q^{\prime}}|^{p}\lesssim\|G\|_{L^{2,p}(\mathbb{R}^{2})}^{p},$ (4)

where $Q\leftrightarrow Q^{\prime}$ denotes the property that $1.1Q\cap
1.1Q^{\prime}\neq\emptyset$ for two squares $Q,Q^{\prime}\in\text{CZ}$ (we say
that $Q$ “touches” $Q^{\prime}$), and $G\in L^{2,p}(\mathbb{R}^{2})$ is any
function satisfying $G|_{E}=f$. Estimate (4) is the essential ingredient in
the proof of the norm bound (1) for the function $F$ defined in (2).

Roughly speaking, each $\eta_{Q}$ corresponds to the average $x^{(2)}$-partial
derivative of $F$ on the square $Q$. Since the value of $f$ near points of the
set $E_{2}$ is our only source of information about the $x^{(2)}$-partial
derivative of $F$, we make use of a natural hierarchical clustering
$\mathcal{C}$ of the set $E_{2}$ to choose the $\eta_{Q}$’s.

Elements $C\in\mathcal{C}$ correspond to the subsets of $E_{2}$ of the form
$C(s_{1},\cdots,s_{k}):=\\{(z,\Delta):z=\sum_{\ell=1}^{L}s_{\ell}\epsilon^{\ell},\;s_{k+1},\cdots,s_{L}\in\\{-1,+1\\}\\}$
for fixed $(s_{1},\cdots,s_{k})\in\\{-1,+1\\}^{k}$. The smallest clusters
correspond to the $2^{L}$ different singleton sets in $E_{2}$ (when $k=L$),
and the largest cluster corresponds to $C=E_{2}$ (when $k=0$). Distinct
clusters are “well-separated” in the sense that
$\text{dist}(C_{1},C_{2})\gg\max\\{\mathrm{diam}(C_{1}),\mathrm{diam}(C_{2})\\}$
for $C_{1},C_{2}\in\mathcal{C}$, $C_{1}\neq C_{2}$.

The set of clusters $\mathcal{C}$ has the structure of a rooted binary tree of
depth $L$. The clusters corresponding to the leaves of the tree are the
singletons $\\{z\\}$ ($z\in E_{2}$), and $E_{2}$ is the root of $\mathcal{C}$.

To every square $Q\in\text{CZ}$, we associate a cluster $C_{Q}\in\mathcal{C}$.
If $1.1Q\cap E_{2}\neq\emptyset$ then $Q$ is associated to the singleton
cluster $C_{Q}=\\{x_{Q}\\}$ where $x_{Q}$ is a point of $1.1Q\cap E_{2}$. To
every other square $Q$ we associate a cluster $C_{Q}\in\mathcal{C}$ that is
nearby to $Q$.

We then introduce real numbers $\\{\eta_{C}\\}_{C\in\mathcal{C}}$ and
postulate that

$\eta_{Q}=\eta_{C_{Q}}\;\text{for every}\;Q\in\text{CZ}.$ (5)

For each $z=(z^{(1)},\Delta)\in E_{2}$, we define

$\eta_{\\{z\\}}=\frac{f(z)-f(z^{(1)},0)}{\Delta}.$

This is natural, as for squares $Q\in\text{CZ}$ satisfying $1.1Q\cap
E_{2}\neq\emptyset$ we will need to choose $\eta_{Q}=\eta_{\\{x_{Q}\\}}$ where
$x_{Q}\in 1.1Q\cap E_{2}$, to ensure that $P_{Q}$ satisfies (3).

Now that we have chosen $(\eta_{\\{z\\}})_{z\in E_{2}}$, we need to choose the
remaining $\eta_{C}$ so as to establish the compatibility condition (4) for
the $P_{Q}$. We use the following theorem of C. Fefferman and B. Klartag,
proved in [3].

######  Theorem 2 (Fefferman-Klartag, 2023).

Consider a full, binary tree of depth $N$ with vertices $V$. Let $V_{k}$
denote the set of vertices of depth $k$. For any $v\in V_{k}$ ($k=1,\dots,N$),
let $\pi(v)$ denote the parent of $v$.

Write $\partial V\subset V$ to denote the set of leaves of $V$ (i.e.,
$\partial V=V_{N}$). Let $\mathbb{R}^{V}$ and $\mathbb{R}^{\partial V}$ denote
the sets of real-valued functions on $V$ and $\partial V$, respectively.

Given weights $w_{1},\dots,w_{N}>0$, define the $L^{1,p}(V)$-seminorm by

$\|\Phi\|_{L^{1,p}(V)}=\bigg{(}\sum_{k=1}^{N}w_{k}\sum_{v\in
V_{k}}|\Phi(\pi(v))-\Phi(v)|^{p}\bigg{)}^{1/p}\;\text{for
any}\;\Phi\in\mathbb{R}^{V}.$ (6)

Define the $L^{1,p}$ trace seminorm by

$\|\phi\|_{L^{1,p}(\partial
V)}=\inf\\{\|\Phi\|_{L^{1,p}(V)}:\Phi|_{E}=\phi\\}\;\text{for
any}\;\phi\in\mathbb{R}^{\partial V}.$

There exists a linear operator $H:\mathbb{R}^{\partial
V}\rightarrow\mathbb{R}^{V}$ with the following properties:

  1. 1.

$H$ is an extension operator, i.e.,

$H\phi|_{\partial V}=\phi\;\text{for any}\;\phi\in\mathbb{R}^{\partial V}.$

  2. 2.

For any $\phi\in\mathbb{R}^{\partial V}$, we have

$\|H\phi\|_{L^{1,p}(V)}\lesssim\|\phi\|_{L^{1,p}(\partial V)}.$

We apply Theorem 2 to the binary tree $\mathcal{C}$ equipped with a natural
set of edge weights, and choose the $\eta_{C}$ by applying the extension
operator $H$ to the data $\\{\eta_{\\{z\\}}\\}_{z\in E_{2}}$; because the
resulting choice of $\\{\eta_{C}\\}$ minimizes the seminorm (6), one can show
the resulting polynomials $\\{P_{Q}\\}$ defined in terms of the
$\\{\eta_{Q}\\}$ (which are related to the $\\{\eta_{C}\\}$ in (5)) will
satisfy (4). As mentioned before, the norm bound (1) follows as a consequence
of this condition.

Because the $\eta_{\\{z\\}}$ depend linearly on $f$, and the $\eta_{C}$ depend
linearly on $\\{\eta_{\\{z\\}}\\}_{z\in E_{2}}$, it is obvious that the
$P_{Q}$ depend linearly on $f$, and so, $F$ depends linearly on $f$.

It is finally trivial to extend $F:Q^{0}\rightarrow\mathbb{R}$ to a function
$\widetilde{F}:\mathbb{R}^{2}\rightarrow\mathbb{R}$ satisfying
$\|\widetilde{F}\|_{L^{2,p}(\mathbb{R}^{2})}\leq C\|F\|_{L^{2,p}(Q^{0})}$.
Since $F\in L^{2,p}(Q^{0})$ is an extension of $f$ satisfying the norm bound
(1), we deduce that $\widetilde{F}\in L^{2,p}(\mathbb{R}^{2})$ is an extension
of $f$ satisfying $\|\widetilde{F}\|_{L^{2,p}(\mathbb{R}^{2})}\leq
C\|G\|_{L^{2,p}(\mathbb{R}^{2})}$ for any $G\in L^{2,p}(\mathbb{R}^{2})$ with
$G|_{E}=f$. Thus, we cam set $Tf=\widetilde{F}$, and $T$ is a bounded linear
extension operator for $L^{2,p}(E)$.

This concludes our overview of the proof of Theorem 1.

We remark that when $\varepsilon$ is bounded away from a certain “critical
value” $\varepsilon_{0}=(1/2)^{1/(2-p)}$, it is possible to prove Theorem 1
without invoking Theorem 2. In particular, one can construct an extension
operator for $L^{2,p}(E)$ by making certain analogies with the case $p>2$.
When $\varepsilon=\varepsilon_{0}$, however, we know of no such construction.

Throughout this paper we write $C,C^{\prime},C^{\prime\prime},\dots$ to denote
positive constants. Such constants are allowed to depend only on $p$ (but not
on $\varepsilon,L$). We write $C_{X},C^{\prime}_{X},\dots$ for positive
constants depending on some quantity $X$. For positive real numbers $A,B$ we
write $A\lesssim B$ if there exists a constant $C$ such that $A\leq CB$ and
$A\lesssim_{X}B$ if $A\leq C_{X}B$. We write $A\approx B$ if $A\lesssim B$ and
$A\lesssim B$.

We thank Charles Fefferman, Anna Skorobogotova, and Ignacio Uriarte-Tuero, for
helpful conversations. We also thank Pavel Shvartsman for suggesting that we
use the Hardy-Littlewood maximal function; this greatly simplified some of the
arguments.

##  2 Preliminaries

For a (Lebesgue) measurable function $F$ defined on a measurable set
$S\subset\mathbb{R}^{2}$ with $|S|>0$, we write $(F)_{S}:=|S|^{-1}\int_{S}F\
dx$. We begin by stating a couple of standard inequalities for Sobolev spaces.
For details see, e.g., [4].

Given an annulus $A=\\{x\in\mathbb{R}^{2}:r\leq|x-x_{0}|\leq R\\}$ with inner
radius $r$ and outer radius $R$, the _thickness ratio_ of $A$ is defined to be
the quantity $R/r$.

######  Lemma 1.

Let $\Omega\subset\mathbb{R}^{2}$ be a square, a ball, or an annulus with
thickness ratio at most $C_{0}\in[1,\infty)$. Then the following hold.

  1. 1.

Let $1<r<2$, and $r^{\prime}=2r/(2-r)$. Then for any $F\in
L^{2,r}(\mathbb{R}^{2})$ we have

$\bigg{(}\int_{\Omega}|\nabla F(x)-(\nabla F)_{\Omega}|^{r^{\prime}}\
dx\bigg{)}^{1/r^{\prime}}\lesssim_{r,C_{0}}\|F\|_{L^{2,r}(\Omega)}.$

  2. 2.

Let $q>2$. Then for any $F\in L^{1,q}(\Omega)$ we have (after potentially
redefining $F$ on a set of measure 0) that

$|F(x)-F(y)|\lesssim_{q,C_{0}}|x-y|^{1-2/q}\|F\|_{L^{1,q}}\;\text{for
any}\;x,y\in\Omega.$

We use these inequalities to prove the following basic lemma.

######  Lemma 2.

Let $\Omega\subset\mathbb{R}^{2}$ be a square, a ball, or an annulus with
thickness ratio at most $C_{0}\in[1,\infty)$ and let $1<r<2$. For any $F\in
L^{2,r}(\Omega)$ and any $y\in\Omega$, we define a function
$T_{y,\Omega}(F):\mathbb{R}^{2}\rightarrow\mathbb{R}$ by

$T_{y,\Omega}(F)(x)=F(y)+(\nabla F)_{\Omega}\cdot(x-y).$

We then have

$|T_{x,\Omega}(F)(y)-T_{z,\Omega}(F)(y)|\lesssim_{r,C_{0}}\|F\|_{L^{2,r}(\Omega)}|x-z|^{2-2/r}\;\text{for
any}\;x,z\in\Omega.$

In particular,

$\|F-T_{y,\Omega}(F)\|_{L^{\infty}(\Omega)}\lesssim_{r,C_{0}}\mathrm{diam}(\Omega)^{2-2/r}\|F\|_{L^{2,r}(\Omega)}.$

###### Proof.

Let $r^{\prime}=2r/(2-r)$. For any $x\in\mathbb{R}^{2}$ define
$G_{x}:\mathbb{R}^{2}\rightarrow\mathbb{R}$ by

$G_{x}(y)=T_{y,\Omega}(F)(x).$

By Part 1 of Lemma 1, we have

$\|G_{x}\|_{L^{1,r^{\prime}}(\Omega)}\lesssim_{r,C_{0}}\|F\|_{L^{2,r}(\Omega)}.$

Note that $r^{\prime}>2$, since $r<2$. Applying Part 2 of Lemma 1 to the
function $G_{x}$ proves the lemma. ∎

Let $B(z,r)$ denote the ball of radius $r>0$ centered at $z\in\mathbb{R}^{2}$,
and let $\mathcal{M}$ denote the uncentered Hardy-Littlewood maximal operator,
i.e.,

$(\mathcal{M}f)(x)=\sup_{B(z,r)\ni x}\frac{1}{|B(z,r)|}\int_{B(z,r)}f(y)\
dy\;\text{for any}\;f\in L^{1}_{\text{loc}}(\mathbb{R}^{2}).$

Recall that $\mathcal{M}$ is a bounded operator from $L^{q}(\mathbb{R}^{2})$
to $L^{q}(\mathbb{R}^{2})$ for any $1<q\leq\infty$ (see, e.g., [5]).

##  3 The CZ decomposition

We will work with squares in $\mathbb{R}^{2}$; by this we mean an axis
parallel square of the form $Q=[a_{1},b_{1})\times[a_{2},b_{2})$. We let
$\delta_{Q}$ denote the sidelength of such a square $Q$. To _bisect_ a square
$Q$ is to partition $Q$ into squares $Q_{1},Q_{2},Q_{3},Q_{4}$, where
$\delta_{Q_{i}}=\delta_{Q}/2$ for each $i=1,2,3,4$. We refer to the $Q_{i}$ as
the _children_ of $Q$.

We define a square $Q^{0}=[-4,4)\times[-4,4)$; note that $E\subset Q^{0}$. A
_dyadic_ square $Q$ is one that arises from repeated bisection of $Q^{0}$.
Every dyadic square $Q\neq Q^{0}$ is the child of some square $Q^{\prime}$; we
call $Q^{\prime}$ the _parent_ of $Q$ and denote this by $(Q)^{+}=Q^{\prime}$.

We say that two dyadic square $Q,Q^{\prime}$ _touch_ if $(1.1Q\cap
1.1Q^{\prime})\neq\emptyset$. We write $Q\leftrightarrow Q^{\prime}$ to denote
that $Q$ touches $Q^{\prime}$.

For any dyadic square $Q$, we define a collection $\text{CZ}(Q)$, called the
_Calderón-Zygmund decomposition of_ $Q$, by setting

$\text{CZ}(Q)=\\{Q\\}\;\text{if }\\#(3Q\cap E)\leq 1,$

and

$\text{CZ}(Q)=\bigcup\\{\text{CZ}(Q^{\prime}):(Q^{\prime})^{+}=Q\\}\;\text{if}\;\\#(3Q\cap
E)\geq 2.$

We write $\text{CZ}=\text{CZ}(Q^{0})$. Note that $\text{CZ}\neq\\{Q^{0}\\}$
because $\\#(3Q^{0}\cap E)=\\#E\geq 2$. Then CZ is a partition of $Q^{0}$ into
dyadic squares $Q$ satisfying

$\delta_{Q}\geq\frac{\Delta}{9}.$ (7)

To see this, observe that for any $Q\in\text{CZ}$ we have $\\#(3Q^{+}\cap
E)\geq 2$ and $3Q^{+}\subset 9Q$. Since points of $E$ are $\Delta$-separated,
we have $\delta_{Q}\geq\Delta/9$, as claimed.

We now summarize some basic properties of the collection CZ.

######  Lemma 3.

The collection CZ has the following properties:

  1. 1.

For any $Q\in\emph{CZ}$, we have $\\#(1.1Q\cap E)\leq 1$ and $\\#(3Q^{+}\cap
E)\geq 2$.

  2. 2.

For any $Q,Q^{\prime}\in\emph{CZ}$ with $Q\leftrightarrow Q^{\prime}$, we have
$\frac{1}{2}\delta_{Q}\leq\delta_{Q^{\prime}}\leq 2\delta_{Q}$.

  3. 3.

For any $Q\in\emph{CZ}$, we have

$\\#\\{Q^{\prime}:Q\leftrightarrow Q^{\prime}\\}\lesssim 1.$

  4. 4.

For any $x\in\mathbb{R}^{2}$,

$\\#\\{Q\in\emph{CZ}:x\in 1.1Q\\}\lesssim 1.$

  5. 5.

For any $Q\in\emph{CZ}$ with $\\#(1.1Q\cap E)=0$, we have
$\delta_{Q}\approx\emph{dist}(Q,E)$.

We omit the proof of Lemma 3, as this type of decomposition is standard in the
literature; see, e.g., [1].

We say that $Q\in\text{CZ}$ is a _boundary square_ if $1.1Q\cap\partial
Q^{0}\neq\emptyset$. Denote the set of boundary squares by
$\partial\text{CZ}$.

Observe that every $Q\in\partial\text{CZ}$ satisfies $\delta_{Q}\geq 1$.
Indeed, this follows because $E\subset[-1,1]\times[-1,1]$, and if $Q$ is a
dyadic square intersecting the boundary of $Q^{0}$ with $\delta_{Q}=1$ then
$3Q$ is disjoint from $E$. We denote $z_{0}:=(-1,0)$, $w_{0}:=(1,0)$ to be the
points of maximal separation in $E_{1}$. Note that

$z_{0},w_{0}\in 50Q\mbox{ for all }Q\in\partial\text{CZ}.$ (8)

We say that a square $Q\in\text{CZ}$ is of _Type I_ if $\\#(1.1Q\cap
E_{1})=1$, _Type II_ if $\\#(1.1Q\cap E_{2})=1$, and _Type III_ if
$\\#(1.1Q\cap E)=0$. We denote the collection of squares of Type I, II, and
III by $\text{CZ}_{I}$, $\text{CZ}_{II}$, and $\text{CZ}_{III}$, respectively.
These collections form a partition of CZ because $\\#(3Q\cap E)\leq 1$ for any
$Q\in\text{CZ}$ by construction.

Observe that $\partial\text{CZ}\subset\text{CZ}_{III}$.

From Property 1 of Lemma 3, it is easy to deduce that

$\delta_{Q}\approx\Delta\;\text{for
every}\;Q\in\text{CZ}_{I}\cup\text{CZ}_{II}.$ (9)

From Property 5 of Lemma 3 we have

$\delta_{Q}\approx\text{dist}(Q,E)\;\text{for every}\;Q\in\text{CZ}_{III}.$

Combining this with (7), and using that points of $E$ are $\Delta$-separated,
we get

$\delta_{Q}\approx\text{dist}(Q,E_{1})\;\text{for
every}\;Q\in\text{CZ}_{III}.$

Combining this with (7), (9) gives

$\delta_{Q}\approx(\Delta+\text{dist}(Q,E_{1}))\;\text{for
any}\;Q\in\text{CZ}.$ (10)

For each $Q\in\text{CZ}_{II}$ we let $x_{Q}$ be the unique point in
$(1.1Q)\cap E=(1.1Q)\cap E_{2}$. Note that $x_{Q}$ is undefined for
$Q\in\text{CZ}\setminus\text{CZ}_{II}$.

For each $Q\in\text{CZ}$ we associate a pair of points $z_{Q},w_{Q}\in E_{1}$.
We list the key properties of these points in the next lemma.

######  Lemma 4.

For each $Q\in\emph{CZ}$ there exist points $z_{Q},w_{Q}\in(50Q)\cap E_{1}$,
satisfying the conditions below.

  1. 1.

$|z_{Q}-w_{Q}|\approx\delta_{Q}$.

  2. 2.

If $Q\in\text{CZ}_{I}$ then $z_{Q}\in(1.1Q)\cap E_{1}$.

  3. 3.

If $Q\in\text{CZ}_{II}$ then $z_{Q}=(x_{Q}^{(1)},0)$, where
$x_{Q}=(x_{Q}^{(1)},\Delta)$ is the unique point in $1.1Q\cap E_{2}$.

  4. 4.

If $Q\in\partial\text{CZ}$ then $z_{Q}=z_{0}$ and $w_{Q}=w_{0}$.

###### Proof.

We first check that for each $Q\in\text{CZ}$ there exist points
$z_{Q},w_{Q}\in(50Q)\cap E_{1}$ satisfying $|z_{Q}-w_{Q}|\approx\delta_{Q}$.
Fix $Q\in\text{CZ}$. By definition of the Calderón-Zygmund stopping rule, the
set $3Q^{+}\cap E$ is nonempty; also, $3Q^{+}\subset 9Q$ by properties of
dyadic squares, so $9Q\cap E$ is nonempty. Thus, either $9Q\cap
E_{1}\neq\emptyset$ or $9Q\cap E_{2}\neq\emptyset$. We claim that $30Q\cap
E_{1}$ is nonempty in either case. This is true if $9Q\cap
E_{1}\neq\emptyset$. On the other hand if $9Q\cap E_{2}\neq\emptyset$, we let
$y_{Q}$ be a point of $9Q\cap E_{2}$, and note that
$\text{dist}(y_{Q},E_{1})=\Delta\leq 9\delta_{Q}$, hence, $(30Q)\cap
E_{1}\neq\emptyset$. In any case, we have shown $(30Q)\cap
E_{1}\neq\emptyset$. Once that is established, by the definition of $E_{1}$ as
a sequence of $\Delta$-separated points and because $9\delta_{Q}\geq\Delta$,
we see that $50Q\cap E_{1}$ contains at least two points. Thus, we can order
the points of $(50Q)\cap E_{1}\subset\mathbb{R}\times\\{0\\}$ according to the
order on the real number line and let $z_{Q}$ and $w_{Q}$ be the distinct
minimal and maximal points in the set $(50Q)\cap E_{1}$. Obviously then
$|z_{Q}-w_{Q}|\approx\delta_{Q}$.

We make small modifications to the construction to establish conditions 2-4 of
the lemma.

If $Q\in\text{CZ}_{I}$ then we instead select $z_{Q}\in(1.1)Q\cap E_{1}$ and
then let $w_{Q}\in E_{1}$ be adjacent to $z_{Q}$ so that
$|z_{Q}-w_{Q}|=\Delta\approx\delta_{Q}$. Since $9\delta_{Q}\geq\Delta$, it
follows that $w_{Q}\in 50Q$, so $w_{Q}\in 50Q\cap E_{1}$, as desired.

If $Q\in\text{CZ}_{II}$ then we instead choose $z_{Q}\in E_{1}$ to be the
point directly below $x_{Q}\in(1.1Q)\cap E_{2}$ so that
$|z_{Q}-x_{Q}|=\Delta$. We then let $w_{Q}\in E_{1}$ be a point adjacent to
$z_{Q}$, so that $|w_{Q}-z_{Q}|=\Delta\approx\delta_{Q}$. As before, since
$x_{Q}\in 1.1Q$ and $9\delta_{Q}\geq\Delta$, we see that $z_{Q},w_{Q}\in 50Q$,
as desired.

If $Q\in\partial\text{CZ}$ then we define $z_{Q}=z_{0}$ and $w_{Q}=w_{0}$,
where $z_{0}=(-1,0)$ and $w_{0}=(1,0)$. Note that $|z_{Q}-w_{Q}|\approx
1\approx\delta_{Q}$. Before we established that $z_{0},w_{0}\in 50Q$, so, in
particular, $z_{Q},w_{Q}\in 50Q\cap E_{1}$, as desired.

∎

##  4 Constructing the interpolant

Let $f:E\rightarrow\mathbb{R}$. In this section, we will construct a function
$F:Q^{0}\rightarrow\mathbb{R}$ satisfying $F|_{E}=f$.

Let $\\{\theta_{Q}\\}_{Q\in\text{CZ}}$ be a partition of unity subordinate to
CZ constructed so that the following properties hold. For any $Q\in\text{CZ}$,
we have:

  1. (POU1)

$\text{supp}(\theta_{Q})\subset 1.1Q$.

  2. (POU2)

For any $|\alpha|\leq 2$,
$\|\partial^{\alpha}\theta_{Q}\|_{L^{\infty}}\lesssim\delta_{Q}^{-|\alpha|}.$

  3. (POU3)

$0\leq\theta_{Q}\leq 1$.

For any $x\in Q^{0}$, we have

  1. (POU4)

$\sum_{Q\in\text{CZ}}\theta_{Q}(x)=1.$

Our interpolant $F$ will then be of the form

$F=\sum_{Q\in\text{CZ}}P_{Q}\theta_{Q},$ (11)

where each $P_{Q}$ is an affine polynomial on $\mathbb{R}^{2}$ of the form

$P_{Q}(x)=L_{Q}(x)+\eta_{Q}\cdot
x^{(2)}\;\text{for}\;x=(x^{(1)},x^{(2)})\in\mathbb{R}^{2}.$

Here, $L_{Q}$ is an affine polynomial satisfying $\partial_{2}L_{Q}=0$ and
$\eta_{Q}$ is a real number.

In the previous section we have associated to each square $Q\in\text{CZ}$ the
points $z_{Q},w_{Q}\in E_{1}$. We now define $L_{Q}$ to be the unique affine
polynomial satisfying:

$L_{Q}|_{\\{z_{Q},w_{Q}\\}}=f|_{\\{z_{Q},w_{Q}\\}}\mbox{ and
}\partial_{2}L_{Q}=0.$ (12)

Thanks to Property 4 of Lemma 4 there exists an affine polynomial $L_{0}$ for
which

$L_{Q}=L_{0}\;\text{for all}\;Q\in\partial\text{CZ}.$

We will choose the $\eta_{Q}$ later in Sections 6 and 7.

We now compute a simple upper bound for the $L^{2,p}$-seminorm of $F$.

######  Lemma 5 (The Patching Lemma).

The function $F$ satisfies

$\|F\|^{p}_{L^{2,p}(Q^{0})}\lesssim\sum_{\begin{subarray}{c}Q,Q^{\prime}\in\text{CZ}:\\\
Q\leftrightarrow
Q^{\prime}\end{subarray}}\Big{\\{}\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}^{p}\delta_{Q}^{2-2p}+|\eta_{Q}-\eta_{Q^{\prime}}|^{p}\delta_{Q}^{2-p}\Big{\\}}.$

###### Proof.

Fix a square $Q^{\prime}\in\text{CZ}$. Observe that

$F(x)=\sum_{Q\in\text{CZ}}\theta_{Q}(x)[P_{Q}(x)-P_{Q^{\prime}}(x)]+P_{Q^{\prime}}(x).$

By Property 4 of Lemma 3, there are a bounded number of squares
$Q\in\text{CZ}$ for which $x\in(1.1Q)\cap Q^{\prime}$. Therefore, by (POU1),
there are a bounded number of $Q\in\text{CZ}$ with
$\text{supp}(\theta_{Q})\cap Q^{\prime}\neq\emptyset$. Taking $2^{\text{nd}}$
derivatives, using (POU2), and integrating $p^{\text{th}}$ powers then gives

$\|F\|_{L^{2,p}(Q^{\prime})}^{p}\lesssim\sum_{\begin{subarray}{c}Q\in\text{CZ}:\\\
Q\leftrightarrow
Q^{\prime}\end{subarray}}\big{\\{}\delta_{Q}^{2-2p}\|P_{Q}-P_{Q^{\prime}}\|^{p}_{L^{\infty}(Q)}+\delta_{Q}^{2-p}|\nabla(P_{Q}-P_{Q^{\prime}})|\big{\\}}.$

For any affine polynomial $P$ we have $|\nabla
P|\leq\delta_{Q}^{-1}||P||_{L^{\infty}(Q)}$, and thus

$\|F\|_{L^{2,p}(Q^{\prime})}^{p}\lesssim\sum_{\begin{subarray}{c}Q\in\text{CZ}:\\\
Q\leftrightarrow
Q^{\prime}\end{subarray}}\delta_{Q}^{2-2p}\|P_{Q}-P_{Q^{\prime}}\|^{p}_{L^{\infty}(Q)}.$

By the triangle inequality, and the fact that $|z^{(2)}|\leq C\delta_{Q}$
whenever $z\in 1.1Q$,

$\displaystyle\|P_{Q}-P_{Q^{\prime}}\|_{L^{\infty}(Q)}$
$\displaystyle\leq\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}+|\eta_{Q}-\eta_{Q^{\prime}}|\|z^{(2)}\|_{L^{\infty}(Q)}$
$\displaystyle\lesssim\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}+|\eta_{Q}-\eta_{Q^{\prime}}|\delta_{Q}.$

Therefore,

$\|F\|_{L^{2,p}(Q^{\prime})}^{p}\lesssim\sum_{\begin{subarray}{c}Q\in\text{CZ}:\\\
Q\leftrightarrow
Q^{\prime}\end{subarray}}\left\\{\delta_{Q}^{2-2p}\|L_{Q}-L_{Q^{\prime}}\|^{p}_{L^{\infty}(Q)}+\delta_{Q}^{2-p}|\eta_{Q}-\eta_{Q^{\prime}}|^{p}\right\\}.$

Since CZ is partition of $Q^{0}$, summing over $Q^{\prime}\in\text{CZ}$ proves
the lemma. ∎

##  5 Establishing compatibility of the $L_{Q}$

In this section we will prove that for any function $G\in
L^{2,p}(\mathbb{R}^{2})$ with $G|_{E}=f$ we have

$\sum_{\begin{subarray}{c}Q,Q^{\prime}\in\text{CZ}:\\\ Q\leftrightarrow
Q^{\prime}\end{subarray}}\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}^{p}\delta_{Q}^{2-2p}\lesssim\|G\|_{L^{2,p}(\mathbb{R}^{2})}^{p}.$
(13)

Fix some $r$ satisfying $1<r<p$. We claim that for any
$Q,Q^{\prime}\in\text{CZ}$ with $Q\leftrightarrow Q^{\prime}$ we have

$\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}^{r}\lesssim\delta_{Q}^{2r-2}\|G\|_{L^{2,r}(250Q)}^{r}.$
(14)

Observe that for any $x\in Q$ we have

$L_{Q}(x)-L_{Q^{\prime}}(x)=f(z_{Q})+\partial_{1}L_{Q}\cdot(x-z_{Q})-f(z_{Q^{\prime}})-\partial_{1}L_{Q^{\prime}}\cdot(x-z_{Q^{\prime}}).$

Therefore, since $G(z_{Q^{\prime}})=f(z_{Q^{\prime}})$ and
$\partial_{2}L_{Q}=\partial_{2}L_{Q^{\prime}}=0$, we have

$\displaystyle\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}\leq$
$\displaystyle|f(z_{Q})-T_{z_{Q^{\prime}},250Q}(G)(z_{Q})|$
$\displaystyle+|(\partial_{1}G)_{250Q}-\partial_{1}L_{Q}|\cdot\delta_{Q}+|(\partial_{1}G)_{250Q}-\partial_{1}L_{Q^{\prime}}|\cdot\delta_{Q}.$

Recall that for any $Q,Q^{\prime}\in\text{CZ}$ with $Q\leftrightarrow
Q^{\prime}$ we have $\frac{1}{2}\delta_{Q^{\prime}}\leq\delta_{Q}\leq
2\delta_{Q^{\prime}}$ (see Lemma 3), and therefore $50Q^{\prime}\subset 250Q$.
In particular, we have

$\\{z_{Q},w_{Q},z_{Q^{\prime}},w_{Q^{\prime}}\\}\subset(250Q)\cap E_{1}.$

Since $G|_{E}=f$, Lemma 2 then implies

$\displaystyle|f(z_{Q})-T_{z_{Q^{\prime}},250Q}(G)(z_{Q})|\lesssim\delta_{Q}^{2-2/r}\|G\|_{L^{2,r}(250Q)},$
$\displaystyle|f(z_{Q})-f(w_{Q})-(\partial_{1}G)_{250Q}\cdot(z_{Q}-w_{Q})|\lesssim\delta_{Q}^{2-2/r}\|G\|_{L^{2,r}(250Q)},$
$\displaystyle|f(z_{Q^{\prime}})-f(w_{Q^{\prime}})-(\partial_{1}G)_{250Q}\cdot(z_{Q^{\prime}}-w_{Q^{\prime}})|\lesssim\delta_{Q}^{2-2/r}\|G\|_{L^{2,r}(250Q)};$

we deduce (14).

The inequality (14) implies that

$\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}^{r}\lesssim\delta_{Q}^{2r}\mathcal{M}(|\nabla^{2}G|^{r})(z)\;\text{for
any}\;z\in Q,$

where $\mathcal{M}$ is the Hardy-Littlewood maximal operator (see Section 2).
Taking $(p/r)$-th powers and integrating gives

$\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}^{p}\lesssim\delta_{Q}^{2p-2}\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(Q)}^{p/r}.$

By Properties 2 and 3 of Lemma 3, we deduce

$\sum_{\begin{subarray}{c}Q,Q^{\prime}\in\text{CZ}:\\\ Q\leftrightarrow
Q^{\prime}\end{subarray}}\|L_{Q}-L_{Q^{\prime}}\|_{L^{\infty}(Q)}^{p}\delta_{Q}^{2-2p}\lesssim\sum_{Q\in\text{CZ}}\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(Q)}^{p/r}.$

Since CZ is a pairwise disjoint collection of squares, we have

$\sum_{Q\in\text{CZ}}\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(Q)}^{p/r}\leq\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(\mathbb{R}^{2})}^{p/r}.$

We use the boundedness of the Hardy-Littlewood maximal operator from $L^{q}$
to $L^{q}$ for $1<q\leq\infty$ to deduce (13).

##  6 Step I of choosing the $\eta_{Q}$: Clustering

For each $0\leq\ell\leq L$ and fixed
$\vec{s}_{\leq\ell}=(s_{1},\cdots,s_{\ell})\in\\{-1,+1\\}^{\ell}$ we define a
set
$C(\vec{s}_{\leq\ell}):=\\{(z,\Delta):z=\sum_{k=1}^{L}s_{k}\varepsilon^{k},\;s_{\ell+1},\cdots,s_{L}\in\\{-1,+1\\}\\}\subset
E_{2}$. We refer to $C(\vec{s}_{\leq\ell})$ as a _cluster_ of $E_{2}$ at depth
$\ell$. (By convention, in the edge case $\ell=0$, $\vec{s}_{\leq 0}$ is the
empty list and $C(\vec{s}_{\leq 0})=E_{2}$.) Note that the clusters of depth
$L$ are singletons.

Accordingly, for fixed $\ell$ there are $2^{\ell}$ distinct clusters of
$E_{2}$ of depth $\ell$. The convex hulls of distinct clusters are disjoint
(assuming $\varepsilon\leq 1/2$), and thus, the clusters of depth $\ell$
inherit an order from the real number line. We shall order the clusters of
$E_{2}$ of depth $\ell$ by $C_{1}^{\ell}$, $C_{2}^{\ell}$, …,
$C_{2^{\ell}}^{\ell}$—the following properties are apparent:

  * •

$\\#(C_{i}^{\ell})=2^{L-\ell}$,

  * •

$\mathrm{diam}(C_{i}^{\ell})\approx\varepsilon^{\ell+1}$ (for
$\ell=0,\dots,L-1)$, and

  * •

$\\{C_{i}^{\ell}\\}_{i=1}^{2^{\ell}}$ is a partition of $E_{2}$.

We write $\mathcal{C}_{\ell}:=\\{C_{i}^{\ell}\\}_{i=1}^{2^{\ell}}$ to denote
the set of all clusters of $E_{2}$ of depth $\ell$. We then define the set of
all clusters

$\mathcal{C}=\bigcup_{\ell=0}^{L}\mathcal{C}_{\ell}.$

The set of all clusters forms a full, binary tree via the relation of set
inclusion, with clusters of depth $\ell$ corresponding to vertices of depth
$\ell$. Any $C\in\mathcal{C}_{\ell}$ with $\ell\geq 1$ therefore has a unique
_parent cluster_ $\pi(C)\in\mathcal{C}_{\ell-1}$.

To every cluster $C\in\mathcal{C}_{\ell}$ for $\ell=0,\dots,L-1$ we associate
a ball $B_{C}$ and to every cluster $C\in\mathcal{C}_{\ell}$ for
$\ell=1,\dots,L-1$ we associate a ball $\hat{B}_{C}$. For convenience, we’ll
assume that $B_{C}$, $\hat{B}_{C}$ are centered at the same point and that
$\text{radius}(\hat{B}_{C})=10^{M+1}\cdot\text{radius}(B_{C})$ for a positive
integer $M$ (independent of the cluster $C$). We require these balls to
satisfy the following properties:

  * •

For every $C\in\mathcal{C}_{\ell}$ ($\ell=0,\cdots,L-1$), we have

    * $\star$

$\mathrm{diam}(B_{C})\approx\mathrm{diam}(C)\approx\varepsilon^{\ell+1}$, and

    * $\star$

$C\subset B_{C}$.

  * •

For every $C\in\mathcal{C}_{\ell}$ ($\ell=1,\dots,L-1)$, we have

    * $\star$

$\mathrm{diam}(\hat{B}_{C})\approx\mathrm{diam}(\pi(C))\approx\varepsilon^{\ell}$,
and

    * $\star$

$B_{C}\subset\hat{B}_{C}\subset B_{\pi(C)}$.

  * •

For distinct clusters $C,C^{\prime}\in\mathcal{C}_{\ell}$, we have

    * $\star$

$\text{dist}(B_{C},B_{C^{\prime}})>c\varepsilon^{\ell}$ ($\ell=0,\dots,L-1$),
and

    * $\star$

$\text{dist}(\hat{B}_{C},\hat{B}_{C^{\prime}})>c\varepsilon^{\ell}$
($\ell=1,\dots,L-1)$.

We remark that (after taking $\varepsilon$ smaller than some absolute
constant) the last bullet point implies that, for fixed $\ell$, each of the
families $\\{B_{C}\\}_{C\in\mathcal{C}_{\ell}}$ and
$\\{\hat{B}_{C}\\}_{C\in\mathcal{C}_{\ell}}$ is pairwise disjoint.

Given $f:E\rightarrow\mathbb{R}$, for each $x=(x^{(1)},\Delta)\in E_{2}$ we
define

$\eta_{x}=\frac{f(x)-f(x^{(1)},0)}{\Delta}.$ (15)

For each $Q\in\text{CZ}_{II}$ there is a single point in $(1.1Q\cap E_{2})$,
denoted by $x_{Q}$. We then define

$\eta_{Q}=\eta_{x_{Q}}\;\text{for every}\;Q\in\text{CZ}_{II}.$ (16)

To any square $Q\in\text{CZ}$ we associate a cluster $C_{Q}$ as follows. If
$Q\in\text{CZ}\backslash\text{CZ}_{II}$, then we define $C_{Q}$ to be equal to
the cluster $C\in\mathcal{C}_{\ell}$ ($\ell=0,1,\cdots,L-1$) of smallest
diameter for which $Q\subset B_{C}$ if such a cluster exists and equal to
$E_{2}$ (recall that $E_{2}$ is the unique cluster of depth 0) if no such
cluster exists. If $Q\in\text{CZ}_{II}$, then we set
$C_{Q}=\\{x_{Q}\\}\in\mathcal{C}_{L}$, where $x_{Q}$ is the unique point in
$1.1Q\cap E_{2}$. Observe that for all $Q\in\partial\text{CZ}$ we have
$C_{Q}=E_{2}$.

Observe that $C_{Q}\in\mathcal{C}_{L}$ if and only if $1.1Q\cap
E_{2}\neq\emptyset$. In particular, if $1.1Q\cap E_{2}=\emptyset$ then
$C_{Q}\in\mathcal{C}_{\ell}$ ($\ell=0,\cdots,L-1$) has cardinality at least
$2$.

For each cluster $C\in\mathcal{C}$ we introduce a real number $\eta_{C}$.
Recall that every cluster $C\in\mathcal{C}_{L}$ satisfies $\\#(C)=1$; we let
$x_{C}$ denote the unique point in $C$. We then define

$\eta_{C}=\eta_{x_{C}}\;\text{for every}\;C\in\mathcal{C}_{L}.$ (17)

(Recall that $\eta_{x}$ is defined by (15).) We defer choosing
$\\{\eta_{C}\\}_{C\in\mathcal{C}_{\ell}}$ for $\ell=0,\dots,L-1$ until Section
7.

We determine the $\eta_{Q}$ in terms of the $\\{\eta_{C}\\}$ by specifying
that

$\eta_{Q}=\eta_{C_{Q}}\;\text{for all}\;Q\in\text{CZ}.$ (18)

According to the above definitions, we have

$\eta_{Q}=\eta_{C_{Q}}=\eta_{x_{Q}}\mbox{ for all }Q\in\text{CZ}_{II},$

where $C_{Q}=\\{x_{Q}\\}=1.1Q\cap E_{2}$. From this property, observe that,
independently of how we choose the remaining $\eta_{Q}$, the function $F$
satisfies

$F|_{E}=f,$

as claimed.

We now work to bound the expression

$\sum_{\begin{subarray}{c}Q,Q^{\prime}\in\text{CZ}\\\ Q\leftrightarrow
Q^{\prime}\end{subarray}}|\eta_{Q}-\eta_{Q^{\prime}}|^{p}\delta_{Q}^{2-p}$

appearing on the right-hand side of the patching lemma (Lemma 5).

Note that any distinct $Q,Q^{\prime}\in\text{CZ}$ with $Q\leftrightarrow
Q^{\prime}$ for which $\eta_{Q}\neq\eta_{Q^{\prime}}$ necessarily satisfy
either (1), $C_{Q}=\pi(C_{Q^{\prime}})$, (2) $C_{Q^{\prime}}=\pi(C_{Q})$, or
(3) $C_{Q},C_{Q^{\prime}}\in\mathcal{C}_{L}$, $C_{Q}\neq C_{Q^{\prime}}$ and
$\pi(C_{Q})=\pi(C_{Q^{\prime}})$. Therefore,

$\begin{split}\sum_{Q\leftrightarrow
Q^{\prime}}|\eta_{Q}-\eta_{Q^{\prime}}|^{p}\delta_{Q}^{2-p}\lesssim&\sum_{\ell=1}^{L}\sum_{C\in\mathcal{C}_{\ell}}|\eta_{\pi(C)}-\eta_{C}|^{p}\sum_{(Q,Q^{\prime})\in\mathcal{Q}_{C}}\delta_{Q}^{2-p}\\\
&+\sum_{\begin{subarray}{c}C,C^{\prime}\in\mathcal{C}_{L}:\\\
\pi(C)=\pi(C^{\prime})\end{subarray}}|\eta_{C}-\eta_{C^{\prime}}|^{p}\sum_{\begin{subarray}{c}Q,Q^{\prime}\in\text{CZ}\\\
C_{Q}=C,C_{Q^{\prime}}=C^{\prime}\end{subarray}}\delta_{Q}^{2-p},\end{split}$
(19)

where $\mathcal{Q}_{C}$ is defined for $C\in\mathcal{C}_{\ell}$
($\ell=1,\dots,L)$ by

$\mathcal{Q}_{C}:=\\{(Q,Q^{\prime})\in\text{CZ}\times\text{CZ}:Q\leftrightarrow
Q^{\prime},C_{Q}=C,C_{Q^{\prime}}=\pi(C)\\}.$

We first bound the second sum on the right-hand side of (19). Note that for
$C\in\mathcal{C}_{L}$ there are a bounded number of $Q\in\text{CZ}$ with
$C_{Q}=C$ (any such $Q$ satisfies that $1.1Q\cap E_{2}=\\{x_{Q}\\}=C$). For
any such $Q$, it holds that $\delta_{Q}\approx\Delta=\epsilon^{L}$. Similarly,
for $C^{\prime}\in\mathcal{C}_{L}$ there are a bounded number of
$Q^{\prime}\in\text{CZ}$ with $C_{Q^{\prime}}=C^{\prime}$. If
$\pi(C)=\pi(C^{\prime})$ then we can use the triangle inequality to estimate
$|\eta_{C}-\eta_{C^{\prime}}|\leq|\eta_{C}-\eta_{\pi(C)}|+|\eta_{C^{\prime}}-\eta_{\pi(C^{\prime})}|$.
Thus,

$\sum_{\begin{subarray}{c}C,C^{\prime}\in\mathcal{C}_{L}:\\\
\pi(C)=\pi(C^{\prime})\end{subarray}}|\eta_{C}-\eta_{C^{\prime}}|^{p}\sum_{\begin{subarray}{c}Q,Q^{\prime}\in\text{CZ}\\\
C_{Q}=C,C_{Q^{\prime}}=C^{\prime}\end{subarray}}\delta_{Q}^{2-p}\lesssim\epsilon^{L(2-p)}\sum_{C\in\mathcal{C}_{L}}|\eta_{C}-\eta_{\pi(C)}|^{p}.$
(20)

Note that for any cluster $C\in\mathcal{C}_{\ell}$, $\ell=1,\dots,L-1$, we
have

$\Delta/9\leq\delta_{Q}\leq c\varepsilon^{\ell+1}\;\text{for
any}\;Q\in\text{CZ}\;\text{for which}\;C_{Q}=C.$ (21)

Indeed, see (7), and note that if $Q$ and $C$ are as above then $Q\subset
B_{C}$ and so $\delta_{Q}\leq\mathrm{diam}(B_{C})\approx\epsilon^{\ell+1}$.

Observe that $\\#\mathcal{Q}_{C}\lesssim 1$ for any $C\in\mathcal{C}_{L}$,
simply because there are at most a bounded number of squares $Q$ with
$C_{Q}=C$ (any such square satisfies $1.1Q\cap E=C_{Q}$), and each of these
squares $Q$ touches a bounded number of squares $Q^{\prime}$. Since any $Q$
with $C_{Q}=C$ for $C\in\mathcal{C}_{L}$ satisfies
$\delta_{Q}\approx\Delta=\varepsilon^{L}$, we get

$\sum_{(Q,Q^{\prime})\in\mathcal{Q}_{C}}\delta_{Q}^{2-p}\lesssim\varepsilon^{L(2-p)}\;\text{for
any}\;C\in\mathcal{C}_{L}.$ (22)

Now fix $C\in\mathcal{C}_{\ell}$ for $\ell=1,\dots,L-1$. We claim that

$\\#\\{(Q,Q^{\prime})\in\mathcal{Q}_{C}:\delta_{Q}=\delta\\}\lesssim
1\;\text{for every}\;\delta>0.$ (23)

Suppose $(Q,Q^{\prime})\in\mathcal{Q}_{C}$ with $\delta_{Q}=\delta$. Then,
since $Q\subset B_{C}$, $Q^{\prime}\not\subset B_{C}$, and $Q\leftrightarrow
Q^{\prime}$, it must be the case that $Q,Q^{\prime}$ are contained in a
$c\delta_{Q}$-neighborhood of the boundary of $B_{C}$ for some absolute
constant $c$. By (10), it is also the case that $Q,Q^{\prime}$ are at most
distance $c^{\prime}\delta_{Q}$ from the $x^{(1)}$-axis for another absolute
constant $c^{\prime}$. Here, $\delta_{Q}=\delta$ is fixed. A simple packing
argument then yields (23). Combining (21) and (23), we show that

$\displaystyle\sum_{(Q,Q^{\prime})\in\mathcal{Q}_{C}}\delta_{Q}^{2-p}\leq\sum_{k\leq\log_{2}(c\epsilon^{\ell+1})}\sum_{(Q,Q^{\prime})\in\mathcal{Q}_{C},\delta_{Q}=2^{k}}(2^{k})^{2-p}$
(24)
$\displaystyle\lesssim\sum_{k\leq\log_{2}(c\epsilon^{\ell+1})}2^{k(2-p)}\lesssim\varepsilon^{(\ell+1)(2-p)}\quad(C\in\mathcal{C}_{\ell},\ell=1,\cdots,L-1).$

(Note that we’ve used the assumption $(2-p)>0$.)

Combining (20) with (22), (24), allows us to continue the bound in (19),

$\begin{split}\sum_{Q\leftrightarrow
Q^{\prime}}|\eta_{Q}-\eta_{Q^{\prime}}|^{p}\delta_{Q}^{2-p}\lesssim&\sum_{\ell=1}^{L-1}\varepsilon^{(\ell+1)(2-p)}\sum_{C\in\mathcal{C}_{\ell}}|\eta_{\pi(C)}-\eta_{C}|^{p}\\\
&+\varepsilon^{L(2-p)}\sum_{C\in\mathcal{C}_{L}}|\eta_{\pi(C)}-\eta_{C}|^{p}.\end{split}$
(25)

For $\ell=1,\dots,L$ we define

$\nu_{\ell}=\begin{cases}\varepsilon^{(\ell+1)(2-p)}&\text{for}\;\ell=1,\dots,L-1,\\\
\varepsilon^{L(2-p)}&\text{for}\;\ell=L.\end{cases}$ (26)

We then rewrite inequality (25) as

$\sum_{Q\leftrightarrow
Q^{\prime}}|\eta_{Q}-\eta_{Q^{\prime}}|^{p}\delta_{Q}^{2-p}\lesssim\sum_{\ell=1}^{L}\nu_{\ell}\sum_{C\in\mathcal{C}_{\ell}}|\eta_{\pi(C)}-\eta_{C}|^{p}.$
(27)

In the next section we will choose the remaining $\eta_{C}$ (for
$C\in\mathcal{C}_{\ell}$ with $\ell=0,1,\dots,L-1$) and prove that our choices
satisfy suitable estimates. Finally, in the last section we will explain how
to use those estimates to complete the proof of Theorem 1.

##  7 Step II of choosing the $\eta_{Q}$: Minimizing $\|F\|_{L^{2,p}}$

Recall that we have already defined $\eta_{C}$ for $C\in\mathcal{C}_{L}$ in
(17).

The goal of this section is to choose $\eta_{C}$ for each
$C\in\mathcal{C}_{\ell}$ ($\ell=0,1,\dots,L-1)$ so that for any $G\in
L^{2,p}(\mathbb{R}^{2})$ with $G|_{E}=f$ we have

$\sum_{\ell=1}^{L}\nu_{\ell}\sum_{C\in\mathcal{C}_{\ell}}|\eta_{\pi(C)}-\eta_{C}|^{p}\lesssim\|G\|_{L^{2,p}(\mathbb{R}^{2})}^{p}.$
(28)

This is easy to do, thanks to Theorem 2. Recall $\nu_{\ell}$ are defined in
(26).

The following is an immediate corollary of Theorem 2.

######  Corollary 1.

There exist $\eta_{C}$ for each $C\in\mathcal{C}_{\ell}$ ($\ell=1,\dots,L-1)$,
depending linearly on $\\{\eta_{C}\\}_{C\in\mathcal{C}_{L}},$ so that the
following holds. Let $\\{\gamma_{C}\\}_{C\in\mathcal{C}}$ be a collection of
real numbers with $\gamma_{C}=\eta_{C}$ for each $C\in\mathcal{C}_{L}$. Then

$\sum_{\ell=1}^{L}\nu_{\ell}\sum_{C\in\mathcal{C}_{\ell}}|\eta_{\pi(C)}-\eta_{C}|^{p}\lesssim\sum_{\ell=1}^{L}\nu_{\ell}\sum_{C\in\mathcal{C}_{\ell}}|\gamma_{\pi(C)}-\gamma_{C}|^{p}.$

We fix the definition of $\\{\eta_{C}\\}_{C\in\mathcal{C}}$ as in Corollary 1.
Recall that $\\{\eta_{C}\\}_{C\in\mathcal{C}_{L}}$ depend linearly on the data
$f$ – see (17) and (15). Thus, $\eta_{C}$ depends linearly on $f$ for each
$C\in\mathcal{C}$.

We claim that for any $G\in L^{2,p}(\mathbb{R}^{2})$ with $G|_{E}=f$ we have

$\sum_{\ell=1}^{L-1}\varepsilon^{(\ell+1)(2-p)}\sum_{C\in\mathcal{C}_{\ell}}|(\partial_{2}G)_{B_{\pi(C)}}-(\partial_{2}G)_{B_{C}}|^{p}\lesssim\|G\|_{L^{2,p}(\mathbb{R}^{2})}^{p}.$
(29)

We will later show that (29) and Corollary 1 allow us to deduce estimate (28)
for the $\\{\eta_{C}\\}_{C\in\mathcal{C}}$, completing the task of this
section.

For every $C\in\mathcal{C}_{\ell}$, $\ell=1,\dots,L-1$, let $r_{C},x_{C}$
denote the radius and center, respectively, of the ball $B_{C}$. For $k\geq 0$
define the annulus

$A_{C,k}=\\{x\in\mathbb{R}^{2}:10^{k}r_{C}\leq|x-x_{C}|<10^{k+1}r_{C}\\}.$

Recall (see Section 6) that $\hat{B}_{C}$ is also centered at $x_{C}$ and that

$\text{radius}(\hat{B}_{C})=10^{M+1}r_{C}.$

for some positive integer $M$. Define another annulus

$A_{C}=\bigcup_{k=0}^{M}A_{C,k}.$

Note that the collection of annuli
$\\{A_{C}\\}_{C\in\mathcal{C}_{\ell},\ell=1,\dots L-1}$ is pairwise disjoint.

We claim that for any $1<r<p$ and for every $C\in\mathcal{C}_{\ell}$
($\ell=1,\dots,L-1$) we have

$|(\partial_{2}G)_{B_{\pi(C)}}-(\partial_{2}G)_{B_{C}}|^{p}\varepsilon^{(\ell+1)(2-p)}\lesssim\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(A_{C})}^{p/r}.$
(30)

Since the $A_{C}$ are pairwise disjoint, (30) implies

$\sum_{\ell=1}^{L-1}\varepsilon^{(\ell+1)(2-p)}\sum_{C\in\mathcal{C}_{\ell}}|(\partial_{2}G)_{B_{\pi(C)}}-(\partial_{2}G)_{B_{C}}|^{p}\lesssim\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(\mathbb{R}^{2})}^{p/r};$

we use the boundedness of the Hardy-Littlewood maximal operator from $L^{p/r}$
to $L^{p/r}$ to deduce (29).

To prove (30), use Lemma 2 to get

$\begin{split}|(\partial_{2}G)_{B_{C}}-(\partial_{2}G)_{A_{C,0}}|&\lesssim\varepsilon^{(\ell+1)(1-2/r)}\|G\|_{L^{2,r}(B_{C}\cup
A_{C,0})}\\\
&\lesssim\varepsilon^{\ell+1}(\mathcal{M}(|\nabla^{2}G|^{r}(z))^{1/r}\end{split}$

for any $z\in A_{C,0}$. (Recall that $r_{C}\approx\varepsilon^{\ell+1}$.)
Taking $p$-th powers and integrating over $A_{C,0}$, we get

$|(\partial_{2}G)_{B_{C}}-(\partial_{2}G)_{A_{C,0}}|^{p}\varepsilon^{(\ell+1)(2-p)}\lesssim\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(A_{C,0})}^{p/r}.$

Similarly, we can show

$\displaystyle|(\partial_{2}G)_{A_{C,k}}-(\partial_{2}G)_{A_{C,k+1}}|^{p}\varepsilon^{(\ell+1)(2-p)}\lesssim
10^{k(p-2)}\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(A_{C,k})}^{p/r},$
$\displaystyle|(\partial_{2}G)_{B_{\pi(C)}}-(\partial_{2}G)_{A_{C,M}}|^{p}\varepsilon^{(\ell+1)(2-p)}\lesssim
10^{M(p-2)}\|\mathcal{M}(|\nabla^{2}G|^{r})\|_{L^{p/r}(A_{C,M})}^{p/r}.$

We apply the triangle inequality and use that $p<2$ to get

$\begin{split}|(\partial_{2}G)_{B_{C}}-(\partial_{2}G)_{B_{\pi(C)}}|\varepsilon^{(\ell+1)(2/p-1)}&\lesssim\|\mathcal{M}(|\nabla^{2}G|^{r})\|^{1/r}_{L^{p/r}(A_{C})}\sum_{k=0}^{M}10^{k(1-2/p)}\\\
&\lesssim\|\mathcal{M}(|\nabla^{2}G|^{r})\|^{1/r}_{L^{p/r}(A_{C})},\end{split}$

proving (30), and thus, proving (29).

We now explain how to prove (28). We fix $G\in L^{2,p}(\mathbb{R}^{2})$ with
$G|_{E}=f$ and define $(\gamma_{C})_{C\in\mathcal{C}}$ in terms of $G$ and
$(\eta_{C})_{C\in\mathcal{C}}$. We take $\gamma_{C}=(\partial_{2}G)_{B_{C}}$
if $C\in\mathcal{C}_{\ell}$ for $\ell=0,\dots,L-1$ and $\gamma_{C}=\eta_{C}$
if $C\in\mathcal{C}_{L}$. Now, we apply Corollary 1 to deduce that

$\begin{split}\sum_{\ell=1}^{L}\nu_{\ell}\sum_{C\in\mathcal{C}_{\ell}}|\eta_{\pi(C)}-\eta_{C}|^{p}&\lesssim\sum_{\ell=1}^{L-1}\varepsilon^{(\ell+1)(2-p)}\sum_{C\in\mathcal{C}_{\ell}}|(\partial_{2}G)_{B_{\pi(C)}}-(\partial_{2}G)_{B_{C}}|^{p}\\\
&\qquad+\varepsilon^{L(2-p)}\sum_{C\in\mathcal{C}_{L}}|(\partial_{2}G)_{B_{\pi(C)}}-\eta_{C}|^{p}.\end{split}$
(31)

Let $C\in\mathcal{C}_{L}$. Observe that
$\eta_{C}=\eta_{x_{C}}=\frac{f(x_{C})-f(x_{C}^{(1)},0)}{\Delta}=\frac{G(x_{C})-G(x_{C}^{(1)},0)}{\Delta}$.
By Lemma 2, we easily get that

$|(\partial_{2}G)_{B_{\pi(C)}}-\eta_{C}|^{p}\varepsilon^{L(2-p)}\lesssim||G||_{L^{2,p}(B_{\pi(C)})}^{p}\;\text{for
any}\;C\in\mathcal{C}_{L}.$

The collection of balls $\\{B_{\pi(C)}\\}_{C\in\mathcal{C}_{L}}$ has bounded
overlap, so

$\varepsilon^{L(2-p)}\sum_{C\in\mathcal{C}_{L}}|(\partial_{2}G)_{B_{\pi(C)}}-\eta_{C}|^{p}\lesssim||G||_{L^{2,p}(\mathbb{R}^{2})}^{p}.$

Combining this estimate with (31) and (29), we complete the proof of (28).

##  8 Proof of Main Theorem

Combining Lemma 5 and the inequalities (13), (27), and (28) proves the
following lemma.

######  Lemma 6.

Let $\\{\eta_{C}\\}_{C\in\mathcal{C}}$ be defined via (17) and Corollary 1,
and let $\\{\eta_{Q}\\}_{Q\in\text{CZ}}$ be defined in terms of
$\\{\eta_{C}\\}_{C\in\mathcal{C}}$ in (18). Then the function $F\in
L^{2,p}(Q^{0})$ defined by (11) satisfies:

  * •

$F|_{E}=f$

  * •

For any $G\in L^{2,p}(\mathbb{R}^{2})$ with $G|_{E}=f$, we have

$\|F\|_{L^{2,p}(Q^{0})}\lesssim\|G\|_{L^{2,p}(\mathbb{R}^{2})}.$

It is easy to deduce Theorem 1 from Lemma 6. Recall that there is some affine
polynomial $L_{0}$ such that

$L_{Q}=L_{0}\;\text{for every}\;Q\in\partial\text{CZ}.$

Similarly, recall that for every $Q\in\partial\text{CZ}$ we have
$C_{Q}=E_{2}$. Writing $\eta_{0}=\eta_{E_{2}}$, we thus have

$\eta_{Q}=\eta_{0}\;\text{for every}\;Q\in\partial\text{CZ}.$

We define a function $\tilde{F}:\mathbb{R}^{2}\rightarrow\mathbb{R}$ by
setting

$\tilde{F}(x)=\begin{cases}F(x)&\text{if }x\in Q^{0},\\\
L_{0}(x)+\eta_{0}\cdot x^{(2)}&\text{if }x\notin Q^{0}.\end{cases}$

Clearly, $\tilde{F}|_{E}=f$ and
$\|\tilde{F}\|_{L^{2,p}(\mathbb{R}^{2})}=\|F\|_{L^{2,p}(Q^{0})}$. This proves
Theorem 1.

## References

  * [1] Charles Fefferman and Arie Israel.  Fitting Smooth Functions to Data, volume 135 of CBMS Regional Conference Series in Mathematics.  AMS, 2020.
  * [2] Charles Fefferman, Arie Israel, and Garving Luli.  Sobolev extension by linear operators.  J. Am. Math. Soc., 27(1):69–145, 2014.
  * [3] Charles Fefferman and Bo’az Klartag.  Linear extension operators for sobolev spaces on radially symmetric binary trees.  Adv. Nonlinear Stud., 23(1):20220075, 2023.
  * [4] David Gilbarg and Neil S Trudinger.  Elliptic Partial Differential Equations of Second Order.  Springer-Verlag Berlin, 1 edition, 1977.
  * [5] Elias M Stein.  Harmonic Analysis: Real-Variable Methods, Orthogonality, and Oscillatory Integrals, volume 43 of Princeton Mathematical Series.  Princeton University Press, 1993.


# Twins in ordered hyper-matchings

Andrzej Dudek  Department of Mathematics, Western Michigan University,
Kalamazoo, MI, USA<EMAIL_ADDRESS>,  Jarosław Grytczuk  Faculty of
Mathematics and Information Science, Warsaw University of Technology, Warsaw,
Poland<EMAIL_ADDRESS>and  Andrzej Ruciński  Department of
Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland
<EMAIL_ADDRESS>
###### Abstract.

An _ordered $r$-matching_ of _size_ $n$ is an $r$-uniform hypergraph on a
linearly ordered set of vertices, consisting of $n$ pairwise disjoint edges.
Two ordered $r$-matchings are _isomorphic_ if there is an order-preserving
isomorphism between them. A pair of _twins_ in an ordered $r$-matching is
formed by two vertex disjoint isomorphic sub-matchings. Let $t^{(r)}(n)$
denote the maximum size of twins one may find in _every_ ordered $r$-matching
of size $n$.

By relating the problem to that of largest twins in permutations and applying
some recent Erdős-Szekeres-type results for ordered matchings, we show that
$t^{(r)}(n)=\Omega\left(n^{\frac{3}{5\cdot(2^{r-1}-1)}}\right)$ for every
fixed $r\geqslant 2$. On the other hand,
$t^{(r)}(n)=O\left(n^{\frac{2}{r+1}}\right)$, by a simple probabilistic
argument. As our main result, we prove that, for _almost all_ ordered
$r$-matchings of size $n$, the size of the largest twins achieves this bound.

The first author was supported in part by Simons Foundation Grant #522400.

The second author was supported in part by Narodowe Centrum Nauki, grant
2020/37/B/ST1/03298.

The third author was supported in part by Narodowe Centrum Nauki, grant
2018/29/B/ST1/00426

##  1\. Introduction

Let $r\geq 2$ be a fixed integer. An _ordered $r$-matching_ of _size_ $n$ is
an $r$-uniform hypergraph $M$ on a linearly ordered vertex set $V$, with
$|V|=rn$, consisting of $n$ pairwise disjoint edges. One may represent such a
matching as a _word_ with $n$ distinct letters in which every letter occurs
exactly $r$ times. For instance, the word $AABCBDBDACCD$ represents an ordered
$3$-matching of size $4$ whose edges correspond to sets of positions occupied
by a given letter, i.e., $A=\\{1,2,9\\}$, $B=\\{3,5,7\\}$, $C=\\{4,10,11\\}$,
and $D=\\{6,8,12\\}$. We will frequently identify an ordered matching with its
representing word.

Two ordered matchings are _isomorphic_ if there is an order-preserving
bijection between their vertex sets inducing a one-to-one correspondence
between their edge sets. In particular, the words representing isomorphic
ordered matchings are identical up to renaming the letters. A pair of two
vertex disjoint isomorphic sub-matchings of an ordered matching $M$ is called
_twins_. By the _size_ of twins we mean the size of just one of the two in the
pair. The maximum size of twins in a matching $M$ will be denoted by $t(M)$.
The corresponding extremal function is defined by

$t^{(r)}(n)=\min\\{t(M):M\text{ is an ordered $r$-matching of size $n$}\\}.$

For instance, in the matching $M$ represented by the word

$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}AA\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}B\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}C\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}BD\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}EE\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}BD\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}ACC\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}D$

one can find a pair of twins of size two formed by the sub-matchings
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}AACACC$ and
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}BBDBDD$. So,
$t(M)=2$ as, trivially, we always have $t(M)\leq n/2$ for a matching of size
$n$.

In a recent paper [5] (see also [6]) we demonstrated that the following
inequalities hold for all $n\geq 2$ (note that $t^{(2)}(1)=0$):

$\frac{1}{16\sqrt[5]{2}}\cdot n^{\frac{3}{5}}\leqslant
t^{(2)}(n)\leqslant\frac{e}{\sqrt[3]{2}}\cdot n^{\frac{2}{3}}.$

The upper bound is obtained by a standard probabilistic argument based on the
expectation. In fact, we proved in [5] that this upper bound is a.a.s.
(asymptotically almost surely) attained by almost all ordered matching of size
$n$. The lower bound is a consequence of a result by Bukh and Rudenko [3],
concerning the related problem for permutations.

By _twins_ in a permutation $\pi$ we mean a pair of disjoint order-isomorphic
subsequences of $\pi$. Let $\tau(n)$ be the maximum length of twins contained
in every permutation of length $n$. The result in [3] states that
$\tau(n)\geq\tfrac{1}{8}\cdot n^{\frac{3}{5}}$, which is so far the best lower
bound, while $\tau(n)=O\left(n^{\frac{2}{3}}\right)$ follows by an elementary
probabilistic argument. It is conjectured by Gawron [9] that this upper bound
yields the correct order of magnitude for $\tau(n)$. If true, this would imply
the same for the function $t^{(2)}(n)$, since we proved in [5, 6] that
$t^{(2)}(n)=\Theta(\tau(n))$. For other related results on twins in
permutations, as well as for the rich background of the problem, we encourage
the reader to look at our paper [4].

In the present paper we extend the above results to ordered $r$-matchings,
$r\geqslant 3$, in both, the deterministic and the random setting. Let
$\mathbb{RM}_{n}:=\mathbb{RM}^{(r)}_{n}$ denote a _random_ ordered
$r$-matching of size $n$ (for precise definition, see the next section).

######  Theorem 1.1.

For every $r\geq 2$, a.a.s.,

$t(\mathbb{RM}_{n})=\Theta\left(n^{\frac{2}{r+1}}\right).$ (1.1)

The proof of the upper bound follows, once again, by a standard application of
the first moment method. To get the lower bound we apply a more sophisticated
argument, similar to that in [4] and [5, 6], which is based on a concentration
inequality of Talagrand for permutations [11] (see Section 2).

Of course, the upper bound in (1.1) is also true in the deterministic case,
so, we have $t^{(r)}(n)=O\left(n^{\frac{2}{r+1}}\right)$, for every
$r\geqslant 2$. Our second result gives a lower bound for $t^{(r)}(n)$.

######  Theorem 1.2.

For every $r\geqslant 2$, we have

$t^{(r)}(n)=\Omega\left(n^{\frac{3}{5}\cdot\frac{1}{2^{r-1}-1}}\right).$ (1.2)

The proof of Theorem 1.2 in Section 3, is based on a key lemma (Lemma 3.2),
establishing a double recurrence for $t^{(r)}$, and a recent Erdős-Szekeres
type result [8] for ordered matchings obtained by Sauerman and Zakharov [13].
This latter result states that every sufficiently large ordered $r$-matching
$M$ contains a large homogenous “clique”, i.e., a sub-matching $M^{\prime}$
whose all pairs of edges form pairwise isomorphic $r$-matchings (of size two).
More specifically, the size of such a “clique” $M^{\prime}$ in any ordered
$r$-matching with $n$ edges is at least $\frac{1}{2}\cdot
n^{\frac{1}{2^{r}-1}}$, as proved in [13].

Observe that if $M^{\prime}=\\{e_{1},\dots,e_{m}\\}$, then by arbitrarily
splitting $M^{\prime}$ in half, e.g., $\\{e_{1},\dots,e_{\lfloor
m/2\rfloor}\\}$ and $\\{e_{\lceil m/2\rceil+1},\dots,e_{m}\\}$, we obtain
twins. Thus, we immediately get the lower bound
$t^{(r)}(n)=\Omega\left(n^{\frac{1}{2^{r}-1}}\right)$, which is, however, much
worse than the bound in (1.2). For instance, the exponents of $n$ in these two
bounds are equal, respectively, to $\frac{1}{5}$ and $\frac{1}{7}$ ($r=3$), to
$\frac{3}{35}$ and $\frac{1}{15}$ ($r=4$), and to $\frac{1}{25}$ and
$\frac{1}{31}$ ($r=5$). In fact, their ratio converges to $\frac{6}{5}$ as $r$
is growing. Nonetheless, the ratio of the logarithms of the current upper and
lower bounds for $t^{(r)}(n)$ grows rather rapidly with $r$.

We will use the standard notation $[n]:=\\{1,2,\ldots,n\\}$.

##  2\. Random matchings

In this section we prove Theorem 1.1. Recall that
$\mathbb{RM}_{n}:=\mathbb{RM}^{(r)}_{n}$ denotes a random ordered $r$-matching
of size $n$, that is, an ordered $r$-matching picked uniformly at random out
of all

$\alpha^{(r)}_{n}:=\frac{(rn)!}{(r!)^{n}\,n!}$

such $r$-matchings on the set $[rn]$.

The formula for $\alpha^{(r)}_{n}$ indicates that each ordered matching can be
coupled with exactly $(r!)^{n}n!$ permutations. Indeed, one can generate an
ordered matching by the following permutational scheme. Let $\pi$ be a
permutation of $[rn]$. Now $\pi$ can be chopped off into an $r$-matching
consisting of the following collection of edges

$\\{\pi(1),\dots,\pi(r)\\},\\{\pi(r+1),\dots,\pi(2r)\\},\dots,\\{\pi(rn-r+1),\dots,\pi(rn)\\}.$

Clearly, there are exactly $(r!)^{n}n!$ permutations $\pi$ yielding the same
matching. Thus, a (uniformly) random permutation $\Pi_{rn}$ of $[rn]$
generates a (uniformly) random $r$-matching $\mathbb{RM}_{n}$. This scheme
allows one to use concentration inequalities (such as the Talagrand inequality
[14]) for random permutations in the context of random matchings.

###### Proof of Theorem 1.1: upper bound.

The upper bound in formula (1.1) was already mentioned without proof in [7,
Section 2]. The proof is based on the standard first moment method. For each
$k$, let $X_{k}$ be the number of twins of size $k$ in $\mathbb{RM}_{n}$. Then

${\mathds{E}}X_{k}=\frac{1}{2!}\cdot\binom{rn}{rk,rk,rn-2rk}\cdot\frac{\alpha^{(r)}_{k}\cdot
1\cdot\alpha^{(r)}_{n-2k}}{\alpha^{(r)}_{n}}=\frac{1}{2}\cdot\frac{n!}{(n-2k)!}\cdot\frac{1}{k!}\cdot(r!)^{k}\cdot\frac{1}{(rk)!},$

where the factor of 1 represents the second twin which is fully determined by
the first one.

Ignoring $\tfrac{1}{2}$ and using inequalities $n!/(n-2k)!\leq n^{2k}$,
$k!\geq(k/e)^{k}$, $r!\leq r^{r}$, and $(rk)!\geq(rk/e)^{rk}$, we thus get

${\mathds{E}}X_{k}\leq n^{2k}\cdot\left(\frac{e}{k}\right)^{k}\cdot
r^{rk}\cdot\left(\frac{e}{rk}\right)^{rk}=\left(n^{2}\cdot\frac{e}{k}\cdot
r^{r}\cdot\left(\frac{e}{rk}\right)^{r}\right)^{k}=\left(\frac{n^{2}}{\left(k/e\right)^{r+1}}\right)^{k},$

which converges to 0 as $n\to\infty$ for $k\geq cn^{2/(r+1)}$, with any
constant $c>e$. Hence, for such $k$,
${\mathds{P}}(X_{k}>0)\leq{\mathds{E}}X_{k}=o(1)$ and so, a.a.s.
$t^{(r)}(\mathbb{RM}_{n})\leq cn^{2/(r+1)}$. ∎

An important ingredient of the proof of the lower bound in Theorem 1.1 is a
Talagrand’s concentration inequality for random permutations from [14]. We
quote here a slightly simplified version from [11, Inequality (2) with $l=2$]
(see also [12, Inequlity (1.3)]). Let ${\Pi}_{n^{\prime}}$ be a random
permutation of order $n^{\prime}$ (we will be applying this theorem with
$n^{\prime}=rn$).

######  Theorem 2.1 (Luczak and McDiarmid [11]).

Let $h(\pi)$ be a function defined on the set of all permutations of order
$n^{\prime}$ which, for some positive constants $c$ and $d$, satisfies

  1. ( )

if $\pi_{2}$ is obtained from $\pi_{1}$ by swapping two elements, then
$|h(\pi_{1})-h(\pi_{2})|\leq c$;

  2. ( )

for each $\pi$ and $s>0$, if $h(\pi)=s$, then in order to show that
$h(\pi)\geq s$, one needs to specify only at most $ds$ values $\pi(i)$.

Then, for every $\varepsilon>0$,

${\mathds{P}}(|h({\Pi}_{n^{\prime}})-m|\geq\varepsilon m)\leq
4\exp(-\varepsilon^{2}m/(32dc^{2})),$

where $m$ is the median of the random variable $h({\Pi}_{n^{\prime}})$.

As mentioned above, one can use this lemma for random $r$-matchings, as they
can be generated by random permutations.

###### Proof of Theorem 1.1: lower bound.

Set

$a:=\beta n^{(r-1)/(r+1)}\quad\text{ with
}\quad\beta:=\frac{1}{(20er!)^{1/(r+1)}}$

and

$N:=\frac{rn}{a}=\frac{r}{\beta}n^{2/(r+1)}.$

For simplicity we assume that both $a$ and $N$ are integers. Partition
$[rn]=A_{1}\cup\cdots\cup A_{N}$, where $A_{i}$’s are consecutive blocks of
$a$ integers each. For every $I=\\{i_{1},\dots,i_{r}\\}$ with $1\leq
i_{1}<\dots<i_{r}\leq N$, we call an $r$-element subset $S\subset[rn]$ an _$I$
-set_ if $|S\cap A_{i_{j}}|=1$ for each $1\leq j\leq r$. Further, define a
random variable $X_{I}$ which counts the number of edges of $\mathbb{RM}_{n}$
which are $I$-sets.

Consider an auxiliary $r$-uniform hypergraph $H:=H(\mathbb{RM}_{n})$ on vertex
set $[N]$, where $I$ is an edge in $H$ if and only if $X_{I}\geq 2$. For
better clarity the edges of $H$ will be sometimes called $H$-edges. Trivially,
the maximum degree in $H$ is at most $\binom{N-1}{r-1}$, but also, due to the
disjointness of edges in $\mathbb{RM}_{n}$, at most $a/2$.

It is easy to see that a matching of size $k$ in $H$ corresponds to twins in
$\mathbb{RM}_{n}$ of size $k$. Indeed, let $M=\\{I_{1},\dots,I_{k}\\}$ be a
matching in $H$. For every $1\leq\ell\leq k$, let
$e^{(\ell)}_{1},e^{(\ell)}_{2}\in\mathbb{RM}_{n}$ be two $I_{\ell}$-edges.
Then, the sub-matchings $M_{1}=\\{e^{(1)}_{1},\dots,e^{(k)}_{1}\\}$ and
$M_{2}=\\{e^{(1)}_{2},\dots,e^{(k)}_{2}\\}$, owing to the sequential choice of
$A_{i}$’s, form twins in $\mathbb{RM}_{n}$. Thus, our ultimate goal is to show
that a.a.s. $H$ contains a matching of size $\Omega(n^{2/(r+1)})$. Let
$\nu(H)$ be the size of the largest matching in $H$. Our ultimate goal is thus
to show that a.a.s. $\nu(H)=\Omega(N)$. Anticipating application of Theorem
2.1 to $\nu(H)$, it will be sufficient to bound ${\mathds{E}}(\nu(H))$ from
below. We will do it in a most “silly” way by looking just for isolated
$H$-edges.

Let $H_{1}$ be a subgraph of $H$ induced by the set $V_{1}$ of vertices of
degrees at most $1$ in $H$, that is, $E(H_{1})$ consists of isolated edges in
$H$ which, of course, form a matching. Set $W=|E(H)|$ and $W_{1}=|E(H_{1})|$
for the random variables counting the edges in $H$ and $H_{1}$, respectively.
Then, ${\mathds{E}}(\nu(H))\geq{\mathds{E}}(W_{1})$ and

$W_{1}=W-|\\{e\in E(H):\;e\cap(V\smallsetminus V_{1})\neq\varnothing\\}|\geq
W-\sum_{d=2}^{\lfloor a/2\rfloor}dZ_{d},$

where $Z_{d}$ counts the number of vertices of degree $d$ in $H$. Note that
${\mathds{E}}(Z_{d})=N{\mathds{P}}(D=d)$, where $D$ is the degree of a fixed
vertex, say vertex 1, in $H$. Thus, we have

${\mathds{E}}(W_{1})\geq{\mathds{E}}(W)-{\mathds{E}}\left(\sum_{d=2}^{\lfloor
a/2\rfloor}dZ_{d}\right)={\mathds{E}}(W)-N\sum_{d=2}^{\lfloor
a/2\rfloor}d{\mathds{P}}(D=d)$ (2.1)

and all we need are a lower bound on ${\mathds{E}}(W)$ and an upper bound on
${\mathds{P}}(D=d)$, so that (2.1) would yield
${\mathds{E}}(W_{1})=\Omega(N)$. We begin with the former task. From the
definition of $H$ we have

${\mathds{E}}(W)=\sum_{I\in\binom{[N]}{r}}{\mathds{P}}(X_{I}\geq 2)$ (2.2)

which, however, unlike in [6], cannot be applied directly. The reason is that
to bound ${\mathds{P}}(X_{I}\geq 2)$ from below one has to handle expressions
like $n!/(n-a)!$ which are asymptotic to $n^{a}$ as long as $a=o(\sqrt{n})$.
In [6] the case of graphs ($r=2$) was considered and we had
$a=\Theta(n^{1/3})$, however, for $r\geq 3$ we have
$a=\Theta(n^{(r-1)/(r+1)})=\Omega(\sqrt{n})$.

Hence, instead of applying (2.2) directly, we define a random variable $Y$
that counts the number of pairs of edges $\\{e_{1},e_{2}\\}$ for which there
exists a set of indices $I=\\{i_{1}<\dots<i_{r}\\}$ such that both $e_{1}$ and
$e_{2}$ are $I$-edges. By definitions, $Y$ and $X_{I}$ are related by the
identity

$Y=\sum_{I\in\binom{[N]}{r},\;X_{I}\geq 2}\binom{X_{I}}{2}.$

Observe that for any integer $t\geq 2$, using the obvious bound $X_{I}\leq a$,
we get

$Y=\sum_{I\in\binom{[N]}{r},\;2\leq X_{I}\leq
t}\binom{X_{I}}{2}+\sum_{I\in\binom{[N]}{r},\;X_{I}\geq
t+1}\binom{X_{I}}{2}\leq\binom{t}{2}\sum_{I\in\binom{[N]}{r},\;X_{I}\geq
2}1+\binom{a}{2}\sum_{I\in\binom{[N]}{r},\;X_{I}\geq t+1}1.$

Thus,

$\displaystyle{\mathds{E}}(Y)$
$\displaystyle\leq\binom{t}{2}\sum_{I\in\binom{[N]}{r}}{\mathds{P}}(X_{I}\geq
2)+\binom{a}{2}\sum_{I\in\binom{[N]}{r}}{\mathds{P}}(X_{I}\geq t+1)$
$\displaystyle=\binom{t}{2}{\mathds{E}}(W)+\binom{a}{2}\sum_{I\in\binom{[N]}{r}}{\mathds{P}}(X_{I}\geq
t+1),$ (2.3)

where we used (2.2).

From here to obtain a lower bound on ${\mathds{E}}(W)$ it suffices to bound
${\mathds{E}}(Y)$ from below and show that, for some constant $t$, the latter
summation above is $o({\mathds{E}}(Y))$. Observe that ${\mathds{E}}(Y)$ can be
calculated directly from its definition as

${\mathds{E}}(Y)=\binom{N}{r}\binom{a}{2}^{r}(2!)^{r-1}\cdot\frac{\alpha^{(r)}_{n-2}}{\alpha^{(r)}_{n}}=\binom{N}{r}\binom{a}{2}^{r}(2!)^{r-1}\cdot(r!)^{2}\frac{n!}{(n-2)!}\frac{(rn-2r)!}{(rn)!}.$

Indeed, there are $\binom{N}{r}$ choices of $I=\\{i_{1},\dots,i_{r}\\}$ and,
given that, there are $\binom{a}{2}^{r}(2!)^{r-1}$ choices of two $I$-sets
$e_{1},e_{2}$. The quotient $\tfrac{\alpha^{(r)}_{n-2}}{\alpha^{(r)}_{n}}$
equals the probability that $\mathbb{RM}_{n}$ contains $e_{1}$ and $e_{2}$ as
edges and the formula follows by the linearity of expectation.

Since $r$ is fixed (and the asymptotic is taken in $n$), each binomial
coefficient can be easily approximated and furthermore $\frac{n!}{(n-2)!}\sim
n^{2}$ and $\frac{(rn-2r)!}{(rn)!}\sim\frac{1}{(rn)^{2r}}$. This yields,

${\mathds{E}}(Y)\sim\frac{N^{r}}{r!}\left(\frac{a^{2}}{2!}\right)^{r}(2!)^{r-1}\cdot\left(\frac{r!n}{(rn)^{r}}\right)^{2}=\frac{N^{r}}{2r!}\left(\frac{(r-1)!a^{r}}{(rn)^{r-1}}\right)^{2}.$

Now expressing $N$ and $a$ as functions of $n$ (leaving just one factor of $N$
intact), we get

$\displaystyle{\mathds{E}}(Y)\sim
N\cdot\frac{\left(\frac{r}{\beta}n^{2/(r+1)}\right)^{r-1}}{2r!}\left(\frac{(r-1)!\beta^{r}n^{(r-1)r/(r+1)}}{(rn)^{r-1}}\right)^{2}=N\cdot\frac{(r-1)!\beta^{r+1}}{2r^{r}}$

and thus, for large $n$,

${\mathds{E}}(Y)\geq N\cdot\frac{(r-1)!\beta^{r+1}}{3r^{r}}.$ (2.4)

Next, we estimate the second summation in (2.3). Note that for a fixed
$I\in\binom{[N]}{r}$,

${\mathds{P}}(X_{I}\geq
t+1)\leq\binom{a}{t+1}^{r}((t+1)!)^{r-1}\frac{\alpha^{(r)}_{n-(t+1)}}{\alpha^{(r)}_{n}}\sim\frac{a^{r(t+1)}}{(t+1)!}\frac{(r!)^{t+1}n^{t+1}}{(rn)^{r(t+1)}}.$

Hence,

${\mathds{P}}(X_{I}\geq t+1)=O_{r,t}\left(n^{-\frac{(r-1)(t+1)}{r+1}}\right)$

and consequently,

$\binom{a}{2}\sum_{I\in\binom{[N]}{r}}{\mathds{P}}(X_{I}\geq
t+1)=O_{r,t}\left(a^{2}N^{r}n^{-\frac{(r-1)(t+1)}{r+1}}\right)=O_{r,t}\left(n^{\frac{2(r-1)+2r-(r-1)(t+1)}{r+1}}\right).$

Since for any $r\geq 2$ and $t\geq 4$,

$\frac{2(r-1)+2r-(r-1)(t+1)}{r+1}=\frac{(r-1)(3-t)+2}{r+1}<\frac{2}{r+1},$

we obtain, taking $t=4$,

$\binom{a}{2}\sum_{I\in\binom{[N]}{r}}{\mathds{P}}(X_{I}\geq 5)=o(N).$ (2.5)

Using (2.4) and (2.5) in (2.3), this implies the bounds

$N\cdot\frac{(r-1)!\beta^{r+1}}{3r^{r}}\leq{\mathds{E}}(Y)\leq\binom{4}{2}{\mathds{E}}(W)+o(N)$

from which it follows that

${\mathds{E}}(W)\geq N\cdot\frac{(r-1)!\beta^{r+1}}{20r^{r}}.$

After having estimated ${\mathds{E}}(W)$ we move to the second major task
which is to bound ${\mathds{P}}(D=d)$ from above where, recall, $D$ is the
degree of vertex 1 in $H$. Every edge of $H$ containing vertex 1 corresponds
to a set $I\in\binom{[N]}{r}$ with $1\in I$ and (not uniquely) to a pair of
to-be $I$-edges $e_{1},e_{2}$ in $\mathbb{RM}_{n}$. The number of choices of
the triple $(I,e_{1},e_{2})$ is $\binom{N-1}{r-1}\binom{a}{2}^{r}(2!)^{r-1}$
and the same bound applies to the $d-1$ remaining triples
$(I^{\prime},e_{1},e_{2}^{\prime})$. Of course, the edges selected to the
triples should be vertex-disjoint as otherwise they could not all appear in a
matching. As we bound from above, we may ignore this requirement. On the other
hand, as the $H$-edges containing vertex 1 are not ordered, we need to divide
by $d!$.

Consequently, very crudely,

$\displaystyle{\mathds{P}}(D=d)\leq{\mathds{P}}(D\geq d)$
$\displaystyle\leq\frac{1}{d!}\left(\binom{N}{r-1}\binom{a}{2}^{r}(2!)^{r-1}\right)^{d}\frac{\alpha^{(r)}_{n-2d}}{\alpha^{(r)}_{n}}$
$\displaystyle\sim\frac{1}{d!}\left(\frac{N^{r-1}}{(r-1)!}\frac{a^{2r}}{2}\right)^{d}\frac{(rn-2rd)!}{(rn)!}\frac{n!}{(n-2d)!}(r!)^{2d}.$

Above we turned to estimating ${\mathds{P}}(D\geq d)$ instead of
${\mathds{P}}(D=d)$ to avoid the issue of producing incidentally more than $d$
edges of $H$ containing vertex 1.

Using the inequality $1-x\geq e^{-2x}$ valid for $x\leq 1/2$, the fraction
$\frac{(rn-2rd)!}{(rn)!}$ can be estimated as

$\frac{(rn-2rd)!}{(rn)!}=\frac{1}{(rn)^{2rd}\left(1-\frac{1}{rn}\right)\cdot\ldots\cdot\left(1-\frac{2rd-1}{rn}\right)}\leq\frac{e^{4rd^{2}/n}}{(rn)^{2rd}}$

and the fraction $\frac{n!}{(n-2d)!}$ is trivially bounded by $n^{2d}$. Hence,

${\mathds{P}}(D=d)\leq\frac{1}{d!}\left(\frac{N^{r-1}}{(r-1)!}\frac{a^{2r}}{2}\right)^{d}\frac{e^{4rd^{2}/n}}{(rn)^{2rd}}\;n^{2d}(r!)^{2d}=\frac{1}{d!}\left(\frac{N^{r-1}}{(r-1)!}\frac{a^{2r}}{2}\frac{e^{4rd/n}}{(rn)^{2r}}\;n^{2}(r!)^{2}\right)d.$

Since $N^{r-1}a^{2r}\frac{n^{2}}{n^{2r}}=r^{r-1}\beta^{r+1}$ and
$e^{4rd/n}\leq 2$ as $d\leq a/2=o(n)$, we get

${\mathds{P}}(D=d)\leq\frac{1}{d!}\left(\frac{1}{(r-1)!}\cdot\frac{1}{2}\cdot\frac{2}{r^{2r}}(r!)^{2}\cdot
r^{r-1}\beta^{r+1}\right)^{d}=\frac{1}{d!}\left(\frac{\beta^{r+1}r!}{r^{r}}\right)^{d}.$

We are now ready to apply (2.1) and get

${\mathds{E}}(W_{1})={\mathds{E}}(W)-N\sum_{d\geq 2}d{\mathds{P}}(D=d)\geq
N\left(\frac{(r-1)!\beta^{r+1}}{20r^{r}}-\sum_{d\geq
2}\frac{1}{(d-1)!}\left(\frac{\beta^{r+1}r!}{r^{r}}\right)^{d}\right).$

Since $\frac{\beta^{r+1}r!}{r^{r}}=\frac{1}{20er^{r}}<1$, we can bound

$\sum_{d\geq
2}\frac{1}{(d-1)!}\left(\frac{\beta^{r+1}r!}{r^{r}}\right)^{d}\leq\left(\frac{1}{20er^{r}}\right)^{2}\sum_{d\geq
2}\frac{1}{(d-1)!}\leq\left(\frac{1}{20er^{r}}\right)^{2}e,$

and thus,

$E(\nu(H))\geq{\mathds{E}}(W_{1})\geq
N\cdot\frac{1}{20^{2}er^{r+1}}\left(1-\frac{1}{r^{r-1}}\right)=\Omega_{r}(N)=\Omega_{r}(n^{2/(r+1)}).$

Finally, owing to the permutational scheme of generating $\mathbb{RM}_{n}$, we
are in a position to apply Theorem 2.1 with $h(\pi)=\nu(H)$. Let us check the
assumptions. For a permutation $\pi$ of $[rn]$, let $M(\pi)$ be the
corresponding matching. Observe that if $\pi_{2}$ is obtained from a
permutation $\pi_{1}$ by swapping some two of its elements, then at most two
edges of $M(\pi_{1})$ can be destroyed and at most two edges of $M(\pi_{1})$
can be created, and thus the same can be said about the $H$-edges of in
$M(\pi_{1})$. This, in turn, implies that the size of the largest matching in
$H$ has been altered by at most two, that is, $|h(\pi_{1})-h(\pi_{2})|\leq 2$.
Moreover, to exhibit that $h(\pi)\geq s$, it obviously suffices to reveal $2s$
edges of $\mathbb{RM}_{n}$, that is, $2rs$ values of $\pi$.

Thus, Theorem 2.1 with $c=2$, $d=2r$, and $\varepsilon=1/2$ yields that

${\mathds{P}}(|\nu(H)-m|\geq m/2)\leq 4\exp(-m/(1024r)).$

Moreover, there is a standard passage from the median to the expectation
$\mu={\mathds{E}}(\nu(H))$. Indeed, we have (see for example [14], Lemma 4.6,
or [12], page 164) that $|m-\mu|=O(\sqrt{m})$. As demonstrated above,
$\mu\to\infty$, so it follows that $m\to\infty$ and, in particular,
$|m-\mu|\leq 0.01\mu$. This implies that ${\mathds{P}}(|\nu(H)-m|\geq
m/2)=o(1)$ and

$\displaystyle{\mathds{P}}(|\nu(H)-\mu|\geq(3/4)\mu)$
$\displaystyle={\mathds{P}}(|\nu(H)-m+m-\mu|\geq(3/4)\mu)$
$\displaystyle\leq{\mathds{P}}(|\nu(H)-m|+|m-\mu|\geq(3/4)\mu)$
$\displaystyle\leq{\mathds{P}}(|\nu(H)-m|\geq(2/3)\mu)\leq{\mathds{P}}(|\nu(H)-m|\geq
m/2)=o(1),$

which means that a.a.s. $\nu(H)=\Omega_{r}(\mu)=\Omega_{r}(n^{2/(r+1)})$, from
which the existence of twins in $\mathbb{RM}_{n}$ of size
$\Omega_{r}(n^{2/(r+1)})$ follows. ∎

Notice that we could not apply Theorem 2.1 directly to the random variable
$W_{1}$, as in order to exhibit $s$ isolated edges of $H$, one would need to
reveal an unbounded number of values of $\pi$ – to make sure that none of the
$r$-element subsets of $[N]$ intersecting the given $s$ forms an edge of $H$.
In fact, for $r=2$, one could use instead the Azuma-Hoeffding inequality (see,
e.g., [6, Theorem 3.7] or the references given there), avoiding the above
issue with the witness assumption of Talagrand’s inequality. Unfortunately,
this does not work for $r\geq 3$, as then we only have
${\mathds{E}}(W_{1})=\Omega(n^{2/(r+1)})$, so we do not know if
$\left({\mathds{E}}(W_{1})\right)^{2}/n$ tends to infinity which makes the
Azuma-Hoeffding inequality useless.

##  3\. General matchings

In this section we will give the proof of Theorem 1.2. We start with stating
the main lemma together with some explanations of how it leads to the desired
lower bound (1.2).

###  3.1. The main lemma and its consequence

In [6, Lemma 3.4, $r=2$] we showed the following lower bound on $t^{(2)}(n)$
in terms of $\tau(n)$. (Note that in [6], unlike here, $r$ meant multiplicity
of twins.)

######  Proposition 3.1.

For all $3/5\leq\alpha\leq 2/3$ and $\beta>0$, if $\tau(n)\geq\beta
n^{\alpha}$ for all $n\geq 2$, then $t^{(2)}(n)\geq\beta(n/4)^{\alpha}$ for
all $n\geq 2$.

It follows that $t^{(2)}(n)=\Omega(\tau(n))$, but, in fact, we have
$t^{(2)}(n)=\Theta(\tau(n))$ (the upper bound is trivial – see [6, Section
3.1] or [5, Section 3]).

Here we generalize Proposition 3.1 for all values of $r$. To this end, we
first show a (doubly) iterative lower bound on $t^{(r)}(n)$ which also depends
on $\tau(n)$. Set $\ell_{2}=n^{1/3}$ and, for every $r\geq 3$, set
$\ell_{r}(n)=\frac{1}{2}n^{1/(2^{r}-1)}$.

######  Lemma 3.2.

For all $n\geq 1$ and $r\geq 2$, $t^{(r)}(n)\geq\min\\{t_{0},t_{1},t_{2}\\}$,
where

$t_{0}=2t^{(r)}(n/3),\qquad t_{1}=\tau\left(\ell_{r-1}(n/6r)\right),$

and

$t_{2}=\min_{2\leq p\leq
r-2}\max\left\\{t^{(r-p)}\left(\ell_{p}(n/6r)\right),t^{(p)}\left(\ell_{r-p}(n/6r)\right)\right\\}.$

For $r\leq 3$, $t_{2}$ is not defined, or, to the same effect, we may set it
equal to $n$ in such cases, so that it does not affect the minimum.

From this we may derive recursively lower bounds on $t^{(r)}(n)$ in terms of
$n$ and $r$, assuming a lower bound on $\tau(n)$. For $r\geq 1$, let
$\eta_{r}=\frac{1}{2^{r}-1}$, so that now we can write
$\ell_{r}(n)=\frac{1}{2}n^{\eta_{r}}$.

######  Corollary 3.3.

For all $3/5\leq\alpha\leq 2/3$ and $\beta>0$, if $\tau(n)\geq\beta
n^{\alpha}$ for all $n\geq 2$, then for all $r\geq 2$ and all $n\geq 2$,

$t^{(r)}(n)\geq\beta_{r}(n/6r)^{\alpha\eta_{r-1}},$ (3.1)

where $\beta_{2}=\beta$, while for $r\geq 3$,

$\beta_{r}=\min\left\\{\min_{2\leq p\leq
r-2}\beta_{p}(12r)^{-\alpha\eta_{p-1}},\;\beta 2^{-\alpha}\right\\}.$

In particular, $t^{(3)}(n)\geq\beta_{3}(n/18)^{\alpha/3}$, where
$\beta_{3}=\beta 2^{-\alpha}$.

For technical reasons we have not pulled out the constant
$(6r)^{-\alpha\eta_{r-1}}$ and incorporated it into $\beta_{r}$ above. Note
also, that just for the sake of unification, for $r=2$ the bound in Corollary
3.3 is slightly weaker than the bound in Proposition 3.1. The case $r=2$ is
special also in that we have $t^{(2)}(n)=\Theta(\tau(n))$ (the upper bound is
trivial – see [6, Section 3.1]). On the other hand, for $r\geq 3$ the lower
bound in Corollary 3.3 does not seem to be close to the truth.

Applying the above mentioned bound $\tau(n)=\Omega\left(n^{3/5}\right)$, we
obtain immediately that

$t^{(r)}(n)=\Omega\left(n^{\frac{3}{5}\eta_{r-1}}\right)$

holds for all $r\geq 2$. This coincides with (1.2) and proves Theorem 1.2.
(For $r=2$ it was already deduced in [6, Corollary 3.5].) So, to complete the
proof of Theorem 1.2, it remains to prove Lemma 3.2 and Corollary 3.3.

###  3.2. Unavoidable patterns

Given $r\geq 2$, there are exactly $\tfrac{1}{2}\binom{2r}{r}$ ways, called
_patterns_ , in which a pair of disjoint edges of order $r$ may intertwine on
an ordered vertex set. We call them $r$-patterns if the order $r$ is to be
emphasized. For instance, using convenient letter notation, there are just
three patterns for $r=2$, namely $AABB,ABBA,ABAB$ and ten for $r=3$: $AAABBB$,
$AABABB$, $AABBBA$, $AABBAB$, $ABBBAA$, $ABBAAB$, $ABBABA$, $ABAABB$,
$ABABBA$, $ABABAB$. For a pattern $P$, a _$P$ -clique_ is defined as a
matching whose all pairs of edges form pattern $P$. For example, with
$P=ABAABB$, a $P$-clique is a 3- matching with the structure $A_{1}\cdots
A_{n}\;A_{1}A_{1}\cdots A_{n}A_{n}.$ Let $L_{P}(M)$ be the size of the largest
$P$-clique in a matching $M$, $L(M)=\max_{P}L_{P}(M)$, and
$L_{r}(n)=\min_{M}L(M)$, where the minimum is taken over all $r$-matchings $M$
of size $n$.

In [6] (see also [5]) we showed that $L_{2}(n)=\lfloor n^{1/3}\rfloor$ and
used this result (the lower bound) to prove Proposition 3.1. Very recently,
building upon the concepts and results contained in [7] and in [1], Sauerman
and Zakharov proved in [13] the following lower bound for every $r$. Recall
our notation from the previous subsection:
$\ell_{r}(n)=\frac{1}{2}n^{1/(2^{r}-1)}$ and $\eta_{r}=\frac{1}{2^{r}-1}$

######  Theorem 3.4 ([13]).

For all $r\geq 2$ and all $n\geq 1$, we have $L_{r}(n)\geq\ell_{r}(n)$.

In fact, in [13] there is a better constant than $\tfrac{1}{2}$ in front of
$n^{\eta_{r}}$ which depends on $r$ and goes to 1 as $r\to\infty$. For our
purposes this has very little effect and therefore we stick to the weaker but
easier to handle $1/2$.

###  3.3. Proof of Lemma 3.2

Let $M=M^{(r)}(n)$ be an ordered $r$-matching on $[rn]=H_{1}\cup H_{2}$, where
$H_{1}=\\{\lfloor rn/2\rfloor\\}$ and $H_{2}=[rn]\smallsetminus H_{1}$ are the
first and second “half” of the vertex set. Further, for
$p=0,1,2,\dots,r-2,r-1,r$, let

$n_{p}=|\\{e\in M\;:|e\cap H_{1}|=p\\}.$

Note that $\sum_{p=0}^{r}n_{p}=n$, while $\sum_{p=0}^{r}pn_{p}=\lfloor
rn/2\rfloor$ and, by symmetry, $\sum_{p=0}^{r}(r-p)n_{p}=\lceil rn/2\rceil$.
The latter identities imply that $\max\\{n_{r},n_{0}\\}\leq n/2$. We consider
three cases (more precisely, two cases one of which splits further into two
subcases) with respect to the values of $n_{p}$. For two edges $e,f\in M$ we
write $e<f$ whenever the leftmost vertex of $e$ is to the left of the leftmost
vertex of $f$, i.e., $\min e<\min f$.

Case 1: $\min\\{n_{0},n_{r}\\}\geq n/3$. Let $M_{r}$ and $M_{0}$ be the sub-
matchings of $M$ consisting of the edges contained in, respectively, $H_{1}$
and $H_{2}$. Then, for $i=0,r$, we have $|M_{i}|\geq n/3$, so
$t^{(r)}(M_{i})\geq t^{(r)}(n/3)$. Thus, by concatenation, $t^{(r)}(M)\geq
2t^{(r)}(n/3)$.

Case 2: $\min\\{n_{0},n_{r}\\}\leq n/3$. In this case, $n_{0}+n_{r}\leq
n/2+n/3=5n/6$, and so

$\sum_{p=1}^{r-1}n_{p}\geq n/6.$

Thus, we may consider two subcases (for simplicity we compromise $r-1$ to $r$
in all denominators).

Subcase 2a: $\max\\{n_{1},n_{r-1}\\}\geq n/(6r)$. W.l.o.g. we assume that
$n_{r-1}\geq n/(6r)$. Let $M_{r-1}\subset M$ consist of all $n_{r-1}$ edges of
$M$ which intersect $H_{1}$ in exactly $r-1$ vertices (and thus they intersect
$H_{2}$ in just one vertex). For each $e\in M_{r-1}$ we write
$e=e^{*}\cup\\{v_{e}\\}$, where $e^{*}\subset H_{1}$ and $v_{e}\in H_{2}$. Let
$M^{*}=\\{e^{*}\;:e\in M_{r-1}\\}$. Note that $|M^{*}|=|M_{r-1}|=n_{r-1}$. By
applying Theorem 3.4 to the $(r-1)$-matching $M^{*}$ we conclude that for some
$(r-1)$-pattern $P$ there is in $M^{*}$ a $P$-clique
$M^{*}_{P}=\\{e^{*}_{1}<\cdots<e^{*}_{m}\\}$ of size $m=L_{r-1}(n_{r-1})$. Set
$v_{i}:=v_{e_{i}}$, for convenience.

Let $\pi=v_{1},\ldots,v_{m}$ be the permutation of the right ends of the edges
of $M^{*}_{P}$ and let $\pi^{\prime}=v_{i_{1}},\ldots,v_{i_{t}}$ and
$\pi^{\prime\prime}=v_{j_{1}},\ldots,v_{j_{t}}$ be the longest twins in $\pi$.
Then, we claim that $M^{\prime}=\\{e_{i_{1}}<\cdots<e_{i_{t}}\\}$ and
$M^{\prime\prime}=\\{e_{j_{1}}<\cdots<e_{j_{t}}\\}$ are twins in $M$. Indeed,
for $1\leq g<h\leq t$, consider two pairs of edges $(e_{i_{g}},e_{i_{h}})\in
M^{\prime}$ and $(e_{j_{g}},e_{j_{h}})\in M^{\prime\prime}$. The first $r-1$
vertices of $e_{i_{g}}$ and $e_{i_{h}}$, i.e., $e^{*}_{i_{g}}$ and
$e^{*}_{i_{h}}$, as well, as $e^{*}_{j_{g}}$ and $e^{*}_{j_{h}}$ form the same
pattern $P$ (as they all belong to the clique $M^{*}_{P}$). Moreover, the
pairs of rightmost vertices, respectively, $v_{i_{g}}$, $v_{i_{h}}$ and
$v_{j_{g}}$, $v_{j_{h}}$, as being at the same positions in the twins
$\pi^{\prime}$ and $\pi^{\prime\prime}$, are in the same relation:
($v_{i_{g}}<v_{i_{h}}$ and $v_{j_{g}}<v_{j_{h}}$) or ($v_{i_{g}}>v_{i_{h}}$
and $v_{j_{g}}>v_{j_{h}}$).

As an example, consider a special case when $r=5$, $p=4$, and $P=ABBBAABA$.
Let $e_{A},e_{B},e_{C}$, $e_{D}$ be four edges whose first four vertices form
mutually pattern $P$, while the last vertices satisfy $v_{A}<v_{B}$ and
$v_{C}<v_{D}$. Then $e_{A}$ and $e_{B}$ form the pattern $ABBBAABA|AB$, while
$e_{C}$ and $e_{D}$ \- pattern $CDDDCCDC|CD$ which is the very same pattern
indeed.

This shows that
$t^{(r)}(M)\geq\tau\left(L_{r-1}(n_{r-1})\right)\geq\tau\left(L_{r-1}(n/6r)\right)$.

Subcase 2b: $\max_{2\leq p\leq r-2}n_{p}\geq n/(6r)$. Let, for some $2\leq
p\leq r-2$, $n_{p}\geq n/(6r)$. Let $M_{p}\subset M$ consist of all $n_{p}$
edges of $M$ which intersect $H_{1}$ in exactly $p$ vertices (and thus they
intersect $H_{2}$ in $r-p$ vertices). For each $e\in M_{p}$ we write
$e=e^{*}\cup e^{**}$, where $e^{*}=e\cap H_{1}$ and $e^{**}=e\cap H_{2}$. Let
$M^{*}=\\{e^{*}\;:e\in M_{p}\\}$. Note that $|M^{*}|=|M_{p}|=n_{p}$. By
applying Theorem 3.4 to the $p$-matching $M^{*}$ we conclude that for some
$p$-pattern $P$ there is in $M^{*}$ a $P$-clique
$M^{*}_{P}=\\{e^{*}_{1}<\cdots<e^{*}_{m}\\}$ of size $m\geq L_{p}(n_{p})$.

Let $M^{**}=\\{e^{**}_{i}:\;i=1,\dots,m\\}$ be the $(r-p)$-matching in $H_{2}$
consisting of the remainders of the edges in $M^{*}_{P}$. Further, let
$M^{**^{\prime}}=\\{e^{**}_{i_{1}}<\cdots<e^{**}_{i_{t}}\\}$ and
$M^{**^{\prime\prime}}=\\{e^{**}_{j_{1}}<\cdots<e^{**}_{j_{t}}\\}$ be the
largest twins in $M^{**}$. Then, we claim that
$M^{\prime}=\\{e_{i_{1}}<\cdots<e_{i_{t}}\\}$ and
$M^{\prime\prime}=\\{e_{j_{1}}<\cdots<e_{j_{t}}\\}$ are twins in $M$. Indeed,
for $1\leq g<h\leq t$, consider two pairs of edges $(e_{i_{g}},e_{i_{h}})\in
M^{\prime}$ and $(e_{j_{g}},e_{j_{h}})\in M^{\prime\prime}$. The $p$-long
prefixes of $e_{i_{g}}$ and $e_{i_{h}}$, i.e. $e^{*}_{j_{g}}$ and
$e^{*}_{j_{h}})$ form pattern $P$, as the prefixes $e^{*}_{j_{g}}$ and
$e^{*}_{j_{h}}$ do. Moreover, the $(r-p)$-element suffixes $e^{**}_{i_{g}}$
and $e^{**}_{i_{h}}$ form the same $(r-p)$-pattern $Q$ as $e^{**}_{j_{g}}$ and
$e^{**}_{j_{h}}$ do. So, the pairs $(e_{i_{g}},e_{i_{h}})$ and
$(e_{j_{g}},e_{j_{h}})$ form the same $r$-pattern $R$, which proves that
$M^{\prime}$ and $M^{\prime\prime}$ are twins.

To illustrate this part of the proof, consider a special case when $r=5$ and
$p=3$. Let $P=AABBBA$ be a collectible 3-pattern and let $Q=ABBA$. If four
edges, $e_{A},e_{B},e_{C}$, $e_{D}$ each have 3 vertices in $H_{1}$ which
mutually form pattern $P$ and, moreover, the 2-vertex remainders of $e_{A}$
and $e_{B}$ form in $H_{2}$ pattern $Q$, and the same holds for the 2-vertex
remainders of $e_{C}$ and $e_{D}$, then edges $e_{A}$ and $e_{B}$ from overall
pattern $AABBBAABBA$, while edges $e_{C}$ and $e_{D}$ form pattern
$CCDDDCCDDC$, which is the very same pattern (we call it $R$ in our proof).

Hence,

$t^{(r)}(M)\geq t^{(r-p)}(m)\geq t^{(r-p)}\left(L_{p}(n_{p})\right).$

We could repeat the entire argument in Subcase 2b with the roles of $p$ and
$r-p$ swapped yielding the $\max$ in the definition of $t_{2}$. Finally, we
have to minimize the obtained bound over all $2\leq p\leq r-2$ and over all
three subcases. ∎

###  3.4. Proof of Corollary 3.3

The proof is by double induction on $r\geq 2$ and $n\geq 2$. The case $r=2$
was proved in [6], see Proposition 3.1 above. Indeed, by Proposition 3.1 we
have

$t^{(2)}(n)\geq\beta(n/4)^{\alpha}\geq\beta(n/12)^{\alpha}=\beta_{2}(n/12)^{\alpha}.$

Moreover, for $r\geq 3$, if $2\leq n\leq
6r(1/\beta_{r})^{\frac{1}{\alpha\eta_{r-1}}}$, then the desired bound becomes
$t^{(r)}(n)\geq 1$ which is trivially true. Thus, assume that $r\geq 3$,
$n\geq 6r(1/\beta_{r})^{\frac{1}{\alpha\eta_{r-1}}}$, equivalently,

$\beta_{r}(n/6r)^{\alpha\eta_{r-1}}\geq 1$ (3.2)

and that (3.1) holds for all $2\leq r^{\prime}<r$ and $2\leq n^{\prime}<n$.

Note that the assumption $\tau(n)\geq\beta n^{\alpha}$ for all $n\geq 2$
implies, by taking $n=2$, that $1\geq\beta 2^{\alpha}$, or $\beta\leq
2^{-\alpha}$. Thus, whenever (3.2) holds, recalling that $\beta_{r}\leq
2^{-\alpha}\beta$, it follows that

$\tfrac{1}{2}(n/6r)^{1/\eta_{r-1}}\geq\tfrac{1}{2}\beta_{r}^{-1/\alpha}\geq\beta^{-1/\alpha}\geq
2.$

This, in turn, implies that $n/6r>1$ and, consequently, that in Lemma 3.2 all
arguments appearing in the functions defining $t_{0}$, $t_{1}$, and $t_{2}$
are larger or equal to 2 (and, obviously, less than $n$) allowing to apply the
induction assumptions.

By Lemma 3.2, we know that $t^{(r)}(n)\geq\min\\{t_{0},t_{1},t_{2}\\}$. So,
consider three cases.

Case 0: $t^{(r)}(n)\geq t_{0}$. As $n/3\geq 2$, by induction’s assumption we
have

$t^{(r)}(n)\geq t_{0}=2t^{(r)}(n/3)\geq
2\beta_{r}(n/18r)^{\alpha\eta_{r-1}}\geq\beta_{r}(n/6r)^{\alpha\eta_{r-1}},$

the last inequality equivalent to $2^{1/\eta_{r-1}}=2^{2^{r-1}-1}\geq
3^{\alpha}$, which is true for $r\geq 3$ (recall that $\alpha\leq 1$).

Case 1: $t^{(r)}(n)\geq t_{1}$. In this case, by the assumption,

$t^{(r)}(n)\geq
t_{1}=\tau\left(\tfrac{1}{2}(n/6r)^{\eta_{r-1}}\right)\geq\beta
2^{-\alpha}(n/6r)^{\alpha\eta_{r-1}}\geq\beta_{r}(n/6r)^{\alpha\eta_{r-1}},$

since $\beta_{r}\leq 2^{-\alpha}\beta$.

Case 2: $t^{(r)}(n)\geq t_{2}$. By induction’s assumption,

$\displaystyle t^{(r)}(n)\geq t_{2}$ $\displaystyle=\min_{2\leq p\leq
r-2}\max\left\\{t^{(r-p)}\left(\tfrac{1}{2}(n/6r)^{\eta_{p}}\right),\;t^{(p)}\left(\tfrac{1}{2}(n/6r)^{\eta_{r-p}}\right)\right\\}$
$\displaystyle\geq\min_{2\leq p\leq
r-2}\max\left\\{\beta_{r-p}\left(\frac{(n/6r)^{\eta_{p}}}{12(r-p)}\right)^{\alpha\eta_{r-p-1}},\;\beta_{p}\left(\frac{(n/6r)^{\eta_{r-p}}}{12p}\right)^{\alpha\eta_{p-1}}\right\\}$
$\displaystyle\geq\min_{2\leq p\leq
r-2}\max\left\\{\beta_{r-p}(12r)^{-\alpha\eta_{r-p-1}},\;\beta_{p}(12r)^{-\alpha\eta_{p-1}}\right\\}(n/6r)^{\alpha\eta_{r-1}}$
$\displaystyle\geq\beta_{r}(n/6r)^{\alpha\eta_{r-1}},$

by choosing $\beta_{r}\leq\min_{2\leq p\leq
r-2}\beta_{p}(12r)^{-\alpha\eta_{p-1}}.$ (Above we used the facts that
$n/6r>1$ and $\eta_{p}\eta_{r-p-1}>\eta_{r-1}$, both with a big margin.) ∎

##  4\. Concluding remarks

Let us conclude the paper with some problems for future considerations.
Firstly, it is natural to speculate on the true asymptotic order of the
function $t^{(r)}(n)$. Based on Theorem 1.1 and the former results around
Gawron’s conjecture [9] on twins in permutations (see also [4]), we dare to
state the following.

######  Conjecture 4.1.

For every $r\geqslant 2$, $t^{(r)}(n)=\Theta\left(n^{\frac{2}{r+1}}\right)$.

Notice that the case $r=2$ of this statement is the original Gawron’s
conjecture. It seems that even increasing the exponent of $n$ in the lower
bound (1.2) to the inverse of any polynomial in $r$ will be quite a challenge.

One could also consider a generalization to $t$-tuplets, that is, $t$-tuples
of vertex disjoint order-isomorphic sub-matchings of a given $r$-matching. In
fact, the proof techniques from Section 2 yield that this generalized
parameter is a.a.s. $\Theta(n^{t/(r(t-1)+1)})$ (for $t=2$ we thus recover
Theorem 1.1). A highly technical analog of Theorem 1.2 could be proved as
well.

It seems also natural to study the problem of the largest twins in more
general classes of ordered graphs ($r=2$) or hypergraphs ($r\geq 3$). By
_twins_ in an ordered graph $G$ we mean a pair of edge-disjoint order-
isomorphic subgraphs of $G$. Let $t(G)$ denote the maximum size of twins in
$G$, and let $t(m)$ be the minimum of $t(G)$ over all ordered graphs with $m$
edges. What can be said about the function $t(m)$? By the results for ordered
matchings we know only that $t(m)=O(m^{\frac{2}{3}})$, but is it optimal? It
is worth mentioning that the analogous problem for unordered graphs was solved
by Lee, Loh, and Sudakov [10] who proved that the corresponding function is
$\Theta\left((m\log m)^{\frac{2}{3}}\right)$.

Finally, one may also investigate the size of twins in general words over
finite alphabets. Therein, twins are defined as pairs of identical
subsequences occupying disjoint sets of positions. Actually, our motivation to
study twins in permutations and ordered matchings has been ignited by a
beautiful result of Axenovich, Person, and Puzynina [2], stating that every
binary word of length $n$ contains twins of size $\frac{1}{2}n-o(n)$.

Inspired by the word representation of ordered matchings (used also in this
paper), one may consider a relaxed variant of twins in words, in which a pair
of disjoint subwords forms _permuted twins_ if they are identical up to a
permutation of their letters. For instance, in this new setting, the subwords
$112142212$ and $223213323$ of a word over alphabet $\\{1,2,3,4\\}$, would
form permuted twins (under permutation $2341$). How large permuted twins may
one find in every word of length $n$ over a $k$-element alphabet? Will they be
much bigger, especially for large $k$, than in the classical case?

Acknowledgments. We would like to thank an anonymous referee for a careful
reading of the manuscript and suggesting a number of editorial improvements.

## References

  * [1] M. Anastos, Z. Jin, M. Kwan and B. Sudakov, Extremal, enumerative and probabilistic results on ordered hypergraph matchings, manuscript, https://arxiv.org/pdf/2308.12268.pdf.
  * [2] M. Axenovich, Y. Person, S. Puzynina, Regularity lemma and twins in sequences, J. Comb. Theory Ser. A 120 (2013) 733–743.
  * [3] B. Bukh and O. Rudenko, Order-isomorphic twins in permutations, SIAM J. Discrete Math. 34 (2020), 1620–1622.
  * [4] A. Dudek, J. Grytczuk and A. Ruciński, Variations on twins in permutations, Electronic Journal of Combinatorics 28 (2021), no. 3, P3.19.
  * [5] A. Dudek and J. Grytczuk and A. Ruciński, Patterns in ordered (random) matchings, A. Castaneda and F. Rodrdriguez-Henrriquez (Eds.): LATIN 2022, LNCS 13568, pp. 544–556, 2022. https://doi.org/10.1007/978-3-031-20624-5_33.
  * [6] A. Dudek, J. Grytczuk and A. Ruciński, Ordered unavoidable sub-structures in matchings and random matchings, manuscript, https://arxiv.org/pdf/2210.14042.pdf.
  * [7] A. Dudek, J. Grytczuk and A. Ruciński, Erdős-Szekeres type theorems for ordered uniform matchings, manuscript, https://arxiv.org/pdf/2301.02936.pdf.
  * [8] P. Erdős, G. Szekeres, A combinatorial problem in geometry, Compositio Mathematica 2 (1935) 463–470.
  * [9] M. Gawron, Izomorficzne podstruktury w słowach i permutacjach, Master Thesis, 2014.
  * [10] C. Lee, P. Loh, B. Sudakov, Self-similarity of graphs, SIAM J. Discret. Math. 27(2) (2013) 959–972.
  * [11] M. Luczak, C. McDiarmid, Concentration for locally acting permutations, Discrete Math. 265 (2003) 159–171.
  * [12] C. McDiarmid, Concentration for independent random permutations, Combin. Probab. Comput. 11 (2002) 163–178.
  * [13] L. Sauermann, D. Zakharov, A sharp Ramsey theorem for ordered hypergraph matchings, manuscript, https://arxiv.org/pdf/2309.04813.pdf.
  * [14] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publ. Math. Inst. Hautes Etudes Sci. 81 (1995) 73–205.