# STUDIES OF THE LINEARITY AND STABILITY OF SILICON DRIFT DETECTORS FOR KAONIC
ATOMS X-RAY SPECTROSCOPY††thanks: Presented at the 4th Jagiellonian Symposium
on Advances in Particle Physics and Medicine, Kraków, Poland, 10-15 July 2022.

A. Khreptaka,b, Corresponding author<EMAIL_ADDRESS>C.
Amslerc M. Bazzia D. Bosnard M. Bragadireanue M. Carminatif,g M. Cargnellic A.
Clozzaa G. Dedaf,g L. De Paolisa R. Del Grandeh,a L. Fabbiettih C. Fiorinif,g
C. Guaraldoa M. Iliescua M. Iwasakii S. Mantia J. Martonc M. Miliuccia P.
Moskalb,j F. Napolitanoa S. Niedźwieckib,j H. Ohnishik K. Piscicchial,a Y.
Sadak A. Scordoa F. Sgaramellaa H. Shic M. Silarskib,j D. Sirghia,l,e F.
Sirghia,e M. Skurzokb,j A. Spallonea K. Tohok M. Tüchlerc,m O. Vazquez Docea
J. Zmeskalc C. Yoshidak and C. Curceanua a INFN, Laboratori Nazionali di
Frascati, Frascati (Roma), Italy
b Institute of Physics, Jagiellonian University, Kraków, Poland
c Stefan-Meyer-Institut für Subatomare Physik, Vienna, Austria
d Department of Physics, Faculty of Science, University of Zagreb, Croatia
e IFIN-HH, Institutul National pentru Fizica si Inginerie Nucleara Horia
Hulubbei, Măgurele, Romania
f Politecnico di Milano, Dipartimento di Elettronica, Informazione e
Bioingegneria, Milano, Italy
g INFN Sezione di Milano, Italy
h Physik Department E62, Technische Universität München, Garching, Germany
i RIKEN, Institute of Physical and Chemical Research, Wako, Japan
j Center for Theranostics, Jagiellonian University, Kraków, Poland
k Research Center for Electron Photon Science (ELPH), Tohoku University,
Sendai, Japan
l Centro Ricerche Enrico Fermi - Museo Storico della Fisica e Centro Studi e
Ricerche “Enrico Fermi”, Rome, Italy
m University of Vienna, Vienna Doctoral School in Physics, Vienna, Austria

###### Abstract

The SIDDHARTA-2 experiment at the DA$\Phi$NE collider aims to perform
precision measurements of kaonic atoms X-ray spectroscopy for the
investigation of the antikaon-nucleon strong interaction. To achieve this
goal, novel large-area Silicon Drift Detectors (SDDs) have been developed.
These devices have special geometry, field configuration and readout
electronics that ensure excellent performance in terms of linearity and
stability. The paper presents preliminary results for the linearity
determination and stability monitoring of the SDDs system during the
measurement of kaonic deuterium carried out in the summer of 2022.

DOI:10.5506/APhysPolBSupp…

##  1 Introduction

The Silicon Drift Detectors (SDDs) [1, 2] combine the silicon p–n junction
response to ionizing radiation with an innovative electronic field design [3].
These devices play a key role in high-precision X-ray spectroscopy of light
exotic atoms [4], due to their low electronic noise, good energy resolution
and high rate capability [5]. In particular, their excellent capabilities are
exploited to extract the shift ($\epsilon$) and width ($\Gamma$) of atomic
levels caused by the strong antikaon-nucleon interaction [6]. Experimental
studies of light kaonic atoms provide a unique tool to investigate the non-
perturbative quantum chromodynamics (QCD) in the strangeness sector [7, 8].

After the successful data taking campaign of the SIDDHARTA (Silicon Drift
Detectors for Hadronic Atom Research by Timing Application) experiment in
2009, resulting in the most precise measurement of the kaonic hydrogen
($\overline{K}p$) fundamental level shift ($\epsilon$) and width ($\Gamma$)
[9], the SIDDHARTA-2 collaboration implemented several updates of the
apparatus to perform the analogous, more challenging kaonic deuterium
($\overline{K}d$) $2p\rightarrow 1s$ transition measurement [10]. The
experimental facility is located at the DA$\Phi$NE collider [11] of the
Istituto Nazionale di Fisica Nucleare - Laboratori Nazionali di Frascati
(INFN-LNF) in Italy.

The SDD detector, used in the experiment, is composed of a fully depleted n-
silicon cylindrical bulk, double sided by p+ silicon doped electrodes [1, 2].
On one side, a layer of p+ concentric ring strips are biased with a negative
voltage through an internal divider, while on the opposite side, a metalized
non-structured p+ layer forms the radiation entrance window (see Fig. 1). The
electrons produced by the absorbed radiation are focused by the radial drift
field to the small n+ anode, placed in the center of the structured side and
connected to the dedicated front-end electronics.

Figure 1: Schematic layout of a cylindrical SDD. The dotted lines represent
the drift field inside the bulk. Figure adapted from Ref. [12]

New monolithic large-area SDD arrays have been developed by Fondazione Bruno
Kessler, together with Politecnico di Milano, INFN-LNF in Italy and the Stefan
Meyer Institute (SMI) in Austria, to perform high precision kaonic deuterium
spectroscopy [3, 7]. The 450 $\mu$m thick SDD array consists of a $2\times 4$
matrix of square cells (0.64 cm2 area for each single unit), mounted on an
alumina carrier. The signals coming from the detectors are buffered by a CMOS
low-noise charge sensitive preamplifier (CUBE [13]), directly connected to the
n+ anode, then processed by a dedicated analog SDD front-end readout ASIC
(SFERA [14]).

The SIDDHARTA-2 experimental apparatus [6, 10] consists of 48 SDD arrays,
resulting in a total of 384 readout channels, and a luminometer built with
plastic scintillators, based on J-PET technology [15, 16, 17, 18, 19]. Studies
of the linearity and stability of the SDD system are mandatory to achieve the
planned high precision measurement of kaonic deuterium X-rays by keeping the
systematic error within a few eV.

##  2 Linearity characterization

The SDD linearity studies were performed with an X-ray tube exciting a target
made of high purity titanium and copper strips [12]. Fig. 2(a) shows a typical
spectroscopic response of a single SDD unit at $-145^{\circ}$C, irradiated by
fluorescence emission from the target strips, activated by the X-ray tube
operated at 25 kV and 50 $\mu$A. Together with the titanium (Ti) and copper
(Cu) lines, the Mn Kα and Fe Kα (produced by the excitation of other
components of the setup) are also visible.

The spectral response of silicon detectors is predominantly described by a
Gaussian function for each X-ray peak, with a low energy tail due to the
incomplete charge collection at the anode, and electron-hole recombination.
Thus, the shape of the peaks was modeled taking into account the intrinsic
Gaussian statistical spread and the tail effect [20, 21, 22].

The fit function (red curve in Fig. 2(a)) reproduces the fluorescence lines
coming from the target. The various contributions to the overall fit function
are also shown. A constant plus an exponential function describes the
background. Fig. 2(b) presents the fit residuals. The Ti Kα, Fe Kα and Cu Kα
peaks were exploited to evaluate the linearity of the detectors, due to their
higher signal-to-background ratio. The positions of these peaks were plotted
as a function of the tabulated energy values [23], and a straight line was
used to interpolate the points (see Fig. 2(c)). The slope of the fit function
(in eV/channel) gives the gain parameter value of the spectrum.

Figure 2: (a) A fitted fluorescence spectrum for a single SDD in arbitrary ADC
units. Red line shows the overall fit function consisting of a sum of Gaussian
(violet line) and tail functions (green line) for each peak, together with a
constant plus an exponential function to describe the background (cyan line).
(b) Residuals from the fit of the spectrum. (c) Linear interpolation of the
experimental Kα peak positions as a function of the known energies of
transitions.

The final energy spectrum is shown in Fig. 3(a). The difference between each
Kα experimental calibrated point ($P^{exp}_{i}$) with respect to its
corresponding theoretical value ($P^{label}_{i}$) was used for the evaluation
of the system linearity:

$R_{i}=P^{label}_{i}-P^{exp}_{i}.$ (1)

Figure 3: (a) Calibrated energy spectrum of the single SDD. (b) Difference
between each Kα experimental calibrated point ($P^{exp}_{i}$) with respect to
its corresponding theoretical value ($P^{label}_{i}$).

The distribution in Fig. 3(b) shows that the peak energies differ from the
theoretical values by less than 1.5 eV, setting the linear response $\Delta
E/E$ of the SDD below $10^{-3}$.

##  3 Stability

Another important aspect of the SDD system that needs to be monitored during
high-precision measurements is its long-term stability, since it is a possible
source of systematic error in the experiment. During the kaonic deuterium test
measurement period, which took place in June-July 2022, 12 calibration runs
were performed. For each SDD, fluctuations over time of the Cu Kα peak
position were used to control the stability (see Fig. 4(a)). During the
measurements in June 2022 the fluctuations of the Cu Kα position were about
0.5 channels, which corresponds to $\sim$1.5 eV, and are comparable with the
residuals evaluated during the analysis in the Section 2. However, the
deviation of the peak position in the last two runs of July was larger (within
$\sim 1.5$ channels, corresponding to $\sim 4.5$ eV), which is related to more
unstable beams condition during the measurement.

Figure 4: (a) The position of the Cu Kα peak (in arbitrary ADC units) as a
function of time for a typical SDD. (b) Width stability of the Cu Kα line.

The energy resolution reflects its accuracy in determining the energy of the
incoming radiation. For the SDD, the Full Width at Half Maximum (FWHM) of the
peak depends on the energy of the incoming photons, and on the electronic
noise of the system [24]. Fig. 4(b) shows the FWHM (in eV) of the Cu Kα line,
as a function of time, for a typical SDD unit. The width of the peak varies by
about $\pm 2.5$ eV.

Both results indicate very good stability of the SDDs throughout the
experiment, thus providing an excellent opportunity to accurately determine
the position of the kaonic deuterium peak, as well as the peak width.

## Conclusions

The SIDDHARTA-2 collaboration has developed a new Silicon Drift Detector (SDD)
system for the measurement of the kaonic deuterium X-ray transitions to the
ground state. The experimental setup has been installed at the DA$\Phi$NE
collider of the INFN-LNF. The linearity and stability of the SDDs were
monitored during the kaonic deuterium test run, and its performance is
described in this work. The detectors are linear and stable within a few eV in
the energy region of interest. Following the 2022 kaonic deuterium test run, a
full measurement will be performed in 2023 to extract for the first time the
strong interaction effects in this exotic atom.

## Acknowledgments

We thank C. Capoccia from LNF-INFN and H. Schneider, L. Stohwasser, and D.
Pristauz-Telsnigg from Stefan-Meyer-Institut for their fundamental
contribution in designing and building the SIDDHARTA-2 setup. We thank as well
the DA$\Phi$NE staff for the excellent working conditions and permanent
support. Part of this work was supported by the Austrian Science Fund (FWF):
[P24756-N20 and P33037-N]; the Croatian Science Foundation under the project
IP-2018-01-8570; the EU STRONG-2020 project (Grant Agreement No. 824093); the
EU Horizon 2020 research and innovation programme under the Marie Skłodowska-
Curie Grant Agreement No. 754496; the Japan Society for the Promotion of
Science JSPS KAKENHI Grant No. JP18H05402; the Polish National Agency for
Academic Exchange (Grant No. PPN/BIT/2021/1/00037); the SciMat and qLIFE
Priority Research Areas budget under the program Excellence Initiative -
Research University at the Jagiellonian University.

## References

  * [1] P. Lechner “Silicon drift detectors for high resolution room temperature X-ray spectroscopy” In _Nucl. Instrum. Meth. Phys. Res. A_ 377.2, 1996, pp. 346 DOI: 10.1016/0168-9002(96)00210-0
  * [2] P. Lechner “Silicon drift detectors for high count rate X-ray spectroscopy at room temperature” In _Nucl. Instrum. Meth. Phys. Res. A_ 458.1, 2001, pp. 281 DOI: 10.1016/S0168-9002(00)00872-X
  * [3] M. Miliucci “Large area silicon drift detectors system for high precision timed x-ray spectroscopy” In _Meas. Sci. Technol._ 33.9, 2022, pp. 095502 DOI: 10.1088/1361-6501/ac777a
  * [4] M. Bazzi “Performance of silicon-drift detectors in kaonic atom X-ray measurements” In _Nucl. Instrum. Meth. Phys. Res. A_ 628.1, 2011, pp. 264 DOI: 10.1016/j.nima.2010.06.332
  * [5] M. Miliucci “Silicon drift detectors system for high-precision light kaonic atoms spectroscopy” In _Meas. Sci. Technol._ 32.9, 2021, pp. 095501 DOI: 10.1088/1361-6501/abeea9
  * [6] Marco Miliucci “Silicon Drift Detectors‘ Spectroscopic Response during the SIDDHARTA-2 Kaonic Helium Run at the DA$\$Phi$NE Collider” In _Condens. Matter._ 6, 2021, pp. 47 DOI: 10.3390/condmat6040047
  * [7] Catalina Curceanu “The modern era of light kaonic atom experiments” In _Rev. Mod. Phys._ 91, 2019, pp. 025006 DOI: 10.1103/RevModPhys.91.025006
  * [8] Catalina Curceanu “Kaonic Atoms to Investigate Global Symmetry Breaking” In _Symmetry_ 12.4, 2020, pp. 547 DOI: 10.3390/sym12040547
  * [9] M. Bazzi “A new measurement of kaonic hydrogen X-rays” In _Phys. Lett. B_ 704.3, 2011, pp. 113 DOI: 10.1016/j.physletb.2011.09.011
  * [10] Marlene Tüchler “Main Features of the SIDDHARTA-2 Apparatus for Kaonic Deuterium X-Ray Measurements” In _EPJ Web Conf._ 262, 2022, pp. 01016 DOI: 10.1051/epjconf/202226201016
  * [11] C. Milardi “Preparation activity for the SIDHARTA-2 run at DA$\Phi$NE” In _Proc. 9th International Particle Accelerator Conference (IPAC’18)_ , 2018, pp. 334 DOI: 10.18429/JACoW-IPAC2018-MOPMF088
  * [12] F. Sgaramella “The SIDDHARTA-2 calibration method for high precision kaonic atoms X-ray spectroscopy measurements” In _arXiv:2201.12101_ , 2022 URL: https://arxiv.org/abs/2201.12101
  * [13] L. Bombelli “”CUBE”, A low-noise CMOS preamplifier as alternative to JFET front-end for high-count rate spectroscopy” In _IEEE Nucl. Sc. Symp. Conf. Record_ , 2011, pp. 1972 DOI: 10.1109/NSSMIC.2011.6154396
  * [14] R. Quaglia “Development of arrays of Silicon Drift Detectors and readout ASIC for the SIDDHARTA experiment” In _Nucl. Instrum. Meth. Phys. Res. A_ 824, 2016, pp. 449 DOI: https://doi.org/10.1016/j.nima.2015.08.079
  * [15] M. Skurzok “Characterization of the SIDDHARTA-2 luminosity monitor” In _JINST_ 15.10, 2020, pp. P10010 DOI: 10.1088/1748-0221/15/10/p10010
  * [16] S. Niedźwiecki “J-PET: A NEW TECHNOLOGY FOR THE WHOLE-BODY PET IMAGING” In _Acta Phys. Pol. B_ 48.10, 2017, pp. 1567 DOI: 10.5506/APhysPolB.48.1567
  * [17] P. Moskal “Simulating NEMA characteristics of the modular total-body J-PET scanner an economic total-body PET from plastic scintillators” In _Phys. Med. Biol._ 66.17, 2021, pp. 175015 DOI: 10.1088/1361-6560/ac16bd
  * [18] P. Moskal “Testing CPT symmetry in ortho-positronium decays with positronium annihilation tomography” In _Nat. Commun._ 12, 2021, pp. 5658 DOI: 10.1038/s41467-021-25905-9
  * [19] P. Moskal “Positronium imaging with the novel multiphoton PET scanner” In _Sci. Adv._ 7.42, 2021, pp. eabh4394 DOI: 10.1126/sciadv.abh4394
  * [20] J. L. Campbell “X-ray spectrometers for PIXE” In _Nucl. Instrum. Methods Phys. Res. B_ 49, 1990, pp. 115 DOI: 10.1016/0168-583X(90)90227-L
  * [21] J. Campbell and J. Maxwell “A cautionary note on the use of the Hypermet tailing function in X-ray spectrometry with Si(Li) detectors” In _Nucl. Instrum. Methods Phys. Res. B_ 129, 1997, pp. 297 DOI: 10.1016/S0168-583X(97)00229-2
  * [22] M. V. Gysel, P. Lemberge and P. V. Espen “Implementation of a spectrum fitting procedure using a robust peak model” In _X-Ray Spectrom._ 32, 2003, pp. 434 DOI: 10.1002/xrs.666
  * [23] H. Winick “X-Ray Data Booklet” Berkeley: LBNL, 2009
  * [24] M. Miliucci “Energy Response of Silicon Drift Detectors for Kaonic Atom Precision Measurements” In _Condens. Matter._ 4.1, 2019, pp. 31 DOI: 10.3390/condmat4010031


M. Kostić,
Stepanov $\rho$-almost periodic functions in general metric,
submitted (2021). https://www.researchgate.net/publication/357152220.

[23]
M. Kostić,
Weyl $\rho$-almost periodic functions in general metric,
submitted (2021). https://www.researchgate.net/publication/357129349.

[24]
M. Kostić,
Multi-dimensional Besicovitch almost periodic type functions and applications,
submitted. 2022.  arXiv:2202.10521.

[25]
M. Kostić, W.-S. Du, V. E. Fedorov,
Doss $\rho$-almost periodic type functions in ${\mathbb R}^{n},$
Mathematics 9 (2021), 2825. https://doi.org/10.3390/math9212825.

[26]
M. Levitan,
Almost Periodic Functions,
G.I.T.T.L., Moscow, 1953 (in Russian).

[27]
B. M. Levitan, V. V. Zhikov,
Almost Periodic Functions and Differential Equations,
Univ. Publ. House, Moscow, 1978, English
translation by Cambridge University Press, 1982.

[28]
A. Nawrocki,
Diophantine approximations and almost
periodic functions,
Demonstr. Math. 50 (2017), 100–104.

[29]
A. Oliaro, L. Rodino, P. Wahlberg,
Almost periodic pseudodifferential operators and Gevrey
Ann. Mat. Pura Appl. 191 (2012), 725–760.

[30]
A. A. Pankov,
Bounded and Almost Periodic Solutions of Nonlinear Operator
Differential Equations, Kluwer Acad. Publ., Dordrecht, 1990.

[31]
M. A. Shubin,
Differential and pseudodifferential operators in spaces of
almost periodic functions,
Math. USSR-Sb. 24 (1974), 547–573.

[32]
S. Stoínski,
A connection between $H$-almost periodic functions and almost periodic functions
of other types,
Funct. Approx. Comment. Math. 3 (1976), 205–223.

[33]
S. Stoínski,
Real-valued functions almost periodic in variation,
Func. Approx.
22 (1993), 141–148.

[34]
S. Stoínski,
$L_{\alpha}$-almost periodic functions,
Demonstratio Math.
28 (1995), 689–696.

[35]
S. Stoínski,
A note on $H$-almost periodic functions and $S^{P}$-almost periodic functions,
Demonstratio Math.
29 (1996), 557–564.

[36]
S. Stoínski,
Some remarks on spaces of almost periodic functions,
Fasc. Math. No. 31 (2001), 105–1115.

[37]
S. Zaidman,
Almost-Periodic Functions in Abstract Spaces,
Pitman Research Notes in
Math, Vol. 126, Pitman, Boston, 1985.


# Ordered unavoidable sub-structures in matchings and random matchings ***An
extended abstract of this paper appears in [DGR_LATIN].

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 matching of size $n$_ is a graph on a linearly ordered vertex set
$V$, $|V|=2n$, consisting of $n$ pairwise disjoint edges. There are three
different ordered matchings of size two on $V=[4]$: an _alignment_
$\\{1,2\\},\\{3,4\\}$, a _nesting_ $\\{1,4\\},\\{2,3\\}$, and a _crossing_
$\\{1,3\\},\\{2,4\\}$. Accordingly, there are three basic homogeneous types of
ordered matchings (with all pairs of edges arranged in the same way) which we
call, respectively, _lines_ , _stacks_ , and _waves_.

We prove an Erdős-Szekeres type result guaranteeing in every ordered matching
of size $n$ the presence of one of the three basic sub-structures of a given
size. In particular, one of them must be of size at least $n^{1/3}$. We also
investigate the size of each of the three sub-structures in a _random_ ordered
matching. Additionally, the former result is generalized to $3$-uniform
ordered matchings.

Another type of unavoidable patterns we study are _twins_ , that is, pairs of
order-isomorphic, disjoint sub-matchings. By relating to a similar problem for
permutations, we prove that the maximum size of twins that occur in every
ordered matching of size $n$ is $O\left(n^{2/3}\right)$ and
$\Omega\left(n^{3/5}\right)$. We conjecture that the upper bound is the
correct order of magnitude and confirm it for almost all matchings. In fact,
our results for twins are proved more generally for $r$-multiple twins, $r\geq
2$.

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

###  1.1. Background

A graph $G$ is said to be _ordered_ if its vertex set is linearly ordered. Let
$G$ and $H$ be two ordered graphs with $V(G)=\\{v_{1}<\cdots<v_{m}\\}$ and
$V(H)=\\{w_{1}<\cdots<w_{m}\\}$ for some integer $m\geq 1$. We say that $G$
and $H$ are _order-isomorphic_ if for all $1\leq i<j\leq m$, $v_{i}v_{j}\in
E(G)$ if and only if $w_{i}w_{j}\in E(H)$. Note that every pair of order-
isomorphic graphs is isomorphic, but not vice-versa. Also, if $G$ and $H$ are
distinct graphs on the same linearly ordered vertex set $V$, then $G$ and $H$
are never order-isomorphic, and so all $2^{\binom{|V|}{2}}$ labeled graphs on
$V$ are pairwise non-order-isomorphic. It shows that the notion of order-
isomorphism make sense only for pairs of graphs on distinct vertex sets.

One context in which order-isomorphism makes quite a difference is that of
subgraph containment. If $G$ is an ordered graph, then any subgraph
$G^{\prime}$ of $G$ can be also treated as an ordered graph with the ordering
of $V(G^{\prime})$ inherited from the ordering of $V(G)$. Given two ordered
graphs, (a “large” one) $G$ and (a “small” one) $H$, we say that a subgraph
$G^{\prime}\subset G$ is _an ordered copy of $H$ in $G$_ if $G^{\prime}$ and
$H$ are order-isomorphic. We will sometimes denote this fact by writing
$G^{\prime}\preceq G$.

All kinds of questions concerning subgraphs in unordered graphs can be posed
for ordered graphs as well (see, e.g., [Tardos] and [BGT]). For example, in
[ConlonFoxSudakov], the authors studied Turán and Ramsey type problems for
ordered graphs. In particular, they showed that there exists an ordered
matching on $n$ vertices for which the (ordered) Ramsey number is super-
polynomial in $n$, a sharp contrast with the linearity of the Ramsey number
for ordinary (i.e. unordered) matchings. This shows that it makes sense to
study even such seemingly simple structures as ordered matchings. In fact,
Jelínek [VJ] counted the number of matchings avoiding (i.e. not containing) a
given small ordered matching.

###  1.2. Topics and organization

In this paper we focus exclusively on _ordered matchings_ , that is, ordered
graphs which consist of vertex-disjoint edges (and have no isolated vertices).
For example, in Figure 1.1, we depict two ordered matchings,
$M=\\{\\{1,3\\},\\{2,4\\},\\{5,6\\}\\}$ and
$N=\\{\\{1,5\\},\\{2,3\\},\\{4,6\\}\\}$ on vertex set $[6]$ with the natural
linear ordering.

Figure 1.1. Exemplary matchings $M$ and $N$.

Unlike in [VJ], we study what sub-structures are _unavoidable_ in ordered
matchings. A frequent theme in both fields, the theory of ordered graphs as
well as enumerative combinatorics, are unavoidable sub-structures, that is,
_patterns_ that appear in every member of a prescribed family of structures. A
flagship example providing everlasting inspiration is the famous theorem of
Erdős and Szekeres [ErdosSzekeres] on monotone subsequences (see [BKP,
BucicSudakovTran, BukhMatousek, EliasMatousek, FoxPachSudakovSuk,
MoshkovitzShapira, SzaboTardos] for some recent extensions and
generalizations). In its diagonal form it states that any sequence
$x_{1},x_{2},\ldots,x_{n}$ of distinct real numbers contains an increasing or
decreasing subsequence of length at least $\sqrt{n}$.

And, indeed, our first goal is to prove its analog for ordered matchings. The
reason why the original Erdős-Szekeres Theorem lists only two types of
subsequences is, obviously, that for any two elements $x_{i}$ and $x_{j}$ with
$i<j$ there are just two possible relations: $x_{i}<x_{j}$ or $x_{i}>x_{j}$.
For matchings, however, for every two edges $\\{x,y\\}$ and $\\{u,w\\}$ with
$x<y$, $u<w$, and $x<u$, there are three possibilities: $y<u$ , $w<y$, or
$u<y<w$ (see Figure 1.2). In other words, every two edges form either _an
alignment_ , _a nesting_ , or _a crossing_ (the first term introduced by
Kasraoui and Zeng in [KZ], the last two terms coined in by Stanley [Stanley]).
These three possibilities give rise, respectively, to three “unavoidable”
ordered sub-matchings (_lines_ , _stacks_ , and _waves_) which play an
analogous role to the monotone subsequences in the classical Erdős-Szekeres
Theorem. (In [Stanley], stacks and waves consisting of $k$ edges were called,
respectively, _$k$ -nestings_ and _$k$ -crossings_.)

Figure 1.2. An alignment, a nesting, and a crossing of a pair of edges.

Informally, lines, stacks, and waves are defined by demanding that every pair
of edges in a sub-matching forms, respectively, an alignment, a nesting, or a
crossing (see Figure 2.1). In Subsection 2.1 we show, in particular, that
every ordered matching of size $n$ contains one of these structures of size at
least $n^{1/3}$. In the remainder of Section 2, we first extend this result to
3-uniform ordered matchings and then study the size of the largest lines,
stacks, and waves in random matchings.

Our second goal is to estimate the size of the largest (ordered) twins in
ordered matchings. The problem of twins has been widely studied for other
combinatorial structures, including words, permutations, and graphs (see,
e.g., [APP, LLSud]). For an integer $r\geq 2$, we say that $r$ edge-disjoint
(ordered) subgraphs $G_{1},G_{2},\dots,G_{r}$ of an (ordered) graph $G$ form
_(ordered) twins in $G$_ if they are pairwise (order-)isomorphic. The size of
the (ordered) twins is defined as $|E(G_{1})|=\cdots=|E(G_{r})|$. For ordinary
matchings, the notion of $r$-twins becomes trivial, as every matching of size
$n$ contains twins of size $\lfloor n/r\rfloor$ – just split the matching into
$r$ as equal as possible parts. But for ordered matchings the problem becomes
interesting. The above mentioned analog of the Erdős-Szekeres Theorem
immediately yields (again by splitting into $r$ equal parts) ordered $r$-twins
of length $\lfloor n^{1/3}/r\rfloor$. We provide much better estimates on the
size of largest $r$-twins in ordered matchings (Subsection 3.1) and random
matchings (Subsection 3.2) which, not so surprisingly, are of the same order
of magnitude as those for $r$-twins in permutations (see [BukhR, DGR]).

###  1.3. Random matchings

As indicated above, we examine both questions, of unavoidable sub-matchings
and of twins, also for _random_ matchings. A random (ordered) matching
$\mathbb{RM}_{n}$ is selected uniformly at random from all

$\alpha_{n}:=\frac{(2n)!}{n!2^{n}}$

ordered matchings on vertex set $[2n]$. Among other results, we show that with
probability tending to 1, as $n\to\infty$, or _asymptotically almost surely_
(a.a.s.), there are in $\mathbb{RM}_{n}$ lines, stacks, _and_ waves of size,
roughly, $\sqrt{n}$, as well as (ordered) twins of size $\Theta(n^{2/3})$.

There are two other ways of generating $\mathbb{RM}_{n}$ which we are going to
utilize in the proofs. Besides the above defined _uniform_ scheme, we define
the _online_ scheme as follows. For an arbitrary ordering of the vertices
$u_{1},\dots,u_{2n}$ one selects uniformly at random a match, say $u_{j_{1}}$,
for $u_{1}$ (in $2n-1$ ways), then, after crossing out $u_{1}$ and $u_{j_{1}}$
from the list, one selects uniformly at random a match for the first uncrossed
vertex (in $2n-3$ ways), and so on. Note that the total number of ways to
select a matching this way is $(2n-1)(2n-3)\cdot\ldots\cdot 3\cdot 1=(2n-1)!!$
which equals $\alpha_{n}$. A third equivalent way to generate
$\mathbb{RM}_{n}$ is particularly convenient when one intends to apply
concentration inequalities available for random permutations. The _permutation
based_ scheme boils down to just generating a random permutation
$\Pi:=\Pi_{n}$ of $[2n]$ and “chopping it off” into a matching
$\\{\Pi(1)\Pi(2),\;\Pi(3)\Pi(4),\dots,\Pi(2n-1)\Pi(2n)\\}$. Note that this way
each matching corresponds, as it should, to exactly $n!2^{n}$ permutations. We
will stick mostly to the uniform scheme, applying the other two only
occasionally.

###  1.4. Gauss codes

A convenient representation of ordered matchings can be obtained in terms of
_double occurrence words_ over an $n$-letter alphabet, in which every letter
occurs exactly twice as the label of the ends of the corresponding edge in the
matching. For instance, our two exemplary matchings can be written as
$M=ABABCC$ and $N=ABBCAC$ (see Figure 1.3). In fact, this is a special case of
an elementary combinatorial bijection between ordered partitions of a set and
permutations with repetitions. A minor nuisance here is that ordered matchings
correspond to unordered partitions, so every permutation of the letters yields
the same matching. Nevertheless, we will sometimes use this representation to
better illustrate some notions and ideas.

Figure 1.3. Exemplary matchings $M=ABABCC$ and $N=ABBCAC$.

Interestingly, this type of words was introduced and studied already by Gauss
[Gauss] as a way of encoding closed self-intersecting curves on the plane
(with points of multiplicity at most two). Indeed, denoting the self-crossing
points by letters and traversing the curve in a fixed direction gives a
(cyclic) word in which every letter occurs exactly twice (by the multiplicity
assumption) (see Figure 1.4). A general problem studied by Gauss was to
characterize those words that correspond to such curves. He found himself a
necessary condition, but a full solution (in terms of some quite involved
constraints on an auxiliary graph of crossing pairs) was obtained much later
(see [ShtyllaTZ] for a brief history and further references).

It is, perhaps, also worthwhile to mention that ordered matchings constitute a
special case of structures, known as _Puttenham diagrams_ , that found an
early application in the theory of poetry (see [Puttenham, PuttenhamEdited]).
A basic idea is simple: a rhyme scheme of a poem can be encoded by a word in
which same letters correspond to rhyming verses. Of particular interest here
are _planar rhyme schemes_ which are nothing else but ordered matchings
without crossings, or more generally, _noncrossing partitions_ (see
[StanleyCatalan]).

Figure 1.4. A curve with Gauss code $ABCCBDDA$.

##  2\. Unavoidable sub-matchings

Let us start with formal definitions. Let $M$ be an ordered matching on the
vertex set $[2n]$, with edges denoted as $e_{i}=\\{a_{i},b_{i}\\}$ so that
$a_{i}<b_{i}$, for all $i=1,2,\ldots,n$, and $a_{1}<\cdots<a_{n}$. We say that
an edge $e_{i}$ is _to the left of_ $e_{j}$ and write $e_{i}<e_{j}$ if
$a_{i}<a_{j}$. That is, in ordering the edges of a matching we ignore the
positions of the right endpoints.

We now define the three basic types of ordered matchings:

  * •

Line: $a_{1}<b_{1}<a_{2}<b_{2}<\cdots<a_{n}<b_{n}$,

  * •

Stack: $a_{1}<a_{2}<\cdots<a_{n}<b_{n}<b_{n-1}<\cdots<b_{1}$,

  * •

Wave: $a_{1}<a_{2}<\cdots<a_{n}<b_{1}<b_{2}<\cdots<b_{n}$.

Assigning letter $A_{i}$ to edge $\\{a_{i},b_{i}\\}$, their corresponding
double occurrence words look as follows:

  * •

Line: $\quad A_{1}A_{1}A_{2}A_{2}\cdots A_{n}A_{n}$,

  * •

Stack: $A_{1}A_{2}\cdots A_{n-1}A_{n}A_{n}A_{n-1}\cdots A_{1}$.

  * •

Wave: $A_{1}A_{2}\cdots A_{n}A_{1}A_{2}\cdots A_{n}$.

Each of these three types of ordered matchings can be equivalently
characterized as follows. Let us consider all possible ordered matchings with
just two edges. In the double occurrence word notation these are $AABB$
(_aligned_ edges), $ABBA$ (_nesting_ edges), and $ABAB$ (_crossing_ edges).
Now a line, a stack, and a wave is an ordered matching in which _every_ pair
of edges is, respectively, aligned, nesting, and crossing (see Figure 2.1).

Figure 2.1. A line, a stack, and a wave of size three.

###  2.1. In arbitrary matchings

Consider a sub-matching $M^{\prime}$ of $M$ and an edge $e\in M\smallsetminus
M^{\prime}$, which is to the left of the left-most edge $f$ of $M^{\prime}$.
Note that if $M^{\prime}$ is a line and $e$ and $f$ form a line, then
$M^{\prime}\cup\\{e\\}$ is a line too. Similarly, if $M^{\prime}$ is a stack
and $\\{e,f\\}$ form a nesting, then $M^{\prime}\cup\\{e\\}$ is a stack too.
However, an analogous statement fails to be true for waves, as $e$, though
crossing $f$, may not necessarily cross all other edges of the wave
$M^{\prime}$. Due to this observation, in the proof of our first result we
will need another type of ordered matchings combining lines and waves. We call
a matching $M=\\{\\{a_{i},b_{i}\\}:\;i=1,\dots,n\\}$ with $a_{i}<b_{i}$, for
all $i=1,2,\ldots,n$, and $a_{1}<\cdots<a_{n}$, _a landscape_ if
$b_{1}<b_{2}<\cdots<b_{n}$, that is, the right-ends of the edges of $M$ are
also linearly ordered (a first-come-first-serve pattern). Notice that there
are no non-trivial stacks in a landscape. In the double occurrence word
notation, a landscape is just a word obtained by a _shuffle_ of the two copies
of the word $A_{1}A_{2}\cdots A_{n}$. Examples of landscapes for $n=4$ are,
among others,
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{ABCD}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{ABCD}$,
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{A}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{A}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{BC}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{BC}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{D}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{D}$,
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{ABC}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{AB}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{D}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{CD}$
(the last one is depicted in Figure 2.2).

Figure 2.2. A landscape of size four.

The following is an Erdős-Szekeres type result for ordered matchings.

######  Theorem 2.1.

Let $\ell,s,w$ be arbitrary positive integers and let $n=\ell sw+1$. Then,
every ordered matching on $2n$ vertices contains a line of size $\ell+1$, or a
stack of size $s+1$, or a wave of size $w+1$.

###### Proof.

Let $M$ be any ordered matching with edges $\\{a_{i},b_{i}\\}$,
$i=1,2,\ldots,n$. Let $s_{i}$ denote the size of a largest stack whose left-
most edge is $\\{a_{i},b_{i}\\}$. Similarly, let $L_{i}$ be the largest size
of a landscape whose left-most edge is $\\{a_{i},b_{i}\\}$. Consider the
sequence of pairs $(s_{i},L_{i})$, $i=1,2,\ldots,n$. We argue that no two
pairs of this sequence may be equal. Indeed, let $i<j$ and consider the two
edges $\\{a_{i},b_{i}\\}$ and $\\{a_{j},b_{j}\\}$. These two edges may form a
nesting, an alignment, or a crossing. In the first case we get $s_{i}>s_{j}$,
since the edge $\\{a_{i},b_{i}\\}$ enlarges the largest stack starting at
$\\{a_{j},b_{j}\\}$. In the two other cases, we have $L_{i}>L_{j}$ by the same
argument. Since the number of pairs $(s_{i},L_{i})$ is $n>s\cdot\ell w$, it
follows that either $s_{i}>s$ for some $i$, or $L_{j}>\ell w$ for some $j$. In
the first case we are done, as there is a stack of size $s+1$ in $M$.

In the second case, assume that $L$ is a landscape in $M$ of size at least
$p=\ell w+1$. Let us order the edges of $L$ as $e_{1}<e_{2}<\cdots<e_{p}$,
accordingly to the linear order of their left ends. Decompose $L$ into edge-
disjoint waves, $W_{1},W_{2},\ldots,W_{k}$, in the following way. For the
first wave $W_{1}$, pick $e_{1}$ and all edges whose left ends are between the
two ends of $e_{1}$, say, $W_{1}=\\{e_{1}<e_{2}<\ldots<e_{i_{1}}\\}$, for some
$i_{1}\geqslant 1$. Clearly, $W_{1}$ is a true wave since there are no nesting
pairs in $L$. Also notice that the edges $e_{1}$ and $e_{i_{1}+1}$ are non-
crossing since otherwise the latter edge would be included in $W_{1}$. Now, we
may remove the wave $W_{1}$ from $L$ and repeat this step for $L-W_{1}$ to get
the next wave $W_{2}=\\{e_{i_{1}+1}<e_{i_{1}+2}<\ldots<e_{i_{2}}\\}$, for some
$i_{2}\geqslant i_{1}+1$. And so on, until exhausting all edges of $L$, while
forming the last wave
$W_{k}=\\{e_{i_{k-1}+1}<e_{i_{k-1}+2}<\ldots<e_{i_{k}}\\}$, with
$i_{k}\geqslant i_{k-1}+1$. Clearly, the sequence
$e_{1}<e_{i_{1}+1}<\ldots<e_{i_{k-1}+1}$ of the leftmost edges of the waves
$W_{i}$ must form a line (see Figure 2.3).

Figure 2.3. Greedy decomposition of a landscape into waves. The left-most
edges of the waves (in bold) form a line.

So, if $k\geqslant\ell+1$, we are done. Otherwise, we have $k\leqslant\ell$,
and because $p=\ell w+1$, some wave $W_{i}$ must have at least $w+1$ edges.
This completes the proof. ∎

It is not hard to see that the above result is optimal. For example, consider
the case $\ell=5$, $s=3$, $w=4$. Take $3$ copies of the wave of size $w=4$:
$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{ABCDABCD}$,
$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{PQRSPQRS}$,
$\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{XYZTXYZT}$.
Arrange them into a stack-like structure (see Figure 2.4):

$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{ABCD}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{PQRS}\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}{XYZTXYZT}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{PQRS}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{ABCD}.$

Figure 2.4. A stack of waves.

Now, concatenate $\ell=5$ copies of this structure. Clearly, we obtain a
matching of size $\ell sw=5\cdot 3\cdot 4$ with no line of size $6$, no stack
of size $4$, and no wave of size $5$. This example can be easily generalized
to get the following fact.

######  Proposition 2.2.

For every positive integers $\ell,s$ and $w$ there exists a matching of size
$n=\ell sw$ with all lines, waves, and stacks of size at most $\ell,s$ and
$w$, respectively.

By forbidding one of the three basic structures to be present in $M$ and
setting the corresponding parameter, $\ell,s$, or $w$ to 1, we immediately
deduce from Theorem 2.1 that one of the other two structure of an
appropriately large size must be present in $M$. For example, in a landscape
(i.e. no nestings) of size $n\geq\ell w+1$ one can find either a line of size
$\ell+1$ or a wave of size $w+1$. More interestingly, forbidding an alignment
we obtain what we define in Section 3.1 as permutational matchings which are
in a one-to-one correspondence with permutations of order $n$. Moreover, under
this bijection waves and stacks in a permutational matching $M$ correspond to,
respectively, increasing and decreasing subsequences of the permutation which
is the image of $M$. Thus, we recover the original Erdős-Szekeres Theorem as a
special case of our Theorem 2.1.

Finally, we formulate separately the diagonal case of Theorem 2.1.

######  Corollary 2.3.

Every ordered matching on $2n$ vertices contains a line, a stack, or a wave of
size at least $n^{1/3}$.

###### Proof.

Given $n$. Clearly, $\lceil n^{1/3}\rceil-1<n^{1/3}$. Hence, $(\lceil
n^{1/3}\rceil-1)^{3}<n$ and so $(\lceil n^{1/3}\rceil-1)^{3}+1\leq n$.
Applying Theorem 2.1 with $\ell=s=w=\lceil n^{1/3}\rceil-1$ implies one of the
three structures of size $(\lceil n^{1/3}\rceil-1)+1\geq n^{1/3}$. ∎

###  2.2. 3-uniform matchings

It is perhaps natural and interesting to try to generalize Theorem 2.1 to
$r$-uniform ordered matchings, that is, families of $n$ disjoint $r$-element
subsets of the linearly ordered set $[rn]$. Here we make the first step by
showing that the case $r=3$ follows relatively easily from Theorem 2.1 itself.

At the start the problem seems a bit overwhelming, as there are
$\tfrac{1}{2}\binom{6}{3}=10$ different ways in which two triples may
intertwine. Using the _triple occurrence words_ , they are $AAABBB$, $AABABB$,
$AABBBA$, $AABBAB$, $ABBBAA$, $ABBAAB$, $ABBABA$, $ABAABB$, $ABABBA$,
$ABABAB$. What is worse, one of them, $AABABB$, stands out as a culprit who
spoils the otherwise nice picture. To see it through, call an ordered pair of
triples $(e,f)$ _collectable_ if for each $k\geq 1$ there exists a collection
of $k$ triples such that every pair of them is order-isomorphic to the pair
$(e,f)$.

For instance, the relation $AAABBB$, which we may call, as before, _an
alignment_ , is collectable, as for any $k$ one can take
$A_{1}A_{1}A_{1}A_{2}A_{2}A_{2}\dots A_{k}A_{k}A_{k}$. Similarly, for
$AABBBA$, say, one may take $(A_{1}A_{1}A_{2}A_{2}\dots A_{k}A_{k})(A_{k}\dots
A_{2}A_{1})$. In fact, all nine relations but $AABABB$ are collectable.
However, for $AABABB$, which we may call _an engagement_ , one cannot even add
a third triple $CCC$. Indeed, if it were possible, then there should be a $C$
between the second and third $A$, but after the first $B$, which makes the
relation between $B$’s and $C$’s not an engagement, as it would begin with
$BC$. (Here we assumed w.l.o.g. that the first $A$ precedes the first $B$
which precedes the first $C$.)

Due to this annoying exception, the Erdős-Szekeres type result we are going to
prove is not as clean as its predecessors for singletons and pairs. For
reasons, which will become clear once we reveal our proof strategy, we “give
names to all the animals” as presented in the first two columns of Table 1.
(Warning: from now on the letters $\ell,s,w$, unlike in the previous
subsection, are just mnemonic symbols, not numbers.)

relation | in words | operation $\oplus$
---|---|---
${\mathcal{R}}_{\ell,\ell}$ | $AAABBB$ | $AABB\oplus AABB=\underline{A}\overline{\underline{A}}\overline{A}\underline{B}\overline{\underline{B}}\overline{B}$
${\mathcal{R}}^{*}_{\ell,\ell}$ | $AABABB$ | $AABB\oplus AABB=\underline{A}\underline{\overline{A}}\underline{B}\overline{A}\underline{\overline{B}}\overline{B}$
${\mathcal{R}}_{\ell,s}$ | $AABBBA$ | $AABB\oplus ABBA=\underline{A}\overline{\underline{A}}\underline{B}\overline{\underline{B}}\overline{B}\overline{A}$
${\mathcal{R}}_{\ell,w}$ | $AABBAB$ | $AABB\oplus ABAB=\underline{A}\overline{\underline{A}}\underline{B}\overline{\underline{B}}\overline{A}\overline{B}$
${\mathcal{R}}_{s,\ell}$ | $ABBBAA$ | $ABBA\oplus BBAA=\underline{A}\underline{B}\overline{\underline{B}}\overline{B}\overline{\underline{A}}\overline{A}$
${\mathcal{R}}_{s,s}$ | $ABBAAB$ | $ABBA\oplus BAAB=\underline{A}\underline{B}\overline{\underline{B}}\overline{\underline{A}}\overline{A}\overline{B}$
${\mathcal{R}}_{s,w}$ | $ABBABA$ | $ABBA\oplus BABA=\underline{A}\underline{B}\overline{\underline{B}}\overline{\underline{A}}\overline{B}\overline{A}$
${\mathcal{R}}_{w,\ell}$ | $ABAABB$ | $ABAB\oplus AABB=\underline{A}\underline{B}\overline{\underline{A}}\overline{A}\overline{\underline{B}}\overline{B}$
${\mathcal{R}}_{w,s}$ | $ABABBA$ | $ABAB\oplus ABBA=\underline{A}\underline{B}\underline{\overline{A}}\underline{\overline{B}}\overline{B}\overline{A}$
${\mathcal{R}}_{w,w}$ | $ABABAB$ | $ABAB\oplus ABAB=\underline{A}\underline{B}\underline{\overline{A}}\underline{\overline{B}}\overline{A}\overline{B}$
Table 1. Possible relations of two triples and their corresponding
decompositions via operation $\oplus$.

To cope with engagements, we will “merry” them with alignments by combining
relations ${\mathcal{R}}_{\ell,\ell}$ and ${\mathcal{R}}^{*}_{\ell,\ell}$
together. First, as in the case of pairs, define _a line_ as an ordered
3-uniform matching $M$ such that all pairs of triples of $M$ are in relation
${\mathcal{R}}_{\ell,\ell}$, that is, each pair forms an alignment. Call $M$
_a semi-line_ if all pairs of triples are in either relation
${\mathcal{R}}_{\ell,\ell}$ or ${\mathcal{R}}^{*}_{\ell,\ell}$, that is, they
form an alignment or an engagement.

######  Proposition 2.4.

Every semi-line of size $k$ contains a line of size at least $k/2$.

###### Proof.

Let $e_{1},\dots,e_{k}$ be a semi-line. Define an auxiliary graph $G$ on
vertex set $[k]$ where $ij\in E(G)$ if $e_{i}$ and $e_{j}$ form an engagement.
It turns out that $G$ is a linear forest. To prove it, assume w.l.o.g. that
for all $i<j$ the left-most vertex of $e_{i}$ is to the left of the left-most
vertex of $e_{j}$. We claim that every vertex $i$ has at most one neighbor
$j>i$. Indeed, if there were edges $ij$ and $ih$, $i<j<h$, then, identifying
$e_{i},e_{j}$ and $e_{h}$, respectively, with letters $A,B$ and $C$, we would
have a sequence $AABCA\dots$, where the last 4 positions are occupied by 2
letters $B$ and 2 letters $C$ in an arbitrary order. This means, however, that
$B$’s and $C$’s, or equivalently $e_{j}$ and $e_{h}$, form neither an
alignment nor an engagement, a contradiction with the definition of a semi-
line. By symmetry, any vertex $i$ has also at most one neighbor $j<i$. So, $G$
is, indeed, a linear forest and as such has an independent number at least
$k/2$. This completes the proof. ∎

We are now ready to formulate an Erdős-Szekeres type result for 3-uniform
matchings.

######  Theorem 2.5.

Let $a_{xy}$, where $x,y\in\\{\ell,s,w\\}$, be arbitrary positive integers and
let

$n=\prod_{x,y}a_{xy}+1.$

Then, every ordered 3-uniform matching $M$ on $3n$ vertices either contains a
semi-line of size $a_{\ell\ell}+1$, or there exists $(x,y)\neq(\ell,\ell)$
such that $M$ contains a sub-matching of $a_{xy}+1$ triples every two of which
are in relation ${\mathcal{R}}_{x,y}$ (as defined in Table 1).

######  Remark 2.6.

As in Corollary 2.3 one can show that every 3-uniform ordered matching of size
$n$ contains one of the nine collectable sub-structures listed in Theorem 2.5
of size at least $n^{1/9}$.

######  Remark 2.7.

At the moment we are not able to find a construction showing optimality of
Theorem 2.5. It was relatively easy in the graph case, as both, stacks and
waves, had the _interval_ chromatic number equal to 2, which enabled one to
superimpose one into another by blowing up the vertices of one of them and
filling its edges with copies of the other (see Figure 2.4 for the
superimposition of a wave of size 4 upon a stack of size 3). Following, e.g.,
[FJKMV], we say that an ordered $r$-uniform hypergraph has _interval chromatic
number $r$_ if it is $r$-partite with the partition sets forming consecutive
blocks of the linearly ordered vertex set.

Now, out of the eight 3-uniform relations, alignments and engagements aside,
only four have interval chromatic number $3$, namely those not having $\ell$
within their indices: ${\mathcal{R}}_{s,s}=ABBAAB$,
${\mathcal{R}}_{s,w}=ABBABA$, ${\mathcal{R}}_{w,s}=ABABBA$, and
${\mathcal{R}}_{w,w}=ABABAB$. Thus, we can provide a counterexample showing
optimality of Theorem 2.5 only in the special case when
$a_{\ell,s}=a_{\ell,w}=a_{s,\ell}=a_{w,\ell}=1$. We do so by superimposing the
four “no-$\ell$” relations and then taking $a_{\ell,\ell}$ disjoint copies of
the obtained construction. The superimposition is done by carefully replacing
each triple of the current matching with a matching obeying mutually the new
relation. E.g., replacing $XYXYXY$ (relation ${\mathcal{R}}_{w,w}$) with
$WZ\;UV\;WZ\;UV\;ZW\;VU$ results in a matching where four pairs of triples
retain relation ${\mathcal{R}}_{w,w}$, while two pairs ($W-Z$ and $U-V$) enjoy
the new relation ${\mathcal{R}}_{w,s}$. It is crucial here that consecutive
blocks of size 2 in $WZ\;WZ\;ZW$ each contain both letters $W$ and $Z$, which
is equivalent to having interval chromatic number $3$.

For the case when $a_{s,s}=a_{s,w}=a_{w,s}=a_{w,w}=2$ (and all other
parameters set to 1) see Figure 2.5, where the pairwise relations between all
16 triples can be described as follows. Let us first focus on the 8 triples
drawn with solid colored lines ($A,\dots,H$). Among them, all 4 monochromatic
pairs of triples (like $A-B$) are in relation ${\mathcal{R}}_{s,s}$, the 8
red-blue and orange-green pairs of triples (like $A-C$) obey relation
${\mathcal{R}}_{s,w}$, while the remaining 16 pairs (like $A-E$) satisfy
relation ${\mathcal{R}}_{w,s}$. The very same is true for the 8 triples drawn
with dashed colored lines ($I,\dots,P$). Finally, each solid-dashed pair (like
$A-I$) satisfies relation ${\mathcal{R}}_{w,w}$. Note that, viewing this
construction as a complete graph $K_{16}$, each relation corresponds to a
bipartite subgraph, and so, crucially, no three triples are mutually in the
same relation.

Figure 2.5. A matching of $2^{4}=16$ triples illustrating optimality of
Theorem 2.5 with $a_{s,s}=a_{s,w}=a_{w,s}=a_{w,w}=2$ (and all other parameters
set to 1).

######  Remark 2.8.

As in the case of graph matchings it is impossible to employ directly the
original Erdős-Szekeres proof idea. To see this, call a relation
${\mathcal{R}}$ _extendable_ if, given a collection $M$ of disjoint triples
which are mutually in relation ${\mathcal{R}}$, every triple to the left of
$M$ which is in relation ${\mathcal{R}}$ with the left-most triple of $M$, is
in relation ${\mathcal{R}}$ with all triples in $M$. For graphs, lines and
stacks were extendable, while waves were not, which forced us to come up with
the notion of a landscape. Now, only ${\mathcal{R}}_{\ell,\ell}$,
${\mathcal{R}}_{\ell,s}$, ${\mathcal{R}}_{s,w}$, and ${\mathcal{R}}_{s,\ell}$
are extendable, so any direct proof of Theorem 2.5 would require more
sophisticated analogs of landscapes. Fortunately, we deduce Theorem 2.5
directly from Theorem 2.1.

###### Proof of Theorem 2.5.

Let $M$ be a matching (of triples) as in the assumptions of the theorem. Our
proof strategy is to apply Theorem 2.1 twice, first to the (graph) matching
$M_{1}$ composed of pairs consisting of the first two elements of the triples
in $M$, then to a suitably chosen sub-matching of the (graph) matching $M_{1}$
composed of pairs of the last two elements of the triples in $M$.

Set $b_{\ell}=a_{\ell,\ell}a_{\ell,s}a_{\ell,w}$,
$b_{s}=a_{s,\ell}a_{s,s}a_{s,w}$, and $b_{w}=a_{w,\ell}a_{w,s}a_{w,w}$ and
apply Theorem 2.1 to $M_{1}$ with $\ell:=b_{\ell}$, $s:=b_{s}$, and
$w:=b_{w}$. We will now examine the three alternatives of the conclusion.

Case $\ell$. $M_{1}$ contains a (graph) line $L$ of size $b_{\ell}+1$. Let
$M_{L}$ be the sub-matching of $M_{2}$ composed of pairs of the last two
elements of those triples in $M$ whose first two elements form a pair
belonging to $L$. Formally,

$M_{L}=\\{\\{j,k\\}:\;i<j<k,\;\\{i,j,k\\}\in
M,\quad\mbox{and}\quad\\{i,j\\}\in L\\}.$

We apply Theorem 2.1 to $M_{L}$ with $\ell:=a_{\ell,\ell}$, $s:=a_{\ell,s}$,
and $w:=a_{\ell,w}$ and examine the three possible outcomes.

Subcase $(\ell,\ell)$. $M_{L}$ contains a line Ł of size $a_{\ell,\ell}+1$.
This is the troublesome case. Let $M_{\ell,\ell}$ be the sub-matching of $M$
consisting of all triples in $M$ whose first pair of elements belongs to $L$,
while the last pair belongs to Ł. Consider any two triples in $M_{\ell,\ell}$.
There are two possible relations they may be in: the alignment
$\underline{A}\overline{\underline{A}}\overline{A}\underline{B}\overline{\underline{B}}\overline{B}$
and the engagement
$\underline{A}\underline{\overline{A}}\underline{B}\overline{A}\underline{\overline{B}}\overline{B}$.
Indeed, in both cases the first pairs and the last pairs, underlined and
overlined, resp., form (graph) alignments. This shows that $M_{\ell,\ell}$ is
a semi-line.

Subcase $(\ell,s)$. $M_{L}$ contains a stack ${S}$ of size $a_{\ell,s}+1$. Let
$M_{\ell,s}$ be the sub-matching of $M$ consisting of all triples in $M$ whose
first pair of elements belongs to $L$, while the last pair belongs to ${S}$.
Consider any two triples in $M_{\ell,s}$. Then they necessarily are in
relation ${\mathcal{R}}_{\ell,s}$, that is, they form the word
$\underline{A}\overline{\underline{A}}\underline{B}\overline{\underline{B}}\overline{B}\overline{A}$.

Subcase $(\ell,w)$. $M_{L}$ contains a wave ${W}$ of size $a_{\ell,w}+1$. Let
$M_{\ell,w}$ be the sub-matching of $M$ consisting of all triples in $M$ whose
first pair of elements belongs to $L$, while the last pair belongs to ${W}$.
Consider any two triples in $M_{\ell,w}$. Then they necessarily are in
relation ${\mathcal{R}}_{\ell,w}$, that is, they form the word
$\underline{A}\overline{\underline{A}}\underline{B}\overline{\underline{B}}\overline{A}\overline{B}$.

Cases $s$ and $w$. Each case splits further, as before, into three subcases.
It is straightforward to check that these altogether six subcases lead to the
remaining six relations ${\mathcal{R}}_{s,\ell}$, ${\mathcal{R}}_{s,s}$,
${\mathcal{R}}_{s,w}$, ${\mathcal{R}}_{w,\ell}$, ${\mathcal{R}}_{w,s}$,
${\mathcal{R}}_{w,w}$, yielding each time the required size of the collection.

The meaning of the subscripts now becomes evident. It turns out that each of
the ten 3-uniform relations can be obtained by the operation $\oplus$ of
merging two of the three graph relations, lines, stacks, and waves, in the way
described above. This mapping is 1-1 except for the alignment and the
engagement which both are possible images of the pair of graph lines. The last
column of Table 1 displays this mapping using, again, the words with
underlined and overlined letters. The three relations with first subscript $s$
differ in that the letters in the second argument of the operation $\oplus$
are reversed; indeed, if the pairs of the first two elements of two triples
form the sequence $ABBA$, then the pairs of the last two elements can only
form sequences $BBAA,BABA$, or $BAAB$. ∎

###  2.3. In random matchings

In this section we shall investigate the size of unavoidable structures one
can find in _random_ ordered matchings with the emphasis on the three
canonical patterns: lines, stacks, and waves. Recall that $\mathbb{RM}_{n}$ is
a random (ordered) matching of size $n$, that is, a matching picked uniformly
at random out of the set of all $\alpha_{n}:=(2n)!/(n!2^{n})$ matchings on the
set $[2n]$.

Stanley in [Stanley] determined the asymptotic distribution of the maximum
size of two of the three canonical patterns contained in a random ordered
matching. As a consequence, their values can be pinpointed very precisely.

######  Theorem 2.9 (Theorem 17 in [Stanley]).

The sizes of the largest stack and the largest wave contained in
$\mathbb{RM}_{n}$ are a.a.s. equal to $(1+o(1))\sqrt{2n}$.

We are going to prove that the maximum size of a line in $\mathbb{RM}_{n}$ is
a.a.s. also of the order of magnitude of $\sqrt{n}$. In addition, we provide a
simple proof of a weaker version of Theorem 2.9, with the coefficient
$\sqrt{2}$ replaced by a pair of constants, roughly $1/(e\sqrt{2})$ and
$e/\sqrt{2}$, setting a lower and upper bound only. The proof of the upper
bound is quite straightforward and provides a more general result.

######  Proposition 2.10.

Let $(M_{k})_{1}^{\infty}$ be a sequence of ordered matchings of size $k$,
$k=1,2,\dots$. Then, a.a.s.

$\max\\{k:\;M_{k}\preceq\mathbb{RM}_{n}\\}\leq(1+o(1))e\sqrt{n/2}.$

###### Proof.

Set $k_{0}=\lfloor\left(1+n^{-1/3}\right)e\sqrt{n/2}\rfloor$, and let $X_{k}$
be a random variable counting the number of ordered copies of $M_{k}$ in
$\mathbb{RM}_{n}$. Our goal is to show, via the first moment method, that
a.a.s. $X_{k}=0$ for all $k\geq k_{0}$. Note that it is _not_ enough to show
that a.a.s. $X_{k_{0}}=0$, as the sequence $(M_{k})_{1}^{\infty}$ may not be
ascending.

To compute the expectation of $X_{k}$, one has to first choose the $2k$
vertices of a copy of $M_{k}$ (the copy itself is placed in just one way),
then count the number of extensions of that copy to an entire matching of size
$n$, and, finally, divide by the total number of matchings. Thus,

${\mathds{E}}X_{k}=\binom{2n}{2k}\cdot
1\cdot\frac{\alpha_{n-k}}{\alpha_{n}}=\frac{2^{k}}{(2k)!}\cdot\frac{n!}{(n-k)!}\leq\frac{2^{k}}{(2k)!}\cdot
n^{k}\leq\frac{2^{k}}{(2k/e)^{2k}}\cdot
n^{k}=\left(\frac{e^{2}n}{2k^{2}}\right)^{k},$

and, by the union bound applied together with Markov’s inequality,

$\displaystyle\Pr(\exists k\geq k_{0}:\;X_{k}>0)$
$\displaystyle\leq\sum_{k=k_{0}}^{n}\Pr(X_{k}\geq 1)$
$\displaystyle\leq\sum_{k=k_{0}}^{n}{\mathds{E}}X_{k}\leq\sum_{k=k_{0}}^{n}\left(\frac{e^{2}n}{2k^{2}}\right)^{k}\leq
n(1+n^{-1/3})^{-2k_{0}}=o(1).$

∎

Owing to the very homogeneous structure of lines, stacks, and waves, we are
able to establish corresponding lower bounds for their maximum sizes in
$\mathbb{RM}_{n}$. It is, perhaps, interesting to note that, unlike for
permutations, the size of the sub-structures guaranteed by the of Erdős-
Szekeres-type result (cf. Corollary 2.3) grows substantially in the random
setting.

######  Theorem 2.11.

A random matching $\mathbb{RM}_{n}$ contains a.a.s. stacks and waves of size
at least $\tfrac{1-o(1)}{e\sqrt{2}}\sqrt{n}$ each, as well as lines of size at
least $\tfrac{1}{8}\sqrt{n}$.

The proof for stacks and waves is very simple and relies mostly on Theorem
2.1. For lines we will make use of the following lemma which might be of some
independent interest. For that reason we state it in a more general setting
than what we actually need. The _length_ of an edge $\\{i,j\\}$ in a matching
on $[2n]$ is defined as $|j-i|$.

######  Lemma 2.12.

Let a sequence $m=m(n)$ be such that $m\to\infty$ and $m=o(n)$. Then, a.a.s.
the number of edges of length at most $m$ in $\mathbb{RM}_{n}$ is $m(1+o(1))$.

###### Proof.

For each pair of vertices $1\leq u<v\leq 2n$, let $X_{uv}$ be the indicator
random variable equal to one if $\\{u,v\\}\in\mathbb{RM}_{n}$ and 0 otherwise.
Clearly, $\Pr(X_{uv}=1)=1/(2n-1)$. The sum $X=\sum_{1\leq v-u\leq m}X_{uv}$
counts all edges in $\mathbb{RM}_{n}$ of length at most $m$. As the number of
summands is $(2n-1)+(2n-2)+\dots+(2n-m)=2nm-\binom{m+1}{2}$, we have

${\mathds{E}}X=\frac{2nm-\binom{m+1}{2}}{2n-1}=m(1-O(m/n)).$

In particular, by the assumptions on $m$, ${\mathds{E}}X=m(1-o(1))\to\infty$.
To estimate the second moment, observe that

$\Pr(X_{u_{1}v_{1}}=X_{u_{2}v_{2}}=1)=\begin{cases}\frac{1}{(2n-1)(2n-3)},&\text{
if }\\{u_{1},v_{1}\\}\cap\\{u_{2},v_{2}\\}=\varnothing,\\\ 0,&\text{
otherwise}.\end{cases}$

Hence, estimating quite crudely,

${\mathds{E}}(X(X-1))\leq\frac{\left(2nm-\binom{m+1}{2}\right)^{2}}{(2n-1)(2n-3)},$

and consequently, by Chebyshev’s inequality

$\displaystyle\Pr(|X-{\mathds{E}}X|\geq\varepsilon{\mathds{E}}X)\leq\frac{{\mathds{E}}(X(X-1))+{\mathds{E}}X-({\mathds{E}}X)^{2}}{\varepsilon^{2}({\mathds{E}}X)^{2}}$
$\displaystyle\qquad\qquad\leq\frac{1}{\varepsilon^{2}}\left(\frac{(2n-1)^{2}}{(2n-1)(2n-3)}+\frac{1}{{\mathds{E}}X}-1\right)=\frac{1}{\varepsilon^{2}}\left(\frac{2}{2n-3}+\frac{1}{{\mathds{E}}X}\right)\to
0,$

provided that $\varepsilon^{2}m\to\infty$. This implies that a.a.s.
$1-\varepsilon-m/(2n)<X/m\leq 1+\varepsilon$. ∎

###### Proof of Theorem 2.11.

We split the proof into two uneven parts.

Stacks and waves: Fix $\varepsilon>0$ and choose $\varepsilon^{\prime}>0$ such
that $\tfrac{1-2\varepsilon^{\prime}}{1+\varepsilon^{\prime}}=1-\varepsilon$.
Let $M$ be the sub-matching of $\mathbb{RM}_{n}$ consisting of all edges with
one end in $[n]$ and the other in $[2n]\smallsetminus[n]$. Set $X:=|M|$. We
have ${\mathds{E}}X=n^{2}/(2n-1)\sim n/2$ and

${\mathds{E}}(X(X-1))=\frac{n^{2}(n-1)^{2}}{(2n-1)(2n-3)}\sim({\mathds{E}}X)^{2},$

so, using Chebyshev’s inequality, it follows that a.a.s. $|X-n/2|=o(n)$.

Observe that there are no lines in $M$ longer than 1. By Proposition 2.10,
a.a.s. there are no stacks or waves in $\mathbb{RM}_{n}$ of size
$k_{0}=\lfloor(1+o(1))e\sqrt{n/2}\rfloor$. Hence, by applying Theorem 2.1 to
$M$ with $\ell=1$, $s=k_{0}-1$, and $w=\lfloor\tfrac{X-1}{k_{0}-1}\rfloor$, we
conclude that a.a.s. there is a wave in $M$, and thus in $\mathbb{RM}_{n}$, of
size at least

$w+1=\frac{1-o(1)}{e\sqrt{2}}\sqrt{n}.$

By swapping the roles of waves and stacks in the above argument, we deduce
that a.a.s. there is also a stack in $M$, and thus in $\mathbb{RM}_{n}$, of
size $\frac{1-o(1)}{e\sqrt{2}}\sqrt{n}$.

Lines: Let $m=\lfloor\sqrt{n}/2\rfloor$. By Lemma 2.12, a.a.s. the number of
edges of length at most $m$ in $\mathbb{RM}_{n}$ is at least $\sqrt{n}/4$. We
will show that among the edges of length at most $k$, there are a.a.s. at most
$\sqrt{n}/8$ pairs forming crossings or nestings. After removing one edge from
each crossing and nesting we obtain a line of size at least
$\sqrt{n}/4-\sqrt{n}/8=\sqrt{n}/8$.

For a 4-element subset $S=\\{u_{1},u_{2},v_{1},v_{2}\\}\subset[2n]$ with
$u_{1}<v_{1}<u_{2}<v_{2}$, let $X_{S}$ be an indicator random variable equal
to $1$ if both $\\{u_{1},u_{2}\\}\in\mathbb{RM}_{n}$ and
$\\{v_{1},v_{2}\\}\in\mathbb{RM}_{n}$, that is, if $S$ spans a crossing in
$\mathbb{RM}_{n}$. Clearly,

$\Pr(X_{S}=1)=\frac{1}{(2n-1)(2n-3)}.$

Let $X=\sum X_{S}$, where the summation is taken over all sets $S$ as above
and such that $u_{2}-u_{1}\leq m$ and $v_{2}-v_{1}\leq m$. Note that this
implies that $v_{1}-u_{1}\leq m-1$. Let $f(n,m)$ denote the number of terms in
this sum. We have

$f(n,m)\leq\left(2n(m-1)-\binom{m}{2}\right)\binom{m}{2}\leq\left(nm-\frac{1}{2}\binom{m}{2}\right)m^{2},$

as we have at most $2n(m-1)-\binom{m}{2}$ choices for $u_{1}$ and $v_{1}$ (see
the proof of Lemma 2.12 with $m$ replaced by $m-1$) and, once $u_{1},v_{1}$
have been selected, at most $\binom{m}{2}$ choices of $u_{2}$, and $v_{2}$. It
is easy to see that $f(n,m)=\Omega(nm^{3})$. (In fact, one could show that
$f(n,m)\sim\tfrac{2}{3}nm^{3}$, but we do not care about optimal constants
here.) Hence, ${\mathds{E}}X=\Omega(m^{3}/n)\to\infty$, while

${\mathds{E}}X=\sum_{S}{\mathds{E}}X_{S}=\frac{f(n,m)}{(2n-1)(2n-3)}\leq\frac{m^{3}}{4n}=\frac{1}{32}\sqrt{n}.$

To apply Chebyshev’s inequality, we need to estimate ${\mathds{E}}(X(X-1))$,
which can be written as

${\mathds{E}}(X(X-1))=\sum_{S,S^{\prime}}\Pr\left(\\{\\{u_{1},v_{1}\\},\\{u_{2},v_{2}\\},\\{u_{1}^{\prime},v_{1}^{\prime}\\},\\{u_{2}^{\prime},v_{2}^{\prime}\\}\\}\subset\mathbb{RM}_{n}\right),$

where the summation is taken over all (ordered) pairs of sets
$S=\\{u_{1},u_{2},v_{1},v_{2}\\}\subset[2n]$ with $u_{1}<v_{1}<u_{2}<v_{2}$
and
$S^{\prime}=\\{u^{\prime}_{1},u^{\prime}_{2},v^{\prime}_{1},v^{\prime}_{2}\\}\subset[2n]$
with $u^{\prime}_{1}<v^{\prime}_{1}<u^{\prime}_{2}<v^{\prime}_{2}$ such that
$u_{2}-u_{1}\leq m$, $v_{2}-v_{1}\leq m$, $u^{\prime}_{2}-u^{\prime}_{1}\leq
m$, and $v^{\prime}_{2}-v^{\prime}_{1}\leq m$. We split the above sum into two
sub-sums $\Sigma_{1}$ and $\Sigma_{2}$ according to whether $S\cap
S^{\prime}=\varnothing$ or $|S\cap S^{\prime}|=2$ (for all other options the
above probability is zero). In the former case,

$\Sigma_{1}\leq\frac{f(n,m)^{2}}{(2n-1)(2n-3)(2n-5)(2n-7)}=({\mathds{E}}X)^{2}(1+O(1/n)).$

In the latter case, the number of such pairs $(S,S^{\prime})$ is at most
$f(n,m)\cdot 4m^{2}$, as given $S$, there are four ways to select the common
pair and at most $m^{2}$ ways to select the remaining two vertices of
$S^{\prime}$. Thus,

$\Sigma_{2}\leq\frac{f(n,m)\cdot
4m^{2}}{(2n-1)(2n-3)(2n-5)}=O(m^{5}/n^{2})=O(\sqrt{n})$

and, altogether,

${\mathds{E}}(X(X-1))\leq({\mathds{E}}X)^{2}(1+O(1/n))+O(\sqrt{n})=({\mathds{E}}X)^{2}+O(\sqrt{n}).$

By Chebyshev’s inequality,

$\displaystyle\Pr(|X-{\mathds{E}}X|\geq{\mathds{E}}X)$
$\displaystyle\leq\frac{{\mathds{E}}(X(X-1))+{\mathds{E}}X-({\mathds{E}}X)^{2}}{({\mathds{E}}X)^{2}}$
$\displaystyle\leq 1+O(1/\sqrt{n})+\frac{1}{{\mathds{E}}X}-1=O(1/\sqrt{n})\to
0.$

Thus, a.a.s. $X\leq 2{\mathds{E}}X\leq\sqrt{n}/16$.

We deal with nestings in a similar way. For a 4-element subset
$S=\\{u_{1},u_{2},v_{1},v_{2}\\}\subset[2n]$ with $u_{1}<v_{1}<v_{2}<u_{2}$,
let $Y_{S}$ be an indicator random variable equal to $1$ if both
$\\{u_{1},u_{2}\\}\in\mathbb{RM}_{n}$ and
$\\{v_{1},v_{2}\\}\in\mathbb{RM}_{n}$, that is, if $S$ spans a nesting in
$\mathbb{RM}_{n}$. Further, let $Y=\sum Y_{S}$, where the summation is taken
over all sets $S$ as above and such that $u_{2}-u_{1}\leq m$ and
(consequently) $v_{2}-v_{1}\leq m-2$. It is crucial to observe that, again,
${\mathds{E}}Y\leq m^{3}/n=\sqrt{n}/32$. Indeed, this time there are at most
$2nm-\binom{m+1}{2}$ choices for $u_{1}$ and $u_{2}$ and, once $u_{1},u_{2}$
have been selected, at most $\binom{m-2}{2}$ choices of $v_{1}$, and $v_{2}$,
while the probability of both pairs appearing in $\mathbb{RM}_{n}$ remains the
same as before. The remainder of the proof goes mutatis mutandis.

We conclude that a.a.s. the number of crossings and nestings of length at most
$m$ in $\mathbb{RM}_{n}$ is at most $\sqrt{n}/8$ as was required. ∎

We close this section with a straightforward generalization of Proposition
2.10 to random $r$-uniform ordered matchings, $r\geq 2$. Let
$\mathbb{RM}^{(r)}_{n}$ be a random (ordered) $r$-matching of size $n$, that
is, a matching picked uniformly at random out of the set of all
$\alpha^{(r)}_{n}:=(rn)!/(n!(r!)^{n})$ matchings on the set $[rn]$.

######  Proposition 2.13.

Let $(M^{(r)}_{k})_{1}^{\infty}$ be a sequence of ordered $r$-matchings of
size $k$, $k=1,2,\dots$. Then, a.a.s.

$\max\\{k:\;M^{(r)}_{k}\preceq\mathbb{RM}^{(r)}_{n}\\}\leq(1+o(1))\frac{e}{r}(r!n)^{1/r}.$

###### Proof.

Let $k_{0}=\lfloor(1+n^{-1/(r+1)})\frac{e}{r}(r!n)^{1/r}\rfloor$ and, for each
$k\geq k_{0}$, let $X^{(r)}_{k}$ be the number of ordered copies of
$M^{(r)}_{k}$ of size $k$ in $\mathbb{RM}^{(r)}_{n}$. Then

${\mathds{E}}X^{(r)}_{k}=\binom{rn}{rk}\cdot
1\cdot\frac{\alpha^{(r)}_{n-k}}{\alpha^{(r)}_{n}}=\frac{(r!)^{k}}{(rk)!}\cdot\frac{n!}{(n-k)!}\leq\frac{(r!)^{k}}{(rk)!}\cdot
n^{k}\leq\frac{(r!)^{k}}{(rk/e)^{rk}}\cdot
n^{k}=\left(\frac{e^{r}r!n}{(rk)^{r}}\right)^{k},$

which implies that

$\Pr(\exists k\geq
k_{0}:\;X^{(r)}_{k}>0)\leq\sum_{k=k_{0}}^{n}\left(\frac{e^{r}r!n}{(rk)^{r}}\right)^{k}\leq
n(1+n^{-1/(r+1)})^{-rk_{0}}=o(1).$

∎

In particular, the above statement yields that in $\mathbb{RM}^{(3)}_{n}$
a.a.s. none of the nine collectable sub-matchings (as defined in Subsection
2.2) has size bigger than $2n^{1/3}$. It is, at the moment, an open problem to
match it with a fair lower bound (see discussion in Section 4).

##  3\. Twins

Recall that for $r\geq 2$, by _$r$ -twins_ in a matching $M$ we mean any
collection of disjoint, pairwise order-isomorphic sub-matchings
$M_{1},M_{2},\dots,M_{r}$. For instance, the matching $M=AABCDDEBCFGHIHEGFI$
contains $3$-twins formed by the triple
$M_{1}=\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{BDDB}$,
$M_{2}=\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@cmyk@stroke{0}{1}{1}{0}\pgfsys@color@cmyk@fill{0}{1}{1}{0}{EHHE}$,
and
$M_{3}=\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color<EMAIL_ADDRESS>(see Figure 3.1).

Recall also that by the _size_ of $r$-twins we mean the size (the number of
edges) in just one of them. Let $t_{r}(M)$ denote the maximum size of
$r$-twins in a matching $M$ and $t_{r}^{\operatorname{match}}(n)$ – the
minimum of $t_{r}(M)$ over all matchings $M$ on $[2n]$.

Figure 3.1. 3-twins of size two.

###  3.1. In arbitrary matchings

Let us first point to a direct connection between twins in permutations and
ordered twins in a certain kind of matchings. By a _permutation_ we mean any
finite sequence of pairwise distinct positive integers. We say that two
permutations $(x_{1},\dots,x_{k})$ and $(y_{1},\dots,y_{k})$ are _similar_ if
their entries preserve the same relative order, that is, $x_{i}<x_{j}$ if and
only if $y_{i}<y_{j}$ for all $1\leqslant i<j\leqslant k$. For $r\geq 2$, any
$r$ pairwise similar and disjoint sub-permutations of a permutation $\pi$ are
called _$r$ -twins_. For example, in permutation

$(6,\hbox{\pagecolor{cyan}1},\hbox{\pagecolor{cyan}4},7,\hbox{\pagecolor{Lavender}3},9,\hbox{\pagecolor{Lavender}8},\hbox{\pagecolor{cyan}2},\hbox{\pagecolor{Lavender}5}),$

the red and blue subsequences form a pair of twins, or 2-twins, of length $3$,
both similar to the permutation $(1,3,2)$.

Let $t_{r}(\pi)$ denote the maximum length of $r$-twins in a permutation $\pi$
and $t_{r}^{\operatorname{perm}}(n)$ – the minimum of $t_{r}(\pi)$ over all
permutations $\pi$ of $[n]$. Gawron [Gawron] proved that $t_{2}(n)\leqslant
cn^{2/3}$ for some constant $c>0$. This was easily generalized to
$t_{r}(n)\leqslant c_{r}n^{r/(2r-1)}$ (see [DGR]).

As for a lower bound, notice that by the Erdős-Szekeres Theorem, we have
$t_{r}^{\operatorname{perm}}(n)\geqslant\left\lfloor\frac{1}{r}n^{1/2}\right\rfloor$.
For $r=2$, this bound was substantially improved by Bukh and Rudenko [BukhR].

######  Theorem 3.1 (Bukh and Rudenko [BukhR]).

For all $n$, $t_{2}^{\operatorname{perm}}(n)\geqslant\frac{1}{8}n^{3/5}$.

Using their approach, in [DGR1], we generalized this bound to arbitrary $r\geq
2$.

######  Theorem 3.2 ([DGR1]).

For all $n$,
$t_{r}^{\operatorname{perm}}(n)\geqslant\frac{1}{3r}n^{\frac{R}{2R-1}}$, where
$R=\binom{2r-1}{r}$.

We call an ordered matching $M$ on the set $[2n]$ _permutational_ if the left
end of each edge of $M$ lies in the set $[n]$ (and so, the right end of each
edge lies in $[n+1,2n]$. In the double occurrence word notation such a
matching can be written as $M=A_{1}A_{2}\ldots A_{n}A_{i_{1}}A_{i_{2}}\ldots
A_{i_{n}}$, where $\pi_{M}=(i_{1},i_{2},\ldots,i_{n})$ is a permutation of
$[n]$. There are only $n!$ permutational matchings, nevertheless this
connection to permutations turned out to be quite fruitful. Indeed, it is not
hard to see that ordered $r$-twins in a permutational matching $M$ are in one-
to-one correspondence with $r$-twins in $\pi_{M}$. In particular, we have
$t_{r}(M)=t_{r}(\pi_{M})$ for such matchings and, consequently,
$t_{r}^{\operatorname{match}}(n)\leq t_{r}^{\operatorname{perm}}(n)$. In
particular, by the above mentioned result of Gawron,
$t_{2}^{\operatorname{match}}(n)=O(n^{2/3})$.

More subtle is the opposite relation.

######  Proposition 3.3.

For all $r\geq 2$ and $1\leq m\leq n$, where $n-m$ is even,

$t_{r}^{\operatorname{match}}(n)\geq\min\left\\{t_{r}^{\operatorname{perm}}(m),\;2t_{r}^{\operatorname{match}}\left(\frac{n-m+2}{2}\right)\right\\}.$

###### Proof.

Let $M$ be a matching on $[2n]$. Split the set of vertices of $M$ into two
halves, $A=[n]$ and $B=[n+1,2n]$ and let $M^{\prime}:=M(A,B)$ denote the set
of edges of $M$ with one end in $A$ and the other end in $B$. Note that
$M^{\prime}$ is a permutational matching. We distinguish two cases. If
$|M^{\prime}|\geqslant m$, then

$t_{r}(M)\geq t_{r}(M^{\prime})=t_{r}(\pi_{M^{\prime}})\geq
t_{r}^{\operatorname{perm}}(|M^{\prime}|)\geq t_{r}^{\operatorname{perm}}(m).$

If, on the other hand, $|M^{\prime}|<m$, that means, $|M^{\prime}|\leq m-2$,
due to the assumption of $n-m$ being even, then we have sub-matchings $M_{A}$
and $M_{B}$ of $M$ of size at least $(n-m+2)/2$ in sets, respectively, $A$ and
$B$. Thus, in this case, by concatenation,

$t_{r}(M)\geq t_{r}(M_{A})+t_{r}(M_{B})\geq
2t_{r}^{\operatorname{match}}\left(\frac{n-m+2}{2}\right).$

∎

Proposition 3.3 allows, under some mild conditions, to ,,carry over” any lower
bound on $t_{r}^{\operatorname{perm}}(n)$ to one on
$t_{r}^{\operatorname{match}}(n)$.

######  Lemma 3.4.

If for some $0<\alpha,\beta<1$, we have
$t_{r}^{\operatorname{perm}}(n)\geq\beta n^{\alpha}$ for all $n\geq 1$, then
$t_{r}^{\operatorname{match}}(n)\geq\beta(\gamma n)^{\alpha}$ for any
$0<\gamma\leq\min\\{1-2^{1-1/\alpha},1/4\\}$ and all $n\geq 1$.

###### Proof.

Assume that for some $0<\alpha,\beta<1$, we have
$t_{r}^{\operatorname{perm}}(n)\geq\beta n^{\alpha}$ for all $n\geq 1$ and let
$0<\gamma\leq\min\\{1-2^{1-1/\alpha},1/4\\}$ be given. We will prove that
$t_{r}^{\operatorname{match}}(n)\geq\beta(\gamma n)^{\alpha}$ by induction on
$n$. For $n\leqslant\tfrac{1}{\gamma}\left(\tfrac{1}{\beta}\right)^{1/\alpha}$
the claimed bound is at most $1$, so it is trivially true. Assume that
$n\geq\tfrac{1}{\gamma}\left(\tfrac{1}{\beta}\right)^{1/\alpha}$ and that
$t_{r}^{\operatorname{match}}(n^{\prime})\geq\beta(\gamma
n^{\prime})^{\alpha}$ for all $n^{\prime}<n$. Let
$n_{\gamma}\in\\{\lceil\gamma n\rceil,\lceil\gamma n\rceil+1\\}$ have the same
parity as $n$. Then, by Proposition 3.3 with $m=n_{\gamma}$,

$t_{r}^{\operatorname{match}}(n)\geq\min\left\\{t_{r}^{\operatorname{perm}}(n_{\gamma}),2t_{r}^{\operatorname{match}}\left(\frac{n-n_{\gamma}+2}{2}\right)\right\\}.$

By the assumption of the lemma,
$t_{r}^{\operatorname{perm}}(n_{\gamma})\geq\beta
n_{\gamma}^{\alpha}\geq\beta(\gamma n)^{\alpha}$. Since $\gamma\leq 1/4$ and
so, $n\geq 4$, we have $(n-n_{\gamma}+2)/2\leq n-1$. Hence, by the induction
assumption, also

$\displaystyle
2t_{r}^{\operatorname{match}}\left(\frac{n-n_{\gamma}+2}{2}\right)\geq
2\beta\left(\gamma\frac{n-n_{\gamma}+2}{2}\right)^{\alpha}\geq
2\beta\left(\gamma n\frac{1-\gamma}{2}\right)^{\alpha}\geq\beta(\gamma
n)^{\alpha},$

where the last inequality follows by the assumption on $\gamma$.

∎

In particular, Theorem 3.2 and Lemma 3.4 with $\beta=1/8$, $\alpha=3/5$, and
$\gamma=1/4$ imply immediately the following result.

######  Corollary 3.5.

For every $n$,
$t_{2}^{\operatorname{match}}(n)\geq\frac{1}{8}\left(\frac{n}{4}\right)^{3/5}$.
∎

Moreover, any future improvement of the bound in Theorem 3.2 would
automatically yield a corresponding improvement of the lower bound on
$t_{2}^{\operatorname{match}}(n)$.

###  3.2. In random matchings

In this section we study the size of the largest $r$-twins in a random
(ordered) matching $\mathbb{RM}_{n}$, which is, recall, selected uniformly at
random from all $\alpha_{n}:=(2n)!/(n!2^{n})$ matchings on vertex set $[2n]$.
The first moment method yields that

$\mbox{a.a.s.}\quad t_{r}(\mathbb{RM}_{n})<cn^{r/(2r-1)}\quad\mbox{for
any}\quad c>e2^{-(r-1)/(2r-1)}.$ (3.1)

Indeed, the expected number of $r$-twins of size $k$ in $\mathbb{RM}_{n}$ is

$\frac{1}{r!}\binom{2n}{\underbrace{2k,\dots,2k}_{\text{{$r$
times}}},2n-2kr}\frac{\alpha_{k}\cdot
1^{r-1}\cdot\alpha_{n-rk}}{\alpha_{n}}=\frac{2^{(r-1)k}n!}{r!(2k)!^{r-1}k!(n-rk)!}<\left(\frac{e^{2r-1}n^{r}}{2^{r-1}k^{2r-1}}\right)^{k},$

where we used inequalities $n!/(n-rk)!\leq n^{rk}$, $(2k)!\geq(2k/e)^{2k}$,
$k!\geq(k/e)^{k}$, and $r!\geq 1$. Thus, it converges to 0, as $n\to\infty$,
provided $k\geq cn^{r/(2r-1)}$, for any $c$ as in (3.1).

It turns out that the a.a.s. the lower bound on $t_{r}(\mathbb{RM}_{n})$ is of
the same order.

######  Theorem 3.6.

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

$t_{r}(\mathbb{RM}_{n})=\Theta\left(n^{r/(2r-1)}\right).$

In the proof of the lower bound we are going to use the Azuma-Hoeffding
inequality for random permutations (see, e.g., Lemma 11 in [FP] or Section 3.2
in [McDiarmid98]):

######  Theorem 3.7.

Let $h(\pi)$ be a function defined on the set of all permutations of order
$2n$ such that, for some constant $c>0$, if a permutation $\pi_{2}$ is
obtained from a permutation $\pi_{1}$ by swapping two elements, then
$|h(\pi_{1})-h(\pi_{2})|\leq c$. Then, for every $\eta>0$,

$\Pr(|h(\Pi_{n})-{\mathds{E}}[h(\Pi_{n})]|\geq\eta)\leq
2\exp(-\eta^{2}/(4c^{2}n)).$

###### Proof of Theorem 3.6.

In view of (3.1), it suffices to prove a lower bound, that is, to show that
a.a.s. $\mathbb{RM}_{n}$ contains $r$-twins of size $\Omega(n^{r/(2r-1)})$. In
doing so we are following the proof scheme applied in [DGR1, Theorem 1.2]. Set

$a:=r!^{1/(2r-1)}(2n)^{(r-1)/(2r-1)}$

and assume for simplicity that both, $a$ and
$N:=2n/a=r!^{-1/(2r-1)}(2n)^{r/(2r-1)}$, are integers. Partition
$[2n]=A_{1}\cup\cdots\cup A_{N}$, where $A_{i}$’s are consecutive blocks of
$a$ integers each, and define, for every $1\leq i<j\leq N$, a random variable
$X_{ij}$ which counts the number of edges of $\mathbb{RM}_{n}$ with one
endpoint in $A_{i}$ and the other in $A_{j}$. Consider an auxiliary graph
$G:=G(\mathbb{RM}_{n})$ on vertex set $[N]$ where $\\{i,j\\}\in G$ if and only
if $X_{ij}\geq r$.

A crucial observation is that a matching of size $t$ in $G$ corresponds to
$r$-twins in $\mathbb{RM}_{n}$ of size $t$. Indeed, let
$M=\\{i_{1}j_{1},\dots,i_{t}j_{t}\\}$, $i_{1}<\cdots<i_{t}$, be a matching in
$G$. For every $1\leq s\leq t$, let $u^{s}_{h}\in A_{i_{s}}$ and $v^{s}_{h}\in
A_{j_{s}}$, $h=1,\dots,r$, be such that
$e^{s}_{h}:=\\{u^{s}_{h},v^{s}_{h}\\}\in\mathbb{RM}_{n}$. Then, the sub-
matchings
$\\{e^{1}_{1},\dots,e^{t}_{1}\\},\dots,\\{e^{1}_{r},\dots,e^{t}_{r}\\}$, owing
to the sequential choice of $A_{i}$’s form $r$-twins in $\mathbb{RM}_{n}$.
Thus, our ultimate goal is to show that a.a.s. $G$ contains a matching of size
$\Theta(n^{r/(2r-1)})$.

Let $\nu(G)$ be the largest size (as the number of edges) of a matching in
$G$. We will first show that $\nu(G)$ is sharply concentrated around its
expectation. For this we appeal to the permutation scheme of generating
$\mathbb{RM}_{n}$ and apply Theorem 3.7. For a permutation $\pi$ of $[2n]$,
let $M(\pi)=\\{\pi(1)\pi(2),\dots,\pi(2n-1)\pi(2n)\\}$ be the corresponding
matching. Further, let $h(\pi)=\nu(G(M(\pi)))$. 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 edges
of $G(M(\pi_{1}))$. This, in turn, implies that the size of the largest
matching has been altered by at most two, that is,
$|h(\pi_{1})-h(\pi_{2})|\leq 2$. Hence, Theorem 3.7 applied to $h(\pi)$, with
$c=2$, and, say, $\eta=n^{2r/(4r-1)}$ implies that

$\Pr\left(|\nu(G)-{\mathds{E}}[\nu(G)]|\geq
n^{2r/(4r-1)}\right)=\Pr\left(|h(\Pi_{n})-{\mathds{E}}[h(\Pi_{n})]|\geq
n^{2r/(4r-1)}\right)=o(1).$ (3.2)

Note that, crucially, $n^{2r/(4r-1)}=o(n^{r/(2r-1)})$, and it thus remains to
show that ${\mathds{E}}(\nu(G))=\Omega(n^{r/(2r-1)})$.

Let us first estimate from below the probability of an edge in $G$, that is,
$\Pr(X_{ij}\geq r)$. Trivially, $\Pr(X_{ij}\geq r)\geq\Pr(X_{ij}=r)$. We are
going to further bound $\Pr(X_{ij}=r)$ from below by counting matchings on
$[2n]$ with precisely $r$ edges between the sets $A_{i}$ and $A_{j}$, but with
no edges within $A_{i}$ or $A_{j}$ (the latter is a simplifying restriction).
To build such a matching one has to first select subsets
$S_{i},S_{j},T_{i},T_{j}$ such that $S_{i}\subset A_{i}$, $S_{j}\subset
A_{j}$, $|S_{i}|=|S_{j}|=r$, while $T_{i}\cap(A_{i}\cup A_{j})=\varnothing$,
$T_{j}\cap(A_{i}\cup A_{j})=\varnothing$, $T_{i}\cap T_{j}=\varnothing$, and
$|T_{i}|=|T_{j}|=a-r$. The total number of these selections is

$\binom{a}{r}^{2}\binom{2n-2a}{a-r}\binom{2n-3a+r}{a-r}.$

Then one has to match $S_{i}$ with $S_{j}$, $A_{i}\smallsetminus S_{i}$ with
$T_{i}$, and $A_{j}\smallsetminus S_{j}$ with $T_{j}$, and find a perfect
matching on the set $[2n]\smallsetminus(A_{i}\cup A_{j}\cup T_{i}\cup T_{j})$
of the remaining $n-4a+2r$ elements. There are

$r!(a-r)!(a-r)!\alpha_{n-2a+r}$

ways of doing so.

Multiplying the two products together and dividing by $\alpha_{n}$, we obtain
the inequality

$\Pr(X_{ij}=r)\geq\frac{a!^{2}4^{a}(2n-2a)!n!}{r!2^{r}(a-r)!^{2}(2n)!(n-2a+r)!}.$

Since $a=o(\sqrt{n})$, we have

$(2n)!/(2n-2a)!=(1+o(1))(2n)^{2a}\quad\mbox{and}\quad
n!/(n-2a+r)!=(1+o(1))n^{2a-r},$

and so the R-H-S above equals

$\frac{(1+o(1))}{r!}\left(\frac{a^{2}}{2n}\right)^{r}.$

Consequently, for $n$ large enough,

$\Pr(X_{ij}\geq
r)\geq\Pr(X_{ij}=r)\geq\frac{1}{2r!}\left(\frac{a^{2}}{2n}\right)^{r}.$

Having estimated the probability of an edge in $G$, we are now in position to
estimate the degree of a vertex. For each $i\in[N]$, let $Y_{i}=\deg_{G}(i)$
be the degree of vertex $i$ in $G$. Then

${\mathds{E}}(Y_{i})=\left(N-1\right)\Pr(X_{ij}\geq
r)\geq\frac{N}{4r!}\left(\frac{a^{2}}{2n}\right)^{r}=\frac{2n}{4r!a}\left(\frac{a^{2}}{2n}\right)^{r}=\frac{1}{4}.$
(3.3)

There is an obvious bound on the size of the largest matching $\nu(G)$ in
$G=(V,E)$ in terms of the vertex degrees, namely

$\nu(G)\geq\frac{|E(G)|}{2\Delta_{G}}=\frac{\sum_{i=1}^{N}Y_{i}}{4\Delta_{G}},$

where $\Delta_{G}$ is the maximum degree in $G$. Note that, trivially,
$\Delta_{G}\leq\min\\{a/r,N-1\\}=a/r$. Unfortunately, since the expected
degrees ${\mathds{E}}(Y_{i})$ are (bounded by) constants – cf. (3.3), in this
form the bound on $\nu(G)$ is of no use, as one cannot show concentration of
all degrees $Y_{i}$ simultaneously. Instead, we resort to an even weaker, but
more manageable bound.

For an integer $D>0$, let $G_{D}$ be a subgraph of $G$ induced by the set
$V_{D}$ of all vertices of degrees at most $D$ in $G$, that is,
$G_{D}=G[V_{D}]$. Then, clearly, $\Delta(G_{D})\leq D$ and

$|E(G_{D})|=|E(G)|-|\\{e\in E(G):\;e\cap(V\smallsetminus
V_{D})\neq\varnothing\\}|\geq\frac{1}{2}\sum_{i=1}^{N}Y_{i}-\sum_{k=D+1}^{\lfloor
a/r\rfloor}kZ_{k},$

where $Z_{k}=|\\{i\in[N]:Y_{i}=k\\}|$, and thus,

$\nu(G)\geq\nu(G_{D})\geq\frac{|E(G_{D})|}{2D}\geq\frac{1}{2D}\left(\frac{1}{2}\sum_{i=1}^{N}Y_{i}-\sum_{k>D}kZ_{k}\right).$

Hence, recalling (3.3) and noticing that ${\mathds{E}}Z_{k}=N\Pr(Y_{1}=k)$, we
have

${\mathds{E}}(\nu(G))\geq\frac{N}{2D}\left(\frac{1}{8}-\sum_{k>D}k\Pr(Y_{1}=k)\right).$

It remains to estimate $\Pr(Y_{1}=k)$ from above. Very crudely, to create a
matching satisfying $Y_{1}=k$, one has to select $k$ other sets $A_{i}$,
choose $r$ vertices from each of them, and match them with some $kr$ vertices
of $A_{1}$. In the estimates below, we ignore the demand that $Y_{1}$ is
precisely $k$, so, in fact, we estimate from above $\Pr(Y_{1}\geq k)$. We thus
have

$\Pr(Y_{1}=k)\leq\Pr(Y_{1}\geq
k)\leq\binom{N}{k}\binom{a}{r}^{k}\binom{a}{rk}(rk)!\frac{\alpha_{n-rk}}{\alpha_{n}}\leq\frac{N^{k}a^{2rk}2^{rk}n^{rk}}{k!r!^{k}}\cdot\frac{(2n-2rk)!}{(2n)!}.$

Using the inequality $1-x\geq e^{-2x}$ valid for $x\leq 1/2$, the last
fraction can be estimated as

$\frac{(2n-2rk)!}{(2n)!}=\frac{1}{(2n)^{2rk}\left(1-\frac{1}{2n}\right)\cdot\ldots\cdot\left(1-\frac{2rk-1}{2n}\right)}\leq\frac{e^{2r^{2}k^{2}/n}}{(2n)^{2rk}}.$

Since $a^{2r-1}=r!n^{r-1}$ and $k\leq a/r$, we have $k^{2}=o(n)$ and can
bound, roughly, $e^{2r^{2}k^{2}/n}\leq 2$. Consequently, recalling that
$N=2n/a$ and using the bound $(k-1)!\geq((k-1)/3)^{k-1}$, we infer that

$k\Pr(Y_{1}=k)\leq\frac{2a^{2rk-k}}{(k-1)!r!^{k}(2n)^{rk-k}}=\frac{2}{(k-1)!}\leq
2\left(\frac{3}{k-1}\right)^{k-1}\leq 2\left(\frac{1}{2}\right)^{k-1}$

for $k\geq 7$. Setting $D=6$ and summing over all $k>D$, we thus obtain the
bound

$\sum_{k>D}^{\lfloor a/r\rfloor}k\Pr(Y_{1}=k)\leq
2\sum_{k>6}^{\infty}\left(\frac{1}{2}\right)^{k-1}=2\sum_{k\geq
6}^{\infty}\left(\frac{1}{2}\right)^{k}=4\cdot 2^{-6}=\frac{1}{16}.$

Finally,

${\mathds{E}}(\nu(G))\geq\frac{N}{12}\left(\frac{1}{8}-\frac{1}{16}\right)\geq\frac{N}{200}=\Theta\left(n^{{r}/{(2r-1)}}\right)$

which, together with (3.2), completes the proof. ∎

##  4\. Final remarks

Let us conclude the paper with some suggestions for future studies. The first
natural goal is to extend our Erdős-Szekers-type results to $r$-uniform
ordered matchings for arbitrary $r\geqslant 4$. We have inspected more
carefully the case of $r=4$ observing some similar phenomena as in the two
smaller cases, $r=2$ and $r=3$. In particular, among the 35 possible relations
between pairs of ordered quadruples there are exactly 27 that are collectable.
This boosts some hope that by cleverly handling the remaining 8 relations, one
can, indeed, generalize Theorem 2.5 with the exponents $1/9$ replaced by
$1/27$.

Returning to the case $r=3$, we are not yet completely done, as we were unable
to construct a general counterexample showing the optimality of Theorem 2.5
for arbitrary values of _all_ 9 parameters (c.f. Remark 2.7).

######  Problem 4.1.

For all positive integers $a_{xy}$, where $x,y\in\\{\ell,s,w\\}$,
$(x,y)\neq(\ell,\ell)$, construct a matching $M$ of size $n=\prod_{x,y}a_{xy}$
such that neither $M$ contains a semi-line of size 2, nor for any pair $(x,y)$
does it contain a sub-matching of $a_{xy}+1$ triples every two of which are in
relation ${\mathcal{R}}_{x,y}$.

As mentioned earlier, setting $a_{\ell,\ell}=1$ is not a restriction at all,
as in the general case one may simply concatenate $a_{\ell,\ell}$ disjoint
copies of the matching described in Problem 4.1

A related problem is to estimate the size of unavoidable patterns in random
$r$-matchings $\mathbb{RM}^{(r)}_{n}$ with $r\geqslant 3$. For $r=2$, we have
established (c.f. Theorem 2.11) that it is a.a.s. of the order
$\Theta(\sqrt{n})$. As it was already mentioned at the end of Section 2.3, as
a consequence of Proposition 2.13, for $r=3$ a.a.s. none of the nine
collectable sub-matchings (as defined in Subsection 2.2) has size bigger than
$2n^{1/3}$. It would be nice to prove a complementary lower bound. Although
for 3-uniform lines this does not seem to be difficult (as, likely, Lemma 2.12
can be extended for hyperedges), showing that a.a.s. $\mathbb{RM}^{(3)}_{n}$
contains _every_ collectable sub-matching of size $\Omega(n^{1/3})$ will
require some new ideas.

For arbitrary $r$, it too seems natural to expect that, as in the case $r=2$,
all homogeneous substructures (corresponding to collectable relations) of
$\mathbb{RM}^{(r)}_{n}$ should a.a.s. have size $\Omega(n^{c_{r}})$, for some
constant $0<c_{r}<1$. By Theorem 2.11 we know that $c_{r}=1/2$, while guided
by Proposition 2.13, we suspect that $c_{r}=1/r$. But, perhaps, even more is
true.

######  Conjecture 4.2.

For every fixed positive integer $r\geqslant 2$ there exist positive constants
$b_{r},c_{r}$ such that the maximum size of each collectable structure in
$\mathbb{RM}^{(r)}_{n}$ is a.a.s. equal to $(1+o(1))b_{r}n^{c_{r}}$.

According to Theorem 2.9, if the Conjecture 4.2 is true, then
$b_{2}=\sqrt{2}$. Unfortunately, we do not know if lines satisfy the assertion
of Theorem 2.9, so the conjecture is open even in the smallest case of $r=2$.

Other open problems can be formulated for twins in ordered matchings. Based on
what we proved here we state the following conjecture.

######  Conjecture 4.3.

For every fixed $r\geqslant 2$, we have
$t_{r}^{\operatorname{match}}(n)=\Theta\left(n^{\frac{r}{2r-1}}\right)$.

The same statement is conjectured for twins in permutations (see [DGR1]), and,
by our results, we know that both conjectures are actually equivalent.

One could also study the size of twins in $r$-uniform ordered matchings or,
more generally, in arbitrary ordered graphs or hypergraphs. For ordinary
_unordered_ graphs there is a result of Lee, Loh, and Sudakov [LLSud] giving
an asymptotically exact answer of order $\Theta(n\log n)^{2/3}$. It would be
nice to have an analogue of this result for ordered graphs.

## References


# TANet++: Triple Attention Network with Filtered Pointcloud on 3D Detection

Cong Ma
Peking University
Beijing  China
<EMAIL_ADDRESS>
###### Abstract

TANet [2] is one of state-of-the-art 3D object detection method on KITTI [1]
and JRDB [3] benchmark, the network contains a Triple Attention module and
Coarse-to-Fine Regression module to improve the robustness and accuracy of 3D
Detection. However, since the original input data (point clouds) contains a
lot of noise during collecting the data, which will further affect the
training of the model. For example, the object is far from the robot, the
sensor is difficult to obtain enough pointcloud. If the objects only contains
few point clouds, and the samples are fed into model with the normal samples
together during training, the detector will be difficult to distinguish the
individual with few pointcloud belong to object or background. In this paper,
we propose TANet++ to improve the performance on 3D Detection, which adopt a
novel training strategy on training the TANet. In order to reduce the negative
impact by the weak samples, the training strategy previously filtered the
training data, and then the TANet++ is trained by the rest of data. The
experimental results shows that AP score of TANet++ is 8.98% higher than TANet
on JRDB benchmark.

##  1 Data Filter Strategy

TANet++ refers to TANet structure (one of the state-of-the-art 3D detection
method) as 3D detection model with same hyper-parameters and training
strategy. To reduce the impact of the bad samples for training the TANet, we
propose three constraints to filter the bad samples and ensure the vaildity of
the training data.

The constraints includes: 1.Distance Constraint; 2.Number of Pointcloud
Constraint; 3.Occlusion Constraint.

###  1.1 Distance Constraint

Since the objects are too far away from the sensor, the captured data does not
contain enough point cloud information to support the representation of the
target features. Furthermore, the model cannot distinguish these objects and
background well, which cause the output of model might contain a large number
of false positives (background are mis-detected as specific object).
Therefore, Distance Constraint aims to filter the objects which is far from
the sensor, the constraint is shown as :

$\displaystyle\left\\{\begin{matrix}discard,\
{||p_{s}-p_{i}||}_{2}^{2}>\eta\\\ keep,\ {||p_{s}-p_{j}||}_{2}^{2}\leq\eta\\\
\end{matrix}\right.$ (1)

where $p_{s}$ and $p_{i}$ indicate the center of 3D position of the sensor and
object respectively, $\eta$ is distance threshold, which is set as 15. If the
distance between sendor and object $i$ is less than $\eta$, then the object
$j$ will be kept in the training set, other wise the object will be remove
from the training set.

###  1.2 Number of Pointcloud Constraint

Since occlusion and the ladar interference, some targets only contain few
pointcloud in their bounding boxes. Even though the object is close to the
senor, the number of pointcould in the target is still limited if the target
is seriously occluded. Therefore, we propose Number of Pointcloud Constraint
to remove the targets which do not contain enough pointcloud, the constraint
is shown as:

$\displaystyle\left\\{\begin{matrix}discard,\ n_{i}<\delta\\\ keep,\
n_{j}\geq\delta\\\ \end{matrix}\right.$ (2)

where $n_{i}$ and $n_{j}$ indicates the number of pointcloud of object $i$ and
$j$ respectively. $\delta$ is the number threshold, which is set as 10. If the
number of pointcloud of target is more than $delta$, then the object $j$ will
be kept in the training set, other wise the object will be remove from the
training set.

Figure 1: Overall Precision-Recall curves: (a): F-PointNet (b):TANet
(c):TANet++ Figure 2: Overall Precision-Recall curves: (a): F-PointNet
(b):TANet (c):TANet++

###  1.3 Occlusion Constraint

JRDB [3] additionally provides the information that the annotated target is
occluded or not, which includes ”Fully Visible”, ”Mostly Visible”, ”Severly
Occluded” and ”Fully Occluded”. These information can help us further filter
the bad samples. The constraint is shown as:

$\displaystyle\left\\{\begin{matrix}discard,\ i\in"FullyOccluded"\\\ keep,\
j\in others\\\ \end{matrix}\right.$ (3)

where if the object $i$ is labelled as ”Fully Occluded”, then the target will
be remove from the training set, otherwise the target will be kept in the
training set.

##  2 Experimental Results

Method | AP
---|---
F-PointNet [4] | 38.21
TANet [2] | 54.94
TANet++ | 63.92
Table 1: Results on JRDB testing set

Table 1 shows the detection results on JRDB testing set, where our method
TANet++ is 8.98% and 25.71% higher than TANet and F-PointNet respectively on
AP.

Figure 1 illstrates the precision-recall curves for F-PointNet, TANet and
TANet++.

Figure2 shows the TANet++ visulization results in JRDB testing set.

## References

  * [1] Andreas Geiger, Philip Lenz, Christoph Stiller, and Raquel Urtasun.  Vision meets robotics: The kitti dataset.  International Journal of Robotics Research (IJRR), 2013.
  * [2] Zhe Liu, Xin Zhao, Tengteng Huang, Ruolan Hu, Yu Zhou, and Xiang Bai.  Tanet: Robust 3d object detection from point clouds with triple attention.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 11677–11684, 2020.
  * [3] Roberto Martin-Martin*, Mihir Patel*, Hamid Rezatofighi*, Abhijeet Shenoi, JunYoung Gwak, Eric Frankel, Amir Sadeghian, and Silvio Savarese.  JRDB: A dataset and benchmark of egocentric robot visual perception of humans in built environments.  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2021.
  * [4] Charles R Qi, Wei Liu, Chenxia Wu, Hao Su, and Leonidas J Guibas.  Frustum pointnets for 3d object detection from rgb-d data.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 918–927, 2018.