# A sharp Ramsey theorem for ordered hypergraph matchings

Lisa Sauermann Institute for Applied Mathematics, University of Bonn, Bonn,
Germany. Email<EMAIL_ADDRESS>Research supported by NSF Award
DMS-2100157 and a Sloan Research Fellowship. Dmitrii Zakharov Department of
Mathematics, Massachusetts Institute of Technology, Cambridge, MA. Research
supported by a Jane Street Graduate Research Fellowship. Email:
<EMAIL_ADDRESS>
###### Abstract

We prove essentially sharp bounds for Ramsey numbers of ordered hypergraph
matchings, inroduced recently by Dudek, Grytczuk, and Ruciński. Namely, for
any $r\geq 2$ and $n\geq 2$, we show that any collection $\mathcal{H}$ of $n$
pairwise disjoint subsets in $\mathbb{Z}$ of size $r$ contains a subcollection
of size $\lfloor n^{1/(2^{r}-1)}/2\rfloor$ in which every pair of sets are in
the same relative position with respect to the linear ordering on
$\mathbb{Z}$. This improves previous bounds of Dudek–Grytczuk–Ruciński and of
Anastos–Jin–Kwan–Sudakov and is sharp up to a factor of $2$. For large $r$, we
even obtain such a subcollection of size $\lfloor(1-o(1))\cdot
n^{1/(2^{r}-1)}\rfloor$, which is asymptotically tight (here, the $o(1)$-term
tends to zero as $r\to\infty$, regardless of the value of $n$).

Furthermore, we prove a multiparameter extension of this result where one
wants to find a clique of prescribed size $m_{P}$ for each relative position
pattern $P$. Our bound is sharp for all choices of parameters $m_{P}$, up to a
constant factor depending on $r$ only. This answers questions of
Anastos–Jin–Kwan–Sudakov and of Dudek–Grytczuk–Ruciński.

##  1 Introduction

Ramsey Theory is one of the most active areas of combinatorics, with a rich
history spanning an entire century and many exciting recent results (e.g. [2,
11, 13, 17], to mention just a few). The basic philosophy behind the results
in this area is that any sufficiently large structure, even if completely
disordered, must contain a homogeneous-looking substructure of a prescribed
size. Such Ramsey results have been established in a variety of contexts, and
improving the quantitative bounds in these results is of great interest (see
the books [10] and [16] for a general overview of the area of Ramsey theory).

Here, we are interested in a Ramsey problem about ordered hypergraph matching.
An $r$-uniform hypergraph matching $\mathcal{H}$ is a finite collection of
pairwise disjoint sets, each of size $r$. These sets are called hyperedges,
and their union is called the vertex set of the hypergraph. An _ordered_
$r$-uniform hypergraph matching $\mathcal{H}$ is such a $r$-uniform hypergraph
matching equipped with a total ordering on the vertex set.

Now, given an ordered hypergraph matching $\mathcal{H}$, we want to find a
large submatching in $\mathcal{H}$ which looks homogeneous with respect to the
linear order on $\mathbb{Z}$. More precisely, if $\mathcal{H}$ is an ordered
$r$-uniform hypergraph matching, then for any two edges $e,f\in\mathcal{H}$ we
can consider the relative order of the vertices in $e$ and $f$. In other
words, we can consider the ordered $r$-uniform hypergraph matching
$\\{e,f\\}$. This can be represented by a string of length $2r$ consisting of
$r$ times the letter $\rm A$ and $r$ times the letter $\rm B$. For example if
$e=\\{1,2,5\\}$ and $f=\\{3,4,6\\}$ and the vertices in $e\cup
f=\\{1,2,\dots,6\\}$ are ordered in the natural way, we obtain the pattern
$\rm AABBAB$ encoding the relative order of the vertices $e$ and $f$. Note
that this pattern is equivalent to the pattern $\rm BBAABA$ upon interchanging
the roles of $e$ and $f$. To make the representation unique, let us impose the
condition that the string needs to start with the letter $\rm A$. We can now
define an _$r$ -pattern_ to be a string in $\\{{\rm A},{\rm B}\\}^{2r}$
starting with $\rm A$ and consisting of $r$ times the letter $\rm A$ and $r$
times the letter $\rm B$.

For any ordered $r$-uniform hypergraph matching $\mathcal{H}$, for any two
edges $e,f\in\mathcal{H}$ we can consider the corresponding $r$-pattern
described by $\\{e,f\\}$. If there is some $r$-pattern $P$ such that for every
pair of edges $e,f\in\mathcal{H}$ the $r$-pattern described by $\\{e,f\\}$ is
$P$, then we call the $r$-uniform hypergraph matching a $P$-clique. We say
that $\mathcal{H}$ contains a $P$-clique of size $m$, if there is some subset
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$ of $|\mathcal{H}^{\prime}|=m$ edges
forming a $P$-clique.

Now we have a natural Ramsey-type question: given a hypergraph matching
$\mathcal{H}$ what is the size of the largest $P$-clique in $\mathcal{H}$ over
all choices of the pattern $P$? In the graph case $r=2$, this question was
introduced and solved by Dudek, Grytczuk, and Ruciński [6]. They showed that
any matching of size $n^{3}+1$ contains a $P$-clique of size $n+1$, where $P$
is one of the three possible 2-patterns: AABB, ABAB, or ABBA. Moreover, they
constructed a matching of size $n^{3}$ without $P$-cliques of size $n+1$ for
any pattern $P$. In a later work, the same authors [7] systematically studied
the higher uniformity version of the problem and showed that any ordered
$r$-uniform hypergraph with $C_{r}n^{3^{r-1}}$ edges contains a $P$-clique of
size $n+1$ for some $r$-pattern $P$. On the other hand, they could only
construct a matching of size $n^{2^{r-1}+2}$ without any $P$-cliques of size
$n+1$. These bounds were substantially improved by Anastos, Jin, Kwan, and
Sudakov [1]: they reduced the upper bound to $C_{r}n^{(r+1)2^{r-2}}$ and
constructed an example with $n^{2^{r}-1}$ edges, thus, showing that the
correct exponent of $n$ is roughly $2^{r}$ rather than $3^{r}$. They also got
a sharp exponent of $n$ in the cases $r=3$ and $r=4$. However, their
techniques required a substantial case analysis already for $r=4$ and do not
seem to generalize to large $r$.

In this paper, we determine the correct behavior of the Ramsey problem for
ordered $r$-uniform hypergraph matchings for all values of $r$.

######  Theorem 1.1.

Let $r$ and $m$ be positive integers. Let $\mathcal{H}$ be an ordered
$r$-uniform hypergraph matching. For every $r$-pattern $P$, assume that every
$P$-clique contained in $\mathcal{H}$ has size at most $m$. Then the number of
edges in $\mathcal{H}$ is bounded by

$|\mathcal{H}|\leq C_{r}\cdot m^{2^{r}-1},$

where $C_{r}=2^{r-1}(r-1)!$.

By the aforementioned construction of Anastos, Jin, Kwan, and Sudakov [1,
Theorem 1.7], the upper bound in Theorem 1.1 is tight up to the constant
factor $C_{r}$. Theorem 1.1 can also be restated in the notation of [1] as
follows. For an ordered matching $\mathcal{H}$, let $L(\mathcal{H})$ be the
size of the largest $P$-clique in $\mathcal{H}$ for any pattern $P$. Define a
Ramsey function $L_{r}(n)$ to be the minimum of $L(\mathcal{H})$ over all
$r$-uniform ordered hypergraph matchings $\mathcal{H}$ with $n$ edges. Then
our Theorem 1.1 can be restated as $L_{r}(n)\geq C_{r}^{-1/(2^{r}-1)}\cdot
n^{1/(2^{r}-1)}$. Comparing this with the construction in [1] giving
$L_{r}(n)\leq\lceil n^{1/(2^{r}-1)}\rceil$, we obtain

$\lceil n^{1/(2^{r}-1)}\rceil\geq L_{r}(n)\geq C_{r}^{-1/(2^{r}-1)}\cdot
n^{1/(2^{r}-1)}>\frac{1}{2}n^{1/(2^{r}-1)}.$

So this determines $L_{r}(n)$ up to a constant of at most $2$ for all $r$ and
$n$ (and the constant factor
$C_{r}^{-1/(2^{r}-1)}=(2^{r-1}(r-1)!)^{-1/(2^{r}-1)}$ actually approaches 1 as
$r$ tends to infinity).

In Theorem 1.1, for every $r$-pattern $P$, the size of every $P$-clique
contained in $\mathcal{H}$ is bounded by $m$. Dudek–Grytczuk–Ruciński and
Anastos–Jin–Kwan–Sudakov also asked for the maximum size of $|\mathcal{H}|$
when bounding the sizes of the $P$-cliques in $\mathcal{H}$ by different
numbers for different $r$-patterns $P$. In other words, how large can
$|\mathcal{H}|$ be, if for each $r$-pattern $P$ the size of each $P$-clique in
$\mathcal{H}$ is at at most a given number $m_{P}$? We also answer this more
general question up to a constant factor depending on $r$.

To state the answer to this multi-parameter version of the problem, we need
some more notation. First, it turns out that not for every $r$-pattern $P$ it
is actually possible to form a large $P$-clique at all. One can show that this
is only possible if $P$ has a particular block structure, where the string
$P\in\\{{\rm A},{\rm B}\\}^{2r}$ can be divided into (consecutive) blocks of
even size such that within each block the string reads either
$\rm{AA}\dots\rm{A}\rm{BB}\dots\rm{B}$ with equally many $\rm{A}$’s and
$\rm{B}$’s or $\rm{BB}\dots\rm{B}\rm{AA}\dots\rm{A}$ with equally many
$\rm{A}$’s and $\rm{B}$’s. Following [1], we call such a decomposition of an
$r$-pattern $P$ a _block partition_. For example, the $5$-pattern
$\rm{AABBBABBAA}$ has the block partition $\rm{AABB|BA|BBAA}$, whereas the
$5$-pattern $\rm{AABABBABBA}$ does not have a block partition.

It is not hard to see that every $r$-pattern $P$ has at most one block
decomposition. Following [7], we call an $r$-pattern with a block
decomposition _collectable_ (then it turns out that the collectable
$r$-patterns are precisely the $r$-patterns $P$ for which there exist
arbitrarily large $P$-cliques, this was shown in [7]).

Given a positive integer $r$, we call a sequence
$\lambda=(\lambda_{1},\dots,\lambda_{s})$ of positive integers with
$\lambda_{1}+\dots+\lambda_{s}=r$ an _ordered partition of $r$_. One may think
of $\lambda$ as a partition of the set $\\{1,\dots,r\\}$ into non-empty
intervals. We call $s$ the _number of parts_ of the ordered partition
$\lambda=(\lambda_{1},\dots,\lambda_{s})$. For two ordered partitions
$\lambda=(\lambda_{1},\dots,\lambda_{s})$ and
$\lambda^{\prime}=(\lambda^{\prime}_{1},\dots,\lambda^{\prime}_{s^{\prime}})$
of $r$, we write $\lambda\succ\lambda^{\prime}$ if the identity
$\lambda^{\prime}_{1}+\dots+\lambda^{\prime}_{s^{\prime}}=r$ can be obtained
from $\lambda_{1}+\dots+\lambda_{s}=r$ by splitting some summands into smaller
sub-summands (without changing the order or re-combining any summands). In the
language of partitions of $\\{1,\dots,r\\}$ into intervals, we have
$\lambda\succ\lambda^{\prime}$ if the partition corresponding to
$\lambda^{\prime}$ is a refinement of the partition corresponding to
$\lambda$.

For any ordered partition $\lambda=(\lambda_{1},\dots,\lambda_{s})$ of $r$,
let $\mathcal{P}(\lambda)$ be the set of collectable $r$-patterns $P$ such
that the block partition of $P$ consists of $s$ blocks of sizes
$2\lambda_{1},2\lambda_{2},\dots,2\lambda_{s}$ (in this order). Note that the
sets $\mathcal{P}(\lambda)$ for all ordered partitions $\lambda$ or $r$ form a
partition of the set of all collectable $r$-patterns. With this notation, our
multi-parameter generalization of Theorem 1.1 can be stated as follows.

######  Theorem 1.2.

Let $r$ be a positive integer, and consider a positive integer $m_{P}$ for
every collectable $r$-pattern $P$. Let $\mathcal{H}$ be an ordered $r$-uniform
hypergraph matching, and assume that for every collectable $r$-pattern $P$,
every $P$-clique contained in $\mathcal{H}$ has size at most $m_{P}$. Then the
number of edges in $\mathcal{H}$ is bounded by

$|\mathcal{H}|\leq
2^{r-1}\sum_{\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}}\
\prod_{P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$
(1.1)

where the sum is over all sequences
$\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}$ of ordered
partitions of $r$ (note that then for $s=1,\dots,r$, the ordered partition
$\lambda^{(s)}$ must automatically have $s$ parts).

Note that Theorem 1.2 directly implies Theorem 1.1 by setting $m_{P}=m$ for
all collectable $r$-patterns $P$. Indeed, for every ordered partition
$\lambda=(\lambda_{1},\dots,\lambda_{s})$ of $r$, we have
$|\mathcal{P}(\lambda)|=2^{s-1}$. There are $(r-1)!$ different sequences
$\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}$ of ordered
partitions of $r$, and for each of them we have
$|\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})|=1+2+\dots+2^{r-1}=2^{r}-1$.
Hence the right-hand side of (1.1) simplifies to $2^{r-1}(r-1)!\cdot
m^{2^{r}-1}$ if $m_{P}=m$ for all $P$.

Our next result shows that the bound in Theorem 1.2 is tight up to a constant
factor depending on $r$.

######  Theorem 1.3.

Let $r$ be a positive integer, and consider a positive integer $m_{P}$ for
every collectable $r$-pattern $P$. Then there exists an ordered $r$-uniform
hypergraph matching $\mathcal{H}$, such that for every collectable $r$-pattern
$P$, every $P$-clique contained in $\mathcal{H}$ has size at most $m_{P}$, and
such that

$|\mathcal{H}|=\max_{\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}}\
\prod_{P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$
(1.2)

where the maximum is over all sequences
$\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}$ of ordered
partitions of $r$.

Note that the right-hand side of (1.2) differs from the right-hand side of
(1.1) by a factor of at most $2^{r-1}(r-1)!$. Indeed, there are exactly
$(r-1)!$ different sequences
$\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}$, and (1.2)
describes the largest of the $(r-1)!$ summands appearing on the right-hand
side of (1.1).

Thus, Theorems 1.2 and 1.3 determine, up to a factor of at most
$2^{r-1}(r-1)!$, the maximum size of $|\mathcal{H}|$ if for every collectable
$r$-pattern every $P$-clique in $\mathcal{H}$ has at most some given size
$m_{P}$.

After discussing some preliminaries in Section 2, we will prove Theorem 1.2
(which implies Theorem 1.1) in Section 3, and Theorem 1.3 in Section 4.

##  2 Preliminaries

The Erdős–Szekeres Theorem [8] states that any sequence of $n^{2}+1$ distinct
integers contains a monotone subsequence of length $n+1$. This is a classical
result in combinatorics with a rich family of generalizations and connections,
see for example [4, 9, 12, 15, 18].

We will need a multi-dimensional version of the the classical (one-
dimensional) Erdős–Szekeres Theorem. For our purposes, this multi-dimensional
version is most convenient to state in the following way. For a function
$\tau:\\{1,\dots,s\\}\to\\{1,-1\\}$ with $\tau(1)=1$, let us say that a
sequence of points $z_{1},\dots,z_{m}\in\mathbb{R}^{s}$ is _$\tau$ -monotone_
if for every $i\in\\{1,\dots,s\\}$ with $\tau(i)=1$ the $i$-th coordinates of
the points $z_{1},\dots,z_{m}$ form a strictly increasing sequence and for
every $i\in\\{1,\dots,s\\}$ with $\tau(i)=-1$ the $i$-th coordinates of the
points $z_{1},\dots,z_{m}$ form a strictly decreasing sequence.

######  Theorem 2.1 (Multi-dimensional Erdős–Szekeres Theorem).

Let $s$ be a positive integer. Furthermore, consider a positive integer
$m_{\tau}$ for every function $\tau:\\{1,\dots,s\\}\to\\{1,-1\\}$ with
$\tau(1)=1$. Let $Z\subseteq\mathbb{R}^{s}$ be a collection of points, whose
$|Z|\cdot s$ coordinates are all distinct. For each
$\tau:\\{1,\dots,s\\}\to\\{1,-1\\}$ with $\tau(1)=1$, assume that every
$\tau$-monotone sequence of points in $Z$ has length at most $m_{\tau}$. Then
the number of points in $Z$ is bounded by

$|Z|\leq\prod_{\tau}m_{\tau},$

where the product is over all functions $\tau:\\{1,\dots,s\\}\to\\{1,-1\\}$
with $\tau(1)=1$.

Furthermore, for any choice of positive integers $m_{\tau}$ for all functions
$\tau:\\{1,\dots,s\\}\to\\{1,-1\\}$ with $\tau(1)=1$, there exists a
collection of points $Z\subseteq\mathbb{R}^{s}$ of size
$|Z|=\prod_{\tau}m_{\tau}$ satisfying the conditions above.

This result was essentially proven in [7] and used to construct the ordered
hypergraph matchings with cliques of bounded sizes. We include a simple (and
fairly standard) proof for the reader’s convenience.

###### Proof.

Note that each function $\tau:\\{1,\ldots,s\\}\rightarrow\\{1,-1\\}$ with
$\tau(1)=1$ naturally defines a partial order $\prec_{\tau}$ on $Z$. Let
$\tau_{1},\ldots,\tau_{2^{s-1}}$ be the list of all such functions in an
arbitrary order. Then we are given positive integers $m_{\tau_{i}}$ for
$i=1,\dots,2^{s-1}$.

Let $Z\subseteq\mathbb{R}^{s}$ be as in the first part of the theorem
statement. By the assumption, for $i=1,\dots,2^{s-1}$, the length of any chain
in $(Z,\prec_{\tau_{i}})$ is at most $m_{\tau_{i}}$. By Dilworth’s Theorem [5]
applied to $(Z,\prec_{\tau_{1}})$, there exists an
$\prec_{\tau_{1}}$-antichain $Z_{1}\subseteq Z$ of size at least
$|Z|/m_{\tau_{1}}$. Then by Dilworth’s Theorem applied to
$(Z_{1},\prec_{\tau_{2}})$, there exists an $\prec_{\tau_{2}}$-antichain
$Z_{2}\subseteq Z_{1}$ of size at least
$|Z_{1}|/m_{\tau_{2}}\geq|Z|/(m_{\tau_{1}}m_{\tau_{2}})$. Continuing this
process for all $i=1,\ldots,2^{s-1}$, we obtain a subset

$Z^{\prime}=Z_{2^{s-1}}\subseteq\ldots\subseteq Z_{1}\subseteq Z$

of size $|Z^{\prime}|\geq|Z|/\prod_{i=1}^{2^{s-1}}m_{\tau_{i}}$ which is an
antichain with respect to $\prec_{\tau_{i}}$ for $i=1,\dots,2^{s-1}$. However,
any two vectors in $\mathbb{R}^{s}$ with distinct coordinates are comparable
with respect to exactly one of the partial orders
$\prec_{\tau_{1}},\dots,\prec_{\tau_{2^{s-1}}}$. Thus, we must have
$|Z^{\prime}|\leq 1$, implying
$|Z|\leq\prod_{i=1}^{2^{s-1}}m_{\tau_{i}}=\prod_{\tau}m_{\tau}$, as desired.

Now we prove the second part of the theorem, i.e. we construct a collection of
points $Z\subseteq\mathbb{R}^{s}$ achieving equality in the bound above. Let
$N$ be a sufficiently large integer such that $N\geq 3m_{\tau_{i}}$ for
$i=1,\dots,2^{s-1}$. For a sequence of numbers $a=(a_{1},\ldots,a_{2^{s-1}})$,
where $a_{i}\in\\{1,\ldots,m_{\tau_{i}}\\}$ for $i=1,\ldots,2^{s-1}$, we
define a vector $z(a)=(z(a)_{1},\ldots,z(a)_{s})\in\mathbb{R}^{s}$ by setting

$z(a)_{j}=\sum_{i=1}^{2^{s-1}}N^{i}\tau_{i}(j)a_{i}$ (2.1)

for $j=1,\dots,s$. Let $Z\subseteq\mathbb{R}^{s}$ be the collection of all
points $z(a)$ for all tuples $a=(a_{1},\ldots,a_{2^{s-1}})$ with
$a_{i}\in\\{1,\ldots,m_{\tau_{i}}\\}$ for $i=1,\ldots,2^{s-1}$. First note
that by the choice of $N$, all the sums of the form (2.1) are pairwise
distinct for all possible choices of sequences $a$ and all $j=1,\dots,s$. So
points the $|Z|\cdot s$ coordinates of the points $Z$ are all distinct
coordinates, and we have
$|Z|=\prod_{i=1}^{2^{s-1}}m_{\tau_{i}}=\prod_{\tau}m_{\tau}$. It remains to
show that for any $i=1,\ldots,2^{s-1}$, any $\prec_{\tau_{i}}$-chain in $Z$
has length at most $m_{\tau_{i}}$.

So let us some $k\in\\{1,\ldots,2^{s-1}\\}$, and suppose that for some
sequences $a^{(1)},\ldots,a^{(t)}$ as above, the points
$z(a^{(1)}),\ldots,z(a^{(t)})\in Z$ form a $\tau_{k}$-monotone sequence. That
means that for each $j\in\\{1,\ldots,s\\}$ we have
$\tau_{k}(j)z(a^{(1)})_{j}<\dots<\tau_{k}(j)z(a^{(t)})_{j}$. Pick an arbitrary
pair of indices $1\leq\ell<\ell^{\prime}\leq t$ and let
$k^{\prime}\in\\{1,\ldots,2^{s-1}\\}$ be the maximum index such that
$a^{(\ell)}_{k^{\prime}}\neq a^{(\ell^{\prime})}_{k^{\prime}}$.

Note that by (2.1), for any $j\in\\{1,\ldots,s\\}$ we have

$z(a^{(\ell)})_{j}-z(a^{(\ell^{\prime})})_{j}=\sum_{i=1}^{k^{\prime}}N^{i}\tau_{i}(j)(a^{(\ell)}_{i}-a^{(\ell^{\prime})}_{i}).$

The $k^{\prime}$-th term in the sum above is larger in absolute value than all
the smaller terms combined, which implies that the numbers
$z(a^{(\ell)})_{j}-z(a^{(\ell^{\prime})})_{j}$ and
$\tau_{k^{\prime}}(j)(a^{(\ell)}_{k^{\prime}}-a^{(\ell^{\prime})}_{k^{\prime}})$
have the same sign. On the other hand, we know that
$\tau_{k}(j)z(a^{(\ell)})_{j}<\tau_{k}(j)z(a^{(\ell^{\prime})})_{j}$. So we
conclude that

$\tau_{k}(j)\tau_{k^{\prime}}(j)a^{(\ell)}_{k^{\prime}}<\tau_{k}(j)\tau_{k^{\prime}}(j)a^{(\ell^{\prime})}_{k^{\prime}}$
(2.2)

holds for every $j\in\\{1,\ldots,s\\}$. Letting $j=1$ and using
$\tau_{k}(1)=\tau_{k^{\prime}}(1)=1$ implies that
$a^{(\ell)}_{k^{\prime}}<a^{(\ell^{\prime})}_{k^{\prime}}$. Combining this
with (2.2), for $j=2,\dots,s$ we get $\tau_{k}(j)=\tau_{k^{\prime}}(j)$,
meaning that the functions $\tau_{k}$ and $\tau_{k^{\prime}}$ coincide and we
in fact have $k=k^{\prime}$.

We conclude that for any $1\leq\ell<\ell^{\prime}\leq t$, the last coordinate
where the sequences $a^{(\ell)}$ and $a^{(\ell^{\prime})}$ differ is always
equal to $k$. In particular, all $k$-th coordinates of the sequences
$a^{(1)},\ldots,a^{(t)}$ are pairwise distinct. Since these coordinates take
values in the set $\\{1,\ldots,m_{\tau_{k}}\\}$, we can conclude that $t\leq
m_{\tau_{k}}$. This shows that the longest $\tau_{k}$-monotone sequence in $Z$
has length at most $m_{\tau_{k}}$, as desired. ∎

In order to make use of Theorem 2.1 in our context, the following notation
will be helpful. Consider an ordered partition
$\lambda=(\lambda_{1},\dots,\lambda_{s})$ of $r$. Then for any function
$\tau:\\{1,\dots,s\\}\to\\{1,-1\\}$ with $\tau(1)=1$, we define a collectable
$r$-pattern $P(\lambda,\tau)\in\mathcal{P}(\lambda)$ as follows. The block
partition of $P$ consists of $s$ blocks of sizes
$2\lambda_{1},\dots,2\lambda_{s}$ (in this order). For each
$i\in\\{1,\dots,s\\}$ with $\tau(i)=1$, in the $i$-th block we take
$\lambda_{i}$ times the letter $\rm A$ followed by $\lambda_{i}$ times the
letter $\rm B$. And for each $i\in\\{1,\dots,s\\}$ with $\tau(i)=-1$, in the
$i$-th block we take $\lambda_{i}$ times the letter $\rm B$ followed by
$\lambda_{i}$ times the letter $\rm A$. This gives a valid block decomposition
of an $r$-pattern, and we call the resulting $r$-pattern $P(\lambda,\tau)$.
Note that by definition, we have $P(\lambda,\tau)\in\mathcal{P}(\lambda)$ and
in particular the $r$-pattern $P(\lambda,\tau)$ is collectable. Furthermore,
every $r$-pattern $P\in\mathcal{P}(\lambda)$ is of the form
$P=P(\lambda,\tau)$ for some function $\tau:\\{1,\dots,s\\}\to\\{1,-1\\}$ with
$\tau(1)=1$.

##  3 Proof of the upper bound

Every ordered $r$-uniform hypergraph matching can be realized by assigning
(positive) integers to the vertices and taking the total ordering on the
vertex set to be the natural ordering of the integers. In order to prove
Theorem 1.2, we can therefore assume without loss of generality that our
ordered $r$-uniform hypergraph matching $\mathcal{H}$ is given in this way. In
other words, we can take $\mathcal{H}$ to be a finite collection of pairwise
disjoint subsets $e\subseteq\mathbb{Z}$, each of size $|e|=r$. This somewhat
simplifies the notation in our proof.

As observed for example in [1], for ordered $r$-uniform hypergraph matching
$\mathcal{H}$ with a certain $r$-partite structure, one can bound the size
$|\mathcal{H}|$ in terms of the maximum sizes of the $P$-cliques contained in
$|\mathcal{H}|$ for each $r$-pattern $P$, just by using the multi-dimensional
Erdős–Szekeres Theorem. The following definition describes a more general
condition under which this is possible.

######  Definition 3.1.

Let $r$ be a positive integer, and consider a finite collection $\mathcal{H}$
of pairwise disjoint subsets $e\subseteq\mathbb{Z}$, each of size $|e|=r$. For
an ordered partition $\lambda=(\lambda_{1},\dots,\lambda_{s})$ of $r$, we say
that $\mathcal{H}$ is _$\lambda$ -partite_ if there are
$x_{0},x_{1},\dots,x_{s}\in\mathbb{R}\setminus\mathbb{Z}$ with
$x_{0}<x_{1}<\dots<x_{s}$ such that we have
$|e\cap(x_{i-1},x_{i})|=\lambda_{i}$ for every $e\in\mathcal{H}$ and every
$i=1,\dots,s$. We say that $\mathcal{H}$ is _interval-wise $\lambda$-partite_
if $x_{0}<x_{1}<\dots<x_{s}$ can be chosen such that in addition to the
previous condition, for each $i=1,\dots,s$, the intervals
$\operatorname{conv}(e\cap(x_{i-1},x_{i}))$ are pairwise disjoint for all
$e\in\mathcal{H}$.

Intuitively speaking, for an ordered partition
$\lambda=(\lambda_{1},\dots,\lambda_{s})$ of $r$, saying that $\mathcal{H}$ is
$\lambda$-partite means that there are $s$ intervals
$(x_{0},x_{1}),(x_{1},x_{2}),\dots,(x_{s-1},x_{s})$ such that every hyperegde
$e\in\mathcal{H}$ has exactly $\lambda_{1}$ elements in the first interval
$(x_{0},x_{1})$, exactly $\lambda_{2}$ elements in the second interval
$(x_{1},x_{2})$, and so on. For $\mathcal{H}$ to be interval-wise
$\lambda$-partite means that the sub-intervals of $(x_{0},x_{1})$ spanned by
the intersections $e\cap(x_{0},x_{1})$ are pairwise disjoint for all
$e\in\mathcal{H}$, and similarly for the sub-intervals of $(x_{1},x_{2})$
spanned by the intersections $e\cap(x_{1},x_{2})$, and so on.

Note that $\mathcal{H}$ is always $\lambda$-partite for the ordered partition
$\lambda=(r)$ of $r$ into a single part (taking $(x_{0},x_{1})$ to be some
interval containing all elements of all $e\in\mathcal{H}$). Also note that if
$\mathcal{H}$ is $\lambda$-partite for some ordered partition $\lambda$, then
$\mathcal{H}$ is automatically also $\lambda^{\prime}$-partite for all
$\lambda^{\prime}$ with $\lambda^{\prime}\succ\lambda$. Furthermore, for the
ordered partition $\lambda=(1,1,\dots,1)$ of $r$ into $r$ parts, it is
equivalent for $\mathcal{H}$ to be $\lambda$-partite or to be interval-wise
$\lambda$-partite.

Finally, if $\mathcal{H}$ is interval-wise $\lambda$-partite for some ordered
partition $\lambda$ of $r$, then any two edges $e,f\in\mathcal{H}$ form some
$r$-pattern in $\mathcal{P}(\lambda)$. Which of the $r$-patterns in
$\mathcal{P}(\lambda)$ is formed by $e$ and $f$ depends on the the order of
the intervals $\operatorname{conv}(e\cap(x_{i-1},x_{i}))$ and
$\operatorname{conv}(f\cap(x_{i-1},x_{i}))$ appearing in Definition 3.1 (for
each $i$, there are two possibilities which of the two intervals comes first).

If $\mathcal{H}$ is interval-wise $\lambda$-partite for some ordered partition
$\lambda$ of $r$, then a bound on $|\mathcal{H}|$ under the assumptions in
Theorem 1.2 follows directly from the multi-dimensional Erdős–Szekeres Theorem
(see Theorem 2.1).

######  Observation 3.2.

Let $r$ be a positive integer, and let
$\lambda=(\lambda_{1},\dots,\lambda_{s})$ be an ordered partition of $r$.
Furthermore, consider a positive integer $m_{P}$ for every $r$-pattern
$P\in\mathcal{P}(\lambda)$. Let $\mathcal{H}$ be a finite collection of
pairwise disjoint subsets $e\subseteq\mathbb{Z}$, each of size $|e|=r$, such
that $\mathcal{H}$ is interval-wise $\lambda$-partite. For every
$P\in\mathcal{P}(\lambda)$, assume that every $P$-clique contained in
$\mathcal{H}$ has size at most $m_{P}$. Then we have

$|\mathcal{H}|\leq\prod_{P\in\mathcal{P}(\lambda)}m_{P}.$

###### Proof.

As $\mathcal{H}$ is interval-wise $\lambda$-partite, there exist
$x_{0}<x_{1}<\dots<x_{s}$ such that for each $i=1,\dots,s$, we have
$|e\cap(x_{i-1},x_{i})|=\lambda_{i}>0$ for every $e\in\mathcal{H}$ and the
intervals $\operatorname{conv}(e\cap(x_{i-1},x_{i}))$ are pairwise disjoint
for all $e\in\mathcal{H}$. Now, for every $e\in\mathcal{H}$, let us define a
point $z(e)\in\mathbb{R}^{s}$ by taking

$z(e)=(\min(e\cap(x_{0},x_{1})),\min(e\cap(x_{1},x_{2})),\dots,\min(e\cap(x_{s-1},x_{s}))),$

and define $Z=\\{z(e)\mid e\in\mathcal{H}\\}\subseteq\mathbb{R}^{s}$. As the
sets $e\in\mathcal{H}$ are pairwise disjoint, the all the coordinates of the
points $z(e)$ for $e\in\mathcal{H}$ are distinct.

For every function $\tau:\\{1,\dots,s\\}\to\\{1,-1\\}$ with $\tau(1)=1$, let
us define $m_{\tau}=m_{P(\lambda,\tau)}$ (recall that
$P(\lambda,\tau)\in\mathcal{P}(\lambda)$ was defined at the end of Section 2).
We claim that then every $\tau$-monotone sequence of points in
$Z\subseteq\mathbb{R}^{s}$ has length at most $m_{\tau}$.

Indeed, for any $\rho:\\{1,\dots,s\\}\to\\{1,-1\\}$ with $\tau(1)=1$, consider
$e^{(1)},e^{(2)},\dots,e^{(t)}\in\mathcal{H}$ such that the point sequence
$z(e^{(1)}),z(e^{(2)}),\dots,z(e^{(t)})$ is a $\tau$-monotone sequence in
$Z\subseteq\mathbb{R}^{s}$. Then for any index $i\in\\{1,\dots,s\\}$ with
$\tau(i)=1$ we have
$\min(e^{(1)}\cap(x_{i-1},x_{i}))<\dots<\min(e^{(t)}\cap(x_{i-1},x_{i}))$, and
in particular
$\min(e^{(\ell)}\cap(x_{i-1},x_{i}))<\min(e^{(\ell^{\prime})}\cap(x_{i-1},x_{i}))$
for any $1\leq\ell<\ell^{\prime}\leq t$. Since furthermore the intervals
$\operatorname{conv}(e^{(\ell)}\cap(x_{i-1},x_{i}))$ and
$\operatorname{conv}(e^{(\ell^{\prime})}\cap(x_{i-1},x_{i}))$ are disjoint,
this means that all elements of $e^{(\ell)}\cap(x_{i-1},x_{i})$ are smaller
than all elements of $e^{(\ell^{\prime})}\cap(x_{i-1},x_{i})$. Similarly, for
any $i\in\\{1,\dots,s\\}$ with $\tau(i)=-1$ and any
$1\leq\ell<\ell^{\prime}\leq t$, all elements of
$e^{(\ell)}\cap(x_{i-1},x_{i})$ are larger than all elements of
$e^{(\ell^{\prime})}\cap(x_{i-1},x_{i})$. Since $x_{0}<x_{1}<\dots<x_{s}$ and
$|e^{(\ell)}\cap(x_{i-1},x_{i})|=|e^{(\ell^{\prime})}\cap(x_{i-1},x_{i})|=\lambda_{i}$
for all $i=1,\dots,s$, this shows that $e^{(\ell)}$ and $e^{(\ell^{\prime})}$
form the pattern $P(\lambda,\tau)$ for all $1\leq\ell<\ell^{\prime}\leq t$.
Hence $e^{(1)},e^{(2)},\dots,e^{(t)}\in\mathcal{H}$ form a
$P(\lambda,\tau)$-clique and therefore $t\leq m_{P(\lambda,\tau)}=m_{\rho}$.
So every $\rho$-monotone sequence in $Z$ indeed has length at most $m_{\rho}$.

Applying Theorem 2.1 now gives

$|\mathcal{H}|=|Z|\leq\prod_{\begin{subarray}{c}\tau:\\{1,\dots,s\\}\to\\{1,-1\\}\\\
\tau(1)=1\end{subarray}}m_{\tau}=\prod_{\begin{subarray}{c}\tau:\\{1,\dots,s\\}\to\\{1,-1\\}\\\
\tau(1)=1\end{subarray}}m_{P(\lambda,\tau)}=\prod_{P\in\mathcal{P}(\lambda)}m_{P},$

as desired. ∎

The main step in our proof of Theorem 1.2 is showing the following lemma,
which roughly speaking states that for every large $\lambda$-partite
$\mathcal{H}$ we can find a large $\mathcal{H}^{*}\subseteq\mathcal{H}$ which
is interval-wise $\lambda$-partite or we can find a large
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$ which is $\lambda^{\prime}$-partite
for some ordered partition $\lambda^{\prime}$ of $r$ with
$\lambda\succ\lambda^{\prime}$. In the first case, we can then apply
Observation 3.2, whereas in the second case we can repeat the argument with
$\lambda^{\prime}$ instead of $\lambda$.

######  Lemma 3.3.

Let $r$ be a positive integer, and let
$\lambda=(\lambda_{1},\dots,\lambda_{s})$ be an ordered partition of $r$ into
$s<r$ parts. For every ordered partition $\lambda^{\prime}$ of $r$ into $s+1$
parts with $\lambda\succ\lambda^{\prime}$, consider some positive integer
$M_{\lambda^{\prime}}$, and let
$M=\sum_{\lambda^{\prime}}M_{\lambda^{\prime}}$ be the sum of all these
positive integers. Let $\mathcal{H}$ be a finite collection of pairwise
disjoint subsets $e\subseteq\mathbb{Z}$, each of size $|e|=r$, such that
$\mathcal{H}$ is $\lambda$-partite. Then at least one of the following two
statements holds:

  * (a)

There is a sub-collection $\mathcal{H}^{*}\subseteq\mathcal{H}$ of size
$|\mathcal{H}^{*}|\geq|\mathcal{H}|/(2M)$ such that $\mathcal{H}^{*}$ is
interval-wise $\lambda$-partite.

  * (b)

For some ordered partition $\lambda^{\prime}$ of $r$ into $s+1$ parts with
$\lambda\succ\lambda^{\prime}$, there is a sub-collection
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$ of size
$|\mathcal{H}^{\prime}|>M_{\lambda^{\prime}}$ such that $\mathcal{H}^{\prime}$
is $\lambda^{\prime}$-partite.

###### Proof.

Suppose that $\mathcal{H}$ does not have a subcollection
$\mathcal{H}^{\prime}$ as in (b). We need to show that then (a) holds. Let
$x_{0}<x_{1}<\dots<x_{s}$ be as in Definition 3.1. For every
$e\in\mathcal{H}$, we consider the intervals $e\cap(x_{i-1},x_{i})$ for
$i=1,\dots,s$. Our goal is to find a subcollection
$\mathcal{H}^{*}\subseteq\mathcal{H}$ of size
$|\mathcal{H}^{*}|\geq|\mathcal{H}|/(2M)$ such that for each $i=1,\dots,s$,
the intervals $\operatorname{conv}(e\cap(x_{i-1},x_{i}))$ are pairwise
disjoint for all $e\in\mathcal{H}^{*}$. Note that for any $i=1,\dots,s$ and
any $e\in\mathcal{H}$, the interval
$\operatorname{conv}(e\cap(x_{i-1},x_{i}))$ is a closed sub-interval of
$(x_{i-1},x_{i})$. Furthermore, the endpoints of all these sub-intervals are
distinct (as all $e\in\mathcal{H}$ are pairwise disjoint subsets of
$\mathbb{Z}$).

Let us consider an auxiliary graph $G$ with vertex set $\mathcal{H}$, where
for $e,e^{\prime}\in\mathcal{H}$ we draw an edge between $e$ and $e^{\prime}$
if
$\operatorname{conv}(e\cap(x_{i-1},x_{i}))\cap\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))\neq\emptyset$
for some $i\in\\{1,\dots,s\\}$. Our goal is then to show that the graph $G$
has an independent set of size at least $|\mathcal{H}|/(2M)$.

Note that for any two closed intervals $[a,b]$ and $[c,d]$ with
$[a,b]\cap[c,d]\neq\emptyset$ we have $a\in[c,d]$ or $c\in[a,b]$. Hence we can
orient the edges of $G$ in such a way that for any
$e,e^{\prime}\in\mathcal{H}$ with an edge from $e$ to $e^{\prime}$ there is an
index $i\in\\{1,\dots,s\\}$ with
$\min(e\cap(x_{i-1},x_{i}))\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$.

In order to show that the graph $G$ contains an independent set of size at
least $|\mathcal{H}|/(2M)$, it suffices to show that $G$ has average degree at
most $2M-1$ (by a well-known result of Caro [3] and Wei [19]). Considering the
orientation of the edges of $G$, it therefore suffices to show that for every
$e\in\mathcal{H}$ there are at most $M-1$ outgoing edges at $e$ in the graph
$G$ (then there are at most $(M-1)|\mathcal{H}|$ total edges in $G$ and hence
the average degree is at most $2M-2$).

So let us now fix some $e\in\mathcal{H}$. We need to show that there are at
most $M-1$ different $e^{\prime}\in\mathcal{H}\setminus\\{e\\}$ such that
$\min(e\cap(x_{i-1},x_{i}))\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$
for some index $i\in\\{1,\dots,s\\}$.

For every index $i\in\\{1,\dots,s\\}$ with $\lambda_{i}=1$, we have
$|e^{\prime}\cap(x_{i-1},x_{i})|=\lambda_{i}=1$ for every
$e^{\prime}\in\mathcal{H}$, and the singleton sets
$e^{\prime}\cap(x_{i-1},x_{i})$ are all distinct for all
$e^{\prime}\in\mathcal{H}$ (as all $e^{\prime}\in\mathcal{H}$ are pairwise
disjoint). Hence we cannot have
$\min(e\cap(x_{i-1},x_{i}))\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$
for any $e^{\prime}\in\mathcal{H}\setminus\\{e\\}$ when $\lambda_{i}=1$.

We claim that for each $i\in\\{1,\dots,s\\}$ with $\lambda_{i}\geq 2$, there
can be at most $\sum_{\lambda^{\prime}}M_{\lambda^{\prime}}-1$ different
$e^{\prime}\in\mathcal{H}\setminus\\{e\\}$ with
$\min(e\cap(x_{i-1},x_{i}))\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$,
where the sum is over all ordered partitions $\lambda^{\prime}$ of $r$ into
$s+1$ parts that can be obtained from $\lambda$ by dividing the $i$-th part
$\lambda_{i}$ into two pieces. This suffices to finish the proof, since then
the total number of $e^{\prime}\in\mathcal{H}\setminus\\{e\\}$ with
$\min(e\cap(x_{i-1},x_{i}))\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$
for some $i\in\\{1,\dots,s\\}$ is at most

$\sum_{\begin{subarray}{c}i\in\\{1,\dots,s\\}\\\ \lambda_{i}\geq
2\end{subarray}}\left(\left(\sum_{\begin{subarray}{c}\lambda^{\prime}\text{obtained
from }\lambda\text{ by}\\\ \text{dividing }\lambda_{i}\text{into two
parts}\end{subarray}}\\!\\!M_{\lambda^{\prime}}\right)-1\right)=\sum_{\lambda^{\prime}}M_{\lambda^{\prime}}-|\\{i\in\\{1,\dots,s\\}\mid\lambda_{i}\geq
2\\}|\leq\sum_{\lambda^{\prime}}M_{\lambda^{\prime}}-1=M-1,$

where in the second and third term the sum is over all ordered partitions
$\lambda^{\prime}$ of $r$ into $s+1$ parts with $\lambda\succ\lambda^{\prime}$
(note that each of these ordered partitions is obtained by dividing some part
$\lambda_{i}$ of $\lambda$ with $\lambda_{i}\geq 2$ into two parts). Also note
that for the inequality sign we have used that there must at least one index
$i\in\\{1,\dots,s\\}$ with $\lambda_{i}\geq 2$, since $s<r$.

It remains to prove the above claim, so fix some index $i\in\\{1,\dots,s\\}$
with $\lambda_{i}\geq 2$. There are $\lambda_{i}-1$ different ordered
partitions $\lambda^{\prime}$ that can be obtained from $\lambda$ by dividing
$\lambda_{i}$ into two parts, namely the ordered partitons
$\mu^{(1)}=(\lambda_{1},\dots,\lambda_{i-1},1,\lambda_{i}-1,\lambda_{i+1},\dots,\lambda_{s}),\
\mu^{(2)}=(\lambda_{1},\dots,\lambda_{i-1},2,\lambda_{i}-2,\lambda_{i+1},\dots,\lambda_{s}),\
\dots,\
\linebreak\mu^{(\lambda_{i}-1)}=(\lambda_{1},\dots,\lambda_{i-1},\lambda_{i}-1,1,\lambda_{i+1},\dots,\lambda_{s})$.
Defining $y=\min(e\cap(x_{i-1},x_{i}))\in\mathbb{Z}$, we need to show that
there are at most $\sum_{j=1}^{\lambda_{i}-1}M_{\mu^{(j)}}-1$ different
$e^{\prime}\in\mathcal{H}\setminus\\{e\\}$ with
$y\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$. Note that for every
such $e^{\prime}\in\mathcal{H}\setminus\\{e\\}$, we also have
$y+0.1\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$, since
$\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$ is a closed interval with
endpoints in $\mathbb{Z}\setminus\\{y\\}$. We furthermore also have
$y+0.1\in\operatorname{conv}(e\cap(x_{i-1},x_{i}))$ (recalling that
$y=\min(e\cap(x_{i-1},x_{i}))$ and that
$e\cap(x_{i-1},x_{i})\subseteq\mathbb{Z}$ is a set of size $\lambda_{i}\geq
2$), which in particular implies $x_{i-1}<y+0.1<x_{i}$. It now suffices to
show that there are at most $\sum_{j=1}^{\lambda_{i}-1}M_{\mu^{(j)}}$
different $e^{\prime}\in\mathcal{H}$ with
$y+0.1\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$. For every such
$e^{\prime}$, we have $1\leq|e^{\prime}\cap(x_{i-1},y+0.1)|\leq\lambda_{i}-1$
(recalling that $e^{\prime}\subseteq\mathbb{Z}$ and
$|e^{\prime}\cap(x_{i-1},x_{i})|=\lambda_{i}$).

For each $j=1,\dots,\lambda_{i}-1$, there can be at most $M_{\mu^{(j)}}$
different $e^{\prime}\in\mathcal{H}$ with $|e^{\prime}\cap(x_{i-1},y+0.1)|=j$.
Indeed, for each such $e^{\prime}\in\mathcal{H}$ we have
$|e^{\prime}\cap(y+0.1,x_{i})|=|e^{\prime}\cap(x_{i-1},x_{i})|-|e^{\prime}\cap(x_{i-1},y+0.1)|=\lambda_{i}-j$.
Hence, by considering
$x_{0},\dots,x_{i-1},y+0.1,x_{i},\dots,x_{s}\in\mathbb{R}\setminus\mathbb{Z}$,
we can observe that the collection $\mathcal{H}^{\prime}\subseteq\mathcal{H}$
of all $e^{\prime}\in\mathcal{H}$ with $|e^{\prime}\cap(x_{i-1},y+0.1)|=j$ is
$\mu^{(j)}$-partite. So by our assumption that (b) does not hold, there can be
at most $M_{\mu^{(j)}}$ different such $e^{\prime}\in\mathcal{H}$ (recall that
$\mu^{(j)}$ is an ordered partition of $r$ into $s+1$ parts with
$\lambda\succ\mu^{(j)}$).

Thus, in total there can be at most $\sum_{j=1}^{\lambda_{i}-1}M_{\mu^{(j)}}$
different $e^{\prime}\in\mathcal{H}$ with
$1\leq|e^{\prime}\cap(x_{i-1},y+0.1)|\leq\lambda_{i}-1$, meaning that there
are at most $\sum_{j=1}^{\lambda_{i}-1}M_{\mu^{(j)}}$ different
$e^{\prime}\in\mathcal{H}$ with
$y+0.1\in\operatorname{conv}(e^{\prime}\cap(x_{i-1},x_{i}))$. This finishes
the proof of the lemma. ∎

We are now ready to prove Theorem 1.2 using Observation 3.2 and Lemma 3.3. In
order to do so, we inductively show the following generalization of the
theorem.

######  Theorem 3.4.

Let $r$ be a positive integer, and let
$\lambda=(\lambda_{1},\dots,\lambda_{s})$ be an ordered partition of $r$. For
every collectable $r$-pattern $P$, consider a positive integer $m_{P}$. Let
$\mathcal{H}$ be a finite collection of pairwise disjoint subsets
$e\subseteq\mathbb{Z}$, each of size $|e|=r$, such that $\mathcal{H}$ is
$\lambda$-partite. Furthermore, assume that for every collectable $r$-pattern
$P$, every $P$-clique contained in $\mathcal{H}$ has size at most $m_{P}$.
Then the number of edges in $\mathcal{H}$ is bounded by

$|\mathcal{H}|\leq
2^{r-s}\sum_{\lambda^{(s)}\succ\lambda^{(s+1)}\succ\dots\succ\lambda^{(r)}}\
\prod_{P\in\mathcal{P}(\lambda^{(s)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$
(3.1)

where the sum is over all sequences
$\lambda^{(s)}\succ\lambda^{(s+1)}\succ\dots\succ\lambda^{(r)}$ of ordered
partitions of $r$ with $\lambda^{(s)}=\lambda$ (note that then for
$t=s,\dots,r$, the ordered partition $\lambda^{(t)}$ must automatically have
$t$ parts).

Note that Theorem 3.4 directly implies Theorem 1.2 by taking $\lambda=(r)$ to
be the ordered partition of $r$ into a single part. Also recall that Theorem
1.2 implies Theorem 1.1.

###### Proof of Theorem 3.4.

We prove the theorem by induction on $r-s$ (note that we always have $s\leq
r$). If $s=r$, i.e. if $\lambda=(1,1,\dots,1)$ is the unique ordered partition
of $r$ into $r$ parts, then $\mathcal{H}$ is automatically interval-wise
$\lambda$-partite. Thus, by Observation 3.2 we have

$|\mathcal{H}|\leq\prod_{P\in\mathcal{P}(\lambda)}m_{P}=2^{r-r}\sum_{\lambda^{(s)}\succ\dots\succ\lambda^{(r)}}\
\prod_{P\in\mathcal{P}(\lambda^{(s)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$

where the sum has only one summand corresponding to the unique length-1
sequence $\lambda^{(s)}\succ\dots\succ\lambda^{(r)}$ with
$\lambda^{(s)}=\lambda^{(r)}=\lambda$.

So let us now assume that $s<r$ and that we already proved the desired
statement for all smaller values of $r-s$. For every ordered partition
$\lambda^{\prime}$ of $r$ into $s+1$ parts with
$\lambda\succ\lambda^{\prime}$, let us define

$M_{\lambda^{\prime}}=2^{r-s-1}\sum_{\lambda^{(s+1)}\succ\lambda^{(s+2)}\succ\dots\succ\lambda^{(r)}}\
\prod_{P\in\mathcal{P}(\lambda^{(s+1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$

where the sum is over all sequences
$\lambda^{(s+1)}\succ\lambda^{(s+2)}\succ\dots\succ\lambda^{(r)}$ of ordered
partitions of $r$ with $\lambda^{(s+1)}=\lambda^{\prime}$. As in Lemma 3.3,
let $M=\sum_{\lambda^{\prime}}M_{\lambda^{\prime}}$ be the sum of these
$M_{\lambda^{\prime}}$ for all ordered partitions $\lambda^{\prime}$ of $r$
into $s+1$ parts with $\lambda\succ\lambda^{\prime}$. Then we have

$M=\sum_{\lambda^{\prime}}M_{\lambda^{\prime}}=2^{r-s-1}\sum_{\lambda^{(s)}\succ\lambda^{(s+1)}\succ\dots\succ\lambda^{(r)}}\
\prod_{P\in\mathcal{P}(\lambda^{(s+1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$

where on the right-hand side the sum is over all sequences
$\lambda^{(s)}\succ\lambda^{(s+1)}\succ\dots\succ\lambda^{(r)}$ of ordered
partitions of $r$ with $\lambda^{(s)}=\lambda$.

For every ordered partition $\lambda^{\prime}$ of $r$ into $s+1$ parts with
$\lambda\succ\lambda^{\prime}$, we can apply the inductive assumption for
$\lambda^{\prime}$, and conclude that for every $\lambda^{\prime}$-partite
sub-collection $\mathcal{H}^{\prime}\subseteq\mathcal{H}$, we must have
$|\mathcal{H}^{\prime}|\leq M_{\lambda^{\prime}}$. Thus, when applying Lemma
3.3 to $\mathcal{H}$ and $\lambda$, with the numbers $M_{\lambda^{\prime}}$ as
defined above, option (b) cannot happen. Hence option (a) must happen, and we
can find a sub-collection $\mathcal{H}^{*}\subseteq\mathcal{H}$ of size
$|\mathcal{H}^{*}|\geq|\mathcal{H}|/(2M)$ such that $\mathcal{H}^{*}$ is
interval-wise $\lambda$-partite. But now by Observation 3.2, we have

$|\mathcal{H}|/(2M)\leq|\mathcal{H}^{*}|\leq\prod_{P\in\mathcal{P}(\lambda)}m_{P}.$

This gives

$|\mathcal{H}|\leq
2M\cdot\prod_{P\in\mathcal{P}(\lambda)}m_{P}=2^{r-s}\sum_{\lambda^{(s)}\succ\lambda^{(s+1)}\succ\dots\succ\lambda^{(r)}}\
\prod_{P\in\mathcal{P}(\lambda^{(s)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$

as desired, where the sum on the right-hand side is again over all sequences
$\lambda^{(s)}\succ\lambda^{(s+1)}\succ\dots\succ\lambda^{(r)}$ of ordered
partitions of $r$ with $\lambda^{(s)}=\lambda$. ∎

##  4 Lower bound Construction

In this section, we prove Theorem 1.3, by giving a construction of a large
ordered hypergraph matching where all $P$-cliques have at most some given
sizes $m_{P}$. The construction is an appropriate multi-parameter
generalization of the argument from [1, Section 4]. We will actually prove the
following stronger form of Theorem 1.3.

######  Theorem 4.1.

Let $r$ be a positive integer, and let
$\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}$ be a sequence of
ordered partitions of $r$. For every $r$-pattern
$P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})$,
consider a positive integer $m_{P}$. Then there exists an ordered $r$-uniform
hypergraph matching $\mathcal{H}$ of size

$|\mathcal{H}|=\prod_{P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$

such that any two edges $e,f\in\mathcal{H}$ form an $r$-pattern in
$\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})$, and for
each $r$-pattern
$P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})$ every
$P$-clique contained in $\mathcal{H}$ has size at most $m_{P}$.

Note that Theorem 4.1 immediately implies Theorem 1.3 by taking
$\lambda^{(1)}\succ\lambda^{(2)}\succ\ldots\succ\lambda^{(r)}$ to be a
sequence of ordered partitions of $r$ achieving maximum in (1.2).

Following [1], for an ordered $r$-uniform hypergraph matching $\mathcal{H}$
and an $r$-pattern $P$, let $L_{P}(\mathcal{H})$ denote the size of the
largest $P$-clique contained in $\mathcal{H}$. Then the conditions on
$\mathcal{H}$ in Theorem 4.1 can be rephrased as $L_{P}(\mathcal{H})\leq
m_{P}$ for all $r$-patterns
$P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})$ and
$L_{P}(\mathcal{H})=1$ for all other $r$-patterns
$P\not\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})$.

An ordered $r$-uniform hypergraph matching $\mathcal{H}$ is _$r$ -partite_, if
in the underlying ordering of the vertex set is such that all the first
vertices of all the edges come before all the second vertices of all the
edges, which come before all the third vertices of all the edges, and so on.
More formally, we can say that $\mathcal{H}$ is $r$-partite, if as an ordered
$r$-uniform hypergraph matching $\mathcal{H}$ is isomorphic to a finite
collection of pairwise disjoint subsets $e\subseteq\mathbb{Z}$, each of size
$|e|=r$, which is $\lambda^{(r)}$-partite according to Definition 3.1 for the
unique ordered partition $\lambda^{(r)}=(1,\dots,1)$ of $r$ into $r$ parts.

For our construction proving Theorem 4.1, we will use a notion of a blow-up
introduced in [6] and later also used in [1].

######  Definition 4.2.

Let $\mathcal{H}$ and $\mathcal{H}_{r}$ be ordered $r$-uniform hypergraph
matchings such that $\mathcal{H}_{r}$ is $r$-partite. Then we define the blow-
up $\mathcal{H}[\mathcal{H}_{r}]$ to be the ordered $r$-uniform hypergraph
matching of size
$|\mathcal{H}[\mathcal{H}_{r}]|=|\mathcal{H}|\cdot|\mathcal{H}_{r}|$ defined
as follows. For the vertex set $\mathcal{H}[\mathcal{H}_{r}]$, starting with
$\mathcal{H}$, let us replace every vertex of $\mathcal{H}$ with
$|\mathcal{H}_{r}|$ copies of itself (right after each other as a contiguous
interval in the ordering of the vertex set). Then, for every edge
$e\in\mathcal{H}$, let us take a matching of $|\mathcal{H}_{r}|$ edges between
these copies of the vertices of $e$, in the shape prescribed by
$\mathcal{H}_{r}$.

More formally, this can be described when modelling $\mathcal{H}$ and
$\mathcal{H}_{r}$ by pairwise disjoint size-$r$ subsets of $\mathbb{Z}$. As
$\mathcal{H}_{r}$ is $r$-partite, there exists a sequence
$x_{0}<x_{1}<\ldots<x_{r}$ of real numbers such that
$|e\cap(x_{i-1},x_{i})|=1$ for all $i=1,\dots,r$ and all
$e\in\mathcal{H}_{r}$. Take a large integer $N$ such that $N>x_{i}-x_{i-1}$
for $i=1,\dots,r$, and define the blow-up $\mathcal{H}[\mathcal{H}_{r}]$ to be
the collection of size-$r$ subsets of $\mathbb{Z}$ of the form

$\\{Nx_{1}+y_{1},Nx_{2}+y_{2},\ldots,Nx_{r}+y_{r}\\}$

for all edges $\\{x_{1},\dots,x_{r}\\}\in\mathcal{H}$ with $x_{1}<\dots<x_{r}$
and all edges $\\{y_{1},\dots,y_{r}\\}\in\mathcal{H}_{r}$ with
$y_{1}<\dots<y_{r}$.

Note that up to an isomorphism of ordered $r$-uniform hypergraph matchings,
the second description in the definition above does not depend on the choice
of $N$ or the choices made when modelling $\mathcal{H}$ and $\mathcal{H}_{r}$
as collections of subsets of $\mathbb{Z}$.

For ordered $r$-uniform hypergraph matchings $\mathcal{H}$ and
$\mathcal{H}_{r}$ as in Definition 4.2, we have

$L_{P}(\mathcal{H}[\mathcal{H}_{r}])\leq
L_{P}(\mathcal{H})L_{P}(\mathcal{H}_{r})$ (4.1)

for every $r$-pattern $P$. Indeed, for any $P$-clique in
$\mathcal{H}[\mathcal{H}_{r}]$, the corresponding edges in $\mathcal{H}$ must
also form a $P$-clique (indeed, any two edges in
$\mathcal{H}[\mathcal{H}_{r}]$ coming from different edges in $\mathcal{H}$
form the same $r$-pattern as the corresponding two edges in $\mathcal{H}$).
Furthermore, for every edge $e\in\mathcal{H}$, the size of the largest
$P$-clique among the edges in $\mathcal{H}[\mathcal{H}_{r}]$ corresponding to
$e$ is bounded by $L_{P}(\mathcal{H}_{r})$ (indeed, such a $P$-clique in
$\mathcal{H}[\mathcal{H}_{r}]$ corresponds to a $P$-clique in
$\mathcal{H}_{r}$).

The other ingredient in our proof Theorem 4.1 is the following statement,
giving a construction of an $r$-partite ordered $r$-uniform hypergraph
matching $\mathcal{H}$ with prescribed bounds for the clique sizes
$L_{P}(\mathcal{H})$. This statement is a direct consequence of the second
part of Theorem‘2.1.

######  Observation 4.3.

Let $r$ be a positive integer, and let $\lambda^{(r)}=(1,\dots,1)$ be the
unique ordered partition of $r$ into $r$ parts. For every $r$-pattern
$P\in\mathcal{P}(\lambda^{(r)})$, consider a positive integer $m_{P}$. Then
there exists an $r$-partite ordered $r$-uniform hypergraph matching
$\mathcal{H}$ of size

$|\mathcal{H}|=\prod_{P\in\mathcal{P}(\lambda^{(r)})}m_{P},$

such that $L_{P}(\mathcal{H})\leq m_{P}$ for all $r$-patterns
$P\in\mathcal{P}(\lambda^{(r)})$ and $L_{P}(\mathcal{H})=1$ for all other
$r$-patterns $P\not\in\mathcal{P}(\lambda^{(r)})$.

We note that for any $r$-partite ordered $r$-uniform hypergraph matching
$\mathcal{H}$ we automatically have $L_{P}(\mathcal{H})=1$ for any
$P\not\in\mathcal{P}(\lambda^{(r)})$. Indeed, for any two edges
$e,f\in\mathcal{H}$, the first vertices of $e$ and $f$ are both before the
second vertices of $e$ and $f$, which are both before the third vertices of
$e$ and $f$ and so on. Hence the $r$-pattern formed by $e$ and $f$ consists of
$r$ blocks that each have one $\rm A$ and one $\rm B$, so the $r$-pattern has
a block partition into $r$ parts and therefore belongs to
$\mathcal{P}(\lambda^{(r)})$.

###### Proof of Observation 4.3.

Recall from the discussion at the end of Section 2 that any $r$-pattern
$P\in\mathcal{P}(\lambda^{(r)})$ is of the form $P=P(\lambda^{(r)},\tau)$ for
a unique function $\tau:\\{1,\dots,r\\}\to\\{1,-1\\}$ with $\tau(1)=1$. For
every such function $\tau$, let us define
$m_{\tau}=m_{P(\lambda^{(r)},\tau)}$. By the second part of Theorem 2.1, there
exists a collection of points $Z\subseteq\mathbb{R}^{r}$ of size
$|Z|=\prod_{\tau}m_{\tau}=\prod_{P\in\mathcal{P}(\lambda^{(r)})}m_{P}$ such
that the $|Z|\cdot r$ coordinates of all the points in $Z$ are all distinct,
and such that for every function $\tau:\\{1,\dots,r\\}\to\\{1,-1\\}$ with
$\tau(1)=1$, every $\tau$-monotone sequence in $Z$ has length at most
$m_{\tau}=m_{P(\lambda^{(r)},\tau)}$.

Without loss of generality, we may assume that all points in $Z$ have positive
coordinates (otherwise, we can translate the set $Z$ accordingly). Let $N>0$
be a number larger than all coordinates of all points in $Z$. Now, for every
point $z=(z_{1},\dots,z_{r})\in Z\subseteq\mathbb{R}^{r}$, let us define
$e(z)=\\{N+z_{1},2N+z_{2},\ldots,rN+z_{r}\\}\subseteq\mathbb{R}$, and note
that the sets $e(z)$ for $z\in Z$ are pairwise disjoint. Taking
$\mathcal{H}=\\{e(z)\mid z\in Z\\}$ to be the collection of the sets $e(z)$
for all $z\in Z$, we obtain an ordered $r$-uniform hypergraph $\mathcal{H}$ by
considering the natural ordering on $\mathbb{R}$ on the vertex set. Note that
$\mathcal{H}$ has size
$|\mathcal{H}|=|Z|=\prod_{P\in\mathcal{P}(\lambda^{(r)})}m_{P}$. Furthermore,
$\mathcal{H}$ is $r$-partite (by the choice of $N$) and so in particular we
have $L_{P}(\mathcal{H})=1$ for any $P\not\in\mathcal{P}(\lambda^{(r)})$. It
remains to check $L_{P}(\mathcal{H})\leq m_{P}$ for every
$P\in\mathcal{P}(\lambda^{(r)})$.

So let $P\in\mathcal{P}(\lambda^{(r)})$ and let
$\tau:\\{1,\dots,r\\}\to\\{1,-1\\}$ with $\tau(1)=1$ be such that
$P=P(\lambda^{(r)},\tau)$, then we have $m_{\tau}=m_{P}$. Let
$z^{(1)},\dots,z^{(t)}\in Z$ be such that the edges
$e(z^{(1)}),\dots,e(z^{(t)})$ form $P$-clique in $\mathcal{H}$. Then for any
$1\leq\ell<\ell^{\prime}\leq t$, for any $i\in\\{1,\dots,r\\}$ with
$\tau(i)=1$, the $i$-th vertex $iN+z^{(\ell)}_{i}$ of $e(z^{(\ell)})$ comes
before the $i$-th vertex $iN+z^{(\ell^{\prime})}_{i}$ of
$e(z^{(\ell^{\prime})})$ and so we have
$z^{(\ell)}_{i}<z^{(\ell^{\prime})}_{i}$. Similarly for any
$i\in\\{1,\dots,r\\}$ with $\tau(i)=1$, the $i$-th vertex of $e(z^{(\ell)})$
comes after the $i$-th vertex of $e(z^{(\ell^{\prime})})$ and so we have
$z^{(\ell)}_{i}>z^{(\ell^{\prime})}_{i}$. Thus, for every
$i\in\\{1,\dots,r\\}$ with $\tau(i)=1$, the $i$-th coordinates of the points
$z^{(1)},\dots,z^{(t)}$ form an increasing sequence
$z^{(1)}_{1}<\dots<z^{(t)}_{i}$, and for every $i\in\\{1,\dots,r\\}$ with
$\tau(i)=-1$, they form a decreasing sequence $z^{(1)}_{1}>\dots>z^{(t)}_{i}$.
Thus, $z^{(1)},\dots,z^{(t)}$ is a $\tau$-monotone sequence of points in $Z$
and hence $t\leq m_{\tau}\leq m_{P}$. This shows that $L_{P}(\mathcal{H})\leq
m_{P}$, as desired. ∎

Finally, we are ready to prove Theorem 4.1 (implying Theorem 1.2).

###### Proof of Theorem 4.1.

We prove the theorem by induction on $r$. Note that the base case $r=1$ is
trivial, so let us assume $r\geq 2$ and that we already proved the theorem for
$r-1$.

In the sequence $\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}$,
each ordered partition $\lambda^{(s)}$ for $s=1,\dots,r$ must have precisely
$s$ parts. In particular, the partition $\lambda^{(r-1)}$ has the form
$\lambda^{(r-1)}=(1,\dots,1,2,1,\dots,1)$. Let $j\in\\{1,\dots,r-1\\}$ be the
unique index such that $\lambda^{(r-1)}_{j}=2$. If we imagine
$\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r)}$ as partitions of
the set $\\{1,\dots,r\\}$ into intervals, then the partition $\lambda^{(r-1)}$
consists of the set $\\{j,j+1\\}$ and singleton sets for all the remaining
elements. Hence $j$ and $j+1$ are in the same set for each of the partitions
$\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r-1)}$. If we ignore
$j$ and relabel the remaining elements accordingly (i.e. $j+1$ is relabeled
$j$, $j+2$ is relabeled $j+1$, and so on),
$\lambda^{(1)}\succ\lambda^{(2)}\succ\dots\succ\lambda^{(r-1)}$ turns into a
sequence of ordered partitions
$\mu^{(1)}\succ\mu^{(2)}\succ\dots\succ\mu^{(r-1)}$ of $r-1$. For
$s=1,\dots,r-1$ we obtain $\lambda^{(j)}$ from $\mu^{(j)}$ by doubling the
element $j$ (keeping both copies in the same set of the partition), and
relabeling the ground set into $\\{1,\dots,r\\}$ accordingly.

Now, for $s=1,\dots,r-1$, every $r$-pattern $P\in\mathcal{P}(\lambda^{(s)})$
turns into an $(r-1)$-pattern $P^{\prime}\in\mathcal{P}(\mu^{(s)})$ when
omitting the $j$-th $\rm A$ and the $j$-th $\rm B$ in $P$ (note that these
occur in the same block, i.e. right adjacent to the $(j+1)$-th $\rm A$ and the
$(j+1)$-th $\rm B$, respectively). Conversely, $P$ can be recovered from
$P^{\prime}\in\mathcal{P}(\mu^{(s)})$ by doubling the $j$-th $\rm A$ in $P$
into $\rm{AA}$ and doubling the $j$-th $\rm B$ in $P$ into $\rm{BB}$. Thus,
these operations give natural bijections between $\mathcal{P}(\lambda^{(s)})$
and $\mathcal{P}(\mu^{(s)})$.

For every $(r-1)$-pattern
$P^{\prime}\in\mathcal{P}(\mu^{(1)})\cup\dots\cup\mathcal{P}(\mu^{(r-1)})$,
let us define $m_{P^{\prime}}=m_{P}$, where
$P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r-1)})$ is
the $r$-pattern obtained from $P^{\prime}$ by doubling the $j$-th $\rm A$ and
the $j$-th $\rm B$. Then, applying the induction hypothesis to the sequence
$\mu^{(1)}\succ\mu^{(2)}\succ\dots\succ\mu^{(r-1)}$ of ordered partitions of
$r-1$, we obtain an ordered $(r-1)$-uniform hypergraph matching
$\mathcal{H}^{\prime}$ of size

$|\mathcal{H}^{\prime}|=\prod_{P^{\prime}\in\mathcal{P}(\mu^{(1)})\cup\dots\cup\mathcal{P}(\mu^{(r-1)})}m_{P^{\prime}}=\prod_{P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r-1)})}m_{P},$

such that $L_{P^{\prime}}(\mathcal{H}^{\prime})\leq m_{P^{\prime}}$ for all
$(r-1)$-patterns
$P^{\prime}\in\mathcal{P}(\mu^{(1)})\cup\dots\cup\mathcal{P}(\mu^{(r-1)})$ and
$L_{P^{\prime}}(\mathcal{H}^{\prime})=1$ for all other $(r-1)$-patterns
$P^{\prime}\not\in\mathcal{P}(\mu^{(1)})\cup\dots\cup\mathcal{P}(\mu^{(r-1)})$.

From $\mathcal{H}^{\prime}$, we can now obtain an ordered $r$-uniform
hypergraph matching $\mathcal{H}^{*}$ with
$|\mathcal{H}^{*}|=|\mathcal{H}^{\prime}|$ by doubling the $j$-th element of
every edge $e^{\prime}\in\mathcal{H}^{\prime}$. More formally, for every edge
$e^{\prime}\in\mathcal{H}^{\prime}$, we add a new element to $e^{\prime}$
right before the $j$-the element of $e^{\prime}$ (in the given ordering of the
underlying vertex set of $\mathcal{H}^{\prime}$). For the resulting edge
$e\in\mathcal{H}^{*}$, we can recover the original edge
$e^{\prime}\in\mathcal{H}^{\prime}$ by deleting the $j$-the element of $e$. If
$e,f\in\mathcal{H}^{*}$ form some $r$-pattern $P$, then the $(r-1)$-pattern
formed by the corresponding edges
$e^{\prime},f^{\prime}\in\mathcal{H}^{\prime}$ is the $(r-1)$-pattern
$P^{\prime}$ obtained from $P$ by omitting the $j$-th $\rm A$ and the $j$-th
$\rm B$. Thus, by the properties of $\mathcal{H}^{\prime}$, we have
$L_{P}(\mathcal{H})\leq m_{P}$ for all $r$-patterns
$P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r-1)})$ and
$L_{P}(\mathcal{H})=1$ for all other $r$-patterns
$P\not\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r-1)})$.

Finally, recall that $\lambda^{(r)}=(1,\dots,1)$ is the unique ordered
partition of $r$ into $r$ parts. Let $\mathcal{H}_{r}$ be an $r$-partite
ordered $r$-uniform hypergraph matching as in Observation 4.3. Now, the blow-
up $\mathcal{H}=\mathcal{H}^{*}[\mathcal{H}_{r}]$ has size

$|\mathcal{H}|=|\mathcal{H}^{*}|\cdot|\mathcal{H}_{r}|=|\mathcal{H}^{\prime}|\cdot|\mathcal{H}_{r}|=\prod_{P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r-1)})}m_{P}\cdot\prod_{P\in\mathcal{P}(\lambda^{(r)})}m_{P}=\prod_{P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})}m_{P},$

and by (4.1) for every $r$-pattern $P$ we have $L_{P}(\mathcal{H})\leq
L_{P}(\mathcal{H}^{*})\cdot L_{P}(\mathcal{H}_{r})$. Hence
$L_{P}(\mathcal{H})\leq m_{P}\cdot 1=m_{P}$ for all
$P\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r-1)})$, and
$L_{P}(\mathcal{H})\leq 1\cdot m_{P}=m_{P}$ for all
$P\in\mathcal{P}(\lambda^{(r)})$, and also $L_{P}(\mathcal{H})\leq 1\cdot 1=1$
for all
$P\not\in\mathcal{P}(\lambda^{(1)})\cup\dots\cup\mathcal{P}(\lambda^{(r)})$.
Thus, we have constructed the desired ordered $r$-uniform hypergraph matching
$\mathcal{H}$. ∎

## References

  * [1] Michael Anastos, Zhihan Jin, Matthew Kwan, and Benny Sudakov “Extremal, enumerative and probabilistic results on ordered hypergraph matchings.” arXiv preprint arXiv:2308.12268 (2023).
  * [2] Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe. “An exponential improvement for diagonal Ramsey.” arXiv preprint arXiv:2303.09521 (2023).
  * [3] Yair Caro. “New Results on the Independence Number.” Technical Report, Tel-Aviv University, 1979.
  * [4] Recep Altar Çiçeksiz, Recep Altar, Zhihan Jin, Eero Räty, and István Tomon. “Exponential Erdő s-Szekeres theorem for matrices.” arXiv preprint arXiv:2305.07003 (2023).
  * [5] Robert P. Dilworth “A Decomposition Theorem for Partially Ordered Sets.” Annals of Mathematics (1950): 161–166.
  * [6] Andrzej Dudek, Jarosław Grytczuk, and Andrzej Ruciński. “Ordered unavoidable sub-structures in matchings and random matchings.” arXiv preprint arXiv:2210.14042 (2022).
  * [7] Andrzej Dudek, Jarosław Grytczuk, and Andrzej Ruciński. “Erdős-Szekeres type Theorems for ordered uniform matchings.” arXiv preprint arXiv:2301.02936 (2023).
  * [8] Paul Erdős and George Szekeres. “A combinatorial problem in geometry.” Compositio mathematica 2 (1935): 463–470.
  * [9] Timothy W. Gowers and Jason Long. “The length of an s-increasing sequence of r-tuples.” Combinatorics, Probability and Computing 30, no. 5 (2021): 686–721.
  * [10] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Ramsey theory. Vol. 20. John Wiley & Sons, 1991.
  * [11] Choongbum Lee. “Ramsey numbers of degenerate graphs.” Annals of Mathematics 185, no. 3 (2017): 791–829.
  * [12] Nathan Linial and Michael Simkin. “Monotone subsequences in high-dimensional permutations.” Combinatorics, Probability and Computing 27, no. 1 (2018): 69–83.
  * [13] Sam Mattheus and Jacques Verstraete. “The asymptotics of $r(4,t)$.” arXiv preprint arXiv:2306.04007 (2023).
  * [14] Leon Mirsky. “A dual of Dilworth’s decomposition theorem.” Amer. Math. Monthly 78, no. 8 (1971): 876-877.
  * [15] Guy Moshkovitz and Asaf Shapira. “Ramsey theory, integer partitions and a new proof of the Erdős–Szekeres theorem.” Advances in Mathematics 262 (2014): 1107–1129.
  * [16] Hans Jürgen Prömel. Ramsey theory for discrete structures. Vol. 3. New York: Springer, 2013.
  * [17] Christian Reiher, and Vojtěch Rödl. “The girth Ramsey theorem.” arXiv preprint arXiv:2308.15589 (2023).
  * [18] Tibor Szabó and Gábor Tardos. “A multidimensional generalization of the Erdős–Szekeres lemma on monotone subsequences.” Combinatorics, Probability and Computing 10, no. 6 (2001): 557–565.
  * [19] Victor K. Wei. “A Lower Bound on the Stability Number of a Simple Graph.” Technical memorandum, TM 81-11217-9, Bell Laboratories, 1981.


# Deep Generative SToRM model for dynamic imaging

###### Abstract

We introduce a novel generative smoothness regularization on manifolds (SToRM)
model for the recovery of dynamic image data from highly undersampled
measurements. The proposed generative framework represents the image time
series as a smooth non-linear function of low-dimensional latent vectors that
capture the cardiac and respiratory phases. The non-linear function is
represented using a deep convolutional neural network (CNN). Unlike the
popular CNN approaches that require extensive fully-sampled training data that
is not available in this setting, the parameters of the CNN generator as well
as the latent vectors are jointly estimated from the undersampled measurements
using stochastic gradient descent. We penalize the norm of the gradient of the
generator to encourage the learning of a smooth surface/manifold, while
temporal gradients of the latent vectors are penalized to encourage the time
series to be smooth. The main benefits of the proposed scheme are (a) the
quite significant reduction in memory demand compared to the analysis based
SToRM model, and (b) the spatial regularization brought in by the CNN model.
We also introduce efficient progressive approaches to minimize the
computational complexity of the algorithm.

##  1 Introduction

The quest for high spatial and temporal resolution is central to several
dynamic imaging problems, ranging from MRI, video imaging, to microscopy. A
popular approach to improve spatio-temporal resolution is self-gating, where
cardiac and respiratory information is estimated from navigator or central
k-space using bandpass filtering or clustering, followed by binning and
reconstruction [1, 2]. Several authors have also introduced smooth manifold
regularization, which models the images in the time series as points on a high
dimensional manifold [3, 4, 5]. This approach may be viewed as an implicit
soft-gating alternative to self-gating methods. Manifold methods including our
smoothness regularization on manifolds (SToRM) approach has been demonstrated
in a variety of dynamic imaging applications with good performance [3, 4, 5].
Since the data is not explicitly binned into a specific phase, manifold
methods are not vulnerable to potential errors in clustering the time series
based on navigators. Despite the benefits, a key challenge with current
manifold methods is the high memory demand. Unlike self-gating methods that
only recover the specific phases, manifold schemes recover the entire time
series. This approach restricts the extension of the framework to higher
dimensional problems. The high memory demand also makes it difficult to use
additional spatial and temporal regularization.

The main focus of this work is to exploit the power of deep convolutional
neural networks (CNN) to introduce an improved and memory efficient
generative/synthesis formulation of SToRM. Unlike current manifold and self-
gating methods, this approach does not require k-space navigators to estimate
the motion states. Besides, unlike traditional CNN based approaches, the
proposed scheme does not require extensive training data, which is challenging
to acquire in free-breathing applications. We note that current manifold
methods can be viewed as an analysis formulation. Specifically, a non-linear
injective mapping is applied on the images such that the mapped points of the
alias-free images lie on a low-dimensional subspace. When recovering from
undersampled data, the nuclear norm prior is applied in the transform domain
to encourage their non-linear mappings to lie in a subspace. Unfortunately,
this analysis approach requires the storage of all the image frames in the
time series. In this work, we model the images in the time series as non-
linear mappings
$\mathbf{\rho}_{t}=\mathcal{G}_{\theta}\left(\mathbf{z}_{t}\right)$, where
$\mathbf{z}_{i}$ are vectors that live in a very low-dimensional subspace. The
dimension of the subspace can be very small (e.g 2-4) in practical
applications. We represent the non-linear mapping using a convolution neural
network with weights $\theta$. The memory footprint of the algorithm depends
on the number of parameters $\theta$ and $z$, which is orders of magnitude
smaller than that of traditional manifold methods.

Fig. 1: (a) Analysis SToRM and (b) Generative SToRM. The analysis formulation
[4, 6] in (a) minimizes the nuclear norm of the non-linear mappings
$\varphi(\mathbf{x}_{i})$ of the images $\mathbf{x}_{i}$ to encourage them to
be in a subspace. By contrast, the proposed formulation expresses the images
as non-linear mappings $\mathcal{G}_{\theta}(\mathbf{z}_{i})$ of the low-
dimensional latent vectors $\mathbf{z}_{i}$. The main benefit of the
generative model is its ability to compress the data, thus offering a memory
efficient algorithm.

We propose to jointly optimize for the network parameters $\theta$ and the
latent vector $\mathbf{z}$ such that the cost
$\sum_{i}\|\mathcal{A}_{t}(\mathcal{G}_{\theta}\mathbf{z}_{t})-\mathbf{b}_{i}\|^{2}$
is minimized during image reconstruction. The smoothness of the manifold
generated by $\mathcal{G}_{\theta}(\mathbf{z})$ depends on the gradient of
$\mathcal{G}_{\theta}$ with respect to its input. To obtain a smooth manifold,
we regularize the gradient of the mapping
$\|\nabla_{z}\mathcal{G}_{\theta}\|^{2}$. Similarly, the images in the time
series are expected to vary smoothly in time. Hence, we also use a Tikhonov
smoothness penalty on the latent vectors $\mathbf{z}_{t}$ to further constrain
the solutions. Unlike traditional CNN methods that are fast during
testing/inference, the direct application of this scheme to the dynamic MRI
setting is computationally expensive. We use a three-step progressive-in-time
approach to significantly reduce the computational complexity of the
algorithm. Specifically, we grow the number of frames in the datasets during
the optimization process. The latent vectors from the previous iteration are
linearly interpolated to initialize the latent vectors. We observe that the
use of the progressive-in-time approach significantly reduces the
computational complexity of the algorithm.

The proposed approach is inspired by deep image prior (DIP) [7], which was
introduced for static imaging problems. We note that the extension of DIP to
dynamic imaging was considered in [8]. The key difference of the proposed
formulation from the above work is the joint optimization of the latent
variables $\mathbf{z}$, unlike the above method that chooses $\mathbf{z}$ as
random or interpolated versions of random vectors. Another key distinction is
the use of regularization priors on the network parameters and latent vectors,
which ensures that the scheme learns meaningful latent vectors and the
performance of the network does not degrade with iterations as in traditional
DIP methods.

##  2 Methods

Smooth manifold methods model images $\mathbf{x}_{i}$ in the dynamic time
series as points on a smooth manifold. In SToRM, the exponential (injective)
functions of the images denoted by $\varphi(\mathbf{x}_{i})$ of the alias-free
images are assumed to lie on a low-dimensional subspace. See Fig. 1.(a). The
joint recovery of the images denoted by the matrix
$\mathbf{X}=\left[\mathbf{x}_{1},..\mathbf{x}_{N}\right]$ from undersampled
data is posed as a nuclear norm minimization problem

$\mathbf{X}^{*}=\arg\min_{\mathbf{X}}\|\mathcal{A}(\mathbf{X})-\mathbf{B}\|^{2}+\lambda~{}\|\left[\varphi(\mathbf{x}_{1}),..,\varphi\\_\\{t\\}(\mathbf{x}_{N})\right]\|_{*}$
(1)

To overcome the challenges with the above analysis scheme, we propose to model
the images in the time series as

$\mathbf{x}_{i}=\mathcal{G}_{\theta}(\mathbf{z}_{i}),$ (2)

where $\mathcal{G}_{\theta}$ is a non-linear mapping. We realize
$\mathcal{G}_{\theta}$ using a deep convolutional neural network, inspired by
the extensive work on generative image models. Here, $\mathbf{z}_{i}$ are
latent vectors that lie in a low-dimensional subspace. As $\mathbf{z}_{i}$
vary in the subspace, their non-linear mappings vary on the image manifold.
The mapping $\mathcal{G}_{\theta}$ may be viewed as the inverse of the
injective mapping $\varphi$ considered in analysis SToRM; rather than mapping
the images to a low-dimensional subspace as in classical SToRM methods we now
propose to express the images as non-linear functions of latent variables
living in a low-dimensional subspace. See Fig. 1.(b).

The smoothness of the manifold is determined by the gradient of the non-linear
mapping, denoted by $\nabla_{\mathbf{z}}\mathcal{G}_{\theta}$. A mapping with
high gradient values can result in very similar latent vectors being mapped to
very different images. To minimize this risk, we propose to penalize the
$\ell_{2}$ norm of the gradients of the network, denoted by
$\|\nabla_{\mathbf{z}}\mathcal{G}_{\theta}\|^{2}$. We term this prior as
network regularizer. We expect the adjacent time frames in the time series to
be similar; we propose to add a temporal smoothness regularizer on the latent
vectors. The parameters of the network $\theta$ as well as the low-dimensional
latent vector $\mathbf{z}$ are estimated from the measured data by minimizing

$\displaystyle\mathcal{C}(\mathbf{z},\theta)$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\|\mathcal{A}_{i}\left(\mathcal{G}_{\theta}[\mathbf{z}_{i}]\right)-\mathbf{b}\|^{2}+\lambda_{1}\underbrace{\|\nabla_{\mathbf{z}}\mathcal{G}_{\theta}\|^{2}}_{\scriptsize\mbox{network
regularization}}$ (3)
$\displaystyle\qquad+\lambda_{2}\underbrace{\|\nabla_{t}\mathbf{z}_{t}\|^{2}}_{\scriptsize\mbox{temporal
regularization}}$

with respect to $\mathbf{z}$ and $\theta$. We initialize the network
parameters and latent vectors to be random variables.

We use ADAM optimization to determine the optimal parameters. Note that the
first and the second term in the expression is separable over $i$. To keep
memory demand of the algorithm low, we propose to choose mini-batches
consisting of random subset of frames. A key benefit of this framework over
conventional neural network schemes is that it does not require any training
data. Note that it is often impossible to acquire fully-sampled training data
in dynamic imaging applications.

The main benefit of this model is the compression offered by the
representation; the number of parameters of the model in (2) is orders of
magnitude smaller than the number of pixels in the dataset. The dramatic
compression offered by the representation, together with the mini-batch
training provides a memory efficient alternative to analysis SToRM [3, 4].
Although our focus is on establishing the utility of the scheme in 2-D
settings in this paper, the approach can be readily translated to higher
dimensional applications. Another benefit is the implicit spatial
regularization brought in by the generative CNN. Specifically, CNNs are
ideally suited to represent images rather than noise-like alias artifacts [7].

Fig. 2: Reconstruction performance with progressive training in time and
without progressive training in time. From the plot, one can see that
progressive training in time produces better results with much less running
time comparing to the training without progressive in time.

Fig. 3: Impact of network regularization and latent variable regularization.
The SER vs epoch plots are shown above, while two of the reconstructed images,
their time profiles, and recovered latent variables are shown. We note that
the blue curve captures respiratory motion, while the orange one captures
cardiac motion.

###  2.1 Progressive in time training

While the generative SToRM approach significantly reduces the memory demand, a
challenge with this approach is the increased computational complexity. To
minimize the complexity, we propose to use a progressive optimization
strategy. Specifically, we solve for a sequence of vectors $\mathbf{z}_{0}$,
$\mathbf{z}_{1}$,.., $\mathbf{z}_{M}$ each corresponding to increasing number
of time frames. For instance, in this work we choose $\mathbf{z}_{0}$ to be a
$2\times 1$ vector, where we consider the recovery of an average image
$\mathcal{G}_{\theta}(\mathbf{z}_{0})=\mathbf{x}_{0}$ from the entire data. We
solve for the optimal $\theta_{0}$ and $\mathbf{z}_{0}$ by minimizing (1).
Since we are solving for a single image, this optimization is fast. Following
convergence, the latent vector $\\{\mathbf{z}_{0}\\}$ is linearly interpolated
to the size of $\mathbf{z}_{1}$ and used along with $\theta_{0}$ as
initialization, while solving for
$\left\\{\theta_{1},\mathbf{z}_{1}\right\\}$. This approach significantly
reduces the computational complexity as seen from our experiments

Fig. 4: Comparison of Generative SToRM, Analysis SToRM, time dependent deep
image prior.

##  3 Experiments

###  3.1 Dataset and imaging experiments

All the experiments in this paper are based on a whole-heart multi-slice
dataset collected in the free-breathing mode using a golden angle spiral
trajectory. The acquisition of the data was performed on a GE 3T scanner. The
sequence parameters were: TR= 8.4 ms, FOV= 320 mm x 320 mm, flip angle= 18
degrees, slice thickness= 8 mm.

Results were generated using an Intel Xeon CPU at 2.40 GHz and a Tesla
P100-PCIE 16GB GPU. Results in §4.2, §4.3 were based on the first slice in the
dataset, and results in §4.4, §4.5 were based on the second slice in the
dataset. We binned the data from six spiral interleaves corresponding to 50 ms
temporal resolution. The entire dataset corresponds to 522 frames. We omit the
first 22 frames and used the remaining 500 frames for SToRM reconstructions,
which is used as ground truth for comparisons. In all the studies, we assumed
the latent variables to be two dimensional since the main source of
variability in the data correspond to cardiac and respiratory motion.

###  3.2 Benefit of progressive in time approach

We demonstrate the quite significant reduction in running time offered by the
progressive training strategy described in Section 2.1 in Fig. 2. Here, we
consider the recovery from 150 frames with and without the progressive
strategy. We plot the reconstruction performance, measured by the Signal-to-
Error Ratio (SER) with respect to the running time. The results show that the
proposed scheme can offer good reconstructions in $\approx 200$ seconds, which
is better than the direct approach that takes more than 2000 seconds.

###  3.3 Impact of regularization priors

We study the impact of network regularization priors in Fig. 3.(a), where we
show the reconstruction performance with respect to the number of epochs. The
recovered latent variables are also shown in the plots. We chose
$\lambda_{2}=2$ in this experiment. We note that unlike the case without
network regularization, the SER of the regularized reconstruction increases
with iteration. The case without regularization will start to fit to the noise
with iterations as in the case of deep image prior. We note that with
regularization, the latent variables capture cardiac (orange curve) and
respiratory (orange curve) motion, even though no explicit priors or
additional information (e.g navigators) about cardiac or respiratory rates
were used. Without network regularization, we observe increased mixing of the
cardiac and respiratory patterns in the latent vectors.

In the cost function (3), we also have the temporal smoothness regularization
of the latent variables. We compare $\lambda_{2}=2$ against $\lambda_{2}=0$,
while $\lambda_{1}$ was fixed as $0.001$. Similar to the network
regularization setting, we observe that the performance of the un-regularized
algorithm falls with iterations, while the performance of the regularized
approach increases or plateau with iterations. We also obsrved significant
mixing between cardiac and respiratory patterns in the latent variables when
no regularization is used.

###  3.4 Comparison with existing methods

We compare the proposed generative SToRM approach with analysis SToRM [6] and
time dependent deep image prior algorithm [8]. We use the k-space data of 150
frames for the reconstructions. The reconstruction results are shown in Fig.
4. The results show that the generative SToRM approach is able to reduce noise
and alias artifacts compared to analysis SToRM, offering around 1dB
improvement in performance. We attribute the improved performance to spatial
regularization offered by the CNN generator, which is absent in the analysis
SToRM formulation. The reconstruction time of both the algorithms are
comparable. The Time-DIP scheme, which assumes the latent variables to be
fixed as random values results in increased artifacts and blurring of motion
details. We note that unlike the analysis schemes, the proposed scheme does
not use k-space navigators to estimate the motion states; the latent variables
are estimated from the measured k-space data itself.

##  4 Conclusion

We introduce a generative manifold representation for the recovery of dynamic
image data from highly undersampled measurements. The deep CNN generator is
used to lift low-dimensional latent vectors to the smooth image manifold and
this proposed scheme does not require fully-sampled training data. We jointly
optimize the CNN generator parameters and the latent vectors based on the
undersampled data. We also proposed the training-in-time approch to minimize
the computational complexity of the algorithm. During the training, the norm
of the gradients of the generator is penalized to the learning of a smooth
surface/manifold, while temporal gradients of the latent vectors are penalized
to encourage the time series to be smooth. Comparisons with existing methods
suggest the utility of the proposed scheme in dynamic images.

##  5 Compliance with Ethical Standards

This research study was conducted using human subject data. The institutional
review board at the local institution approved the acquisition of the data,
and written consent was obtained from the subject.

##  6 Acknowledgments

This work is supported by grants NIH 1R01EB019961-01A1 and R01EB019961-02S.
The authors claim that there is no conflicts of interest.

## References

  * [1] Li Feng, Robert Grimm, Kai Tobias Block, Hersh Chandarana, Sungheon Kim, Jian Xu, Leon Axel, Daniel K Sodickson, and Ricardo Otazo,  “Golden-angle radial sparse parallel mri: combination of compressed sensing, parallel imaging, and golden-angle radial sampling for fast and flexible dynamic volumetric mri,”  Magnetic resonance in medicine, vol. 72, no. 3, pp. 707–717, 2014\.
  * [2] Anthony G Christodoulou, Jaime L Shaw, Christopher Nguyen, Qi Yang, Yibin Xie, Nan Wang, and Debiao Li,  “Magnetic resonance multitasking for motion-resolved quantitative cardiovascular imaging,”  Nature biomedical engineering, vol. 2, no. 4, pp. 215–226, 2018\.
  * [3] Sunrita Poddar and Mathews Jacob,  “Dynamic mri using smoothness regularization on manifolds (storm),”  IEEE transactions on medical imaging, vol. 35, no. 4, pp. 1106–1115, 2015.
  * [4] Sunrita Poddar, Yasir Q Mohsin, Deidra Ansah, Bijoy Thattaliyath, Ravi Ashwath, and Mathews Jacob,  “Manifold recovery using kernel low-rank regularization: Application to dynamic imaging,”  IEEE Transactions on Computational Imaging, vol. 5, no. 3, pp. 478–491, 2019.
  * [5] Ukash Nakarmi, Yanhua Wang, Jingyuan Lyu, Dong Liang, and Leslie Ying,  “A kernel-based low-rank (klr) model for low-dimensional manifold recovery in highly accelerated dynamic mri,”  IEEE transactions on medical imaging, vol. 36, no. 11, pp. 2297–2307, 2017.
  * [6] Abdul Haseeb Ahmed, Ruixi Zhou, Yang Yang, Prashant Nagpal, Michael Salerno, and Mathews Jacob,  “Free-breathing and ungated dynamic mri using navigator-less spiral storm,”  IEEE Transactions on Medical Imaging, 2020.
  * [7] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky,  “Deep image prior,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 9446–9454.
  * [8] Kyong Hwan Jin, Harshit Gupta, Jerome Yerly, Matthias Stuber, and Michael Unser,  “Time-dependent deep image prior for dynamic mri,”  arXiv preprint arXiv:1910.01684, 2019.