\begin{document}

\title[Erd\H os-Szekeres for uniform matchings]{Erd\H os-Szekeres type Theorems for ordered uniform  matchings}

\author{Andrzej Dudek}
\address{Department of Mathematics, Western Michigan University, Kalamazoo, MI, USA}
\email{\tt andrzej.dudek@wmich.edu}
\thanks{The first author was supported in part by Simons Foundation Grant \#522400.}

\author{Jaros\ifmmode\ell\else\polishlcross\fi aw Grytczuk}
\address{Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, Poland}
\email{j.grytczuk@mini.pw.edu.pl}
\thanks{The second author was supported in part by Narodowe Centrum Nauki, grant 2020/37/B/ST1/03298.}

\author{Andrzej Ruci\'nski}
\address{Department of Discrete Mathematics, Adam Mickiewicz University, Pozna\'n, Poland}
\email{\tt rucinski@amu.edu.pl}
\thanks{The third author was supported in part by Narodowe Centrum Nauki, grant 2018/29/B/ST1/00426}

\begin{abstract} For $r,n\ge2$, \emph{an ordered $r$-uniform matching $M^{(r)}_n$ of size $n$} is an $r$-uniform hypergraph on a linearly ordered vertex set~$V$, with $|V|=rn$, consisting of $n$ pairwise disjoint edges. There are $\tfrac12\mathrm{Bin}om{2r}r$ different $M_2^{(r)}$'s, that is, different ways two edges may intertwine,  called here \emph{patterns}. Among them we identify $3^{r-1}$ \emph{collectable} patterns $P$, which have the potential of appearing in arbitrarily large quantities called  \emph{$P$-cliques}. 
	
We prove an Erd\H{o}s-Szekeres type result guaranteeing in every $M^{(r)}_n$ the presence of a $P$-clique of a prescribed size, for some collectable pattern~$P$. In particular, in the diagonal case, one of the $P$-cliques must be of size  $\Omega\ifmmode\ell\else\polishlcross\fieft( n^{3^{1-r}}\right)$. In addition, for each collectable pattern $P$ we show that the largest size of a $P$-clique in a \emph{random} $M^{(r)}_n$ is, with high probability, $\Theta\ifmmode\ell\else\polishlcross\fieft(n^{1/r}\right)$.
\end{abstract}

\maketitle

\@ifstar{\origsection*}{\@startsection{section}{1}\z@{.7\ifmmode\ell\else\polishlcross\fiinespacing\@plus\ifmmode\ell\else\polishlcross\fiinespacing}{.5\ifmmode\ell\else\polishlcross\fiinespacing}{\normalfont\scshape\centering\S}}{Introduction}

For $r\ge2$, an $r$-uniform hypergraph $G$, or, shortly, \emph{ an $r$-graph} is said to be \emph{ordered} if its vertex set is linearly ordered.
Let $G$ and $H$ be two ordered  $r$-graphs with $V(G)=\{v_1<\cdots<v_m\}$ and $V(H)=\{w_1<\cdots<w_m\}$ for some  $m\ge1$. We say that $G$ and $H$ are \emph{order-isomorphic} if for all $1\ifmmode\ell\else\polishlcross\fie i_1<\cdots<i_r\ifmmode\ell\else\polishlcross\fie m$, $\{v_{i_1},\dots,v_{i_r}\}\in E(G)$ if and only if $\{w_{i_1},\dots,w_{i_r}\}\in E(H)$.

Compared to ordinary isomorphism, one context in which order-isomorphism makes quite a difference is that of sub-hypergraph containment. If $G$ is an ordered $r$-graph, then any sub-$r$-graph $G'$ of $G$ can be also treated as an ordered $r$-graph with the ordering of $V(G')$ inherited from the ordering of $V(G)$.
Given  two ordered $r$-graphs,  $G$ and  $H$, we say that a sub-$r$-graph $G'\subset G$ is \emph{an ordered copy of $H$ in $G$} if $G'$ and $H$ are order-isomorphic.
All kinds of questions concerning sub-hypergraphs in unordered hypergraphs can be posed for ordered hypergraphs as well (see, e.g., \cites{Tardos,BGT}).

In this paper we focus exclusively on  \emph{ordered $r$-uniform matchings}, or, shortly, \emph{$r$-matchings}, that is, ordered $r$-uniform hypergraphs  which consist of vertex-disjoint edges (and have no isolated vertices). There are precisely
$\frac{(rn)!}{(r!)^n\, n!}$ $r$-matchings of size $n$. Any one of them will be denoted by $M^{(r)}_n$.

\subsection{Background}

 A frequent theme in combinatorics and graph theory deals with unavoidable sub-structures that appear in every member of a prescribed family of structures. A flagship example  is the famous theorem of Erd\H{o}s and Szekeres \cite{ErdosSzekeres} on monotone subsequences (see, e.g., \cites{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,\ifmmode\ell\else\polishlcross\fidots, x_n$ of distinct real numbers contains a monotone subsequence of length at least~$\sqrt n$.

Our goal is to prove its analog for ordered $r$-matchings. The reason why the original  Erd\H os-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 $r$-matchings, however, for every two edges of size $r$, there are exactly $\tfrac12\mathrm{Bin}om{2r}r$ patterns in which they may intertwine. For example, for $r=2$, every two edges form either  \emph{an alignment},  \emph{a nesting}, or \emph{a crossing} (see Fig.~\ref{ESZ1}).
\begin{figure}
\caption{An alignment, a nesting, and a crossing of a pair of edges.}
\end{figure}

These three patterns give rise, respectively, to three types of homogenous ordered sub-matchings: \emph{lines}, \emph{stacks}, and \emph{waves}, in which every two edges form the same pattern, (see Fig.~\ref{ESZ2}, where we used a handy letter notation to depict the patterns).
 \begin{figure}
\caption{A line, a stack, and a wave of size four.}
\end{figure}

 In \cite{DGR-match} (see also an extended abstract~\cite{DGR_LATIN}) we proved the following analog of the Erd\H os-Szekeres Theorem for ordered 2-matchings.

 \begin{theorem}[\cite{DGR-match}]\ifmmode\ell\else\polishlcross\fiabel{Theorem E-S for LSW}
	Let $\ell,s,w$ be arbitrary positive integers and let $n\ge\ell sw+1$. Then, every $M^{(2)}_n$ contains a line of size $\ell+1$, or a stack of size $s+1$, or a wave of size $w+1$.
\end{theorem}
 In the same paper we also proved an analogous, though a bit blurred, result for ordered $3$-matchings. There are $\tfrac12\mathrm{Bin}om63=10$ possible patterns that can be formed by two triples, see Table~\ref{table:relations} (ignore the R-H-S column for a moment, as well as the alternative notation with double subscripts). Unfortunately, one of them, $P_1^*=AABABB$, or $\{\{1,2,4\}, \{3,5,6\}\}$, stands out as one that cannot be formed mutually by more than two edges. Nevertheless, in \cite{DGR-match} we managed to prove an Erd\H os-Szekeres type result guaranteeing in every $M_n^{(3)}$ the presence of a homogenous sub-matching of a prescribed size for one of the nine remaining patterns, with some deficiency with respect to the pattern $P_1=AAABBB$ caused by a possible, though scattered, occurrence  of the defective pattern $P_1^*$.

 \begin{table}[h!]
 	\centering
 	\begin{tabular}{ |c||c||c| }
 		\hline
 		
 		\textsc{pattern}& \textsc{in words} & \textsc{operation $\oplus$}\\
 		\hline
 		\hline
 		$P_1=P_{\ell,\ell}$ & $AAABBB$ & $AABB\oplus AABB=\underline{A}\overline{\underline{A}}\overline{A}\underline{B}\overline{\underline{B}}\overline{B}$\\
 		\hline
 		$P_1^*=P^*_{\ell,\ell}$ & $AABABB$ &  $AABB\oplus AABB=\underline{A}\underline{\overline{A}}\underline{B}\overline{A}\underline{\overline{B}}\overline{B}$\\
 		\hline
 		\hline
 		$P_2=P_{\ell,s}$ & $AABBBA$ &  $AABB\oplus ABBA=\underline{A}\overline{\underline{A}}\underline{B}\overline{\underline{B}}\overline{B}\overline{A}$\\
 		\hline
 		$P_3=P_{\ell,w}$ & $AABBAB$ &  $AABB\oplus ABAB=\underline{A}\overline{\underline{A}}\underline{B}\overline{\underline{B}}\overline{A}\overline{B}$\\
 		\hline
 		$P_4=P_{s,\ell}$ & $ABBBAA$ & $ABBA\oplus BBAA=\underline{A}\underline{B}\overline{\underline{B}}\overline{B}\overline{\underline{A}}\overline{A}$\\
 		\hline
 		$P_5=P_{s,s}$ & $ABBAAB$ &  $ABBA\oplus BAAB=\underline{A}\underline{B}\overline{\underline{B}}\overline{\underline{A}}\overline{A}\overline{B}$\\
 		\hline
 		$P_6=P_{s,w}$ & $ABBABA$ &  $ABBA\oplus BABA=\underline{A}\underline{B}\overline{\underline{B}}\overline{\underline{A}}\overline{B}\overline{A}$\\
 		\hline
 		$P_7=P_{w,\ell}$  & $ABAABB$ & $ABAB\oplus AABB=\underline{A}\underline{B}\overline{\underline{A}}\overline{A}\overline{\underline{B}}\overline{B}$\\
 		\hline
 		$P_8=P_{w,s}$ & $ABABBA$ & $ABAB\oplus ABBA=\underline{A}\underline{B}\underline{\overline{A}}\underline{\overline{B}}\overline{B}\overline{A}$\\
 		\hline
 		$P_9=P_{w,w}$ & $ABABAB$ & $ABAB\oplus ABAB=\underline{A}\underline{B}\underline{\overline{A}}\underline{\overline{B}}\overline{A}\overline{B}$\\
 		\hline
 	\end{tabular}
 	\caption{All possible patterns of two triples and their corresponding decompositions via operation $\oplus$. The rightmost column reveals the left parent (underlined) and the right parent (overlined) within the children. The alternative notation $P_{xy}$ encodes the pattern's parents, where $\ell$ stands for an alignment, $s$ -- a stack, and $w$ -- a wave.}
 	\ifmmode\ell\else\polishlcross\fiabel{table:relations}
 \end{table}

To state the result in a succinct form,  let us call an ordered $r$-matching whose all pairs of edges form the same, fixed pattern $P$, \emph{a $P$-clique}.
 \begin{theorem}[\cite{DGR-match}]\ifmmode\ell\else\polishlcross\fiabel{Theorem E-S for triples}
 	Let $a_i$, $i=1,\dots,9$, be arbitrary positive integers and let $n\ge\prod_{i=1}^{9}a_{i}+1$.  Then, every $M_n^{(3)}$  either contains a $P_1$-clique of size at least $(a_{1}+1)/2$ or, for some $i\in\{2,\dots,9\}$,  a $P_{i}$-clique of size $a_{i}+1$.
 \end{theorem}

\subsection{Main result}
In this subsection we describe our new results about unavoidable sub-structures in every $M_n^{(r)}$. For results about random $r$-matchings see the next subsection.

The main goal of this paper is to generalize Theorems \ref{Theorem E-S for LSW} and \ref{Theorem E-S for triples} to arbitrary $r\ge 2$. 
In order to state our result we need to introduce some terminology and notation.

Given $r\ge2$, recall that there are exactly $\tfrac12\mathrm{Bin}om{2r}r$ ways, called patterns, in which a pair of disjoint edges of order $r$ may intertwine on an ordered vertex set.
We call them $r$-patterns if the order $r$ is to be emphasized.

 A pattern $P$  is called \emph{collectable} if for every $k\ge2$ there is a $P$-clique of size $k$. It turns out that collectable patterns are easily characterized in terms of binary words with $r$ letters $A$ and $r$ letters $B$ which, due to symmetry, always begin with $A$. Since there is a one-to-one correspondence between the patterns and such words, we will refer to these words as patterns, too.

   \emph{A block} in a word is a segment of consecutive letters of any length. A block consisting of the same letter is called  \emph{a run} (it does not need to be maximal, though). A run $AA\cdots A$ of length $k$ is often denoted compactly by $A^k$ and called  \emph{an $A$-run} of \emph{length} $k$.

  A pattern $P$ is \emph{splittable} if it can be split into a number of blocks each consisting of an $A$-run and a $B$-run  of the same length. For instance, the pattern $AABBABBA$ is splittable, because it splits into three such blocks: $|AABB|AB|BA|$, while $AABABB$ is not.

 It is easy to see that a splittable pattern is collectable. For instance, if $P=|AABB|AB|BA|$, then for every $k\ge 2$,
 $$|A_1A_1A_2A_2\cdots A_kA_k|A_1A_2\cdots A_k|A_k\cdots A_2 A_1|$$
 is a $P$-clique of size $k$.
 Indeed, one can see that for every $1\ifmmode\ell\else\polishlcross\fie i<j\ifmmode\ell\else\polishlcross\fie k$, the letters $A_i$ and $A_j$ do form pattern $P$.

 In Subsection~\ref{char} we show that a pattern is collectable if and only if it is splittable and, moreover, for a non-collectable $P$ there are no $P$-cliques of size greater than two. It follows,  by means of some elementary enumeration, that there are precisely $3^{r-1}$ collectable $r$-patterns for every $r\ge2$.
 In particular,  for $r=2$ all three patterns are collectable, for $r=3$ all but one ($P_1^*$), while for $r=4$, out of 35 patterns, 27 are collectable (see Table \ref{table:patterns4} in Subsection \ref{pat_decomp}, where suitable partitions are shown).

 While  generalizing Theorems \ref{Theorem E-S for LSW} and \ref{Theorem E-S for triples} one has to accommodate the deficiencies  similar to the sole  constant $1/2$ in Theorem \ref{Theorem E-S for triples}. For this sake, we look at the very end of each pattern.

 \emph{The maturity} of a collectable pattern equals the length of its last \emph{maximal} run minus $2$, unless this value is negative, in which case we set it to $0$. The maturity of a pattern $P$ will be denoted by $m(P)$. For instance,  $m(A^4B^4)=4-2=2$, while $m(AABBBBAA)=m(ABABABAB)=0$.

 We may now formulate our main result. An $r$-matching is called \emph{clean} if every pair of its edges forms a collectable pattern.

 \begin{theorem}\ifmmode\ell\else\polishlcross\fiabel{Theorem ESz General_classic}
	For $r\ge 2$, let $P_1,\dots,P_{3^{r-1}}$ be all collectable $r$-patterns and let positive integers $a_1,\dots, a_{3^{r-1}}$ be given. If $n\ge\prod_{i=1}^{3^{r-1}}a_i+1$, then
\begin{itemize}
\item[(a)] every $M_n^{(r)}$ contains, for some $i$, a $P_i$-clique of size greater than $a_i2^{-m(P_i)}$;
\item[(b)] every clean $M_n^{(r)}$  contains, for some $i$, a $P_i$-clique of size at least $a_i+1$.
\end{itemize}
\end{theorem}
\noindent Note that for $r=2$ and $r=3$, we retain, respectively, Theorems \ref{Theorem E-S for LSW} and \ref{Theorem E-S for triples}, the latter with an additional statement (b), where \emph{clean} just means that no pair of edges forms pattern $P_1^*$.

\subsection{Corollaries} In this subsection we gather three easy corollaries of Theorem \ref{Theorem ESz General_classic} and prove them right away.

One context in which clean $r$-matchings emerge is that of $r$-partiteness. An $r$-matching $M$ of size $k$ is \emph{(ordered) $r$-partite} if after splitting  its vertex set $[rk]$ into $r$ consecutive blocks   of size $k$,
 every edge of $M$ contains one vertex from each block.
Note that the only patterns possible in an $r$-partite $r$-matching are those which are themselves $r$-partite. These patterns can be characterized as splittable patterns with each block being either $AB$ or $BA$, except the first one which has to be $AB$. Consequently, there are exactly $2^{r-1}$ of them.
For instance, for $r=2$, both the nestings and the crossing, are bipartite, while
for $r=3$, only patterns $P_5,P_6,P_8,P_9$ (as listed in Table \ref{table:relations}) are tripartite.
Moreover, an $r$-partite $r$-matching is, indeed, clean.
Setting $a_i=1$ for each non-$r$-partite pattern $P_i$, we thus obtain the following corollary of Theorem~\ref{Theorem ESz General_classic}(b).

\begin{cor}\ifmmode\ell\else\polishlcross\fiabel{Theorem ESz General_partite}
	For $r\ge 2$, let $Q_1,\dots,Q_{2^{r-1}}$ be all $r$-partite patterns and let positive integers $b_1,\dots, b_{2^{r-1}}$ be given. If $n\ge\prod_{i=1}^{2^{r-1}}b_i+1$, then every $r$-partite $M_n^{(r)}$ contains, for some $i$, a $Q_i$-clique of size at least $b_i+1$.
 \end{cor}
\noindent The above result illustrates the following principle: setting  $a_i=1$ for any pattern absent from a matching results in more ``prey'' for the remaining  patterns.

\begin{proof}[Proof of Corollary  \ref{Theorem ESz General_partite}] Let us reorder, if necessary, the patterns $P_i$ so that $P_i=Q_i$ for $i=1,\dots,2^{r-1}$. Then set $a_i=b_i$ for every $i\ifmmode\ell\else\polishlcross\fie 2^{r-1}$ and $a_i=1$ for the remaining $i$. The corollary follows from Theorem \ref{Theorem ESz General_classic}(b).
\end{proof}

 Theorem \ref{Theorem ESz General_partite} can be interpreted in terms of edge-colorings of a complete graph. Indeed, we may associate with  $M_n^{(r)}$ a colored complete graph with the $n$ edges of $M_n^{(r)}$ being the vertices and the colors corresponding to all possible $\tfrac12\mathrm{Bin}om{2r}r$ patterns. Of course only the $3^{r-1}$ colors, corresponding to collectable patterns, can form cliques of order larger than two. It follows from known bounds on Ramsey numbers that a monochromatic clique of order $\Omega(\ifmmode\ell\else\polishlcross\fiog n)$ is guaranteed (see, e.g.,~\cite{ConlonFerber}). Theorem \ref{Theorem ESz General_classic} implies that there must be a monochromatic clique of size  $\Omega(n^{3^{1-r}})$.

\begin{cor}\ifmmode\ell\else\polishlcross\fiabel{Theorem ESz General_diagonal}
	For $r\ge 2$, let $P_1,\dots,P_{3^{r-1}}$ be all collectable patterns and $Q_1,\dots,Q_{2^{r-1}}$ be the $r$-partite patterns among them.  Then,
\begin{itemize}
\item[(a)] every $M_n^{(r)}$ contains, for some $i$, a $P_i$-clique of size greater $2^{2-r}n^{3^{1-r}}$,
\item[(b)] every clean $M_n^{(r)}$ contains, for some $i$, a $P_i$-clique of size greater $n^{3^{1-r}}$,
\item[(c)] every $r$-partite $M_n^{(r)}$ contains, for some $i$, a $Q_i$-clique of size greater than $n^{2^{1-r}}$.
\end{itemize}
 \end{cor}

\begin{proof} For (a) and (b), set $a_i=\ifmmode\ell\else\polishlcross\ficeil n^{3^{1-r}}\rceil-1$, $i=1,\dots,3^{r-1}$, and notice that then $\prod_ia_i>n$. Thus, by Theorem \ref{Theorem ESz General_classic}(a),  in every $M_n^{(r)}$ there is, for some $i$, a $P_i$-clique of size greater than $n^{3^{1-r}}2^{m(P_i)}$. Remembering that, by definition, $m(P_i)\ifmmode\ell\else\polishlcross\fie r-2$, completes the proof of part~(a). Next, by Theorem \ref{Theorem ESz General_classic}(b), in every clean $M_n^{(r)}$ there is,  for some $i$, a $P_i$-clique of size greater than $n^{3^{1-r}}$. Finally, setting $b_i=\ifmmode\ell\else\polishlcross\ficeil n^{2^{1-r}}\rceil-1$, $i=1,\dots,2^{r-1}$, by Corollary~\ref{Theorem ESz General_partite},  in every $r$-partite $M_n^{(r)}$ there is, for some $i$, a $Q_i$-clique  of size greater than $n^{2^{1-r}}$.
\end{proof}

 It can be routinely calculated  (see Subsection \ref{char}) that
 \begin{equation}\ifmmode\ell\else\polishlcross\fiabel{summPi}
 \sum_{i=1}^{3^{r-1}}m(P_i)=\tfrac12\ifmmode\ell\else\polishlcross\fieft(3^{r-2}-1\right).
  \end{equation}
  Thus, if one wanted to evenly redistribute the deficiencies $2^{-m(P_i)}$ occurring in Theorem \ref{Theorem ESz General_classic}(a) among \emph{all} collectable patterns, the share of $2^{\gamma_r}$ with
 \begin{equation}\ifmmode\ell\else\polishlcross\fiabel{gamma}
 \gamma_r=\frac{\frac12\ifmmode\ell\else\polishlcross\fieft(3^{r-2}-1\right)}{3^{r-1}}=\frac16-\frac1{2\cdot3^{r-1}}
  \end{equation}
  would seem fair. 
  Turning this utopian idea into reality is quite straightforward and, indeed, we can deduce from Theorem \ref{Theorem ESz General_classic}(a) the following, even more general corollary.

  \begin{cor}\ifmmode\ell\else\polishlcross\fiabel{Theorem ESz General_fair}
	For $r\ge 2$, let $P_1,\dots,P_{3^{r-1}}$ be all collectable patterns, and let positive integers $a_1,\dots, a_{3^{r-1}}$, as well as positive reals $c_1,\dots,c_{3^{r-1}}$ be given such that
$$\prod_{i=1}^{3^{r-1}}c_i=2^{-\sum_{i=1}^{3^{r-1}}m(P_i)}=2^{-(3^{r-2}-1)/2}.$$ If $n\ge\prod_{i=1}^{3^{r-1}}a_i+1$, then every $M_n^{(r)}$ contains, for some $i$, a $P_i$-clique of size  greater than $c_ia_i$. In particular,  one can take all $c_i=2^{-\gamma_r}$ (cf.~\eqref{gamma}), or, for any subset $I\subseteq[3^{r-1}]$ of size $|I|=\tfrac12\ifmmode\ell\else\polishlcross\fieft(3^{r-2}-1\right)$,
\[
c_i=
\begin{cases}
1/2\quad & \mbox{if}\quad i\in I\\
1 \quad & \mbox{otherwise.}
\end{cases}
\]
 \end{cor}
\noindent Both these special cases  show that the constant $2^{-r+2}$ in Corollary \ref{Theorem ESz General_diagonal}(a) can be vastly improved.

The  proof of Corollary \ref{Theorem ESz General_fair} is also quite elementary. It requires, however,   a shift from integer to real-valued parameters.
To this end, let us first restate Theorem \ref{Theorem ESz General_classic}(a). To allow parameters strictly smaller than one we adopt the convention that a single edge of an $r$-matching forms by itself a $P$-clique for any $r$-pattern $P$.

  \begin{thm}\ifmmode\ell\else\polishlcross\fiabel{Theorem ESz General_real}
	For $r\ge 2$, let $P_1,\dots,P_{3^{r-1}}$ be all collectable patterns and let positive real numbers $x_1,\dots, x_{3^{r-1}}$ be given. If $n>\prod_{i=1}^{3^{r-1}}x_i$, then every $M_n^{(r)}$ contains, for some $i$, a $P_i$-clique of size greater than
$x_i2^{-m(P_i)}.$
\end{thm}
  \begin{proof} Set $a_i=\ifmmode\ell\else\polishlcross\fifloor x_i\rfloor$, $i=1,\dots, 3^{r-1}$, and observe that $n\ge\prod_{i=1}^{3^{r-1}}a_i+1$. Thus, by Theorem~\ref{Theorem ESz General_classic}(a), for some $i$, there is a $P_i$-clique of size greater than $a_i2^{-m(P_i)}$, that is, of size at least $(a_i+1)2^{-m(P_i)}>x_i2^{-m(P_i)}$.
  \end{proof}
\noindent Inversely, by choosing integer values for the numbers $x_i$, Theorem \ref{Theorem ESz General_real} trivially implies Theorem \ref{Theorem ESz General_classic}(a). So, the two statements are actually equivalent.

 We may now easily deduce  Corollary \ref{Theorem ESz General_fair} from  Theorem \ref{Theorem ESz General_real}.

\begin{proof}[Proof of Corollary  \ref{Theorem ESz General_fair}]  Define
$x_i=c_i2^{m(P_i)}a_i$ and note that, by \eqref{summPi}
 $$\prod_{i=1}^{3^{r-1}}x_i=2^{(3^{r-2}-1)/2} \prod_i c_i\prod_i a_i=\prod_{i=1}^{3^{r-1}}a_i<n.$$
 Thus, we are in position to apply Theorem \ref{Theorem ESz General_real} to the $x_i$'s and conclude that, for some $i$, there is a $P_i$-clique of size greater than $x_i2^{-m(P_i)}=c_ia_i$.
 \end{proof}

 \subsection{Random matchings}

In the last part of this paper we consider a \emph{random}  $r$-matching $\mathbb{RM}^{(r)}_{n}$, that is, a matching picked uniformly at random from the set of all $\frac{(rn)!}{(r!)^n\, n!}$
matchings $M_n^{(r)}$ on the same vertex set~$[rn]$. We say that an event ${\mathcal A}_n$ holds \emph{asymptotically almost surely}, or shortly, \emph{a.a.s.}, if $\Pr({\mathcal A}_n)\to1$, as $n\to\infty$.

With respect to the  Erd\H os-Szekeres Theorem on monotone subsequences, it is well-known that a.a.s.\ a random permutation contains both, an increasing and a decreasing subsequence, of order $\Theta(\sqrt n)$. This, roughly, matches the order of a monotone subsequence guaranteed in every permutation. In \cite{DGR-match} we proved a similar result about  random 2-matchings.

\begin{thm}[\cite{DGR-match}]\ifmmode\ell\else\polishlcross\fiabel{thm:random2}
A.a.s.\ the size of the largest line,  stack, and  wave  in a random matching $\mathbb{RM}_n^{(2)}$ is~$\Theta(\sqrt n)$.
\end{thm}

Note that, this time, the size of the sub-structure expected in a random matching exceeds that guaranteed in  every matching (c.f. Theorem \ref{Theorem E-S for LSW} with $\ell=s=w=\ifmmode\ell\else\polishlcross\ficeil n^{1/3}\rceil-1$). This trend continues with $r$ growing.
Indeed, in Section~\ref{section:random} we show that, for \emph{every} collectable $r$-pattern $P$,  the largest size of a $P$-clique in $\mathbb{RM}_n^{(r)}$ exceeds substantially the size  guaranteed in the deterministic case by Corollary \ref{Theorem ESz General_diagonal}.

 \begin{thm}\ifmmode\ell\else\polishlcross\fiabel{thm:random}
Let $P$ be an arbitrary collectable $r$-pattern. Then, a.a.s.\ the size of the largest $P$-clique in a random $r$-matching $\mathbb{RM}^{(r)}_{n}$ is~$\Theta_r(n^{1/r})$.
\end{thm}
Here and throughout, we use notation $\Theta_r(.)$, $O_r(.)$, and $\Omega_r(.)$ to stress that the hidden constant depends on~$r$.

\@ifstar{\origsection*}{\@startsection{section}{1}\z@{.7\ifmmode\ell\else\polishlcross\fiinespacing\@plus\ifmmode\ell\else\polishlcross\fiinespacing}{.5\ifmmode\ell\else\polishlcross\fiinespacing}{\normalfont\scshape\centering\S}}{Proof of Theorem \ref{Theorem ESz General_classic}}\ifmmode\ell\else\polishlcross\fiabel{mainproof}

In this section, after some preparations, we prove Theorem \ref{Theorem ESz General_classic}.

\subsection{Collectable patterns}\ifmmode\ell\else\polishlcross\fiabel{char}

In Introduction we defined collectable and splittable patterns. Now we show that these two notions are equivalent. In fact, for any non-collectable pattern $P$, one cannot even construct a $P$-clique of order as small as three.

\begin{prop}\ifmmode\ell\else\polishlcross\fiabel{Proposition Collectable-Splitable}
	A pattern $P$ is collectable if and only if it is splittable. Moreover, if $P$ is unsplittable, then every $P$-clique has size at most two.
\end{prop}

\begin{proof}
	It is not hard to verify that every splittable pattern is collectable. Indeed, as demonstrated in Introduction, it suffices to replace every block of the splitting, which is always of the form $A^tB^t$ or $B^tA^t$, by, respectively, $A_1^t\cdots A_k^t$ or $A_k^t\cdots A_1^t$.

	Now, assume that $P$ is an unsplittable pattern and let $Q$ be the longest splittable prefix of $P$, that is $P=QS$, where $Q$ is a splittable word (possibly empty) of length $2q$, $q\ge0$, and $S$ begins, say, with a block $A^sB^tA$  where $s>t\ge1$.  So, among the first $2q+s+t$ letters of $P$,  the number of $A$'s, $q+s$, is greater than the number of $B$'s, $q+t$. Moreover, the same is true for the first $2q+2t$ letters of $P$, namely, there are $q+\min(s,2t)$ letters $A$ and $q+\max(2t-s,0)$ letters $B$ among them. These precise numbers are of no importance to us - all what matters in the argument below is that the two numbers are different. In summary:
\begin{equation}\ifmmode\ell\else\polishlcross\fiabel{Pprop}
\textit{the numbers of  $A$'s and $B$'s among the first $2q+2t$ letters of $P$ are \emph{not} the same.}
\end{equation}
	
	Suppose to the contrary that there is a $P$-clique $K$ with three edges $e_A$, $e_B$ and $e_C$ (in lexicographic order) represented in the word notation, respectively, by letters $A,B$ and $C$. 
We now examine separately the two subwords $e_A\cup e_B$ and $e_A\cup e_C$.
In view of the above observation, the number of $B$'s  among the first $2q+s+t$ letters of $e_A\cup e_B$ equals $q+t$ and, what is absolutely crucial, they all appear \emph{to the left of} the $(q+s+1)$-st letter $A$. Of course, the same is true for $e_A\cup e_C$\;: there are precisely  $q+t$ letters $C$ before the $(q+s+1)$-st letter $A$. Thus, scanning the whole word $K$, we see that there are exactly $q+t$ letters $B$ and $q+t$ letters $C$ prior to the $(q+s+1)$-st letter $A$.
This implies that among the first $2q+2t$ letters of the subword $e_B\cup e_C$, the number of $B$'s and $C$'s are the same (both equal $q+t$).  This, however, contradicts the property \eqref{Pprop} of $P$ observed earlier.

In the symmetric case when $S$ begins with a block $B^sA^tB$, we examine $e_A\cup e_C$ and $e_B\cup e_C$ first, obtaining the same contradiction for $e_A\cup e_B$.
\end{proof}

Next, using the above characterization, we enumerate the collectable $r$-patterns.
\begin{cor}
There are $3^{r-1}$ collectable patterns. Moreover, the total sum of their maturities equals $(3^{r-2}-1)/2$.
\end{cor}

\begin{proof} By Proposition \ref{Proposition Collectable-Splitable} we enumerate the splittable patterns instead. Let $P$ be a splittable $r$-pattern. Note that its partition into appropriate blocks $X_1,\ifmmode\ell\else\polishlcross\fidots, X_j$ is unique. Further,  the sizes $2s_i:=|X_i|$, $i=1,\dots,j$, of the partition blocks are determined by  ordered partitions  of $r=s_1+\dots+s_j$ into $j$  integer parts $s_i\ge1$ (which are then doubled). Finally, given such a partition,  a splittable pattern is obtained by deciding for each $i=2,\dots,j$,  which letter, $A$ or $B$, goes first in block $X_i$. (Block $X_1$ has to begin with $A$.) As there are $\mathrm{Bin}om{r-1}{j-1}$ such partitions, we infer that the number of splittable, and thus collectable $r$-patterns  equals
$$\sum_{j=1}^r\mathrm{Bin}om{r-1}{j-1}2^{j-1}=3^{r-1}.$$

For the second assertion,  let the last block in the splittable  partition of $P$ be $A^tB^t$, with $3\ifmmode\ell\else\polishlcross\fieq t\ifmmode\ell\else\polishlcross\fieq r$ (for $t=1$ and $t=2$, $m(P)=0$). Then, by the above, there are $3^{r-t-1}$ collectable patterns with this ending block and the same number of them in the symmetric case when $P$ ends with  $B^tA^t$, except for $t=r$. Thus, there are exactly $2\cdot 3^{r-t-1}$ patterns with maturity $t-2$, for each $3\ifmmode\ell\else\polishlcross\fieq t \ifmmode\ell\else\polishlcross\fieq r-1$, and one with maturity $r-2$. In consequence, the total sum of maturities equals
$$(r-2)+2\cdot\sum_{t=3}^{r-1}(t-2)\cdot 3^{r-t-1}=(r-2)+2\cdot\sum_{m=1}^{r-3}m\cdot 3^{r-m-3}=\frac{1}{2}\cdot (3^{r-2}-1),$$

since $\sum_{m=1}^{r-3}m\cdot 3^{-m}=\frac{3}{4}\cdot [(3-2r) 3^{2-r}+1]$ (see, e.g.,\ identity (2.26) in~\cite{Concrete}).
\end{proof}

\subsection{Pattern decompositions and $P$-families}\ifmmode\ell\else\polishlcross\fiabel{pat_decomp}
In this subsection we define a  decomposition of patterns that will play a crucial role in the proof of our main result.

 Given an $r$-pattern $P$,  let $Q:=Q(P)$ denote the $(r-1)$-pattern obtained form $P$ by dropping the last letter $A$ and the last letter $B$, and let $R:=R(P)$ be the 2-pattern formed by the last two letters $A$ and the last two letters $B$ of $P$. Then we write $P=Q\oplus R$. For example, if $P=AABABBAB$, then $P=Q\oplus R$, where $Q=AABABB$ and $R=ABAB$. 
We call $Q$ and $R$,  \emph{the (resp., left and right) parents} of $P$, while $P$ is dubbed \emph{a child} of $Q$ and $R$ (see Fig.\ \ref{ESZ5}).

Recall that there are only three possible right parents, an alignment $R_1=AABB$, a nesting $R_2=ABBA$, and a crossing $R_3=ABAB$. However,  they may sometimes appear in the dual form of, resp.,  $BBAA$, $BAAB$, and $BABA$, forced by the ordering of the letters in the  child (precisely, whenever the penultimate occurrence of letter $A$ is to the right of the penultimate occurrence of letter $B$, or, equivalently, whenever the left parent ends with $A$).

\begin{figure}
\caption{Decomposition of $AABABBAB$ into the left parent (blue) and the right parent (dashed red): $AABABBAB=AABABB\oplus ABAB$.}
\end{figure}

Clearly, for every pattern $P$ its parents are determined uniquely. In other words, $\oplus$ is a function. However, it is not an injection: a pair of parents may ``give birth'' to more than one child. For $r=3$ we have just one such instance: $P_1=AAABBB=AABB\oplus AABB$ and $P_1^*=AABABB=AABB\oplus AABB$ (see Table \ref{table:relations}). For $r=4$, the parents $Q=AAABBB$ and $R=AABB$ have three children, $P_1=AAAABBBB$, $P_1^*=AAABABBB$, and $P_1^{**}=AAABBABB$, and there are three more sets of siblings, each with two elements (see Table \ref{table:patterns4}, where the alternative notation $P_{xyz}$ points to the left parent $P_{xy}$, as given in Table \ref{table:relations}, and the right parent encoded by $z$). Children of the same parents, if more than one, are called  \emph{siblings}.

Notice also that each of the $3\cdot9=27$ pairs of collectable parents listed in Table \ref{table:patterns4} has exactly one collectable child. When this unique collectable child has siblings, it will be termed \emph{ big brother}.

\afterpage{
\begin{longtable}{ |l||c||c| }
	\hline
	\textsc{pattern}& \textsc{in words} & \textsc{operation $\oplus$}\\
	\hline
	\hline
 $P_1=P_{\ell,\ell,\ell}$ $(bb)$& $|AAAABBBB|$ & $AAABBB\oplus AABB$\\
	\hline
	 $P_1^*=P^*_{\ell,\ell,\ell}$ & $AAABABBB$ &  $AAABBB\oplus AABB$\\
	\hline
	 $P_1^{**}=P^{**}_{\ell,\ell,\ell}$ & $AAABBABB$ &  $AAABBB\oplus AABB$\\
\hline
	 $P_{2}=P_{\ell,\ell,s}$ & $|AAABBB|BA|$ &  $AAABBB\oplus ABBA$\\
\hline
	 $P_{3}=P_{\ell,\ell,w}$ & $|AAABBB|AB|$ & $AAABBB\oplus ABAB$\\
	\hline
	\hline
	 $P_4=P_{\ell,s,\ell}$ & $|AABB|BBAA|$ &  $AABBBA\oplus BBAA$\\
\hline
	 $P_{5}=P_{\ell,s,s}$ & $|AABB|BA|AB|$ & $AABBBA\oplus BAAB$\\
\hline
	 $P_{6}=P_{\ell,s,w}$ & $|AABB|BA|BA|$ &  $AABBBA\oplus BABA$\\
\hline
	\hline
	 $P_7=P_{\ell,w,\ell}$ & $|AABB|AABB|$ &  $AABBAB\oplus AABB$\\
\hline
	 $P_{8}=P_{\ell,w,s}$ & $|AABB|AB|BA|$ & $AABBAB\oplus ABBA$\\
\hline
	 $P_{9}=P_{\ell,w,w}$ & $|AABB|AB|AB|$ &  $AABBAB\oplus ABAB$\\
\hline
	\hline
	 $P_{10}=P_{s,\ell,\ell}$ $(bb)$& $|AB|BBBAAA|$ &  $ABBBAA\oplus BBAA$\\
	\hline
	 $P_{10}^*=P^*_{s,\ell,\ell_1}$ & $ABBBABAA$ &  $ABBBAA\oplus BBAA$\\
\hline
	 $P_{11}=P_{s,\ell,s}$ & $|AB|BBAA|AB|$ & $ABBBAA\oplus BAAB$\\
\hline
	 $P_{12}=P_{s,\ell,w}$ & $|AB|BBAA|BA|$ &  $ABBBAA\oplus BABA$\\
\hline
\hline
	 $P_{13}=P_{s,s,\ell}$ & $|AB|BA|AABB|$ &  $ABBAAB\oplus AABB$\\
\hline
	 $P_{14}=P_{s,s,s}$ & $|AB|BA|AB|BA|$ & $ABBAAB\oplus ABBA$\\
\hline
	 $P_{15}=P_{s,s,w}$ & $|AB|BA|AB|AB|$ &  $ABBAAB\oplus ABAB$\\
\hline
\hline
	 $P_{16}=P_{s,w,\ell}$ & $|AB|BA|BBAA|$ & $ABBABA\oplus BBAA$\\
\hline
	 $P_{17}=P_{s,w,s}$ & $|AB|BA|BA|AB|$ &  $ABBABA\oplus BAAB$\\
\hline
	 $P_{18}=P_{s,w,w}$ & $|AB|BA|BA|BA|$ &  $ABBABA\oplus BABA$\\
\hline
	\hline
 $P_{19}=P_{w,\ell,\ell}$ $(bb)$ & $|AB|AAABBB|$ & $ABAABB\oplus AABB$\\
	\hline
	 $P_{19}^*=P^*_{w,\ell,\ell}$ & $ABAABABB$ & $ABAABB\oplus AABB$\\
	\hline
	 $P_{20}=P_{w,\ell,s}$ & $|AB|AABB|BA|$ &  $ABAABB\oplus ABBA$\\
	\hline
	 $P_{21}=P_{w,\ell,w}$ & $|AB|AABB|AB|$ &  $ABAABB\oplus ABAB$\\
\hline
\hline
	 $P_{22}=P_{w,s,\ell}$ & $|AB|AB|BBAA|$ &  $ABABBA\oplus BBAA$\\
\hline
	 $P_{23}=P_{w,s,s}$ & $|AB|AB|BA|AB|$ & $ABABBA\oplus BAAB$\\
\hline
	 $P_{24}=P_{w,s,w}$ & $|AB|AB|BA|BA|$ &  $ABABBA\oplus BABA$\\
\hline
\hline
	 $P_{25}=P_{w,w,\ell}$ & $|AB|AB|AABB|$ &  $ABABAB\oplus AABB$\\
	\hline
	 $P_{26}=P_{w,w,s}$ & $|AB|AB|AB|BA|$ & $ABABAB\oplus ABBA$\\
\hline
	 $P_{27}=P_{w,w,w}$ & $|AB|AB|AB|AB|$ &  $ABABAB\oplus ABAB$\\
\hline
\hline
	 $\bar P_{\ell,\ell,\ell}$ & $AABAABBB$ &  $AABABB\oplus AABB$\\
	\hline
	 $\bar P^*_{\ell,\ell,\ell}$ & $AABABABB$ & $AABABB\oplus AABB$\\
	\hline
	 $\bar P_{\ell,\ell,w}$ & $AABABBAB$ &  $AABABB\oplus ABAB$\\
	\hline
	 $\bar P_{\ell,\ell,s}$ & $AABABBBA$ &  $AABABB\oplus ABBA$\\
	\hline
	\caption{All 35 patterns of two quadruples  and their corresponding decompositions via operation $\oplus$. They are organized into 10 groups by the patterns of their left parents, while the alternative notation $P_{xyz}$ encodes the pattern's parents (cf.\ Table \ref{table:relations}).  Big brothers are marked with $(bb)$, their siblings with $^*$, while other non-collectable patterns (i.e., those whose left parents are non-collectable too) are put at the end, unnumbered, and marked with $\;\bar{}$.}
	\ifmmode\ell\else\polishlcross\fiabel{table:patterns4}
\end{longtable}
}

We collect all essential properties of (the inverse of) operation $\oplus$ in Proposition \ref{Proposition Big Brother} below.
Let $t(Q)$ denote the length of the last (maximal) run in $Q$. Note that $t(Q)\ge1$ and, whenever $t(Q)\ge2$, we have $t(Q)=m(Q)+2$.

\begin{prop}\ifmmode\ell\else\polishlcross\fiabel{Proposition Big Brother} Let $r\ge 3$ and $Q$ be a collectable $(r-1)$-pattern. Then
\begin{itemize}
\item[(i)] for each $j=2,3$, the pair $Q,R_j$ has only one child, and the same is true for the pair $Q,R_1$ provided $t(Q)=1$; moreover, the only child is collectable;
\item[(ii)]  if $t(Q)\ge2$, then the pair $Q,R_1$ has $t(Q)$ children, only one of which, the big brother, is collectable; moreover,  the maturity of the big brother equals $t(Q)-1=m(Q)+1$.
\end{itemize}
\end{prop}

\begin{proof} Assume that $t(Q)=t$ and, w.l.o.g., $Q$ ends with letter $B$, that is, $Q=Q'A^tB^t$, for some $t\geq 1$, where $Q'$ is a collectable $(r-1-t)$-pattern.  The reasoning in the symmetric case (when $Q$ ends with letter $A$) follows mutatis mutandis; in particular, with right parents in the dual form.
	
To produce any child of the pair $(Q,R_j)$, $j=1,2,3$, one has to attach the 2-pattern $R_j$  to the back of $Q$ so that applying operation $\oplus$ to the resulting $r$-pattern would yield back the parents $Q$ and $R_j$. More precisely, one has to identify the first $A$ and the first $B$ of $R_j$ with the last $A$ and the  last $B$ of $Q$, respectively, and then locate the second $A$ and the second $B$ of $R_j$ accordingly to pattern $R_j$. It is not hard to check that for $j\in\{2,3\}$ there is only one way to perform this operation, as illustrated in Fig.\ \ref{ESZ6}, and that we always have $Q\oplus R_2=QAB$ and $Q\oplus R_3=QBA$.

\begin{figure}
\caption{The only children of $Q$ with $ABAB$ and with $ABBA$.}
\end{figure}

There is also a unique outcome whenever  $j=t=1$, but in this case we have $Q\oplus R_1=Q'AABB$ (see Fig.\ \ref{ESZ13}).
This proves part (i) of the proposition.

\begin{figure}
\caption{The only child of $Q$ with $AABB$ when $t=1$.}
\end{figure}

Now assume that $R=R_1$ and $t\ge2$. Obviously the second $B$ of $R_1$ must be attached at the very end of $Q$. However, the second $A$ of $R_1$ may be located either right before the ending run $B^t$, or somewhere within it, as long as the child ends with a run of at least two $B$'s. This brings  exactly $t$ different $r$-patterns -- all children of $Q$ and $R_1$ (see Fig.\ \ref{ESZ7}).

\begin{figure}
\caption{Extending the last block of $Q$ by $AABB$ ($t=3$).}
\end{figure}
Formally,
\begin{equation}\ifmmode\ell\else\polishlcross\fiabel{children}
Q\oplus AABB\in\{Q'A^{t}B^{t_1}AB^{t_2}:\quad t_1+t_2=t+1,\; t_1\geq 0,\;t_2\geq 2\}.
\end{equation}
Among these children only the  one with $t_1=0$ (and thus, $t_2=t+1$) is collectable, because $Q'$ is. Moreover, its maturity equals $t+1-2=t-1=m(Q)+1$.  For $t_1\ge1$, there is a block $BAB^{t_2}$ at the end with $t_2\geq 2$, which excludes splittability, and thus collectability (cf.\ Proposition \ref{Proposition Collectable-Splitable}). In the symmetric case, when $Q$ ends with an $A$, the siblings are of the form $Q'B^{t}A^{t_1}BA^{t_2}$. This completes the proof of part (ii).
\end{proof}

In view of Proposition \ref{Proposition Big Brother}, we may classify all collectable patterns into two categories: those that are the only child of their parents and those that have some \emph{siblings}. In the latter case, as it was already mentioned earlier, we call them \emph{big brothers} (see Table \ref{table:patterns4} where three big brothers are marked by (bb)). It follows from  Proposition \ref{Proposition Big Brother}(ii) that a big brother $P$ has a positive maturity $m(P)$ equal to the number of its siblings. For instance, the pattern $P_1=AAAABBBB$ with $m(P_1)=2$ is a big brother with two siblings, $P_1^*=AAABABBB$ and $P_1^{**}=AAABBABB$. It can be easily calculated that, for $r\ge3$, the number of big brothers among collectable $r$-patterns is $3^{r-3}$.

A big brother $P$ together with all its siblings constitute  \emph{a $P$-family}. A $\emph{$P$-family-clique}$ is a matching whose every pair of edges forms a pattern belonging to the $P$-family. Our next result states that at least a half of any $P$-family-clique  makes up a  $P$-clique. The special case of $r=3$  was already proved in \cite[Prop. 2.4]{DGR-match}.

\begin{prop}\ifmmode\ell\else\polishlcross\fiabel{Proposition P-family-clique}
 For $r\ge3$, let an $r$-pattern $P$ be a big brother. Then every  $P$-family-clique of size $k$ contains a  $P$-clique of size at least $k/2$.
\end{prop}

\begin{proof}
  Let an $r$-pattern $P$ be a big brother  and let an $r$-matching $K$ be a $P$-family-clique of size $k$. Assuming first that $P$ ends with a $B$, by \eqref{children}, the last segments of $P$ and its siblings are of the form
 $A^{t}B^{t_1}AB^{t_2}$, where $0\ifmmode\ell\else\polishlcross\fie t_1\ifmmode\ell\else\polishlcross\fie m(P)$ and $t_1+t_2=m(P)+2\ge3$ (and $t_1=0$ corresponds to the big brother).  A crucial observation is that in each of these patterns there are exactly $m(P)+2$ letters $B$ to the right of the penultimate letter $A$.

 Let us set $P^{0}:=P$ and denote other siblings by $P^{t_1}$, $t_1=1,\dots,m(P)$.
 We may represent $K$ by an auxiliary  colored complete graph $G_K$ whose vertex set is $K$ and whose edges (that is, pairs of edges of $K$) are colored by the patterns they form, or equivalently, by integers $t_0=0,1,\dots,m(P)$, which uniquely represent the big brother and the siblings.

 We are going to show that the spanning subgraph $G^*_K$ of $G_K$ formed by the edges colored by colors $1,\dots,m(P)$ (excluding color 0), is a linear forest, that is, each of its connected components is a path. This, in particular, would mean that $G^*_K$
 is bipartite. Therefore, its complement, that is, the spanning subgraph of $G_K$ consisting exclusively of edges colored by color 0 would contain a clique on at least $k/2$ vertices, a property we want to prove.

Let us number the edges $e_1,e_2,\ifmmode\ell\else\polishlcross\fidots, e_k$  of $K$ according to the linear order of their leftmost vertices. We will demonstrate that
\begin{equation}\ifmmode\ell\else\polishlcross\fiabel{ijh}
\forall\; i<j<h\;:\quad e_ie_j\in G^*_K\;\quad\Rightarrow\;\quad e_ie_h\not\in G^*_K\;,
 \end{equation}
 so each vertex of $G^*_K$ has at most one neighbor to the right.
 Similarly, we will show that
 \begin{equation}\ifmmode\ell\else\polishlcross\fiabel{ijh'}
\forall\; i<j<h\;:\quad e_je_h\in G^*_K\;\quad\Rightarrow\;\quad e_ie_h\not\in G^*_K\;,
 \end{equation}
 so each vertex of $G^*_K$ has also at most one neighbor to the left.
 Both,\; \eqref{ijh} and~\eqref{ijh'} imply that, indeed, $G^*_K$ is a linear  forest (in fact, the paths of this linear forest follow the initial order of vertices, though, we do not need this extra property here).

To prove \eqref{ijh}, consider three  edges $e_i$, $e_j$, and $e_h$ of $K$ to which we associate letters  $A$, $B$, and $C$, respectively. Let $e_i$ and $e_j$ form a pattern $P^{t_1}$, which ends in $AB^{t_1}AB^{t_2}$ and, suppose to the contrary, that $e_i,e_h$ form a pattern $P^{t_1'}$, which ends in $AC^{t'_1}AC^{t'_2}$, where $t_1,t_1'\ge1$, $t_2,t_2'\ge2$, and $t_1+t_2=t_1'+t_2'=m(P)+2$.
But then, after the last occurrence of $A$, there are precisely $t_2$ letters $B$ and $t_2'$ letters $C$, where $t_2,t_2'\ifmmode\ell\else\polishlcross\fie m(P)+1$. This means, in particular, that after the penultimate $B$ there are fewer than $m(P)+2$ letters $C$ (and vice versa), which implies that the $B$'s and the $C$'s, or $e_j$ and $e_h$, cannot form any pattern belonging to the $P$-family, a contradiction with the definition of~$K$.

The proof of \eqref{ijh'}  is even simpler. Assuming that the pairs $(e_j,e_h)$ and $(e_i,e_h)$ form patterns ending with, resp., $BC^{t_1}BC^{t_2}$ and $AC^{t_1'}AB^{t_2'}$, we see that the $A$'s and $B$'s form a pattern, which ends with $AB$ or $BA$, either excluding this pair from $K$, a contradiction again.

In the symmetric case when $P$ ends with $B^{t}A^{t_1}BA^{t_2}$, the proofs of \eqref{ijh} and \eqref{ijh'} are the same, except they swap. Indeed, the assumption that both, $(e_i,e_j)$ and $(e_i,e_h)$, belong to $G^*_K$, implies that we have $BA^{t_1}BA^{t_2}$ and $CA^{t_1}CA^{t_2}$ and so, the pattern of $B$'s and $C$"s ends with $BC$ or $CB$, a contradiction. Similarly, if both, $(e_j,e_h)$ and $(e_i,e_h)$, belong to $G^*_K$, then we have the ending
$CB^{t_1}CB^{t_2}$ and $CA^{t_1}CA^{t_2}$, implying that  after the penultimate $A$ there are fewer than $m(P)+2$ letters $B$ (and vice versa), a contradiction again.
\end{proof}

\subsection{The  inductive  proof}\ifmmode\ell\else\polishlcross\fiabel{section:hyper_new}

The proof of Theorem \ref{Theorem ESz General_classic} is by induction on $r$ with the base case of $r=2$ holding by Theorem \ref{Theorem E-S for LSW} from \cite{DGR-match}. For the sake of completeness, we have reproved it in Appendix~\ref{appendix}. For part (a), we found it convenient to prove the equivalent statement which uses real-valued parameters, that is, Theorem \ref{Theorem ESz General_real}.

\begin{proof}[Proof of Theorem \ref{Theorem ESz General_real}]
	Let $r\geq3$ and assume that the statement is true for $r-1$. Let $x_1,\ifmmode\ell\else\polishlcross\fidots, x_{3^{r-1}}$ be positive real numbers and let $n>\prod_{i=1}^{3^{r-1}}x_i$ be an integer. Let $P_1,P_2,\ifmmode\ell\else\polishlcross\fidots, P_{3^{r-1}}$ be all collectable patterns of uniformity $r$ and let $Q_1,Q_2,\ifmmode\ell\else\polishlcross\fidots, Q_{3^{r-2}}$ be all collectable patterns of uniformity $r-1$. We  assume, for convenience, that this enumeration is chosen, as in Tables 1 and 2, so that $P_{3(i-1)+j}=Q_i\oplus R_j$, where $R_1=AABB$, $R_2=ABBA$, and $R_3=ABAB$ (or their dual versions). Let us also define $y_i=\prod_{j=1}^{3}x_{3(i-1)+j}$ for all $i=1,2,\ifmmode\ell\else\polishlcross\fidots,3^{r-2}$. Notice that $\prod_{i=1}^{3^{r-2}}y_i=\prod_{i=1}^{3^{r-1}}x_i<n$.
	
	Consider  a matching $M:=M_n^{(r)}$. Let $M_1$ be the $(r-1)$-matching  obtained from $M$ by deleting the last vertex of every edge. Thus, $M_1$ is an $M_n^{(r-1)}$. Apply the induction hypothesis to $M_1$ with the patterns $Q_i$ and the numbers $y_i$, $i=1,\dots,3^{r-2}$, defined above, obtaining, for some $i$, a $Q_i$-clique $K_i$ in $M_1$ of size $q_1>y_i/2^{m(Q_i)}$.
	
	Let us look now at the 2-matching $M_2$ formed by the pairs of the last two vertices of all edges of $M$ whose set of the first $r-1$ vertices belongs to $K_i$. Formally,
$$M_2=\big{\{}\{i_{r-1},i_r\}:\; \{i_1<\cdots<i_r\}\in M\quad\mbox{and}\quad \{i_1,\dots,i_{r-1}\}\in K_i\big{\}}.$$
Clearly, $M_2$ is an $M_{q_1}^{(2)}$ and we may apply to it the case $r=2$ of Theorem \ref{Theorem ESz General_real} with
$$z_1=x_{3(i-1)+1}/2^{m(Q_i)}\quad\mbox{and}\quad z_j=x_{3(i-1)+j}\quad\mbox{for}\quad j=2,3$$
(note that $q_1>z_1z_2z_3$). Hence, for some $j\in \{1,2,3\}$, we get an $R_j$-clique $L_j$ in $M_2$ of size $q_2>z_j$.
	
Let us now extend the edges of $L_j$ back to the original $r$-edges of $M$, obtaining  a sub-matching $M_3$ of $M$ of size $q_2$.
Formally,
$$M_3=\big{\{}\{i_1<\cdots<i_r\}\in M:\;\{i_1,\dots,i_{r-1}\}\in K_i\quad\mbox{and}\quad\{i_{r-1},i_r\}\in L_j\big{\}}.$$

By the definition of operation $\oplus$, every pair of edges in $M_3$ forms a pattern $P$ which decomposes into $Q_i\oplus R_j$. Assume first that $j\in\{2,3\}$ or $j=1$ but then $t(Q_i)=1$ and thus, $m(Q_i)=0$. In all these three cases, by our enumeration scheme defined at the beginning of the proof, $P=P_{3(i-1)+j}$; moreover, by Proposition \ref{Proposition Big Brother}(i), the pattern $P$ is unique and, consequently, $M_3$ forms a $P$-clique of size  $q_2>z_j=x_{3(i-1)+j}$.

 In the remaining case, when $j=1$ and $t(Q_i)\ge2$, by Proposition \ref{Proposition Big Brother},  $P$ is a big brother with $m(P)=t(Q_i)-1=m(Q_i)+1$. Then $M_3$ is a $P$-family-clique of size $q_2>z_1$. By Proposition \ref{Proposition P-family-clique}, $M_3$ contains a $P$-clique of size at least $$q_2/2>z_1/2=x_{3(i-1)+1}/2^{m(Q_i)+1}=x_{3(i-1)+1}/2^{m(P)},$$
 which completes the proof.
\end{proof}

The proof of part (b) of Theorem \ref{Theorem ESz General_classic} is very similar and even simpler, as there is no reason to resort to the real-valued version. Moreover, for clean $M_n^{(r)}$ we do not need to worry about the maturities and the case $j=1$, $t(Q_i)\ge2$, is vacuous. For the induction step, however, it is crucial to observe that if $M:=M_n^{(r)}$ is clean, then so is $M_1$ -- the $(r-1)$-matching  obtained from $M$ by deleting the last vertex of every edge. Indeed, removing the last $A$ and the last $B$ from a splittable $r$-pattern results, obviously, in a splittable $(r-1)$-pattern.

\@ifstar{\origsection*}{\@startsection{section}{1}\z@{.7\ifmmode\ell\else\polishlcross\fiinespacing\@plus\ifmmode\ell\else\polishlcross\fiinespacing}{.5\ifmmode\ell\else\polishlcross\fiinespacing}{\normalfont\scshape\centering\S}}{Proof of Theorem \ref{thm:random}}\ifmmode\ell\else\polishlcross\fiabel{section:random}
In this section we prove Theorem \ref{thm:random} which provides estimates of the  size of the largest $P$-cliques one can find in a \emph{random} ordered $r$-uniform matching.
Recall that $\mathbb{RM}^{(r)}_{n}$ denotes a random  (ordered) $r$-matching of size $n$, that is, an $r$-matching  picked uniformly at random out of the set of all
\[
\alpha^{(r)}_n:=\frac{(rn)!}{(r!)^n\, n!}
\]
matchings $M_n^{(r)}$ on the set $[rn]$. There are two more equivalent ways of drawing $\mathbb{RM}^{(r)}_{n}$, \emph{the permutational scheme} and \emph{the online scheme}.

 The formula for $\alpha^{(r)}_n$ indicates that each ordered matching can be coupled with exactly $(r!)^n n!$ permutations. Indeed, one can generate an ordered matching by the following permutational scheme. Let $\pi$ be a permutation of $[rn]$. Now $\pi$ can be chopped off into an $r$-matching $\{\pi(1)\dots\pi(r), \pi(r+1)\dots\pi(2r),\dots,\pi(rn-r-1)\dots\pi(rn)\}$ and, clearly, there are exactly $(r!)^n n!$ permutations $\pi$ yielding the same matching. This scheme  allows one to use concentration inequalities for random permutations in the context of random matchings (see Subsection \ref{lb-gen}).

The online scheme of generating $\mathbb{RM}^{(r)}_{n}$ goes as follows. Given an arbitrary ordering of the vertices $u_1,\dots,u_{rn}$ (not necessarily the same as the canonical ordering $1,2,\dots,rn$) one selects uniformly at random   an $(r-1)$-element set $\{u_{j_1},\dots,u_{j_{r-1}}\}$ (in $\mathrm{Bin}om{rn-1}{r-1}$ ways) to be matched with $u_1$. Then, after crossing out $u_1,u_{j_1},\dots,u_{j_{r-1}}$ from the list, one selects uniformly at random an  $(r-1)$-element set (in $\mathrm{Bin}om{rn-r-1}{r-1}$ ways) to be matched with the first  uncrossed vertex, and so on, and so forth. Note that the total number of ways to select an $r$-matching this way is
\begin{align*}
	\mathrm{Bin}om{rn-1}{r-1} &\mathrm{Bin}om{rn-r-1}{r-1}\cdots \mathrm{Bin}om{2r-1}{r-1} \mathrm{Bin}om{r-1}{r-1}\\
	&= \frac{(rn-1)!}{(r-1)!(rn-r)!} \cdot \frac{(rn-r-1)!}{(r-1)!(rn-2r)!} \cdots \frac{(2r-1)!}{(r-1)! r!}\cdot \frac{(r-1)!}{(r-1)! 0!}\\
	&= \frac{(rn-1)!}{(r-1)!(rn-r)} \cdot \frac{1}{(r-1)!(rn-2r)} \cdots \frac{1}{(r-1)! r} \cdot \frac{1}{(r-1)!}\\
	&= \frac{(rn-1)!}{r!(n-1)} \cdot \frac{1}{r!(n-2)} \cdots \frac{1}{r! \cdot 1} \cdot \frac{1}{(r-1)!}
	= \frac{(rn-1)!}{(r!)^{n-1} (n-1)!} \cdot \frac{1}{(r-1)!},
\end{align*}
which equals $\alpha^{(r)}_n$ as it should. This scheme comes handy when estimating probabilities of events involving small sets of fixed vertices (see Subsections \ref{lb-gen} and \ref{lb-lines}).

\subsection{Upper bound}

We begin with a general upper bound. This result was already stated in \cite{DGR-match} but here we present it again for the sake of completeness. Below, notation $M_k^{(r)}$ stands for a fixed ordered $r$-matching on vertex set $[rk]$, and not to represent any such matching as in the previous sections.
\begin{lemma}\ifmmode\ell\else\polishlcross\fiabel{lem:upbr}
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:\; \mathbb{RM}^{(r)}_n \text{ contains a copy of } M^{(r)}_k \}\ifmmode\ell\else\polishlcross\fie (1+o(1))\frac{e}{r}(r!n)^{1/r}.
\]
\end{lemma}

\begin{proof} With some foresight, we set $k_0=\ifmmode\ell\else\polishlcross\fifloor (1+n^{-1/(r+1)})\frac{e}{r}(r!n)^{1/r}\rfloor$. For each $k\ge k_0$, let $X^{(r)}_k$ be the number of ordered copies of $M^{(r)}_k$  in $\mathbb{RM}^{(r)}_n$. In order to compute the expectation of $X^{(r)}_k$, one has to choose a set $S$ of $rk$ vertices (out of all $rn$ vertices) on which a copy $M^{(r)}_k$ will be planted. Formally, for each $S\in\mathrm{Bin}om{[rn]}{rk}$ define an indicator random variable $I_S=1$ if there is a   copy of $M^{(r)}_k$ on $S$ in $\mathbb{RM}^{(r)}_n$, and $I_S=0$ otherwise. As there is just one way to plant a copy of $M^{(r)}_k$ on a given set $S$, we have  $X^{(r)}_k=\sum_SI_S$. For the same reason,
$$\E I_S = \Pr(I_S=1)=\frac{\alpha^{(r)}_{n-k}}{\alpha^{(r)}_n}.$$
Thus, by the linearity of expectation,
	\[
	\E X^{(r)}_k = \mathrm{Bin}om{rn}{rk} \cdot 1 \cdot \frac{\alpha^{(r)}_{n-k}}{\alpha^{(r)}_n}
	= \frac{(r!)^k}{(rk)!} \cdot \frac{n!}{(n-k)!}
	\ifmmode\ell\else\polishlcross\fie \frac{(r!)^k}{(rk)!} \cdot n^k
	\ifmmode\ell\else\polishlcross\fie \frac{(r!)^k}{(rk/e)^{rk}} \cdot n^k
	= \ifmmode\ell\else\polishlcross\fieft( \frac{e^r r! n}{(rk)^r} \right)^k,
	\]
	which, by union bound and Markov's inequality,  implies that
	\[
	\Pr(\mathrm{ex}ists\, k\ge k_0:\; X^{(r)}_k>0)
	\ifmmode\ell\else\polishlcross\fie \sum_{k=k_0}^{n} \ifmmode\ell\else\polishlcross\fieft( \frac{e^r r! n}{(rk)^r}\right)^k
	\ifmmode\ell\else\polishlcross\fie n(1+n^{-1/(r+1)})^{-rk_0} = o(1),
	\]
which completes the proof.
\end{proof}

Notice that the above lemma implies, in particular, that for any  collectable pattern $P$ the maximum size of a $P$-clique in $\mathbb{RM}^{(r)}_n$ is a.a.s.\ $O_r(n^{1/r})$. (Recall than non-collectable patterns cannot form cliques larger than two.) In the next subsection we will prove the corresponding lower bound (as promised by Theorem~\ref{thm:random}).

\subsection{Lower bound -- general}\ifmmode\ell\else\polishlcross\fiabel{lb-gen}
In this subsection we prove Theorem~\ref{thm:random} for all collectable patterns $P$. 
We start with a straightforward estimate which generalizes one from \cite{ConlonFoxSudakov}, though with a worse constant.
For given disjoint subsets $A_1,\dots,A_r \subseteq [rn]$ we say that an $r$-edge $e$ \emph{spans} these sets if $|e\cap A_i|=1$ for each $1\ifmmode\ell\else\polishlcross\fie i\ifmmode\ell\else\polishlcross\fie r$ (see Fig.\ \ref{span}).

\begin{figure}
\caption{An edge spanning three sets.}
\end{figure}

\begin{lemma}\ifmmode\ell\else\polishlcross\fiabel{lemma:span_prob} Given integers $r\ge2$ and  $2r\ifmmode\ell\else\polishlcross\fie t\ifmmode\ell\else\polishlcross\fie n$,
	let $A_1,\dots,A_r$ be disjoint subsets of $[rn]$ each of size $t$. Then, the probability that there are no edges in $\mathbb{RM}^{(r)}_{n}$ spanning all these sets is at most $\mathrm{ex}p\ifmmode\ell\else\polishlcross\fieft\{-\frac{1}{(2r)^r} \cdot \frac{t^r}{n^{r-1}}\right\}$.
\end{lemma}

\begin{proof} Let $\mathcal E$ be the event that no edge in $\mathbb{RM}^{(r)}_{n}$ spans the sets  $A_1,\dots,A_r$.
	 We will  generate $\mathbb{RM}^{(r)}_{n}$ using the online scheme with the vertices of $A_1$ coming first. We denote by $e_1,e_2,\dots$ the edges drawn randomly along this scheme. Let $t'=\ifmmode\ell\else\polishlcross\ficeil t/(2r)\rceil$ and ${\mathcal E}_i$, $1\ifmmode\ell\else\polishlcross\fie i\ifmmode\ell\else\polishlcross\fie t'$, be the event that $e_i$ does not span  $A_1,\dots,A_r$. Then, by the chain formula,
\begin{equation}\ifmmode\ell\else\polishlcross\fiabel{PPP}
\Pr(\mathcal E)\ifmmode\ell\else\polishlcross\fie\Pr\ifmmode\ell\else\polishlcross\fieft(\bigcap_{i=1}^{t'}{\mathcal E}_i\right)=\Pr({\mathcal E}_1)\Pr({\mathcal E}_2|{\mathcal E}_1)\cdots\Pr\ifmmode\ell\else\polishlcross\fieft({\mathcal E}_{t'}\Big|\bigcap_{i=1}^{t'-1}{\mathcal E}_i\right).
\end{equation}

Let $a_1\in A_1$ be the first vertex to get its match in the online scheme. There are exactly $t^{r-1}$ $r$-element sets of vertices containing $a_1$ which do span the sets $A_1,\dots,A_r$. Thus, the probability that $e_1$ is not any of them
is exactly
	\[
	\Pr({\mathcal E}_1)=1-\frac{t^{r-1}}{\mathrm{Bin}om{rn-1}{r-1}}.
	\]

	Let $a_2$ be the first vertex in $A_1\setminus e_1$. Since  $|A_i\cap e_1|<r$ for each $i=2,\dots,r$, the number of $r$-element sets of vertices containing $a_2$, disjoint from $e_1$, and spanning the sets $A_1,\dots,A_r$ is still greater than $(t-r)^{r-1}$. Thus,

	\[
	\Pr({\mathcal E}_2|{\mathcal E}_1)<1-\frac{ (t-r)^{r-1}}{\mathrm{Bin}om{rn-r-1}{r-1}}.
	\]

	We repeat this process $t'$ times, matching randomly that many vertices from~$A_1$. Note that in the last round the number of available vertices in each $A_i$, $i\ge2$, is at least $t-(t'-1)(r-1)>t/2$. Hence, by \eqref{PPP},
	$$
		\Pr(\mathcal E)\ifmmode\ell\else\polishlcross\fie\ifmmode\ell\else\polishlcross\fieft(1-\frac{t^{r-1}}{\mathrm{Bin}om{rn-1}{r-1}} \right) \ifmmode\ell\else\polishlcross\fieft(1-\frac{ (t-r)^{r-1}}{\mathrm{Bin}om{rn-r-1}{r-1}}\right) \ifmmode\ell\else\polishlcross\fidots
		\ifmmode\ell\else\polishlcross\fieft(1-\frac{ (t/2)^{r-1}}{\mathrm{Bin}om{rn-r(t'-1)-1}{r-1}}\right).
	$$
	We bound each factor from above, taking the smallest numerator and the largest denominator, by
	\[
	1 - \frac{(t/2)^{r-1}}{\mathrm{Bin}om{rn-1}{r-1}}
	\ifmmode\ell\else\polishlcross\fie 1 - \frac{(t/2)^{r-1}}{(rn)^{r-1}}
	= 1 - \ifmmode\ell\else\polishlcross\fieft(\frac{t}{2rn} \right)^{r-1}
	\ifmmode\ell\else\polishlcross\fie \mathrm{ex}p\ifmmode\ell\else\polishlcross\fieft\{{- \ifmmode\ell\else\polishlcross\fieft(\frac{t}{2rn} \right)^{r-1}}\right\}.
	\]
	Thus,
	\[
	\Pr(\mathcal E)\ifmmode\ell\else\polishlcross\fie \mathrm{ex}p\ifmmode\ell\else\polishlcross\fieft\{{- t' \ifmmode\ell\else\polishlcross\fieft(\frac{t}{2rn} \right)^{r-1}}\right\}
	\ifmmode\ell\else\polishlcross\fie \mathrm{ex}p\ifmmode\ell\else\polishlcross\fieft\{{-\frac{1}{(2r)^r} \cdot \frac{t^r}{n^{r-1}}}\right\}.
	\]
\end{proof}

Another ingredient of the proof of the lower bound in Theorem~\ref{thm:random} is a Talagrand's concentration inequality for random permutations from \cite{Talagrand}. We quote here a slightly simplified version from \cite{LuczakMcDiarmid} (see also \cite{McDiarmid}). Let ${\Pi}_N$ be a random permutation of order $N$.

\begin{theorem}[Luczak and McDiarmid \cite{LuczakMcDiarmid}]\ifmmode\ell\else\polishlcross\fiabel{tala}
	Let $h(\pi)$ be a function defined on the set of all permutations of order $N$ which, for some positive constants $c$ and $d$, satisfies
	\begin{enumerate}[label=\upshape({\itshape \roman*\,})]
		\item\ifmmode\ell\else\polishlcross\fiabel{thm:talagrand:i} if $\pi_2$ is obtained from $\pi_1$ by swapping two elements, then $|h(\pi_1)-h(\pi_2)|\ifmmode\ell\else\polishlcross\fie c$;
		\item\ifmmode\ell\else\polishlcross\fiabel{thm:talagrand:ii} for each $\pi$ and $s>0$, if $h(\pi)=s$, then in order to show that $h(\pi)\ge s$, one needs to specify only at most $ds$ values $\pi(i)$.
	\end{enumerate}
	Then, for every $\eps>0$,
	$$\Pr(|h({\Pi}_N)-m|\ge \eps m)\ifmmode\ell\else\polishlcross\fie4 \mathrm{ex}p(-\eps^2 m/(32rc^2)),$$
	where $m$ is the median of $h({\Pi}_N)$.
\end{theorem}
Notice that we can use this lemma in case of random $r$-matchings as they can be generated by random permutations (c.f.\ the permutational scheme at the beginning of this section).

Finally, we are able to prove Theorem~\ref{thm:random}.

\begin{proof}[Proof of Theorem~\ref{thm:random}]
Let $P$ be a collectable $r$-pattern. Lemma~\ref{lem:upbr} immediately implies that a.a.s.\ the size of the largest $P$-clique in~$\mathbb{RM}^{(r)}_{n}$ is of size at most~$O_r(n^{1/r})$.
Thus, it only remains to prove the lower bound, that is, that a.a.s.\ the random matching $\mathbb{RM}^{(r)}_{n}$ contains a $P$-clique of size at least $\Omega_r(n^{1/r})$.
	Let $t=n^{1-\frac{1}{r}}$. For simplicity,  assume that both, $t$ and $k:=n/t=n^{1/r}$ are integers.  We divide $[rn]$ into $rk$ consecutive blocks $B_1,\dots,B_{rk}$, each of length $t$. So,  $B_1=\{1,\dots,t\}$,  $B_2=\{t+1,\dots,2t\}$, etc.

Let $K$ be a (template) $P$-clique of size $k$ on vertex set $\{v_1,\dots,v_{rk}\}$ disjoint from $[rn]$ and with edges $e_1,\dots,e_k$.
	We may think of the sets $B_j$ as $t$-blow-ups of the vertices $v_j$ of $K$.
	For every $i=1,\dots,k$, let $I_i$ be the indicator random variable equal to 1 if there is an edge in $\mathbb{RM}^{(r)}_{n}$ spanning the sets $B_j$ for all $v_j\in e_i$ and 0 otherwise.
 Further, define $X = \sum_{i=1}^k I_i$.

 Observe that if $X=k$, we would find a copy of $K$ in $\mathbb{RM}^{(r)}_{n}$. More generally (and realistically), since every subset of edges of $K$ forms itself a $P$-clique, by our construction, there will be a $P$-clique of size $X$ in $\mathbb{RM}^{(r)}_{n}$ (see Fig.\ \ref{K}). To finish the proof, we are going to show that a.a.s.~$X=\Omega_r(k)$. 
	
\begin{figure}
\caption{A $P_9$-clique $K$ of size 3 and a copy of its sub-clique in $\mathbb{RM}
\end{figure}

	
	To this end, observe that by Lemma~\ref{lemma:span_prob} applied separately for each $i$ to the sets $B_j$, $v_j\in e_i$,	
	\[
	\E X = \sum_{i=1}^k \Pr(I_i=1)
	\ge \ifmmode\ell\else\polishlcross\fieft(1-\mathrm{ex}p\ifmmode\ell\else\polishlcross\fieft\{-\frac{1}{(2r)^r} \cdot \frac{t^r}{n^{r-1}}\right\}\right)k = \ifmmode\ell\else\polishlcross\fieft(1-\mathrm{ex}p\ifmmode\ell\else\polishlcross\fieft\{-\frac{1}{(2r)^r} \right\}\right)k=:\gamma_rk.
	\]

	Now we just need to show a sharp concentration of $X$ around $\E X$. For this, recalling the permutation scheme of generating $\mathbb{RM}^{(r)}_{n}$,  we view $X$ as a function of $\Pi_{rn}$ and are going to apply Theorem~\ref{tala} with $h({\Pi}_{rn}):=X$. We begin with checking its assumptions.
	

 Observe that swapping two elements of $\Pi_{rn}$ affects at most two edges of $\mathbb{RM}^{(r)}_{n}$, and so it changes   the values of  at most two indicators $I_i$, that is, it changes the value of $X = \sum_{i=1}^k I_i$ by at most 2. Moreover, to exhibit the event $X\ge s$, it is sufficient to reveal, for each $1\ifmmode\ell\else\polishlcross\fie i\ifmmode\ell\else\polishlcross\fie s$, one edge spanning the sets $B_j$, $v_j\in e_i$, which boils down to specifying just $rs$ values of $\Pi_{rn}$.
  Thus, we are in position to apply Theorem~\ref{tala} to $X$ with $N=rn$, $c=2$ and $d=r$.
  Let $m$ be the median of $X$. Then, by Theorem \ref{tala},
	\[
	\Pr(|X-m|\ge m/2)\ifmmode\ell\else\polishlcross\fie4\mathrm{ex}p(-m/(512r)).
	\]
	Moreover, there is a standard way to switch from the median to the expectation $\mu=\E X$. Indeed, we have (see for example \cite{Talagrand}, Lemma 4.6, or \cite{McDiarmid}, page 164)  that $|m -\mu|=O(\sqrt m)$. As $\mu\ge c_rk\to\infty$, it follows that $m\to\infty$ and, in particular,  $|m-\mu|\ifmmode\ell\else\polishlcross\fie 0.01\mu$. This implies that $\Pr(|X-m|\ge m/2) = o(1)$ and
	\begin{align*}
		\Pr(|X-\mu|\ge(3/4)\mu)
		&= \Pr(|X-m + m-\mu|\ge(3/4)\mu)\\
		&\ifmmode\ell\else\polishlcross\fie \Pr(|X-m| + |m-\mu|\ge(3/4)\mu)\\
		&\ifmmode\ell\else\polishlcross\fie \Pr(|X-m| \ge(2/3)\mu)
		\ifmmode\ell\else\polishlcross\fie \Pr(|X-m|\ge m/2) = o(1).
	\end{align*}
	Hence, a.a.s.~$X \ge (1/4)\mu\ge (\gamma_r/4)k=(\gamma_r/4)n^{1/r}$, finishing the proof.
\end{proof}

\begin{rem}
If we only aimed at showing the presence of $P$-cliques of size at least $n^{1/r}/\omega(n)$, where $\omega:=\omega(n)\to\infty$ arbitrarily slowly, then we would do without Talagrand's inequality. Indeed, setting $t=\omega n^{1-1/r}$ and $Y=k-X$, by Markov's inequality and Lemma~\ref{lemma:span_prob},
$$\Pr(X\ifmmode\ell\else\polishlcross\fie k/2)=\Pr(Y\ge k/2)\ifmmode\ell\else\polishlcross\fie2\E Y/k=2\Pr(I_1=0)\ifmmode\ell\else\polishlcross\fie\mathrm{ex}p\ifmmode\ell\else\polishlcross\fieft\{-\frac{\omega^r}{(2r)^r} \right\}=o(1).$$
\end{rem}

\subsection{Lower bound -- lines}\ifmmode\ell\else\polishlcross\fiabel{lb-lines}
 Let $P_1$ be the pattern of the form $A^rB^r$, called often \emph{an alignment}. A $P_1$-clique will be called \emph{a line}. So, a line of size $k$ is just a matching represented by the word $A_1^rA_2^r\cdots A_k^r$ consisting of $k$ consecutive runs of $k$ different letters, each run of length $r$. It turns out that for lines the proof of the lower bound in Theorem~\ref{thm:random} is  more elementary than for other $P$-cliques (as it does not use Talagrand's inequality). We state now this special case separately.

\begin{thm}\ifmmode\ell\else\polishlcross\fiabel{lower_line}
	A random matching $\mathbb{RM}^{(r)}_{n}$ contains a.a.s.\ a line of size  $\Omega_r(n^{1/r})$.
\end{thm}

The idea behind the proof of Theorem \ref{lower_line}, employed already in \cite{DGR-match}, is to restrict oneself to short edges of $\mathbb{RM}^{(r)}_{n}$ and show that most among them the number of pairs od edges \emph{not} forming an alignment is smaller than the total number of such edges. Hence, removing one edge of each such pair leaves a large line.
To make this idea work, we need an auxiliary result counting short edges of $\mathbb{RM}^{(r)}_{n}$. Define  \emph{the length} of a subset $S=\{i_1<\dots<i_s\}$ of $[rn]$ as $d(S):=i_s-i_1$ (see Fig.\ \ref{length}). Clearly, for every $S$ we have $s-1\ifmmode\ell\else\polishlcross\fie d(S)\ifmmode\ell\else\polishlcross\fie rn-1$. Furthermore, let $f_s^{(r)}(n,m)$ be the number of $s$-element subsets $S$ of $[rn]$ with $d(S)\ifmmode\ell\else\polishlcross\fie m$. Then
 \begin{equation}\ifmmode\ell\else\polishlcross\fiabel{f}
 f_s^{(r)}(n,m)=\sum_{s-1\ifmmode\ell\else\polishlcross\fie d\ifmmode\ell\else\polishlcross\fie m} (rn-d) \mathrm{Bin}om{d-1}{s-2}=rn\mathrm{Bin}om m{s-1}-(s-1)\mathrm{Bin}om{m+1}s,
  \end{equation}
  since for every choice of vertices $i_1$ and $i_s$ such that $i_s-i_1=d$ (there are $rn-d$ such choices), there are $\mathrm{Bin}om{d-1}{s-2}$ choices for the remaining vertices of $S$, and, moreover,
 $\sum_{s-1\ifmmode\ell\else\polishlcross\fie d\ifmmode\ell\else\polishlcross\fie m} \mathrm{Bin}om{d-1}{s-2} = \mathrm{Bin}om{m}{s-1}$, while $\sum_{s-1\ifmmode\ell\else\polishlcross\fie d\ifmmode\ell\else\polishlcross\fie m} d\mathrm{Bin}om{d-1}{s-2} = (s-1)\mathrm{Bin}om{m+1}{s}$.

\begin{figure}
\caption{An edge of length $d$.}
\end{figure}

\begin{lemma}\ifmmode\ell\else\polishlcross\fiabel{lemma:edges}
	Let a sequence $m=m(n)$ be given such that $n^{1-\frac{1}{r-1}} \ifmmode\ell\else\polishlcross\fil m \ifmmode\ell\else\polishlcross\fil n$.
	Then, a.a.s.\ the number of edges  $e\in\mathbb{RM}^{(r)}_{n}$ with length $d(e)\ifmmode\ell\else\polishlcross\fie m$ is equal to $\frac{m^{r-1}}{(rn)^{r-2}} (1+o(1))$.
\end{lemma}

\begin{proof} We are going to apply the second moment method based on Chebyshev's inequality.
	For each $r$-tuple $e\in\mathrm{Bin}om{[rn]}r$, let $I_e$ be the indicator random variable such that $I_e=1$   if $e \in \mathbb{RM}^{(r)}_{n}$ and $I_e=0$, otherwise. Clearly, using the online scheme, $\Pr(I_{e}=1)=1/\mathrm{Bin}om{rn-1}{r-1}$. Let $X = \sum I_{e}$, where the summation is taken over all $e=\{i_1<\dots<i_r\}$ with $d(e)\ifmmode\ell\else\polishlcross\fie m$. In other words, $X$ counts all edges in $\mathbb{RM}^{(r)}_{n}$ of length at most $m$.
	Observe that the number of summands in the definition of $X$ is exactly $f_r^{(r)}(n,m)$. As
 $m \ifmmode\ell\else\polishlcross\fil n$, by \eqref{f} we have
	\[
	 f_r^{(r)}(n,m)= rn \mathrm{Bin}om{m}{r-1} (1+o(1))
	\]
	and so
	\[
	\E X =\sum\E I_e=\frac{f_r^{(r)}(n,m)}{\mathrm{Bin}om{rn-1}{r-1}}= \frac{rn \mathrm{Bin}om{m}{r-1} (1+o(1))}{\mathrm{Bin}om{rn-1}{r-1}}

	= \frac{m^{r-1}}{(rn)^{r-2}} (1+o(1)).
	\]
	By the assumption that $m\gg n^{1-\frac{1}{r-1}}$, we have $\E X\to\infty$.

To estimate the second moment, notice that by the online scheme of generating $\mathbb{RM}^{(r)}_n$,
	\begin{align}\ifmmode\ell\else\polishlcross\fiabel{ee}
	\Pr(I_{e}=I_{e'}=1) &=\Pr(e,e'\in \mathbb{RM}^{(r)}_n)=\Pr(e\in \mathbb{RM}^{(r)}_n)\Pr(e'\in \mathbb{RM}^{(r)}_n|e\in\mathbb{RM}^{(r)}_n)\notag \\
&=\begin{cases}
		\frac{1}{\mathrm{Bin}om{rn-1}{r-1} \mathrm{Bin}om{rn-r-1}{r-1}}, & \text{ if $e\cap e'=\emptyset$},\\
		0, & \text { otherwise}.
	\end{cases}
	\end{align}

	
	Thus, quite crudely,
\begin{align*}
	\E(X(X-1))&=\sum_{e:d(e)\ifmmode\ell\else\polishlcross\fie m}\sum_{e': e'\cap e=\emptyset, d(e')\ifmmode\ell\else\polishlcross\fie m}\Pr(I_e=I_{e'}=1)\\
	&\ifmmode\ell\else\polishlcross\fie \frac{(f_r^{(r)}(n,m))^2}{\mathrm{Bin}om{rn-1}{r-1}\mathrm{Bin}om{rn-r-1}{r-1}} = (\E X)^2 \frac{\mathrm{Bin}om{rn-1}{r-1}}{\mathrm{Bin}om{rn-r-1}{r-1}}.
\end{align*}

Let $\eps:=\eps(n)\to0$, but $\eps\gg\sqrt{n^{r-2}/m^{r-1}}$.
Then, by applying Chebyshev's inequality
	\begin{align*}\Pr(|X-\E X|\ge\eps\E X) &\ifmmode\ell\else\polishlcross\fie \frac{\E (X(X-1))+\E X-(\E X)^2}{\eps^2(\E X)^2}\\&\ifmmode\ell\else\polishlcross\fie\frac1{\eps^2}\ifmmode\ell\else\polishlcross\fieft(\frac{\mathrm{Bin}om{rn-1}{r-1}}{\mathrm{Bin}om{rn-r-1}{r-1}}+\frac1{\E X}-1\right)=\frac1{\eps^2}\ifmmode\ell\else\polishlcross\fieft(O\ifmmode\ell\else\polishlcross\fieft(1/n\right)+\frac{1}{\E X}\right)
		\to0,
	\end{align*}
	as $\eps^2 \E X \to\infty$. Thus, a.a.s.\ $X=(1\pm\eps)\E X=\frac{m^{r-1}}{(rn)^{r-2}} (1+o(1))$.
\end{proof}

\begin{proof}[Proof of Theorem \ref{lower_line}]
	For $r=2$ it was already proven in~\cite{DGR-match} that a.a.s.\ in $\mathbb{RM}^{(2)}_{n}$ there are lines of size $\Omega(\sqrt{n})$. Nevertheless, we include this case here.
	
	Let  $m =  n^{1-\frac{1}{r}}$ (for simplicity assume that this is an integer). Note that $n^{1-\frac{1}{r-1}} \ifmmode\ell\else\polishlcross\fil m \ifmmode\ell\else\polishlcross\fil n$. By Lemma~\ref{lemma:edges}, a.a.s.\ the number of edges $X$ of length at most~$m$ in $\mathbb{RM}^{(r)}_{n}$ is
	\[
X=\frac{m^{r-1}}{(rn)^{r-2}} (1+o(1))
	\ge\frac{2m^{r-1}}{3(rn)^{r-2}}
	= \frac{2n^{(r-1)^2/r}}{3(rn)^{r-2}}
	= \frac{2}{3r^{r-2}}n^{1/r}.
	\]
	We say that two edges $\{i_1<\dots<i_r\}$ and $\{j_1<\dots<j_r\}$ form \emph{a nonliner} if either $i_1<j_1<i_r$ or $j_1<i_1<j_r$.  In other words, a nonliner is any pattern, collectable or not, other than the alignment $P_1$.
	
	We are going to show that among the edges of length at most~$m$, there are a.a.s.\ at most $\frac{1}{2r^{r-2}}n^{1/r}$ nonliners. After removing one edge from each nonliner (possibly with repetitions) we then obtain a line of size at least $\frac{1}{6r^{r-2}}n^{1/r}$, which will end the proof.
	
	For a $2r$-element subset $T=\{i_1<\dots<i_r,\; j_1<\dots<j_r\}\subset [rn]$ with $i_1<j_1<i_r$, let $I_T$ be the indicator random variable equal to $1$ if both $e_1:=\{i_1<\dots<i_r\}$ and $e_2:=\{j_1<\dots<j_r\}$ are edges of $\mathbb{RM}^{(r)}_n$,  and $I_T=0$ otherwise. Note that if $I_T=1$, then $e_1,e_2$ form a nonliner  in $\mathbb{RM}^{(r)}_n$. By \eqref{ee},
	\[
	\Pr(I_T=1)=\frac{1}{\mathrm{Bin}om{rn-1}{r-1} \mathrm{Bin}om{rn-r-1}{r-1}}
	= \frac{((r-1)!)^2}{(rn)^{2r-2}} (1+o(1)).
	\]

\begin{figure}
\caption{A nonliner with edges of lengths at most $m$.}
\end{figure}

	Let $Y = \sum I_T$, where the summation is taken over all sets $T$ as above and such that $i_r-i_1\ifmmode\ell\else\polishlcross\fie m$ and $j_r-j_1\ifmmode\ell\else\polishlcross\fie m$  (see Fig.\ \ref{T}). Then $Y$ counts all nonliners in $\mathbb{RM}^{(r)}_n$ formed by the edges of length at most $m$. Let $g^{(r)}(n,m)$ denote the number of terms in this sum. In order to estimate $g^{(r)}(n,m)$,  we first count the number of choices of $e_1$ and $j_1$. Since $i_1<j_1<i_r$, we can treat them as one  $(r+1)$-set $\{\iota_1<\dots<\iota_{r+1}\}$ from $[rn]$ of length at most $m$. Once it is chosen, we designate one of the vertices in~$\{\iota_2,\dots,\iota_{r}\}$ to be $j_1$ and the remaining ones become $e_1$. Using notation from prior to Lemma~\ref{lemma:edges}, the number of such choices is
	\[
	f_{r+1}^{(r)}(n,m) \cdot (r-1)
	= r(r-1)n \mathrm{Bin}om{m}{r} (1+o(1)).
	\]
	Finally, the number of choices of $\{j_2,\dots,j_r\}$ satisfying $j_r-j_1\ifmmode\ell\else\polishlcross\fie m$ is at least $\mathrm{Bin}om{m-(r-1)}{r-1}$ and at most $\mathrm{Bin}om{m}{r-1}$. Thus,
	\[
	g^{(r)}(n,m) = r(r-1)n \mathrm{Bin}om{m}{r} \mathrm{Bin}om{m}{r-1} (1+o(1))
	= \frac{(r-1)nm^{2r-1}}{((r-1)!)^2} (1+o(1))
	\]
	and so
	\[
	\E Y = \frac{(r-1)nm^{2r-1}}{(rn)^{2r-2}} (1+o(1))
	= \frac{(r-1)nn^{(r-1)(2r-1)/r}}{(rn)^{2r-2}} (1+o(1))
	= \frac{r-1}{r^{2r-2}} n^{1/r} (1+o(1)).
	\]
	It remains to show that, say, a.a.s.\ $Y\ifmmode\ell\else\polishlcross\fie \frac 32\E Y$. If so, then a.a.s.\
	\[
	Y \ifmmode\ell\else\polishlcross\fie \frac{3(r-1)}{2r^{2r-2}} n^{1/r}(1+o(1))  < \frac{1}{2r^{r-2}}n^{1/r},
	\]
as required,
	since the inequality $\frac{3(r-1)}{2r^{2r-2}} < \frac{1}{2r^{r-2}}$ is equivalent to $3(r-1)< r^r$, which holds for every $r\ge2$.
	
	To achieve our last goal, we apply Chebyshev's inequality. For this sake, we need to estimate $\E (Y(Y-1))$, which can be written as
	\[
	\E(Y(Y-1))=\sum_{T,T'}\Pr(I_T=I_{T'}=1),
	\]
	where the summation is taken over all (ordered) pairs of $2r$-sets $T$ and $T'$ such that each of $T=(e_1,e_2)$ and $T'=(e_1',e_2')$ is a potential
	  nonliner in $\mathbb{RM}^{(r)}_n$. We split the above sum into two sub-sums $\Sigma_1$ and $\Sigma_2$ according to whether $T\cap T'=\emptyset$ or $|T\cap T'|=r$ (and then $e_i=e_j'$ for some $1\ifmmode\ell\else\polishlcross\fie i\ifmmode\ell\else\polishlcross\fie j\ifmmode\ell\else\polishlcross\fie 2$ -- for all other options the above probability is zero).
	
	In the former case, by a similar chain formula as in \eqref{ee},
$$\Pr(I_T=I_{T'}=1)=\frac1{\mathrm{Bin}om{rn-1}{r-1} \mathrm{Bin}om{rn-r-1}{r-1}\mathrm{Bin}om{rn-2r-1}{r-1} \mathrm{Bin}om{rn-3r-1}{r-1}}$$
and so

	\[
	\Sigma_1\ifmmode\ell\else\polishlcross\fie\frac{g^{(r)}(n,m)^2}{\mathrm{Bin}om{rn-1}{r-1} \mathrm{Bin}om{rn-r-1}{r-1}\mathrm{Bin}om{rn-2r-1}{r-1} \mathrm{Bin}om{rn-3r-1}{r-1}}
	=(\E Y)^2(1+o(1)).
	\]
	In the latter case,
$$\Pr(I_T=I_{T'}=1)=\frac1{\mathrm{Bin}om{rn-1}{r-1} \mathrm{Bin}om{rn-r-1}{r-1}\mathrm{Bin}om{rn-2r-1}{r-1} },$$
while the number of such pairs $(T,T')$ is at most $g^{(r)}(n,m)\cdot 4m\mathrm{Bin}om{m}{r-1}$, as given $T$, there are four ways to select the common $r$-tuple and at most $m\mathrm{Bin}om{m}{r-1}$ ways to select the other $r$-tuple of $T'$. Thus,
	\[
	\Sigma_2\ifmmode\ell\else\polishlcross\fie \frac{f^{(r)}(n,m)\cdot 4m\mathrm{Bin}om{m}{r-1}}{\mathrm{Bin}om{rn-1}{r-1} \mathrm{Bin}om{rn-r-1}{r-1}\mathrm{Bin}om{rn-2r-1}{r-1}}
	=O_r\ifmmode\ell\else\polishlcross\fieft(\frac{nm^{2r-1}\cdot m^r}{n^{3r-3}} \right)
	=O_r\ifmmode\ell\else\polishlcross\fieft(\frac{m^{3r-1}}{n^{3r-4}} \right)
	=O_r(n^{1/r})
	\]
	and, altogether,
	\[
	\E (Y(Y-1)) \ifmmode\ell\else\polishlcross\fie (\E Y)^2(1+o(1)) + O_r(n^{1/r}).
	\]
	By Chebyshev's inequality,
	\begin{align*}
		\Pr(|Y-\E Y|\ge\E Y/2)&\ifmmode\ell\else\polishlcross\fie \frac{\E(Y(Y-1))+\E Y-(\E Y)^2}{(2\E Y)^2}\\
		&\ifmmode\ell\else\polishlcross\fie\frac14\ifmmode\ell\else\polishlcross\fieft(1+o(1)+\frac{O_r(n^{1/r})}{(\E Y)^2}+\frac1{\E Y}-1\right)=O_r(n^{-1/r})+o(1)=o(1).
	\end{align*}
	Thus, a.a.s.\ $Y\ifmmode\ell\else\polishlcross\fie \frac32\E Y$, as required.
\end{proof}

\begin{rem}
In fact, for $r=2$, it is sufficient to prove the lower bound in Theorem \ref{thm:random} only for lines. Indeed, then the lower bound for the other two patterns follows from Lemma~\ref{lem:upbr} combined with Corollary \ref{Theorem ESz General_partite} applied to the bipartite sub-matching of $\mathbb{RM}^{(2)}_n$, that is, one consisting  of edges with one endpoint in $[n]$ and the other in $[2n]\setminus[n]$ (note that such a sub-matching has no alignments and has, a.a.s., about $n/2$ edges; for details, see \cite{DGR-match}).
\end{rem}

\begin{rem}
In the above proof we had a little choice in defining $m$. Indeed, there were two constraints: 1) the number of short edges $X=\Theta_r\ifmmode\ell\else\polishlcross\fieft( \frac{m^{r-1}}{n^{r-2}}\right)$ should be $\Omega_r(n^{1/r})$ and 2) the number of nonliners $Y=\Theta_r\ifmmode\ell\else\polishlcross\fieft( \frac{m^{2r-1}}{n^{2r-3}}\right)$ should be $O_r\ifmmode\ell\else\polishlcross\fieft( \frac{m^{r-1}}{n^{r-2}}\right).$
And they are equivalent, respectively, to $m=\Omega_r(n^{1-1/r})$ and $m=O_r(n^{1-1/r})$.
\end{rem}

\@ifstar{\origsection*}{\@startsection{section}{1}\z@{.7\ifmmode\ell\else\polishlcross\fiinespacing\@plus\ifmmode\ell\else\polishlcross\fiinespacing}{.5\ifmmode\ell\else\polishlcross\fiinespacing}{\normalfont\scshape\centering\S}}{Final remarks}

\subsection{Optimality}
Here we discuss the issue of optimality of Theorem \ref{Theorem ESz General_classic}. The case $r=2$, that is, Theorem \ref{Theorem E-S for LSW}, is best possible, as demonstrated by an explicit construction in \cite{DGR-match}. However, already for $r=3$, we can show the optimality of Theorem \ref{Theorem ESz General_classic},  only in special cases (cf.\ Remark 2.7 in \cite{DGR-match}). The most general construction we can get for $r=3$ is when $M$ is clean, that is, no pair of edges forms pattern $P^*_1$, and some three of the parameters $a_2,a_3,a_4,a_7$ are set to 1.

To describe it, we define an operation on pairs of $r$-matchings. Given $r$-matchings $M$ and $N$, the latter of size $t$, \emph{the $N$-blow-up}  of $M$ is the matching $M[N]$ obtained from $M$ by replacing every vertex $i$ of $M$ by an ordered set $U_i$, $|U_i|=t$, and each edge $e=\{i_1,\dots,i_r\}\in M$ by a copy $N_e$ of $N$ on $\bigcup_{j=1}^rU_{i_j}$. Thus, in $M[N]$ there are two kinds of pairs of edges: 1) both within the same copy of $N$, call them $N$-pairs, and 2) each from a different copy of $N$, call them $M$-edges.

 This operation is particularly useful when $N$ is \emph{(ordered) $r$-partite} (see Introduction for the definition).
Recall that for $r=2$ both $R_2=ABBA$ and $R_3=ABAB$, and so every $R_2$-clique and $R_3$-clique, are bipartite, while
for $r=3$, only patterns $P_5,P_6,P_8,P_9$ are tripartite, and so are $P_i$-cliques for $i=5,6,8,9$.

If $N$ is an $r$-partite $P$-clique, then in $M[N]$ every  $N$-pair forms, obviously, pattern $P$, while every $M$-pair made of one edge of $N_e$ and one of $N_f$, where $e,f\in M$, forms the same pattern as the  pair $\{e,f\}$ does in $M$. Moreover, if $M$ is also $r$-partite, then so is $M[N]$.

 Now, we are ready to describe our constructions for $r=2$ and $r=3$. For $r=2$ the optimal construction  from \cite{DGR-match} mentioned above is just $\ell S_s[W_w]$, that is, a concatenation of $\ell$ copies of the $W_w$-blow-up of $S_s$, where $S_s$ is a stack, or $R_2$-clique, of size $s$ and $W_w$ is a wave, or $R_3$-clique, of size $w$. Since both cliques are bipartite, the blow-up operation is, in fact, exchangeable, so another construction is $\ell W_w[S_s]$.

 For $r=3$, let $K_i$ be a $P_i$-clique of size $a_i$, $i=2,5,6,8,9$. Consider the 4-fold blow-up operation $M=K_2[K_5[K_6[K_8[K_9]]]]$. Every pair of edges of $M$ forms one of the five patterns but the largest $P_i$-clique in $M$ is still of size $a_i$, $i=2,5,6,8,9$. The final construction is obtained by taking $a_1$ copies of $M$ ordered linearly. It has $n=a_1a_2a_5a_6a_8a_9$ edges and, in addition to the above, the largest $a_1$-clique (a line) therein is of size $a_1$.
This shows that Theorem \ref{Theorem ESz General_classic}(b) is optimal if, say $a_3=a_4=a_7=1$. For larger $r$, in  similar constructions, the sets of non-marginal values of parameters $a_i$ are getting proportionally smaller.
Indeed, there are exactly $2^{r-1}$ $r$-partite $r$-patterns, so all but $2^{r-1}+2$ parameters $a_i$ must be set to~1. This, in particular, shows that Corollary \ref{Theorem ESz General_partite} is optimal.

Another optimal case for $r=3$ is when $a_1=n/2$, $a_3=2$ (or $a_7=2$),  and all other seven parameters $a_i$ are set to 1. It is realized  by a simple chain-like construction.
For an $r$-pattern $P$, define \emph{a $P$-chain} as a matching in which consecutive  edges (in the order of the left-ends) form pattern $P$, while all other pairs of edges form the alignment $P_1=A^rB^r$. For $r=3$, one can easily construct a $P_i$-chain for $i=3,7$, which shows  optimality of Theorem \ref{Theorem ESz General_classic}(b) in the above mentioned case.
For example,  the $P_3$-chain looks like this:
\[
A_1A_1A_2A_2A_1A_3A_3A_2A_4A_4A_3A_5A_5A_4A_6A_6A_5A_7A_7\dots A_{n-2}A_nA_nA_{n-1}A_n.
\]

For general $r$, the same construction works for all patterns $P$ in which the first $A$-run is at least as long as the number of $B$'s preceding the last $A$, which equals $r$ minus the length of the $B$-run at the end of $P$. Among collectable patterns, for $r=3$ this property is satisfied only by $P_3$ and $P_7$ and, for $r=4$, only by $P_3$, $P_7$, and $P_{19}$ (cf.\ Table \ref{table:patterns4}).

But $P$-chains with non-collectable $P$ can be useful in showing optimality of Theorem~\ref{Theorem ESz General_classic}(a) for some very special cases.
Indeed, for $r=3$, consider the $P_1^*$-chain
\[
A_1A_1A_2\;A_1A_2A_3\;A_2A_3A_4\;A_3A_4A_5\;... \;A_{n-3}A_{n-2}A_{n-1}\;A_{n-2}A_{n-1}A_n\; A_{n-1}A_nA_n
\]
(the spaces between 3-letter blocks where introduced solely for the benefit of the reader) and observe that the consecutive edges form pattern $P^*_1$, while all other pairs of edges form pattern $P_1$, that is, they form a $P_1$-clique of size $\ifmmode\ell\else\polishlcross\ficeil n/2\rceil$.  This shows that in the special case when $a_1=n$ is even (with  $a_i=1$ for all other $i$), the factor of $1/2$ appearing in the assertion of Theorem \ref{Theorem ESz General_classic}(a)   cannot be improved.

On the negative side, consider the case when $r=3$ and all $a_i=1$, except $i=2$ and $i=4$ and assume that $n=a_2a_4+1$. Let every pair of edges of  $M=M_n^{(3)}$ form either pattern $P_2=AABBBA$ or $P_4=ABBBAA$. Let the edges of $M$ be (from left to right) $e_1,\dots,e_n$ with the corresponding letters $A_1,\dots,A_n$. W.l.o.g., let $e_1$ and $e_2$ form pattern $P_2$, i.e., there is a subsequence $A_1A_1A_2A_2A_2A_1$. Then also $e_1$ and $e_j$, $j=3,\dots,n$, must form pattern $P_2$, because no matter what the relation between $e_2$ and $e_j$ is, $e_j$ is totally ``inside'' $e_2$. For the same token, if $e_1$ and $e_2$ form pattern $P_4$, then so do $e_1$ and $e_j$, $j=3,\dots,n$. And the same is true for every $e_h$, $h\ge2$, that is, for every $j\ge h$, $e_h$ and $e_j$ form the same pattern, always $P_2$ or always $P_4$. It follows that for every partition $n=n_2+n_4$, there is a $P_2$-clique of size $n_2$ or a $P_4$-clique of size  $n_4$, a much stronger statement that what is implied by Theorem \ref{Theorem ESz General_classic}.

An even more surprising is the combination of $P_3$ and $P_7$ ($r=3$). One can easily check that when the edges of $M=M_n^{(3)}$ form only patterns $P_3$ and $P_7$, then, in fact, $M$ must be either entirely a $P_3$-clique or entirely a $P_7$-clique. Indeed, if edges $e_A$ and $e_B$ form  pattern $P_7=ABAABB$ and $e_B$ and $e_C$ form pattern $P_3=BBCCBC$, then $e_A$ and $e_C$ are forced to form pattern $P_1$, a contradiction. If, on the other hand,  we have $AABBAB$ and $BCBBCC$, then $AACACC=P_1^*$, a contradiction again. This is the most striking case against the optimality of Theorem \ref{Theorem ESz General_classic}.

\subsection{Open questions} Let us conclude the paper with some  questions concerning possible future research. Firstly, in view of the discussion in the previous subsection, one could try to strengthen Theorem \ref{Theorem ESz General_classic} so that the new version would be indeed optimal.

Another direction into which one could sail inspired by our results is a \emph{cyclic} version of ordered matchings. In much the same way, a \emph{cyclic $r$-matching} of size $n$ is just an $r$-uniform matching with $n$ edges on a cyclically ordered set of vertices. Such matchings can be naturally represented by cyclic words in which every letter corresponding to an edge occurs exactly $r$ times. For instance, for $r=2$ we have only two possible cyclic patterns, namely $Q_1=AABB$ and $Q_2=ABAB$ (since $ABBA$ is equivalent to $AABB$), while for $r=3$ there are just four of them: $AAABBB$, $AABABB$, $AABBAB$, and $ABABAB$. 
It would be desirable  to know whether in this setting a similar Erd\H os-Szekeres type phenomena occur. First, however, we should solve the following problem.
\begin{prob} For $r\ge4$, identify and/or characterize all collectable patterns in cyclic ordered $r$-matchings.
	\end{prob}
\noindent Only then we would be able to state a suitable Erd\H os-Szekeres type question.

Let us mention that a cyclic version of the original Erd\H{o}s-Szekeres theorem for permutations was obtained recently by Czabarka and Wang \cite{Czabarka}.
But already for $r=2$, we do not know the exact answer. Interestingly, the problem in this case  has another intriguing context and, it turns out, has been recently solved up to a constant factor. 

Indeed, suppose that we are given a cyclic $2$-matching $M$ of size $n$ represented by a (cyclic) double occurrence word with $n$ distinct letters $A_1,\ifmmode\ell\else\polishlcross\fidots, A_n$. Imagine that these $2n$ letters are placed on a geometric circle. Now, the edges of $M$ can be drawn as chords of the circle and we obtain in this way a structure known as \emph{the circle graph} $G_M$, which is the \emph{intersection graph} of the chords. The set of vertices of $G_M$ is the set of chords (the edges of $M$), and two chords form an edge in $G_M$ if they are crossing.

Since there are just two possible cyclic patterns, we have basically just two types of homogenous cyclic matchings: \emph{cyclic lines} ($Q_1$-cliques) and \emph{cyclic waves} ($Q_2$-cliques). Notice that waves correspond to cliques in the circle graph $G_M$, while lines correspond to independent sets of $G_M$. In this way we have arrived at the following Ramsey type question for circle graphs.
 
 Let $R^{cir}(w,\ell)$ denote the least number $n$ such that every circle graph with $n$ vertices contains a clique of size $w$ or an independent set of size $\ell$.
In \cite{Kostochka} Kostochka gave a construction of a family of circle graphs showing that $R^{cir}(w,w)=\Omega(w^2\ifmmode\ell\else\polishlcross\fiog w)$. His construction was recently improved by Davis \cite{Davies}, who proved that $R^{cir}(w,\ell)\geqslant w(\ifmmode\ell\else\polishlcross\fin w-2)\ell$, for arbitrary $w,\ell\geqslant 2$. Moreover, Davis also proved in \cite{Davies} that the chromatic number of circle graphs with clique number $w$ is at most $O(w\ifmmode\ell\else\polishlcross\fiog w)$, which implies that $R^{cir}(w,\ell)=\Theta(\ell w\ifmmode\ell\else\polishlcross\fiog w)$. Still, it remains to determine $R^{cir}(w,\ell)$ exactly.
We anticipate that already for $r=3$, obtaining analogous results could be very challenging.

Our next two questions are about the random case. First, in the initial attempts to the proof of Theorem~\ref{thm:random} we have tried unsuccessfully to show concentration of $X$ by Chebyshev's inequality instead of Talagand's inequality. We wonder if such a proof is still possible and, if so, how  complicated  would it be.

Another problem related to Theorem~\ref{thm:random} is to pinpoint the constants. In \cite{DGR-match} we stated the following conjecture.

\begin{conj}[\cite{DGR-match}]
	For every $r\geqslant 2$ there exist positive constants $b_r$ and $c_r$ such that for each collectable pattern $P$, the maximum size of a $P$-clique in $\mathbb{RM}^{(r)}_n$ is a.a.s.\ equal to $(1+o(1))b_rn^{c_r}$.
\end{conj}

By Theorem \ref{thm:random} we now know that $c_r=1/r$. More mysterious are the multiplicative constants $b_r$. We only know that if the conjecture is true for $r=2$, then necessarily $b_2=\sqrt{2}$. Indeed,   Stanley \cite{Stanley}  deduced  from a deep result of Baik and Rains \cite{BaikRains} concerning monotone subsequences in random permutations that the maximum size of stacks and waves in $\mathbb{RM}^{(2)}_n$ is a.a.s  $(1+o(1))\sqrt{2n}$.  However, for lines (even for $r=2$) the multiplicative constant remains unknown.

Let us conclude with  asking for the largest twins, both in every $M_n^{(r)}$ and in $\mathbb{RM}^{(r)}_n$. By \emph{twins} in an ordered $r$-matching we mean a pair of order-isomorphic, disjoint sub-matchings. Let $t^{(r)}(M)$  denote the maximum size of twins in an $r$-matching $M$ (measured by the size of just one of them) and $t^{(r)}(n)$ -- the minimum of $t^{(r)}(M)$ over all $r$-matchings on $[rn]$. In \cite{DGR-match} we proved that a.a.s.\ $t^{(2)}(\mathbb{RM}^{(2)}_n)=\Theta(n^{2/3})$ and, by linking the presence of twins in 2-matchings with the presence of twins in permutations, we  derived an estimate  $t^{(2)}(n)=\Omega(n^{3/5})$. We conjectured in \cite[Conjecture 4.1]{DGR-match}  (in the more general setting of multiple twins) that $t^{(2)}(n)=\Omega(n^{2/3})$.

In the $r$-uniform scenario, our results on $P$-cliques immediately yield lower bounds $t^{(r)}(n)\ge\tfrac12 n^{3^{1-r}}$ and a.a.s.\ $t^{(r)}(\mathbb{RM}^{(r)}_n)=\Omega_r(n^{1/r})$. We believe that both values are significantly larger. In fact,  an easy  first moment proof yields that a.a.s.\  $t^{(r)}(\mathbb{RM}^{(r)}_n)=O_r(n^{2/(r+1)})$ and so we feel that the following conjecture can be true.

\begin{conj}
	For every $r\geqslant 2$,  a.a.s.\ $t^{(r)}(\mathbb{RM}^{(r)}_n)=\Theta_r(n^{2/(r+1)})$.
\end{conj}
However, we are cautious about formulating its deterministic, much harder counterpart, $t^{(r)}(n)=\Theta_r(n^{2/(r+1)})$, as even a similar question for permutations remains wide open (see, e.g.,~\cite{BukhR}).

\begin{bibdiv}
\begin{biblist}

\bib{BaikRains}{article}{
      author={Baik, Jinho},
      author={Rains, Eric~M.},
       title={The asymptotics of monotone subsequences of involutions},
        date={2001},
        ISSN={0012-7094},
     journal={Duke Math. J.},
      volume={109},
      number={2},
       pages={205\ndash 281},
         url={https://doi.org/10.1215/S0012-7094-01-10921-6},
      review={\MR{1845180}},
}

\bib{BKP}{unpublished}{
      author={B\'ar\'any, Imre},
      author={Kalai, Gil},
      author={P\'or, Attila},
       title={Erd{\H o}s--{S}zekeres theorem for $k$-flats},
        note={\href{https://arxiv.org/pdf/2103.13185.pdf}{arXiv:2103.13185}},
}

\bib{BGT}{unpublished}{
      author={Bar\'at, J\'anos},
      author={Gy\'arf\'as, Andr\'as},
      author={T\'oth, G\'eza},
       title={Monochromatic spanning trees and matchings in ordered complete
  graphs},
        note={\href{https://arxiv.org/pdf/2210.10135.pdf}{arXiv:2210.10135}},
}

\bib{BucicSudakovTran}{article}{
      author={Buci\'{c}, M.},
      author={Sudakov, B.},
      author={Tran, T.},
       title={{E}rd{\H o}s--{S}zekeres theorem for multidimensional arrays},
        date={2022},
     journal={J. Eur. Math. Soc.},
}

\bib{BukhMatousek}{article}{
      author={Bukh, B.},
      author={Matou\v{s}ek, J.},
       title={{E}rd{\H o}s--{S}zekeres--type statements: {R}amsey function and
  decidability in dimension 1},
        date={2014},
     journal={Duke Math. J.},
      volume={163},
       pages={2243\ndash 2270},
}

\bib{BukhR}{article}{
      author={Bukh, Boris},
      author={Rudenko, Oleksandr},
       title={Order-isomorphic twins in permutations},
        date={2020},
        ISSN={0895-4801},
     journal={SIAM J. Discrete Math.},
      volume={34},
      number={3},
       pages={1620\ndash 1622},
      review={\MR{4127099}},
}

\bib{ConlonFerber}{article}{
      author={Conlon, David},
      author={Ferber, Asaf},
       title={Lower bounds for multicolor {R}amsey numbers},
        date={2021},
        ISSN={0001-8708},
     journal={Adv. Math.},
      volume={378},
       pages={Paper No. 107528, 5},
         url={https://doi.org/10.1016/j.aim.2020.107528},
      review={\MR{4186575}},
}

\bib{ConlonFoxSudakov}{article}{
      author={Conlon, David},
      author={Fox, Jacob},
      author={Lee, Choongbum},
      author={Sudakov, Benny},
       title={Ordered {R}amsey numbers},
        date={2017},
        ISSN={0095-8956},
     journal={J. Combin. Theory Ser. B},
      volume={122},
       pages={353\ndash 383},
      review={\MR{3575208}},
}

\bib{Czabarka}{article}{
      author={Czabarka, \'{E}va},
      author={Wang, Zhiyu},
       title={Erd{\H{o}}s-{S}zekeres theorem for cyclic permutations},
        date={2019},
        ISSN={1944-4176},
     journal={Involve},
      volume={12},
      number={2},
       pages={351\ndash 360},
         url={https://doi.org/10.2140/involve.2019.12.351},
      review={\MR{3864223}},
}

\bib{Davies}{article}{
      author={Davies, James},
       title={Improved bounds for colouring circle graphs},
        date={2022},
     journal={Proceedings of the American Mathematical Society},
      volume={150},
      number={12},
       pages={5121\ndash 5135},
}

\bib{DGR-match}{unpublished}{
      author={Dudek, Andrzej},
      author={Grytczuk, Jaros{\ifmmode\ell\else\polishlcross\fi a}w},
      author={Ruci\'{n}ski, Andrzej},
       title={Ordered unavoidable sub-structures in matchings and random
  matchings},
        note={\href{https://arxiv.org/pdf/2210.14042.pdf}{arXiv:2210.14042}},
}

\bib{DGR_LATIN}{incollection}{
      author={Dudek, Andrzej},
      author={Grytczuk, Jaros{\ifmmode\ell\else\polishlcross\fi a}w},
      author={Ruci\'{n}ski, Andrzej},
       title={Patterns in ordered (random) matchings},
        date={2022},
   booktitle={L{ATIN} 2022: {T}he 15th {L}atin {A}merican {T}heoretical
  {I}nformatics {S}ymposium},
      series={Lecture Notes in Comput. Sci.},
      volume={13568},
   publisher={Springer},
       pages={544\ndash 556},
}

\bib{EliasMatousek}{article}{
      author={Eli\'{a}\v{s}, M.},
      author={Matou\v{s}ek, J.},
       title={Higher--order {E}rd{\H o}s--{S}zekeres theorems},
        date={2013},
     journal={Adv. Math.},
      volume={244},
       pages={1\ndash 15},
}

\bib{ErdosSzekeres}{article}{
      author={Erd\H{o}s, P.},
      author={Szekeres, G.},
       title={A combinatorial problem in geometry},
        date={1935},
        ISSN={0010-437X},
     journal={Compositio Math.},
      volume={2},
       pages={463\ndash 470},
      review={\MR{1556929}},
}

\bib{FoxPachSudakovSuk}{article}{
      author={Fox, J.},
      author={Pach, J.},
      author={Sudakov, B.},
      author={Suk, A.},
       title={{E}rd{\H o}s--{S}zekeres--type theorems for monotone paths and
  convex bodies},
        date={2012},
     journal={Proc. Lond. Math. Soc.},
      volume={105},
       pages={953\ndash 982},
}

\bib{Concrete}{book}{
      author={Graham, Ronald~L.},
      author={Knuth, Donald~E.},
      author={Patashnik, Oren},
       title={Concrete mathematics},
     edition={Second},
   publisher={Addison-Wesley Publishing Company, Reading, MA},
        date={1994},
        ISBN={0-201-55802-5},
        note={A foundation for computer science},
      review={\MR{1397498}},
}

\bib{Kostochka}{article}{
      author={Kostochka, Alexandr},
       title={Coloring intersection graphs of geometric figures with a given
  clique number},
        date={2004},
     journal={Contemporary mathematics},
      volume={342},
       pages={127\ndash 138},
}

\bib{LuczakMcDiarmid}{article}{
      author={Luczak, Malwina~J.},
      author={McDiarmid, Colin},
       title={Concentration for locally acting permutations},
        date={2003},
        ISSN={0012-365X},
     journal={Discrete Math.},
      volume={265},
      number={1-3},
       pages={159\ndash 171},
      review={\MR{1969372}},
}

\bib{McDiarmid}{article}{
      author={McDiarmid, Colin},
       title={Concentration for independent permutations},
        date={2002},
        ISSN={0963-5483},
     journal={Combin. Probab. Comput.},
      volume={11},
      number={2},
       pages={163\ndash 178},
      review={\MR{1888907}},
}

\bib{MoshkovitzShapira}{article}{
      author={Moshkovits, G.},
      author={Shapira, A.},
       title={Ramsey theory, integer partitions and a new proof of the {E}rd{\H
  o}s--{S}zekeres {T}heorem},
        date={2014},
     journal={Adv. Math.},
      volume={262},
       pages={1107\ndash 1129},
}

\bib{Stanley}{incollection}{
      author={Stanley, Richard~P.},
       title={Increasing and decreasing subsequences and their variants},
        date={2007},
   booktitle={International {C}ongress of {M}athematicians. {V}ol. {I}},
   publisher={Eur. Math. Soc., Z\"{u}rich},
       pages={545\ndash 579},
      review={\MR{2334203}},
}

\bib{SzaboTardos}{article}{
      author={Szab\'{o}, Tibor},
      author={Tardos, Gabor},
       title={A multidimensional generalization of the {E}rd{\H o}s--{S}zekeres
  lemma on monotone subsequences},
        date={2001},
     journal={Combin. Prob. Comput.},
      volume={10},
       pages={557\ndash 565},
}

\bib{Talagrand}{article}{
      author={Talagrand, Michel},
       title={Concentration of measure and isoperimetric inequalities in
  product spaces},
        date={1995},
        ISSN={0073-8301},
     journal={Inst. Hautes \'{E}tudes Sci. Publ. Math.},
      number={81},
       pages={73\ndash 205},
      review={\MR{1361756}},
}

\bib{Tardos}{inproceedings}{
      author={Tardos, G\'{a}bor},
       title={Extremal theory of ordered graphs},
        date={2018},
   booktitle={Proceedings of the {I}nternational {C}ongress of
  {M}athematicians---{R}io de {J}aneiro 2018. {V}ol. {IV}. {I}nvited lectures},
   publisher={World Sci. Publ., Hackensack, NJ},
       pages={3235\ndash 3243},
      review={\MR{3966530}},
}

\end{biblist}
\end{bibdiv}

\appendix
\@ifstar{\origsection*}{\@startsection{section}{1}\z@{.7\ifmmode\ell\else\polishlcross\fiinespacing\@plus\ifmmode\ell\else\polishlcross\fiinespacing}{.5\ifmmode\ell\else\polishlcross\fiinespacing}{\normalfont\scshape\centering\S}}{Proof of Theorem \ref{Theorem E-S for LSW}}\ifmmode\ell\else\polishlcross\fiabel{appendix}

Since the proof of Theorem \ref{Theorem ESz General_classic} is inductive with the base step $r=2$, we provide here, for completeness, a proof of Theorem \ref{Theorem E-S for LSW} which differs slightly from that given in \cite{DGR-match}.

\begin{proof}[Proof of Theorem \ref{Theorem E-S for LSW}] Let $M$ be an ordered matching consisting of edges $\{a_i,b_i\}$, $i=1,2,\ifmmode\ell\else\polishlcross\fidots, n$, with the left ends satisfying $a_1<\cdots <a_n$. Notice that the right ends of the edges define a permutation $\pi=(j_1,j_2,\ifmmode\ell\else\polishlcross\fidots,j_n)$ accordingly to the order  $b_{j_1}<b_{j_2}<\cdots<b_{j_n}$.

By the original Erd\H{o}s-Szekeres theorem this permutation contains either a decreasing subsequence of length $s+1$ or an increasing subsequence of length $p=w\ell+1$. In the former case we are done, since any such decreasing subsequence corresponds to a stack. In the latter case we get a sub-matching $L$ with $p$ edges whose right ends come in the same order as the left ends. We call $L$ \emph{a landscape} (see Fig.\ \ref{ESZ3}). Notice that no pair of edges in a landscape may form a nesting.
\begin{figure}
\caption{A landscape with five edges.}
\end{figure}

 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,\ifmmode\ell\else\polishlcross\fidots, W_k$, in the following greedy 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<\ifmmode\ell\else\polishlcross\fidots<e_{i_1}\}$, for some $i_1\geqslant 1$. Clearly, $W_1$ is a genuine wave since there are no lines (and no nestings) in $W_1$.
 Also notice that the edges $e_1$ and $e_{i_1+1}$ form an alignment, 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}<\ifmmode\ell\else\polishlcross\fidots<e_{i_2}\}$, for some $i_2\geqslant i_{1}+1$. We iterate this procedure until there are no edges of $L$ left. Let the last wave be $W_k=\{e_{i_{k-1}+1}<e_{i_{k-1}+2}<\ifmmode\ell\else\polishlcross\fidots<e_{i_k}\}$, with $i_k\geqslant i_{k-1}+1$. Clearly, the sequence $e_1<e_{i_1+1}<\ifmmode\ell\else\polishlcross\fidots<e_{i_{k-1}+1}$ of the leftmost edges of the waves $W_i$, $i=1,\dots,k$,  forms a line (see Figure~\ref{ESZ4}).
\begin{figure}
\caption{Greedy decomposition of a landscape into waves. The left-most edges of the waves, forming a line, are bold.}
\end{figure}

If $k\geqslant \ell+1$, then we are done. Otherwise,  $k\ifmmode\ell\else\polishlcross\fieqslant \ell$, and, since $p=\ell w+1$, some wave $W_i$ must have at least
$$\frac pk=\frac{\ell w+1}\ell>w$$
edges. This completes the proof.
\end{proof}

\end{document}